08 Swarm Behaviors & Formations · #33 of 46

Distance-Based Formations

How a swarm holds its shape with no leader and no map

A skein of geese flying in a clean V-formation against a pale sky. — Geese hold a crisp V with no leader broadcasting coordinates. Each bird keeps one fixed offset from the bird ahead, and the whole formation falls out of that single repeated rule. · Jan Baker, CC BY-SA 2.0

A thousand fish wheel as one and never collide. There is no captain, no shared map, no fish shouting coordinates. Each one is doing something almost embarrassingly simple.

It is keeping a fixed distance from its neighbours, and that, repeated everywhere at once, is the shape.

That is the whole trick of distance-based formation control. Forget global coordinates. Forget a leader broadcasting "everyone to position 47." A robot in a distance-based formation knows exactly one kind of fact: I should be this far from that one, and that far from this one. Get every pairwise distance right and the shape falls out for free.

The rigid-rod picture

Imagine your robots bolted together with rigid rods of fixed length. Pull on the cluster and it slides across the floor; spin it and it rotates as a block. What it cannot do is change shape: the rods forbid it. That stiffness is the entire goal, and the beautiful part is that the rods are imaginary. Each robot enforces its own rod by watching one number: the distance to a neighbour, and how far that number has drifted from its target.

Define a target distance $d_{ij}$ for each connected pair $(i, j)$ .
Each robot nudges itself to drive its distance errors toward zero.
Do this everywhere, continuously, and the formation translates and rotates as one rigid body.

No robot ever needs to know where it is in the world. It only needs to know where it is relative to the robots it can see. That is what makes the idea scale: add a hundred more robots and no single one has to think any harder.

A herded flock of sheep moving across open ground while holding a loose, even spacing. — A herded flock keeps a roughly even gap between animals as it moves, a natural distance-based formation where the shape emerges from each one minding its neighbours rather than following a map. · Azonesa / Radomianin, CC BY-SA 4.0

When the sky has no GPS

This is not just a tidy thought experiment. The first big swarms of flying robots cheated: they flew indoors under banks of motion-capture cameras, an outside eye feeding every drone its exact position many times a second. Take the cameras away, fly outdoors, and you can lean on GPS instead, which is what most show drones do. But GPS gets you a few metres of accuracy on a good day, drops out under bridges and indoors, and can be jammed.

So a whole line of research went the other way: let each drone measure only the relative bearing and distance to its neighbours, using onboard cameras and radios, and never ask where it is on the map at all. Groups led by Martin Saska at the Czech Technical University flew swarms held together purely by this onboard relative localization, exactly so they would keep their shape in the places GPS abandons you. That is distance-based formation control doing the one job no central referee can.

When the shape goes floppy

Here is where it gets subtle. Constraining distances is not the same as constraining shape, and the gap between them is where formations quietly fail.

A triangle of three robots, each holding a target distance to the other two, is rigid. Three constraints, three robots, locked solid: it can only slide and spin. Now take four robots in a square and constrain just the four edges. Looks pinned down. It isn't. With nothing constraining the diagonal, the square can shear, collapsing smoothly into a parallelogram while every single edge length stays perfectly correct. The robots are all "satisfied" and the formation is melting in front of you.

Add one diagonal constraint and the shear is dead. That single extra rod is the difference between a shape and a sad rhombus.

Maxwell counted bars in 1864

The counting rule is older than robots. James Clerk Maxwell, the same physicist who tied electricity and magnetism together, worked out in 1864 how to tell whether a frame of stiff bars and pin joints would stand up or fold. Count the bars, count the joints, and the arithmetic tells you if the structure is braced or floppy. Engineers used it to design bridges and roof trusses long before anyone thought to point it at a flying robot.

