Mixed integer programming for multi-vehicle path planning

Tom Schouwenaars, Bart De Moor, Eric Feron, Jonathan How

Research output: Chapter in Book/Report/Conference proceedingConference contribution

346 Scopus citations

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.
Original languageEnglish (US)
Title of host publication2001 European Control Conference, ECC 2001
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2603-2608
Number of pages6
ISBN (Print)9783952417362
DOIs
StatePublished - Jan 1 2001
Externally publishedYes

Fingerprint

Dive into the research topics of 'Mixed integer programming for multi-vehicle path planning'. Together they form a unique fingerprint.

Cite this