Betweenness Centrality in Multi-Agent Path Finding

Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms’ performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

Authors

• Eric Ewing
• Jingyao Ren
• Dhvani Kansara University of Southern California
• Vikraman Sathiyanarayanan
• Nora Ayanian

Keywords

• Multi-Agent Path Finding
• Algorithm Portfolio
• Betweenness Centrality