融合插点和跳跃点改进A*算法的路径规划

为了解决传统A*算法在路径规划中存在的一些问题,提出了一种融合插值点跳跃搜索路径算法来改进A*算法。在对栅格环境图中具有特殊意义的多组数据进行预处理后,通过起始点和目标点确定目标函数,并搜索出一条最优路径。利用MATLAB软件平台对8组规格不同的环境地图进行了路径规划仿真。实验结果表明:改进后的算法可以减少计算时间、搜索节点数量、内存占用和搜索路径长度。可见改进后的算法在搜寻最佳路径方面的效率更高。

融合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*算法提高路径规划的安全性和效率性效果越明显。

基于密度分类的JPS+移动机器人全局路径规划算法

针对传统全局路径规划中扩展节点多、寻路时间长等问题,提出一种基于JPS+(jump point search plus)算法的全局路径规划算法,旨在提高机器人在复杂环境的智能性、高效性的要求。首先引入了一种基于密度的判断障碍物角点规则,实现对于主要跳点的识别数目,减少搜索路径过程中的可扩展节点,同时在路径求解过程中对目标跳点的判定规则进行了修改,最终实现了减少计算量、缩短计算时长的目标。为验证所提改进型JPS+算法的有效性,将A、JPS+算法在不同类型地图中与改进型JPS+算法进行了比较。仿真结果表明,改进型JPS+算法与A算法相比,在路径长度、寻路时间和扩展节点数量上都有明显改进;在生成相同路径的基础上,与传统JPS+算法相比,在障碍物占比33.25%的地图中搜索时间降低了7.58%,节点扩展数量减少了9.38%,能够满足移动机器人快速全局路径规划的要求。