Laplacian Flow

In the last lesson, robots agreed by taking discrete steps: tick, tick, tick toward consensus. Now slow the clock until the steps vanish and the motion becomes continuous. The stair-stepping smooths into a glide. And once it's smooth, a century of physics rushes in to tell you precisely how it behaves.

The thermostat analogy

Picture a row of rooms connected by open doors, each starting at a different temperature. No one runs the furnace; no one is in charge. Heat simply flows from hot to cold across every doorway at once. Wait long enough and every room settles to the same temperature: the average of where they all started.

Swarm consensus is that, with information playing the role of heat. Each robot continuously nudges its value toward its neighbors', at a rate set by how far apart they are. The bigger the disagreement across a link, the harder the pull:

$\dot{x}_i = -\sum_{j \in N_i} (x_i - x_j)$

Robot $i$'s value changes in proportion to the total gap between it and everyone it can talk to. That single line is the whole algorithm.

Disagreement is energy, and it rolls downhill

Here's the elegant part. Define the swarm's total disagreement as

$E = \frac{1}{2}\sum_{(i,j)\,\in\,E} (x_i - x_j)^2$

that is, sum the squared gap across every communication link. Laplacian flow is nothing more than gradient descent on this energy. The robots aren't told to agree; they're each rolling downhill on a shared landscape, and the bottom of that valley is consensus. They reach it not by negotiation but by physics, the way water finds its level.

In matrix form the whole swarm collapses to one breathtakingly compact statement:

$\dot{x} = -Lx$

where $L$ is the graph Laplacian, a matrix that encodes the entire topology of who can hear whom. The minus sign is the only thing standing between agreement and a swarm that flies apart.

What you would see

You can run this in your head. Start a handful of robots at wildly different values and watch:

• Everything glides. Unlike the discrete rule, which jumps in visible steps, continuous flow slides every value toward agreement along a smooth curve: no stair-stepping, no jitter.
• The error decays exponentially. Track the spread of values over time and it collapses fast at first, then trails off in a long, patient tail crawling toward zero. It never quite arrives; it just gets exponentially close.
• Density sets the speed. Add more communication links and information mixes faster, so the swarm agrees sooner. A sparse chain converges too; it just takes its sweet time.

That last point has a precise number behind it. The decay rate is governed by $\lambda_2$, the second-smallest eigenvalue of the Laplacian, known as the algebraic connectivity or Fiedler value. Denser, better-connected graphs have a larger $\lambda_2$ and therefore agree faster.

↘ Solving ẋ = −Lx exactly

The equation $\dot{x} = -Lx$ is a linear system, so it has a clean closed-form solution:

$x(t) = e^{-Lt}\,x(0)$

For a connected graph, $L$ has exactly one zero eigenvalue whose eigenvector is the all-ones vector $\mathbf{1}$. That zero mode never decays (it's the part of the state that's already in agreement), and every other mode dies off. So the swarm converges to the average of its starting values:

$\lim_{t \to \infty} x(t) = \frac{1}{n}\,\mathbf{1}^{T} x(0)\cdot \mathbf{1}$

The rate at which it gets there is bounded by the smallest nonzero eigenvalue:

$\lVert x(t) - \bar{x}\rVert \le e^{-\lambda_2 t}\,\lVert x(0) - \bar{x}\rVert$

This is why $\lambda_2$ is the headline number. Want consensus error below $0.001$ in minimum time? Maximize $\lambda_2$: add edges, strengthen weak links, kill bottlenecks.

↘ Why it really is the heat equation, not just like it

The link to heat is not a loose metaphor. The continuous heat equation uses the Laplace operator $\nabla^2$, which at each point measures how much a value sits above or below the average of its surroundings. Approximate that operator on a grid with the finite difference method and the recipe becomes: for each point, subtract its value from the sum of its neighbors' values. Write that down for a graph instead of a grid and you have rebuilt $-L$ exactly. So $L$ is the discrete Laplace operator, the graph standing in for the continuous space.

There is even a boundary condition baked in. A robot only ever talks to the neighbors it actually has, with nothing reaching in from outside the swarm. In heat-flow terms that is a free, insulated edge (a homogeneous Neumann boundary): no heat crosses the outer wall, so the total amount inside is conserved. That conservation is why the swarm settles on the average of its starting values and not some other number. The heat had nowhere to leak.

From continuous math to running code

Real robots have clocks, so you implement this beautiful continuous flow as discrete Euler steps with a small $dt$. The continuous analysis isn't thrown away: it tells you how small $dt$ has to be (smaller than $1/\lambda_{\max}$, or your "agreement" will overshoot and oscillate into nonsense).

fn laplacian_flow_step(agents: &mut [Agent], dt: f32, neighbors: &[Vec<usize>]) {
    let mut derivatives = vec![0.0; agents.len()];

    for i in 0..agents.len() {
        let mut sum_diff = 0.0;
        for &j in &neighbors[i] {
            sum_diff += agents[j].value - agents[i].value;
        }
        derivatives[i] = -sum_diff;
    }

    for i in 0..agents.len() {
        agents[i].value += derivatives[i] * dt;
    }
}

Key takeaways

• Continuous-time consensus obeys $\dot{x} = -Lx$, with $L$ the graph Laplacian.
• It is exactly gradient descent on the disagreement energy $E = \frac{1}{2}\sum (x_i - x_j)^2$.
• Error decays exponentially at rate $\lambda_2$, the algebraic connectivity. Denser graphs agree faster.
• In code it's Euler integration with $dt < 1/\lambda_{\max}$ for stability.