Source-linked AI summary
Resilient Consensus of Second-Order Agent Networks: Asynchronous Update Rules with Delays
Seyed Mehran Dibaji, Hideaki Ishii
TL;DR
The paper addresses resilient consensus for sampled-data double-integrator networks subject to malicious agents and delayed information. It develops MSR-type algorithms for synchronous and partially asynchronous updates, deriving graph-robustness conditions for safety and agreement. The results include conditions for fixed and jointly robust time-varying networks, while the asynchronous analysis has a gap between sufficient and necessary conditions.
Problem
The problem is achieving consensus while normal second-order agents face arbitrary malicious inputs and delayed neighbor information.
Method
The paper uses MSR-type filtering that ignores extreme neighbor positions, analyzing synchronous and partially asynchronous updates under f-total and f-local malicious models.
Results
The results derive graph-robustness conditions for resilient consensus, including (2f + 1)-robustness for the asynchronous f-local model and joint (2f + 1)-robustness for time-varying networks.
Takeaways & Limitations
The supported consequence is a robust-graph characterization of resilient consensus for second-order networks under synchronous and partially asynchronous updates with bounded delays.
Takeaways & Limitations
The asynchronous analysis has a gap between sufficient and necessary conditions, and a 2f-robust graph can fail to achieve resilience under asynchronous DP-MSR.
Abstract
from arXiv · showhide
We study the problem of resilient consensus of sampled-data multi-agent networks with double-integrator dynamics. The term resilient points to algorithms considering the presence of attacks by faulty/malicious agents in the network. Each normal agent updates its state based on a predetermined control law using its neighbors' information which may be delayed while misbehaving agents make updates arbitrarily and might threaten the consensus within the network. Assuming that the maximum number of malicious agents in the system is known, we focus on algorithms where each normal agent ignores large and small position values among its neighbors to avoid being influenced by malicious agents. The malicious agents are assumed to be omniscient in that they know the updating times and delays and can collude with each other. We deal with both synchronous and partially asynchronous cases with delayed information and derive topological conditions in terms of graph robustness.
1 Introduction
The paper studies resilient consensus for second-order agents under malicious behavior, using MSR-type filtering and graph robustness to handle synchronous and partially asynchronous updates. It extends prior work to the f-total model and delayed asynchronous information.
- Motivation: The study addresses consensus in networked control systems vulnerable to attacks and malicious misbehavior.Consensus requires agents interacting locally to reach a common value.
- Resilient consensus approach: MSR-type algorithms mitigate attacks by disregarding the most deviated or unsafe neighbor values without identifying malicious agents.These algorithms have been used in both computer science and control.
- Update rules: The asynchronous setting allows occasional normal-agent updates and delayed neighbor data, while malicious agents know update times and delays and may collude.Normal agents do not know their neighbors’ updating times.
- Contributions: The paper derives graph-robustness conditions for both synchronous and partially asynchronous updates, with synchronous rules requiring less connectivity than asynchronous rules.A new asynchronous update scheme is introduced for delayed information.
- Problem scope: The paper analyzes second-order agents, which model autonomous mobile robots and vehicles but have more complicated dynamics than first-order agents.The work considers the f-total malicious model, which permits at most f faulty agents in the entire network.
2 Problem Setup
The problem setup defines directed-graph robustness, sampled-data double-integrator agents, malicious-agent models, and resilient consensus. Normal agents must remain within a safety interval and asymptotically agree with zero velocity despite arbitrary malicious inputs.
- 2.1 Graph Theory Notions: Partially asynchronous updates share sampling times but occur at different times using delayed information, unlike fully asynchronous updates with independent clocks.The paper focuses on the partially asynchronous case.
- 2.1 Graph Theory Notions: Graph robustness is the critical connectivity notion for MSR-type resilient consensus algorithms.The paper defines (r, s)-robustness through conditions on every pair of nonempty disjoint node subsets.
- 2.1 Graph Theory Notions: An (r, s)-robust graph is also r-robust, at least r-connected, and has a directed spanning tree, while r-connectedness alone does not imply r-robustness.The graph parameters additionally satisfy r ≤ ⌈n/2⌉.
- 2.2 Agent Dynamics: Each agent has double-integrator dynamics, with position derivative equal to velocity and velocity derivative equal to control input.The system is discretized with sampling period T using zeroth-order-held control inputs.
- 2.2 Agent Dynamics: At each step, agents update position and velocity using a time-varying interaction graph, relative neighbor positions, and their own velocity.The control law uses adjacency weights, a positive scalar α, and desired relative positions δ_i.
- 2.3 Malicious Agents: A normal agent follows the predefined control, whereas a malicious agent may choose arbitrary control inputs; f-total and f-local models bound malicious-agent counts globally or per neighborhood.The upper bound on misbehaving agents is assumed known.
- 2.4 Resilient Consensus: Resilient consensus requires safety of normal positions within a bounded interval and agreement on a common limiting position with velocities converging to zero.The safety interval is determined by normal agents’ initial positions and velocities.
3 Synchronous Networks
The synchronous DP-MSR algorithm enables resilient consensus for second-order agents by filtering extreme neighbor positions, under a precise graph-robustness condition and parameter assumptions.
- 3.1 DP-MSR Algorithm: DP-MSR filters up to f neighbors with largest positions and f with smallest positions before forming the update graph.The remaining edges determine the time-varying graph, adjacency matrix, and Laplacian matrix.
- 3.2 System Model: The normal agents’ positions are convex combinations of current and previous positions, while malicious control inputs do not directly enter their new positions.Malicious initial positions may still influence the first update, but extreme values outside the normal range are filtered when permitted by f.
- 3.2 System Model: The sampling-period and control-parameter condition can permit oscillatory agent movements, although it is less restrictive than a condition in prior work.The paper identifies this assumption as a subject for further study.
- 3.3 A Necessary and Sufficient Condition: Under the f-total malicious model, resilient consensus holds if and only if the underlying graph is (f +1, f +1)-robust.The associated safety interval is determined by the initial positions of the normal agents.
- 3.3 A Necessary and Sufficient Condition: The maximum normal-agent position is nonincreasing and the minimum is nondecreasing, keeping all normal positions within the safety interval.This establishes the safety condition used in the consensus proof.
- 3.3 A Necessary and Sufficient Condition: The proof shows that progressively shrinking sets of normal agents near the limiting bounds eventually become empty because the number of normal agents is finite.This argument supports convergence under the graph-robustness condition.
- 3.4 Convergence Rate: The resulting resilient consensus has an exponential convergence rate.The rate is reduced by ignored edges and can also be slowed when malicious agents remain clustered with normal agents.
4 Networks with Partial Asynchrony and Delay
The paper extends resilient second-order consensus to partially asynchronous updates with delayed information, using asynchronous DP-MSR and graph-robustness conditions. It establishes sufficient and necessary conditions, identifies a gap between them, and develops extensions to f-local faults and time-varying networks.
- Partial Asynchrony and Delays: Asynchronous DP-MSR modifies the synchronous algorithm to handle agents updating at different times and using delayed neighbor information.The setting is more vulnerable because malicious agents know update times and delays and can exploit them.
- Consensus Conditions: A (2f + 1)-robust graph guarantees resilient consensus under the f-total malicious model, while (f + 1, f + 1)-robustness is necessary.The safety interval is given by (20).
- Consensus Conditions: The asynchronous analysis requires denser connectivity than the synchronous setting because malicious agents can present different positions to different normal agents.This behavior contributes to the more restrictive condition in the delayed setting.
- Limitations and Counterexample: A 2f-robust graph with minimum degree 2f + 1 can still fail to achieve resilient consensus under asynchronous DP-MSR.In the constructed scenario, normal agents in G3 and G4 remain at distinct positions, preventing position agreement.
- Further Results: The result extends to the f-local malicious model: (2f + 1)-robustness guarantees resilient consensus with the same safety interval.The proof depends only on the number of malicious agents in each normal agent’s neighborhood.
- Further Results: For time-varying networks, joint (2f + 1)-robustness with condition (25) guarantees resilient consensus under the f-total/f-local model.The safety interval remains (20).
5 Numerical Example
The numerical examples show that synchronous DP-MSR achieves resilient consensus on a robust graph but fails on a non-robust graph, while asynchronous delayed updates require stronger robustness.
- Synchronous Network: The conventional control reaches agreement by following the malicious agent, so the safety condition is violated.The safety interval is S = [0.19, 8.54].
- Synchronous Network: With f = 1, synchronous DP-MSR keeps normal agents within the safety interval and achieves consensus on the (2,2)-robust graph.This confirms Theorem 3.3 in the simulated setting.
- Synchronous Network: Removing edge (2, 5) makes the graph non-robust, and synchronous DP-MSR fails to attain consensus.Agent 5 cannot update because it has only two neighbors after the edge removal.
- Asynchronous Delayed Network: Under partially asynchronous delayed updates, the (2,2)-robust graph does not guarantee consensus against a malicious agent appearing at different positions.Normal agents split into groups around x̂_i = 9 and x̂_i = 3.7.
- Asynchronous Delayed Network: Making the five-node graph complete produces a 3-robust graph whose responses verify the sufficient condition for the asynchronous setting.This is the only 3-robust graph with five nodes.
6 Conclusion
The paper studies resilient consensus for second-order agent networks with known bounds on faulty agents and develops MSR-type algorithms for synchronous and partially asynchronous updates with bounded delays.
- The proposed algorithms address resilient consensus under synchronous updates and partially asynchronous updates with bounded delays.The paper also develops topological conditions in terms of robust graphs.