DISSERTATION DEFENSE Department of Computer Science and Engineering University of South Carolina Author : Adem Coskun Advisor : Dr. Marco Valtorta Date : April 7, 2021 Time : 12:00 pm - 02:00 pm Place : Virtual Defense (link below) Link : Microsoft Teams: https://teams.microsoft.com/l/meetup-join/19%3ameeting_YTJkMzc0MjEtNDg3… Abstract Multi-robot systems are increasingly deployed in environments where they interact with humans. From the perspective of a robot, such interaction could be considered a disturbance that causes a well-planned trajectory to fail. This dissertation addresses the problem of multi-robot coordination in scenarios where the robots may experience unexpected delays in their movements. Prior work by Cap Gregoire, and Frazzoli introduced a control law, called RMTRACK, which enables robots in such scenarios to execute pre-planned paths in spite of disturbances that affect 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 when execution starts and are 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 is expected 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 algorithms achieve significantly smaller average travel time than RMTRACK at only a modest computational expense. However, deadlock may arise when rearranging the order in which robots pass collision regions and other obstacles. We provide a precise definition of deadlock using a graphical representation and prove some of its important properties. We show how to exploit the representation to detect the possibility of deadlock and to characterize conditions under which deadlock may not occur. We provide experiments in simulated environments that illustrate the potential usefulness of our theory of deadlock.