Generating Dynamically Feasible Trajectories for Quadrotor Cameras

Mike Roberts

Pat Hanrahan

Stanford University

ACM Transactions on Graphics 35(4) (SIGGRAPH 2016)

Featured in the SIGGRAPH 2016 Technical Papers Trailer

Figure: Our algorithm for generating feasible quadrotor camera trajectories. Our algorithm takes as input a infeasible quadrotor camera trajectory (top row, left) and produces as output a feasible trajectory that is as similar as possible to the input trajectory (top row, right). By design, our algorithm does not change the spatial layout or visual contents of the input trajectory. Instead, our algorithm guarantees the feasibility of the output trajectory by re-timing the input trajectory, perturbing its timing as little as possible while remaining within velocity and control force limits (top row, insets). Our algorithm runs at interactive rates, solving for the feasible trajectory shown above in less than 2 seconds. Infeasible trajectories can be unsafe to fly on real quadrotor cameras, but we can safely fly the feasible trajectories generated by our algorithm, producing real video footage that is faithful to a Google Earth shot preview (bottom row).

Paper | Code (coming soon...) | Data (coming soon...)

Abstract: When designing trajectories for quadrotor cameras, it is important that the trajectories respect the dynamics and physical limits of quadrotor hardware. We refer to such trajectories as being feasible. In this paper, we introduce a fast and user-friendly algorithm for generating feasible quadrotor camera trajectories. Our algorithm takes as input an infeasible trajectory designed by a user, and produces as output a feasible trajectory that is as similar as possible to the user's input. By design, our algorithm does not change the spatial layout or visual contents of the input trajectory. Instead, our algorithm guarantees the feasibility of the output trajectory by re-timing the input trajectory, perturbing its timing as little as possible while remaining within velocity and control force limits. Our choice to perturb the timing of a shot, while leaving the spatial layout and visual contents of the shot intact, leads to a well-behaved non-convex optimization problem that can be solved at interactive rates.

We implement our algorithm in an open-source tool for designing quadrotor camera shots, where we achieve interactive performance across a wide range of camera trajectories. We demonstrate that our algorithm is between 25x and 45x faster than a spacetime constraints approach implemented using a commercially available solver. As we scale to more finely discretized trajectories, this performance gap widens, with our algorithm outperforming spacetime constraints by between 90x and 180x. Finally, we fly 5 feasible trajectories generated by our algorithm on a real quadrotor camera, producing video footage that is faithful to Google Earth shot previews, even when the trajectories are at the quadrotor's physical limits.

@article{roberts:2016,
    author  = {Mike Roberts AND Pat Hanrahan},
    title   = {Generating Dynamically Feasible Trajectories for Quadrotor Cameras},
    journal = {ACM Transactions on Graphics (Proc. SIGGRAPH 2016)},
    volume  = {35},
    number  = {4},
    year    = {2016}
}

Acknowledgements: We thank the anonymous reviewers for their valuable feedback; Niels Joubert for his assistance in collecting video footage; Anh Truong for her support in modifying the Horus user interface; Mackenzie Leake for her assistance in preparing the supplementary video; Jane E for narrating the supplementary video; Ross Daly for his assistance in preparing figures; Enzo Busseti for his assistance with an early version of the optimization problem in this paper; Stephen Boyd and Ron Fedkiw for their helpful and lively discussions; and 3D Robotics for their generous hardware support. This work was supported in part by a NSERC Alexander Graham Bell Canada Graduate Scholarship. Finally, we dedicate this paper in loving memory of our dear friend and valued collaborator, Floraine Berthouzoz.