PaperlayerView exact revision on arXiv

Source-linked AI summary

Coherence in Large-Scale Networks: Dimension-Dependent Limitations of Local Feedback

Bassam Bamieh, Mihailo R. Jovanović, Partha Mitra, Stacy Patterson

arXiv:1112.4011v1math.OCcs.MAeess.SY

TL;DR

The paper asks whether local feedback can maintain coherence in large stochastic consensus and vehicular-formation networks. It defines macroscopic coherence measures and analyzes their asymptotic scaling through Fourier and energetic modes. The results show dimension-dependent limitations: one-dimensional vehicular formations cannot remain globally coherent under distributed disturbances using only local feedback, whereas sufficiently high dimensions can regulate large-scale disturbances under stated conditions.

  • Problem

    The paper asks whether local feedback is sufficient to maintain coherence in large-scale consensus and vehicular networks subject to stochastic disturbances.

  • Method

    The paper defines macroscopic coherence measures and analyzes their H2, Gramian, eigenvalue, and Fourier-symbol representations under local-feedback constraints.

  • Results

    One-dimensional vehicular formations cannot achieve large-scale coherence with only localized feedback under any amount of distributed stochastic disturbance; higher dimensions have more favorable boundedness under stated conditions.

  • Takeaways & Limitations

    Low-dimensional local feedback fails to regulate large-scale disturbances, producing slow temporal and long spatial accordion-like modes, while higher-dimensional networks can regulate them under suitable conditions.

Abstract

from arXiv · show

We consider distributed consensus and vehicular formation control problems. Specifically we address the question of whether local feedback is sufficient to maintain coherence in large-scale networks subject to stochastic disturbances. We define macroscopic performance measures which are global quantities that capture the notion of coherence; a notion of global order that quantifies how closely the formation resembles a solid object. We consider how these measures scale asymptotically with network size in the topologies of regular lattices in 1, 2 and higher dimensions, with vehicular platoons corresponding to the 1 dimensional case. A common phenomenon appears where a higher spatial dimension implies a more favorable scaling of coherence measures, with a dimensions of 3 being necessary to achieve coherence in consensus and vehicular formations under certain conditions. In particular, we show that it is impossible to have large coherent one dimensional vehicular platoons with only local feedback. We analyze these effects in terms of the underlying energetic modes of motion, showing that they take the form of large temporal and spatial scales resulting in an accordion-like motion of formations. A conclusion can be drawn that in low spatial dimensions, local feedback is unable to regulate large-scale disturbances, but it can in higher spatial dimensions. This phenomenon is distinct from, and unrelated to string instability issues which are commonly encountered in control problems for automated highways.

I. INTRODUCTION

The paper studies whether local feedback can preserve coherence in large consensus and vehicular-formation networks under stochastic disturbances. It relates performance to spatial dimension, network topology, and macroscopic measures of formation rigidity.

  • The platooning problem is treated as the one-dimensional case of vehicular formation control on regular lattices in arbitrary spatial dimensions.
  • The study investigates performance limits of globally stabilizing local feedback laws using coherence measures that quantify resemblance to a rigid lattice or solid object.
  • Consensus and vehicular formations are modeled as networked dynamical systems with first-order and second-order local dynamics, respectively.
  • Macroscopic performance variances are computed through H2 norms, Grammians, and eigenvalue sums, while circulant structure links feedback gains to Fourier-symbol eigenvalues.
  • The networks are defined on d-dimensional discrete tori, with spatial indices interpreted modulo N and multidimensional Fourier transforms used throughout.
  • Consensus with stochastic disturbances models fluctuating node states rather than asymptotic equilibrium, making fluctuation variance a measure of approximate consensus.

B. Vehicular Formations

