Exploration of polygonal environments

Sammanfattning:

Several robotic problems involve the systematic traversal of environments, commonly called exploration. This thesis presents a strategy for exploration of finite polygonal environments, assuming a point robot that has 1) no positional uncertainty and 2) an ideal range sensor that measures range in N uniformly distributed directions in the plane. The range data vector, obtained from the range sensor, corresponds to a sampled version of the visibility polygon. Edges of the visibility polygon that do not correspond to environmental edges are called jump edges and the exploration strategy is based on the fact that jump edges indicate directions of possibly unexplored regions.This thesis describes a) the conditions under which it is possible to detect environmental edges in the range data, b) how the exploration strategy can be used in an exploration algorithm, and c) the conditions under which the exploration algorithm is guaranteed to terminate within a finite number of measurements.