利用跳点搜索算法加速A*寻路

介绍广泛应用于游戏寻路中的标准A*算法,指出跳点搜索(JPS)算法使A*生成并扩展的节点数量很少,而且到达目标的速度很快.因为跳点搜索能够消除路径间的对称性,通过在直线和对角线方向上修剪节点来识别后继,在搜索时跳过了大量可能会添加到open列表和closed列表中的中间节点以及其他计算,这使搜索速度有了很大提升.在5个基准网格地图上测试A*+JPS对A*的相对加速比,实验结果表明:跳点搜索可将标准A*搜索的速度提高一个数量级甚至更多,并且速度收益的程度取决于基础网格地图的地貌,对于大的开放区域,跳点搜索更加高效.另外,跳点搜索对A*在节点扩展数量上的改进甚至比搜索时间的改进更加显著.无论从搜索时间还是从节点扩展数量上,A*+JPS都明显优于A*,利用跳点搜索算法可显著加速A*寻路.     

面向移动机器人快速全局路径规划的改进跳点搜索算法

针对传统全局路径规划算法计算量大,寻路时间过长等问题,为了进一步提高移动机器人综合作业能力,本文提出了一种基于跳点搜索算法的快速全局路径规划算法,旨在减少时间成本,以满足移动机器人在实际复杂环境中对智能性、高效性、安全性和可靠性的要求。首先通过“块”操作方法,在一次搜索中快速扫描底层网格中的一个区域,将跳点搜索算法的修剪规则一次应用于多个节点,减少搜寻跳点时所涉及的大部分迭代计算,并在采取“对角优先”方式的前提下,剔除仅具有改变方向的中间转折点,大量减少Openlist和Closedlist的不必要节点,减少计算量,提高路径规划的实时性。为了验证改进算法的有效性与可行性,分别在规则的网格地图、测试库基准地图及移动机器人Turtlebot2进行仿真实验验证,结果表明在生成相同路径的基础上,改进跳点搜索算法与A*算法相比扩展节点数目缩减了68.9%,搜索耗费时间降低了71.9%;与传统跳点搜索算法相比,扩展节点数目缩减了41.3%,搜索耗费时间降低了33.4%,能够满足移动机器人快速全局路径规划的要求。     

基于同步可视图构造和A~*算法的全局路径规划

为提高全局路径规划的效率,在路径搜索的过程中同步构造可视图,提出了1种新的算法。在搜索过程中,使用A~*算法确定待扩展的节点。根据节点状态,构造上一节点到当前节点或者当前节点到目标点的连线。如果该连线没有穿越障碍物,则将其添加到可视图中,否则将被穿越障碍物远离连线的2个顶点添加到待扩展列表中。仿真结果表明,与完整可视图+A~*算法、导向可视图(OVG)+A~*算法、简化可视图+A~*算法比较,该文算法在能够搜索到最优路径的前提下,降低了路径规划的耗时。     

一种面向非结构化环境的改进跳点搜索路径规划算法

为解决非结构化复杂场景下基于搜索的寻路算法中存在的计算时间长、路径非最优等问题,在跳点搜索(jump point search,JPS)算法的基础上,提出一种带权重的跳点搜索(weighted jump point search,WJPS)算法.WJPS算法改进了启发式函数,同时采用非传统的距离表达,最终实现了在保证全局路径最短的同时,降低了计算时间.为了验证WJPS算法的有效性,设计了多种非结构化复杂场景地图,对A?、JPS算法和WJPS算法在寻路时间、扩展点数和路径长度3方面进行了对比.实验结果显示,相比A?算法和JPS算法,WJPS算法在复杂环境中能保证生成路径是最短的,同时利用JPS跳点算法中寻找拓展点的策略,能够实现毫秒级别的规划,且算法效率能够满足智能体对路径规划层的要求.另外,WJPS算法采用微分平坦法对生成的路径点作曲线拟合,使智能体的运动轨迹更加平滑.     

