Mixed integer programming for multi-vehicle path planning

Citations Over TimeTop 10% of 2001 papers

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.

Related Papers

• → Multi-UAV Path Planning with Collision Avoidance in 3D Environment Based on Improved APF(2023)5 cited
• → Three-dimensional Collision Avoidance Design on Unmanned Aerial Vehicle(2018)3 cited
• → Reward Function Optimization of a Deep Reinforcement Learning Collision Avoidance System(2023)3 cited
• → Optimal Weapon-Target Assignment of Multiple Dissimilar Closed-In Weapon Systems Using Mixed Integer Linear Programming(2019)
• → Optimal Telecommunications Network Expansion Using Mixed Linear Integer Programming(2022)