Multi-robot task and motion planning in hybrid state spaces

Motes, James

Permalink

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

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