基于改进A*算法的燃气微泄漏四足巡检机器人路径规划

针对四足机器人在城市燃气微泄漏巡检中路径规划的需求,提出了一种基于改进A*算法的四足机器人燃气巡检路径获取方法。首先,采用网格法构建了四足机器人的二维工作地图。然后改进A*算法的启发函数,引入了自适应调整策略,让搜索节点减少且路径更不易陷入局部最优。最后从路径长度、平均搜索时间、搜索节点个数三个性能方面进行评估,改进A*算法达到了预期效果。使用Matlab2016b作为仿真软件,仿真结果显示,改进A*算法完成了寻路任务。与经典A*算法相比,改进算法的平均搜索时间降低了52.13%,搜索节点个数减少了30.23%。该算法在尺寸200×200以下地图的路径规划中具有较高的搜索效率。     

基于混合SA算法的智能汽车全局路径规划

针对目前智能汽车路径规划存在A~*算法规划的路径精度高却搜索耗时长、搜索耗时短但精度差的矛盾问题,提出了一种既保证搜索效率又可提高路径精度的混合连接SA算法.在原有连接方式的基础上,提出了一种新型的连接方式和S算法,设计了混合SA算法的切换机制,确保了SA算法可获取保证搜索效率的次优路径.进行了路径规划单一地图仿真试验,验证了SA算法在不同的单一环境地图中,重复规划的路径具有一致性、耗时具有一定局限性;同时进行了路径规划普适性仿真试验,对比分析了混合连接SA算法与四连接A~*算法的各项性能指标.结果表明:在全局工况下,SA算法相比于四连接A~*算法,在保证搜索耗时优势的同时,提高了规划路径精度,尤其是在低百分比障碍物地图下,效果更为明显.     

A*算法与蚁群算法相结合的无人艇巡逻路径规划

针对无人艇海上巡逻路径规划问题,提出了一种A~*算法与蚁群算法相结合进行最短巡逻路径优化的方法.在传统A~*算法的八角度搜索基础上,设计了一种多角度A~*算法以获得更短的两点之间可行路径,并以A~*算法搜索结果构建任意两个巡逻点之间的最短路径网络.结合最短路径网络建立多点巡逻路径规划问题的目标函数,利用蚁群算法进行求解以获得全局最优的巡逻路径.针对巡逻路径转折角较大的问题,提出了一种平滑算法以获得更符合实际航行需求的平滑路径.仿真结果表明:该方法有效地去除了冗余节点,缩短了路径长度,提高了路径平滑度,规划出了一条更优的无人艇巡逻路径.     

一种改进工业自动导引车路径规划算法

为了解决当前工业自动导引车(automated guided vehicle,AGV)栅格地图下路径规划算法存在路径转弯较多、弯曲度较大、搜路时间较长且距离障碍物近等问题,基于A?算法提出了一种改进路径规划算法.首先,通过在全局地图中设置路径关键节点,生成关键点拓扑地图,并利用Floyd算法进行最短路径规划,输出路径节点集合;其次,利用A?算法对集合中相邻节点进行路径规划,并将生成的路径进行拼接;最后,通过引入贝塞尔曲线对拼接路径进行平滑处理,以获取全局路径.实验结果表明:本文算法规划的路径转弯更少、弯曲度更小、搜索时间更短且能完全避开障碍物行走,更符合工业AGV的应用环境.     

基于在线图修剪的网格地图寻路

跳点搜索算法(JPS)是网格地图上最先进的图形修剪技术,由Daniel Harabor在2011年开发。它是A*的变种,提高了A*在等价网格上寻路的速度,当考虑当前节点的孩子可能被添加到OPEN集合时候,跳点搜索算法则直接从当前节点跳跃到了远处可见的节点。本文给出了跳点搜索算法的两个规则,并通过实证分析,将跳点搜索算法与两个先进的搜索空间约化算法进行了对比。结果显示:跳点搜索算法相对于Swamps(保持最优性的修剪技术)来说有显著地改进;同样,相对于很多情况下性能上占优的HPA*(次优寻路算法)也具有优越性。     

