Consider a swarm of \( N \) identical robots, each with state \( x_i(t) \in \mathbb{R}^d \) at time \( t \ge 0 \). A generic local-update model for the swarm is

\[ x_i(t+1) = f\Big( x_i(t), \{x_j(t)\}_{j \in \mathcal{N}_i(t)}, \eta_i(t), \xi_i(t) \Big), \quad i = 1,\dots,N, \]

where \( \mathcal{N}_i(t) \) is the set of neighbors of robot \( i \) at time \( t \), \( \eta_i(t) \) models sensing and actuation noise, and \( \xi_i(t) \) encodes random topology or environment changes.

Let a global performance functional at horizon \( T \) be

\[ J_N = \mathbb{E}\Big[ \Phi\big(x_1(T),\dots,x_N(T)\big) \Big], \]

where \( \Phi \) encodes task-specific objectives such as coverage uniformity, aggregation time, or transport throughput. We define:

• Robustness: insensitivity of \( J_N \) to perturbations in disturbances, failures, or model parameters.
• Scalability: behavior of \( J_N \) and resource usage (time, communication, memory) as \( N \) varies, typically with fixed robot density.

A simple sensitivity measure with respect to a disturbance parameter \( \delta \in \mathbb{R}^m \) is

\[ S_N(\delta) = \big|J_N(\delta) - J_N(0)\big|. \]

A swarm is called robust in the large-scale limit if there exists a constant \( C \), independent of \( N \), such that for small enough perturbations

\[ S_N(\delta) \le C \lVert \delta \rVert \quad \text{for all sufficiently large } N. \]

Scalability can be captured by the asymptotic growth rate of completion time \( T(N) \) or steady-state error \( E(N) \). For example, a coverage algorithm with \( T(N) = \mathcal{O}(\log N) \) is usually considered scalable, while \( T(N) = \mathcal{O}(N^2) \) is not.

flowchart TD
  D["Disturbances: noise, failures, topology changes"] --> L["Local update rule f"]
  L --> E["Emergent swarm pattern"]
  E --> M["Global metric J_N"]
  M --> R["Robustness: sensitivity w.r.t. disturbances"]
  M --> S["Scalability: growth vs. swarm size N"]
        

We formalize canonical uncertainty sources as random variables. Let \( F_i \in \{0,1\} \) denote a failure indicator for robot \( i \), where \( F_i = 1 \) means the robot is failed (e.g., stopped or malicious). A simple independent failure model is

\[ F_i \sim \operatorname{Bernoulli}(p_f), \quad i = 1,\dots,N, \]

where \( p_f \) is the marginal failure probability. The number of alive robots is

\[ N_{\text{alive}} = \sum_{i=1}^N (1 - F_i). \]

Sensing and actuation noise are modeled as

\[ z_i(t) = h\big(x_i(t)\big) + v_i(t),\quad v_i(t) \sim \mathcal{N}(0,\sigma_v^2) \]

and

\[ u_i(t) = u_i^{\text{ideal}}(t) + w_i(t),\quad w_i(t) \sim \mathcal{N}(0,\sigma_w^2), \]

where \( h \) is the measurement function and \( u_i^{\text{ideal}}(t) \) is the nominal local control policy.

The communication topology can be represented by a random adjacency matrix \( A(t) = \big(a_{ij}(t)\big) \), with \( a_{ij}(t) \in \{0,1\} \) and

\[ a_{ij}(t) = \begin{cases} 1, & \text{if robot } j \text{ is a neighbor of } i \text{ at time } t, \\ 0, & \text{otherwise}. \end{cases} \]

Link failures or packet drops are introduced through random variables \( L_{ij}(t) \in \{0,1\} \) such that the effective adjacency is \( a_{ij}(t)L_{ij}(t) \). Independence and mixing assumptions on \( L_{ij}(t) \) play a central role in robustness proofs.

A basic robustness metric is the expected fraction of robots that remain functional:

\[ \rho_{\text{alive}}(N,p_f) = \frac{1}{N} \mathbb{E}\left[ \sum_{i=1}^N (1 - F_i) \right] = 1 - p_f. \]

