AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
Multi-Agent Path Finding for Self Interested Agents
Zahy Bnaya, Roni Stern, Ariel Felner, Roie Zivan, Steven Okamoto

Last modified: 2013-06-19


Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e.g., the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are {\em self-interested}, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents.


Artificial Intelligence; Multi-agent systems; Navigation; Path finding

Full Text: PDF