Multi-Hop Preconditioning for Large Rigid Formations

Robot swarms commonly hold a shape by descending a virtual energy. Each robot measures how far it is from its neighbors and moves to reduce the mismatch with the desired distances. This rule is fully local, and for well-chosen neighbor graphs it provably reaches the correct shape. It has a hidden cost at scale. A large triangulated formation behaves like an elastic sheet, and a sheet driven only by local springs relaxes its long, floppy bending modes very slowly. The time to settle grows roughly with the square of the formation's diameter. We propose to let each robot spend communication rather than motion. Between physical control steps, robots exchange a few rounds of messages with neighbors up to $\kappa$ hops away. From these messages each robot computes a multi-hop "preconditioned" version of its descent direction, one that anticipates how distant parts of the sheet will respond.

The central claim is that this multi-hop step keeps everything that makes potential-based control trustworthy. The robots use the same energy, reach the same set of rest configurations, and keep the same classification of which rest configurations are stable and which are escapable saddles. The energy also decreases monotonically, so a collision barrier is never crossed. What changes is speed: settling time should shrink by a factor between $\kappa$ and $\kappa^2$, depending on the construction, until $\kappa$ reaches the formation diameter. This makes communication radius a quantitative knob on convergence speed for nonlinear formation control. The existing theory of "how much locality costs" establishes such a knob only for linear systems.

Why this intersection, and what is actually open

Two bodies of work meet here without touching. On the formation side, Global Stabilization of Triangulated Formations computes the signature of the energy's curvature matrix (its Hessian) at every rest configuration of a triangulated Laman graph, a rigid graph grown by repeatedly attaching a new agent to two existing neighbors. That analysis proves that every wrong shape is an unstable saddle, so plain gradient descent almost surely reaches the target. Formation Control with Triangulated Laman Graphs supplies the same topological restriction. These papers constrain our design: any modification must provably preserve that saddle structure, or we lose the guarantee that is the whole reason to prefer potentials. Neither paper says anything about how convergence rate scales with formation size.

On the locality side, On the Optimal Control of Network LQR with Spatially-Exponential Decaying Structure shows that for stable linear networks the optimal feedback gain decays exponentially with graph distance, so truncating to $\kappa$ hops costs little. Stability and Regret Bounds on Distributed Truncated Predictive Control for Networked Dynamical Systems turns this into a truncated predictive controller whose regret decays exponentially in $\kappa$. Both results assume linear, open-loop-stable dynamics. Formations violate this in two ways. The energy is nonconvex. Near the target, its curvature is a stiffness matrix whose smallest nonzero eigenvalue shrinks with size, like a graph Laplacian on a mesh. The second fact means the uniform spatial decay those papers rely on should fail for large formations, which is precisely why locality hurts. We treat the linear theory as motivation and borrow its polynomial-truncation viewpoint, but we do not inherit its proofs.

The closest intersection papers do not address this. Distributed formation tracking using local coordinate systems couples a one-hop distance potential with a centroid estimator and never considers multi-hop information or size scaling. V-Formation via Model Predictive Control resizes neighborhoods adaptively, but it uses particle-swarm optimization and a globally propagated cost, and its guarantees cover only V shapes. Controlling and Stabilizing a Rigid Formation Using a Few Agents supplies a structural fact we reuse: reciprocal pairwise gradient flows are symmetric under rigid motions. None of these papers accelerates the flow itself.

Core Claim

Let $x$ stack all positions, let $V(x)=\tfrac14\sum_{(i,j)}(\|x_i-x_j\|^2-d_{ij}^2)^2$ be the distance energy, and let $R(x)$ be the rigidity matrix, whose rows are the edge vectors. The gradient is then $\nabla V = R^\top e$, where $e$ holds the squared-distance errors. We propose the controller

$$u = -\alpha\, p_\kappa\big(R(x)^\top R(x)\big)\,\nabla V(x),$$

Here $\alpha$ is a step size and $p_\kappa$ is a degree-$(\kappa-1)$ polynomial that is positive on $(0,\lambda_{\max}]$. The matrix $R^\top R$ is always positive semidefinite and has the same sparsity as the graph, so each matrix-vector product costs exactly one round of neighbor messages. Applying $p_\kappa$ therefore costs $\kappa-1$ rounds, and each agent's command depends on its $\kappa$-hop neighborhood.

