基于自适应控制采样的RRT^(*)足路径规划算法研究

Research of RRT^(*)Path Planning Algorithm Based on Adaptive Control Sampling

针对传统渐进最优快速随机搜索树(Rapidly Exploring Random Tree Star,RRT^(*))算法在无人车全局路径规划时,由于初始路径生成方式基于随机概率,导致目的性较差,使得初始路径的生成时间过长;在复杂环境下,算法的采样区域过大,增加了额外计算量,导致算法计算速度较慢的问题,提出了一种基于贪心策略(Greedy Algorithm,GA)和自适应控制采样范围的改进的RRT^(*)算法。在初始路径生成时引入GA,缩短初次路径生成所需的时间,从而缩短算法整体所需的时间;寻到目标点生成首次路径后,加入决策条件限制,将采样点限制在生成树的附近,减少算法的无关计算量。仿真试验结果证明,改进后的算法生成首条路径速度快了约169%,有限次采样后路径缩短了约10%,整体所需时间减少约13%。所提出算法加快了路径生成的速度,减少了寻找目标所需的时间,为后续同类算法的改进提供参考。

When the traditional Rapidly Exploring Random Tree Star(RRT^(*))algorithm is used for the overall path planning of unmanned vehicles,the generation time for the initial path can be too long due to the poor purposefulness given by the generation method of the initial path based on random probability.Meanwhile,in the complex environment,the additional calculated amount can be also added because of the large algorithm sampling area,resulting in the low calculation speed of the algorithm.Therefore,an improved RRT^(*)algorithm based on Greedy Algorithm(GA)and adaptive control of the sampling range is proposed.The GA is introduced in the initial path generation to shorten the time required for the initial path generation,thus shortening the overall time required by the algorithm;and after finding the target point to generate the first path,a decision condition constraint is added to limit the sampling points to the vicinity of the spanning tree to reduce the extraneous calculated amount of the algorithm.By the simulation experiments,the experimental results show that the improved algorithm generates the first path about 169%faster,shortening the path by about 10%after the finite sampling and reducing the overall time required by about 13%.The path generation is accelerated by the proposed algorithm,with the time required to find the target also reduced,providing reference for the subsequent improvements of similar algorithms.