Robot navigation in an unexplored terrain

Abstract Navigation planning is one of the most vital aspects of an autonomous mobile robot. Robot navigation for completely known terrain has been solved in many cases. Comparatively less research dealing with robot navigation in unexplored obstacle terrain has been reported in the literature. In recent times this problem has been addressed by adding learning capability to a robot. The robot explores terrain using sensors as it navigates, and builds a terrain model in an incremental manner. In this article we present concurrent algorithms for robot navigation in unexplored terrain. The performance of the concurrent algorithms is analyzed in terms of planning time, travel time, scanning time, and update time. The analysis reveals the need for an efficient data structure to store an obstacle terrain model in order to reduce traversal time, and also to incorporate learning. A modified adjacency list is proposed as a data structure for storing a spatial graph that represents an obstacle terrain. The time complexities of the algorithms that access, maintain, and update the spatial graph are estimated, and the effectiveness of the implementation is illustrated.