Abstract
This paper addresses the multi-agent transport task problem, common in automated factory and warehouse settings, where items must be delivered from start to goal poses while robots avoid mutual collisions. We introduce the Task Conflict-Based Search (TCBS) algorithm, the first approach to optimally solve the combined delivery task allocation and multi-agent path planning problem. Although the problem is NP-hard and the optimal solver faces scalability challenges, TCBS provides a critical "gold standard" baseline for evaluating the sub-optimality and regret of heuristic methods. Experimental results demonstrate that TCBS achieves superior efficiency compared to decoupled approaches.
Introduction: The CTAPF Problem
In modern logistics, robots are tasked with moving items across complex environments. Traditionally, this is treated as two independent problems: Multi-Agent Task Allocation (MATA) and Multi-Agent Path Finding (MAPF). However, these domains are deeply coupled. An allocation that appears optimal in a vacuum may lead to severe congestion or unavoidable collisions when paths are planned. This paper tackles the Combined Task Allocation and Path Finding (CTAPF) problem, aiming for global optimality by solving both assignment and routing simultaneously.
Methodology: Task Conflict-Based Search (TCBS)
TCBS is an evolution of the Conflict-Based Search (CBS) algorithm, extended to handle dynamic task queues. It operates as an A* tree search that branches in two distinct ways to explore the joint solution space:
- Task Expansion: If current paths are collision-free but tasks remain in the queue, the algorithm branches by assigning a new task to an agent.
- Conflict Expansion: If current paths result in a collision, the algorithm branches by adding spatio-temporal constraints, forcing agents to find alternative routes.
To maintain optimality while managing the search space, TCBS utilizes an admissible heuristic based on the Manhattan distance of unassigned tasks to the nearest available agent. This ensures the algorithm never overestimates the remaining cost, guaranteeing a perfect solution upon completion.
Experimental Evaluation
The authors evaluated TCBS using a hand-crafted 8x8 grid designed to highlight the pitfalls of decoupled solvers, as well as randomized scenarios with 20% obstacle density.
The Cost of Separation
A key insight is the "regret" introduced by solving task allocation and pathfinding separately. In the hand-crafted test case, TCBS found an optimal solution with a total duration of 21 units. In contrast, a Mixed Integer Linear Programming (MINLP) approach, which separates the two steps, resulted in a cost of 26 units. This 23% increase in cost occurred because the MINLP allocator was "blind" to the spatial congestion its assignments created, leading to robots blocking each other's paths.
Scalability and Performance
As an optimal solver for an NP-hard problem, TCBS's planning time grows exponentially with the number of tasks and agents. While it is not intended for real-time execution in massive warehouses, its value lies in benchmarking. By providing the absolute minimum cost for small-to-medium scenarios, researchers can precisely quantify the efficiency loss in faster, heuristic-based sub-optimal planners.
Conclusion and Future Work
TCBS establishes a vital theoretical baseline for the CTAPF problem. Future work includes using TCBS to refine more sophisticated sub-optimal planners and exploring approximate versions of the solver that prune the search tree to improve speed while maintaining near-optimal performance. Additionally, extending the model to multi-task robots and time-window constraints remains an open area for research.
Summary updated