⚡ electrical engineering

From Non-Rigid to Rigid: Safe Acquisition of Rigid Communication Graphs under Limited Sensing

This paper presents a distributed, collision-free control strategy that enables heterogeneous nonlinear multi-robot systems to autonomously acquire and maintain a rigid communication graph under limited sensing ranges without requiring an initial rigid topology or global position information.

Original authors: Saharsh, Vedhas Talnikar, Pushpak Jagtap

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Saharsh, Vedhas Talnikar, Pushpak Jagtap

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a flock of robotic birds trying to form a perfect, unbreakable diamond shape in the sky. In the world of robotics, this "diamond" is called a rigid formation. It's special because, unlike a floppy chain of paperclips that can twist and turn into any shape, a rigid formation holds its specific shape no matter how it moves. This is crucial for teams of robots doing things like carrying heavy loads or patrolling borders together.

But here's the catch: these robots have "night vision" goggles with a very short range. They can only see their immediate neighbors. If they start out scattered and just try to hold hands with whoever is closest, they often end up in a floppy chain (like a tree branch) that can bend and collapse. They need to find extra friends to hold hands with to become rigid, but they can't see far enough to find them without crashing into each other first.

This paper proposes a clever, step-by-step dance to solve this problem.

The Problem: The Floppy Chain

The authors start by pointing out a common mistake in robot research. Many existing methods assume the robots are already holding hands in a perfect, rigid formation. But in the real world, they aren't. If you have four robots in a line (1-2-3-4), they can bend like a snake. Robot 1 and Robot 4 could drift far apart, breaking the formation. To fix this, you need more connections. For four robots, you need at least five connections to make them rigid, not just three.

The paper explicitly argues against the idea that you can just rely on "connectivity" (making sure everyone is connected to someone). A connected group can still be floppy. It also argues against methods that try to fix a broken formation by just shoving robots together; this often leads to "deadlocks," where robots get stuck in a traffic jam, afraid to move because they might hit a neighbor, and never finish forming the shape.

The Solution: The "Splay" Dance

The authors designed a new way for robots to organize themselves, which they call a "Splay Scheme."

Imagine a tree growing from the ground up.

The Leaders: A few "leader" robots (at least two) start at the top. They know where they are in the world (like having a GPS).
The Layers: The other robots are organized in layers, like rings on a tree trunk.
The Dance: The leaders stay in a circle. The next layer of robots forms a smaller circle around their "parent" leader. The next layer forms an even smaller circle around their parents.

This creates a beautiful, shrinking spiral of robots. The paper proves mathematically that if the circles get smaller at just the right rate (using a "decay rate" of about 0.436 in their tests), the robots will naturally spread out enough to avoid crashing, but close enough to grab the extra hands they need.

How They Stay Safe

The biggest fear is that while robots are moving to find their new "hands" (connections), they will crash into each other. The paper uses a safety tool called a Control Barrier Function (CBF).

Think of this as an invisible, magical force field. If a robot sees another robot getting too close, this force field gently pushes it away, but only enough to keep them safe. It doesn't stop the robot from dancing; it just makes sure the dance doesn't turn into a pile-up. The authors extended this tool to handle robots that are speeding up or slowing down, not just moving at a constant speed.

The "Second Parent" Trick

Here is the magic trick that makes the formation rigid. In their "tree" structure, every robot has one main parent (the one it follows). But to make the whole group rigid, every robot needs a second parent from a different branch of the tree.

The "Splay" dance naturally moves the robots into positions where they can suddenly "see" this second parent. Once they spot them, they grab their hand. The paper shows that the required sensing range depends on the specific connection being made: agents in the outer layers need a range of at least 18 units to find a second parent within their own tree branch, while specific agents needing to connect to a different tree branch require a larger range of 50 units.

What They Actually Did

The authors didn't just dream this up; they tested it.

Simulations: They ran computer simulations with 27 robots. They started with the robots in a messy, non-rigid pile. The robots danced into their splay formation, grabbed their second parents, and by 12 seconds, they had formed a perfect, rigid structure. No crashes occurred.
Hardware: They also tested this with 5 real physical robots and 9 virtual robots in a motion-capture lab. The real robots successfully followed the plan, avoiding collisions and forming the shape.

What They Didn't Do

It's important to note what this paper doesn't claim. They didn't say this works for any number of robots or any environment. They specifically tested it on a flat, 2D plane (like a floor). They also didn't claim that their method is the only way to do it, but they did show that the old ways (which assume the robots are already rigid) fail when the robots start in a messy, non-rigid state.

The Bottom Line

This paper provides a recipe for a group of robots to go from a messy, floppy mess to a strong, rigid team, even if they can only see a short distance away. They do this by organizing themselves into shrinking circles, using a safety force field to avoid crashes, and grabbing extra "hands" from neighbors they couldn't see at the start. The math proves it works, and the robots in the lab proved it works in real life, all without needing to know their exact global location or having a perfect starting formation.

Technical Summary: From Non-Rigid to Rigid: Safe Acquisition of Rigid Communication Graphs Under Limited Sensing

