复杂环境下基于采样空间自调整的航迹规划算法

针对具有渐进最优性的快速扩展随机树(RRT*)算法在面对高维、复杂环境时所表现出的寻路效率低、收敛速度缓慢的问题,在RRT*的基础上,提出一种基于采样空间自调整的渐进最优快速扩展随机树(AS-RRT*)无人机(UAV)航迹规划算法.该算法可以自适应调整采样空间,进而引导树更为高效地生长,而这些主要通过有偏采样、节点筛选...

Path planning algorithm in complex environment using self-adjusting sampling space

To overcome low pathfinding efficiency and slow convergence speed of Rapid-exploring Random Tree star(RRT^*) in high-dimensional and complex environment, an Unmanned Aerial Vehicle(UAV) path planning algorithm with self-adjusting sampling space based on RRT^* named Adjust Sampling space-RRT^*(AS-RRT^*) was proposed. In this algorithm, by adjusting the sampling space adaptively, the tree was guided to grow more efficiently, which was realized through three strategies including:biased sampling, node selection and node learning. Firstly, the light and dark areas in the sampling space were defined to performing biased sampling, and the probability weights of the light and dark areas were determined by the current expansion failure rate, so as to ensure that the algorithm was both exploratory and directional when searching for the initial path. Then, once the initial path was found,the nodes were periodically filter,and the high-quality nodes were used as learning samples to generate the new sampling distribution, the lowest-quality nodes were replaced by new nodes after the algorithm reaching the maximum number of nodes. Simulation experiments for comparison were conducted in multiple types of environments. The results show that the proposed algorithm improves the inherent randomness of the sampling algorithm to a certain extent, and compared with the traditional RRT^* algorithms, it has less pathfinding time used in the same environment, lower cost path generated in the same time, and the improvements are more obvious in three-dimensional space.