Path Planning of Mobile Robots Based on Improved Bi-RRT Algorithm

摘要

Bidirectional Fast Expanding Random Tree (Bi-RRT) algorithm has the problems of long search time and low sampling efficiency in path planning in complex environment due to the randomness of sampling points. Therefore, an improved Bi-RRT path planning algorithm for mobile robots was proposed;The algorithm introduces a heuristic search strategy, takes the starting point and the ending point of the robot as the center, constructs a two-dimensional Gaussian distribution function, and uses this probability density function to constrain the generation of sampling points, so that the spatial sampling points closer to the target point have a higher probability of occurrence, while retaining some uniformly distributed sampling points. In this way, the sampling process can not only make use of the location information of the target point but also ensure the probabilistic completeness of the algorithm; With the guidance of heuristic sampling points designed by the algorithm, two random trees can grow rapidly toward the target area, which reduces the blindness of the search and improves the efficiency of the search; Simulation results: Compared with the basic BI-RRT algorithm, the planning time of the improved algorithm is shortened by 43.9% in complex environment, the number of extended nodes is reduced by 41.4%, and the path length is optimized by 8.1%. The influence of the ratio of Gaussian distribution sampling points to the total number of sampling points on the performance of the algorithm is analyzed.