期刊
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
卷 24, 期 3, 页码 197-224出版社
ELSEVIER
DOI: 10.1016/S0925-7721(02)00110-4
关键词
mobile robot covering; competitive covering; sensor based covering; on-line spanning tree construction
We describe in this paper two on-line algorithms for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithms, called Spanning Tree Covering (STC) algorithms, incrementally subdivide the planar area into a grid of D-size cells, while following a spanning tree of a grid graph whose nodes are 2D-size cells. The two STC algorithms cover general planar grids. The first, Spiral-STC, employs uniform weights on the grid-graph edges and generates spiral-like covering patterns. The second, ScanSTC, assigns lower weights to edges aligned with a particular direction and generates scan-like covering patterns along this direction. Both algorithms cover any planar grid using a path whose length is at most (n + m)D, where n is the total number of D-size cells and m less than or equal to n is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also demonstrate that any on-line coverage algorithm generates a covering path whose length is at least (2-epsilon)l(opt) in worst case, where l(opt) is the length of the optimal off-line covering path. Since (n + m)D less than or equal to 2l(opt), the bound is tight and the STC algorithms are worst-case optimal. Moreover, in practical environments m much less than n, and the STC algorithms generate close-to-optimal covering paths in such environments. (C) 2002 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据