Multi-Agent Pathfinding as a Combinatorial Auction

Authors

  • Ofra Amir Harvard University
  • Guni Sharon Department of Information Systems Engineering, Ben-Gurion University of the Negev
  • Roni Stern Department of Information Systems Engineering, Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/aaai.v29i1.9427

Keywords:

Multi-agent pathfinding, Combinatorial auctions

Abstract

This paper proposes a mapping between multi-agent pathfinding (MAPF) and combinatorial auctions (CAs). In MAPF, agents need to reach their goal destinations without colliding. Algorithms for solving MAPF aim at assigning agents non-conflicting paths that minimize agents' travel costs. In CA problems, agents bid over bundles of items they desire. Auction mechanisms aim at finding an allocation of bundles that maximizes social welfare. In the proposed mapping of MAPF to CAs, agents bid on paths to their goals and the auction allocates non-colliding paths to the agents. Using this formulation, auction mechanisms can be naturally used to solve a range of MAPF problem variants. In particular, auction mechanisms can be applied to non-cooperative settings with self-interested agents while providing optimality guarantees and robustness to manipulations by agents. The paper further shows how to efficiently implement an auction mechanism for MAPF, utilizing methods and representations from both the MAPF and CA literatures.

Downloads

Published

2015-02-18

How to Cite

Amir, O., Sharon, G., & Stern, R. (2015). Multi-Agent Pathfinding as a Combinatorial Auction. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9427

Issue

Section

AAAI Technical Track: Multiagent Systems