The random exploration graph for optimal exploration of unknown environments

Abstract

The exploration of an unknown environment by a robot system is a well-studied problem in robotics; however, although many of the proposals made in this field represent efficient tools in terms of exploration paradigm, most of them are not efficient for time critical applications since the robot may visit the same place more than once during backtracking. In this way and considering these limitations, this article presents a novel approach called the random exploration graph, which addresses the problem of exploring unknown environments by building a graph structure created incrementally by the random choice of the free frontier in the observation range of the robot. In addition, the random exploration graph algorithm uses a new concept called “frontier control” introduced in this work, used to store nodes left behind in the graph structure that have not been fully explored and that will be used to guide the exploration process in an efficient way, when the algorithm needs to go back to previously visited areas to continue exploration. The frontier control concept next to the versatility of the graph structure used for the exploration process is the main contribution of this work.