Vehicular formations use second-order position–velocity dynamics on d-dimensional toroidal grids, with feedback structure constrained by spatial invariance, locality, and measurement assumptions.

  • B. Vehicular Formations: The formation contains N^d identical vehicles arranged on a d-dimensional torus, with each vehicle modeled by position and velocity states.
  • B. Vehicular Formations: The controlled vehicle dynamics include double-integrator motion, control input u, and mutually uncorrelated white disturbances w.
  • B. Vehicular Formations: Vehicles are intended to follow desired trajectories with constant heading velocity while maintaining grid spacing Δ in every coordinate direction.
  • B. Vehicular Formations: Position and velocity deviations from desired trajectories are represented by ˜x_k := x_k − ¯x_k and ˜v_k := ˙x_k − ¯v.
  • B. Vehicular Formations: Feedback is full-state, linear, and expressed as u = G˜x + F˜v, with operators G and F determined by available measurements and structural assumptions.
  • B. Vehicular Formations: Relative feedback uses neighboring differences, whereas absolute feedback uses positions or velocities measured against a moving reference coordinate system.
  • C. Structural assumptions: Spatial invariance makes feedback convolutional, and reflection symmetry gives even feedback arrays and real-valued Fourier symbols.
  • C. Structural assumptions: Locality restricts feedback to a neighborhood of width 2q, where q is independent of network size N; coordinate decoupling simplifies multidimensional control calculations.

III. PERFORMANCE MEASURES

The paper defines microscopic and macroscopic output variances to measure local regulation, long-range disorder, and deviation from the network average, then derives Fourier-domain formulas for them.

  • Output variances remain finite when unstable mean modes are unobservable from the output, and they are quantified by squared H2 norms.
  • Spatial invariance makes output variances equal across sites; individual output variances equal total H2 norm divided by system size M = N^d.
  • The three performance measures are local error, long-range deviation, and deviation from average.
  • Local error measures differences between neighboring nodes or vehicles and is therefore a microscopic measure.
  • Long-range deviation measures disagreement or spacing deviation between the most distant nodes or vehicles, capturing end-to-end rigidity.
  • Deviation from average measures each state’s or position error’s departure from the network-wide average.
  • Macroscopic errors are interpreted as disorder or lack of coherence, and both macroscopic measures have similar asymptotic scaling with system size.
  • Fourier-domain Lyapunov equations and symbols of feedback, dynamics, and output operators yield formulas for the six consensus and vehicular cases.

IV. UPPER BOUNDS USING STANDARD ALGORITHMS

The paper derives asymptotic upper bounds by evaluating simple standard feedback laws, with the resulting performance scalings depending strongly on spatial dimension.

  • Upper bounds are derived for all three performance measures in consensus and vehicular formation problems using feedback laws resembling the standard consensus algorithm.
  • The vehicular analysis distinguishes relative and absolute position and velocity feedback, covering all four combinations.
  • The asymptotic behavior of the upper bounds depends importantly on the underlying spatial dimension d.

A. Upper bounds in the consensus case

The standard consensus algorithm yields dimension-dependent macroscopic upper bounds, while its individual local error remains bounded for every network size and spatial dimension.

  • The standard consensus algorithm’s local error is bounded above for any network size in any dimension d.
  • Deviation-from-average and long-range deviation are compared through sums whose terms share the same sign, with the former using a subset of the latter’s terms.
  • The macroscopic upper bounds are obtained by evaluating Fourier-symbol sums and their asymptotics across spatial dimensions.The derivation uses reflection symmetry and bounds on sums involving the Fourier symbol.
  • The resulting upper bounds have the same form when expressed using total network size M = N^d.The dimension-dependent constant C_d is independent of N and β.

B. Upper bounds for vehicular formations

Vehicular-formation upper bounds depend on which absolute or relative position and velocity feedback terms are available. Absolute feedback can bound local errors, while viscous friction makes relative-velocity-only cases scale like consensus.

  • Relative position and velocity feedback alone produces a local-error scaling with the same asymptotic form as standard consensus, multiplied by an extra 1/β factor.
  • Adding absolute velocity or absolute position feedback makes the local-error sum scale like M, yielding a constant local error after division by network size.Both absolute position and velocity feedback also yield uniformly bounded local error.
  • Four vehicular feedback strategies combine relative or absolute position and velocity feedback, with their asymptotic scalings summarized by microscopic and macroscopic measures.Table I reports quantities up to factors independent of M or β.
  • When g_o < 0 and f_o < 0, each term in the relevant sum is bounded and the entire sum scales as M.
  • Viscous friction μ > 0 supplies absolute velocity feedback even with relative velocity error feedback only, giving formation-performance scaling similar to consensus.
  • Increasing β proportionally to M can bound one-dimensional consensus macroscopic errors, but requires feedback gains that grow unboundedly with M.The paper identifies this control-effort growth as unacceptable in realistic control problems.

