Improving Continuous-Time Conflict Based Search

Authors

  • Anton Andreychuk Peoples’ Friendship University of Russia (RUDN University) Federal Research Center for Computer Science and Control of Russian Academy of Sciences
  • Konstantin Yakovlev Federal Research Center for Computer Science and Control of Russian Academy of Sciences HSE University
  • Eli Boyarski Ben Gurion University of the Negev
  • Roni Stern Ben Gurion University of the Negev Palo Alto Research Center

Keywords:

Continuous Problem Solving

Abstract

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for n agents in a graph such that each agent reaches its goal vertex and the agents do not collide with each other while moving along these paths. While different problem statements of MAPF exist, we are focused on MAPFr (Walker, Sturtevant, and Felner 2018), in which actions’ durations can be non-uniform, agents have geometric shapes, and time is continuous. Continuous-time conflict-based search (CCBS) (Andreychuk et al. 2019) is a recently proposed algorithm for finding optimal solutions to MAPFr problems. In this work, we propose several improvements to CCBS based on known improvements to the Conflictbased search (CBS) algorithm (Sharon et al. 2015) for classical MAPF, namely Disjoint Splitting (DS), Prioritizing Conflicts (PC), and high-level heuristics. We evaluate the impact of these improvements experimentally on both roadmaps and grids. Our results show that CCBS with these improvements is able to solve significantly more problems.

Downloads

Published

2021-07-22