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

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

基于跳点搜索算法的网格地图寻路

等价网格环境下的寻路问题普遍存在于机器人、电子游戏等应用领域.其中,最先进的技术都被分层寻路算法所主导,这些算法速度快且内存开销较小,但通常返回的路径都是次优的.本文提出了一个新颖的、特定于网格的搜索策略,该策略速度快、最优且无需内存开销,其算法可以描述为一个宏算符,该宏算符识别和有选择地扩展网格地图上的仅仅某些节点,我们称之为跳点,连接两个跳点的路径上的中间节点将不再被扩展.我们将证明该方法计算出的解总是优解的;然后,进行了深入的实证分析,并将我们的方法与其他文献上的相关工作做对比.我们发现利用跳点进行搜索能将A＊算法的速度提高一个数量级甚至更多;同时,我们报告了跳点搜索相对于当前最先进的技术而言有明显的改进.     

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

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

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

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

自动寻路A*算法的应用及优化设计

自动寻路A*算法是富互联网应用(RIA)游戏制作过程中的核心算法,解决了地图中两点之间寻路的问题,应用于很多游戏中.对A*寻路算法的实现方法进行了研究和探讨,并对该算法进行了优化设计,体现了该算法的功能,最后对其应用前景进行了展望.     

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

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

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

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

两种改进的最优路径规划算法

在对经典Dijkstra算法和A*算法分析的基础上对它们分别进行了改进.在经典Dijkstra算法中,针对当前不相连节点间路径长度为无穷大这一特点,首先对两个节点是否相连进行判断;若发现两个节点并不相连时,则舍去相应计算,从而减小计算量.针对A*算法在实际应用中搜索效率低的缺点,将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后,再按照经典A*算法搜索出相应的新最优路径,最后再将原始最优路径与这些新最优路径进行对比,以便确定最终的最优路径.仿真研究表明:改进的Dijkstra算法可以减少大量的无关节点计算,提高运算的效率;改进的A*算法则可以提高搜索到最优路径的成功率.     

动态障碍的A*算法及其实现

A*算法作为人工智能中一种普遍而重要的启发式搜索算法,主要广泛应用在最短路径的搜索,特别是游戏设计中的路径搜索。游戏设计中较注重算法的速度和效率,不仅要在静态障碍物的情况下寻找最佳路径,还要在动态障碍物的情况下寻找最佳路径。动态障碍物环境下的寻路实现在现实应用中也是十分关键的。本文主要介绍了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＊算法,主要的改变是将结点空间从二维扩展到三维,使搜索过程能曲线转弯,避免了碰撞障碍物,实现了“合法”转弯．     

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

近年来,跳点搜索(Jump Point Search, JPS)算法在移动机器人的全局路径规划中得到广泛运用,但其本身存在计算量较大、用时较长等问题。因而有人又提出了通过地图预处理提高效率的JPS+算法,但仍然在计算量和用时上有改进空间。针对业界存在的现实问题,首先介绍了JPS+的主要工作,并对JPS+算法进行了详尽分析,继而阐明了本文提出的两点改进策略。一是引入了一种基于密度的判断障碍物角点规则,进而减少主要跳点的数量;二是在进行最短路径求解过程中对目标跳点的判定规则进行了修改,从而实现了减少计算量、缩短计算时长的目标。为验证所提改进型JPS+算法的有效性,将JPS+算法在不同类型地图中与改进型JPS+算法进行了比较。仿真结果表明,改进型JPS+算法在多种地图中均能有效提高搜索速度,路径规划也十分合理,由此证明所提改进型JPS+算法对于全局路径规划具有实用价值和推广意义。     

贺兰山岩画的多尺度非局部滤波算法

针对贺兰山岩画提出了一种新的滤波算法,该方法基于混合多尺度和非局部平均滤波的思想处理噪声图像.首先,将RGB彩色空间转换到L*a*b*颜色空间;其次,对L*a*b*颜色空间的每个分量进行多层小波变换;然后通过2种不同的策略处理粗尺度的小波系数,即对低频系数进行非局部平均滤波,对高频系数进行阈值处理,并对处理后的粗尺度小波系数进行重构得到上一层的低频图像;之后,对每一个尺度继续上面的操作直到得到最细尺度的系数,并对完全重构的图像进行非局部平均滤波;最后,将处理结果转换到通常的RGB彩色空间.大量的实验用于讨论参数的选取和算法的有效性.结果表明,该方法在计算效率、鲁棒性和视觉效果方面均优于已有的混合高斯尺度方法、多尺度双边滤波方法、非局部平均滤波方法.     

求解P~*(τ)阵线性互补问题的宽邻域路径跟踪算法

针对p*(τ)阵线性互补问题,提出一种新的内点算法—宽邻域路径跟踪算法.该算法基于精典线性规划路径跟踪算法思想,把宽邻域路径跟踪算法推广到p*(τ)阵非单调线性互补问题,给出算法的具体步骤,讨论算法的迭代复杂性,并给出数值实验.     

某些积分算子解析函数的性质

设A表示单位圆盘U={z：｜z｜〈1,z∈c）内的单叶解析函数族,定义A的子族MDg（α,β）={f（z）∈A：Re（z（f＊g）＇（z）/（f＊g（z））〈β｜（z（f＊g）＇（z）/（f＊g（z）-1｜＋α,g（z）∈A}这里α〉1,β≤0,介绍3类积分算子函数Fn（z）,G（z）,In（z）,利用解不等式的技巧和解析函数理论,对它们的性质进行探究．     

B（H）上广义Jordan triple可导映射

利用算子论方法,证明了YA∈（B）（B）,若δ满足δ（AA＊ A）=δ（A）A＊A-Aδ（A）＊A＋AA＊δ（A）,则（E） S,T∈（B）（B）和λ∈{C＼R}∪{0},且S＊-S=T＊-T=λi,使得（a） A∈（B）（B）有δ（A）=SA-AT.     

全局优化问题的无参数填充函数法

通过对全局优化问题的填充函数算法的研究,克服了填充函数P（x,x^＊,γ,ρ）和P（x,x^＊）存在的缺陷,构造了2个连续的无参数填充函数W（x,x^＊）和W（x,x^＊）,并证明了它们满足填充函数的定义。数值试验的结果表明,新的填充函数算法对于求解全局优化问题是有效的。     

关于欧拉公式在(3，1)*-列表着色中应用的一个注记

如果对于图G的每个满足|L(v)|=k(其中v为G的任意顶点)的列表分配L,G都存在一个L-着色,使得G的每个顶点至多有d个邻居与其自己着有相同的颜色,则称图G是(k,d)*-可选的。在只用欧拉公式和图的结构性质研究2-连通平面图的(3,1)*-列表着色的基础上,研究欧拉公式在平面图的(3,1)*-列表着色中的应用,证明欧拉公式在研究有割点的平面图的(3,1)*-列表着色时也是有效的。