Event Location: NSH 1305

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, search and rescue, 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 includes (a) Task group constraints: where tasks are divided into 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 one tightly-coupled macro task is divided into multiple micro tasks and needs multiple robots to perform each simultaneously. (b) 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. (c) Uncertain payoffs: where payoffs are not fixed but can be characterized as a probabilistic distribution or uncertain range. From the solution/algorithm aspect, there is often a need for decentralized solution that are implemented on individual robots. 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 static tasks with group constraints, we present a distributed algorithm that provides an almost optimal solution. This is an extension of Bertsekas’ algorithm for the linear assignment problem where tasks are assumed to be independent. 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 also include simulations to evaluate the average-case performance of our algorithm. In our future work, we propose to (a) extend our algorithm to address other constraints among tasks, e.g., task deadline constraints or precedence constraints; (b) design algorithms to address the payoff uncertainty.

Committee:Katia Sycara, Chair

Stephen Smith

Anthony Stentz

Edmund Durfee, University of Michigan