Multi-Agent Pathfinding as a Combinatorial Auction
Stearn, RoniNote: Order does not necessarily reflect citation order of authors.
MetadataShow full item record
CitationAmir,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.
AbstractThis 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:34306001
- FAS Scholarly Articles