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:
- 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.
- Partial Expansions (PE): To reduce computational overhead in the high-level search tree, GPBS generates child nodes incrementally.
- 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.
- 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.
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.
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