Lloyd’s algorithm
Spreads a drone swarm evenly over any field with a GPS boundary, for the Waterloo Aerial Robotics Group.
0.46 → 0.06Spacing unevenness from a bunched start to the end, where 0 is perfectly even. Median of 90 of 90 simulated runs. Tested in simulation only.
- Status
- In review
- Role
- Built for the autonomy software team in November 2026, as my second task there. I wrote the whole pull request: the module and its 28 tests.
- Code
- Pull request #247
What it does
After take-off the drones are bunched together. To cover a field they have to spread out evenly, whatever its shape. Give this module each drone’s GPS position and the field’s boundary, and it says where each drone should fly next.
Each step splits the field into Voronoi cells, the area closest to each drone, and moves every drone to the middle (the centroid) of its cell. Repeating this spreads the swarm out evenly.
Step 32 of 32Coverage cost 513 m²
Coverage cost at each step, log scale. It never goes up.
The data and the method
- Where the test fields came from
- There’s no recorded data. The tests make their own: 3 fields (a 200 m square, a 200 m L-shape and an irregular field), with 4, 6 or 10 drones starting bunched near a launch point, from 10 different random starts each. A further 600 random starts put drones outside the field on purpose.
- What was tuned and what was scored
- Nothing is learned, so there’s no training or test split. Every run is scored the same way, by spacing unevenness and coverage cost, and the tests check that the coverage cost never goes up from one step to the next.
- What kind of method it is
- It isn’t a trained model or a hand-tuned rule. Lloyd’s algorithm is fixed geometry: split the field into Voronoi cells, move each drone to the middle of its cell, and repeat until no drone moves more than 10 cm in a step.
- What it outputs
- Where each drone should go next, by drone, each step. The result shown here comes from running those steps until the swarm settles, then measuring how evenly the drones are spaced.
Even spacing in 90 of 90 simulated runs
Spacing unevenness is how much each drone’s distance to its nearest neighbour varies (standard deviation divided by mean). 0 is perfectly even.
| Settled into even spacing | 90 of 90 runs |
|---|---|
| Spacing unevenness | 0.46 at the start, 0.06 at the end (medians) |
| Drones starting outside the field | 0 crashes and 0 drones left outside, in 600 random starts |
| Tests | 28 unit and property tests |
What was hard
Concave fields
In an L-shaped field, a cell’s centroid can fall outside the cell. Then the drone goes to the nearest point of its own cell instead, so it stays inside and the coverage cost still never goes up.
Stray drones
Drones that start outside the field are pulled back in and kept apart. Testing random starts found a crash: two stray drones snapped to the same corner. Now they’re placed one at a time on free points.
Proving the cost never rises
The coverage cost is computed exactly from each cell’s polygon, not estimated by sampling, so a test can check it never goes up. I broke each key fix on purpose to make sure a test catches it.
Where it still falls short
It evens out spacing, not area: cells can still differ in size, the largest up to about 1.8× the smallest. Every result is from simulation, it hasn’t flown, and the pull request hasn’t merged.