Decentralized Allocation of Tasks with Temporal and Precedence Constraints to a Team of Robots
2017-01
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Decentralized Allocation of Tasks with Temporal and Precedence Constraints to a Team of Robots
Authors
Published Date
2017-01
Publisher
Type
Thesis or Dissertation
Abstract
The use of multiple robots is beneficial, and sometimes required, to complete sets of tasks. Designing functional multi-robot systems is particularly relevant in application domains such as search and rescue, surveillance, and warehouse management. Allocation of tasks to a team of robots is a well studied topic in the multi-robot systems field. In contrast, task allocation problems where tasks have constraints on where, when and in which order they should be performed have received limited attention, especially in decentralized settings where multiple decision makers are allowed. Here, we investigate multi-robot task allocation problems with temporal and precedence constraints. To address this class of problems, we employ decentralized algorithms to find approximate solutions that minimize the maximum time needed to complete all tasks. To achieve decentralization, we use auction-based insertion heuristics that allow robots to divide work among themselves. To do so, robots take active part in computing schedules that help the team achieve its objectives. This leads to solutions that are robust to the failure of any single robot or task. In this thesis, the use of decentralized algorithms in multi-robot task allocation is explored in four chapters. First, we propose a taxonomy for task allocation problems with temporal and ordering constraints. The taxonomy is the first in the multi-robot task allocation literature to focus specifically on these constraints. It also distinguishes between studies in which task allocation is done deterministically vs. stochastically, and between works that assume hard vs. soft constraints. The taxonomy provides a broad classification of the existing literature, and places our technical work within its different subclasses. Second, we explore the task allocation problem with temporal constraints and propose the temporal sequential single-item auction (TeSSI). TeSSI's key innovation is its combination of sequential single-item auctions and simple temporal networks. The auctions allows robots to distribute work among themselves. Each robot also controls its own simple temporal network, which is used to ensure that new allocations respect tasks' temporal constraints. One of the attractive aspects of the approach is that can be readily used in offline allocations, where tasks are known upfront, or in online scenarios, where tasks arrive over time. We validate the method experimentally, and show its competitiveness when compared to an optimal method, and its advantage over another state of the art auction, and a baseline greedy algorithm. Third, we study task allocation problems with general precedence constraints and propose the simple and prioritized iterated auctions (sIA and pIA). These auctions' novelty is the decomposition of precedence constraints, such that an auctioneer agent handles the precedence constraints, while individual robots bid on pairwise unconstrained tasks. The auctioneer abstracts the precedence graph into layers, and in each iteration a set of pairwise unconstrained tasks is formed and sent to the robots for bidding. We show via thorough experimental evaluations that the method is competitive, and in some instances achieves solutions that are 10% from an optimal solution. Fourth, we address the allocation and execution of tasks with temporal and precedence constraints. A re-purposed pIA auction that relies on a modified TeSSI auction is used for task allocation. A simple executor is also proposed. The executor is made robust by fast adjustments to robots' schedules when robots are delayed, and by a single-shot auction which is used when robots can no longer perform a task in their schedule. We validate the framework in simulation and also run experiments in a robotic testbed with three Turtlebot 2 robots. Additionally, we leverage the power of simulation as a schedule evaluation tool. We present risk and probabilistic analysis that enable users to assess when to readjust tasks' constraints to improve task completion. Taken together, this thesis proposes methods that divide tasks and constraints among the robots, such that each robot controls a subset of the constraints. This decomposition leads to low computational costs, flexibility to handle local failures, and greater individual robot autonomy. These features are important in designing responsive systems for groups of robots that operate in environments where exogenous events are common and may affect robot performance.
Description
University of Minnesota Ph.D. dissertation. January 2017. Major: Computer Science. Advisor: Maria Gini. 1 computer file (PDF); xi, 136 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Nunes, Ernesto. (2017). Decentralized Allocation of Tasks with Temporal and Precedence Constraints to a Team of Robots. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/185585.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.