Deadlock-free, safe, and decentralized multi-robot navigation in social mini-games via discrete-time control barrier functions
Top Cited Papers
Open Access
- 20 April 2025
- journal article
- research article
- Published by Springer Nature in Autonomous Robots
- Vol. 49 (2) , 1-31
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 that ensure safety and resolve deadlocks, optimally preventing deadlocks in a minimally invasive and decentralized fashion 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 social mini-games. Formally, we solve a discrete-time optimal receding horizon control problem leveraging control barrier functions for safe long-horizon planning. Our approach to ensuring liveness rests on the insight that there exists barrier certificates that allow each robot to preemptively perturb their state in a minimally-invasive fashion onto liveness sets i.e. states where robots are deadlock-free. We evaluate our approach in simulation as well on physical robots using F1/10 robots, a Clearpath Jackal, as well as a Boston Dynamics Spot in a doorway, hallway, 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
Funding Information
- National Science Foundation (2046955, 1937957, 1937957, 2019844, 2046955)
- Office of Naval Research (N00014-18-2243)
- Army Research Office (E2061621)
This publication has 55 references indexed in Scilit:
- 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
- Why Does Symmetry Cause Deadlocks?IFAC-PapersOnLine, 2020
- Learning Transferable Policies for Monocular Reactive MAV Control2017
- Twenty Lectures on Algorithmic Game Theory2016
- Models, feedback control, and open problems of 3D bipedal robotic walkingAutomatica, 2014
- Optimal Reciprocal Collision Avoidance for Multiple Non-Holonomic Robots2013
- Reciprocal n-Body Collision Avoidance2011
- Guidelines in nonholonomic motion planning for mobile robots2006
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programmingMathematical Programming, 2005