Deadlock-Free Online Plan Repair in Multi-robot Coordination with Disturbances

Authors

  • Adem Coskun
  • Jason O'Kane
  • Marco Valtorta University of South Carolina

DOI:

https://doi.org/10.32473/flairs.v34i1.128371

Keywords:

Multi-Robot Systems, Deadlock Detection, Coordination Space, Collision Avoidance, Online Plan Repair, Segment Graph

Abstract

Multirobot 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. Previous approaches that modify trajectories in the presence of disturbances rearrange the order in which robots pass collision regions and other obstacles, in the laudable attempt to improve the average travel time for all robots. By doing so, however, deadlock may arise. In this paper, 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.

Downloads

Published

2021-04-18

How to Cite

Coskun, A., O’Kane, J., & Valtorta, M. (2021). Deadlock-Free Online Plan Repair in Multi-robot Coordination with Disturbances. The International FLAIRS Conference Proceedings, 34. https://doi.org/10.32473/flairs.v34i1.128371

Issue

Section

Special Track: Autonomous Robots and Agents