Abstract
This paper introduces the first scalable, strategyproof mechanisms for Multi-Agent Path Finding (MAPF) in environments where agents are self-interested and may misreport their preferences. Traditional optimal mechanisms like Vickrey-Clarke-Groves (VCG) are computationally intractable for MAPF due to its NP-hard nature. We propose a Monte-Carlo based approach leveraging the "Maximal-In-Range" (MIR) property. Our primary contribution, Monte-Carlo Prioritized Planning (MCPP), ensures truthful reporting as a dominant strategy by selecting the best outcome from a fixed, randomly sampled set of priority orderings. Empirical evaluations on standard benchmarks demonstrate that MCPP scales to thousands of agents while significantly improving social welfare over baseline methods.
Introduction
Multi-Agent Path Finding (MAPF) is critical for coordinating fleets of robots in warehouses or delivery drones in urban airspace. While traditional research assumes a central controller with cooperative agents, real-world applications often involve self-interested entities. In such settings, an agent might lie about its delay costs to receive priority.
Standard economic tools like VCG payments can align incentives but require finding mathematically optimal solutions to maintain strategyproofness. Since optimal MAPF is NP-hard, using approximate or heuristic solutions with VCG typically breaks incentive guarantees. This paper bridges the gap between computational efficiency and economic stability.
Methodology: Maximal-In-Range (MIR)
The authors utilize the Maximal-In-Range (MIR) property to maintain strategyproofness without requiring global optimality. By restricting the search space to a fixed subset of outcomes and picking the best one within that subset, the mechanism remains strategyproof as long as the subset is independent of agent reports.
Three mechanisms are explored:
- Payment-CBS (PCBS): An optimal benchmark pairing Conflict-Based Search with VCG payments. It is efficient but lacks scalability.
- Exhaustive-PBS (EPBS): A strategyproof version of Priority-Based Search that explores a full search tree of priority orderings.
- Monte-Carlo Prioritized Planning (MCPP): The most scalable solution. It randomly samples $m$ priority orderings, calculates paths for each, and selects the one maximizing reported social welfare. Increasing $m$ allows for a tunable trade-off between computation time and welfare.
Key Results and Scalability
The mechanisms were evaluated on four standard 2D MAPF benchmarks: random-32-32-20, den312d, den520d, and Paris-1-256.
As shown in the results, MCPP scales linearly with the number of agents and samples. While optimal methods like PCBS and search-based methods like EPBS failed as agent counts approached 100, MCPP successfully handled up to 3,000 agents on the random grid map. Furthermore, MCPP maintained a 100% success rate in "well-formed" instances and provided a measurable boost in total social welfare compared to a standard First-Come-First-Serve (FCFS) baseline.
Economic Insights
A significant finding of the study is the distribution of VCG payments. In many MAPF scenarios, agents do not impose heavy externalities on one another, leading to zero or very small payments. This suggests that market-based MAPF systems are not only theoretically sound but also practically affordable for users.
Conclusion
By leveraging the MIR property, this work provides a practical framework for deploying strategyproof mechanisms in large-scale MAPF applications. MCPP offers a scalable, tunable, and economically robust alternative to traditional cooperative algorithms. Future work will focus on extending these mechanisms to dynamic settings where agents arrive and depart over time, and exploring more sophisticated sampling techniques to further enhance social welfare.
Summary updated