Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, and collaborative autonomous manufacturing. In MRS applications, there are realistic constraints on robots and tasks, including (a) Task group constraints: where multiple micro tasks form tightly-couple macro tasks and need multiple robots form tightly-coupled micro tasks and need multiple robots to perform each simultaenously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically in scenarios like search-rescue (new citims are found dynamically). (d) Robot budget constraints: where the number of of tasks each robot can perform is bounded according to the energy it possesses. There is often a need for decentralized solutions thart are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to be adaptive to environmental changes.
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, I propose methods to address these issues for the polynomial time solvable constrained linear assignment problem and NP-hard constrained generalized assignment problem. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multirobt assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimzation problem leads to a provably good solution to the overall problem. For the constrainted linear assignment problem, my approach provides an almost optimal solution. For the constrainted generalized assignment problem, my approach leads to a solution within a constrant factor of the optimal solution. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.
Edmund Durfee (University of Michigan)
lyonsmuth [atsymbol] cmu.edu