• //

Multi Robot Collaboration

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

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 managed 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 showed an improvement of 13 percent in schedule efficiencies as compared to a 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 were similar and small, typically less than one second.

Multi Robot System

Live Demo of Multi-Robot Coordination and STEP
BARC recently contributed to a collaborative effort in the development of a new STEP file format (STEP242) that aims to increase the capabilities of 3D part model files to have the ability to store not only geometric dimensioning, but also fabrication process definitions. In the context of multi-robot-coordinated production, a STEP file that contains the pertinent geometric and process data can be directly interpreted into low-level robot code that can then be uploaded to the robots and used, in conjunction with supervisory cell control, for production. This was demonstrated on BARC’s multi-robot system (shown in the data flow chart): (i) a STEP file of a facsimile wing was created to have geometric and process data, (ii) the data was split per each robot and robot (RAPID) code was generated for each robot, and (iii) the RAPID code was ported onto the robots and was executed.

Multi Robot System

Related Publications

V. Tereshchuk, J. Stewart, N. Bykov, S. Pedigo, S. Devasia, and A. Banerjee, IEEE Robotics and Automation Letters An Efficient Scheduling Algorithm for Multi-Robot Task Allocation in Assembling Aircraft Structures, Vol. 4(4), pp. 3844-3851, October 2019, and presented at the IEEE/RAS International Conference on Intelligent Robots and Systems (IROS) 2019.

Researchers involved include: Veniamin Tereshchuk, John Stewart, Nikolay Bykov, Sam Pedigo, Santosh Devasia and Ashis Banerjee