2023/12/26 by Thayne T. Walker, Nathan Sturtevant, Walker, Thayne T. +3 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Robotic Path Planning Algorithms #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2312.16106
openalex publication_date 2023/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
While the study of unit-cost Multi-Agent Pathfinding (MAPF) problems has been popular, many real-world problems require continuous time and costs due to various movement models. In this context, this paper studies symmetry-breaking enhancements for Continuous-Time Conflict-Based Search (CCBS), a solver for continuous-time MAPF. Resolving conflict symmetries in MAPF can require an exponential amount of work. We adapt known enhancements from unit-cost domains for CCBS: bypassing, which resolves cost symmetries and biclique constraints which resolve spatial conflict symmetries. We formulate a novel combination of biclique constraints with disjoint splitting for spatial conflict symmetries. Finally, we show empirically that these enhancements yield a statistically significant performance improvement versus previous state of the art, solving problems for up to 10% or 20% more agents in the same amount of time on dense graphs.