  Trajectory planning for multiple robots in shared environments is a
challenging problem especially when there is limited communication available or
no central entity. In this article, we present Real-time planning using Linear
Spatial Separations, or RLSS: a real-time decentralized trajectory planning
algorithm for cooperative multi-robot teams in static environments. The
algorithm requires relatively few robot capabilities, namely sensing the
positions of robots and obstacles without higher-order derivatives and the
ability of distinguishing robots from obstacles. There is no communication
requirement and the robots' dynamic limits are taken into account. RLSS
generates and solves convex quadratic optimization problems that are
kinematically feasible and guarantees collision avoidance if the resulting
problems are feasible. We demonstrate the algorithm's performance in real-time
in simulations and on physical robots. We compare RLSS to two state-of-the-art
planners and show empirically that RLSS does avoid deadlocks and collisions in
forest-like and maze-like environments, significantly improving prior work,
which result in collisions and deadlocks in such environments.
