航空機構造組立におけるマルチロボット作業割当のための効率的スケジューリングアルゴリズム
An Efficient Scheduling Algorithm for Multi-Robot Task Allocation in Assembling Aircraft Structures
航空機組立の反復作業を複数ロボットに割り当てる問題を、部品形状と問題構造を活かして初期スケジュールを生成し、故障時は市場ベース最適化で残作業を再割当する手法を提案。4ロボット系でスケジュール効率が11.5%向上し、計算時間は数百ミリ秒。
著者: Veniamin Tereshchuk, John Stewart, Nikolay Bykov, Samuel Pedigo, Santosh Devasia, Ashis G. Banerjee
分類: cs.RO, cs.MA
原文アブストラクト
Efficient utilization of cooperating robots in the assembly of aircraft structures relies on balancing the workload of the robots and ensuring collision-free scheduling. We cast this problem as that of allocating a large number of repetitive assembly tasks, such as drilling holes and installing fasteners, among multiple robots. Such task allocation is often formulated as a Traveling Salesman Problem (TSP), which is NP-hard, implying that computing an exactly optimal solution is computationally prohibitive for real-world applications. The problem complexity is further exacerbated by intermittent robot failures necessitating real-time task reallocation. In this letter, we present an efficient method that exploits workpart geometry and problem structure to initially generate balanced and conflict-free robot schedules under nominal conditions. Subsequently, we deal with the failures by allowing the robots to first complete their nominal schedules and then employing a market-based optimizer to allocate the leftover tasks. Results show an improvement of 11.5\% in schedule efficiency as compared to an optimized greedy multi-agent scheduler on a four robot system, which is especially promising for aircraft assembly processes that take many hours to complete. Moreover, the computation times are similar and small, typically hundreds of milliseconds.
