異種ロボット群の設計によるタスク割り当てと順序決定
Designing Heterogeneous Robot Fleets for Task Allocation and Sequencing
時間枠と多様な要件を持つ空間分散タスクを処理するため、予算制約下で最適な異種ロボット群を選定し、タスク割り当てと順序を決定する手法を提案。MILP定式化と大近傍探索ヒューリスティックを開発し、貪欲法より低予算で全タスクを処理できることを示した。
著者: Nils Wilde, Javier Alonso-Mora
分類: cs.RO
原文アブストラクト
We study the problem of selecting a fleet of robots to service spatially distributed tasks with diverse requirements within time-windows. The problem of allocating tasks to a fleet of potentially heterogeneous robots and finding an optimal sequence for each robot is known as multi-robot task assignment (MRTA). Most state-of-the-art methods focus on the problem when the fleet of robots is fixed. In contrast, we consider that we are given a set of available robot types and requested tasks, and need to assemble a fleet that optimally services the tasks while the cost of the fleet remains under a budget limit. We characterize the complexity of the problem and provide a Mixed-Integer Linear Program (MILP) formulation. Due to poor scalability of the MILP, we propose a heuristic solution based on a Large Neighbourhood Search (LNS). In simulations, we demonstrate that the proposed method requires substantially lower budgets than a greedy algorithm to service all tasks.
