Studies in constraint-based search for multi-robot planning

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Lee, Hannah

Contributors dc:contributor

• Amato, Nancy M
• Hauser, Kris
• Serlin, Zachary
• Morales, Marco

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

Statement dc:rights

• Copyright 2025 Hannah Lee

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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