Time-optimal planning for quadrotors: reaching constant computation costs for arbitrary distance

We tackle the challenge of time-optimal planning for quadrotors aiming for long-distance flights. State-of-the-art methods favor discretized state-space representation for its capacity to generate sharp state changes. However, they are haunted by the formidable computation cost when the destination is far because the number of optimization variables needs to be increased correspondingly to maintain a small sampling time. In addition, it is challenging to formulate the problem in the case that the end time is unknown a prior. We present a novel methodology that can achieve a near-constant computation cost (i.e., time and memory) for arbitrary target distances while keeping a high solution accuracy. This approach can handle the full quadrotor dynamics and actuator constraint in terms of the single-rotor thrust, and scale very well to waypoint-flight scenarios. The key idea is that while the required duration grows with the distance, the structure of optimal trajectories remains consistent. We begin by analyzing the properties of time-optimal maneuver via the Pontryagin Maximum Principle, using which the minimal representation of the optimal trajectory can be developed. Then, we optimize the trajectory coefficients to reach a minimum trajectory duration without violating any system constraint. Extensive numerical studies are conducted to verify its superior efficiency and solution quality. It only yields a 1.7% longer duration compared to the discretization-based method on the Split-S race track, yet it is ten times faster in computation. We demonstrate a peak velocity of 8.72 m/s in real-world experiments.

Preprint