Sample-based Frontier-Block Detection for Autonomous Robot Exploration

Abstract

Autonomous exploration requires a robot to find frontiers as quickly as possible. The rapidly-exploring random tree (RRT) in the motion planning field has been widely adopted recently. However, the classical RRT and its variant algorithms are still relatively aimless and inefficient for the reason that there are lots of repeated useless sampling operations and the process of finding the nearest point costs too much time. So a sample-based frontier-block detection method (SFBD) is proposed to avoid directly searching for the nearest point from a set with a large number of points and SFBD uses the block structure to record collision thus reducing useless sampling. Then, SFBD uses an improved block operation, which can greatly reduce the counts each block is operated. In order to demonstrate that SFBD does not depend on local tree excessively, only global RRT and two trees are respectively used in two simulation environments. The experimental results indicate that SFBD can more efficiently complete the exploration tasks comparing to other algorithms.