A Study on Improving Multi-agent Path Finding in Congested Environments Using Agent Merging and Splitting

The rising demand for robots in warehouses has highlighted the need for efficient multi-robot algorithms. In response, researchers have focused on Multi-Agent Path Finding (MAPF), which enables multiple agents to calculate conflict-free paths to their individual goals. However, the computation time of conflict-based MAPF algorithms significantly increases as the number of conflicts rises, a common challenge in warehouse environments with narrow passages or corridors. To tackle this issue, this study introduces a new type of conflict called “Overlap Conflict.” Overlap Conflicts occur when an agent stops, causing chain conflicts among subsequent agents traveling in the same direction. When an Overlap Conflict arises, the affected agents are dynamically merged into a single group, shifting the conflicts from an individual level to a group level. If the merged agents find themselves with unreachable goals, they are split back into individual agents to continue calculating paths to their respective destinations. This approach effectively reduces computation time in congested environments, particularly in narrow corridors where alternative routes exist.