For a coverage task in an environment \( \Omega \subset \mathbb{R}^2 \), let \( \rho(x,T) \) denote the robot spatial density at time \( T \), and \( \rho^{\star}(x) \) the desired density. The coverage error is

\[ E_{\text{cov}}(T) = \int_{\Omega} \big| \rho(x,T) - \rho^{\star}(x) \big|\,\mathrm{d}x. \]

Robustness to failures is characterized by the sensitivity of \( E_{\text{cov}}(T) \) to \( p_f \), e.g.

\[ \frac{\partial E_{\text{cov}}(T)}{\partial p_f} \quad \text{or} \quad \sup_{p_f \in [0,\bar{p}]} \frac{ E_{\text{cov}}(T;p_f) - E_{\text{cov}}(T;0) }{ p_f }. \]

Scalability can be expressed via asymptotic exponents. Suppose completion time \( T(N) \) of a task obeys \( T(N) \approx c N^{\alpha} \) as \( N \to \infty \). Then:

• \( \alpha < 0 \): super-scalable (rare).
• \( \alpha = 0 \): time is essentially constant.
• \( 0 < \alpha \le 1 \): acceptable scaling.
• \( \alpha > 1 \): poor scalability.

Communication scalability is captured by the average degree of the interaction graph. If each robot has degree \( \deg_i(N) \), we define

\[ d_{\text{avg}}(N) = \frac{1}{N} \sum_{i=1}^N \deg_i(N). \]

A communication pattern is often considered scalable if \( d_{\text{avg}}(N) = \mathcal{O}(1) \) or \( d_{\text{avg}}(N) = \mathcal{O}(\log N) \), while dense all-to-all schemes with \( d_{\text{avg}}(N) = \mathcal{O}(N) \) are not.

A key source of robustness in large swarms is the averaging effect of many agents. Consider a binary task state \( Y_i(t) \in \{0,1\} \), where \( Y_i(t)=1 \) means robot \( i \) has completed its local objective at time \( t \). Define the empirical fraction of successful robots:

\[ X_N(t) = \frac{1}{N} \sum_{i=1}^N Y_i(t). \]

Suppose that, conditionally on the swarm interaction process, \( Y_i(t) \) are identically distributed with success probability \( p(t) \) and uncorrelated enough so that a law of large numbers holds. Then

\[ X_N(t) \xrightarrow[N \to \infty]{\text{prob.}} p(t). \]

A finite-sample concentration bound (e.g. Chebyshev) yields

\[ \mathbb{P}\Big( \big|X_N(t) - p(t)\big| \ge \varepsilon \Big) \le \frac{p(t)\big(1-p(t)\big)}{N\varepsilon^2}, \quad \varepsilon > 0, \]

which shows that fluctuations decay as \( \mathcal{O}(1/N) \) in variance. Thus, aggregate performance becomes sharply concentrated for large swarms.

Incorporating failures, let \( F_i \) be independent of \( Y_i(t) \), with failure probability \( p_f \). The fraction of robots that are both alive and successful is

\[ Z_N(t) = \frac{1}{N} \sum_{i=1}^N \big(1 - F_i\big) Y_i(t). \]

Then

\[ \mathbb{E}[Z_N(t)] = \big(1-p_f\big)p(t), \]

and a similar concentration bound holds. Hence, as \( N \) grows, the relative effect of independent failures on aggregate performance becomes predictable and small in variance.

Many swarm algorithms can be approximated by mean-field ordinary differential equations (ODEs). For example, a simple two-state Markov process (e.g., exploring vs. committed to a site) leads to

\[ \dot{p}(t) = \alpha \big(1-p(t)\big) - \beta p(t), \]

with solution

\[ p(t) = p_{\infty} + \big(p(0) - p_{\infty}\big) e^{-(\alpha + \beta)t}, \quad p_{\infty} = \frac{\alpha}{\alpha + \beta}. \]

The rate \( \alpha + \beta \) and equilibrium \( p_{\infty} \) can be related to local interaction rules and thus tuned for robust convergence.

Many swarm behaviors (aggregation, alignment, formation) can be modeled as consensus processes. Let \( x_i(k) \in \mathbb{R} \) denote a scalar state (e.g., heading angle) at discrete time \( k \). A standard consensus update is

