Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding

Xinyi Zhong, Jiaoyang Li, Sven Koenig, Hang Ma

In the rapidly evolving landscape of automated logistics, the coordination of robotic fleets has become a cornerstone of operational efficiency. Modern warehouse robots are rarely tasked with moving from a single point A to point B; instead, they must execute complex sequences, such as retrieving an inventory pod, transporting it to a picking station, and returning it to a storage location. This paper, authored by researchers from Simon Fraser University and USC, formalizes this challenge as the Multi-Goal Task Assignment and Path Finding (MG-TAPF) problem.

The Complexity of Integrated Coordination

Traditionally, multi-robot coordination is treated as two distinct problems: Task Assignment (TA), which determines which robot handles which task, and Multi-Agent Path Finding (MAPF), which plans collision-free routes for robots with pre-assigned goals.

However, solving these problems independently creates a significant "gap." A task assignment that looks optimal on paper might be impossible to execute without collisions, or it might lead to "deadlocks" where robots block each other entirely. The MG-TAPF framework seeks to bridge this gap by solving assignment and routing simultaneously to minimize flowtime—the total time all agents spend completing their multi-goal sequences.

The authors provide a rigorous theoretical foundation for this problem, proving that MG-TAPF is NP-hard to solve optimally. Furthermore, they demonstrate that it is even difficult to approximate within a factor of 4/3 for makespan, justifying the development of sophisticated search-based algorithms over simpler polynomial-time heuristics.

The CBS-TA-MLA Framework

To address the MG-TAPF problem, the researchers introduced a hierarchical framework called Conflict-Based Search with Task Assignment and Multi-Label A* (CBS-TA-MLA). This approach operates on two levels:

High-Level: CBS-TA

This level manages the global task assignments and resolves inter-agent collisions. Unlike standard CBS, which starts with a single root node, CBS-TA utilizes a "forest" of constraint trees. Each tree begins with a different potential task assignment calculated via the Hungarian method. When the low-level planner detects a collision between two robots, the high-level search splits the node and imposes constraints (e.g., "Agent A cannot occupy location X at time T") to find a conflict-free resolution.

Low-Level: Multi-Label A (MLA)

For an individual agent assigned to a specific multi-goal task, the low-level planner must find the fastest path that visits all required goals in the correct order. The authors developed Multi-Label A*, which augments the search state with a "label" representing the agent's progress through its goal sequence. This ensures the pathfinding remains efficient while strictly adhering to the task's requirements.

Enhancing Performance through Heuristics and Suboptimality

To make the search viable for complex environments, the authors introduced several advanced techniques:

  • MDD Labeling: The authors adapted Multi-Valued Decision Diagrams (MDDs)—a powerful MAPF pruning tool—to handle sequential goals. By labeling MDD nodes based on the goal sequence, the algorithm can identify "cardinal collisions" (collisions that must be resolved to improve the solution), significantly narrowing the search space.
  • Weighted Dependency Graphs (WDG): This heuristic proved to be the most effective in testing, drastically reducing the number of nodes expanded in the search tree by providing better estimates of the cost of resolving conflicts.
  • Bounded-Suboptimal Search (ECBS-TA-MLA): Recognizing that absolute optimality is often computationally prohibitive in large-scale warehouses, the authors developed a bounded-suboptimal variant. By using a "focal search" that accepts solutions within a factor of $\omega$ of the optimum, the algorithm can find valid paths much faster.

Experimental Insights

The algorithms were rigorously tested across dense warehouse-style grids, sparse random maps, and open environments. The results highlighted several key insights:

  1. The Failure of Decoupling: In dense environments, "Greedy" approaches (assigning tasks before planning paths) frequently failed because they chose assignments that made collision resolution impossible. The integrated CBS-TA-MLA approach successfully navigated these constraints.
  2. Scalability: In a dense map with 20 agents, the optimal solver achieved only a 29% success rate within the time limit. However, the bounded-suboptimal version (ECBS-TA-MLA) achieved a 100% success rate with a suboptimality bound of 1.3, with only a marginal increase in actual path costs.
  3. Goal Depth: In sparse maps, the bounded-suboptimal solver demonstrated impressive scalability, handling tasks with up to 20 sequential goals per agent while maintaining a success rate over 70%.

Future Directions

While CBS-TA-MLA represents a significant step forward, the authors note that computational overhead remains a challenge in extremely cramped environments with high agent counts. Future work will likely focus on "lifelong" planning—where tasks appear dynamically over time rather than being known upfront—and exploring more efficient search space division techniques like disjoint splitting.

Summary updated

BibTeX
@inproceedings{zhong2022optimal,
  author = {Xinyi Zhong and Jiaoyang Li and Sven Koenig and Hang Ma},
  title = {{Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2022},
  url = {https://openreview.net/forum?id=N9vKPBZpU44},
}
Figure