K. E. Bekris, D. K. Grady, M. Moll, and L. E. Kavraki, “Safe Distributed Motion Coordination for Second-Order Systems With Different Planning Cycles,” International Journal of Robotics Research, vol. 31, no. 2, pp. 129–150, Feb. 2012.
When multiple robots operate in the same environment, it is desirable for scalability purposes to coordinate their motion in a distributed fashion while providing guarantees about their safety. If the robots have to respect second-order dynamics, this becomes a challenging problem, even for static environments. This work presents a replanning framework where each robot computes partial plans during each cycle, while executing a previously computed trajectory. Each robot communicates with its neighbors to select a trajectory that is safe over an infinite time horizon. The proposed approach does not require synchronization and allows the robots to dynamically change their cycles over time. This paper proves that the proposed motion coordination algorithm guarantees safety under this general setting. This framework is not specific to the underlying robot dynamics, as it can be used with a variety of dynamical systems, nor to the planning or control algorithm used to generate the robot trajectories. The performance of the approach is evaluated using a distributed multi-robot simulator on a computing cluster, where the simulated robots are forced to communicate by exchanging messages. The simulation results confirm the safety of the algorithm in various environments with up to 32 robots governed by second-order dynamics.
Publisher: http://dx.doi.org/10.1177/0278364911430420
PDF preprint: http://kavrakilab.org/publications/bekris-grady2012safe-distributed-motion.pdf