Rendezvous

The trick is almost insultingly simple: each robot inches toward the average position of the neighbours it can sense. Do that, repeatedly, everywhere at once, and the whole flock collapses onto one point: the centroid of where everyone started. No vote, no negotiation, no boss. This is rendezvous, and it is consensus from earlier in this phase, except the thing being agreed upon is not a number but a place.

↘ Where would you meet a stranger in New York?

Years before Alpern, the economist Thomas Schelling asked a simpler-sounding version and got a famous answer. Imagine you have to meet someone in New York City tomorrow, but you cannot communicate to set a time or place. Where do you go, and when? When Schelling asked people, a striking share gave the same answer: Grand Central Terminal, at noon. Nobody told them to. There was no rule, no leader, no message. They converged on the obvious place anyway.

Schelling called such a spot a focal point (people now call it a Schelling point): a choice that stands out as the natural one, not because it is best, but because each person expects everyone else to expect it. The selection is made by shared culture and shared expectation, not by any equation. Schelling laid this out in his 1960 book The Strategy of Conflict, and in 2005 he shared the Nobel Memorial Prize in Economics, partly for ideas like this one.

Here is the tie back to the swarm. The robots in this lesson never need a focal point, because the averaging rule already breaks the tie for them: there is exactly one centroid, and the math drags everyone to it. The Schelling point is what you reach for when there is no shared rule to compute, only a shared guess about what the others will guess. Robots get a rule. Humans get a hunch.

Watch them fall together

The dots below are robots. Each step, every dot drifts toward the mean of its neighbours. Push the slider and watch the cloud implode toward one meeting point.

Try this:

1. Plain rendezvous. Leave everyone free and step the sim forward. The cloud spirals inward and lands on its own centre of mass. Read off the predicted meeting point, then check it against where they actually pile up.
2. Crank the step size. Slide α up and the swarm snaps together fast; slide it down and it oozes. Push it too far and watch the meeting overshoot and wobble. Averaging can be too eager.
3. Cut the graph. Split the swarm so two halves can't sense each other. Each half rendezvouses on its own point. Connectivity, not goodwill, is what buys you a single meeting place.

Two forces in tension: every robot wants to be where its neighbours are, and the only way to satisfy everyone is to all be in the same spot. The algorithm just lets that desire run to its conclusion.

The rule, in one line

Call robot $i$'s position $p_i$ and its set of sensed neighbours $N_i$. Every tick, it moves a fraction $\alpha$ of the way toward their average:

$p_i(t+1) = p_i(t) + \alpha \left( \frac{1}{|N_i|} \sum_{j \in N_i} p_j(t) - p_i(t) \right)$

That is the entire algorithm. The bracketed term is "where my neighbours' centre is, relative to me"; $\alpha$ is how boldly I step that way. Each robot runs it independently, using only what it can see. There is no global coordinate, no shared clock, no message that says the meeting is at X. The agreement is emergent: it falls out of everyone obeying the same local rule.

Where it lands, and why

If the communication graph is connected (if you can hop from any robot to any other through a chain of neighbours), the swarm provably converges to the centroid of its starting positions:

$\lim_{t \to \infty} p_i(t) = \frac{1}{n} \sum_{j=1}^n p_j(0)$

Connectivity is the whole ballgame. Disconnect the graph and you get one meeting point per connected component: three islands of robots that can't sense across the gaps produce three separate rendezvous, each one the centroid of its own little island. The math doesn't fail; it just answers a different question for each cluster.

↘ Why connectivity guarantees one point

Stack all the positions into a vector and the update becomes a single linear map, $p(t+1) = (I - \alpha L)\,p(t)$, where $L$ is the graph Laplacian, a matrix that encodes who senses whom. Its eigenvalues control everything.

$L$ always has a zero eigenvalue whose eigenvector is the all-ones vector $\mathbf{1}$; that is the mode where everyone shares one position, and the update leaves it untouched. The deep fact: the multiplicity of that zero eigenvalue equals the number of connected components. One connected graph means one zero eigenvalue, so there is exactly one surviving steady state, a single shared point. Two components means two zeros, two independent meeting points, and so on.

The smallest nonzero eigenvalue, the algebraic connectivity $\lambda_2$, sets the speed: the swarm contracts at a rate governed by $1 - \alpha\lambda_2$. A well-knit graph (big $\lambda_2$) snaps together; a stringy, barely-connected one crawls. And $\alpha$ must stay small enough that $|1 - \alpha\lambda_n| \le 1$ for the largest eigenvalue $\lambda_n$. Push $\alpha$ past that and the iteration overshoots and diverges. That is the wobble you can provoke in the sim.

Key takeaways

• Rendezvous is position consensus: every robot edges toward its neighbours' average position, and they all meet at one point.
• With a connected graph, that point is the centroid of the starting positions, no leader required.
• Disconnect the graph and you get one meeting point per connected component.
• It is the geometric foundation of formation control: agree on a point, then offset from it to agree on a shape.