Sensor coverage robot swarms using local sensing without metric information

Abstract

We consider the problem of deploying a swarm of mobile robots into an unknown environment for attaining complete sensor coverage of the environment. The robots have limited and noisy sensing capabilities and no metric or global information available to them. Using tools from algebraic topology, we formally describe the sensor coverage as a simplicial complex, deploy robots through the complex using bearing-based local controllers, and attain coverage while identifying and removing sensor redundancies. Despite the highly limited sensing capabilities and complete lack of global localization and metric information, we demonstrate that the proposed algorithm is complete, always terminates in a finite-sized environment, is guaranteed to attain complete coverage and is robust to sensor failures. The algorithm presented in this paper was demonstrated through simulation and proves to effectively cover and explore unknown indoor environments.