Summary

We implemented and evaluated several parallel approaches for solving dense multi-agent path finding (MAPF) instances. Our target workload was small_32, a 10-by-30 grid with 32 robots. This case was small enough to run repeatedly, but dense enough to create many robot conflicts, making it useful for studying collision resolution and repair parallelism. Our implementation evolved through three major versions: a greedy repair solver with batched disjoint conflict repair, a parallel speculative beam-search-style repair solver, and a bitset wavefront low-level planner integrated into the MAPF repair loop. The best multicore scaling came from the greedy-batch version, which improved from 156.3 seconds at 1 thread to 33.3 seconds at 16 threads, but then plateaued. The best solution quality came from the parallel speculative beam-8 planner, which reduced total cost from 1109 to 1019 and makespan from 39 to 36. The best single-thread runtime came from the bitset wavefront MAPF planner, which solved small_32 in 15.5 seconds. Overall, our project shows that MAPF repair exposes some parallelism, but the amount of useful work per repair round is limited by conflict structure, synchronization overhead, and the granularity of low-level search.

The project was evaluated on PSC Bridges-2 nodes, including r009.ib.bridges2.psc.edu and br014.ib.bridges2.psc.edu.

Background

Multi-agent path finding is the problem of routing multiple agents from start locations to goal locations while avoiding collisions. In our project, the agents are robots moving on a grid. The input is a grid map and a set of robot start and goal positions. The output is a path for each robot such that no two robots occupy the same cell at the same timestep and no two robots traverse the same edge in opposite directions at the same timestep.

There are two main types of collisions. A vertex collision occurs when two robots occupy the same cell at the same timestep. An edge collision occurs when two robots swap positions across the same edge at the same timestep. The solver repeatedly detects these collisions and repairs one or more robot paths until the full set of paths is collision-free.

The expensive part of the computation is the repeated repair process. Each repair round requires collision detection, choosing conflicts to repair, generating constraints, replanning one or more robots, scoring candidate repairs, and merging accepted path changes back into the global solution. The low-level replanning step is especially expensive because it may call A* or another shortest-path routine many thousands of times. In the greedy-batch baseline for small_32, the solver made 58,760 A* calls and expanded 158,852,792 states.

The key parallelization challenge is that MAPF is not simply independent single-agent path planning. Each robot path interacts with other robot paths through collisions. Therefore, the solver must expose parallel work while still preserving global collision resolution semantics. We explored high-level repair parallelism, where multiple candidate repairs are evaluated in parallel, and low-level search parallelism, where the single-agent planner is made more regular using bitset wavefront propagation.

Approach

Initial CBS-style direction

Our early implementation used standard MAPF components: collision detection, A* as the low-level single-agent planner, and CBS-style conflict handling. CBS, or Conflict-Based Search, maintains a high-level constraint tree. When a collision is found, CBS branches by adding a constraint to one robot in one branch and to the other robot in another branch. This approach is exact, but the branching factor becomes expensive when many robots interact.

The main lesson from this stage was that exact CBS was not practical for our target benchmark regime. It worked on very small cases, but the number of high-level branches became too large as the number of robots increased. This motivated moving to a greedy repair approach: keep MAPF collision detection and repair semantics, but avoid maintaining the full CBS constraint tree.

Stage 1: Greedy repair with batched disjoint conflict repair

The first practical solver was a greedy repair algorithm. The solver begins by planning an initial path for every robot. It then repeatedly detects collisions and repairs selected conflicts by adding constraints and replanning.

The key idea was to select multiple robot-disjoint conflicts in each iteration. If two conflicts involve disjoint sets of robots, then repair candidates for those conflicts can be evaluated independently. This gives a natural OpenMP parallel loop over repair candidates.

1. Detect all current vertex and edge collisions.
2. Sort collisions by earliest timestep.
3. Select up to top_k_conflicts conflicts, requiring selected conflicts to be robot-disjoint.
4. For each selected conflict, generate two possible repair constraints, one for each robot in the conflict.
5. Replan the constrained robot with A*.
6. Score each candidate by remaining collision count and total path cost.
7. Keep the best candidate for each conflict.
8. Merge compatible repaired paths into the current solution.
9. Repeat until no collisions remain.

This maps to the machine by assigning independent repair candidates to OpenMP worker threads. Each worker evaluates a candidate repair by running low-level A* and computing the resulting collision/cost score. The global solution is only updated after candidate evaluation, so the parallel work is mostly in candidate generation and replanning.

