Mixed-integer linear programming (MILP) provides a very general framework for capturing problems with both discrete decisions and continuous variables. Extensive research in the Aerospace Controls Lab (ACL) has explored ways of applying MILP to the control of unmanned aerial vehicles (UAVs). The standard MILP formulation has been used to model many UAV scenarios:

• Obstacle/collision avoidance and non-convex constraints
• Plume impingement
• Minimum-time trajectory problems
• Visibility graph-based cost-to-go models
• Multi-vehicle task assignment
• Hybrid systems
• Use of invariant sets for guaranteed safety

Recent work in MILP control has focused on the implementation of a three-dimensional trajectory optimization algorithm in the lab’s indoor testbed, the Real-time indoor Autonomous Vehicle test Environment (RAVEN). This implementation is designed to fly quadrotor UAVs in a three-dimensional obstacle environment. The MILP formulation uses non-uniform timesteps to design a detailed plan for the short term and a coarse plan for the long term. Additional upgrades include an expanding reachable horizon, such that only nearby obstacles are included in the formulation, and linear interpolation points to reduce the “discretization gap” between timesteps.

A video demonstrating the use of MILP trajectory optimization for a quadrotor vehicle is available here.

Related Publications

• Luders, B. D., “Robust Trajectory Planning for Unmanned Aerial Vehicles in Uncertain Environments,” Master's thesis, Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2008.