  Typical Multi-agent Path Finding (MAPF) solvers assume that agents move
synchronously, thus neglecting the reality gap in timing assumptions, e.g.,
delays caused by an imperfect execution of asynchronous moves. So far, two
policies enforce a robust execution of MAPF plans taken as input: either by
forcing agents to synchronize or by executing plans while preserving temporal
dependencies. This paper proposes an alternative approach, called
time-independent planning, which is both online and distributed. We represent
reality as a transition system that changes configurations according to atomic
actions of agents, and use it to generate a time-independent schedule.
Empirical results in a simulated environment with stochastic delays of agents'
moves support the validity of our proposal.