\[ x_i(k+1) = x_i(k) + \varepsilon \sum_{j \in \mathcal{N}_i(k)} a_{ij}(k) \big(x_j(k) - x_i(k)\big), \]

with step-size \( \varepsilon > 0 \). In vector form,

\[ x(k+1) = \big(I - \varepsilon L(k)\big)x(k), \]

where \( L(k) \) is the graph Laplacian of the interaction graph at time \( k \).

For a static, connected, undirected graph with Laplacian \( L \) having eigenvalues \( 0 = \lambda_1 < \lambda_2 \le \dots \le \lambda_N \), the second-smallest eigenvalue \( \lambda_2 \) is the algebraic connectivity. Under mild conditions on \( \varepsilon \), the consensus error satisfies

\[ \big\| x(k) - \bar{x}\mathbf{1} \big\|_2 \le C \big(1 - \varepsilon \lambda_2\big)^k \big\| x(0) - \bar{x}\mathbf{1} \big\|_2, \]

where \( \bar{x} \) is the average of the initial states. Thus, larger \( \lambda_2 \) implies faster convergence and better robustness to perturbations.

Node failures remove rows and columns of \( L \), while link failures perturb its off-diagonal entries. A k-vertex-connected graph, which remains connected after removal of any set of up to \( k-1 \) nodes, guarantees that consensus can still be achieved if fewer than \( k \) robots fail. Designing local rules that preserve high algebraic connectivity even under random failures is a core robustness challenge in swarm robotics.

Assume robots are uniformly distributed in a compact region \( \Omega \subset \mathbb{R}^2 \) of area \( A \) and that two robots are neighbors if their distance is at most a communication radius \( r \). This defines a random geometric graph \( G(N,r) \).

For fixed area \( A = 1 \), classical results show that connectivity occurs with high probability when the radius satisfies

\[ r_c(N) \approx \sqrt{ \frac{\log N}{\pi N} }. \]

At this scaling, the expected degree grows like \( d_{\text{avg}}(N) \approx \log N \), which is near-minimal for connectivity. Thus, consensus-based swarms on \( G(N,r_c(N)) \) are both connected (with high probability) and have communication cost that grows only logarithmically with swarm size.

If the physical density is kept constant, then \( A \propto N \), and a fixed communication range \( r \) yields a constant expected degree \( d_{\text{avg}}(N) = \mathcal{O}(1) \). In this regime, the swarm can scale to arbitrarily large \( N \) without increasing per-robot communication load, at the price of larger absolute diameters and longer convergence times.

flowchart TD
  P["Choose local rule (e.g., consensus, coverage)"] --> S["Fix robot density and comm radius r"]
  S --> L["Simulate for increasing N"]
  L --> M1["Measure: completion time T(N)"]
  L --> M2["Measure: error E(N), average degree"]
  M1 --> C["Fit scaling exponents (e.g., T(N) ~ N^alpha)"]
  M2 --> C
        

We now implement a simple 1D consensus swarm with independent robot failures and link drops. The goal is to estimate convergence time and consensus error as functions of \( N \), \( p_f \), and \( p_{\text{drop}} \). We use numpy for vectorized operations. In a full robotics stack this logic would typically be wrapped in ROS topics or a gym-like simulation environment.

import numpy as np

rng = np.random.default_rng(seed=0)

def build_ring_adjacency(N):
    A = np.zeros((N, N), dtype=float)
    for i in range(N):
        A[i, (i - 1) % N] = 1.0
        A[i, (i + 1) % N] = 1.0
    return A

def consensus_step(x, A, alive, eps=0.2, noise_std=0.0, p_drop=0.0):
    N = x.shape[0]
    # Effective adjacency with symmetric link drops
    mask = rng.random((N, N)) >= p_drop
    A_eff = A * mask * mask.T
    x_new = np.copy(x)
    for i in range(N):
        if not alive[i]:
            continue
        # Local noisy consensus update
        neighbors = np.where(A_eff[i] > 0.0)[0]
        if neighbors.size == 0:
            continue
        diff = x[neighbors] - x[i]
        x_new[i] = x[i] + eps * diff.mean() + noise_std * rng.normal()
    return x_new

