Jump to
MODULE 09 // SWARM SYSTEMS

UAV Swarm Systems

A single UAV can be shot down. A swarm of two hundred cannot all be intercepted simultaneously β€” and that asymmetry is transforming military doctrine. Swarm systems are among the most technically demanding problems in autonomous UAV engineering: coordinating hundreds of agents without a central controller, maintaining formation through communication loss and attrition, and allocating tasks dynamically as the situation evolves.

Algebraic Graph Theory Consensus Algorithms MARL Coordination Mesh Networking

πŸ“š  REFERENCES: Intelligent Coordination of UAV Swarm Systems Ch.2–5  Β·  MDPI Autonomous Control Ch.7–8  Β·  Bestaoui Sebbane Β§11

9.1 Why Swarms? The Military Logic

Plain English First

The defining military advantage of a drone swarm is not any individual capability β€” it is mass combined with coordination. A single MQ-9 Reaper costs $30 million and takes years to build. A single Switchblade 600 costs $70,000. For the cost of one Reaper, you could buy ~430 Switchblades. Even if an adversary's air defence system destroys half of them, 215 still reach their targets. No air defence system can simultaneously engage hundreds of small, fast, independently manoeuvring targets. This is the saturation attack doctrine β€” and it is why swarms are the most strategically disruptive development in military aviation since precision-guided munitions.

The Intelligent Coordination of UAV Swarm Systems identifies three distinct military value propositions that swarms offer beyond individual platforms: Intelligent Coordination Ch.2

Saturation

Launch more simultaneous, independently manoeuvring threats than the adversary can intercept. Each interceptor can only engage one target; the swarm sends many more. Even with 50% attrition, mission-critical mass survives. The economics favour the attacker when individual unit cost is low.

Distributed ISR

A hundred small sensors spread across a battlespace collect more total intelligence than one large sensor with higher individual quality. Swarm ISR is impossible to fully suppress β€” destroying 30% of nodes still leaves 70% operational. Coverage is persistent and geographically complete.

Cooperative Effect

Coordinated swarms achieve effects impossible for any individual: one group suppresses air defences while another strikes the main target; triangulation from multiple bearings provides precise geolocation; relayed communications extend operational range beyond any single platform.

Key Real-World Swarm Programmes

ProgrammeNationTypeScaleKey Capability
DARPA OFFSETUSAUrban ISR/strike250 agentsGPS-denied urban swarm coordination
DARPA GremlinsUSAAir-launched, recoverable4–20 per launchLaunched from manned aircraft, recovered in flight
PerdixUSA (MIT LL)Micro ISR swarm103 launched simultaneouslyCollective decision-making; no central controller
Shahed-136/191Iran/RussiaLoitering munition wave10s–100s per attackMass saturation of air defence; GPS + IR terminal
CH-901ChinaAttritable loiteringUp to 200Coordinated strike, heterogeneous payloads
The Perdix Demonstration β€” What Decentralised Swarms Can Do In November 2016, the US DoD demonstrated 103 Perdix micro-drones launched from F/A-18 Super Hornets. The drones collectively decided on formations, adapted when drones were removed, and maintained a persistent ISR orbit β€” with no pre-programmed routes and no individual pilot. The entire coordination emerged from shared algorithms running on each drone's embedded processor communicating over a mesh network. This demonstration established that swarm coordination at military scale was not theoretical β€” it was operational. Intelligent Coordination Ch.2

9.2 Algebraic Graph Theory β€” The Mathematical Backbone

Plain English First

To reason about how information spreads through a swarm β€” who can talk to whom, how quickly a command propagates, whether the group will ever reach agreement β€” you need a mathematical language for describing networks of interconnected agents. That language is graph theory. Each drone is a node in a graph; each communication link is an edge. The algebraic properties of this graph (its eigenvalues, connectivity, diameter) directly determine the swarm's coordination capabilities. A swarm with a disconnected communication graph cannot reach consensus β€” no matter how good its individual algorithms are.

Graph Definitions for Swarms

A swarm communication topology is modelled as a directed or undirected graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$: Intelligent Coordination Ch.3

Graph ElementSwarm InterpretationNotation
Vertex set $\mathcal{V}$Set of UAV agents $\{1, 2, \ldots, N\}$$|\mathcal{V}| = N$ (swarm size)
Edge set $\mathcal{E}$Active communication links between UAVs$(i,j) \in \mathcal{E}$ if $i$ can receive from $j$
Adjacency matrix $A$$A_{ij} = 1$ if link $(i,j)$ exists, else 0$A \in \{0,1\}^{N\times N}$
Degree matrix $D$$D_{ii} = \sum_j A_{ij}$ (number of neighbours of $i$)$D = \text{diag}(d_1, \ldots, d_N)$
Laplacian $L$$L = D - A$ β€” encodes connectivity algebraically$L \in \mathbb{R}^{N\times N}$, PSD, $L\mathbf{1} = \mathbf{0}$
Neighbourhood $\mathcal{N}_i$Set of UAVs within communication range of $i$$\mathcal{N}_i = \{j : (i,j) \in \mathcal{E}\}$

The Graph Laplacian β€” Spectral Properties

The graph Laplacian $L$ is the central object in swarm coordination theory. Its eigenvalues directly encode the network's coordination capabilities: Intelligent Coordination Ch.3

Graph Laplacian Eigenspectrum $$0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_N$$

