TR-86: Robot Navigation in Unknown Terrains Using Learned Visiblity Graphs. Part I: The Disjoint Convex Obstacles Case

Abstract

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. In this paper, we consider completely unexplored obstacle terrain. In this case, the process of navigation involves both learning the information about the obstacle terrain and path planning. We present an algorithm to navigate a 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. The proposed algorithm is proven to yield a convergent solution to each path of traversal. Initially, the terrain is explored using a rather primitive 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 informa­tion about the paths traversed so far. At any stage of learning, the par­tially learnt terrain model is represented as a learned visibility graph, and it is updated after each traversal. It is proven that the learned visibility graph converges to the visibility graph with probability one, when the source and destination points are chosen randomly. Ultimately, the avai­lability of the complete visibility graph enables the robot to plan globally optimal paths, and also obiviates the further usage of sensors.