Abstract:
Collision avoidance for multirobot systems is a well-studied problem. Recently, control barrier functions (CBFs) have been proposed for synthesizing controllers that guarantee safety while simultaneously encouraging goal stabilization for multiple robots. However, it has been noted that reactive control synthesis methods (such as CBFs) are prone to deadlock, an equilibrium of system dynamics that causes robots to come to a standstill before reaching their goals. In this talk, we will propose an approach to analyze long-term behavior of reactive optimization-based controllers such as CBFs and show that geometric symmetry in the positions of robots using these controllers leads to deadlocks. Additionally, we will show how tools from duality theory and graph enumeration can be used to analyze geometric properties of a system in deadlock. Our main deductions are that system deadlock is indeed characterized by a force equilibrium on robots, that deadlock occurs to ensure safety when safety is at the brink of being violated, and that the complexity of deadlock analysis increases combinatorially with the number of robots. This allows us to interpret deadlock as a subset of the state space, and we prove that this set is non-empty and located on the boundary of the safety set. The motivation to derive these properties is so we can use them to exit this subset, i.e. construct a controller for deadlock resolution that delivers all robots to their goals while avoiding collisions. So we will conclude the presentation with simulations demonstrating that.

Committee:
Changliu Liu (Co-advisor)
Katia Sycara (Co-advisor)
Howie Choset
Wenhao Luo