BSA: a coverage algorithm

Abstract

This paper presents a new coverage online strategy BSA, backtracking spiral algorithm. Some service tasks involve the filling/sweeping of the surface that is accessible to the robot from its starting position. BSA is a structured way to perform this kind of procedures assuring the complete coverage of the surface regardless of the space topology. One of the main innovations of BSA is the use of spiral filling paths instead of zig-zag like paths, which makes it robust regardless of the robot initial orientation. In order to assure that the whole surface is covered, the algorithm is based in a backtracking procedure that makes the robot get back to unfulfilled detected regions. BSA is implemented with a set of simple rules. As the first ring of the spiral-filling path is accomplished nearby the obstacles, BSA indirectly contributes to improve the performance of a localisation system using obstacles as beacons. BSA has been validated in simulation.