$\lambda_1 = 0$ always (corresponding eigenvector $\mathbf{v}_1 = \mathbf{1}/\sqrt{N}$, the uniform consensus state). The graph is connected if and only if $\lambda_2 > 0$. The second-smallest eigenvalue $\lambda_2$ β€” the algebraic connectivity (Fiedler value) β€” quantifies how well connected the graph is. Large $\lambda_2$: high connectivity, fast consensus. Small $\lambda_2 \to 0$: near-disconnected, slow or impossible consensus. $\lambda_N / \lambda_2$ (spectral ratio) characterises coordination difficulty.

Worked Example 9.1 β€” Laplacian of a 4-UAV Swarm

Four UAVs form a ring topology: 1↔2↔3↔4↔1. Compute the Laplacian, its eigenvalues, and interpret their operational meaning.

Adjacency matrix (ring): $$A = \begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}, \quad D = \text{diag}(2,2,2,2)$$ Laplacian: $$L = D - A = \begin{bmatrix}2&-1&0&-1\\-1&2&-1&0\\0&-1&2&-1\\-1&0&-1&2\end{bmatrix}$$

Eigenvalues: $\lambda = \{0, 2, 2, 4\}$ (computed analytically for cycle graph $C_4$: $\lambda_k = 2 - 2\cos(2\pi k/N)$).

Interpretation: $\lambda_2 = 2 > 0$ β†’ graph is connected, consensus is achievable. Convergence rate proportional to $\lambda_2 = 2$. Compare: a path graph (1β†’2β†’3β†’4) has $\lambda_2 \approx 0.586$ β€” much slower consensus. A fully connected graph ($K_4$) has $\lambda_2 = 4$ β€” fastest possible consensus. For a military swarm with 200 nodes, the planner must ensure $\lambda_2 > \lambda_{2,min}$ at all times β€” requiring periodic topology updates as UAVs manoeuvre and links drop. Intelligent Coordination Ch.3

9.3 Consensus Algorithms β€” Reaching Agreement Without a Leader

Plain English First

Consensus is the problem of getting all agents in a swarm to agree on a common value β€” a heading, a target position, a timing signal β€” using only local communication between neighbours. No central controller sends the answer to everyone; each agent only talks to a few neighbours, yet through repeated local exchanges, the entire swarm converges on a single agreed value. This is how biological swarms work (bird flocks, fish schools) and how military swarms must work to remain functional when communication infrastructure is destroyed or jammed. The mathematics of when and how fast this convergence happens is exactly the graph Laplacian theory from section 9.2.

The Linear Consensus Protocol

The fundamental consensus algorithm for continuous-time multi-agent systems: Intelligent Coordination Ch.3

Continuous-Time Consensus Protocol $$\dot{x}_i(t) = \sum_{j \in \mathcal{N}_i} a_{ij}\left(x_j(t) - x_i(t)\right) = -\sum_{j \in \mathcal{N}_i} a_{ij}\left(x_i(t) - x_j(t)\right)$$ $$\dot{\mathbf{x}} = -L\,\mathbf{x}$$

$x_i \in \mathbb{R}$: state of agent $i$ (e.g., desired heading, altitude setpoint); $a_{ij}$: communication weight on link $(i,j)$. Each agent moves its state toward the average of its neighbours' states. The collective dynamics: $\dot{\mathbf{x}} = -L\mathbf{x}$. Since $L$ is positive semi-definite with $\lambda_1 = 0$, the system is stable and all states converge to the average: $x_i(\infty) = \bar{x} = \frac{1}{N}\sum_j x_j(0)$.

Theorem 9.1 β€” Consensus Convergence Rate

For the linear consensus protocol $\dot{\mathbf{x}} = -L\mathbf{x}$ on a connected graph, the disagreement vector $\boldsymbol{\delta}(t) = \mathbf{x}(t) - \bar{x}\mathbf{1}$ converges exponentially:

$$\|\boldsymbol{\delta}(t)\| \leq \|\boldsymbol{\delta}(0)\|\, e^{-\lambda_2 t}$$

Proof sketch: Decompose $\mathbf{x}(t) = \bar{x}\mathbf{1} + \boldsymbol{\delta}(t)$. Since $L\mathbf{1} = \mathbf{0}$, only $\boldsymbol{\delta}$ is affected by the dynamics. The solution is $\boldsymbol{\delta}(t) = e^{-Lt}\boldsymbol{\delta}(0)$. The slowest mode decays as $e^{-\lambda_2 t}$ β€” the Fiedler eigenvalue governs convergence speed.

Consensus time constant: $\tau = 1/\lambda_2$. To achieve 95% convergence ($\|\boldsymbol{\delta}\| \leq 0.05\|\boldsymbol{\delta}(0)\|$): $t_{95\%} = 3\tau = 3/\lambda_2$. For a 200-drone ring swarm with $\lambda_2 \approx 0.001$ (ring graph, large N): $t_{95\%} \approx 3000$ s β€” far too slow for tactical operations. Solution: use a better topology (random geometric graph, small-world network) that achieves $\lambda_2 \sim O(\log N / N)$ giving $t_{95\%} \sim O(N/\log N)$. Intelligent Coordination Ch.3

Discrete-Time Consensus β€” What Runs on Real Hardware

Discrete-Time Consensus (Update at Rate $h$) $$x_i[k+1] = x_i[k] + \varepsilon \sum_{j \in \mathcal{N}_i} a_{ij}(x_j[k] - x_i[k])$$ $$\mathbf{x}[k+1] = W\,\mathbf{x}[k], \qquad W = I - \varepsilon L$$

