Why Does Symmetry Cause Deadlocks?

Abstract

Collision avoidance for multirobot systems has been studied thoroughly. Recently, control barrier functions (CBFs) have been proposed to mediate between collision avoidance and goal achievement for multiple robots. However, it has been noted that reactive controllers (such as CBFs) are prone to deadlock, an equilibrium that causes the robots to stall before reaching their goals. In this paper, we formally analyze two and three robot systems and discover circumstances under which CBFs cause deadlocks using duality theory. For the two robot system, we consider mutually heterogeneous robots (such as one more vigorous or closer to its goal than the other) and prove that this heterogeneity does not help in preventing deadlock. We then consider three robots, and conclude from these two scenarios that the geometric symmetry resulting from robots’ initial positions and goals constrains CBFs to generate velocities that render deadlock stable. Thus, conferring skewness to the system can help evade deadlock.