MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem

Mingkai Tang, Yuanhang Li, Hongji Liu, Yingbing Chen, Ming Liu, Lujia WangIJCAI 2024

Abstract

Multi-Goal Multi-Agent Path Finding (MG-MAPF) is a critical challenge in automated logistics, requiring agents to visit multiple locations while avoiding collisions. Traditional methods often prioritize local "earliest arrival" times, which can lead to global sub-optimality. We present MGCBS, an algorithm that decouples goal visiting orders using "Safe Intervals" and a novel Time-Interval-Space (TIS) Forest. MGCBS is mathematically proven to be optimal and achieves up to a 7x speedup over previous state-of-the-art methods.

Introduction

In modern automated warehouses, robots are rarely assigned a single task. Instead, a robot might need to visit several distinct locations to fulfill a single order. This scenario defines the Multi-Goal Multi-Agent Path Finding (MG-MAPF) problem, which combines the complexity of the Traveling Salesman Problem (TSP) with the dynamic constraints of collision avoidance.

A typical MG-MAPF scenario where multiple agents navigate to several goals.

The primary difficulty lies in the interdependence of agent paths. Previous approaches, such as Decoupled Vertex visiting order Search (DVS), often failed because they assumed that reaching a goal as early as possible was always optimal. In reality, a "greedy" arrival can cause congestion that delays other agents, increasing the total system cost.

Methodology

MGCBS introduces two core innovations to ensure both optimality and computational efficiency.

Decoupling Goal Safe Interval Visiting Order Search (DSS)

Rather than searching for a sequence of physical vertices, MGCBS searches through Goal Safe Intervals (GSI). A safe interval represents a time window during which a specific location is unoccupied. By treating time as a first-class dimension in the goal-ordering process, the algorithm can strategically incorporate "waiting" periods. This allows agents to avoid future conflicts that would otherwise necessitate long detours.

The Time-Interval-Space (TIS) Forest

To address the high computational cost of path recalculation, the authors developed the TIS Forest. This data structure pre-calculates shortest paths from any starting point and time step to specific goal intervals using a backward Dijkstra-based search.

The TIS Forest structure mapping graph nodes to time-interval-space costs.

When the high-level Conflict-Based Search (CBS) solver requires the cost for an agent to reach its next goal, it performs a simple query against the TIS Forest. This eliminates the need for redundant A* searches, significantly accelerating the overall pathfinding process.

Experimental Results

The performance of MGCBS was evaluated against standard benchmarks (e.g., maze-32-32-4, lak303d) and custom maps designed to expose the flaws in non-optimal algorithms.

  • Efficiency: MGCBS demonstrated a 7x speedup over the previous state-of-the-art (HCBS) when utilizing the TIS Forest.
  • Optimality: In specific test cases, HCBS produced solutions that were up to 17.39% longer than the optimal paths found by MGCBS.
  • Scalability: On complex maps like orz900d, MGCBS maintained a 100% success rate in scenarios where previous methods failed to find any solution within the 60-second time limit.

Conclusion

MGCBS represents a significant advancement in MG-MAPF by proving that "earliest arrival" is not a prerequisite for global optimality. By leveraging safe intervals and the TIS Forest, it provides a robust framework for managing complex robot fleets. Future research will focus on extending this model to dynamic environments where goals appear in real-time and incorporating more complex robot kinematics.

Summary updated

BibTeX
@inproceedings{tang2024mgcbs,
  author = {Mingkai Tang and Yuanhang Li and Hongji Liu and Yingbing Chen and Ming Liu and Lujia Wang},
  title = {{MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure