Robot navigation in unknown generalized polygonal terrains using a discrete scan sensor

Consideration is given to the navigation and terrain model acquisition problems in unknown two-dimensional terrains populated by disjoint obstacles whose boundaries are connected sequences of circular arcs and straight line segments. A general result is given that shows that a solution for the navigation problem (or terrain model acquisition problem) requires an infinite number of scan operations in critical regions around the obstacle vertices at which a convex arc meets a concave arc. Either problem is considered to be solved with a precision ε if a point p in a critical region within a distance of ε from each of the arcs of the region is considered a part of fictitious obstacle. Two navigational structures are proposed for generalized polygonal terrains that yield solutions to both problems with a precision ε.