CPC: Complementary Progress Constraints for Time-Optimal Quadrotor Trajectories

In many mobile robotics scenarios, such as drone racing, the goal is to generate a trajectory that passes through multiple waypoints in minimal time. This problem is referred to as time-optimal planning. State-of-the-art approaches either use polynomial trajectory formulations, which are suboptimal due to their smoothness, or numerical optimization, which requires waypoints to be allocated as costs or constraints to specific discrete-time nodes. For time-optimal planning, this time-allocation is a priori unknown and renders traditional approaches incapable of producing truly time-optimal trajectories. We introduce a novel formulation of progress bound to waypoints by a complementary constraint. While the progress variables indicate the completion of a waypoint, change of this progress is only allowed in local proximity to the waypoint via complementary
constraints. This enables the simultaneous optimization of the trajectory and the time-allocation of the waypoints. To the best of our knowledge, this is the first approach allowing for truly time-optimal trajectory planning for quadrotors and other systems. We perform and discuss evaluations on optimality and convexity, compare to other related approaches, and qualitatively to an expert-human baseline.

Reference:
"CPC: Complementary Progress Constraints for Time-Optimal Quadrotor Trajectories"
P. Foehn, D. Scaramuzza
arXiv preprint: http://arxiv.org/abs/2007.06255

This talk is part of the "Robotics, Science and Systems" 2020 Workshop on "Perception and Control for Fast and Agile Super-Vehicles"
Website: https://mit-fast.github.io/WorkshopRS...
YouTube: WS1-8: Perception and Control for Fas...

Check out our research on:
Drone Racing: http://rpg.ifi.uzh.ch/research_drone_...
Aggressive Vision-Based Flight: http://rpg.ifi.uzh.ch/aggressive_flig...

Affiliations: The authors are with the Robotics and Perception Group, Dep. of informatics, University of Zurich, and Dep. of Neuroinformatics, University of Zurich and ETH Zurich, Switzerland http://rpg.ifi.uzh.ch/