def simulate_swarm(N=50, steps=200, p_fail=0.1, p_drop=0.05,
                   eps=0.2, noise_std=0.01):
    # Initial headings
    x = rng.uniform(low=-1.0, high=1.0, size=N)
    alive = np.ones(N, dtype=bool)

    A = build_ring_adjacency(N)

    # Draw failures once at the beginning
    failures = rng.random(N) < p_fail
    alive[failures] = False

    history = [x.copy()]
    for k in range(steps):
        x = consensus_step(x, A, alive, eps=eps,
                           noise_std=noise_std, p_drop=p_drop)
        history.append(x.copy())

    history = np.array(history)  # shape: (steps+1, N)
    # Consensus error vs time (alive robots only)
    alive_idx = np.where(alive)[0]
    if alive_idx.size == 0:
        return history, None

    mean_traj = history[:, alive_idx].mean(axis=1)
    err_traj = np.linalg.norm(
        history[:, alive_idx] - mean_traj[:, None],
        ord=2, axis=1
    ) / np.sqrt(alive_idx.size)

    return history, err_traj

if __name__ == "__main__":
    for N in [20, 50, 100]:
        _, err = simulate_swarm(N=N, p_fail=0.2, p_drop=0.1)
        if err is not None:
            print(f"N={N}, final error={err[-1]:.4f}")
      

By plotting err_traj for various \( N \) and noise levels, students can empirically estimate convergence rates and verify robustness and scalability properties predicted by the theory.

In C++, a similar experiment can be implemented efficiently. Robotics software typically uses Eigen for linear algebra and runs inside ROS nodes; here we show a minimal STL-based implementation focusing on the core logic.

#include <iostream>
#include <vector>
#include <random>

struct SwarmConfig {
    int N;
    int steps;
    double p_fail;
    double p_drop;
    double eps;
    double noise_std;
};

int main() {
    SwarmConfig cfg{50, 200, 0.2, 0.1, 0.2, 0.01};

    std::mt19937 gen(0);
    std::uniform_real_distribution<double> uni(-1.0, 1.0);
    std::uniform_real_distribution<double> uni01(0.0, 1.0);
    std::normal_distribution<double> gauss(0.0, cfg.noise_std);

    std::vector<double> x(cfg.N);
    std::vector<bool> alive(cfg.N, true);

    for (int i = 0; i < cfg.N; ++i) {
        x[i] = uni(gen);
        if (uni01(gen) < cfg.p_fail) {
            alive[i] = false;
        }
    }

    for (int k = 0; k < cfg.steps; ++k) {
        std::vector<double> x_new = x;
        for (int i = 0; i < cfg.N; ++i) {
            if (!alive[i]) continue;

            int left = (i - 1 + cfg.N) % cfg.N;
            int right = (i + 1) % cfg.N;

            bool link_left_ok = (uni01(gen) >= cfg.p_drop);
            bool link_right_ok = (uni01(gen) >= cfg.p_drop);

            double sum_diff = 0.0;
            int count = 0;

            if (link_left_ok && alive[left]) {
                sum_diff += (x[left] - x[i]);
                ++count;
            }
            if (link_right_ok && alive[right]) {
                sum_diff += (x[right] - x[i]);
                ++count;
            }

            if (count > 0) {
                double avg_diff = sum_diff / static_cast<double>(count);
                x_new[i] = x[i] + cfg.eps * avg_diff + gauss(gen);
            }
        }
        x.swap(x_new);
    }

    double sum = 0.0;
    int count_alive = 0;
    for (int i = 0; i < cfg.N; ++i) {
        if (alive[i]) {
            sum += x[i];
            ++count_alive;
        }
    }
    double mean = (count_alive > 0) ? sum / count_alive : 0.0;
    double err2 = 0.0;
    for (int i = 0; i < cfg.N; ++i) {
        if (alive[i]) {
            double d = x[i] - mean;
            err2 += d * d;
        }
    }
    double rmse = (count_alive > 0)
        ? std::sqrt(err2 / static_cast<double>(count_alive))
        : 0.0;

    std::cout << "Final RMSE among alive robots: " << rmse << std::endl;
    return 0;
}
      

This code can be embedded in a ROS2 node that publishes headings and subscribes to neighbor states; robustness and scalability can then be studied on real robotic platforms or high-fidelity simulators.

