On Multi-Robot Area Coverage

Abstract

This paper presents an approach allowing a team of robots each with limited visibility to cover an area in the presence of different types of static obstacles. We introduce Reduced-CDT, an environment representation method based on Constrained Delaunay Triangulation. A new graph segmentation method called Multi-Prim’s is used to decompose the Reduced-CDT and construct a forest of partial spanning trees (PSTs). Each PST is then modified through a mechanism called the Constrained Spanning Tour (CST) to build a cycle which is assigned to an explorer robot. Subsequently, robots start navigating the cycles and consequently cover the whole area. The proposed approach is guaranteed to be complete and robust. 1.