Obstacle-guided informed planning towards robot navigation in cluttered environments
Zehui Meng, Hailong Qin, Hao Sun, Xiaotong T. Shen, Marcelo H. Ang · 2017
Informed sampling, a sampling method that focuses the search by sampling the subset of states that potentially improve the current solution, has been adopted in path-planning algorithms like Informed RRT* [1] and its successor, Batch Informed Trees (BIT*) [2], for speeding up the convergence and improving the quality of solution. In this paper, we consider the problem of path planning in cluttered environments containing narrow passages. We build as an extension to BIT* our obstacle-guided sampling and biasing strategy. With a neighbourhood sampling step, we embed obstacle-based Gaussian sampling in the underlying uniform sampling, which gives rise to the sample density in difficult-to-sample homotopy classes. The local obstacle information is implicitly extracted with simple heuristics to recognize “navigators” that belong to narrow passages, and to inform the planner for subsequent sample biasing, so that the convergence of the solution towards optimum can be locally accelerated leveraging obstacle information. Our strategy combines the exploratory advantage of uniform informed sampling and the exploitative feature of obstacle-based Gaussian sampling, while retaining the asymptotic sample coverage of the free space to search for the global optimal solution. We apply such customization of the BIT* algorithm to robot navigation path planning instances and demonstrate hte improved planning efficiency in 2D and 3D cluttered environments with narrow passages.