Back to search

University of Washington

Multi-Robot Task Allocation and Scheduling for Efficient Aircraft Structure Assembly

Abstract

dc:description.abstract

This thesis presents the development of methods for extending multi-robot systems to aircraft structure assembly and manufacture. The use of multiple, stationary, cooperating robotic manipulators in aircraft assembly lines has the potential to increase production throughput without increasing footprint, especially benefiting high-volume production lines. As such, multi-robot systems must maximally utilize the robot assets in the production cell, which entails balanced work allocation and collision-free task scheduling to enable efficient and safe cell operation. The task allocation and scheduling problem, often modeled as a multiple traveling salesman problem is an NP-hard problem. However, since task allocation in aircraft structure assembly is a large scale problem, often having as many as on the order of 10^3 total tasks, current methods for allocation and scheduling are computationally prohibitive, and excessive robot idling due to long computation of task schedules also has the potential to decrease the efficiency of the production cell. The scheduling is further complicated by the dynamic nature of the robots' capabilities that comes in the forms of periodic robot failures that require a robot to be pulled out of operation for maintenance, and tool changes for robots that are required for the robots to be able to service a variety of tasks. This poses some unique challenges in terms of (i) enabling fast, balanced and collision-free scheduling of the robots that properly responds to robot failures, (ii) determining the proper placement of the robot bases in the robot cell to ensure maximal workload sharing potential, and (iii) ensuring that tool changes are handled such that the time cost of changing tools is minimized. In addressing these challenges, the contributions of this thesis are to (i) employ a partition-based scheduler and market-based schedule optimizer in a two stage scheduling framework to enable fast, collision-free and efficient cell operation, (ii) outline robot base placement and mobility strategies as a means to attenuate the effects of robot failures on cell efficiency, and (iii) adapt auction-based methods to minimize tool changes and develop a machine-learning framework for generating scheduling heuristics in an operationally robust manner. The methods are developed and tested on a physical multi-robot system that enables real-world application of the research.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tereshchuk, Veniamin
Advisors dc:contributor.advisor
  • Devasia, Santosh
  • Banerjee, Ashis G

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • none
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/46110

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Tereshchuk, Veniamin. Multi-Robot Task Allocation and Scheduling for Efficient Aircraft Structure Assembly. 2020. http://hdl.handle.net/1773/46110