Java is often used for educational simulators and GUI-based swarm visualizations. The following code fragment implements a discrete-time consensus with failures on a ring topology.

import java.util.Random;

public class SwarmConsensus {
    private final int N;
    private final int steps;
    private final double pFail;
    private final double pDrop;
    private final double eps;
    private final double noiseStd;
    private final double[] x;
    private final boolean[] alive;
    private final Random rng;

    public SwarmConsensus(int N, int steps,
                          double pFail, double pDrop,
                          double eps, double noiseStd) {
        this.N = N;
        this.steps = steps;
        this.pFail = pFail;
        this.pDrop = pDrop;
        this.eps = eps;
        this.noiseStd = noiseStd;
        this.x = new double[N];
        this.alive = new boolean[N];
        this.rng = new Random(0L);

        for (int i = 0; i < N; i++) {
            x[i] = -1.0 + 2.0 * rng.nextDouble();
            alive[i] = (rng.nextDouble() >= pFail);
        }
    }

    private double gauss() {
        // Box-Muller
        double u1 = rng.nextDouble();
        double u2 = rng.nextDouble();
        return Math.sqrt(-2.0 * Math.log(u1))
             * Math.cos(2.0 * Math.PI * u2) * noiseStd;
    }

    public void run() {
        for (int k = 0; k < steps; k++) {
            double[] xNew = x.clone();
            for (int i = 0; i < N; i++) {
                if (!alive[i]) continue;

                int left = (i - 1 + N) % N;
                int right = (i + 1) % N;

                double sumDiff = 0.0;
                int count = 0;

                if (rng.nextDouble() >= pDrop && alive[left]) {
                    sumDiff += x[left] - x[i];
                    count++;
                }
                if (rng.nextDouble() >= pDrop && alive[right]) {
                    sumDiff += x[right] - x[i];
                    count++;
                }

                if (count > 0) {
                    double avgDiff = sumDiff / (double) count;
                    xNew[i] = x[i] + eps * avgDiff + gauss();
                }
            }
            System.arraycopy(xNew, 0, x, 0, N);
        }
    }

    public double computeRMSE() {
        double sum = 0.0;
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (alive[i]) {
                sum += x[i];
                count++;
            }
        }
        if (count == 0) return 0.0;
        double mean = sum / (double) count;

        double err2 = 0.0;
        for (int i = 0; i < N; i++) {
            if (alive[i]) {
                double d = x[i] - mean;
                err2 += d * d;
            }
        }
        return Math.sqrt(err2 / (double) count);
    }

    public static void main(String[] args) {
        SwarmConsensus sim = new SwarmConsensus(100, 300, 0.2, 0.1, 0.2, 0.01);
        sim.run();
        System.out.println("RMSE = " + sim.computeRMSE());
    }
}
      

Graphical front-ends can display the evolution of headings or positions, providing intuition for how robustness degrades with increasing failure and drop probabilities.

In MATLAB, we can prototype the same discrete-time consensus process. A Simulink model can then be constructed where each robot is a subsystem implementing the local update law and noise injection.

function [rmse, x_hist] = swarm_consensus_matlab(N, steps, p_fail, p_drop, eps, noise_std)
    if nargin < 1, N = 50; end
    if nargin < 2, steps = 200; end
    if nargin < 3, p_fail = 0.2; end
    if nargin < 4, p_drop = 0.1; end
    if nargin < 5, eps = 0.2; end
    if nargin < 6, noise_std = 0.01; end

    rng(0);
    x = -1 + 2 * rand(N, 1);
    alive = rand(N, 1) >= p_fail;

    x_hist = zeros(N, steps + 1);
    x_hist(:, 1) = x;

    for k = 1:steps
        x_new = x;
        for i = 1:N
            if ~alive(i), continue; end
            left = mod(i - 2, N) + 1;
            right = mod(i, N) + 1;

            sumDiff = 0;
            count = 0;

            if rand() >= p_drop && alive(left)
                sumDiff = sumDiff + (x(left) - x(i));
                count = count + 1;
            end
            if rand() >= p_drop && alive(right)
                sumDiff = sumDiff + (x(right) - x(i));
                count = count + 1;
            end

            if count > 0
                avgDiff = sumDiff / count;
                x_new(i) = x(i) + eps * avgDiff + noise_std * randn();
            end
        end
        x = x_new;
        x_hist(:, k + 1) = x;
    end

    idx_alive = find(alive);
    if isempty(idx_alive)
        rmse = 0;
        return;
    end
    mean_val = mean(x(idx_alive));
    rmse = sqrt(mean((x(idx_alive) - mean_val).^2));
