MAPF-HD: Multi-Agent Path Finding in High-Density Environments
Hiroya Makino, Seigo Ito
AI summary
Problem
Existing multi-agent path finding methods struggle in high-density environments because optimizing paths for both target and obstructing agents via integer linear programming is computationally prohibitive, while simpler heuristics fail to efficiently relocate obstacles.
Approach
PHANS employs a two-stage heuristic that first plans target paths using a modified A* algorithm accounting for evacuation costs, then sequentially clears obstacles by swapping them with nearby empty vertices.
Key results
- Solves high-density MAPF in seconds for environments exceeding 700 cells
- Reduces computational complexity from exponential to polynomial time
- Effectively evacuates obstructing agents to enable target navigation
- Demonstrates scalability and robustness in large, obstacle-rich environments
Why it matters
Enables real-time path planning for high-density automated warehouses, valet parking, and crowd control applications.
Abstract
Multi-agent path finding (MAPF) involves planning efficient paths for multiple agents to move simultaneously while avoiding collisions. In typical warehouse environments, agents are often sparsely distributed along aisles; however, increasing the agent density can improve space efficiency. When the agent density is high, it becomes necessary to optimize the paths not only for goal-assigned agents but also for those obstructing them. This study proposes a novel MAPF framework for high-density environments (MAPF-HD). Several studies have explored MAPF in similar settings using integer linear programming (ILP). How- ever, ILP-based methods require substantial computation time to optimize all agent paths simultaneously. Even in small grid-based environments with fewer than 100 cells, these computations can take tens to hundreds of seconds. Such high computational costs render these methods impractical for large-scale applications such as automated warehouses and valet parking. To address these limitations, we introduce the phased null-agent swapping (PHANS) method. PHANS employs a heuristic approach to incrementally swap positions between agents and empty vertices. This method solves the MAPF-HD problem within a few seconds, even in large environments containing more than 700 cells. The proposed method has the potential to improve efficiency in various real-world applications such as warehouse logistics, traffic management, and crowd control.