$\varepsilon$: step size β€” must satisfy $\varepsilon < 2/\lambda_N$ for stability (prevents oscillation). Optimal step: $\varepsilon^* = 2/(\lambda_2 + \lambda_N)$, achieving convergence rate $\rho^* = (\lambda_N - \lambda_2)/(\lambda_N + \lambda_2)$ (spectral gap β€” maximised when graph is balanced and well-connected). $W$ is a doubly stochastic matrix if the graph is undirected β€” this ensures the average is preserved: $\sum_i x_i[k] = \text{const}$ for all $k$.

Worked Example 9.2 β€” Consensus Speed: Ring vs. Random Geometric Graph (N=20)

Compare consensus convergence time for 20 drones in a ring topology vs. a random geometric graph (RGG) where each drone connects to all others within radius $r$.

Topology$\lambda_2$$\lambda_N$$t_{95\%} = 3/\lambda_2$ [s]Operational Implication
Ring ($C_{20}$)0.0983.90230.6 sToo slow for fast tactical coordination
RGG ($r=0.4$, avg degβ‰ˆ6)0.828.33.7 sAcceptable for mission-level coordination
Complete graph ($K_{20}$)20200.15 sOptimal but requires NΒ² links β€” impractical
Small-world (Watts-Strogatz)0.657.84.6 sGood balance of local + global connectivity

The RGG and small-world topologies are the practical operating points for military swarms: enough connectivity for fast consensus, without requiring every drone to communicate with every other drone (which would saturate available bandwidth). Swarm designers target $\lambda_2 \geq 0.5$ at minimum for tactical coordination.

9.4 Formation Control β€” Flying in Coordinated Geometry

Plain English First

Formation control extends consensus to three dimensions: instead of agreeing on a single value, agents agree on a geometric arrangement β€” a line, a V-shape, a sphere, a distributed aperture. Each UAV maintains a desired offset from either a virtual leader position or its neighbours. Military formations serve tactical purposes: a V-shape maximises radar coverage area, a tight cluster minimises radar cross section, a dispersed grid maximises ISR coverage. The challenge is maintaining formation when wind disturbs agents, when some agents fail, and when the formation must transition from one geometry to another without collisions during the transition.

Leader-Follower Formation

In leader-follower formation, one agent (the leader) follows a mission trajectory; all others maintain prescribed offsets from the leader or from each other in a chain: Intelligent Coordination Ch.4

Leader-Follower Control Law $$\dot{\mathbf{p}}_i = \mathbf{v}_{leader} + K_p(\mathbf{p}_{leader} + \mathbf{d}_i - \mathbf{p}_i) + K_d(\mathbf{v}_{leader} - \mathbf{v}_i)$$

$\mathbf{d}_i$: desired offset of agent $i$ from the leader in leader's body frame; $K_p, K_d$: position and velocity gain matrices. Vulnerability: If the leader fails, the entire formation loses its reference. Military implementation: designate a secondary leader that autonomously takes command if the primary exceeds a state-error threshold for more than $\tau_{fail}$ seconds.

Virtual Structure Formation β€” Rigid Body Reference

Instead of designating a real agent as leader, a virtual rigid body moves through space and each agent tracks its assigned point on this virtual structure: Intelligent Coordination Ch.4

Virtual Structure Control Law $$\mathbf{p}_i^{desired}(t) = \mathbf{p}_{VS}(t) + R_{VS}(t)\,\mathbf{d}_i^{body}$$ $$\mathbf{u}_i = K_p(\mathbf{p}_i^{desired} - \mathbf{p}_i) + K_d(\dot{\mathbf{p}}_i^{desired} - \dot{\mathbf{p}}_i)$$

$(\mathbf{p}_{VS}, R_{VS})$: position and orientation of the virtual structure (rigid body); $\mathbf{d}_i^{body}$: fixed offset of agent $i$ in the virtual body frame. Advantage: formation geometry is exactly preserved even during manoeuvres. Disadvantage: requires all agents to know the virtual structure state β€” needs broadcast.

Behaviour-Based Formation β€” Emergent from Local Rules

From Module 01, Reynolds' flocking rules (separation, alignment, cohesion) produce collective formation behaviour from purely local interactions. For precision military formations, these are augmented with formation-specific attraction terms: Intelligent Coordination Ch.4

Augmented Flocking with Formation Attraction $$\mathbf{u}_i = w_s\mathbf{f}_{sep} + w_a\mathbf{f}_{align} + w_c\mathbf{f}_{cohesion} + w_f\mathbf{f}_{formation} + w_o\mathbf{f}_{obstacle}$$ $$\mathbf{f}_{formation,i} = \sum_{j \in \mathcal{N}_i} \left[(\mathbf{p}_j - \mathbf{p}_i) - (\mathbf{d}_j - \mathbf{d}_i)\right]$$

$\mathbf{d}_i, \mathbf{d}_j$: desired positions of agents $i$ and $j$ in formation. The formation term drives each agent to maintain the correct relative offset from its neighbours β€” without knowing the absolute formation geometry. This is fully decentralised and resilient to leader failure.

9.5 Task Allocation β€” Who Does What?

Plain English First

A swarm of 50 UAVs must cover 20 target locations, 10 communication relay points, and 5 threat suppression tasks β€” with 50 agents and 35 tasks, how do you decide who does what? This is the task allocation problem. A good allocation maximises total mission value (cover the highest priority targets) while respecting each agent's constraints (range, payload, communication range). A bad allocation sends the wrong UAVs to the wrong targets, wastes fuel, and leaves high-priority targets uncovered. In a dynamic battlespace, allocation must be recomputed continuously as UAVs are attrited, targets change, and new tasks emerge.

