Concurrent Algorithms for Autonomous Robot Navigation in an Unexplored Terrain

摘要

Navigation planning is one of the vital aspects of any autonomous mobile robot. In this paper, we present concurrent algorithms for an autonomous robot navigation system that does not require a pre-learned obstacle terrain model. The terrain model is gradually built by integrating the information from multiple journeys. The available information is used to the maximum extent in navigation planning, and global optimality is gradually achieved. It is shown that these concurrent algorithms are 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. A modified adjacency list is proposed as the data structure for the spatial graph that represents an obstacle terrain. The time complexities of various algorithms that access, maintain, and update the spatial graph are estimated, and the effectiveness of the implementation is illustrated. (ERA citation 11:025952)