Skip to content

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.

Presentation

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

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}
}