Spatial Coverage Without Computation

Abstract

We study the problem of controlling a swarm of anonymous, mobile robots to cooperatively cover an unknown two-dimensional space. The novelty of our proposed solution is that it is applicable to extremely simple robots that lack run-time computation or storage. The solution requires only a single bit of information per robot-whether or not another robot is present in its line of sight. Computer simulations show that our deterministic controller, which was obtained through off-line optimization, achieves around 71-76% coverage in a test scenario with no robot redundancy, which corresponds to a 26-39% reduction of the area that is not covered, when compared to an optimized random walk. A moderately lower level of performance was observed in 20 experimental trials with 25 physical e-puck robots. Moreover, we demonstrate that the same controller can be used in environments of different dimensions and even to navigate a maze. The controller provides a baseline against which one can quantify the performance improvements that more advanced and expensive techniques may offer. Moreover, due to its simplicity, it could potentially be implemented on swarms of sub-millimeter-sized robots. This would pave the way for new applications in micro-medicine.