Imagine a robot composed of thousands of tiny autonomous blocks. To navigate a narrow pipe, climb a ledge, or engulf an object, these blocks must detach, slide past one another, and reassemble into an entirely new shape. If a single block loses contact with the main body during this process, it can become permanently stranded, losing both its power source and its communication link.
For this reason, maintaining global connectivity throughout a shape transformation is a strict survival constraint. As noted by Abdullah Almethen et al. in On efficient connectivity-preserving transformations in a grid, breaking connectivity during reconfiguration is highly detrimental to systems requiring continuous structural integrity. However, restricting a system to only connectivity-preserving steps turns simple geometric reconfigurations into highly constrained, computationally complex problems.
The Algorithmic Cost of Staying Connected
Why does a connectivity constraint make shape transformation so difficult? If modules can disconnect and move independently, transforming one shape into another is computationally straightforward. Enforcing continuous connectivity, however, introduces severe algorithmic overhead.
George Skretas et al. proved in On the transformation capability of feasible mechanisms for programmable matter that shape transformation problems that are solvable in polynomial time without connectivity constraints suddenly become PSPACE-complete when continuous connectivity must be maintained. This complexity explosion happens because modules act as physical obstacles to one another; a move that seems locally optimal might inadvertently cut off a bottleneck path, trapping other modules or fragmenting the system.
This challenge is vividly illustrated in the "sliding cube" model of modular robotics. One might intuitively assume that modules on the exterior of a shape can always safely detach and move. However, Tillmann Miltzow et al. in Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition) disproved this long-standing assumption. By constructing a layered "rope basket" configuration that carefully encloses internal empty spaces (voids), they demonstrated that exterior modules can become completely locked. In their design, no outer cube can move without breaking the global connectivity of the robot, proving that local greedy movement strategies are insufficient for universal reconfiguration.
Geometric Strategies: Perimeter Routing and Line Moves
To bypass these topological deadlocks, researchers design specific mechanical movement primitives and routing protocols that inherently preserve the underlying graph structure.
Perimeter Routing and Minimal Seeds
One elegant way to guarantee connectivity is to restrict module movement strictly to the boundary of the shape. Matthew Connor et al. in Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for all Orthogonal Convex Shapes and Matthew Connor et al. in Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach developed centralized algorithms that rely on a tiny, mobile cluster of modules—a "minimal seed"—to safely guide other modules along the shape's perimeter. By using formal sequences to determine exactly when a module can safely rotate without causing a split, they guarantee that the system remains a single connected component throughout the transformation.
A similar intuition applies to decentralized swarms. Mario Coppola et al. demonstrated in Provable self-organizing pattern formation by a swarm of robots with limited knowledge that if individual robots only move when their immediate neighbors form a single connected group, the global swarm can safely reorganize its perimeter without risking fragmentation or collisions.
Line and Pushing Moves
Moving modules one by one along a perimeter scales poorly for large systems. To accelerate this, Abdullah Almethen et al. introduced a "pushing lines" mechanism in Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter. By shifting entire rows or columns of entities in parallel using coordinated folding and extending sequences, they achieved sub-quadratic transformation speeds ($O(n \log n)$) while strictly preserving continuous physical connectivity.
Physical Stability: From Topology to Rigidity
In physical implementations, simple topological connectivity (keeping the graph connected) is often insufficient. The robot must also maintain mechanical stability so it does not collapse under gravity or external forces during the transition.
Infinitesimal Rigidity
Daniel Zelazo et al. elevated this constraint from basic graph connectivity to infinitesimal rigidity in Rigidity Maintenance Control for Multi-Robot Systems. By optimizing a distributed gradient controller based on a spectral metric called the rigidity eigenvalue, they proved that maintaining structural stiffness inherently guarantees network connectivity. Because rigidity is a stricter mathematical requirement than simple connectivity, it provides a built-in safety margin for multi-robot formations navigating cluttered environments.
Static Determinacy in Trusses
For Variable Topology Trusses (VTTs)—modular space-frame robots that change shape by extending links and swapping nodes—reconfiguration requires a delicate balance between continuous joint motion and discrete topological changes. As detailed by the authors of Motion Planning for Variable Topology Truss Modular Robot, the system must enforce static determinacy during split and merge actions. By ensuring each node remains connected to a minimum number of structural members at all times, the robot avoids mechanical failure or collapse while joints are moving.
Chao Liu et al. expanded on this in Motion Planning for Variable Topology Trusses: Reconfiguration and Locomotion by partitioning the robot's configuration space into enclosed stable subspaces. This allows the truss to temporarily alter its topology to bypass internal geometric constraints that would otherwise block continuous movement, maintaining static stability relative to a shifting center of mass.
Managing Forces and Compliance
When modules interact physically, structural stability also depends on geometry and joint compliance. Hangxin Liu et al. observed in Aggregating Single-wheeled Mobile Robots for Omnidirectional Movements that modular systems using circular geometries frequently suffer from low shear resistance, causing individual units to slip against one another under high torque.
To combat this in rugged environments, Runze Xiao developed a framework in MRS-CWC: A Weakly Constrained Multi-Robot System with Controllable Constraint Stiffness for Mobility and Navigation in Unknown 3D Rough Environments that implements "weak constraints" with adjustable stiffness. By dynamically softening or stiffening the physical joints between units based on real-time environmental interactions, the interconnected chain can distribute forces and provide mutual support, allowing the collective to traverse obstacles that would cause discrete robot swarms to fail.
Even in automated design optimization, maintaining these physical connections is vital. Jie Xu et al. achieved this in An End-to-End Differentiable Framework for Contact-Aware Robot Design by merging the control handles of adjacent component cages at their connection points. This constraint ensures that as individual parts deform to optimize performance, the robot remains a single, structural unit with functional joints.
Distributed Coordination and Spatial Partitioning
Finally, maintaining connectivity requires careful coordination at path intersections or during spatial division. In early work on distributed modular robots, Zack J. Butler et al. introduced the PacMan algorithm in Distributed Motion Planning for 3D Modular Robots with Unit-Compressible Modules. This approach utilizes specialized state variables and message types to manage local disconnections at path intersections, preventing these temporary gaps from merging and fragmenting the robot.
For multi-robot coverage tasks, Lin Li et al. utilized a tree-partition strategy in Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments to ensure that the spatial regions assigned to different robots remain contiguous, simplifying control and preventing collisions by maintaining the connectivity of robot-assigned partitions.
Key Foundational Work
Distributed Motion Planning for 3D Modular Robots with Unit-Compressible Modules (2002) — contributed 3 concept elements to this direction.
Multirobot Rendezvous With Visibility Sensors in Nonconvex Environments (2009) — contributed 2 concept elements to this direction.