The main advantage of this design is that it exposes parallel work without abandoning the central MAPF collision-resolution problem. The main disadvantage is that the amount of parallelism is bounded by the number of disjoint conflicts. With 32 robots, there can be at most 16 robot-disjoint pairwise conflicts in one repair round, and each conflict gives at most two direct repair candidates. Therefore, this design cannot naturally keep 64 or 128 threads busy on small_32.

Stage 2: Parallel speculative repair with beam merge

The greedy-batch solver improved runtime, but it still made many stagnant repairs and required thousands of repair iterations. On small_32, the greedy-batch solver needed 4,914 repair iterations, considered 29,364 conflicts, generated 58,728 candidate repairs, and made 58,760 A* calls.

The next approach was a parallel speculative planner. It still used the same basic MAPF repair ingredients as Stage 1: detect collisions, generate one-robot vertex or edge constraints, replan the constrained robot, and score the resulting global solution by remaining collision count and total path cost. However, it changed the high-level search policy. In Stage 1, one candidate meant one constrained replan for one robot, and the solver only kept the best local candidate per conflict before greedy merge. In Stage 2, one candidate became a speculative repair state that could contain multiple newly added constraints and multiple repaired robots. The main benchmark used a conflict pool of 128, beam width 8, and lookahead depth 1.

1. Detect all collisions and sort them by earliest timestep.
2. Select up to conflict_pool_size robot-disjoint conflicts from that sorted list. Stage 2 did not remove the disjointness restriction; it simply used a much larger bound than Stage 1.
3. For each selected conflict, generate the two standard one-sided repair constraints, one for each robot involved in the conflict.
4. Evaluate those speculative repair tasks in parallel. Each worker adds one constraint, replans the constrained robot with A*, applies the repaired path to a copy of the current solution, and scores the resulting state by remaining collision count and total path cost.
5. If lookahead depth is 2, expand each surviving first-step candidate by one more repair step. This creates a second speculative layer, and a better two-step descendant can replace its parent candidate. The reported beam-8 benchmark used lookahead depth 1, so the main measured result is a one-step speculative beam search.
6. Keep the best speculative candidate for each originating conflict, sort those candidates globally by score, and keep only the top beam_width candidates for merge.
7. Greedily merge candidates back into the current solution, but only if they are compatible. A candidate is rejected if it introduces a duplicate constraint or if it changes a robot that was already modified by an earlier accepted beam candidate in the same round.
8. After tentatively applying a candidate, recompute global collisions and total cost. Commit the candidate only if the merged solution improves. If no beam candidate can be merged, fall back to the single best candidate overall.

The goal was to improve the search trajectory, not just to evaluate the same local repairs faster. By ranking and merging a beam of speculative candidates, Stage 2 tried to spend more computation per repair round in order to make better high-level choices. This worked algorithmically: the speculative planner reduced repair iterations from 4,914 to 1,628 and low-level searches from 58,760 to 21,124 on small_32. It also improved solution quality, lowering total cost from 1109 to 1019 and makespan from 39 to 36.

Stage 3: Bitset wavefront low-level planning

Profiling showed that useful application work was still dominated by low-level A* search and its supporting data structures. To address this, we implemented a bitset wavefront low-level planner. Instead of representing the frontier with irregular A* priority queues and hash tables, the bitset planner represents reachable cells at each timestep as dense bitsets.

More concretely, each timestep stores the reachable cells of every row as one or more uint64_t words. The next frontier is formed by deriving five candidate move masks from the current frontier: wait, move left, move right, move up, and move down. Horizontal moves are implemented with word shifts, vertical moves by copying row-aligned words, and every move is masked against pre-indexed vertex and edge constraints for the next timestep. The resulting masks are ORed together to form the next reachable set, while a compact parent-move array records how each newly reached cell was first discovered so that a valid path can be reconstructed once the goal becomes reachable.

