  Collision avoidance for multirobot systems is a well-studied problem.
Recently, control barrier functions (CBFs) have been proposed for synthesizing
controllers that guarantee collision avoidance and goal stabilization for
multiple robots. However, it has been noted that reactive control synthesis
methods (such as CBFs) are prone to \textit{deadlock}, an equilibrium of system
dynamics that causes the robots to stall before reaching their goals. In this
paper, we analyze the closed-loop dynamics of robots using CBFs, to
characterize controller parameters, initial conditions, and goal locations that
invariably lead the system to deadlock. Using tools from duality theory, we
derive geometric properties of robot configurations of an $N$ robot system once
it is in deadlock and we justify them using the mechanics interpretation of KKT
conditions. Our key deductions are that 1) system deadlock is characterized by
a force-equilibrium on robots and 2) deadlock occurs to ensure safety when
safety is on the brink of being violated. These deductions allow us to
interpret deadlock as a subset of the state space, and we show that this set is
non-empty and located on the boundary of the safe set. By exploiting these
properties, we analyze the number of admissible robot configurations in
deadlock and develop a provably-correct decentralized algorithm for deadlock
resolution to safely deliver the robots to their goals. This algorithm is
validated in simulations as well as experimentally on Khepera-IV robots.

Robotics;Multiagent Systems;Optimization and Control