Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding

Hannah Lee, James Motes, Marco Morales, Nancy Amato

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number9483630
Pages (from-to)7001-7008
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number4
StatePublished - Oct 2021


  • Multi-robot systems
  • parallel algorithms
  • path planning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence


Dive into the research topics of 'Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding'. Together they form a unique fingerprint.

Cite this