Multi-agent pathfinding with continuous time

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in a wide range of real-world applications such as warehouse management and autonomous vehicles. Optimizing common MAPF objectives, such as minimizing sum-of-costs or makespan, is computationally intractable, but state-of-the-art algorithms are able to solve optimally problems with dozens of agents. However, most MAPF algorithms assume that (1) time is discretized into time steps and (2) the duration of every action is one time step. These simplifying assumptions limit the applicability of MAPF algorithms in real-world applications and raise non-trivial questions such as how to discretize time in an effective manner. We propose two novel MAPF algorithms for finding optimal solutions that do not rely on any time discretization. In particular, our algorithms do not require quantization of wait and move actions' durations, allowing these durations to take any value required to find optimal solutions. The first algorithm we propose, called Continuous-time Conflict-Based Search (CCBS), draws on ideas from Safe Interval Path Planning (SIPP), a single-agent pathfinding algorithm designed to cope with dynamic obstacles, and Conflict-Based Search (CBS), a state-of-the-art search-based MAPF algorithm. SMT-CCBS builds on similar ideas, but is based on a different state-of-the-art MAPF algorithm called SMT-CBS, which applied a SAT Modulo Theory (SMT) problem-solving procedure. CCBS guarantees to return solutions that have minimal sum-of-costs, while SMT-CCBS guarantees to return solutions that have minimal makespan. We implemented CCBS and SMT-CCBS and evaluated them on grid-based MAPF problems and general graphs (roadmaps). The results show that both algorithms can efficiently solve optimally non-trivial MAPF problems. © 2022 Elsevier B.V.

Andreychuk A. 1, 4 , Yakovlev K. 1, 2, 3 , Surynek P.7 , Atzmon D.5 , Stern R.5, 6
Elsevier B.V.
  • 1 Federal Research Center for Computer Science and Control of Russian Academy of Sciences, Russian Federation
  • 2 HSE University, Russian Federation
  • 3 Moscow Institute of Physics and Technology (MIPT), Russian Federation
  • 4 Peoples' Friendship University of Russia (RUDN University), Russian Federation
  • 5 Software and Information Systems Eng., Ben Gurion University of the Negev, Israel
  • 6 System Sciences Laboratory (SSL), Palo Alto Research Center (PARC), United States
  • 7 Faculty of Information Technology (FIT), Czech Technical University (ČVUT), Czech Republic
Conflict-based search; Heuristic search; Multi-agent pathfinding; Safe-interval path planning; SAT modulo theory
Date of creation
Date of change
Short link

Other records