2026-09-19T07:09:55Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/129443 2025-10-20 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms The student, Hannah Lee, accepted the attached license on 2025-04-24 at 12:44. The student, Hannah Lee, submitted this Dissertation for approval on 2025-04-24 at 12:53. This Dissertation was approved for publication on 2025-04-24 at 15:22. DSpace SAF Submission Ingestion Package generated from Vireo submission #21953 on 2025-10-19 at 18:18:58 Studies in constraint-based search for multi-robot planning Lee, Hannah 2025-04-24 Amato, Nancy M 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 eng 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. 2025-05 Thesis https://hdl.handle.net/2142/129443 Copyright 2025 Hannah Lee Siebel School Comp & Data Sci Computer Science University of Illinois Urbana-Champaign Ph.D. Dissertation