Multi-Agent Pathfinding as a Combinatorial Auction

DSpace/Manakin Repository

Multi-Agent Pathfinding as a Combinatorial Auction

Citable link to this page


Title: Multi-Agent Pathfinding as a Combinatorial Auction
Author: Amir, Ofra; Sharon, Guni; Stearn, Roni

Note: Order does not necessarily reflect citation order of authors.

Citation: Amir,Ofra, Guni Sharon, and Roni Stern. 2015. "Multi-Agent Pathfinding as a Combinatorial Auction." In Proceedings of the AAAI Conference on Artificial Intelligence, Austin, Texas January 25-29, 2015: 2003-2009.
Full Text & Related Files:
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.
Published Version:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search