Finding a High-Quality Initial Solution for the RRTs Algorithms in 2D Environments

Abstract

Summary In this paper, we propose a bioinspired path planning algorithm for finding a high-quality initial solution based on the pipeline of the Rapidly exploring Random Tree (RRT) method by modifying the sampling process. The modification mainly includes controlling the sampling space and using the probabilistic sampling with the two-dimensional Gaussian mixture model. Inspired by the tropism of plants, we use a Gaussian mixture model to imitate the tree’s growth in nature. In a 2D environment, we can get an approximate moving point’s probabilistic distribution, and the initial path can be found much quickly guided by the probabilistic heuristic. At the same time, only a small number of nodes are generated, which can reduce the memory usage. As a meta-algorithm, it can be applicable to other RRT methods and the performance of underlying algorithm is improved dramatically. We also prove that the probabilistic completeness and the asymptotic optimality depend on the original algorithm (other RRTs). We demonstrate the application of our algorithm in different simulated 2D environments. On these scenarios, our algorithm outperforms the RRT and the RRT* methods on finding the initial solution. When embedded into post-processing algorithms like the Informed RRT*, it also promotes the convergence speed and saves the memory usage.