ROBOT NAVIGATION IN UNKNOWN GENERALIZED POLYGONAL TERRAINS USING VISION SENSORS

This paper considers the problem of navigating a point robot in an unk nown two-dimensional terrain populated by disjoint generalized polygon al obstacles. A generalized polygon consists of a connected sequence o f circular arcs and straight-line segments. The terrain model is not k nown a priori, but the robot is equipped with a vision sensor. A discr ete vision sensor detects all visible (from a single position) portion s of the obstacle boundaries in a single scan operation. The navigatio n problem deals with moving the robot through the terrain from a sourc e position to a destination position, and the terrain model acquisitio n problem deals with autonomously building a model of the terrain. A c omplete solution to either problem is shown to require an infinite num ber of scan operations in cusp regions formed by a pair of convex and concave obstacle edges. Either problem is considered solved with a pre cision epsilon if the points that have not been scanned are those in a cusp region with a clearance less than epsilon from two obstacle edge s. Three methods are proposed to solve both problems with a precision epsilon based on extensions of the generalized visibility graph, the g eneralized Voronoi diagram, and the trapezoidal decomposition. Then si mplified versions of these structures are proposed to exactly solve th e navigation and terrain model acquisition problems using a continuous vision sensor that detects all visible obstacle boundaries as the rob ot navigates along a path.