Collision Avoidance for Persistent Monitoring in Multi-Robot Systems with Intersecting Trajectories

Persistent robot tasks such as monitoring and cleaning are concerned with controlling mobile robots to act in a changing environment in a way that guarantees that the uncertainty in the system (due to change and to the actions of the robot) remains bounded for all time. Prior work in persistent robot tasks considered only robot systems with collision-free paths that move following speed controllers. This work is focused on a solution to multi-robot persistent monitoring, where robots have intersecting trajectories. We develop collision and deadlock avoidance algorithms that are based on stopping policies, and quantify the impact of the stopping times on the overall stability of the speed controllers. The algorithm works for any number of robots and was implemented with both ground robots (Roombas) and flying robots (quadrotors). The main contribution of this work is to enable the persistent speed controllers developed by Stephen L. Smith, in previous work, to operate when multiple robots have intersecting trajectories. Here, we mean intersection in the sense that the robot bodies could collide. We develop a collision avoidance procedure based on stopping, and quantify its effect on the stability of these controllers. The collision avoidance operates by identifying collision zones in which collisions could occur. We then avoid collisions by stopping and restarting robots so that at most one robot occupies a given collision zone at any moment in time. We also design a procedure to avoid deadlocks; a situation in which a group of robots are all stopped, and are waiting for each other to move before resuming motion. We identified several different stopping policies and perform extensive simulations to determine the most effective policy.