V. LOWER BOUNDS

The lower-bound analysis covers all local linear static state-feedback algorithms under bounded control variance. It finds that topology and structural locality impose the same asymptotic performance limits as standard algorithms.

  • The analysis studies any linear static state-feedback algorithm satisfying locality and structural assumptions under a constraint on control effort.Control effort is measured by the steady-state variance of the control signal at each site.
  • The lower bounds scale like the standard algorithms’ upper bounds, with the control-effort bound W replacing the algorithm parameter β.
  • Under control-effort constraints, no algorithm in the analyzed class improves asymptotic performance over the standard algorithms.The conclusion attributes the fundamental limitations primarily to network topology and structural constraints rather than parameter selection.
  • Lower bounds are derived for microscopic and macroscopic performance measures using H2-norm arguments valid across an entire class of feedback gains.The detailed calculations presented focus on deviation-from-average macroscopic measures.
  • The Fourier analysis uses locality to bound low-frequency feedback symbols and obtain network-size-dependent lower bounds after dividing by M = N^d.

B. Lower bounds for vehicular formations

The lower-bound analysis connects localized feedback structure to asymptotic coherence limits in vehicular formations, while simulations illustrate the resulting large-scale motion. The examples distinguish coherence loss from string instability and relate energetic modes to slow temporal and long spatial scales.

  • B. Lower bounds for vehicular formations: Lower bounds for vehicular formations use Fourier symbols of local feedback gains and compare their asymptotic behavior with upper bounds.For relative position and relative velocity feedback, the lower-bound argument repeats the consensus-case reasoning for the corresponding symbols.
  • B. Lower bounds for vehicular formations: The derivation assumes nonpositive absolute feedback terms and a control-effort constraint.These conditions are imposed before establishing the lower bounds.
  • B. Lower bounds for vehicular formations: The absolute position and absolute velocity feedback case has finite upper bounds, making a separate lower-bound analysis unnecessary.The paper states that the question of lower bounds is moot in this case.
  • B. Lower bounds for vehicular formations: The resulting lower bounds match the corresponding upper-bound scalings, with 1/β^2 replaced by 1/W^3.The constants c1 and c2 are independent of N and W.
  • VI. EXAMPLES AND MULTISCALE INTERPRETATION: A 100-vehicle simulation with distributed disturbances exhibits slow accordion-like motion in the full formation despite relatively regulated local spacing.The zoomed-out view reveals fluctuating large-scale shape features, whereas the zoomed-in view shows vehicle-to-vehicle distances remaining comparatively well regulated.
  • VI. EXAMPLES AND MULTISCALE INTERPRETATION: The coherence loss has a slow temporal and long spatial wavelength signature: small-scale disturbances are regulated better than large-scale disturbances.The paper interprets this pattern as a limitation of local feedback against large-scale disturbances.
  • VI. EXAMPLES AND MULTISCALE INTERPRETATION: Under white disturbances, slower temporal modes contain more energy, and the most energetic motions combine slow temporal dynamics with long spatial wavelengths.The systems are diagonalizable through the spatial Discrete Fourier Transform, linking modal behavior to spatial scales.
  • VI. EXAMPLES AND MULTISCALE INTERPRETATION: String instability is distinct from the studied coherence phenomenon: with disturbance applied only to the leader, trajectories can remain regulated against that disturbance.High temporal-frequency disturbances are regulated well, while low-frequency disturbances propagate deeper before eventually being regulated farther from the leader.

VII. DISCUSSION

