An Efficient Scheduling Algorithm for Multi-Robot Task Allocation in Assembling Aircraft Structures

Efficient utilization of cooperating robots in the assembly of aircraft\nstructures relies on balancing the workload of the robots and ensuring\ncollision-free scheduling. We cast this problem as that of allocating a large\nnumber of repetitive assembly tasks, such as drilling holes and installing\nfasteners, among multiple robots. Such task allocation is often formulated as a\nTraveling Salesman Problem (TSP), which is NP-hard, implying that computing an\nexactly optimal solution is computationally prohibitive for real-world\napplications. The problem complexity is further exacerbated by intermittent\nrobot failures necessitating real-time task reallocation. In this letter, we\npresent an efficient method that exploits workpart geometry and problem\nstructure to initially generate balanced and conflict-free robot schedules\nunder nominal conditions. Subsequently, we deal with the failures by allowing\nthe robots to first complete their nominal schedules and then employing a\nmarket-based optimizer to allocate the leftover tasks. Results show an\nimprovement of 11.5\\% in schedule efficiency as compared to an optimized greedy\nmulti-agent scheduler on a four robot system, which is especially promising for\naircraft assembly processes that take many hours to complete. Moreover, the\ncomputation times are similar and small, typically hundreds of milliseconds.\n