Parallel Hierarchical Composition Conflict-Based Search

Conflict-Based Search (CBS) is a complete multi-agent pathfinding (MAPF) algorithm. It is hybrid in that it:

  • Decouples the search for individual agent paths
  • Couples the resolution of conflicts that occur between agents

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.

CBS vs CBS w/P

Conflict-Based Search (CBS) is a complete multi-agent pathfinding (MAPF) algorithm. It performs individual path planning and resolves conflicts through constraint trees.

In environments with many inter-agent conflicts, the search process can require significant computational effort. To address this, we introduce parallelization within the CBS framework.

CBS with parallelization (CBS w/P) distributes portions of the search across multiple threads using multithreading. This approach leverages available computational resources to accelerate execution while maintaining the CBS structure.

(P)HC-CBS

Hierarchical Composition Conflict-Based Search (HC-CBS) modifies the existing CBS algorithm to solve layers of subproblems consisting of grouping of agents. Subproblems are multi-agent pathfinding problems where only a subset of agents from the full problem are considered. These subsets are solved and hierarchically composed into larger groupings of agents until the original multi-agent pathfinding problem is formed.

The parallel hierarchical extensions include:

  • PHC-CBS, which distributes work to threads in a structured layered system that mirrors HC-CBS.
  • DPHC-CBS, which 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, constraints, 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:

1. Heuristic Evaluation

Tests different heuristics for the agent group composition function.

2. Collision-Heavy Cross Environment

Runtime and memory performance were measured in a difficult, collision-heavy environment.

3. Randomly Generated Environments

Tests the runtime and memory 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
  • Improved CBS

Key Findings

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 be preferred over the other.

For an in-depth analysis of the algorithms, please refer to the original paper linked below.

Publications

Updated: