LivePoint : Fully Decentralized, Safe, Deadlock-Free Multi-Robot Control in Cluttered Environments with High-Dimensional Inputs
Jeffrey Chen, Rohan Chandra · 2025
Read LivePoint : Fully Decentralized, Safe, Deadlock-Free Multi-Robot Control in Cluttered Environments with High-Dimensional Inputs by Jeffrey Chen, Rohan Chandra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-13098.txt.
Introduction
Teams of robots in tight, busy spaces must avoid both collisions and deadlocks, the frozen standoffs where nobody can move. Jeffrey Chen and Rohan Chandra present LIVEPOINT, a control framework where each robot decides on its own using only its onboard sensing. The method builds safety rules, called control barrier functions, directly over point clouds from lidar or cameras, rather than needing exact positions of everything. A shared fairness measure adjusts each robot's speed so the group eases through bottlenecks without freezing.
In simulations of doorways and intersections, crowded scenarios where rival methods collided or stalled, LIVEPOINT finished every run with no collisions and no deadlocks. Its paths were also smoother than the baselines in the doorway test, despite putting safety first. The authors argue that working straight from raw sensor clouds makes the method practical for real fleets, where exact state measurements are rarely available.
Catalog record
| CREATOR | Jeffrey Chen, Rohan Chandra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-13098
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LivePoint : Fully Decentralized, Safe, Deadlock-Free Multi-Robot Control in Cluttered Environments with High-Dimensional Inputs Thanks: Authors are with the Department of Computer Science, University of Virginia. {fyy2ws, aar8xx}@virginia.edu Jeffrey Chen, Rohan Chandra Abstract Fully decentralized, safe, and deadlock-free multi-robot navigation in dynamic, cluttered environments is a critical challenge in robotics. Current methods require exact state measurements in order to enforce safety and liveness e.g. via control barrier functions (CBFs), which is challenging to achieve directly from onboard sensors like lidars and cameras. This work introduces LivePoint , a decentralized control framework that synthesizes universal CBFs over point clouds to enable safe, deadlock-free real-time multi-robot navigation in dynamic, cluttered environments. Further, LivePoint ensures minimally invasive deadlock avoidance behavior by dynamically adjusting agents’ speeds based on a novel symmetric interaction metric. We validate our approach in simulation experiments across highly constrained multi-robot scenarios like doorways and intersections. Results demonstrate that LivePoint achieves zero collisions or deadlocks and a 100 % 100\% success rate in challenging settings compared to optimization-based baselines such as MPC and ORCA and neural methods such as MPNet, which fail in such environments. Despite prioritizing safety and liveness, LivePoint is 35 % 35\% smoother than baselines in the doorway environment, and maintains agility in constrained environments while still being safe and deadlock-free. I INTRODUCTION The dream of having robots work with us in our kitchens, construction sites, and hospitals has driven interest in multi-robot navigation among autonomous vehicles [ 1 , 2 , 3 , 4 , 5 ] , warehouse robots [ 6 ] , and personal home robots [ 7 ] . Often, these applications feature small, cluttered environments (such as doorways, hallways, or rooms filled with obstacles). Humans naturally and gracefully navigate these environments every day, such as by weaving through a crowd or slowing down by just enough to let another reach the doorway first [ 8 , 9 , 10 ] . For robots to seamlessly navigate through these cluttered environments in a similar manner, they must learn to navigate like humans–safely, gracefully, and without getting stuck (deadlock-free). Conventional wisdom [ 11 , 12 , 13 , 14 ] tells us that in order for robots to achieve human-like mobility in cluttered environments, their low-level controllers need exact and accurate state measurements of their surroundings which is difficult in practice to realize, especially if the environment is dynamic. Most roboticists, however, would ideally prefer navigation systems that produce human-like trajectories directly using input from onboard sensors such as lidars and cameras, without relying on expensive mapping and perception for exact state measurements [ 15 ] . For instance, Sa et al. [ 15 ] perform point cloud-based single robot navigation to handle dynamic environments, allowing robots to react to rapidly changing obstacles. Fig. 1 : Our decentralized approach enables effective, safe, live, and socially compliant robot navigation in cluttered environments using only high-dimensional point cloud input. There are several challenges to safe and deadlock-free multi-robot navigation in cluttered environments with high-dimensional inputs such as point clouds. The first key challenge is that ensuring both safety and liveness using dense point clouds can be complex [ 15 , 16 ] and thus, computationally expensive. For instance, some analytical methods use control barrier functions (CBFs) [ 15 , 17 ] to guarantee safety, which requires intensive computations to evaluate the barrier function and its derivatives. Additionally, in decentralized systems, we have no central authority that can coordinate agents in a manner that deadlocks will be prevented or resolved, particularly critical when agents are self-interested (each optimizes its own individual objective function) and have conflicting objectives [ 6 , 18 , 18 , 19 , 20 ] . Lastly, learning-based methods [ 21 , 22 , 23 , 24 , 25 ] can struggle with generalization and lack formal safety guarantees. Moreover, cluttered environments pose additional challenges in computing safe paths for multiple robots, particularly due to geometric symmetry in the environment [ 26 ] . Symmetry arises when multiple robots find themselves in nearly identical situations–having similar distances to their goals, nearly equal velocities, and overlapping optimal trajectories [ 27 ] . Unlike humans, who naturally resolve such conflicts through social cues and subtle motion adjustments, robots lack an inherent mechanism to break symmetry, making coordination difficult and leading to deadlocks [ 28 ] . Geometric and model-based methods [ 29 , 30 , 31 ] have been explored to address navigation in such environments, but conflicting navigation objectives can still result in deadlock [ 26 ] . Reactive collision avoidance techniques, such as Optimal Reciprocal Collision Avoidance (ORCA) [ 32 ] attempt to resolve these issues by computing admissible velocity sets. However, in highly constrained environments, these methods can fail, as robots overly adjust their velocities to avoid collisions but ultimately stall [ 33 ] . Many existing approaches remain too conservative to effectively navigate cluttered environments without deadlock [ 26 ] . I-A Main Contributions To address these challenges, we propose a new multi-robot navigation approach that takes as input point clouds and produces in real-time safe and deadlock-free trajectories for fully decentralized robots in cluttered environments. Key to our approach is a novel universal CBF formulation that dynamically and simultaneously computes safety and liveness certificates for the controller. The safety component of the universal CBF follows the standard CBF definition commonly employed in the literature [ 34 ] . The liveness component is driven by an interaction function that intelligently breaks deadlock-causing symmetry between agents in a minimally invasive fashion, and is cast as a CBF. In summary, our contributions are as follows: 1. A fully decentralized multi-robot navigation algorithm with point cloud input: We introduce a sequential control strategy that enables each agent to dynamically adjust its safety constraints based on real-time observations of other agents. Each robot processes point cloud data to construct CBFs while considering the motion of dynamic obstacles (i.e., other agents) in a real time, iterative framework, where each control cycle takes 0.04 seconds. 2. Synthesizing a universal CBF for safety and liveness: We introduce a deadlock prevention mechanism that quantifies symmetry between interacting agents, identifying cases where robots are likely to deadlock, particularly in highly constrained spaces like doorways and intersections. When symmetry is detected, we apply minimal velocity perturbations to proactively break deadlock-prone configurations while maintaining safety guarantees. By integrating the deadlock detection mechanism within the same framework as the CBF constraints, LivePoint unifies CBF-based safety and deadlock avoidance into a single cohesive approach, eliminating the need for separate heuristics or rule-based strategies. Our universal CBF ensures that each robot not only avoids collisions but also maintains continuous progress, even in highly constrained environments. We evaluate our proposed multi-agent Depth-CBF framework in simulation scenarios, including highly constrained environments such as narrow doorways and intersections. Results show that LivePoint reduces collisions and deadlocks to zero and achieves 100% successful navigation in challenging settings where previous methods fail. I-B Organization of Paper Section II presents relevant prior work that has been done in the areas relevant to our work. Section III introduces the problem formulation, including the notation used throughout the paper, general notions of multi-agent navigation, and the concept of Social Mini Games. Section IV presents important