Pseudo Spanning Tree-based Complete and Competitive Robot Coverage using Virtual Nodes

In this paper, we propose a new robot coverage algorithm using approximate cellular decomposition. The algorithm uses spanning tree on adjacency graph formed by the decomposed cells. We introduce a concept of a virtual node corresponding to a partially occupied cell, leading to a pseudo spanning tree. Unlike the existing approximate cellular decomposition based coverage algorithms reported in the literature, the proposed algorithm ensures complete coverage of even partially occupied cells, with minimal (or no) overlapping/retracing of the path. The algorithm is illustrated using examples comparing its coverage performance with that of the STC and Competitive-STC algorithms, two spanning tree based coverage algorithms using approximate cellular decomposition reported in the literature.