This changes the low-level planner from irregular graph search into a more regular wavefront computation. In parallel systems terms, this improves spatial locality, reduces allocation traffic, and turns low-level search into dense row-wise bit-mask updates. Importantly, this optimization only replaced the single-robot replanner inside the same high-level MAPF repair loop; collision detection, constraint generation, and repeated repair iterations still remained. On wider grids, additional chunk-level parallelism would also be possible. This was the most successful constant-factor optimization. On small_32, the bitset MAPF planner solved the instance in 15.5 seconds on one thread, compared with 156.3 seconds for greedy-batch and 38.4 seconds for parallel beam-8. However, because small_32 is only a 10-by-30 grid, the row-wise bitset kernel did not expose much useful thread-level work, so Stage 3 improved per-search efficiency far more than multicore scaling.

Abandoned suffix A* optimization

We also tried a suffix A* optimization. The idea was that if a conflict occurs at time t, the solver could keep the robot's prefix path before t and only replan the suffix from around the conflict to the goal. In practice, this did not remain in the final implementation. A conservative version compared suffix A* against a full replan and kept the better candidate, but that often required running both searches, increasing total work. A suffix-first version with fallback-on-failure avoided always running both searches, but it accepted locally valid suffix repairs that were poor choices for the global greedy repair loop. Because this experiment was reverted and no durable small_32 benchmark file remains in the current repo, we treat it as an attempted optimization rather than a main measured result.

Experimental Setup

The primary benchmark in this report is small_32:

Grid: 10 x 30
Robots: 32

This workload was chosen because it is small enough to run repeatedly, but dense enough to create many conflicts. We measured wall-clock runtime, total solution cost, makespan, repair iterations, conflicts considered, candidate repairs, low-level searches or A* calls, successful repairs, stagnant repairs, states expanded, and states generated.

The greedy-batch scaling run used thread counts 1, 2, 4, 8, 16, 32, 64, 128 on r009.ib.bridges2.psc.edu with cpus_per_task=128. The parallel beam-8 and bitset-wavefront runs ran on br014.ib.bridges2.psc.edu. The beam-8 run used thread counts 1 through 128, while the bitset run used thread counts 1, 2, 4, and 8.

We profiled the parallel beam-8 planner at 16 threads using perf record, perf stat -d, and perf report:

./benchmark_runner small_32 --planner parallel --beam-width 8 -N 16

Results

Greedy-batch scaling

The greedy-batch solver showed useful speedup up to 16 threads. Runtime improved from 156,346.908 ms at 1 thread to 33,336.595 ms at 16 threads. This is approximately a 4.69x speedup.

The solution quality and search statistics were identical across all thread counts. Every run produced total cost 1109, makespan 39, 4,914 repair iterations, 58,760 A* calls, 158,852,792 states expanded, and 248,070,127 states generated. This means the thread count did not change the algorithmic trajectory. The same repair decisions and same amount of search work occurred in every run. The only difference was how that fixed work was scheduled across threads.

Parallel speculative beam-8 results

The parallel speculative beam-8 planner was algorithmically better than greedy-batch, but worse as a multicore scaling strategy.

The beam planner reduced repair iterations by about 66.9% and low-level searches by about 64.0%. It also reduced state expansions from 158,852,792 to 30,946,123.

This result shows a distinction between algorithmic improvement and parallel speedup. Beam-8 made better repair choices and greatly reduced total search work. But its OpenMP implementation did not keep more cores busy.

Beam-8 profiling

Even though the run requested 16 OpenMP workers, the process averaged less than one CPU utilized. The hot libgomp addresses were consistent with a pause/compare spin loop, which indicates barrier or synchronization waiting rather than useful application work. This rules out one simple explanation: the bottleneck was not mainly a single serial merge function or collision detection. The dominant issue was that each repair iteration exposed too little independent work, while OpenMP synchronization and A* internals remained expensive.

Bitset wavefront results

The bitset-wavefront MAPF planner produced the best single-thread runtime.

The bitset version was about 10.1x faster than greedy-batch at 1 thread and about 2.5x faster than beam-8 at 1 thread. It also improved solution quality relative to greedy-batch, reducing cost from 1109 to 1060 and makespan from 39 to 37. However, it did not beat beam-8 on solution quality: beam-8 achieved cost 1019 and makespan 36.

The likely reason is granularity. A 10-by-30 grid is too small for the implemented row-level OpenMP parallelism to amortize overhead. Since each row fits in one 64-bit word, there is no additional chunk-level work to distribute within a row on this benchmark. The low-level computation is already compact and efficient on one core, so adding threads mostly introduces scheduling and synchronization costs without enough useful extra work.

Discussion

