An optimal algorithm to solve the combined task allocation and path finding problem
Christian Henkel, Jannik Abbenseth, Marc Toussaint @ IROS 2019
📄 pdf 🔗 doi: 10.1109/IROS40897.2019.8968096
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.
Links
Presentation
BibTeX
@misc{henkel2019optimal,
title={An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem},
author={Christian Henkel and Jannik Abbenseth and Marc Toussaint},
year={2019},
eprint={1907.10360},
archivePrefix={arXiv},
primaryClass={cs.RO}
}