• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •
Deadlock-free, Safe, and Decentralized Multi-Robot Navigation in Social Mini-Games via Discrete-Time Control Barrier Functions.
Rohan Chandra, Vrushabh Zinage, Efstathios Bakolas, Peter
Stone, and Joydeep Biswas.
Autonomous Robots, 2025.
We present an approach to ensure safe and deadlock-free navigation fordecentralized multi-robot systems operating in constrained environments,including doorways and intersections. Although many solutions have been proposedthat ensure safety and resolve deadlocks, optimally preventing deadlocks in aminimally invasive and decentralized fashion remains an open problem. We firstformalize the objective as a non-cooperative, non-communicative, partiallyobservable multi-robot navigation problem in constrained spaces with multipleconflicting agents, which we term as social mini-games. Formally, we solve adiscrete-time optimal receding horizon control problem leveraging control barrierfunctions for safe long-horizon planning. Our approach to ensuring liveness restson the insight that there exists barrier certificates that allow each robot topreemptively perturb their state in a minimally-invasive fashion onto livenesssets i.e. states where robots are deadlock-free. We evaluate our approach insimulation as well on physical robots using F1/10 robots, a Clearpath Jackal, aswell as a Boston Dynamics Spot in a doorway, hallway, and corridor intersectionscenario. Compared to both fully decentralized and centralized approaches withand without deadlock resolution capabilities, we demonstrate that our approachresults in safer, more efficient, and smoother navigation, based on acomprehensive set of metrics including success rate, collision rate, stop time,change in velocity, path deviation, time-to-goal, and flow rate.
@Article{smg,
author = {Rohan Chandra and Vrushabh Zinage and Efstathios Bakolas and Peter Stone and Joydeep Biswas},
title = {Deadlock-free, Safe, and Decentralized Multi-Robot Navigation in Social Mini-Games via Discrete-Time Control Barrier Functions},
journal = {Autonomous Robots},
year = {2025},
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.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Tue May 06, 2025 18:17:36