View planning for mobile robots

Abstract

Two O(N log N) heuristic approaches for planning viewpoints in 2D known environments are described. Both are based on the generalized Delaunay triangulation of a polygon with holes. The main difference between them is the heuristic strategies used to merge the triangles to form the partitioning or covering star polygons. When the environment needs to be explored, an O(N/sup 2/ log N) heuristic scheme which successively selects the viewpoints and views for mobile robots is used. Upper bounds on the number of planned viewpoints and views for each scheme are estimated.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>