A multi-robot system consists of a set of robots \( \mathcal{R} = \{1,\dots,N\} \) executing a joint task, such as rendezvous, formation, or cooperative manipulation. Coordination specifies how information and decisions are shared across robots. At a high level:

• Centralized coordination: a single logical node (e.g., a server) collects state estimates of all robots, solves a global decision/optimization problem, and sends commands or references back to each robot.
• Decentralized coordination: each robot computes its own control inputs using only locally available information (on-board sensing and communication with neighbors), without any all-knowing central authority.

The trade-offs hinge on information structure, computational complexity, communication burden, and robustness to failures. Centralized schemes are often easier to design but suffer from scaling and single-point-of-failure issues. Decentralized schemes are more robust and scalable but are harder to analyze and design.

flowchart LR
  subgraph CENTRALIZED
    C["Coordinator (global optimization)"]
    R1["Robot 1"]
    R2["Robot 2"]
    RN["Robot N"]
    R1 --> C
    R2 --> C
    RN --> C
    C --> R1
    C --> R2
    C --> RN
  end

  subgraph DECENTRALIZED
    D1["Robot 1 (local policy)"]
    D2["Robot 2 (local policy)"]
    DN["Robot N (local policy)"]
    D1 -- "neighbor links" --- D2
    D2 --- DN
    DN --- D1
  end

  CENTRALIZED:::arch --> DECENTRALIZED:::arch

  classDef arch fill:#f0f0f0,stroke:#333,stroke-width:1px;
        

To move beyond intuition, we now formalize the underlying mathematical models that will allow us to rigorously compare these architectures.

We consider a team of \( N \) robots, robot \( i \) having state \( x_i(t) \in \mathbb{R}^{d} \) and control input \( u_i(t) \in \mathbb{R}^{m} \). For simplicity in this lesson, we use single-integrator dynamics:

\[ \dot{x}_i(t) = u_i(t), \quad i = 1,\dots,N. \]

Stacking all states into a single vector \( x(t) \in \mathbb{R}^{dN} \) and inputs into \( u(t) \in \mathbb{R}^{mN} \), we write

\[ x(t) = \begin{bmatrix} x_1(t) \\ \vdots \\ x_N(t) \end{bmatrix}, \quad u(t) = \begin{bmatrix} u_1(t) \\ \vdots \\ u_N(t) \end{bmatrix}, \quad \dot{x}(t) = u(t). \]

A typical global performance criterion over horizon \( [0,T] \) is a sum of local stage costs plus a terminal cost:

\[ J(u) = \int_0^T \sum_{i=1}^N \ell_i\big(x_i(t),u_i(t)\big)\,\mathrm{d}t + \Phi\big(x(T)\big), \]

subject to dynamics and constraints such as collision avoidance, actuation limits, or task-specific constraints. Collision avoidance can be modeled, for example, via pairwise distance constraints

\[ \big\|x_i(t) - x_j(t)\big\|_2 \ge d_{\min}, \quad \forall i \neq j. \]

Information exchange among robots is described by a (possibly time-varying) communication graph \( \mathcal{G} = (\mathcal{V},\mathcal{E}) \), where \( \mathcal{V} = \{1,\dots,N\} \) and an undirected edge \( (i,j) \in \mathcal{E} \) indicates that robots \( i \) and \( j \) can exchange information. The neighbor set of robot \( i \) is \( \mathcal{N}_i = \{j \in \mathcal{V} \mid (i,j) \in \mathcal{E}\} \).

In a centralized architecture, a logical coordinator has access to the full state \( x(t) \) (typically via communication from all robots) and computes the entire input trajectory \( u(t) \) that minimizes the global cost \( J(u) \) subject to system-level constraints. In continuous time, the centralized problem is

