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

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

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

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

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

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

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

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

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

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

基于混合蛙跳算法的层次化群体路径规划

在复杂的群体运动场景中,传统路径规划方法具有计算量大、耗时长、效果生硬等缺点。为此笔者提出了一种层次化路径规划方法,将群体路径规划问题分为两个层次,在底层使用A*算法进行全局路径搜索,规划出一条从起始点到目标点的全局最优路径,使群智能算法进行上层局部路径规划时只考虑上层粒子间的碰撞;在上层采用混合蛙跳算法并结合多线程技术进行个体路径的动态规划。仿真实验结果表明：所提出的方法有效降低了群体路径规划中的算法复杂度和时间复杂度,在较为复杂场景下能够逼真和高效地进行群体运动仿真。     

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

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

复杂环境下六自由度机械臂路径规划的Biased-RRT修正算法

为解决复杂环境下六自由度机械臂的路径规划问题,提出一种基于采样规则目标导向设计、父节点重选的修正算法。该算法在原目标偏置策略的基础上对随机采样点的选取规则进行重新设定,以引导算法搜索树在尽可能向目标区域扩展的同时有效避开复杂障碍物。在节点扩展方面,依据新节点距离目标点的远近采用变步长扩展方式,即在距离远时选用大步长,加快搜索树扩展;进入目标区域后选用小步长,防止节点扩展陷入局部死循环。在路径优化方面,所提算法通过引入基于路径代价最小的重选父节点操作及多余路径节点剔除操作,来使规划出的路径相对优化。最后,利用三次样条插值技术为机械臂各关节规划出一条光滑、连续且无障的运动曲线。仿真结果表明,所提算法可有效缩短路径规划时间、减少路径长度,较好地完成了复杂环境下六自由度机械臂的预期路径规划任务。     

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

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

基于改进JPS算法的电影群体动画全局路径规划

目前,电影场景中的群体动画路径一般是静态设置的,以镜头拍摄效果为主,因而存在路径不连续、动画制作效率低等问题.提出一种新的电影群体动画全局路径规划算法,在跳点搜索(jump-point search, JPS)算法的基础上引入Bezier曲线和群体密度信息进行路径编辑和优化.首先,采用JPS算法自动生成群体运动路径,得到可编辑的路径节点作为Bezier曲线的控制点,并利用Bezier曲线对路径进行调整,解决路径中存在的折线、偏转角度大、不平滑等问题.然后,在JPS算法规划好的路径节点上设置群体密度信息,并根据密度信息调整智能体的速度以及运动方向,解决群体运动堵塞和个体碰撞问题.实验结果证实了该算法的可行性,在保证镜头效果的情况下,能够逼真地模拟大规模群体运动,大大提高了群体动画运动路径的制作效率,适用于各种复杂电影场景.     

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

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

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

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

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

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

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

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

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

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

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

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