ROBOT NAVIGATION IN UNKNOWN TERRAINS OF CONVEX POLYGONAL OBSTACLES USING LEARNED VISIBILITY GRAPHS

The problem of navigating an autonomous mobile robot through an unexplored terrain of obstacles is the focus of this paper. The case when the obstacles are 'known' has been extensively studied in literature. The process of robot navigation in completely unexplored terrains involves both learning the information about the obstacle terrain and path planning. We present an algorithm to navigate a point robot in an unexplored terrain that is arbitrarily populated with disjoint convex polygonal obstacles in the plane. The navigation process is constituted by a number of traversals; each traversal is from an arbitrary source point to an arbitrary destination point. Initially, the terrain is explored using a sensor and the paths of traversal made may be sub-optimal. The visibility graph that models the obstacle terrain is incrementally constructed by integrating the information about the paths traversed so far. At any stage of learning, the partially learnt terrain model is represented as a learned visibility graph, and it is updated after each traversal. The proposed algorithm is proven to yield a convergent solution to each path of traversal. It is also shown that the learned visibility graph converges to the visibility graph with probability one, when the source and destination points are chosen randomly. Ultimately, the availability of the complete visibility graph enables the robot to plan globally optimal paths, and also obviates the further usage of sensors.