基于改进Bi-RRT的移动机器人路径规划算法

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

摘要:

双向快速扩展随机树(Bi-RRT)算法因采样点的随机性导致在复杂环境中的路径规划存在搜索时间长、采样效率低等问题，为此提出了一种改进Bi-RRT的移动机器人路径规划算法。算法引入启发式搜索策略，分别以机器人的起点和终点为中心，构造了二维高斯分布函数，并用该概率密度函数约束采样点的生成，使得越接近目标点的空间采样点出现概率越大，同时保留部分均匀分布的采样点，这样采样过程既可以利用目标点的位置信息又保证了算法的概率完备性。通过算法设计的启发式采样点的引导，两棵随机树可以快速向着目标区域生长，降低了搜索的盲目性，提高了搜索的效率。仿真结果：相比于基本Bi-RRT算法，改进算法在复杂环境下规划时间缩短了43.9%，扩展节点数目减少了41.4%，路径长度优化了8.1%，并分析了高斯分布采样点占采样点总数的比值对算法性能的影响。

Abstract:

Because of the randomness of the sampling points, the bidirectional rapidly-exploring random tree algorithm (Bi-RRT) has long search time and low sampling efficiency in path planning in complex environments. For this reason, an improved Bi-RRT Path planning algorithm is proposed. The algorithm introduces a heuristic search strategy to construct a two-dimensional Gaussian distribution density function with the start and end points of the robot as the center, and use this function to constrain the generation of sampling points, so that the closer the target point is, the greater the probability of occurrence of the spatial sampling point. At the same time, some uniformly distributed sampling points are retained, so that the sampling process can not only use the location information of the target point, but also ensure the completeness of the probability. Guided by the heuristic sampling points designed by the algorithm, two random trees can quickly grow toward the target area, thereby reducing the blindness of the search and improving the efficiency of the search. The simulation results : compared with the basic Bi-RRT algorithm, the planning time of the improved algorithm in complex environments is shortened by 43.9%, the number of extended nodes is reduced by 41.4%, and the path length is optimized by 8.1%. Finally, 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.