The terrain acquisition problem deals with the acquisition of the complete obstacle terrain model by a mobile robot placed in an unexplored terrain. This is a precursory problem to many well-known find-path and related problems which assume the availability of the complete terrain model. In this paper, we present a method for terrain acquisition by a finite-sized robot operating in plane populated by an unknown (but, finite) number of polygonal obstacles; each obstacle is arbitrarily located and has unknown (but, finite) number of vertices. The robot progressively explores newer vertices of the obstacles using sensor equipment. We show that the complete terrain model will be built by the robot in a finite time. We also show that at any point of time the partially acquired terrain suffices for the navigation of the robot during the exploration. Hence we conclude that the navigation techniques for known terrains can be applied for the robot navigation during exploration.

Navigation planning is one of the most vital aspects of an autonomous mobile robot. The problem of navigation in a completely known obstacle terrain is solved in many cases. Comparatively less number of research results are reported in literature about robot navigation in a completely unknown obstacle terrain. In recent times, this problem is solved by imparting the learning capability to the robot. The robot explores the obstacles terrain using sensors and incrementally builds the terrain model. As the robot keeps navigating, the terrain model becomes more learned and the usage of sensors is reduced. The navigation paths are computed by making use of the existing terrain model. The navigation paths gradually approach global optimality as the learning proceeds. In this paper, we present concurrent algorithms for an autonomous robot navigation in an unexplored terrain. These concurrent algorithms are proven to be free from deadlocks and starvation. The performance of the concurrent algorithms is analyzed in terms of the planning time, travel time, scanning time, and update time. The analysis reveals the need for an efficient data structure for the obstacle terrain in order to reduce the navigation time of the robot, and also to incorporate learning. The modified adjacency list is proposed as a data structure for the spatial graph that represents the obstacle terrain. The time complexities of various algorithms that access, maintain, and update the spatial graph are estimated, and the effectiveness of the the implementation is illustrated.