融合JPS和改进A^(*)算法的移动机器人路径规划

针对传统A^(*)算法在场景较大的栅格地图路径规划时,很多冗余节点的遍历导致寻路算法内存消耗大、计算速度慢等问题,提出了一种对A^(*)算法的改进策略。首先,改进启发函数的具体计算方式,利用切比雪夫距离替代欧氏距离使启发式函数精确地等于实际最佳路径,减少A^(*)节点的拓展数量;其次,使用跳点搜索(JPS)策略筛选出跳点添加到OpenList和ClosedList代替A^(*)算法中大量不必要的邻节点,通过跳点实现较长距离的跳跃,从而减少内存占用以及对节点的评估,直到生成最终路径。为了验证A^(*)算法改进后的效果,在五种尺寸的二维栅格地图中进行仿真测试,结果表明,改进后的A^(*)算法减少了大量寻路过程评估的节点,提高了寻路速度,并且随着地图尺寸的增加,改进后的A^(*)算法能将寻路速度提高一个数量级以上。最后,将改进后的算法应用在移动机器人路径规划器上进行实验,在同一规划任务下,JPS策略下改进的A^(*)算法较传统A^(*)算法,路径搜索耗费时间减少了92.2%,拓展的节点减少了97.37%,能够满足大场景下移动机器人快速路径规划的要求。

基于改进JPS和A*算法的组合路径规划

针对跳点搜索(JPS)算法预处理规则不安全、大规模地图中存在跳点多且混乱的问题,设计了一种基于改进JPS和A*算法的组合规划算法。首先,改进了JPS算法的跳点筛选规则且对冗余的中间跳点进行删减,通过引入安全性评估模型保证规划路径的安全性;然后,根据路径搜索环境的复杂度设计了一种跳点阈值函数,在此基础上将改进JPS算法与A*算法相结合构成组合路径规划算法,该算法根据跳点的数量对路径搜索中后继节点拓展策略进行不同的选择,由此减少计算节点的数量并达到提高路径全局规划效率的目的;最后,仿真实验结果表明,当地图规模越大或非对称路径越多时,本文所设计的改进JPS和A*算法提高路径规划的安全性和效率性效果越明显。