CPC: Complementary Progress Constraints for Time-Optimal Quadrotor Trajectories
This addresses a key bottleneck in mobile robotics like drone racing by enabling faster and more efficient trajectory generation, though it appears incremental as it builds on existing optimization methods.
The paper tackled the problem of generating time-optimal trajectories for quadrotors through multiple waypoints by introducing complementary progress constraints, enabling simultaneous optimization of trajectory and time-allocation, resulting in the first approach for truly time-optimal planning.
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 complementarity 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 complementarity 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.