Route Assignment for Autonomous Vehicles

We demonstrate a self-organizing, multi-agent system to generate approximate solutions to the route assignment problem for a large number of vehicles across many origins and destinations. Our algorithm produces a set of mixed strategies over the set of paths through the network, which are suitable for use by autonomous vehicles in the absence of centralized control or coordination. Our approach combines ideas from co-evolutionary dynamics in which many species coordinate and compete for efficient navigation, and ideas from swarm intelligence in which many simple agents self-organize into successful behavior using limited inter-agent communication. Experiments demonstrate a marked improvement of both individual and total travel times as compared to greedy uncoordinated strategies, and we analyze the differences in outcomes for various routes as the simulation progresses.