Exact Convex Relaxation Using Supporting Hyperplane for Trajectory Optimization of UAVs

This paper investigates the minimum-time trajectory optimization problem for unmanned aerial vehicles (UAVs) with practical constraints on velocity, thrust acceleration, and thrust direction. We present how to obtain its exact convex relaxation based on the concept of supporting hyperplane. A convex relaxation of the original problem is obtained by equivalent convexification of the dynamics and relaxing a nonlinear equality constraint. To make the convex relaxation exact, our contribution lies in proposing a method of replacing the objective function by a parameterized one and achieving exactness of the convex relaxation by iteratively updating one parameter. This innovative method is inspired by finding an appropriate supporting hyperplane to support the feasible set at the solution of the original problem. Based on the proposed method, we can design an algorithm to very efficiently find the solution of the original problem, and convergence is theoretically ensured. The proposed method can be readily extended to missions with obstacle avoidance constraints, where such constraints are simply linearized. We can design a double-loop algorithm, which has very robust convergence, to find minimum-time collision-free trajectories. Numerical examples are provided to demonstrate the effectiveness and high efficiency of the algorithms.