We consider boundary coverage of a regular structure by a swarm of miniature robots, and compare a suite of three fully distributed
coordination algorithms experimentally. All algorithms rely on boundary coverage by reactive control, whereas coordination
of the robots high-level behavior is fundamentally different: random, self-organized, and deliberative with reactive elements.
The self-organized coordination algorithm was designed using macroscopic probabilistic models that lead to analytical expressions
for the algorithm’s mean performance. We contrast this approach with a provably complete, near optimal coverage algorithm,
which is due to its assumption (noise-less sensors and actuators) infeasible on a real miniature robotic platform, but is
considered to yield best-possible policies for an individual robot.
Experimental results with swarms of up to 30 robots show that self-organization significantly improves coverage performance
with increasing swarm size. We also observe that enforcing a provably complete policy on a miniature robot with limited hardware
capabilities is highly sub-optimal as there is a trade-off between coverage throughput and time spent for localization and
navigation.