Rohan Chandra, Vrushabh Zinage, Efstathios Bakolas, Joydeep Biswas, Peter Stone
We present an approach to ensure safe and deadlock-free navigation for decentralized multi-robot systems operating in constrained environments, including doorways and intersections. The primary objective of our navigation problem is for each robot to reach its target without colliding, freezing, and minimally deviating from its preferred plan or trajectory. Furthermore, they must navigate with partial observability using decentralized controllers. Although many solutions have been proposed to ensure safety, preventing deadlocks in a decentralized fashion with global consensus remains an open problem. In this work, we first formalize the above multi-robot navigation problem in constrained spaces with multiple conflicting agents, which we term as \emph{social mini-games}. To solve social mini-games, we propose a new class of decentralized controllers that ensure both safety and deadlock resolution by attaining a game-theoretic Nash equilibrium. Our controller builds on two key insights: first, we reduce the deadlock resolution problem to solving a modified version of an N-player Chicken game, for which a Nash equilibrium solution exists. Second, we formulate the Nash equilibrium as a control barrier function (CBF) and integrate it with traditional CBFs to inherit their safety guarantees. We compare game-theoretic deadlock resolution with random perturbation and find that our proposed strategy results in lower cost and path deviation for robots. We further demonstrate the effectiveness of our proposed CBF controller in various challenging constrained environments.
PDF.