Mixed Integer Linear Programming for Trajectory Optimization and Formation Management

Prof. Jonathon How, Department of Aeronautics and Astronautics, MIT

Mixed Integer Linear Programming (MILP) provides a powerful technique for solving for optimal trajectories and plans for multi-vehicle operations. The approach is an extension of linear programming, which is formed by restricting some of the variables to take only integer values. This allows us to include various types of logical constraints and discrete decisions in the trajectory optimization problem. Powerful software exists for finding MILP solutions, offering a direct route to optimal solutions of complicated problems. The approach has been applied to several air and space applications. For example, reconfiguration maneuvers for many formation- flying spacecraft can be planned by MILP using Hill's equations as the system dynamics. We can also include collision avoidance and plume impingement constraints in mixed integer form. In addition, the assignment of spacecraft positions within the formation and the selection of the formation orientation can be expressed as decisions using integer variable constraints. Only the desired relative alignment of the formation is specified, and the rest is optimized to minimize the fuel cost.

MILP techniques have also been developed for aircraft applications, such as 'free-flight' problems, that require cooperative collision-avoiding maneuvers for multiple aircraft. The aircraft dynamics are modeled using a linear approximation that restricts the turn rate. The approach also extends to maneuvers with multiple waypoints. MILP can be used to optimize the order and times at which each waypoint is visited. For example, the optimization can change the order in which the waypoints are visited to avoid a collision with another aircraft or a new obstacle.

Many approaches have been proposed for path planning in applications from deep sea to deep space. In every case, some simplification of the problem is used to reduce it to a computationally tractable optimization. For MILP, it is necessary to approximate dynamics and constraints in linear form, which is possible for most types of vehicle. The method allows us to keep high-level decisions, such as formation configuration and waypoint selection, as decision variables in the optimization. The talk will address the approximations used in the aircraft and spacecraft applications and show the results of numerous optimization examples.