マルチロボットタスク割当の計算複雑性と近似アルゴリズム
Multi-Robot Task Allocation -- Complexity and Approximation
各タスクに複数ロボットが必要で各ロボットは1タスクのみ担当する設定で、総予算・タスク予算・ロボット予算の3種の制約下で完了タスク数を最大化する問題の複雑性を解析し、近似解法と多項式時間アルゴリズムを提案した。
著者: Haris Aziz, Hau Chan, Ágnes Cseh, Bo Li, Fahimeh Ramezani, Chenhao Wang
分類: cs.RO, cs.AI
原文アブストラクト
Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.