基于打破对称性的快速寻路算法

基于Java实现了跳点搜索算法,给出了算法实现的过程.实验结果表明:跳点搜索算法找到了一条从起始节点到目标节点的最优路径,且能够有效地识别和消除网格地图上的路径对称性,大幅度减少了节点扩展的数量.对比A*、宽度优先搜索、最佳优先搜索和Dijkstra可知,在所求解的路径长度一致的情况下,跳点搜索在平均搜索时间上显著快于其他算法.因此,跳点搜索是快速、高效的.     

基于改进人工鱼群算法的机器人路径规划

为改进人工鱼群算法在路径规划中的寻优作用,利用改进视觉范围和拥挤度因子函数,提高鱼群算法在机器人路径规划中的寻优工作。在传统鱼群算法中,视觉范围是恒定不变的。视觉范围决定寻优的全局和局部工作,拥挤度因子对算法收敛性具有影响。同时,在传统鱼群算法中,每次都选取最优解来执行,在栅格环境中往往会导致全局最优和局部最优互扰,导致路径规划不合理,为此,利用改进视觉范围拥挤度因子,同时记录可行解,当存在鱼群找到目标点时,就记录下找到目标点的鱼群轨迹,形成路径规划的可行解,在可行解中,选取路径最短为最优,保证路径的规划的合理性。与传统鱼群算法对比,证实研究算法在路径规划中具有更好的寻优工作,通过MATLAB仿真实验,验证了算法的有效性和稳定性。     

基于改进蚁群算法与Morphin算法的机器人路径规划方法

 针对动态复杂环境下的机器人路径规划问题,建立栅格地图模型,研究一种改进蚁群算法与Morphin 算法相结合的动态路径规划方法。改进蚁群算法引入拐点参数评价路径优劣,并对路径进行拐角处理以及变更拐角处信息素更新机制,使规划的全局路径更加平滑;Morphin 算法则在机器人行走时,根据全局路径的局部环境实时规划局部路径,使机器人有效地躲避障碍物。仿真试验结果表明,该方法结合全局规划与局部规划的特点,能够使机器人沿着一条短而平滑的最优路径快速、安全地到达目标点。     

基于IAPF-ACO的工业机器人运动规划

针对蚁群算法运动规划收敛慢且精度不佳的问题,提出一种改进势场蚁群(improved artificial potential field ant colony optimization, IAPF-ACO)算法。斥力计算模型引入目标调节因子解决势场寻优不可达且易陷入局部最优问题。蚁群算法计算框架加入改进势场模型,即启发信息函数中增加势场信息因子。三维障碍物空间仿真规划表明：IAPF-ACO算法在离散环境与聚集环境规划路径质量较优、规划结果较为稳定。在MATLAB搭建工业机器人仿真模型,关节空间内对规划路径点平滑处理,避障仿真结果表明,工业机器人末端位移是一条安全、平滑的运动轨迹。     

求解路网最短路的快速算法

探讨了最短路算法在交通分配中的重要地位。在此基础上．比较了现有最短路算法的优缺点,同时提出了一种改进的矩阵迭代算法．并利用该算法对一简单路网进行了验证。     

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

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

“机器人”路径改进型单亲遗传算法规划及其仿真

在中国机器人大赛"机器人游中国"比赛项目的路径规划基础上,为克服遗传算法在有约束组合优化问题中计算效率不高的问题,提出了改进的单亲遗传算法.该算法在传统单亲遗传算法的计算步骤中,引入了交换算子、提前算子和修复算子,较大程度地提高了单亲遗传算法的搜索效率.Matlab仿真试验表明,改进的单亲遗传算法计算效率和路径规划能力得到大幅度提高.