Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search

Thayne T. Walker (University of Denver & Lockheed Martin Corporation), Nathan R. Sturtevant (Department of Computing Science, Alberta Machine Intelligence Institute (Amii), University of Alberta), Ariel Felner (Ben-Gurion University)

Abstract

We study 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 symmetry-breaking enhancements from unit-cost domains for CCBS. We then improve upon these to produce a new state of the art algorithm: CCBS with disjoint k-partite cliques (CCBS+DK). Finally, we show empirically that CCBS+DK solves for up to 20% more agents in the same amount of time when compared to previous state of the art.