The Assignment Problem β€” Hungarian Algorithm

For static, one-to-one assignment (one UAV per task, one task per UAV), the assignment problem is solved optimally by the Hungarian algorithm in $O(N^3)$: Bestaoui Sebbane Β§11.1

Binary Integer Programme β€” Optimal Assignment $$\max \sum_{i=1}^N \sum_{j=1}^M c_{ij} x_{ij}$$ $$\text{subject to:} \quad \sum_{j=1}^M x_{ij} \leq 1\; \forall i, \quad \sum_{i=1}^N x_{ij} \leq 1\; \forall j, \quad x_{ij} \in \{0,1\}$$

$c_{ij}$: reward for assigning UAV $i$ to task $j$ (function of travel time, payload match, priority). $x_{ij}$: binary assignment variable. This is NP-hard in general, but tractable as a linear assignment problem when the constraints are as above. Hungarian algorithm solves it in $O(N^3)$. For $N = 200$ drones: $8\times10^6$ operations β€” solvable in milliseconds on modern hardware. For dynamic re-allocation (new tasks, attrition), an incremental re-assignment approach re-solves only the affected subproblem.

Auction-Based Distributed Task Allocation

For large swarms where centralised assignment is impractical (communication bandwidth, single-point-of-failure), distributed auction algorithms allow each agent to bid on tasks and negotiate assignment through local communication: Intelligent Coordination Ch.5

Consensus-Based Bundle Algorithm (CBBA) β€” Distributed Auction $$y_{ij}(t) = \max_{k \in \mathcal{N}_i \cup \{i\}} c_{kj} \quad \text{(best known bid for task } j \text{)}$$ $$z_{ij}(t) = \arg\max_{k} c_{kj} \quad \text{(current winning bidder for task } j \text{)}$$

Each agent maintains a bundle of tasks it has won and communicates winning bids to neighbours. Through consensus (section 9.3), bid information spreads through the network. A task is assigned to the agent with the highest bid once that bid has propagated to all agents in the swarm (convergence requires at most graph diameter communication rounds). CBBA is asymptotically optimal and provably conflict-free β€” no two agents will be assigned the same task at convergence. Communication cost: $O(NM \cdot \text{diam}(\mathcal{G}))$ per allocation cycle.

9.6 Multi-Agent Reinforcement Learning (MARL)

Plain English First

Consensus algorithms and formation controllers work for well-defined coordination problems with known structure. But what if the swarm faces novel adversarial environments β€” an adaptive adversary that learns counter-tactics, a search problem with unknown target distributions, a communication-jammed environment where the network topology is unpredictable? Multi-Agent Reinforcement Learning (MARL) allows the swarm to learn collective behaviour through experience, without needing to hand-design every coordination rule. The agents jointly discover strategies that work β€” including strategies no human designer would have thought to specify.

The Decentralised POMDP (Dec-POMDP) Framework

MARL for swarms is formally grounded in the Dec-POMDP β€” an extension of the single-agent POMDP (Module 08) to $N$ agents: MDPI Autonomous Control Ch.8

Dec-POMDP β€” N-Agent Cooperative Task $$\mathcal{M}_{Dec} = (\mathcal{S},\, \{\mathcal{A}_i\}_{i=1}^N,\, \{\mathcal{O}_i\}_{i=1}^N,\, P,\, \{Z_i\}_{i=1}^N,\, R,\, \gamma)$$ $$\mathbf{a} = (a_1, \ldots, a_N) \in \mathcal{A}_1 \times \cdots \times \mathcal{A}_N \quad \text{(joint action)}$$ $$\text{Optimal joint policy:} \quad \boldsymbol{\pi}^* = \arg\max_{\boldsymbol{\pi}} \mathbb{E}\!\left[\sum_{t=0}^\infty \gamma^t R(s_t, \mathbf{a}_t)\right]$$

Each agent $i$ has its own local observation $o_i \in \mathcal{O}_i$ and action $a_i \in \mathcal{A}_i$. There is a single shared reward $R$ (cooperative task) β€” all agents work toward the same objective. The joint policy space is exponential in $N$: $|\boldsymbol{\Pi}| = |\Pi_i|^N$. For $N=10$ agents each with 10 actions: $10^{10}$ joint actions β€” centralised optimisation is intractable.

CTDE
Centralised Training, Decentralised Execution
During training: central critic sees all agents' observations and actions. During deployment: each agent acts on its local observation only. Key algorithms: MADDPG, QMIX, MAPPO. Dominant paradigm for military swarm RL β€” centralised training is feasible on ground servers; decentralised execution runs on each UAV's onboard compute.
Parameter Sharing
Shared Policy Weights
All agents share the same neural network weights. Distinguishes agents via an agent-ID input. Dramatically reduces training complexity ($N \times$ fewer parameters). Handles variable swarm size gracefully β€” just add/remove agents at execution time. Used in MAPPO, HAPPO for large-scale swarm coordination.
Communication
Learned Communication Protocols
Rather than hand-designing what agents communicate, let agents learn what messages to send. CommNet, DIAL, TarMAC allow agents to learn compact, task-relevant messages. Critical for bandwidth-constrained military swarms β€” reduces required communication bandwidth by 3–10Γ— vs. full state sharing.
Credit Assignment
Individual vs. Team Reward
The hardest MARL problem: when the team succeeds, which agents contributed? QMIX uses a monotone mixing network to decompose team reward into individual Q-values while preserving joint optimality. Poor credit assignment β†’ agents free-ride on teammates' effort β†’ coordination fails.
Theorem 9.2 β€” QMIX Monotone Mixing Property

