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

arXiv: https://arxiv.org/abs/1902.08905 · HTML: https://mlsanity.com/paper/1902.08905/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [PIMbot: Policy and Incentive Manipulation for Multi-Robot Reinforcement Learning in Social Dilemmas](https://mlsanity.com/paper/2307.15944/) (2023)
- [PIMbot: A Self-Adaptive Attack Framework for Adversarial Manipulation of Multi-Robot Reinforcement Learning](https://mlsanity.com/paper/2605.23027/) (2026)

## Abstract (arXiv)

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.