Parallel Hierarchical Planning Algorithms
Related Projects:  Robot Task and Motion Planning    Parallel & Distributed Planning Methods    STAPL: Standard Template Adaptive Parallel Library    Multi-Agent Systems    Multi-Robot Motion Planning    Integrated Task and Motion Planning  
Hierarchical algorithms prioritize certain aspects of planning over others. They are typically organized in layers requiring different levels of planning. In the lab, we develop parallel hierarchical planning algorithms for multi-robot motion planning and multi-robot task and motion planning.

Parallel Hierarchical Composition Conflict-Based Search

Conflict-Based Search (CBS) is a complete multi-agent pathfinding (MAPF) algorithm. It is a hybrid MAPF algorithm in that it decouples the search for agent's individual paths and couples the resolution of conflicts that occur between them. Our work creates a hierarchical composition of the CBS algorithm and parallelizes it using multithreading. The Hierarchical Composition Conflict-Based Search (HC-CBS) algorithm, modifies the existing CBS algorithm to solve layers of subproblems consisting of grouping of agents.

Additionally, this work leverages the embarrassingly parallel nature of HC-CBS to parallelize via multithreading. We present two parallel extensions: Parallel Hierarchical Composition Conflict-Based Search (PHC-CBS) and Dynamic Parallel Hierarchical Composition Conflict-Based Search (DPHC-CBS). PHC-CBS distributes work to threads in a structured layered system that mirrors HC-CBS. DPHC-CBS distributes work dynamically to threads based on available work and available threads.

Algorithm Overview

The intuition behind this work is to solve smaller subproblems and to use the non-conflicting paths to aid in solving larger subproblems. Subproblems are multi-agent pathfinding problems where only a subset of agents from the full problem are considered. These subsets of agents are solved and hierarchically composed into larger groupings of agents until the original multi-agent pathfinding problem is formed. Information regarding paths, constaints, and costs from smaller subproblems are used to generate a set of starting points from which larger subproblems can begin their search. The goal of this hierarchical structure is to solve smaller subproblems to target strongly coupled agents and reduce the number of explored states to reduce the amount of work required to solve larger subproblems.

Subproblems are solved and merged based on an agent group composition function. This uses a heuristic to estimate the amount of computational work a subproblem will require to be solved. The agent group composition function determines which agent groups should be paired together and solved. The agent group composition is crucial in determining subproblems that effectively target problematic agents.

Subproblems are solved using CBS and the information about their paths, constraints, and costs are used in the future when solving larger subproblems through a process called crossing constraint trees. This is the process of taking information from each subproblem and combining them to provide a starting basis for larger subproblems. The process of organizing, solving, and merging subproblems is repeated until the full multi-agent pathfinding problem is solved.


The hierarchical composition algorithms were tested on three sets of experiments. The first tests different heuristics for the agent group composition function. The second experiment tests the runtime and memory performance of the algorithms on a difficult, collision-heavy cross environment. The third experiment tests the runtime an dmemory performance of the algorithms on randomly generated environments. All algorithms were run for 20 iterations and the results were averaged. The hierarchical composition algorithms were tested against CBS and Improved CBS. We show improved scalability in robot numbers in difficult problems consisting of many inter-agent conflicts. For the two parallel extensions, we analyze its performance and discuss situations in which one should preferred over the other. For an in-depth analysis of the algorithms, please refer to the original paper linked below.

Related Publications

Parallel Hierarchical Composition Conflict-Based Search, Hannah Lee, James Motes, Marco Morales, Nancy M. Amato, IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol: 6, Issue: 4, pp. 7001-7008, Prague, Czech Republic, Jul 2021. DOI: 10.1109/LRA.2021.3096476.
Keywords: Multi-Agent, Parallel Planning, Path Planning
Links : [Published]


title={Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding},
author={Lee, Hannah and Motes, James and Morales, Marco and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},


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.