\[ \begin{aligned} \min_{u(\cdot)} \quad & J(u) = \int_0^T \sum_{i=1}^N \ell_i\big(x_i(t),u_i(t)\big)\,\mathrm{d}t + \Phi\big(x(T)\big) \\ \text{s.t.} \quad & \dot{x}(t) = u(t), \\ & x(0) = x_0, \\ & g\big(x(t),u(t)\big) \le 0 \quad \text{for almost all } t \in [0,T], \end{aligned} \]

where \( g \) encodes constraints such as collision avoidance. After discretizing time with step \( \Delta t \) and horizon \( K \), we obtain a finite-dimensional optimization problem, e.g.

\[ x_{k+1} = x_k + \Delta t\,u_k, \quad k=0,\dots,K-1, \]

and the optimizer solves for all inputs \( u_0,\dots,u_{K-1} \) simultaneously. Even for simple quadratic costs

\[ \ell_i(x_i,u_i) = \tfrac{1}{2}\big\|x_i - x_i^{\mathrm{ref}}\big\|_2^2 + \tfrac{\rho}{2}\big\|u_i\big\|_2^2, \]

the centralized problem couples all robots through constraints \( g \) and the stacked dynamics, leading to large optimization problems of dimension proportional to \( dNK \). A naive second-order method may take time on the order of \( \mathcal{O}\big((dNK)^3\big) \) per solve due to matrix factorizations.

For model-predictive control (MPC) implementations, such centralized solves must be repeated at every sampling time, which quickly becomes prohibitive as \( N \) grows.

In decentralized coordination, robot \( i \) computes its control input using only its own state and information received from neighbors:

\[ u_i(t) = \pi_i\Big( x_i(t), \{x_j(t)\}_{j \in \mathcal{N}_i}, \theta_i \Big), \]

where \( \pi_i \) is a local policy and \( \theta_i \) contains any parameters or local objectives. The global behavior is emergent: the global cost

\[ J(u) = \sum_{i=1}^N J_i(u_i), \quad J_i(u_i) = \int_0^T \ell_i\big(x_i(t),u_i(t)\big)\,\mathrm{d}t + \Phi_i\big(x_i(T)\big), \]

is indirectly minimized (or at least reduced) by the combination of all local decisions. A classical tool for such systems is the graph Laplacian. Define the adjacency matrix \( A \in \mathbb{R}^{N \times N} \) by \( A_{ij}=1 \) if \( (i,j)\in\mathcal{E} \) and \( A_{ij}=0 \) otherwise, the degree matrix \( D = \operatorname{diag}(d_1,\dots,d_N) \) with \( d_i = |\mathcal{N}_i| \), and the Laplacian

\[ L = D - A. \]

For real-valued scalar states \( p_i(t) \in \mathbb{R} \), a common decentralized coordination law uses only relative differences between neighbors:

\[ \dot{p}_i(t) = -k \sum_{j \in \mathcal{N}_i} \big(p_i(t) - p_j(t)\big), \quad k > 0. \]