Two properties follow. First, $\dot V = -\alpha\,\nabla V^\top p_\kappa(R^\top R)\nabla V \le 0$ everywhere, with equality only where $\nabla V=0$, because $\nabla V$ lies in the range of $R^\top$. The rest configurations are therefore exactly those of gradient descent. At each one, the linearization $p_\kappa H$, restricted to directions that are not rigid motions, has the same count of positive and negative eigenvalues as $H$. This holds because a product of a positive-definite and a symmetric matrix inherits the symmetric factor's inertia. Consequently, the Hessian-signature argument of Global Stabilization of Triangulated Formations transfers unchanged, and wrong shapes remain saddles.

Second, near the target the error contracts at a rate governed by $\min_\lambda \lambda\,p_\kappa(\lambda)$ over the stiffness spectrum. There are two natural choices of polynomial. A truncated Neumann series, $p_\kappa(\lambda)=\sum_{k<\kappa}(1-\alpha\lambda)^k$, needs no spectral knowledge and improves the slowest-mode rate by a factor of about $\kappa$. A shifted Chebyshev polynomial needs an estimate of the smallest stiffness eigenvalue and improves it by about $\kappa^2$, following standard Chebyshev approximation of $1/\lambda$. For a 2D triangulated lattice with diameter $D$, the condition number scales like $D^2$, so we predict

$$T_{\text{settle}}(\kappa) \propto \frac{D^2}{\kappa^{s}},\qquad s\in\{1,2\},$$

with saturation once $\kappa$ approaches $D$.

Evaluating the matrix products requires neighbors' message vectors to be expressed in each agent's own frame. Agents therefore need relative orientation to each neighbor, either a shared compass or measured mutual bearings. This is a real limitation compared with the purely local-frame setting of Distributed formation tracking using local coordinate systems, and we state it as a limitation rather than hide it.

Research Program

The theory has three parts. First, we prove the two properties above: preserved critical set and inertia, and monotone energy decrease with a repulsive barrier term added. The barrier result is the key safety property. It holds for any polynomial that is positive on the relevant spectrum, because the barrier becomes part of $V$ and the modified matrix remains positive semidefinite. Second, we derive the rate law for triangulated lattices and Henneberg-grown triangulated graphs. We will bound the smallest stiffness eigenvalue in terms of diameter, and we will check empirically whether the inverse stiffness matrix, restricted away from rigid motions, fails to decay uniformly in $N$. That result would be the nonlinear-formation counterpart of the open size-dependence question raised by the network LQR work, and we will report whatever we find. Third, we analyze robustness when the $\kappa$ message rounds are imperfect. Stale or dropped messages break the exact polynomial and can destroy positive-definiteness. We will derive a condition on message staleness under which descent still holds, and we will study a fallback that reverts to a lower degree when a round fails.

The engineering work is a simulator for double-integrator and kinematic agents in 2D and 3D. Communication runs at a configurable number of rounds per control period, with delay and packet loss. It also includes a small wheeled-robot replication.

Baselines

The naive reference point is plain one-hop gradient descent on the same energy, as in Distributed rigid formation control algorithm for multi-agent systems, with the step size tuned to the largest stable value. It shares our critical set and guarantees and differs only in the preconditioner, so it isolates the question. Beating it means a reduction in settling time that grows with $D$, at equal peak speed and equal minimum inter-agent distance.

The strongest competitor on the speed question is one-hop heavy-ball or Nesterov-damped second-order gradient dynamics. Momentum also buys the square-root improvement in conditioning, and it uses only one hop per step. It will be run on identical graphs, initial conditions, and actuator speed limits. Its momentum and damping will be tuned by grid search with the same budget we give to $\alpha$ and the Chebyshev spectral bound. Beating it means matching its settling time while having zero barrier violations and lower overshoot. Alternatively, it means beating its settling time outright when several communication rounds fit in each control period. If momentum matches us on settling, overshoot, and safety at every communication rate, the multi-hop design is unnecessary.

