Decentralized Multi-Robot Social Navigation in Constrained Environments via Game-Theoretic Control Barrier Functions
Preprint
Abstract
We present an approach to ensure safe and deadlock-free navigation for decentralized multi-robot systems operating in constrained environments, including doorways and intersections. Although many solutions have been proposed to ensure safety, preventing deadlocks in a decentralized fashion with global consensus remains an open problem. We first formalize the objective as a non-cooperative, non-communicative, partially observable multi-robot navigation problem in constrained spaces with multiple conflicting agents, which we term as \emph{social mini-games}. Our approach to ensuring liveness rests on two novel insights: $(i)$ there exists a mixed-strategy Nash equilibrium that allows decentralized robots to perturb their state onto \textit{liveness sets} i.e. states where robots are deadlock-free and $(ii)$ forward invariance of liveness sets can be achieved identical to how control barrier functions (CBFs) guarantee forward invariance of safety sets. We evaluate our approach in simulation as well on physical robots using F$1/10$ robots, a Clearpath Jackal, as well as a Boston Dynamics Spot in a doorway and corridor intersection scenario. Compared to both fully decentralized and centralized approaches with and without deadlock resolution capabilities, we demonstrate that our approach results in safer, more efficient, and smoother navigation, based on a comprehensive set of metrics including success rate, collision rate, stop time, change in velocity, path deviation, time-to-goal, and flow rate.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- DS-MPEPC: Safe and Deadlock-Avoiding Robot Navigation in Cluttered Dynamic Scenes2023
- Motion planning and control for mobile robot navigation using machine learning: a surveyAutonomous Robots, 2022
- ALGAMES: a fast augmented Lagrangian solver for constrained dynamic gamesAutonomous Robots, 2021
- Collision Avoidance in Pedestrian-Rich Environments With Deep Reinforcement LearningIEEE Access, 2021
- Why Does Symmetry Cause Deadlocks?IFAC-PapersOnLine, 2020
- Twenty Lectures on Algorithmic Game Theory2016
- Flow of pedestrians through narrow doors with different competitivenessJournal of Statistical Mechanics: Theory and Experiment, 2016
- Models, feedback control, and open problems of 3D bipedal robotic walkingAutomatica, 2014
- Experimental study of pedestrian flow through a bottleneckJournal of Statistical Mechanics: Theory and Experiment, 2006
- The dynamic window approach to collision avoidanceIEEE Robotics & Automation Magazine, 1997