The paper develops dimension-dependent coherence limits for local feedback and emphasizes that conventional eigenvalue-based performance measures can misrepresent large-network behavior. It also identifies scope limits and open questions for broader network classes and controller designs.

  • General networks: The correct generalization of spatial dimension to arbitrary graphs remains unresolved, although coherence and error measures extend more readily.
  • Order of local dynamics: For local dynamics modeled as chains of n integrators, the cutoff dimension for bounded macroscopic measures is 1 + 2n.
  • Mistuning designs: Optimal LQR platoon designs can exhibit underdamped slow modes with long spatial wavelengths, producing the same incoherence phenomenon.
  • Measuring performance: Performance measures can remain bounded even as system eigenvalues approach zero in the large-network limit.
  • Measuring performance: Consensus macroscopic measures are uniformly bounded for d ≥3, despite eigenvalue-based convergence indicators becoming arbitrarily poor with increasing network size.
  • Measuring performance: The least damped eigenvalue is not a sufficiently meaningful performance measure for large-scale systems.
  • Mistuning designs: Mistuning can improve H∞ performance, while its effect on the H2 measures studied here remains an open question.

APPENDIX

The appendix derives asymptotic bounds by converting multidimensional Fourier sums into integrals. The resulting estimates are governed by the behavior near the lower integration limit as network size grows.

  • Fourier preliminaries: The discrete Fourier transform uses spatial indices for array locations and wavenumbers for spatial frequency variables.
  • Fourier preliminaries: For circulant convolution operators, eigenvalues are Fourier-symbol values, and the trace equals their sum.
  • Asymptotic estimates: Asymptotic sums are bounded using upper and lower Riemann sums for integrals over multidimensional regions.
  • Asymptotic estimates: The grid spacing is Δ = 1/N, so the large-network limit is analyzed through the lower integration limit approaching zero.
  • Asymptotic estimates: The integral is evaluated in hyperspherical coordinates, introducing a dimension-dependent constant C_d.
  • Asymptotic estimates: A second bound follows by approximating an integral with a fourth-power denominator; details are omitted.

C. Proof of Lemma 3.1

The proof reduces performance calculations to decoupled Fourier-mode Lyapunov equations. Output-specific Fourier symbols then yield the H2 norms for the vehicle-formation measures.

  • Consensus and vehicular calculations: The consensus Lyapunov equation is solved mode by mode after coordinate decoupling makes the Fourier-domain matrices diagonal.
  • Consensus and vehicular calculations: The zero Fourier mode contributes zero because the performance output has zero Fourier symbol there.
  • Consensus and vehicular calculations: For vehicular formations, the state equation uses position and velocity states, with performance output determined by the selected operator C.
  • Consensus and vehicular calculations: The total vehicle-formation H2 norm is obtained by summing the solved Fourier-mode contributions, with a multiplicative factor d from the trace.
  • Performance measures: The local error measure uses an output operator satisfying C* C = −1/(2dβ) O, which gives the corresponding V_loc result.
  • Performance measures: The long-range deviation and deviation-from-average measures are obtained by inserting their Fourier symbols into the general norm formula.

2) Vehicular formations:

The vehicular-formation proof computes the H2 norm through Fourier-domain Lyapunov equations. Stability and locality assumptions then support bounds on the resulting modal sum.

  • Proof of Lemma 5.1: The proof rewrites consensus dynamics so that u is treated as an output and computes its H2 norm using formula (24).
  • 2) Vehicular formations:: Vehicular formations use the dynamics in (7) together with a position-based output equation.
  • 2) Vehicular formations:: Because the output depends on all states, the consensus formula is unavailable, so the H2 norm is computed through a Lyapunov equation.
  • 2) Vehicular formations:: Only the first and last matrix equations are needed to obtain tr(Ŷ_n).
  • 2) Vehicular formations:: Diagonal submatrices with equal entries reduce the calculation to scalar equations.
  • 2) Vehicular formations:: The resulting H2 norm is obtained after solving those scalar equations.
  • Proof of Lemma 5.1: Stability gives f̂_n ≤ 0 and ĝ_n ≤ 0, while locality bounds the norm of g.
  • Proof of Lemma 5.1: The Fourier coefficients are real with â_0 = 0, so the relevant modal sum becomes the ℓ1-norm of {â_n}.
Loading 1112.4011v1…