The catch is that simple counting can lie. You can have the right number of bars and still leave a hole somewhere, with a wasted extra bar bunched up in a corner that braces nothing. The mathematician Gerard Laman pinned down the exact condition in 1970: in the plane you need $2n - 3$ bars and every subgroup of robots has to carry its fair share, so no part is left under-braced while another is over-stiffened. That precise statement is what robotics borrowed wholesale to reason about which formations actually hold their shape.

Remove an edge from a rigid formation and it goes floppy again: the robots slide into a different shape while still honouring every remaining distance. So the real engineering question is never "are the distances right?" It's "are there enough of the right distances to leave only one shape standing?"

The two jobs at once

The genuinely hard part isn't holding a static shape. It's holding the shape while the whole group moves toward a target. Every robot is simultaneously a shape-keeper (don't let the formation deform) and a traveller (get us all to the goal). Those two pulls have to be balanced every instant: too much travel and the formation smears; too much shape-keeping and the group never leaves. Solve that tension and you have robots that march in tight formation across a room without anyone in charge.

The math: formation energy and the gradient that holds the shape

Treat the whole formation as a single spring network and write down its potential energy. For an edge set $E$ with target distances $d_{ij}$ :

$E = \sum_{(i,j) \in E} \left(\,\lVert p_i - p_j \rVert - d_{ij}\,\right)^2$

Every term is the squared error of one "rod." The energy is zero exactly when every distance hits its target, and grows as the shape distorts. The controller's job is to roll downhill on this surface, so each robot follows the negative gradient of the energy:

$a_i = -k \sum_{j:(i,j) \in E} \left(\,\lVert p_i - p_j \rVert - d_{ij}\,\right) \frac{p_i - p_j}{\lVert p_i - p_j \rVert}$

Read it physically: the fraction is a unit vector pointing from neighbour $j$ toward robot $i$ ; the scalar in front is the signed distance error. If $i$ is too far, the error is positive and the robot is pulled in; too close, and it's pushed out. Each rod behaves like a spring with rest length $d_{ij}$ , and the gain $k$ sets how stiff the springs are.

A formation is rigid when the distance constraints determine the positions uniquely, up to a rigid motion (translation and rotation). That "up to a rigid motion" is why the energy never tries to fix the formation's global position or heading: sliding and spinning leave every distance untouched, so they cost zero energy and the controller leaves them free. The minimal recipe in the plane is the $2n - 3$ count from above; below it, the energy surface has a flat valley the shape can slide along without ever climbing, and that valley is the shear you watched the square fall into.

1,218 drones, one operator

To see just how far the scripted approach can scale, look at Intel's Shooting Star drones. At the opening ceremony of the 2018 Winter Olympics in PyeongChang, 1,218 of them rose together, formed a snowboarder in midair, and melted into the five Olympic rings. It set a Guinness World Record for the most drones airborne at once, smashing Intel's own previous mark of 500, flown in Germany in 2016.

The numbers behind it are the fun part. Each little drone weighs less than a volleyball and carries an LED that can mix over four billion colour combinations. The whole fleet is flown from a single computer by one operator, who never touches a joystick: the software hands each craft its path frame by frame. And the Olympic show was not even live. The weather that night was risky, so the broadcast quietly cut to a version filmed weeks earlier, which roughly 28 million viewers watched without ever knowing.

Key takeaways

Shape from distances. Maintain target distances $d_{ij}$ between neighbours and the formation holds, with no leader and no global coordinates.
Constraints aren't shape. A square held only by its four edges can shear into a parallelogram; you need the right number of the right constraints.
Rigidity has a count. In 2D a formation needs at least $2n - 3$ distance constraints, or it flexes and shears.
Two jobs at once. Keeping the formation rigid while the whole group translates is the real control problem.

A school of fish has no leader and no map, yet it turns as one and never tears. It does it with the humblest rule in the swarm playbook: stay this far from the ones beside you.

Get enough of those little rules pointing the same way and a shape appears out of nowhere: rigid, mobile, and answerable to no one. That is formation control: not a plan handed down from above, but an agreement that holds itself together from the inside.