Complete and robust cooperative robot area coverage with limited range
Pooyan Fazli, Alireza Davoodi, Philippe Pasquier, Alan K. Mackworth · 2010
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 theConstrained Delaunay Triangulation(CDT).Multi-Prim'sis used to decompose the graph into a forest ofpartial spanning trees(PSTs). Each PST is then modified through a mechanism calledConstrained Spanning Tour(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.