The main lesson from this project is that parallelizing MAPF is not just a matter of adding OpenMP to the low-level planner or evaluating candidates in parallel. The structure of the MAPF repair loop strongly controls available parallelism.

Why greedy-batch scaled up to 16 threads

Greedy-batch scaled because it exposed independent repair candidates. For each selected robot-disjoint conflict, the solver could evaluate candidate constraints independently. This created useful parallel work and produced a 4.69x speedup at 16 threads. But the scaling plateaued because the number of independent repair tasks per round is naturally limited. With 32 robots, there cannot be hundreds of robot-disjoint conflict repairs in one iteration. Once the thread count exceeds the number of useful repair tasks, the extra threads mostly wait.

Why beam-8 improved quality but not scaling

Beam-8 made better decisions. It reduced the number of high-level repair iterations and low-level searches, which is why the 1-thread beam-8 run was much faster than the 1-thread greedy-batch run. However, better decision quality did not imply better parallel execution. Profiling showed that the 16-thread beam-8 run averaged only 0.935 CPUs utilized and spent more than half of sampled cycles in libgomp synchronization/spin-loop behavior.

Why bitset wavefront was the best single-thread result

The bitset planner attacked a different bottleneck: the cost of low-level A* search. A* uses priority queues, hash tables, dynamic allocation, and irregular memory access. Bitset wavefront planning improved this by replacing irregular search with dense bit operations. This gave a large constant-factor improvement, making the 1-thread bitset solver the fastest measured configuration.

But the bitset planner still lived inside the high-level MAPF repair loop. It did not remove the need for thousands of repair iterations and tens of thousands of low-level searches. On small_32, the grid was too small for the implemented row-wise bitset kernel to expose much useful thread-level parallelism. Therefore, the bitset implementation improved per-search efficiency but did not create scalable multicore execution on this workload.

What limited speedup overall

• Limited repair-level parallelism: independent repair work is bounded by the number of robot-disjoint conflicts.
• Fine-grained synchronization: repeated repair rounds require frequent coordination between candidate evaluation and global merge.
• Irregular low-level search: A* spends time in hash tables, allocation, and priority queues.
• Small grid size for bitset threading: the 10-by-30 grid does not provide enough row/chunk-level work for many threads.
• Stagnant repairs: many accepted repairs do not immediately reduce collision count, showing that local greedy repair can spend work without direct immediate progress.

Conclusion

We implemented and evaluated three increasingly optimized MAPF solvers. The greedy-batch solver showed that repair-candidate parallelism can provide useful speedup, reaching about 4.7x speedup on small_32 at 16 threads. The parallel speculative beam-8 solver showed that better repair choices can significantly reduce total search work and improve solution quality, but profiling revealed that it did not expose enough useful parallel work to keep many OpenMP threads busy. The bitset wavefront planner showed that low-level representation changes can produce large constant-factor gains by replacing irregular A* search with dense bit operations, producing the best single-thread runtime.

The final result is not perfect multicore scaling. Instead, the project demonstrates a more realistic parallel systems lesson: algorithmic structure determines available parallelism. MAPF collision repair has dependencies that limit coarse-grained parallelism, and small-grid low-level planning does not provide enough fine-grained work to compensate. Different versions produced the strongest results on different axes: greedy-batch gave the best multicore speedup, beam-8 gave the best solution quality, and bitset wavefront gave the best single-thread runtime. The overall lesson is therefore about choosing the right algorithmic structure and representation for each bottleneck, rather than simply using more threads.

References

1. Sharon, G., Stern, R., Felner, A., and Sturtevant, N. R. “Conflict-Based Search for Optimal Multi-Agent Pathfinding.”
2. Hart, P. E., Nilsson, N. J., and Raphael, B. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.”
3. OpenMP Architecture Review Board. OpenMP Application Programming Interface.
4. Linux perf profiling tools.
5. Project benchmark files in benchmark_results/, especially small_32_implementation_timeline_summary.txt, small_32_scaling_40176493.txt, small_32_parallel_beam8_scaling_20260424_084154.txt, small_32_bitset_scaling_20260424_083916.txt, and small_32_parallel_beam8_n16_perf_summary.txt.

Work Distribution

50%-50%. Jongsun worked on the initial CBS-style direction and the bitset wavefront low-level planner. Dylan worked on greedy repair with batched disjoint conflict repair and the parallel speculative repair solver.