QMIX factorises the joint action-value function $Q_{tot}(\mathbf{s}, \mathbf{a})$ into individual $Q_i(o_i, a_i)$ through a mixing network with a monotonicity constraint:

$$Q_{tot}(\mathbf{s}, \mathbf{a}) = f_{mix}(Q_1, Q_2, \ldots, Q_N \mid \mathbf{s})$$ $$\text{subject to:} \quad \frac{\partial Q_{tot}}{\partial Q_i} \geq 0 \quad \forall i$$

The monotonicity constraint ensures that the greedy joint action (argmax over all $a_i$ simultaneously) equals the decentralised greedy action (each agent maximises its own $Q_i$ independently). This is the IGM property (Individual-Global-Max) β€” necessary for CTDE to function correctly. Without IGM, agents trained centrally would take wrong actions when deployed independently, because their individually optimal actions might not be globally optimal. MDPI Autonomous Control Ch.8

9.7 Swarm Mesh Networking

Plain English First

A swarm's communication network is as important as its flight capability. Without reliable data exchange between agents, consensus fails, task allocation degrades, and the swarm fragments into isolated individuals. A mesh network β€” where every node can relay messages for every other node β€” is the only architecture robust enough for military swarm operations. There is no central router that can be destroyed; the network self-heals around lost nodes by discovering alternative routes. The challenge is doing this with minimal bandwidth, minimal latency, and in a spectrum-contested environment where the adversary actively tries to jam it.

MANET β€” Mobile Ad Hoc Network Protocols

Swarms use Mobile Ad Hoc Network (MANET) protocols adapted for highly dynamic, 3D mobile topology: Intelligent Coordination Ch.5

ProtocolTypeOverheadBest ForMilitary Limitation
OLSRProactive (maintains full routes)HighStable topologies, <50 nodesOverhead scales poorly; beacon traffic jams tactical bands
AODVReactive (route on demand)Low at rest, bursty on demandSparse, >50 nodesRoute discovery latency β€” too slow for time-critical coordination
BATMANProactive, distributedMediumUrban, dense swarmsNo guaranteed delivery; unreliable for safety-critical messages
Tactical TDMAScheduled time slotsLow, deterministicSmall, structured swarmsSynchronisation overhead; slot assignment complexity with attrition
Gossip / EpidemicProbabilistic floodingControllableLarge swarms, unreliable linksNo delivery guarantee; eventual consistency only

Link Budget for Swarm Communication

Within a swarm, communication links are short-range (typically 1–10 km between nodes) using licence-exempt bands (900 MHz, 2.4 GHz, 5.8 GHz) or military-specific waveforms (Link 16, TTNT): Bestaoui Sebbane Β§11.3

Swarm Intra-Link Budget (Short Range) $$P_r = P_t + G_t + G_r - 20\log_{10}\!\left(\frac{4\pi d f}{c}\right) - L_{body}$$

At 2.4 GHz, $d = 1$ km, $P_t = +20$ dBm (100 mW), omnidirectional antennas ($G_t = G_r = 0$ dBi), $L_{body} = 3$ dB body shielding: $P_r = 20 + 0 + 0 - 100.0 - 3 = -83$ dBm. Typical 802.11n sensitivity: $-90$ dBm β†’ link margin = 7 dB. At $d = 5$ km: $P_r = -97$ dBm β†’ margin negative β†’ link fails. This gives a swarm spacing constraint: nodes must stay within ~3 km of at least one neighbour for reliable communication. Formation geometry and consensus topology must respect this constraint.

9.8 Swarm Resilience β€” Functioning Under Attrition

Plain English First

Military swarms operate in environments where some nodes will be destroyed β€” either by adversary action or mechanical failure. A swarm that fragments and loses coordination when 20% of its nodes are lost has no military value. Resilience means the swarm degrades gracefully under attrition: losing nodes reduces capability proportionally, but never causes catastrophic failure of the coordination mechanism. This requires both algorithmic resilience (the consensus and allocation algorithms must work on a reduced graph) and topological resilience (the communication graph must stay connected even when nodes are removed).

$k$-Connectivity β€” Topological Resilience Guarantee

Graph $k$-Connectivity Definition $$\kappa(\mathcal{G}) = k \quad \Leftrightarrow \quad \text{graph remains connected after removing any } k-1 \text{ nodes}$$

A swarm with $\kappa(\mathcal{G}) = k$ can tolerate the simultaneous failure of $k-1$ nodes without losing connectivity. For a military swarm expecting 20% attrition in a 200-node swarm (40 nodes lost): design for $\kappa \geq 40$. Practical constraint: $\kappa(\mathcal{G}) \leq \delta(\mathcal{G})$ where $\delta$ is the minimum degree. To achieve $\kappa = 40$, every node must have at least 40 neighbours β€” a communication range requirement that grows the network overhead. Trade-off: higher $k$ gives more resilience but requires more links and bandwidth. Typical military swarm design target: $k = 2$–$4$ for ISR, $k = 1$ (connectivity only) for attritable strike swarms. Intelligent Coordination Ch.5

