Spanning-tree based coverage of continuous areas by a mobile robot

摘要

The paper considers the problem of covering a continuous planar area by a square-shaped tool attached to a mobile robot. Using a tool-based approximation of the work-area, we present an algorithm that covers every point of the approximate area. The algorithm, called spanning tree covering (STC), subdivides the work-area into disjoint cells corresponding to the square-shaped tool, then follows a spanning tree of the graph induced by the cells, while covering every point precisely once. We present and analyze three versions of the STC algorithm. The first version is an off-line algorithm that computes an optimal covering path in linear time O(N), where N is the number of cells comprising the approximate area. The second version is an online or sensor based algorithm, that completes an optimal covering path in time O(N), but requires O(N) memory for its implementation. The third version of STC is "ant"-like, where the robot may leave pheromone-like markers during the coverage process. The ant-like STC algorithm runs in time O(N) and requires only O(1) memory. We present simulation results of the three STC algorithms, demonstrating their effectiveness in cases where the tool size is significantly smaller than the work-area characteristic dimension.