Trajectory optimization using mixed-integer linear programming.pdf

Trajectory Optimization using Mixed-Integer
Linear Programming
by
Arthur e Richards
Master of Engineering
University of Cambridge, 2000
Submitted to the Department of Aeronautics and Astronautics
in partial fulfillment of the requirements for the degree of
Master of Science
at the
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
June 2002

c Arthur e Richards, MMII. All rights reserved.
The author hereby grants to MIT permission to reproduce and
distribute publicly paper and electronic copies of this thesis document
in whole or in part.
Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Department of Aeronautics and Astronautics
May 5, 2002
Certified by. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Jonathan P. How
Associate Professor
Thesis Supervisor
Accepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Wallace E. Vander Velde
Chairman, mittee on Graduate Students
2
Trajectory Optimization using Mixed-Integer Linear
Programming
by
Arthur e Richards
Submitted to the Department of Aeronautics and Astronautics
on May 5, 2002, in partial fulfillment of the
requirements for the degree of
Master of Science
Abstract
This thesis presents methods for finding optimal trajectories for vehicles subjected to
avoidance and assignment requirements. The former include avoidance of collisions
with obstacles or other vehicles and avoidance of thruster plumes from spacecraft.
Assignment refers to the inclusion of decisions about terminal constraints in the opti-
mization, such as assignment of waypoints to UAVs and the assignment of spacecraft
to positions in a formation. These requirements lead to non-convex constraints and
difficult optimizations. However, they can be formulated as mixed-integer linear pro-
gram