Leader Election Under Attrition

When a leader-follower formation loses its leader, a new one must be elected β€” fast enough that the formation doesn't fragment before re-coordination. Distributed leader election algorithms (based on consensus): Bestaoui Sebbane Β§11.4

Bully-Style Leader Election (Distributed) $$\text{Leader}_k = \arg\max_{i \in \mathcal{V}} \left\{w_i : w_i = \text{priority}(i) + \epsilon_i\right\}$$

$\text{priority}(i)$: static rank of agent $i$ (e.g., fuel remaining, distance to objective); $\epsilon_i \sim \text{Uniform}(0, \delta)$: tie-breaking noise. Each agent broadcasts its priority. After receiving all neighbours' priorities, the agent with the highest priority declares itself leader and broadcasts confirmation. Convergence time: $O(\text{diam}(\mathcal{G}))$ communication rounds. For a 200-node swarm with diameter 6 and 10 Hz communication: election completes in $6 \times 0.1 = 0.6$ s β€” acceptably fast for formation recovery.

Worked Example 9.3 β€” Swarm Resilience Analysis: 200-Node Strike Swarm

A 200-drone strike swarm uses a random geometric graph topology with average degree $\bar{d} = 8$. The adversary's C-UAS system can destroy 30 drones before the swarm reaches the target (15% attrition). Analyse whether the swarm maintains connectivity.

ParameterValueDerivation / Source
Initial nodes $N$200Swarm design
Average degree $\bar{d}$8From communication range and density
$\lambda_2$ initialβ‰ˆ 1.8RGG with $N=200$, $\bar{d}=8$
Attrition30 nodes (15%)C-UAS engagement rate
$\lambda_2$ after attritionβ‰ˆ 1.4Estimated from random node removal theory
$k$-connectivity$\kappa \approx 3$Min degree 8 β†’ $\kappa \leq 8$; typical RGG $\kappa \approx \bar{d}/3$

Connectivity after 30-node loss: With $\kappa = 3$, the swarm guarantees connectivity after losing any $\kappa - 1 = 2$ nodes simultaneously. However, 30 random node removals are unlikely to simultaneously disconnect the graph unless they are targeted (adversary removes strategically placed bridge nodes).

Consensus time after attrition: $t_{95\%} = 3/\lambda_2 = 3/1.4 \approx 2.1$ s β€” slightly degraded from initial 1.7 s but still tactically acceptable.

