MS thesis abstract - Bellingham, John

Author:Bellingham, John
Degree:Masters of Science
SERC #:12-02
File type:PDF, 1014 kB
download iconDownload file (opens in new window)

Coordination and Control of UAV Fleets using Mixed-Integer Linear Programming

This thesis considers two important topics in the coordination and control of fleets of UAVs; the allocation and trajectory design problems. The first allocates waypoints to individual vehicles in the fleet, and includes constraints on vehicle capability, waypoint visitation, and visit timing. Formulations of the allocation problem are presented to find minimum mission completion time and maximum stochastic expectation of mission benefit. The trajectory design problem provides a minimum time reference trajectory to the goal, while avoiding obstacles in the environment and obeying a limited turning rate.

Mixed-Integer Linear Programming (MILP) is applied to both problems in order to integrate discrete and continuous decisions, making into one optimization program. The MILP allocation program's cost function is evaluated using estimated trajectory parameters, which come from approximated paths. This partially decouples the allocation and trajectory design problems, and detailed trajectories can later be designed for the selected waypoint sequences. This significantly reduces the allocation solution time, with negligible loss in performance. The stochastic formulation is shown to recover sophisticated attrition reduction strategies.

MILP is applied to the trajectory design problem within a receding horizon control framework. The optimization uses a novel terminal penalty which approximates the cost to go to the goal, and is cognizant of intervening obstacles. This approach provides trajectories that are within 3% of optimal with significantly less computational effort, while avoiding entrapment in concave obstacles. This trajectory designer is modified to guarantee its stability, and the resulting controller is capable of planning trajectories in highly constrained environments, without large increases in computation time.

The approaches presented here successfully solve the allocation and trajectory design problems, offering good performance and computational tractability.


Copyright © 2001-2004 Massachusetts Institute of Technology