Multi-Agent Path Finding for Self Interested Agents

Authors

  • Zahy Bnaya Ben Gurion University
  • Roni Stern Harvard University
  • Ariel Felner Ben Gurion University
  • Roie Zivan Ben Gurion University
  • Steven Okamoto Ben Gurion University

DOI:

https://doi.org/10.1609/socs.v4i1.18292

Keywords:

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

Abstract

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.

Downloads

Published

2021-08-20