Problem Statement
In multi-robot systems (MRS), achieving a unique formation shape typically requires a rigid communication graph. However, in practical scenarios, robots operate under limited sensing ranges and dynamic conditions, often resulting in initially non-rigid, tree-like topologies that cannot maintain a unique formation shape (e.g., a chain can bend into a ring). Existing literature largely assumes a rigid graph is already available or focuses on maintaining connectivity, failing to address the acquisition of rigidity from a non-rigid state. Furthermore, acquiring the necessary additional edges to achieve rigidity while operating in close proximity introduces significant collision risks. Current safety methods, such as those based on constant-velocity assumptions, are insufficient for accelerating nonlinear agents, and the interplay between safety constraints and rigidity acquisition often leads to deadlocks where agents halt indefinitely.

Methodology
The paper proposes a distributed framework for acquiring a rigid, collision-free communication graph for heterogeneous nonlinear multi-agent systems without relying on global absolute positions. The approach integrates a specific graph architecture, a geometric formation strategy, and a safety-preserving controller.

Interleaved Layered Directed Acyclic Graph (iLDAG):
The system utilizes a time-invariant spanning forest structure called iLDAG. This architecture organizes agents into a hierarchy of directed trees rooted at leaders. Agents are indexed using an "Interleaved Breadth-First Indexing" (iBFI) scheme across layers. This structure ensures that while the initial graph is a forest (non-rigid), it provides a systematic scaffold for edge acquisition.
Splay Scheme and Geometric Constraints:
To facilitate the acquisition of missing edges required for rigidity, the agents are guided toward a "splay formation." In this scheme, children of a parent agent arrange themselves uniformly on a circular orbit around that parent. The orbit radius decays geometrically across layers ( $\eta_s = \eta_0 \alpha^s$ ).
- Safety: The geometric parameters (orbit radii and decay rate) are analytically derived to guarantee a minimum safe distance between all agents, preventing collisions even during the transient phase of formation.
- Rigidity: The splay geometry is designed such that the sensing range constraints are satisfied to allow agents to establish "cross-family" maintenance links (connecting to a second parent or a parent in an adjacent tree).
Control Framework (C3BF-QP):
The control law is a hierarchical quadratic programming (QP) optimization that balances formation tracking with safety:
- Nominal Controller: A distributed controller drives agents toward the splay formation consensus using relative position and velocity information from neighbors. It operates on the time-invariant spanning forest.
- Safety Filter: To ensure safety during the acquisition process, the framework employs an extended Collision Cone Control Barrier Function (C3BF). Unlike previous methods limited to constant-velocity obstacles, this C3BF is adapted for accelerating nonlinear agents. It incorporates Lipschitz constants of the system dynamics and accumulated relative state information (propagated from parents) to handle model uncertainties.
- Optimization: The final control input is computed by minimizing the deviation from the nominal controller subject to the C3BF constraints, ensuring forward invariance of the safe set.

Key Contributions

Rigidity Acquisition Framework: A novel method to transition a multi-agent system from a non-rigid, tree-based topology to a rigid graph using only local relative information, without assuming an initial rigid structure.
Heterogeneous System Support: The approach accommodates heterogeneous agents with different sensing ranges and nonlinear dynamics (e.g., differential-drive robots, Ackermann vehicles) without requiring global position data (GPS-denied environments).
Formal Safety Guarantees: The paper provides formal guarantees for inter-agent collision avoidance during the rigidity acquisition process, extending C3BF theory to accelerating obstacles and proving forward invariance of the safe set.
Deadlock Avoidance: By enforcing a unique target (splay orbit) for each agent, the method prevents the deadlocks common in safety-constrained rigidity acquisition where agents might otherwise block each other indefinitely.

Results
The proposed framework was validated through:

Simulations: A MATLAB simulation with 27 agents (including leaders and followers) demonstrated the transition from a non-rigid initial state to a rigid maintenance graph. The results showed that agents successfully acquired the requisite cross-family links while maintaining safety margins, with position and velocity errors converging to zero.
Hardware Experiments: Experiments conducted in a motion-capture environment using physical robots (differential-drive) and virtual agents (Gazebo) confirmed the method's reliability under limited sensing capabilities. The system successfully formed the rigid splay structure without collisions.
Comparative Analysis: The paper contrasts its approach with rigidity-matrix-based and algebraic connectivity-based methods. It demonstrates that existing maintenance-only controllers fail to achieve formation convergence when starting from a non-rigid graph, often resulting in drift or failure to converge.

Significance
The paper claims to address a critical gap in distributed formation control: the safe and systematic acquisition of rigidity from a non-rigid state under sensing limitations. By decoupling the time-invariant structural constraints (the iLDAG) from the time-varying edge acquisition (the splay scheme), the method ensures that rigidity is achieved without compromising safety. The work is significant for applications in GPS-denied environments and dynamic scenarios where robots must self-organize into rigid formations from arbitrary, non-rigid initial configurations while avoiding collisions. The validation through both simulation and hardware experiments underscores the practical viability of the proposed C3BF-QP controller for real-world multi-robot deployments.