Online Plan Repair in Multi-robot Coordination with Disturbances

Abstract

This paper addresses the problem of multi-robot coordination in scenarios where the robots may experience unexpected delays in their movements. Prior work by Čáp, Gregoire, and Frazzołi introduced a control law, called RMTRACK, which enables robots in such scenarios to execute preplanned paths in spite of disturbances in the execution speed of each robot, while guaranteeing that each robot can reach its goal without collisions and without deadlocks. We extend that approach to handle scenarios in which the disturbance probabilities are unknown at the start and non-uniform across the environment. The key idea is to `repair' a plan on-the-fly, by swapping the order in which a pair of robots passes through a mutual collision region (i.e. a coordination space obstacle), when making such a change can be estimated to improve the overall performance of the system. We introduce a technique based on Gaussian Processes to estimate future disturbances, and propose two algorithms for testing, at appropriate times, whether a swap of a given obstacle would be beneficial. Tests in simulation demonstrate that our algorithm achieves significantly smaller average travel time than RMTRACK at only a modest computational expense.