Aircraft trajectory planning with collision avoidance using mixed integer linear programming

TLDR

Trajectory optimization with collision avoidance can be formulated as a mixed‑integer linear program, as demonstrated in recent spacecraft path‑planning studies. The paper proposes a method to compute optimal, collision‑free trajectories for multiple aircraft by applying a MILP formulation based on a linearized aircraft dynamics model. This method employs a linearized aircraft dynamics model and a MILP formulation solved with commercial operations‑research software, and can be extended to multi‑waypoint path planning.

Abstract

Describes a method for finding optimal trajectories for multiple aircraft avoiding collisions. Developments in spacecraft path-planning have shown that trajectory optimization including collision avoidance can be written as a linear program subject to mixed integer constraints, known as a mixed-integer linear program (MILP). This can be solved using commercial software written for the operations research community. In the paper, an approximate model of aircraft dynamics using only linear constraints is developed, enabling the MILP approach to be applied to aircraft collision avoidance. The formulation can also be extended to include multiple waypoint path-planning, in which each vehicle is required to visit a set of points in an order chosen within the optimization.