Worst case β€” targeted node removal: An adversary that identifies and preferentially targets the highest-degree nodes (network hubs) can fragment a 200-node RGG with as few as 10 hub removals. Counter-measure: topology obfuscation (don't broadcast degree information), LPI/LPD waveforms to prevent adversary mapping the swarm's communication graph. Intelligent Coordination Ch.5

9.9 Python: Swarm Simulation β€” Consensus, Formation, and Resilience

What This Code Covers Three simulations: (1) Graph Laplacian construction and eigenvalue analysis for swarm connectivity assessment. (2) Discrete-time consensus simulation on a random geometric graph β€” measures convergence time. (3) A 2D Reynolds flocking simulation with formation attraction term β€” 20 agents form a V-shape and maintain it under a disturbance. Run with: pip install numpy scipy
Python
# swarm_systems.py
# ─────────────────────────────────────────────────────────────────
# Part 1: Graph Laplacian + eigenvalue analysis
#         Intelligent Coordination Ch.3
# Part 2: Discrete-time consensus on random geometric graph
#         Theorem 9.1
# Part 3: Reynolds flocking with formation attraction (2D)
#         Intelligent Coordination Ch.4
# ─────────────────────────────────────────────────────────────────

import numpy as np
from   scipy.spatial import distance_matrix


# ════════════════════════════════════════════════════════════════
# PART 1 β€” Graph Laplacian and Swarm Connectivity
# ════════════════════════════════════════════════════════════════

def build_rgg(N: int, radius: float, seed: int = 42):
    """
    Build Random Geometric Graph:
    N nodes placed uniformly in [0,1]^2.
    Two nodes are connected if their distance < radius.
    Returns: positions (NΓ—2), adjacency matrix A (NΓ—N)
    """
    np.random.seed(seed)
    pos = np.random.rand(N, 2)
    D   = distance_matrix(pos, pos)
    A   = (D < radius).astype(float)
    np.fill_diagonal(A, 0)    # no self-loops
    return pos, A


def graph_laplacian(A: np.ndarray) -> np.ndarray:
    """Compute graph Laplacian L = D - A."""
    D = np.diag(A.sum(axis=1))
    return D - A


def connectivity_analysis(A: np.ndarray, name: str = ""):
    """
    Compute and report graph connectivity metrics.
    Intelligent Coordination Ch.3
    """
    L = graph_laplacian(A)
    eigvals = np.sort(np.linalg.eigvalsh(L))

    lambda2  = eigvals[1]         # algebraic connectivity (Fiedler value)
    lambdaN  = eigvals[-1]        # largest eigenvalue
    connected = lambda2 > 1e-8    # connected iff Ξ»β‚‚ > 0
    t95      = 3.0 / lambda2 if connected else float('inf')
    min_deg  = int(A.sum(axis=1).min())
    mean_deg = A.sum(axis=1).mean()

    print(f"\n  [{name}]")
    print(f"    N={A.shape[0]}  Connected: {connected}")
    print(f"    Ξ»β‚‚ (Fiedler):  {lambda2:.4f}  |  Ξ»_N: {lambdaN:.4f}")
    print(f"    Mean degree:   {mean_deg:.1f}   |  Min degree: {min_deg}")
    print(f"    t_95%:         {t95:.2f} s  (consensus time const)")
    return lambda2, t95


# ════════════════════════════════════════════════════════════════
# PART 2 β€” Discrete-Time Consensus Simulation
# ════════════════════════════════════════════════════════════════

def simulate_consensus(N: int = 20, radius: float = 0.4,
                        dt: float = 0.1, T: float = 20.0):
    """
    Simulate discrete-time consensus on RGG.
    Each agent has a scalar state x_i (e.g., desired heading).
    Convergence to average is monitored.
    Theorem 9.1 β€” convergence rate = Ξ»β‚‚
    """
    pos, A = build_rgg(N, radius)
    L      = graph_laplacian(A)

    # Optimal step size: Ξ΅* = 2/(Ξ»β‚‚ + Ξ»_N)
    eigvals = np.sort(np.linalg.eigvalsh(L))
    lambda2, lambdaN = eigvals[1], eigvals[-1]
    eps = 2 / (lambda2 + lambdaN) if lambda2 > 1e-8 else 0.1

    # Initial states: random headings in [0, 2Ο€]
    x   = np.random.rand(N) * 2 * np.pi
    x_avg = x.mean()          # target consensus value

    steps = int(T / dt)
    W     = np.eye(N) - eps * L   # consensus weight matrix
    disagreement = [np.std(x)]

    for _ in range(steps):
        x = W @ x
        disagreement.append(np.std(x))

    t_conv = next((k*dt for k, d in enumerate(disagreement)
                   if d < 0.05 * disagreement[0]), T)

    print(f"\n  [Consensus Simulation N={N}, r={radius}]")
    print(f"    Ξ΅* = {eps:.4f}  |  Ξ»β‚‚ = {lambda2:.4f}")
    print(f"    Initial std: {disagreement[0]:.3f} rad")
    print(f"    Final std:   {disagreement[-1]:.4f} rad  (converged to avg={x_avg:.3f})")
    print(f"    95% convergence time: {t_conv:.1f} s  (theory: {3/lambda2:.1f} s)")
    return disagreement


# ════════════════════════════════════════════════════════════════
# PART 3 β€” Reynolds Flocking with Formation Attraction
# ════════════════════════════════════════════════════════════════

def build_v_formation(N: int, spacing: float = 2.0) -> np.ndarray:
    """
    Create V-shaped formation offsets for N drones.
    Drones spread symmetrically: left and right arms of the V.
    """
    offsets = np.zeros((N, 2))
    offsets[0] = [0, 0]   # leader at tip
    for i in range(1, N):
        side  = 1 if i % 2 == 1 else -1   # alternate left/right
        rank  = (i + 1) // 2              # position along arm
        offsets[i] = [-rank * spacing, side * rank * spacing]
    return offsets


class SwarmFlock:
    """
    2D Reynolds flocking with formation attraction.
    Intelligent Coordination Ch.4
    """
    def __init__(self, N: int = 20, dt: float = 0.05):
        self.N  = N
        self.dt = dt
        np.random.seed(99)
        # Initialise in loose cluster with random offset from formation
        self.formation_offsets = build_v_formation(N, spacing=3.0)
        self.pos = self.formation_offsets + np.random.randn(N, 2) * 5.0
        self.vel = np.random.randn(N, 2) * 0.5

        # Behaviour weights (Intelligent Coordination Ch.4)
        self.w_sep   = 3.0   # separation (collision avoidance)
        self.w_align = 1.5   # alignment (velocity matching)
        self.w_coh   = 0.8   # cohesion (stay together)
        self.w_form  = 2.5   # formation attraction
        self.r_sep   = 2.5   # separation radius
        self.r_neigh = 12.0  # neighbourhood radius
        self.v_max   = 5.0   # max speed [m/s]

    def step(self, t: float):
        """One simulation timestep."""
        accel = np.zeros((self.N, 2))

        for i in range(self.N):
            sep_f = np.zeros(2)
            ali_f = np.zeros(2)
            coh_f = np.zeros(2)
            frm_f = np.zeros(2)
            n_sep = 0; n_nei = 0

            for j in range(self.N):
                if i == j: continue
                diff = self.pos[j] - self.pos[i]
                dist = np.linalg.norm(diff) + 1e-6

                # Separation β€” push away from close neighbours
                if dist < self.r_sep:
                    sep_f -= diff / dist**2
                    n_sep += 1

                # Alignment + cohesion + formation within neighbourhood
                if dist < self.r_neigh:
                    ali_f += self.vel[j]
                    coh_f += self.pos[j]
                    # Formation: drive to correct relative offset
                    desired_diff = self.formation_offsets[j] - self.formation_offsets[i]
                    frm_f += (diff - desired_diff)
                    n_nei += 1

            if n_sei := n_sep: sep_f /= n_sei      # normalise
            if n_nei:
                ali_f = ali_f / n_nei - self.vel[i]   # velocity error
                coh_f = coh_f / n_nei - self.pos[i]   # position to centroid
                frm_f = frm_f / n_nei

            accel[i] = (self.w_sep  * sep_f +
                        self.w_align* ali_f +
                        self.w_coh  * coh_f +
                        self.w_form * frm_f)

        # Integrate
        self.vel += accel * self.dt
        # Speed limit
        speeds = np.linalg.norm(self.vel, axis=1, keepdims=True)
        mask   = speeds > self.v_max
        self.vel[mask[:,0]] *= (self.v_max / speeds[mask[:,0]])
        self.pos += self.vel * self.dt

    def formation_error(self) -> float:
        """RMS deviation from desired formation geometry."""
        centroid = self.pos.mean(axis=0)
        form_centroid = self.formation_offsets.mean(axis=0)
        errors = []
        for i in range(self.N):
            desired = centroid + (self.formation_offsets[i] - form_centroid)
            errors.append(np.linalg.norm(self.pos[i] - desired))
        return float(np.sqrt(np.mean(np.array(errors)**2)))


def simulate_swarm_flock(N: int = 20, T: float = 30.0, dt: float = 0.05):
    """Simulate flock formation convergence. Intelligent Coordination Ch.4"""
    swarm = SwarmFlock(N, dt)
    steps = int(T / dt)

    print(f"\n{'='*54}")
    print(f"  SWARM FORMATION SIMULATION (N={N} drones)")
    print(f"  Intelligent Coordination Ch.4")
    print(f"{'='*54}")
    print(f"\n  {'Time':>5} | {'Formation Error':>15} | Notes")
    print(f"  {'-'*45}")

    prev_err = swarm.formation_error()
    print(f"  {0:5.1f}s | {prev_err:15.2f} m | Initial (random positions)")

    for k in range(steps):
        t = (k+1) * dt

        # Inject disturbance at t=15s to test resilience
        if abs(t - 15.0) < dt:
            swarm.pos += np.random.randn(N, 2) * 3.0   # wind gust disturbance
            print(f"  {t:5.1f}s | {'--- DISTURBANCE ---':>15}   | Wind gust injected")

        swarm.step(t)

        if k % 100 == 99:   # print every 5 seconds
            err = swarm.formation_error()
            note = "converged" if err < 1.5 else "converging"
            print(f"  {t:5.1f}s | {err:15.2f} m | {note}")

    final_err = swarm.formation_error()
    print(f"\n  Final formation error: {final_err:.2f} m")
    print(f"  Improvement: {swarm.formation_error()/prev_err*100:.0f}% of initial error remains")
    print(f"  β†’ Formation recovered from wind disturbance at t=15s")
    print(f"{'='*54}\n")


if __name__ == "__main__":
    np.random.seed(42)
    print("\n" + "="*54)
    print("  GRAPH LAPLACIAN ANALYSIS β€” Intelligent Coordination Ch.3")
    print("="*54)

    # Compare topologies
    _, A_ring  = build_rgg(20, radius=0.25)  # approximately ring-like (sparse)
    _, A_rgg   = build_rgg(20, radius=0.40)  # moderate density RGG
    _, A_dense = build_rgg(20, radius=0.65)  # dense RGG

    connectivity_analysis(A_ring,  "Sparse graph (r=0.25)")
    connectivity_analysis(A_rgg,   "Moderate RGG (r=0.40)")
    connectivity_analysis(A_dense, "Dense RGG (r=0.65)")

    print("\n" + "="*54)
    print("  CONSENSUS SIMULATION")
    print("="*54)
    simulate_consensus(N=20, radius=0.40, dt=0.1, T=30.0)

    simulate_swarm_flock(N=20, T=30.0)
Expected Output Sparse graph: Ξ»β‚‚ β‰ˆ 0.1–0.4, t₉₅ β‰ˆ 7–30 s (slow consensus) Β· Moderate RGG: Ξ»β‚‚ β‰ˆ 0.8–1.5, t₉₅ β‰ˆ 2–4 s (tactical) Β· Dense RGG: Ξ»β‚‚ β‰ˆ 3–6, t₉₅ β‰ˆ 0.5–1 s (fast) Β· Consensus: heading std drops from ~1.8 rad to ~0.001 rad by convergence time Β· Formation: error drops from ~12 m to ~1.5 m within 10 s; recovers after t=15 s disturbance
  1. The Fiedler value $\lambda_2$ of the graph Laplacian governs consensus convergence rate. From the eigendecomposition of $L$, derive why $\lambda_2$ specifically (and not $\lambda_1$ or $\lambda_3$) determines the slowest convergence mode. For a swarm designer who must improve $\lambda_2$ from 0.5 to 2.0 (4Γ— faster consensus) without changing total number of nodes: what graph-theoretic property of an edge tells you how much adding it will increase $\lambda_2$, and where in the network should new edges be added for maximum impact?
  2. The Consensus-Based Bundle Algorithm (CBBA) requires at most $\text{diam}(\mathcal{G})$ communication rounds to converge. For a 200-node swarm with graph diameter 6 and communication rate 10 Hz, calculate the allocation convergence time. Now suppose during this convergence window, 3 new high-priority targets are detected. Describe the race condition this creates in the distributed auction, and propose two architectural solutions used in operational swarm systems.
  3. QMIX enforces the IGM property through a monotone mixing network. Explain why IGM is necessary for the CTDE paradigm to produce correct decentralised policies β€” what goes wrong if IGM is violated? Show with a concrete two-agent example where $Q_1(a_1) > Q_1(a_1')$ and $Q_2(a_2) > Q_2(a_2')$ but the joint policy $(a_1', a_2')$ achieves higher $Q_{tot}$ than $(a_1, a_2)$. Why can QMIX's state-dependent mixing weights represent this case while a fixed additive value decomposition (VDN) cannot?
β—‚ Module 08: Autonomy Module 10: Systems Engineering β–Έ