Back to search

Georgia Institute of Technology

Interleaving Allocation, Planning, and Scheduling for Heterogeneous Multi-Robot Coordination through Shared Constraints

Abstract

dc:description.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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Interactive Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Messing, Andrew Kenneth
Advisor dc:contributor.advisor
  • Hutchinson, Seth
Committee members dc:contributor.committeemember
  • Chernova, Sonia
  • Ravichandar, Harish
  • Roy, Nicholas
  • Faust, Aleksandra

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/70147

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Messing, Andrew Kenneth. Interleaving Allocation, Planning, and Scheduling for Heterogeneous Multi-Robot Coordination through Shared Constraints. Doctoral thesis, Georgia Institute of Technology, 2022. http://hdl.handle.net/1853/70147