基于人工势场法和启发式采样的最优路径收敛方法

作者：李伟; 金世俊^*

来源：计算机应用, 2021, 41(10): 2912-2918.

• 路径规划
• 快速搜索随机树算法
• 人工势场法
• 启发采样集合
• 启发式渐进最优快速搜索随机树算法

具有渐进最优性的快速搜索随机树(RRT*)算法在路径规划过程中确保了其概率完备性和渐进最优性,然而仍存在收敛速度慢且产生大而密集的采样空间等问题。为了加快算法的收敛速度,提出了一种基于人工势场法和启发集合采样来快速获取最优路径的方法。首先,利用人工势场法构建出一条由起点到目标点的初始路径;然后,以起点和目标点的位置和之间的距离以及初始路径的路径代价作为参数来构建初始启发采样集合;最后,限定在启发集合内进行采样,并且在算法进行的过程中调整启发采样集合的范围,进而加快路径收敛速度。仿真实验中,获取相同路径代价的路径时,所提人工势场结合启发式采样的方法为基础的结合人工势场法和启发采样策略的快速获取最优路径的RRT*(PI-RRT*)算法相较于RRT*算法,采样点数减少了约67%,算法运行时间平均缩短了约74.5%;相较于启发式RRT*(Informed-RRT*)算法,采样点数减少了约40～50%,算法运行时间平均缩短了约62.5%。所提出的最优路径收敛方法大量减少了冗余采样次数并缩短了算法运行时间,具有更高的算法效率,收敛到最优路径的速度更快。

• 单位
  东南大学