MILP and NLP techniques for centralized trajectory planning of multiple unmanned air vehicles

Abstract

We consider the problem of optimal cooperative three-dimensional conflict resolution involving multiple Unmanned Air Vehicles (UAVs) using numerical trajectory optimization methods. The conflict problem is posed as an optimal control problem of finding trajectories that minimize a certain objective function while maintaining the safe separation between each UAV pair. We assume the origin and destination of the UAV are known and consider UAV models with simplified linear kinematics. The main objective of this report is to present two different approaches to the solution of the problem. In the first approach, the optimal control is converted to a finite dimensional Nonlinear Program (NLP) by using collocation on finite elements and by reformulating the disjunctions involved in modeling the protected zones by using continuous variables. In the second approach the optimal control is converted to a flnite dimensional Mixed Integer Linear Program (MILP) using Euler discretization and reformulating the disjunctions involved with the protected zones by using binary variables and Big-M techniques. Based on results of extensive random simulations, we compare time complexity and optimality of the solutions obtained with the MILP approach and the NLP approach. NLPs are essential to enforce flyability constraints on more detailed UAV models. Moreover, any nonlinear extensions to the problem cannot be dealt with by MILP solvers. The main objective of this paper is to open the route to the use of MILP solutions (based on simple linear UAV models) in order to initialize NLP solvers which allow the use of dynamic UAV models at any desired level of detail. © 2006 IEEE.