Some Performance Bounds of Strategies for Graph Exploration

Exploration of unknown environments is relevant for many robotics applications, like map building and coverage. Several works in the literature have proposed exploration strategies that drive a mobile robot to greedily choose where to go next in order to incrementally map an initially unknown environment. In this paper, we theoretically study the worst and average traveled distance required to explore graphbased environments by some exploration strategies that consider distance and information gain in selecting the next destination location.