An efficient terrain acquisition algorithm for a mobile robot

A terrain acquisition algorithm for an autonomous mobile robot to learn and model its surrounding terrain efficiently with respect to travel distance, and sensing operations is presented. It is shown that this algorithm enables a mobile robot to visit relatively few obstacle vertices to construct a map of a planar terrain occupied by polygonal obstacles. According to this algorithm, a mobile robot travels to a vertex of the obstacles only when additional terrain information can be obtained from there. The decision to move to a vertex is thus based on whether any incident edge of a vertex is missing or occluded