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