Event Location: GHC 8102

Abstract: The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. In multi-robot systems (MRS), there are various applications of task assignment, such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks are forming disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown beforehand. Such tasks arise in scenarios like search-rescue, where new victims are found dynamically. (d) Uncertain payoffs: where payoffs are not fixed but can be characterized as a probabilistic distribution. From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Additionally, there is a need for these algorithms to have formal performance guarantees.

Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, we propose methods to address these issues for two classes of problems: one is constrained linear assignment problem; the other is constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. Our method is a decomposition-based distributed auction algorithm framework. The multi-robot assignment is first decomposed into each individual robot’s optimal assignment based on modified payoff values, and each robot would iteratively update its assignment as well as task price till convergence. For constrained linear assignment problem, we present a distributed algorithm that provides an almost optimal solution. For constrained generalized assignment problem, we present a distributed algorithm with a different task price update scheme that provides an approximation guarantee. We then study the online version of the task allocation problem with task group constraints. We analyze the online property of the repeated greedy version of our algorithm when tasks arise dynamically, and prove the competitive ratio of the algorithm. We include simulations to evaluate the average-case performance of our algorithm. We also include results on multi-robot cooperative package transport to illustrate our approach.

Committee:Katia Sycara, Chair

Stephen Smith

Anthony Stentz

Edmund Durfee, University of Michigan