Abstract: 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.

Key words: path planning, asymptotically-optimal Rapid-exploring Random Tree star （RRT^*）, adaptive sampling, initial path, complex environment

摘要： 针对具有渐进最优性的快速扩展随机树（RRT^*）算法在面对高维、复杂环境时所表现出的寻路效率低、收敛速度缓慢的问题，在RRT^*的基础上，提出一种基于采样空间自调整的渐进最优快速扩展随机树（AS-RRT^*）无人机（UAV）航迹规划算法。该算法可以自适应调整采样空间，进而引导树更为高效地生长，而这些主要通过有偏采样、节点筛选和节点学习这三种策略来实现。首先，在采样空间中定义向光和背光区域来进行有偏采样，而向光和背光区域的概率权重由当前扩展失败率决定，从而保证算法在搜索初始航迹时同时具有探索性和方向性；然后，在完成初始航迹的搜索后，算法就开始周期性地筛选节点，高质量的节点作为学习样本来产生新的抽样分布，质量最低的节点在算法达到最大节点数量后被新节点替代。在多种不同类型的环境下进行了对比仿真实验，结果表明所提算法在一定程度上改善了采样算法固有的随机性，而且相较于传统的RRT^*算法，该算法在相同环境里使用了更少的寻路时间，在相同时间里生成了更低代价的航迹，且在三维空间里的改进更为明显。

关键词: 航迹规划, 渐进最优的快速扩展随机树, 自适应采样, 初始航迹, 复杂环境