Studies in constraint-based search for multi-robot planning

Lee, Hannah

Permalink

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

Description

Title

Studies in constraint-based search for multi-robot planning

Author(s)

Lee, Hannah

Issue Date

2025-04-24

Director of Research (if dissertation) or Advisor (if thesis)

Amato, Nancy M

Doctoral Committee Chair(s)

Amato, Nancy M

Committee Member(s)

• Hauser, Kris
• Serlin, Zachary
• Morales, Marco

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Artificial Intelligence
• Multi-Robot System
• Multi-Robot Planning
• Search Algorithms
• Multi-Agent Pathfinding
• Task and Motion Planning

Abstract

Constraint-based search has emerged as a powerful framework for solving multi-agent pathfinding (MAPF) problems by iteratively refining naive solutions through the introduction of constraints. While extensively studied in centralized MAPF, its broader applicability to more complex multi-robot planning problems remains underexplored. This dissertation investigates the adaptability and scalability of constraint-based search across various domains, including large-scale MAPF, decentralized multi-task multi-agent pathfinding (MT-MAPF), and multi-robot task allocation (MRTA). We analyze how constraint selection, search strategies, and distributed computation impact performance, ultimately extending constraint-based search to a diverse range of multi-robot coordination challenges. We begin by introducing a classification system for constraints, offering a structured framework to analyze how different constraint types impact search efficiency and solution quality across various problem representations. Building on this foundation, we address large-scale scalability in MAPF with Hierarchical Composition Conflict-Based Search (HC-CBS), a distributed framework that partitions MAPF problems into smaller, more tractable subproblems. Next, we extend constraint-based search to decentralized Multi-Task Multi-Agent Pathfinding (MT-MAPF) by introducing Pathfinding with Rapid Information Sharing using Motion Constraints (PRISM), which enables agents to plan dynamically in real-time while handling communication constraints. Finally, we integrate constraint-based search with task allocation through Task and Motion Planning Conflict-Based Search (TMP-CBS), a method that jointly optimizes task decomposition, allocation, and motion planning, facilitating structured and efficient multi-robot task execution. Through extensive empirical evaluation, we demonstrate significant improvements in efficiency, scalability, and solution quality across all three domains. Our results show that constraint-based search can be effectively adapted beyond traditional MAPF, facilitating distributed, decentralized, and task-integrated multi-robot planning. This work provides a foundation for further research into scalable, constraint-driven multi-agent coordination methods, with potential applications in warehouse automation, autonomous transportation, and large-scale robotic fleets.

Graduation Semester

2025-05

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Hannah Lee

Owning Collections