Authors: Hannah Lee, James Motes, Marco Morales, Nancy M. Amato

Venue: IEEE/RSJ International Conference on Intelligent Robots and Systems
DOI: 10.1109/LRA.2021.3096476.
Link to Publication

Abstract:
"In this letter, we present the following optimal multi-agent pathfinding (MAPF) algorithms: Hierarchical Composition Conflict-Based Search, Parallel Hierarchical Composition Conflict-Based Search, and Dynamic Parallel Hierarchical Composition Conflict-Based Search. MAPF is the task of finding an optimal set of valid path plans for a set of agents such that no agents collide with present obstacles or each other. The presented algorithms are an extension of Conflict-Based Search (CBS), where the MAPF problem is solved by composing and merging smaller, more easily manageable subproblems. Using the information from these subproblems, the presented algorithms can more efficiently find an optimal solution. Our three presented algorithms demonstrate improved performance for optimally solving MAPF problems consisting of many agents in crowded areas while examining fewer states when compared with CBS and its variant Improved Conflict-Based Search." 

@article{Lee-phccs-2021, 
 author = {Lee, Hannah and Motes, James and Morales, Marco and Amato, Nancy M}, 
 journal = {IEEE Robotics and Automation Letters}, 
 number = {4}, 
 pages = {7001--7008}, 
 publisher = {IEEE}, 
 title = {Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding}, 
 volume = {6}, 
 year = {2021} 
}