Stacking \( p(t) = [p_1(t),\dots,p_N(t)]' \), this becomes

\[ \dot{p}(t) = -k L\,p(t). \]

This system has rich properties (consensus, convergence rates, and robustness) that we will study formally in the next lesson. At this point, note that all operations in the right-hand side depend only on neighbor differences, which makes this law implementable in a decentralized way.

flowchart TD
  S["Start at time k"] --> OBS["Each robot i measures own state and receives neighbor states"]
  OBS --> LOC["Compute local control u_i = pi_i(x_i, neighbors)"]
  LOC --> APPLY["Apply u_i to low-level controller"]
  APPLY --> NEXT["Advance system (integrate dynamics)"]
  NEXT --> S
        

Consider \( N \) robots moving along a line with scalar positions \( p_i(t) \in \mathbb{R} \) and single-integrator dynamics \( \dot{p}_i(t) = u_i(t) \). The rendezvous objective is to bring all robots to the initial average position

\[ \bar{p}(0) = \frac{1}{N} \sum_{i=1}^N p_i(0). \]

5.1 Centralized Controller

A centralized controller first computes \( \bar{p}(0) \) and then broadcasts it. Each robot implements

\[ \dot{p}_i(t) = -k\big(p_i(t) - \bar{p}(0)\big), \quad k > 0. \]

This is a linear first-order system whose solution is

\[ p_i(t) = \bar{p}(0) + \big(p_i(0) - \bar{p}(0)\big)\mathrm{e}^{-kt}. \]

As \( t \to \infty \), \( \mathrm{e}^{-kt} \to 0 \), hence all positions converge exponentially to \( \bar{p}(0) \). This is easily analyzed and implemented but requires a global computation of the average and reliable broadcast to all robots.

5.2 Decentralized Neighbor-Averaging Controller

Suppose the robots form a connected undirected communication graph \( \mathcal{G} \). A purely decentralized law is

\[ \dot{p}_i(t) = -k \sum_{j \in \mathcal{N}_i}\big(p_i(t) - p_j(t)\big), \quad k > 0. \]

In vector form \( \dot{p}(t) = -kLp(t) \). Since \( L \) is symmetric positive semidefinite, there exists an orthonormal basis of eigenvectors \( v_1,\dots,v_N \) with eigenvalues

\[ 0 = \lambda_1 < \lambda_2 \le \dots \le \lambda_N, \quad Lv_r = \lambda_r v_r. \]

Moreover, \( v_1 = \tfrac{1}{\sqrt{N}}[1,\dots,1]' \) is the eigenvector associated with \( \lambda_1 = 0 \). The solution can be written as

\[ p(t) = \mathrm{e}^{-kLt}p(0) = \sum_{r=1}^N \mathrm{e}^{-k\lambda_r t} (v_r' p(0)) v_r. \]

For \( r \ge 2 \) we have \( \lambda_r > 0 \), so the coefficients \( \mathrm{e}^{-k\lambda_r t} \) decay to zero as \( t \to \infty \). Only the component along \( v_1 \) remains:

\[ \lim_{t \to \infty} p(t) = (v_1' p(0)) v_1 = \frac{1}{N}\left(\sum_{i=1}^N p_i(0)\right)[1,\dots,1]'. \]

Thus all robots converge to the initial average, just as in the centralized controller, but using only neighbor communication. This is a prototypical example where decentralized and centralized coordination yield the same limit behavior under ideal conditions, yet have very different communication and computation structures.

We now implement a simple discrete-time simulation for 1D rendezvous. The continuous-time dynamics \( \dot{p}_i = u_i \) are approximated using forward Euler:

\[ p_i(k+1) = p_i(k) + \Delta t\,u_i(k). \]

The following Python code uses numpy to simulate both centralized and decentralized controllers on a ring communication graph.

import numpy as np

def ring_neighbors(N):
    """Return neighbor sets for a ring topology."""
    neighbors = []
    for i in range(N):
        left = (i - 1) % N
        right = (i + 1) % N
        neighbors.append([left, right])
    return neighbors

def centralized_step(p, k_gain, dt):
    """One step of centralized rendezvous: move toward initial average."""
    N = len(p)
    p_avg0 = np.mean(p0)  # global average at time 0 (constant)
    u = -k_gain * (p - p_avg0)
    return p + dt * u

def decentralized_step(p, neighbors, k_gain, dt):
    """One step of decentralized neighbor-averaging."""
    N = len(p)
    u = np.zeros_like(p)
    for i in range(N):
        s = 0.0
        for j in neighbors[i]:
            s += (p[i] - p[j])
        u[i] = -k_gain * s
    return p + dt * u

# parameters
N = 6
dt = 0.05
k_gain = 1.0
T = 5.0
steps = int(T / dt)

# random initial positions
rng = np.random.default_rng(1)
p0 = rng.uniform(-5.0, 5.0, size=N)

# neighbor structure (ring)
nbrs = ring_neighbors(N)

# simulate both controllers
p_central = p0.copy()
p_decent  = p0.copy()

hist_central = [p_central.copy()]
hist_decent  = [p_decent.copy()]

for k in range(steps):
    p_central = centralized_step(p_central, k_gain, dt)
    p_decent  = decentralized_step(p_decent, nbrs, k_gain, dt)
    hist_central.append(p_central.copy())
    hist_decent.append(p_decent.copy())

hist_central = np.array(hist_central)
hist_decent  = np.array(hist_decent)

# Example: print final positions
print("Initial positions:", p0)
print("Centralized final:", hist_central[-1])
print("Decentralized final:", hist_decent[-1])
print("Initial average:", np.mean(p0))
      

With a connected graph and sufficiently small \( \Delta t \), both controllers drive robots to a common value close to the initial average, but their transient behaviors and communication patterns differ.

The following C++ snippet implements one discrete-time update for both centralized and decentralized controllers. Note that real systems would integrate these updates into a control loop interfacing with sensors and actuators.

#include <iostream>
#include <vector>
#include <cmath>

using std::size_t;

void centralized_step(std::vector<double> &p,
                      const std::vector<double> &p0,
                      double k_gain, double dt)
{
    const size_t N = p.size();
    double p_avg0 = 0.0;
    for (size_t i = 0; i < N; ++i) {
        p_avg0 += p0[i];
    }
    p_avg0 /= static_cast<double>(N);

    for (size_t i = 0; i < N; ++i) {
        double u_i = -k_gain * (p[i] - p_avg0);
        p[i] += dt * u_i;
    }
}

void decentralized_step(std::vector<double> &p,
                        const std::vector<std::vector<size_t> > &neighbors,
                        double k_gain, double dt)
{
    const size_t N = p.size();
    std::vector<double> u(N, 0.0);

    for (size_t i = 0; i < N; ++i) {
        double s = 0.0;
        for (size_t j : neighbors[i]) {
            s += (p[i] - p[j]);
        }
        u[i] = -k_gain * s;
    }

    for (size_t i = 0; i < N; ++i) {
        p[i] += dt * u[i];
    }
}

int main()
{
    const size_t N = 5;
    double dt = 0.05;
    double k_gain = 1.0;
    std::vector<double> p0{ -2.0, -1.0, 0.5, 1.5, 3.0 };
    std::vector<double> p_central = p0;
    std::vector<double> p_decent  = p0;

    // ring neighbors
    std::vector<std::vector<size_t> > neighbors(N);
    for (size_t i = 0; i < N; ++i) {
        neighbors[i].push_back((i + N - 1) % N);
        neighbors[i].push_back((i + 1) % N);
    }

    const int steps = 200;
    for (int k = 0; k < steps; ++k) {
        centralized_step(p_central, p0, k_gain, dt);
        decentralized_step(p_decent, neighbors, k_gain, dt);
    }

    std::cout << "Centralized final:" << std::endl;
    for (double v : p_central) std::cout << v << " ";
    std::cout << std::endl;

    std::cout << "Decentralized final:" << std::endl;
    for (double v : p_decent) std::cout << v << " ";
    std::cout << std::endl;

    return 0;
}
      

This code emphasizes how centralized control requires access to p0 (or the global average), whereas the decentralized step uses only neighbor differences.

A Java version follows the same structure: vectors of positions and a neighbor list for decentralized updates.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Rendezvous {

    public static void centralizedStep(double[] p, double[] p0,
                                       double kGain, double dt) {
        int N = p.length;
        double sum = 0.0;
        for (int i = 0; i < N; ++i) {
            sum += p0[i];
        }
        double pAvg0 = sum / N;

        for (int i = 0; i < N; ++i) {
            double u = -kGain * (p[i] - pAvg0);
            p[i] += dt * u;
        }
    }

    public static void decentralizedStep(double[] p,
                                         List<List<Integer>> neighbors,
                                         double kGain, double dt) {
        int N = p.length;
        double[] u = new double[N];

        for (int i = 0; i < N; ++i) {
            double s = 0.0;
            for (int j : neighbors.get(i)) {
                s += (p[i] - p[j]);
            }
            u[i] = -kGain * s;
        }

        for (int i = 0; i < N; ++i) {
            p[i] += dt * u[i];
        }
    }

    public static void main(String[] args) {
        int N = 4;
        double dt = 0.05;
        double kGain = 1.0;
        double[] p0 = new double[] { -1.0, 0.0, 2.0, 4.0 };
        double[] pCentral = Arrays.copyOf(p0, p0.length);
        double[] pDecent = Arrays.copyOf(p0, p0.length);

        // ring neighbor lists
        List<List<Integer>> neighbors = new ArrayList<>();
        for (int i = 0; i < N; ++i) {
            List<Integer> nbr = new ArrayList<>();
            nbr.add((i - 1 + N) % N);
            nbr.add((i + 1) % N);
            neighbors.add(nbr);
        }

        int steps = 200;
        for (int k = 0; k < steps; ++k) {
            centralizedStep(pCentral, p0, kGain, dt);
            decentralizedStep(pDecent, neighbors, kGain, dt);
        }

        System.out.println("Centralized final: " + Arrays.toString(pCentral));
        System.out.println("Decentralized final: " + Arrays.toString(pDecent));
    }
}
      

This structure extends naturally to higher-dimensional states \( x_i \in \mathbb{R}^d \) by storing arrays or small vector classes instead of scalars.

The following MATLAB script simulates the same discrete-time rendezvous setup. A Simulink implementation would replace the explicit Euler update with integrator blocks and gain blocks wired according to the centralized or decentralized interconnection.

function multi_robot_rendezvous
    N = 5;
    dt = 0.05;
    T  = 5.0;
    steps = round(T / dt);
    k_gain = 1.0;

    rng(1);
    p0 = -3 + 6 * rand(N,1);

    % ring neighbors
    neighbors = cell(N,1);
    for i = 1:N
        neighbors{i} = [mod(i-2,N)+1, mod(i,N)+1]; % 1-based ring
    end

    p_central = p0;
    p_decent  = p0;

    p_hist_central = zeros(N, steps+1);
    p_hist_decent  = zeros(N, steps+1);
    p_hist_central(:,1) = p_central;
    p_hist_decent(:,1)  = p_decent;

    for k = 1:steps
        p_central = centralized_step(p_central, p0, k_gain, dt);
        p_decent  = decentralized_step(p_decent, neighbors, k_gain, dt);
        p_hist_central(:,k+1) = p_central;
        p_hist_decent(:,k+1)  = p_decent;
    end

    t = 0:dt:T;
    figure;
    subplot(2,1,1);
    plot(t, p_hist_central);
    title('Centralized rendezvous');
    xlabel('time'); ylabel('position');

    subplot(2,1,2);
    plot(t, p_hist_decent);
    title('Decentralized rendezvous');
    xlabel('time'); ylabel('position');
end

function p_next = centralized_step(p, p0, k_gain, dt)
    N = numel(p);
    p_avg0 = mean(p0);
    u = -k_gain * (p - p_avg0);
    p_next = p + dt * u;
end

function p_next = decentralized_step(p, neighbors, k_gain, dt)
    N = numel(p);
    u = zeros(N,1);
    for i = 1:N
        s = 0.0;
        for j = neighbors{i}
            s = s + (p(i) - p(j));
        end
        u(i) = -k_gain * s;
    end
    p_next = p + dt * u;
end
      

In Simulink, one can create a subsystem for each robot implementing \( \dot{p}_i = u_i \). For centralized coordination, a global block computes the average and broadcasts it to the subsystems. For decentralized coordination, each subsystem receives neighbor states via signal lines reflecting the communication graph.

Mathematica is convenient for symbolic analysis and rapid prototyping of multi-robot coordination laws. The code below simulates decentralized rendezvous and visualizes trajectories.

ClearAll["Global`*"];

(* parameters *)
n = 6;
dt = 0.05;
tmax = 5.0;
steps = Round[tmax/dt];
kGain = 1.0;

(* initial positions *)
SeedRandom[1];
p0 = RandomReal[{-5, 5}, n];

(* ring neighbors as index lists *)
neighbors[i_] := {Mod[i - 2, n] + 1, Mod[i, n] + 1};

centralizedStep[p_List, p0_List] := Module[
  {pAvg0, u},
  pAvg0 = Mean[p0];
  u = -kGain (p - pAvg0);
  p + dt u
];

decentralizedStep[p_List] := Module[
  {u, s},
  u = Table[
    s = Total[(p[[i]] - p[[#]]) & /@ neighbors[i]];
    -kGain s,
    {i, 1, n}
  ];
  p + dt u
];

pCentral = p0;
pDecent = p0;
histCentral = {pCentral};
histDecent = {pDecent};

Do[
  pCentral = centralizedStep[pCentral, p0];
  pDecent = decentralizedStep[pDecent];
  AppendTo[histCentral, pCentral];
  AppendTo[histDecent, pDecent];
, {steps}];

tgrid = Range[0, tmax, dt];

ListLinePlot[
  Transpose[histDecent],
  PlotRange -> All,
  AxesLabel -> {"time index", "position"},
  PlotLegends -> Table["robot " <> ToString[i], {i, 1, n}],
  PlotLabel -> "Decentralized rendezvous trajectories"
]
      

Symbolic tools in Mathematica can further be used to analyze eigenvalues of the Laplacian and verify consensus properties for small networks.

Problem 1 (Centralized Quadratic Cost): Consider the 1D rendezvous setup with positions \( p_i(t) \) and dynamics \( \dot{p}_i = u_i \). For a fixed horizon \( T \), the centralized controller minimizes

\[ J(u) = \frac{1}{2}\sum_{i=1}^N \int_0^T \Big( p_i(t) - \bar{p}(0) \Big)^2 + \rho\,u_i(t)^2 \,\mathrm{d}t, \quad \rho > 0. \]

Show that the optimal controller is linear in the error \( p_i(t) - \bar{p}(0) \) and derive the feedback gain for the infinite-horizon limit.

Solution: The problem separates across robots since both the cost and dynamics are decoupled. For each robot, we have a scalar linear-quadratic regulator (LQR) with dynamics \( \dot{p}_i = u_i \) and cost

\[ J_i(u_i) = \frac{1}{2}\int_0^T \Big( p_i(t) - \bar{p}(0) \Big)^2 + \rho u_i(t)^2 \,\mathrm{d}t. \]

Shifting coordinates via \( e_i(t) = p_i(t) - \bar{p}(0) \) yields \( \dot{e}_i = u_i \) and cost \( J_i = \tfrac{1}{2}\int_0^T e_i(t)^2 + \rho u_i(t)^2 \,\mathrm{d}t \) . The infinite-horizon LQR solution for \( \dot{e} = u \) with state penalty 1 and input penalty \( \rho \) is

\[ u_i(t) = -k\,e_i(t), \quad k = \sqrt{\frac{1}{\rho}}. \]

Hence the centralized optimal feedback has the form \( u_i(t) = -k\big(p_i(t) - \bar{p}(0)\big) \), confirming the proportional structure used earlier and providing an explicit expression for the optimal gain \( k \).

Problem 2 (Invariance of Average under Decentralized Law): For the decentralized rendezvous dynamics

\[ \dot{p}_i(t) = -k \sum_{j \in \mathcal{N}_i} \big(p_i(t) - p_j(t)\big), \quad k > 0, \]

show that the average \( \bar{p}(t) = \tfrac{1}{N}\sum_{i=1}^N p_i(t) \) is constant over time.

Solution: Differentiate the average:

\[ \dot{\bar{p}}(t) = \frac{1}{N}\sum_{i=1}^N \dot{p}_i(t) = -\frac{k}{N}\sum_{i=1}^N \sum_{j \in \mathcal{N}_i} \big(p_i(t) - p_j(t)\big). \]

For an undirected graph, each unordered pair \( \{i,j\} \) appears twice in the double sum: once as \( p_i - p_j \) and once as \( p_j - p_i \). Therefore the sum cancels:

\[ \sum_{i=1}^N \sum_{j \in \mathcal{N}_i} \big(p_i - p_j\big) = 0, \]

and \( \dot{\bar{p}}(t) = 0 \), proving that \( \bar{p}(t) = \bar{p}(0) \) is invariant. This invariance is a key ingredient in showing convergence to the initial average.

Problem 3 (Centralized vs Decentralized Communication Load): Assume each robot state is a vector in \( \mathbb{R}^{d} \). In one sampling step, how many state vectors are transmitted for: (a) a centralized architecture, and (b) a decentralized architecture implementing the ring graph described in the code examples?

Solution: (a) In a centralized architecture, every robot sends its state to the coordinator (\( N \) vectors) and the coordinator sends commands back (\( N \) vectors). Thus \( 2N \) state-like messages are exchanged per step.

(b) In the ring decentralized architecture, each robot sends its state only to its two neighbors. Each directed edge carries one state vector. There are \( N \) undirected edges in a ring and \( 2N \) directed edges, so \( 2N \) state vectors are transmitted per step as well. However, the key difference is that no node must receive all \( N \) states; the per-node bandwidth demand remains constant as \( N \) grows, which is favorable for scalability.

Problem 4 (Failure of Central Coordinator): Consider a centralized scheme where the coordinator fails at time \( t_f \). Describe qualitatively the behavior of the robots after \( t_f \) if low-level controllers simply hold the last received command. Contrast this with a decentralized scheme under the same fault.

Solution: In the centralized scheme, once the coordinator fails robots no longer receive updated commands or references. If the last command is a constant velocity, robots may drift away from their intended rendezvous point. If the last command was zero, robots will freeze at their current positions and coordination will stop. In either case, there is a single point of failure.

In a decentralized scheme, a single node failure (of one robot) only removes a vertex from the graph. If the remaining graph stays connected, the surviving robots continue to exchange information and can still achieve rendezvous (possibly with a changed average value). Decentralized coordination is therefore more robust to isolated faults, although it is still vulnerable to large-scale network failures.

Problem 5 (Continuous vs Discrete-Time Stability): For the discrete-time decentralized update

\[ p(k+1) = \big(I - \alpha L\big)p(k), \]

where \( L \) is the Laplacian and \( \alpha > 0 \), derive a sufficient condition on \( \alpha \) to guarantee that all eigenvalues of \( I - \alpha L \) except one lie strictly inside the unit circle.

Solution: The eigenvalues of \( I - \alpha L \) are \( 1 - \alpha \lambda_r \), where \( \lambda_r \) are the eigenvalues of \( L \). We know \( 0 = \lambda_1 < \lambda_2 \le \dots \le \lambda_N \). The eigenvalue corresponding to \( \lambda_1 = 0 \) is \( 1 \) (associated with the consensus subspace), which is allowed. For \( r \ge 2 \), we need \( |1 - \alpha \lambda_r| < 1 \), which implies

\[ -1 < 1 - \alpha \lambda_r < 1 \quad \Rightarrow \quad 0 < \alpha \lambda_r < 2. \]

Since \( \lambda_r \le \lambda_N \), \( \alpha \lambda_N < 2 \) is sufficient. Hence a sufficient stability condition is

\[ 0 < \alpha < \frac{2}{\lambda_N}. \]

This connects step size selection in discrete-time decentralized control with spectral properties of the communication graph.

In this lesson we formalized centralized and decentralized coordination for multi-robot systems. Starting from a global optimal control viewpoint, we showed how centralized coordinators optimize a joint cost over all robots, while decentralized schemes rely on local policies defined over a communication graph. Using the rendezvous problem, we derived and analyzed simple controllers, highlighted the role of the graph Laplacian, and illustrated how decentralized neighbor-averaging can recover the same limiting behavior as a centralized controller. The next lesson will deepen this analysis, introducing the consensus framework and formation control in continuous and discrete time.