PhD Defense by Andrew Messing
Title: Interleaving Allocation, Planning, and Scheduling for Heterogeneous Multi-Robot Coordination through Shared Constraints
Date: Tuesday, November 29th
Time: 12 pm - 2 pm EST
Location: (in person) Klaus 1315, (virtual) Link will be sent closer to the date
Dr. Seth Hutchinson (Advisor) - School of Interactive Computing, Georgia Institute of Technology
Dr. Sonia Chernova - School of Interactive Computing, Georgia Institute of Technology
Dr. Harish Ravichandar - School of Interactive Computing, Georgia Institute of Technology
Dr. Nicholas Roy - Department of Aeronautics and Astronautics, Massachusetts Institute of Technology
Dr. Alekandra Faust - Senior Staff Research Scientist, Google Brain Research
In a wide variety of domains, such as warehouse automation, agriculture, defense, and assembly, effective coordination of heterogeneous multi-robot teams is needed to solve complex problems. Effective coordination is predicated on the ability to solve the four fundamentally intertwined questions of coordination: what (task planning), who (task allocation), when (scheduling), and how (motion planning). Owing to the complexity of these four questions and their interactions, existing approaches to multi-robot coordination have resorted to defining and solving problems that focus on a subset of the four questions. Notable examples include Task and Motion Planning (what and how), Multi-Agent Planning (what and who), and Multi-Agent Path Finding (who and how). In fact, a holistic problem formulation that fully integrates the four questions lies beyond the scope of prior literature.
This dissertation focuses on examining the use of shared constraints on tasks and robots to interleave algorithms for task planning, task allocation, scheduling, and motion planning and investigating the hypothesis that a framework that interleaves algorithms to these four sub-problems will lead to solutions with lower makespans, greater computational efficiency, and the ability to solve larger problems. To support this claim, this dissertation contributes: (i) a novel temporal planner that interleaves task planning and scheduling layers, (ii) a trait-based time-extended task allocation framework that interleaves task allocation, scheduling, and motion planning, (iii) the formulation of holistic heterogeneous multi-robot coordination problem that simultaneously considers all four questions, (iv) a framework that interleaves layers for all four questions to solve this holistic heterogeneous multi-robot coordination problem, (v) a scheduling algorithm that reasons about temporal uncertainty, provides a theoretical guarantee on risk, and can be utilized within our framework, and (vi) a learning-based scheduling algorithm that reasons about deadlines and can be utilized within our framework.