EXPLORATION OF POLYGONAL ENVIRONMENTS USING RANGE DATA

Several robotic problems involve the systematic traversal of the envir onment, commonly referred to as exploration, We present a strategy for the exploration of unknown finite polygonal environments, using a poi nt robot with 1) no positional uncertainty and 2) an ideal range senso r that measures range in N uniformly distributed directions. The range data vector, obtained from the range sensor, corresponds to a sampled version of a visibility polygon. Visibility polygon edges that do not correspond to environmental edges are called jump edges and the explo ration strategy is based on the fact that jump edges indicate directio ns of possibly unexplored environmental regions. We describe condition s under which it is possible to identify jump edges in the range data. We also show how the exploration strategy can be used in a solution t o the terrain acquisition problem and describe conditions under which a solution is guaranteed within a finite number of measurements.