end
      

In Simulink, each agent can be modeled as a discrete-time subsystem with:

• A unit-delay block holding x_i(k).
• Sum blocks computing x_j(k) - x_i(k) for neighbors; link drops modeled by random switch blocks.
• A gain block implementing the step-size \( \varepsilon \) and an additive noise block for \( w_i(k) \).

The swarm is then obtained by replicating this subsystem \( N \) times and wiring according to the desired topology.

Wolfram Mathematica is well suited to symbolic and numeric analysis of swarm robustness. Below we build a ring graph, simulate consensus, and compute the algebraic connectivity lambda2.

(* Build ring graph *)
ClearAll[Nrobots, ring, A, L, lambda2]
Nrobots = 30;
ring = CycleGraph[Nrobots];

(* Adjacency and Laplacian *)
A = AdjacencyMatrix[ring] // Normal;
L = GraphLaplacian[ring] // Normal;

(* Second-smallest eigenvalue (algebraic connectivity) *)
lambda2 = Sort[Eigenvalues[L]][[2]]

(* Discrete-time consensus without failures *)
eps = 0.2;
steps = 100;
x0 = RandomReal[{-1, 1}, Nrobots];

consensusStep[x_] := Module[{xNew = x},
  Do[
    (* Neighbors of node i *)
    neighbors = VertexList[NeighborhoodGraph[ring, i, 1]][[2 ;;]];
    diff = Mean[x[[neighbors]]] - x[[i]];
    xNew[[i]] = x[[i]] + eps * diff,
    {i, 1, Nrobots}
  ];
  xNew
];

xHist = NestList[consensusStep, x0, steps];

(* Consensus error over time *)
meanTraj = Mean /@ xHist;
errTraj = Table[
  Sqrt[Mean[(xHist[[k]] - meanTraj[[k]])^2]],
  {k, 1, Length[xHist]}
];

ListLinePlot[errTraj,
  AxesLabel -> {"k", "RMSE"},
  PlotRange -> All
]
      

The value of lambda2 can be compared across different topologies (e.g., adding random long-range links) to study how robust convergence improves as connectivity increases.

Problem 1 (Mean-Field Robustness to Independent Failures). Consider \( N \) robots, each with a binary task success variable \( Y_i \in \{0,1\} \) and independent failures \( F_i \sim \operatorname{Bernoulli}(p_f) \). Assume \( \mathbb{P}(Y_i = 1) = p_s \), independent of \( F_i \). Define \( Z_N = \frac{1}{N}\sum_{i=1}^N (1-F_i)Y_i \), the fraction of robots that are alive and successful. Show that \( Z_N \xrightarrow[N \to \infty]{\text{prob.}} (1-p_f)p_s \).

Solution:

The random variables \( (1-F_i)Y_i \) are i.i.d. with

\[ \mathbb{E}\big[(1-F_i)Y_i\big] = \mathbb{E}[1-F_i]\, \mathbb{E}[Y_i] = (1-p_f)p_s. \]

Since \( 0 \le (1-F_i)Y_i \le 1 \), they have finite variance. The weak law of large numbers implies

\[ Z_N = \frac{1}{N} \sum_{i=1}^N (1-F_i)Y_i \xrightarrow[N \to \infty]{\text{prob.}} (1-p_f)p_s. \]

Hence, the fraction of alive and successful robots converges to a deterministic value for large swarms, illustrating robustness to independent failures.

Problem 2 (Chebyshev Bound for Swarm Performance). Using the same setting as Problem 1, derive a bound on \( \mathbb{P}(|Z_N - (1-p_f)p_s| \ge \varepsilon) \) in terms of \( N \), \( p_f \), \( p_s \), and \( \varepsilon > 0 \).

Solution:

