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

Committee:

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

Abstract:

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.