Swarm Coverage Control (Voronoi/Lloyd)

Swarm Size

Robots 12

Coverage Priority

Control Gain

Convergence rate k 1.4

Live State

Coverage cost H

—

Mean drift to centroid

—

Simulated time

0.0 s

How it works

Each robot i owns the region of space closer to it than to any other robot — its Voronoi cell V_i. Together the cells exactly partition the domain. The quality of a sensing deployment is measured by a coverage cost that penalises distance from every point q to its nearest robot, weighted by an importance/density function φ(q):

H(p₁..pₙ) = Σᵢ ∫_Vᵢ ‖q − pᵢ‖² φ(q) dq

For fixed robot positions, this cost is minimised by the ordinary nearest-neighbour Voronoi partition. Within a cell, it is minimised when the robot sits exactly at the cell's density-weighted centroid:

cᵢ = ∫_Vᵢ q φ(q) dq  /  ∫_Vᵢ φ(q) dq

Driving each robot toward its own cell centroid with the simple proportional law

dpᵢ/dt = k (cᵢ − pᵢ)

provably decreases H every step (it is a gradient descent on H), so the swarm converges to a centroidal Voronoi tessellation — a locally optimal spread where sensing effort matches importance. This is Lloyd's algorithm applied to distributed multi-robot coverage (Cortés, Martínez, Karataş & Bullo, 2004), the standard method real surveillance-drone fleets, environmental-monitoring buoys and warehouse sensor swarms use to spread out without any central planner — each robot only needs to know its own cell.

Robots slider — more agents subdivide the domain into smaller cells and lower the achievable cost H.
Coverage priority — switches φ(q): flat (uniform), one Gaussian "hot zone", or two — cells automatically shrink around high-importance regions.
Convergence rate k — the proportional gain in the control law; higher k reacts faster but can overshoot on a coarse grid.
The thin lines from each robot point at its live target centroid — when a line shrinks to nothing, that robot has converged.

Robot / cell colour Target centroid

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.

Swarm Coverage Control — Voronoi Partitioning & Lloyd's Algorithm