Multi-robot task and motion planning in hybrid state spaces

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Motes, James

Contributors dc:contributor

• Amato, Nancy M
• Bretl, Timothy
• Drigs-Campbell, Katie
• Morales, Marco
• Kroeger, Torsten

• Multi-robot Systems
• Task And Motion Planning

Statement dc:rights

• Copyright 2023 James Motes

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121443