Scalable Mechanism Design for Multi-Agent Path Finding
CoRR(2024)
摘要
Multi-Agent Path Finding (MAPF) involves determining paths for multiple
agents to travel simultaneously through a shared area toward particular goal
locations. This problem is computationally complex, especially when dealing
with large numbers of agents, as is common in realistic applications like
autonomous vehicle coordination. Finding an optimal solution is often
computationally infeasible, making the use of approximate algorithms essential.
Adding to the complexity, agents might act in a self-interested and strategic
way, possibly misrepresenting their goals to the MAPF algorithm if it benefits
them. Although the field of mechanism design offers tools to align incentives,
using these tools without careful consideration can fail when only having
access to approximately optimal outcomes. Since approximations are crucial for
scalable MAPF algorithms, this poses a significant challenge. In this work, we
introduce the problem of scalable mechanism design for MAPF and propose three
strategyproof mechanisms, two of which even use approximate MAPF algorithms. We
test our mechanisms on realistic MAPF domains with problem sizes ranging from
dozens to hundreds of agents. Our findings indicate that they improve welfare
beyond a simple baseline.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要