University of Illinois Urbana-Champaign

Multi-robot task and motion planning in hybrid state spaces

Motes, James

Content Files
MOTES-DISSERTATION-2023.pdf

Permalink

https://hdl.handle.net/2142/121443

Description

Title
Multi-robot task and motion planning in hybrid state spaces
Author(s)
Motes, James
Issue Date
2023-06-30
Director of Research (if dissertation) or Advisor (if thesis)
Amato, Nancy M
Doctoral Committee Chair(s)
Amato, Nancy M
Committee Member(s)
  • Bretl, Timothy
  • Drigs-Campbell, Katie
  • Morales, Marco
  • Kroeger, Torsten
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Multi-Robot Systems
  • Task and Motion Planning
Abstract
The use of autonomous multi-robot systems is rapidly increasing. Utilizing these systems requires the ability to quickly generate plans for large numbers of robots and to handle highly coordinated interactions between robots. Current methods consist of either decoupled or composite approaches. Decoupled approaches are able to quickly find plans for large numbers of robot but struggle when high levels of coordination are required. Composite approaches are capable of planning highly coordinated actions but are computationally expensive. This research aims to develop hybrid planning techniques which leverage the strengths of both approaches while avoiding their drawbacks. These hybrid approaches adapt the planning method to the local level of coordination in the problem by starting with decoupled techniques and then deciding when to employ the more expensive coordinated composite techniques. We present a general framework for multi-robot planning which generalizes decoupled, composite, and hybrid planning approaches. This framework utilizes a novel hypergraph- based representation for modeling this formulation of the planning space. We develop several search variants for this representation and discuss the theoretical properties of different representation and search design choices. We apply this framework to multi-robot motion planning (MRMP), multi-manipulator rearrangement, and multi-robot task allocation (MRTA), presenting new methods for each of these problem domains. In the MRMP problem, we demonstrate the ability to adapt the local level of coordination to the problem, finding higher quality solutions than both decoupled and composite approaches, often in less time. In the multi-manipulator rearrangement problem, we demonstrate up to three orders of magnitude faster planning times than relevant methods while successfully planing for up to 20 objects. In the MRTA problem, we successfully plan for twice as many tasks as comparable methods while achieving up to an order of magnitude improvement in planning times. Additionally, we lay the groundwork for the parallelization of multi-robot planning and present a new parallel multi-agent pathfinding algorithm.
Graduation Semester
2023-08
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/121443
Copyright and License Information
Copyright 2023 James Motes

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois