Linear-programming-based multi-vehicle path planning with adversaries

Georgios C. Chasparis*, Jeff S. Shamma

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

A linear-programming (LP) based path planning algorithm is developed for deriving optimal paths for a group of autonomous vehicles in an adversarial environment. In this method, both friendly and enemy vehicles are modelled as different resource types in an arena of sectors, and the path planning problem is viewed as a resource allocation problem. Simple model simplifications are introduced to allow the use of linear programming in conjunction with a receding horizon implementation for multi-vehicle path planning. Stochastic models based on the current position of opposing vehicles are used to describe their possible future trajectories. The utility of the LP-based algorithm is tested in the RoboFlag drill, where both teams of vehicles have equal path planning capabilities using the proposed algorithm. Results show that the LP-based path planning in combination with a simple enemy model can be used for efficient multi-vehicle path planning in an adversarial environment.

Original languageEnglish (US)
Article numberWeB16.3
Pages (from-to)1072-1077
Number of pages6
JournalProceedings of the American Control Conference
Volume2
StatePublished - 2005
Externally publishedYes

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Linear-programming-based multi-vehicle path planning with adversaries'. Together they form a unique fingerprint.

Cite this