Improved Backtracking Algorithm for Efficient Sensor-Based Random Tree Exploration

Mobile robots need to explore novel environments to build useful maps for later navigation and motion planning. Sensor-based Random Tree, (SRT), technique had been used for exploration but it is problematic since the robot may visit the same place more than one time during backtracking process. In this paper, we propose a new heuristic algorithm to reduce this backtracking problem using the obtained map data. This algorithm is tested through computer simulations for several scenarios. The performance is evaluated in terms of exploration time, travelled distance and number of visited nodes. Since these classical evaluation metrics are correlated, we propose a new evaluation metric, that combines the total performance. The new algorithm is confirmed to reduce the exploration time of up to 30 %. The new evaluation metric is also shown to encapsulate the exploration performance and can be regarded as a much better representative of the performance that facilitate comparisons.