An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem

Christian Henkel, Jannik Abbenseth, Marc Toussaint

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:

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

The TCBS search tree illustrates the dual branching strategy: Task Expansion for unassigned tasks and Conflict Expansion to resolve path collisions.

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.

Comparison of the problem configuration and the resulting paths for TCBS (optimal) versus MINLP (sub-optimal). TCBS avoids the congestion that leads to the higher cost in the MINLP solution.

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

Abstract

We consider multi-agent transport task problems where, e.g. in a factory setting, items have to be delivered from a given start to a goal pose while the delivering robots need to avoid collisions with each other on the floor. We introduce a Task Conflict-Based Search (TCBS) Algorithm to solve the combined delivery task allocation and multi-agent path planning problem optimally. The problem is known to be NP-hard and the optimal solver cannot scale. However, we introduce it as a baseline to evaluate the sub-optimality of other approaches. We show experimental results that compare our solver with different sub-optimal ones in terms of regret.
BibTeX
@inproceedings{henkel2019optimal,
  author = {Christian Henkel and Jannik Abbenseth and Marc Toussaint},
  title = {{An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=J_OZjcHv0f},
}
Figure