An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem
This work addresses the challenge of efficient multi-agent coordination in logistics settings like factories, though it is incremental as it focuses on providing an optimal baseline rather than a scalable solution.
The paper tackles the NP-hard problem of optimally combining task allocation and multi-agent path planning for delivery tasks, such as in factories, by introducing the Task Conflict-Based Search (TCBS) Algorithm, which serves as a baseline to evaluate the sub-optimality of other approaches in terms of regret.
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.