配送タスク割当と経路計画を同時に最適化するアルゴリズム
An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem
工場などで複数ロボットが衝突を避けつつ物品を運ぶ問題に対し、タスク割当と経路計画を統合的に最適解くTCBSアルゴリズムを提案し、既存の準最適手法との比較で評価した。
著者: Christian Henkel, Jannik Abbenseth, Marc Toussaint
分類: cs.RO
原文アブストラクト
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.
