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

Christian Henkel; Jannik Abbenseth; Marc Toussaint

IROS 2019poster51 citations

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

Christian Henkel, Jannik Abbenseth, Marc Toussaint

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 multiagent 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{iros2019_anoptimalalgorit,
  title = {An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem},
  author = {Christian Henkel and Jannik Abbenseth and Marc Toussaint},
  booktitle = {IROS 2019},
  year = {2019}
}