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

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 pro-ramming 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.