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

Georgios C. Chasparis, Jeff S. Shamma

Research output: Contribution to journalConference articlepeer-review


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
StatePublished - 2005
Externally publishedYes
Event2005 American Control Conference, ACC - Portland, OR, United States
Duration: Jun 8 2005Jun 10 2005

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


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

Cite this