Complete and robust cooperative robot area coverage with limited range

Abstract

We address the problem of multi-robot area coverage and present a new approach in the case where the map of the area and its static obstacles are known and the robots have a limited visibility range. The proposed method starts by locating a set of static guards on the map of the target area and then builds a graph called Reduced-CDT, a new environment representation method based on the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Constrained Delaunay Triangulation</i> (CDT). <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Multi-Prim's</i> is used to decompose the graph into a forest of <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">partial spanning trees</i> (PSTs). Each PST is then modified through a mechanism called <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Constrained Spanning Tour</i> (CST) to build a cycle which is then assigned to an individual robot. Subsequently, robots start navigating the cycles and consequently cover the whole area. We show that the proposed approach is complete and robust with respect to robot failure.