Abtin Aryanpour

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.

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.

One simulated run: 10 drones on a 200 m L-shaped field, starting bunched within 15 m of a launch point. Each shaded area is one drone’s cell, the lines are the paths flown, and the grey dots are where they started. Coverage cost is the mean squared distance from a point in the field to its nearest drone.

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.

All simulated, on the test fields described above.
Settled into even spacing90 of 90 runs
Spacing unevenness0.46 at the start, 0.06 at the end (medians)
Drones starting outside the field0 crashes and 0 drones left outside, in 600 random starts
Tests28 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.