Multi-Agent Path Finding for Self Interested Agents

摘要: 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 will follow assigned to them. When are {\em self-interested}, however, they expected path only if consider be their most beneficial option. In this paper we propose use taxation scheme implicitly coordinate self-interested in MAPF. We several schemes and compare them experimentally. show intelligent can result lower total than non coordinated even take into consideration both travel taxes paid by