Mixed integer programming for multi-vehicle path planning

TLDR

The basic problem formulation is to have the vehicles move from an initial dynamic state to a final state without colliding with each other while avoiding other stationary and moving obstacles. The paper proposes a fuel‑optimal multi‑vehicle path‑planning method that combines linear and integer programming. The authors reformulate the problem as a mixed‑integer linear program, address implementation issues, and compare receding‑horizon versus fixed‑arrival‑time strategies. The method can be efficiently solved with CPLEX via an AMPL/Matlab interface, and a worked example demonstrates its suitability for path planning and collision avoidance.

Abstract

This paper presents a new approach to fuel-optimal path planning of multiple vehicles using a combination of linear and integer programming. The basic problem formulation is to have the vehicles move from an initial dynamic state to a final state without colliding with each other, while at the same time avoiding other stationary and moving obstacles. It is shown that this problem can be rewritten as a linear program with mixed integer/linear constraints that account for the collision avoidance. A key benefit of this approach is that the path optimization can be readily solved using the CPLEX optimization software with an AMPL/Matlab interface. An example is worked out to show that the framework of mixed integer/linear programming is well suited for path planning and collision avoidance problems. Implementation issues are also considered. In particular, we compare receding horizon strategies with fixed arrival time approaches.