  Trajectory replanning is a critical problem for multi-robot teams navigating
dynamic environments. We present RLSS (Replanning using Linear Spatial
Separations): a real-time trajectory replanning algorithm for cooperative
multi-robot teams that uses linear spatial separations to enforce safety. Our
algorithm handles the dynamic limits of the robots explicitly, is completely
distributed, and is robust to environment changes, robot failures, and
trajectory tracking errors. It requires no communication between robots and
relies instead on local relative measurements only. We demonstrate that the
algorithm works in real-time both in simulations and in experiments using
physical robots. We compare our algorithm to a state-of-the-art online
trajectory generation algorithm based on model predictive control, and show
that our algorithm results in significantly fewer collisions in highly
constrained environments, and effectively avoids deadlocks.
