Continuous-Time Multi-Agent Path Planning with LNS

Discrete-time multi-agent pathfinding (MAPF) problems have been extensively studied, with conflict-based search (CBS) being a well-known optimal algorithm for solving classical MAPF instances, and Large Neighborhood Search being a fast alternative method to obtain a sub-optimal solution. In a continuous-time MAPF problem, conflicts can occur between agents traversing different edges, as well as between an agent waiting at a node and another agent moving along an edge. We considered all types of conflicts (node-node, edge-edge and node-edge conflict) and designed some new continuous-time algorithms based on Continuous-CBS and LNS to solve the problem.