Robust Continuous-Time Multi-Agent Path Execution

Most prior work on multi-agent path finding and execution has assumed that time is discretized into timesteps and the agents move in grid maps with uniform action durations. However, in real-world multi-agent applications, agents of different shapes can move in arbitrary directions, and unforeseen failures and anomalies can cause unexpected delays of the agents. These delays are difficult to model and predict, and they can break the assumptions made in path planning and degrade the effectiveness of path execution. This paper studies robust and effective execution of continuous-time multi-agent path plans. We define a feasibility problem of whether a path plan (or a leftover portion of it) can be successfully executed and propose an algorithm to solve it. We further develop offline and online algorithms to coordinate the agents, where conflict-freeness and deadlock-freeness are guaranteed during the path execution.