基于分区思想的两阶段RRT*算法

作者：马智焕; 胡立坤^*; 陶兴华; 刘月洋; 胡正南

来源：国外电子测量技术, 2023, 42(08): 40-46.

DOI：10.19652/j.cnki.femt.2304972

• *" name="keyword">RRT*
• 路径规划
• 分区检索
• 节点拒绝
• 自适应采样

针对RRT*算法采样效率低、搜索时间长等问题，提出了一种基于分区思想的两阶段RRT*算法(TP-RRT*)。在探索阶段，利用自适应采样限制采样点的随机性，根据平行四边形法则合成新的矢量节点，既提升了采样点的方向性，又增强了算法对地图的搜索能力。在寻找最近点时，遍历整个随机树的过程存在计算量大、耗时长的问题，因此采用分区存储和检索的方法提升搜索的效率，同时限定分区中的节点数量，避免同一区域过度搜索。并在此基础上，生成一个新的父节点来改进原始算法中的重选父节点环节，进一步减少路径长度。最终在优化阶段时，通过对全局区域进行随机采样，并构造评估函数，得到可以改善路径的节点。仿真实验结果表明，改进算法与原算法在3种不同地图下，路径长度均减少了10%以上、时间均缩短了61%以上、节点数量均降低了75%以上；TP-RRT*算法在路径规划的长度、时间、节点数等方面都优于Q-RRT*和informed-RRT*。

• 单位
  南宁学院; 广西大学