Source-linked AI summary
Tutorial on dynamic average consensus: the problem, its applications, and the algorithms
Solmaz S. Kia, Bryan Van Scoy, Jorge Cortes, Randy A. Freeman, Kevin M. Lynch, Sonia Martinez
TL;DR
The paper addresses how communicating agents can track the average of locally time-varying reference signals without centralizing information. It provides a tutorial synthesis of distributed dynamic average consensus formulations, applications, algorithms, trade-offs, and convergence requirements. The paper reports that dynamic consensus tracks changing averages better than repeatedly reinitialized static consensus, while guarantees depend on network connectivity and signal variation.
Problem
Distributed agents need to track the average of time-varying local references despite information being distributed across the network and finite propagation time.
Method
The article gives a tutorial overview of distributed dynamic average consensus algorithms, their applications, design trade-offs, and convergence requirements.
Results
Dynamic consensus produces better tracking than static consensus reinitialized at each sampling time.
Takeaways & Limitations
Dynamic average consensus provides a distributed basis for applications including formation tracking, state estimation, and optimization.
Takeaways & Limitations
Zero-error tracking of an arbitrarily fast average is infeasible without prior information about the signals’ generating dynamics.
Abstract
from arXiv · showhide
This paper considers the problem of dynamic average consensus algorithm design for a group of communicating agents. This problem consists of designing a distributed algorithm that enables a group of agents with communication and computation capabilities to use local interactions to track the average of locally time-varying reference signals at each agent. The objective of this article is to provide an overview of the dynamic average consensus problem that serves as a comprehensive introduction to the problem definition, its applications, and the distributed methods available to solve them. Our primary intention, rather than providing a full account of all the available literature, is to introduce the reader, in a tutorial fashion, to the main ideas behind dynamic average consensus algorithms, the performance trade-offs considered in their design, and the requirements needed for their analysis and convergence guarantees.
Centralized solutions have drawbacks
Dynamic average consensus is motivated by the limitations of centralized and repeatedly reinitialized static approaches for tracking distributed, time-varying signals. The paper presents a tutorial overview of distributed algorithms, applications, design trade-offs, and convergence requirements.
- Centralized solutions have drawbacks: Centralized averaging is fragile, unscalable, delayed, identifier-dependent, and exposes reference signals across the network.Its single centralized agent creates a single failure point, while communication and memory requirements grow with network size.
- Multiple instantiations of static average consensus algorithms are not able to deal with dynamic problems: Zero-order sampling with repeated static consensus cannot track changing references exactly because information propagation requires finite time.The resulting error depends on the static algorithm’s convergence speed and the rate at which inputs change.
- Multiple instantiations of static average consensus algorithms are not able to deal with dynamic problems: Dynamic consensus retains past actions and produces better tracking than static consensus reinitialized with current samples.In the numerical comparison, the dynamic algorithm tracks the changing average more closely, whereas static consensus lacks sufficient time to converge between samples.
- Objectives and roadmap of the article: The article fills a tutorial gap by unifying dynamic average consensus developments rather than attempting a complete literature account.It emphasizes algorithmic ideas, performance trade-offs, and requirements for analysis and convergence guarantees.
- Objectives and roadmap of the article: The paper introduces problem formulation, applications, static-consensus foundations, dynamic algorithms, graph-theoretic tools, and algorithm shortcomings.Applications span distributed formation, state estimation, and optimization in network systems.
Dynamic Average Consensus: Problem Formulation
Dynamic average consensus uses local interactions and internal states so agents can asymptotically track the average of time-varying local reference signals. Desired algorithms are distributed, scalable, robust, and correct, but convergence depends on connectivity and signal variation.
- Dynamic Average Consensus: Problem Formulation: Each agent uses its local reference and out-neighbor information to drive an agreement state toward the network-wide average.The driving command may be memoryless or generated by local internal dynamics.
- Dynamic Average Consensus: Problem Formulation: Dynamic average consensus supports both continuous-time and discrete-time signals and algorithms, including execution over communicating networks.Discrete-time formulations seek convergence at sampled times, and Algorithm 1 illustrates per-agent execution.
- Dynamic Average Consensus: Problem Formulation: The agreement state can also represent a physical quantity indirectly, such as a mobile agent’s position, by computing reference signals to be tracked.The paper distinguishes logical computational states from physical states with more complex dynamics.
- Dynamic Average Consensus: Problem Formulation: The desired algorithm properties are scalability, robustness to practical disturbances, and correctness through exact convergence or a formal error guarantee.Examples of disturbances include delays, packet drops, changing membership, and noisy measurements.
- Dynamic Average Consensus: Problem Formulation: Agreement requires sufficiently frequent information flow through the communication network.The formulation assumes a fixed directed communication topology and local scalar reference signals.
- Dynamic Average Consensus: Problem Formulation: Zero-error tracking of an arbitrarily fast average is infeasible without prior information about the signals’ generating dynamics.Convergence guarantees therefore depend on both network connectivity and the rate of change of the reference signals.
Applications of Dynamic Average Consensus in Network Systems
Dynamic average consensus supports distributed coordination, estimation, and optimization by computing changing global quantities from local information. The paper illustrates these roles in formation tracking, sensor-network estimation, resource allocation, and convex optimization.
- Distributed formation control: A two-layer architecture lets mobile agents track moving targets by computing the targets’ geometric center in a cyber layer and controlling motion in a physical layer.Agents maintain prescribed relative offsets from the time-varying geometric center.
- Distributed state estimation: Networked sensors can replace a fusion-center implementation with distributed local filtering to avoid a single failure point and costly sensor-to-center communication.The centralized alternative uses a Kalman filter for minimum-variance state estimation, while distributed methods fuse local measurements with neighboring estimates.
- Distributed unconstrained convex optimization: For convex differentiable costs with L-Lipschitz gradients, trajectories of the cited distributed optimization method converge to the optimum for 0 < η < 1.This result is stated for the algorithm in (6).
- Distributed unconstrained convex optimization: Dynamic consensus estimates coupling terms online so distributed optimization can proceed without halting at each step for exact global aggregation.For Nesterov-based optimization, the estimated cumulative gradient is fed into the algorithm while the optimization updates the quantity being estimated.
- Distributed resource allocation: In optimal resource allocation, agents cooperatively meet a demand while minimizing the sum of their convex local costs.The formulation assigns each agent a scalar decision x_i and cost function f_i.
- Distributed resource allocation: Resource-allocation applications include optimal dispatch in power networks, optimal routing, and economic systems.A microgrid demand-response example uses flexible loads to collectively adjust power consumption for grid regulation.
- Distributed resource allocation: A centralized primal-dual formulation for resource allocation couples agents through the demand mismatch, which dynamic consensus can estimate online.The approach uses local reference signals such as x_i(t) − d/N when agents know demand and network size.
A Look at Static Average Consensus Leading up to the Design of a Dynamic Average Consensus Algorithm
Static consensus initializes agents with fixed reference values and uses Laplacian feedback, whereas dynamic consensus continuously injects references to track changing averages. Algorithm (11) offers asymptotic tracking under specified signal and graph conditions, but derivative knowledge and initialization requirements constrain implementation.
- Static average consensus: Static consensus starts each agent at its reference value and updates agreement states using weighted feedback based on neighbor differences.Its stacked dynamics are ˙x(t) = −L x(t) in continuous time and x(k + 1) = (I −L) x(k) in discrete time.
- A first design for dynamic average consensus: Algorithm (11) achieves zero asymptotic tracking error for connected graphs when each reference signal has left-half-plane Laplace poles and at most one zero pole.These conditions correspond to signals that are asymptotically constant.
- A first design for dynamic average consensus: Algorithm (11) can also perfectly track unbounded references when their uncommon components asymptotically converge to a constant, provided the special initialization is satisfied.The bound depends on the disagreement component ∥(I_N −1)˙u(τ)∥ rather than the full derivative ∥˙u(τ)∥.
- A first design for dynamic average consensus: Tracking performance improves with graph connectivity because the smallest nonzero Laplacian eigenvalue measures information-diffusion speed and shapes the tracking bound.For algorithm (11), convergence to the error bound is no worse than Re(λ2); switching graphs replace this rate with λ under admissibility conditions.
- Implementation challenges and solutions: Algorithm (16) avoids explicit reference differentiation and is robust to bounded communication errors, but its zero-sum internal-state initialization limits agent arrivals and departures.Algorithm (11) instead requires derivative information and exact initial reference conditions; initialization perturbations can produce steady-state bias.
Continuous-Time Dynamic Average Consensus Algorithms
Continuous-time algorithms address changing reference signals through distributed dynamics, with robustness, convergence, and tracking performance shaped by initialization, graph structure, signal variation, and design parameters.
- Algorithm overview: The reviewed algorithms differ in driving commands, initialization requirements, derivative-information needs, and robustness properties.Alternative implementations can remove explicit access to reference-signal derivatives.
- Robustness to initialization and permanent agent dropout: Algorithm (19) uses additional dynamics and adjustable communication structures to track inputs with unbounded common derivative components.A change of variables removes the need for explicit derivative knowledge, while two adjacency matrices provide extra performance-design freedom.
- Robustness to initialization and permanent agent dropout: For bounded-rate dynamic signals, algorithm (19) has an ultimately bounded tracking error whose performance depends on signal-derivative magnitude and graph connectivity.Its convergence analysis assumes strongly connected, weight-balanced digraphs and uses an input-to-state stability bound.
- Robustness to initialization and permanent agent dropout: Algorithm (19) is robust to initialization errors and can accommodate agent arrivals and departures while retaining satisfactory tracking performance.The formation-control simulation includes an agent leaving the network at t = 10 s.
- Controlling the rate of convergence: FOI-DC combines fast consensus dynamics with slower tracking dynamics so the convergence rate can be prescribed independently of interaction topology.A small ϵ improves tracking accuracy and increases the fast subsystem’s decay rate, while β regulates the dominant rate and control effort.
- Robustness to initialization and permanent agent dropout: Algorithm (25) also provides robustness to measurement perturbations and preserves input privacy against adversaries with access to network communication histories.The paper relates algorithm (25) to algorithms (11) and (16) through a pole-zero cancellation while distinguishing their robustness and privacy properties.
Discrete-Time Dynamic Average Consensus Algorithms
Discrete-time algorithms accommodate bandwidth limits by communicating at discrete instants, but their parameters must be selected carefully for convergence and rate optimization. Extra dynamics accelerate convergence, while proportional-integral structures provide robustness to initial conditions.
- Motivation and algorithm families: Discrete-time dynamic average consensus replaces continuous communication with sampled communication because continuous communication is infeasible under practical bandwidth constraints.The paper analyzes discrete-time algorithms as a response to this implementation limitation.
- Motivation and algorithm families: Unlike continuous-time algorithms, discrete-time parameters require careful selection to ensure convergence, making convergence-rate optimization a central design problem.The analysis assumes a constant, connected, undirected graph with known or bounded smallest and largest nonzero Laplacian eigenvalues.
- Rate optimization: The paper analyzes standard, accelerated, and proportional-integral discrete-time algorithms using Laplacian eigenvalue decompositions and root-locus design.Root-locus optimization minimizes the maximum pole magnitude over disagreement modes.
- Accelerated algorithms: Adding extra dynamics can significantly improve convergence with only a small increase in memory, although it changes the convergence behavior from finite-time to exponential.The accelerated algorithm requires each agent to maintain two internal state variables.
- Robust algorithms: Proportional-integral algorithms are slower than their corresponding non-robust counterparts but remain robust to initial conditions.The comparison is presented through convergence rates plotted as a function of λ2/λN.
- Convergence guarantees: With parameters selected according to the prescribed design, the analyzed algorithms converge exponentially to the average with rate ρ under the stated graph and initialization conditions.Theorem 5 assumes constant reference signals and a connected, undirected graph.
Perfect Tracking Using A Priori Knowledge of the Input Signals
When reference-signal models are known, dynamic average consensus algorithms can exploit that information to achieve zero or arbitrarily small steady-state tracking error under stated conditions. Different designs trade off delay, stability, graph requirements, and robustness to initial conditions.
- Motivation: Slowly varying signals can produce large tracking errors, motivating algorithms that incorporate prior knowledge of reference-signal models.Model-free guarantees are strongest for constant or slowly varying signals.
- Polynomial signals: Degree m−1 polynomial signals can be tracked with zero steady-state error by cascading m dynamic average consensus stages, each containing a pole at z = 1.The cascaded design uses the internal model principle; correct initialization is required for the illustrated algorithms.
- Polynomial signals: One cascaded design has zero-delay estimates and numerical stability, but its tracking performance degrades when the communication graph is time-varying.The alternative design has delayed output but retains tracking properties under time-varying graphs.
- Bandlimited signals: Bandlimited signals can be tracked with arbitrarily small steady-state error by prefiltering references and applying repeated consensus stages under graph, scaling, approximation, and arithmetic conditions.The prefilter must approximate z^m over the passband, and exact arithmetic is required for arbitrarily small error.
- Bounded derivatives: Continuous-time finite-time tracking can guarantee zero error when a derivative bound is known, but sliding-mode chattering increases control-energy expenditure and smoothing introduces boundary-layer error.The derivative bound is used to select the sliding-mode gain.
- Bounded derivatives: Adding extra dynamics places a strictly proper transfer function between Laplacian blocks and changes convergence from finite time to exponential.This design choice alters the convergence behavior of the algorithm.
Conclusions
The article surveys distributed dynamic average consensus algorithms, their applications, and their design trade-offs. It identifies event-triggered communication, cloud-based coordination, interconnection, self-tuning, and privacy preservation as continuing research directions.
- Conclusions: The survey covers applications including distributed formation control, state estimation, convex optimization, and optimal resource allocation.It also reviews continuous- and discrete-time algorithms and designs using prior information about reference signals.
- Conclusions: Algorithm design balances convergence rate, steady-state error, robustness to initial conditions, internal stability, memory, and communication requirements.These properties are presented as desirable but potentially competing features in large-scale interconnected systems.
- Open directions: Event-triggered methods remain an open direction because triggering criteria must provide convergence guarantees and support performance comparisons with periodic implementations.The stated goal is to replace periodic or continuous sampling and control with deliberate aperiodic interactions for improved efficiency.
- Open directions: Cloud-based coordination could let agents exchange estimates, plans, or fallback strategies indirectly through a cloud rather than direct peer-to-peer communication.The cloud may also provide high-performance computation to agents with limited capabilities.
- Open directions: Interconnecting dynamic average consensus with other coordination layers is identified as a fertile area for research and applications involving changing estimates and time-varying agent signals.The article also suggests self-tuning mechanisms that adapt execution to signal evolution.
- Open directions: Privacy-preserving dynamic average consensus is still in its infancy despite the importance of protecting sensitive signals in distributed automated systems.The paper highlights power networks, smart transportation, the Internet of Things, and manufacturing systems as relevant scenarios.
Sidebar: Further Reading
Related work addresses robustness, graph assumptions, and implementation variations in dynamic average consensus. Average computation over directed or time-varying networks requires structural or algorithmic conditions that may fail under communication disruptions.
- Robustness and variants: Prior studies examine robustness to fixed delays, additive input disturbances, time-varying communication graphs, and driving-command saturation.Other variants incorporate specific agent dynamics or different problem structures.
- Graph assumptions: For directed interactions, average consensus commonly assumes a weight-balanced graph, equivalent to a doubly stochastic consensus matrix.Computing an average requires explicit or implicit use of out-degrees, global identifiers, randomization, or suitable asynchronous updates.
- Graph assumptions: Time-varying graph approaches require the graph to remain weight-balanced, although expected balance can preserve solvability when failures disrupt that property.Communication-range limits and obstacle blocking are examples of disruptions that can destroy weight balance.
Authors Information
The article is authored by researchers whose affiliations and backgrounds span mechanical and aerospace engineering, electrical engineering, applied mathematics, robotics, and distributed multi-agent systems.
- Authors: Solmaz S. Kia is an Assistant Professor of Mechanical and Aerospace Engineering at the University of California, Irvine.She earned her Ph.D. from UCI and earlier degrees from Sharif University of Technology.
- Authors: Bryan Van Scoy is a postdoctoral researcher at the University of Wisconsin–Madison studying distributed algorithms for multi-agent systems and optimization algorithms.His degrees include a Ph.D. in Electrical Engineering and Computer Science.
- Authors: Jorge Cortés is a Professor of Mechanical and Aerospace Engineering at the University of California, San Diego.His training includes mathematics and engineering mathematics.
- Authors: Randy Freeman is a Professor of Electrical Engineering and Computer Science at Northwestern University whose interests include distributed control and multi-agent systems.His research also covers robust, optimal, and nonlinear control.
- Authors: Kevin Lynch is a Professor and Chair of Mechanical Engineering at Northwestern University with research interests in robotics and complex systems.He is associated with the Neuroscience and Robotics Laboratory and the Northwestern Institute on Complex Systems.
- Authors: Sonia Martínez is a Professor of Mechanical and Aerospace Engineering at the University of California, San Diego.She received her Ph.D. in Engineering Mathematics from Universidad Carlos III de Madrid.