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.

Evaluation

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]