Greedy Priority-Based Search for Suboptimal Multi-Agent Path Finding

Shao-Hung Chan, Roni Stern, Ariel Felner, Sven Koenig

Introduction

Multi-Agent Path Finding (MAPF) is a critical challenge in robotics, requiring the navigation of multiple agents to their respective goals without collisions. While optimal solutions are NP-hard to compute, real-world applications like automated warehouses often require fast, suboptimal solutions. Priority-Based Search (PBS) has emerged as a leading suboptimal solver, yet it struggles in high-density environments where path-cost optimization often leads to search stagnation or dead-ends.

Greedy Priority-Based Search (GPBS)

This paper introduces Greedy Priority-Based Search (GPBS), which prioritizes conflict minimization over path-cost optimization. GPBS incorporates four primary enhancements to improve scalability and success rates in congested maps:

  1. Greedy Search Strategy: GPBS expands nodes with the fewest conflicting pairs and utilizes a modified SIPPS (Safe Interval Path Planning with Soft Constraints) low-level solver to minimize collisions.
  2. Partial Expansions (PE): To reduce computational overhead in the high-level search tree, GPBS generates child nodes incrementally.
  3. Target Reasoning (TR) & Induced Constraints (IC): These heuristics prioritize resolving conflicts involving agents at their goals and select conflicts that maximize implicit priority constraints, effectively pruning the search space.
  4. Soft Restarts (SR): When the search encounters a dead-end, SR clears priority constraints while retaining current paths, allowing the algorithm to escape local minima without losing progress.
Impact of Target Reasoning (TR) variants on the number of node expansions across different MAPF instances.

Experimental Evaluation

The authors evaluated GPBS using the MovingAI MAPF benchmark suite, focusing on small/dense maps (Random, Maze, Room) and large-scale warehouse environments with up to 2,000 agents.

Key Results

GPBS demonstrated superior performance across all benchmarks:

  • Success Rate: GPBS achieved an 84% success rate within a 1-minute limit, significantly outperforming the previous PBS baseline (43%) and MAPF-LNS2 (73%).
  • Density Performance: In high-density scenarios, GPBS outperformed EECBS by 67% and MAPF-LNS2 by 19%.
  • Search Efficiency: The greedy heuristics significantly reduced the number of node expansions required to find a solution.
Comparison of search expansions in Maze and Room benchmarks for GPBS variants using Induced Constraints (IC).

Discussion and Future Work

While GPBS excels in finding solutions quickly, its greedy nature results in higher Sum of Costs (SOC) compared to optimal or bounded-suboptimal solvers. Furthermore, like PBS, it is not a complete algorithm. Future research will explore integrating incremental search at the low level and applying greedy strategies to other MAPF frameworks.

Summary updated

Abstract

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment, while minimizing their sum of travel times. Since solving MAPF optimally is NP-hard, researchers have explored algorithms that solve MAPF suboptimally but efficiently. Priority-Based Search (PBS) is the leading algorithm for this purpose. It finds paths for individual agents, one at a time, and resolves collisions by assigning priorities to the colliding agents and replanning their paths during its search. However, PBS becomes ineffective for MAPF instances with high densities of agents and obstacles. Therefore, we introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques that speed up GPBS further, namely partial expansions, target reasoning, induced constraints, and soft restarts. We show that GPBS with all these improvements has a higher success rate than the state-of-the-art suboptimal algorithm for a 1-minute runtime limit, especially for MAPF instances with small maps and dense obstacles.
BibTeX
@inproceedings{chan2023greedy,
  author = {Shao-Hung Chan and Roni Stern and Ariel Felner and Sven Koenig},
  title = {{Greedy Priority-Based Search for Suboptimal Multi-Agent Path Finding}},
  booktitle = {SOCS},
  year = {2023},
  doi = {10.1609/socs.v16i1.27278},
}
Figure