Abstract
T. Huang, B. Dilkina and S. Koenig. Learning Node-Selection Strategies in Bounded-Suboptimal Conflict-Based Search for Multi-Agent Path Finding. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 611-619, 2021.Abstract: Multi-Agent Path Finding (MAPF) is an NP-hard problem that has important applications for distribution centers, traffic management and computer games, and it is still difficult for current solvers to solve large instances optimally. Bounded suboptimal solvers, such as Enhanced Conflict-Based Search (ECBS) and its variants, are more efficient than optimal solvers in finding a solution with suboptimality guarantees. ECBS is a tree search algorithm that expands the search tree by repeatedly selecting search tree nodes from a focal list. In this work, we propose to use machine learning (ML) to learn a node-selection strategy to speed up ECBS. In the first phase of our framework, we use imitation learning and curriculum learning to learn node-selection strategies iteratively for different numbers of agents from training instances. In the second phase, we deploy the learned models in ECBS and test their solving performance on unseen instances drawn from the same distribution as the training instances. We demonstrate that our solver, ECBS+ML, shows substantial improvement in terms of the success rates and runtimes over ECBS on five different types of grid maps from the MAPF benchmark.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.