フロー分解による高速な準最適異種タスク割り当て
Fast Near-Optimal Heterogeneous Task Allocation via Flow Decomposition
異種能力を持つマルチロボットのタスク割り当てを、最小費用流で解ける同種サブ問題に分解し、最適解の1/2以上の近似保証で高速に解く手法を提案した。
著者: Kiril Solovey, Saptarshi Bandyopadhyay, Federico Rossi, Michael T. Wolf, Marco Pavone
分類: cs.RO, cs.DS, cs.MA, cs.SY, eess.SY
原文アブストラクト
Multi-robot systems are uniquely well-suited to performing complex tasks such as patrolling and tracking, information gathering, and pick-up and delivery problems, offering significantly higher performance than single-robot systems. A fundamental building block in most multi-robot systems is task allocation: assigning robots to tasks (e.g., patrolling an area, or servicing a transportation request) as they appear based on the robots' states to maximize reward. In many practical situations, the allocation must account for heterogeneous capabilities (e.g., availability of appropriate sensors or actuators) to ensure the feasibility of execution, and to promote a higher reward, over a long time horizon. To this end, we present the FlowDec algorithm for efficient heterogeneous task-allocation achieving an approximation factor of at least 1/2 of the optimal reward. Our approach decomposes the heterogeneous problem into several homogeneous subproblems that can be solved efficiently using min-cost flow. Through simulation experiments, we show that our algorithm is faster by several orders of magnitude than a MILP approach.
