Receding Horizon Control of Autonomous Aerial Vehicles

This page presents a new approach to trajectory optimization for autonomous aerial vehicles performing large-scale maneuvers. We have developed a receding horizon trajectory planner based on Mixed Integer-Linear Programming (MILP) that is capable of planning planar trajectories to a goal. The planner can handle constraints such as no-fly areas and aircraft dynamics. This research is part of the MICA project .

Please email John Bellingham with any comments or questions.

Documents about the Receding Horizon Controller:

Presentation slides about the receding controller .pdf version
Paper submitted to American Controls Conference 2002 .pdf version .ps version (See below for abstract)
Movies of the receding horizon controller, planning as it executes: Movie 1 , Movie 2 , Movie 3 , Movie 4 , .zip file of all four movies

If the .pdf files display slowly, download them to your computer before viewing them.

Note that the movies are each about 30 MB in size, but the .zip file is only about 0.5 MB.


 Receding Horizon Controller Schematic

Abstract of the Paper:

This paper presents a new approach to trajectory optimization for autonomous aerial vehicles performing large-scale maneuvers. The main result is a receding horizon trajectory planner based on Mixed Integer-Linear Programming (MILP) that is capable of planning planar trajectories to a goal constrained by no-fly areas, or obstacles, and aircraft dynamics. MILP is well suited to trajectory planning because it can directly incorporate logical constraints such as obstacle avoidance and waypoint selection and because it provides an optimization framework that can account for basic dynamic constraints such as turn limitations.

However, as with many trajectory optimizers, there are difficulties in applying MILP with a fixed planning horizon to real-time control because the computational effort required grows rapidly with the length of the route to be planned and the number of obstacles to be avoided. This limitation can be avoided by using a receding horizon framework in which MILP is used to form a plan that extends towards the goal, but does not necessarily reach it. Each plan is partially executed while the next plan is being formulated.

This paper presents a heuristic that accurately estimates the cost from the plan's end point to the goal, accounting for decisions required to reach the goal that are beyond the planning horizon. A key point of this approximate cost function is that it is linear, so it can be included directly into the MILP trajectory optimization problem. Comparison between the fixed horizon MILP formulation and the receding horizon MILP formulation shows that, for relatively short trajectory problems, the arrival time of the receding horizon controller is within 3 % of optimal. The resulting controller is also shown to work consistently on much larger trajectory optimization problems that are intractable for the fixed horizon MILP formulation.