Let \( W_i = (1-F_i)Y_i \), which is Bernoulli with parameter \( q = (1-p_f)p_s \). Then \( Z_N = \frac{1}{N}\sum_{i=1}^N W_i \) and

\[ \operatorname{Var}(Z_N) = \frac{1}{N^2} \sum_{i=1}^N \operatorname{Var}(W_i) = \frac{q(1-q)}{N}. \]

Chebyshev's inequality gives

\[ \mathbb{P}\Big( \big|Z_N - q\big| \ge \varepsilon \Big) \le \frac{\operatorname{Var}(Z_N)}{\varepsilon^2} = \frac{q(1-q)}{N\varepsilon^2}. \]

Thus deviations decay at least on the order of \( 1/N \).

Problem 3 (Algebraic Connectivity and Convergence Rate). Consider continuous-time consensus \( \dot{x}(t) = -Lx(t) \) with connected, undirected Laplacian \( L \). Show that \( \lVert x(t) - \bar{x}\mathbf{1} \rVert_2 \le e^{-\lambda_2 t} \lVert x(0) - \bar{x}\mathbf{1} \rVert_2 \), where \( \lambda_2 \) is the second-smallest eigenvalue of \( L \).

Solution:

Diagonalize \( L = Q\Lambda Q^{\top} \) with \( \Lambda = \operatorname{diag}(\lambda_1,\dots,\lambda_N) \). In the coordinates \( y = Q^{\top}x \) the dynamics are \( \dot{y}_i(t) = -\lambda_i y_i(t) \) and thus \( y_i(t) = e^{-\lambda_i t} y_i(0) \). The component along \( \mathbf{1} \) corresponds to \( \lambda_1 = 0 \) and remains constant; the remaining coordinates decay at least as fast as \( e^{-\lambda_2 t} \). Therefore,

\[ \big\| x(t) - \bar{x}\mathbf{1} \big\|_2 = \Big( \sum_{i=2}^N e^{-2\lambda_i t} y_i(0)^2 \Big)^{1/2} \le e^{-\lambda_2 t} \Big( \sum_{i=2}^N y_i(0)^2 \Big)^{1/2} = e^{-\lambda_2 t} \big\| x(0) - \bar{x}\mathbf{1} \big\|_2. \]

Thus convergence speed is controlled by algebraic connectivity, which is a natural robustness metric for swarm communication graphs.

Problem 4 (Scalability of Communication Degree). Suppose robots are uniformly distributed in a region of area \( A = 1 \), and each communicates with all robots within radius \( r(N) = \sqrt{\frac{\log N}{\pi N}} \). Show that the expected degree grows like \( \mathcal{O}(\log N) \).

Solution:

The expected number of neighbors is the expected number of points in a disc of area \( \pi r(N)^2 \), i.e.,

\[ d_{\text{avg}}(N) \approx N \pi r(N)^2 = N \pi \frac{\log N}{\pi N} = \log N. \]

Thus communication load per robot grows only logarithmically with swarm size, which is typically considered scalable.

Problem 5 (Task Completion Time Scaling). Assume a coverage algorithm operates on a region of area \( A \propto N \) with constant robot density and that information propagates diffusively, so that the characteristic convergence time scales as the square of the graph diameter. Argue that completion time scales as \( T(N) = \mathcal{O}(N) \) for a two-dimensional lattice-like topology.

Solution:

For a 2D lattice-like topology with \( N \) nodes at constant density, the side length scales as \( \sqrt{N} \), and the graph diameter scales like \( \mathcal{O}(\sqrt{N}) \). If information propagation is diffusive, convergence time scales roughly as the square of this diameter, i.e. \( \mathcal{O}((\sqrt{N})^2) = \mathcal{O}(N) \). Hence the coverage algorithm has linear time scaling with swarm size.

In this lesson we formalized robustness and scalability in swarm robotics using probabilistic, mean-field, and graph-theoretic tools. We showed how independent failures and noise are averaged out in large swarms, leading to concentration of performance; how algebraic connectivity governs consensus convergence and robustness; and how random geometric graph models clarify the trade-offs between connectivity and communication load. Programming examples in Python, C++, Java, MATLAB/Simulink, and Wolfram Mathematica demonstrated how to simulate and empirically evaluate robustness and scalability indices for consensus-based swarm behaviors.