Two further references are needed. The first is a truncated predictive controller in the style of Stability and Regret Bounds on Distributed Truncated Predictive Control for Networked Dynamical Systems. It will be applied to the formation linearized at the target, with the same $\kappa$, and compared on settling time and per-agent compute. The second is a distributed neural controller distilled from centralized predictive control, following Neural Flocking: MPC-Based Supervised Learning of Flocking Controllers. That paper reports 1.6 ms per step against 1209 ms for centralized MPC, 100% convergence for 15 agents, and less than a 2% collision-rate increase at 40 agents. We will train it on our lattice scenarios with a matched data budget and compare success rate from random initializations at sizes beyond training.

The key ablation replaces $R^\top R$ with the plain graph Laplacian at the same $\kappa$. This tests whether shape-aware stiffness, rather than generic multi-hop averaging, produces the speedup. A second ablation compares Neumann and Chebyshev polynomials to test the predicted slopes of one and two.

Why not just…?

Why not just raise the gain of one-hop gradient descent? In discrete time, the stable step size is capped at about $2/\lambda_{\max}$, and physical speed limits cap it further. Raising the gain therefore speeds up only the stiff modes that are already fast; the slow bending modes stay slow. The baseline sweep above tests this directly by plotting settling time against gain until the flow becomes unstable or speed-limited.

Why not just use one-hop momentum? This is the real threat, since momentum and Chebyshev iteration are mathematically close relatives. The difference is where the iteration happens. Momentum iterates in physical space, so the swarm overshoots and energy is not monotone; kinetic energy can carry agents through a barrier. Our method iterates in the message layer between physical steps, so the physical path descends $V$ monotonically. If communication is no faster than motion, we expect momentum to match us on speed. The experiment varies the number of rounds per control period from one to $\kappa$ to locate the crossover honestly.

Why not just add longer-range sensing edges? Denser rigid graphs are stiffer and faster, but sensing range is set by hardware. Extra edges also change the rest-configuration structure, and the triangulated-graph guarantees do not automatically cover them. We will compare against graphs augmented with the same number of extra edges, and report both speed and the rate of convergence to wrong shapes.

Why not just distill a centralized controller? The neural flocking result is fast, but it offers no guarantee against converging to spurious shapes or crossing barriers. Non-Parametric Neuro-Adaptive Formation Control needs online adaptive terms to cover residual errors. Our comparison measures failures from out-of-distribution sizes and initializations.

Proposed Experiments

For the sanity check, we reproduce the eight-agent octagon tracking the trajectory $[6t, 5\cos t]$ from Distributed formation tracking using local coordinate systems, which reports lock-on within 1.5 seconds. With diameter four, we expect little gain; that is the point, and it confirms that the method does no harm. We also match the multi-layer UAV setting of Consensus Control of Large-Scale UAV Swarm Based on Multi-Layer Graph, which reports distances within 2 m in about 150 steps and full configuration in about 800 steps. That scenario lets us check whether flat multi-hop preconditioning matches a hand-built hierarchy.

The decisive scaling experiment uses triangulated lattices and Henneberg-grown graphs from 16 to 1024 agents. For each size we sweep $\kappa$ from 1 to $D$ and measure settling time to 1% shape error, peak speed, minimum pairwise distance, and communication rounds. There is no reported result on Lacuna for gradient-flow settling time as a function of formation size, so the one-hop baseline curve is itself a contribution. The prediction is falsified if the log-log slope of settling time against $\kappa$ is not near $-1$ for Neumann and $-2$ for Chebyshev before saturation.

The guarantee check runs $10^4$ random initializations per graph and counts convergence to wrong shapes. Our method should match gradient descent's near-zero rate, while the Laplacian ablation and augmented graphs may not.

The robustness check injects message delay, packet loss, and distance-measurement bias. Bias matters because reciprocal mismatch breaks gradient structure. For each condition we report the largest disturbance level at which monotone descent survives.

Finally, a five-robot wheeled replication reports the worst-case rigidity index used in Distributed rigid formation control algorithm for multi-agent systems, which found values above zero for successful formations and up to 2.5. We will check that preconditioning keeps the formation rigid during motion on real hardware.