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.
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.
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