路径规划是移动机器人技术的核心环节,对于实现机器人的高效、安全与智能运行起着至关重要的作用[1]。移动机器人路径规划主要分为全局路径规划与局部路径规划[2]。全局路径规划属于静态规划,它依据全局环境地图中的已知信息进行路径规划,以避开障碍物,常用的算法主要有A*算法[3]、RRT算法[4]、粒子群算法[5]、遗传算法[6]和JPS(jump point search)算法[7]等;局部路径规划属于动态规划,旨在对行驶环境中可能出现的未知障碍物进行避障,常用的算法主要有人工势力场法[8]、DWA(dynamic window approach)[9]、TEB(timed elastic band)[10]和MPC(model predictive control)[11]等。
JPS算法是对A*算法的改进与优化。相较于其他算法,该算法在进行路径规划时具有显著优势:一方面,JPS 能够在开阔区域快速找到最短路径,因为它可以跳过众多不必要的节点扩展,这是其他算法难以实现的;另一方面,JPS算法因其高效性,特别适用于对路径搜索速度有严格要求的应用场景,例如实时或近实时的路径规划问题。尽管 JPS 算法及其变种在上述场景中表现优异,但它主要适用于静态环境中的路径规划,并且依赖于网格结构[12-14]。因此,本文将 JPS 算法与DWA算法相融合,即先利用 JPS 算法快速规划出移动机器人的全局路线,再通过融合 DWA 算法,使其能够根据当前行驶的环境状况制定相应的行驶策略。
秦齐等[15]运用了双向JPS搜索算法,提高了搜索速度和移动机器人路径规划的导航适应性,但是双向搜索和动态跳点处理都需要额外的计算资源,可能无法满足对实时性的严格要求。Su等[16]通过引入人工势场计算扩展方向优先级来指导后续跳点搜索,从而提高了寻路效率,但是构建人工势场(artificial potential field,APF)和方向图可能会增加算法的复杂度,特别是在高维度或大规模的环境中。Chen等[17]将JPS与蚁群优化算法( ant colony optimization,ACO)相结合,能够处理复杂环境中的动态障碍物,并能通过蚁群算法自适应调整路径规划,但蚁群算法的性能对参数设置较为敏感,需要精细调整以获得最佳效果。张庆等[18]通过使用切比雪夫距离替代欧氏距离来优化启发函数,使得启发式函数精确等于实际最佳路径,从而减少了节点的扩展数量,但是文献中没有考虑到路径平滑性的问题,特别是在机器人运动特性要求下,路径的平滑性对于实际应用至关重要。DWA算法在静态环境具有良好避障能力,但在动态环境中表现欠佳。Kobayashi等[19]对DWA算法进行了更深层次的扩展,他们利用激光测距仪和RGB-D相机实时获取环境信息,并通过估算盲区和改进的代价函数来优化局部路径规划安全性和最优性,但是在动态环境中,物体的运动可能导致盲区的变化,增加了预测和规避的难度。刘宙浩等[20]基于障碍物距离移动机器人的位置,在评价函数中加入了动态权重系数,提升了算法路径规划时的适应性,但在遇到移动障碍物时可能存在较大的偏移角度和较长的避障路径等问题。Berti等[21]在算法中加入Lyapunov稳定性判据,能使移动机器人以稳定的速度输出控制指令,保证了移动机器人运动控制的安全性和稳定性,但也带来了一定的计算开销,特别是在实时性要求较高的系统中,可能会导致性能下降。王超等[22]对移动障碍物的预测轨迹采用两直线相交法,保证了移动机器人的安全性,但该算法在密集障碍物区域可能无法选择最佳路径,导致避障效果不佳。
因此,本文针对传统JPS算法在搜索时无法有效解决计算成本和内存消耗急剧上升等问题,改进了算法的搜索方向和核心评价函数,在保证算法高效性的同时,减少了不必要扩展节点的搜索;其次对全局路径进行二次规划,消除了原有路径中存在的冗余节点。此外,针对DWA算法在相遇其他移动机器人时适应性和灵活性较差等问题,提出了一种基于碰撞距离的优先级动态避让策略。最终实现改进JPS算法快速高效地规划出移动机器人全局路线,改进DWA算法根据全局路径的具体环境状况做出相应的避障策略。
1 算法基础及预处理
1.1 地图建立及预处理
传统JPS算法是将全局地图简化成栅格地图,如图1所示。为了简单实现环境建模,对于形状不规则的障碍物,规定只要涉及障碍物的栅格区域,使其占满一个完整的栅格并以黑色标识。
图1 栅格地图
Figure 1 Grid map
鉴于移动机器人的自身尺寸,为避免移动机器人在拐角处与障碍物发生碰撞,根据栅格地图中障碍物的密集程度对障碍物的最外层进行膨胀处理,可避免将跳点搜索到危险区域以确保移动机器人的安全行驶[23]。
对障碍物进行膨胀处理所依据的评价函数为
(1)
式中:a表示障碍物的膨胀栅格数;m表示地图中障碍物的密集程度;k表示移动机器人安全间隔系数;L表示移动机器人自身的最大空间尺寸,m;「⎤为向上取整符号。当0.7≤m<1时,高密度障碍物地图已不适合障碍物膨胀和大尺寸机器人行驶,所以不对障碍物进行膨胀处理操作。
1.2 JPS算法介绍及预处理
JPS算法是一种启发式搜索算法,通过评价函数(式(2))来确定地图网格中节点的选取[3]。
f(n)=g(n)+h(n)。
(2)
式中:n为当前节点;g(n)为起始节点到当前节点n的实际代价;h(n)为当前节点n到目标节点的估计代价;f(n) 为起始节点到当前节点n的总代价。其中h(n)具有多种计算方式,如图2所示。
图2 h(n)计算方式
Figure 2 h(n) calculation
本文选用更加接近真实距离的对角线距离作为h(n)的计算方式[24],计算过程为
L1=|xnow-xgoal|+|ynow-ygoal|;
(3)
L2=min(|xnow-xgoal|,|ynow-ygoal|);
(4)
(5)
式中:(xnow,ynow)为当前节点的坐标;(xgoal,ygoal)为目标节点的坐标。
JPS的高效性得益于其独特的自然领域节点裁剪和跳跃规则。自然邻域节点裁剪可分为以下两种情况。当父节点np的自然邻域不存在障碍物时,修剪规则定义为从父节点np出发,经过某一个自然邻域节点nnature到目标节点ngoal的代价距离小于等于父节点np经过除去节点nnature外的其余节点到目标节点ngoal的代价距离,裁剪后保留的自然邻域节点nnature约束公式[6]表示为
length({np,n1,n2,…,ngoal}\nnature)≥
length({np,nnature,ngoal})。
(6)
式中:{np,n1,n2,…,ngoal}表示父节点np到目标节点ngoal的一系列路径点的集合;\为集合差符号。
当父节点np的自然邻域周围存在障碍物时,修剪规则将会选取具有强迫邻居的自然邻域节点nnature作为待定强制节点,其中强迫邻居节点nforced的特征为从父节点np出发,经过此自然邻域节点nnature到强迫邻居节点nforced的距离代价比任何其他不经过nnature到达强迫邻居节点nforced的距离代价都小。强迫邻居节点nforced的约束公式[6]表示为
length({np,n1,n2,…,nforced}\nnature)≥
length({np,nnature,nforced})。
(7)
式中:{np,n1,n2,…,nforced}表示父节点np到强迫邻居节点nforced的一系列路径点的集合。
跳跃规则是JPS算法通过迭代当前节点的继承跳点,并通过评价函数选取继承跳点中f估计值最小的跳点再进行拓展,直至到达目标点。
2 改进JPS算法
2.1 搜索方向的改进
传统JPS算法在初始搜索阶段时未确定拓展方向。如图3(a)所示,由于起点nstart不存在父节点,起点nstart开始向周围所有方向扩展,对于目标节点ngoal来说,起点nstart的右上方向是最优搜索方向,右方和上方是高效搜索方向,其他方向搜索均为低效搜索方向,这些方向上搜索到的新跳点在增加系统计算资源和内存储存资源的消耗,同时也会增加冗余跳点的数量,降低算法寻优效率。同样,在中间跳点的强迫邻居方向搜索时也会产生相同的问题,如图3(b)所示。并且随着拓展方向的增加,算法的运行速度也会受到影响而变慢。
图3 传统JPS搜索方向示意图
Figure 3 Traditional JPS search direction diagram
为解决上述问题,本文对JPS跳点搜索方向进行改进,提出了一种具有优先搜索方向的改进JPS算法。具体算法步骤如下。
步骤1 算法在起点nstart处搜索跳点时先根据起点与目标点的位置计算目标方向Goal_dir,并将此方向设为优先搜索方向。为了保证算法的全局最优性,避免算法在搜索过程中陷入局部最优,将与目标方向相邻的两个方向一并设为优先搜索方向,如图4(a)所示。
图4 改进JPS搜索方向示意图
Figure 4 Improved JPS search direction diagram
步骤2 当算法在中间跳点njump处进行搜索时,将目标方向及两个相邻方向设为优先搜索方向,并降低跳点njump强迫邻居搜索方向Neighbor_dir的优先级,规定只有当目标方向未搜索到新的跳点时,算法开始从跳点的强迫邻居方向搜索新的跳点,如图4(b)所示。
步骤3 为了保证算法的简洁性和鲁棒性,当目标点方向位于起点的垂直向上或水平向右方向时,默认起点的优先搜索方向为右上角。以此类似,当目标点方向位于起点的垂直向下或水平向左方向时,默认起点的优先搜索方向为左下角。
2.2 自适应权重评价函数
JPS算法路径规划的核心在于评价函数(式(2)),传统JPS算法由于评价函数的单一性存在诸多问题,例如出现重复访问不必要跳点、扩展节点搜索范围变大、冗余跳点数目增加的现象。因此,本文引入了移动机器人位置因子对启发函数进行动态加权,通过动态调整启发函数的权重系数来减少无关拓展节点和冗余跳跃节点的搜索。改进后的启发函数为
f(n)=khh(n)+kgg(n)。
(8)
(9)
式中:kh为估计代价h(n)的动态权重系数;kg为实际代价g(n)的动态权重系数;l为当前跳点到目标点的欧氏距离,m;l′为起点到目标点的欧氏距离,m。将kh和kg分别取P的比值形式的原因是为了缓和当前跳点与父节点相距较远时P值激变所带来的影响。
通过引入自适应权重系数后,评价函数会根据当前跳点的位置而动态地改变估计代价h(n)和实际代价g(n)的占比。当跳点位置距离目标点较远时,算法将提高估计代价h(n)的占比,更加关注于快速接近目标点,减少冗余节点的搜索,降低了资源占用对算法搜索效率的影响。当跳点位置接近目标点时,算法将提高实际代价g(n)的占比,更关注全局信息以寻找最优路径,提高路径规划的安全性和可靠性。
2.3 冗余节点的删除
针对传统JPS算法规划出的全局路径中存在冗余节点导致路径转折点增多、平滑性降低的现象,本文对改进的JPS算法规划后的全局路径进行二次处理,提出了冗余节点裁剪算法,即通过判断节点之间的连线是否存在障碍物以去除中间冗余节点。如图5所示,当节点n1与节点n3之间不存在障碍物时,算法将以节点n1为基点,节点n3为起点,判断后续节点与节点n1之间是否存在障碍物,直至算法递进到节点n5发现障碍物后,算法将停止递进并裁剪冗余节点n3,保留后续关键节点n4。随后算法将以节点n4为基点继续递进裁剪。冗余节点裁剪算法具体步骤如下。
图5 冗余节点裁剪示例图
Figure 5 Example of redundant node trimming
步骤1 输入3个相邻的初始路径点ni,ni+1,ni+2。
步骤2 判断节点ni和节点ni+2之间是否存在障碍物,是则执行步骤3,否则执行步骤4。
步骤3 将节点ni和节点ni+1添加到新路径中并更新递进节点位置到i+1处,执行步骤5。
步骤4 以节点ni为基点,节点ni+2为起点开始向后递进搜索,直到ni和ni+m之间存在障碍物,将ni和ni+m-1添加到新路径中并更新递进节点位置到i+m-1,执行步骤5。
步骤5 判断当前节点位置是否为目标点或目标点前一路径点,若存在,则输出裁剪后的路径;否则转到步骤2。
为验证本文提出的冗余节点裁剪算法的有效性,利用MATLAB 2022a搭建模拟仿真环境,构建100×100像素的街道栅格地图以及100×100像素的仓库栅格地图,分别对改进后的JPS算法进行仿真验证。在确保各项仿真条件相同的情况下,仿真结果如图6所示,路径数据如表1所示。
表1 裁剪前后结果对照
Table 1 Comparison of results before and after cutting
地图路径长度节点数优化前优化后裁剪前裁剪后街道110.77107.552416仓库131.30125.464125
图6 地图路径对比
Figure 6 Comparison of map paths
由图6和表1可知,应用冗余节点裁剪算法后,在街道栅格地图中,裁剪后的路径长度比裁剪前的路径长度缩短了2.9%,节点数减少了33.3%;在仓库栅格地图中,裁剪后的路径长度比裁剪前的路径长度缩短了4.4%,节点数减少了39.0%。分析可知,本文设计的冗余节点裁剪算法能够有效去除路径中存在的冗余节点,提升路径规划的平滑性和机器人路径跟踪的安全性。
3 融合JPS算法和DWA算法
3.1 DWA算法
DWA算法是比较常用的局部路径规划算法,其主要步骤是移动机器人首先根据当前运动状态计算出当前的速度和角速度范围,此范围就是动态窗口。随后在此窗口中计算并模拟出以不同速度和角速度在未来一定时间内的行程轨迹,最后通过评价函数选出评分最高的最优轨迹,重复上述过程直至到达目标点。其运动模型[7]可表示为
(10)
为了保证移动机器人安全行驶,对其速度和角速度的采样范围进行约束,约束公式[7]为
Vm={(v,ω)|v∈[vmin,vmax],ω∈[ωmin,ωmax]}。
(11)
式中:vmin、vmax分别为最小、最大线速度;ωmin、ωmax分别为最小、最大角速度。
移动机器人的线加速度和角加速度受自身电机性能的限制,在一个速度采样周期内,移动机器人实际能到达的速度为[7]
(12)
式中:vc、ωc表示当前时刻的线速度与角速度;
表示在电机影响下线速度所能达到的最大减速度与最大加速度;
表示在电机影响下角速度所能达到的最大减速度与最大加速度。
为了避免移动机器人因速度过快与障碍物发生碰撞,对移动机器人安全制动范围进行约束[7],即
(13)
式中:dist(v,ω)表示速度空间对应的轨迹离障碍物最近的距离。
综上所述,移动机器人最终动态窗口的移动速度Vr取值范围为
Vr=Vm∩Vd∩Va。
(14)
轨迹空间中有多条基于不同速度和角速度形成的预测轨迹,为了选出最优轨迹,需要引入评价函数对其进行打分,评价函数[7]为
G(v,ω)=σ(α·Heading(v,ω)+β·dist(v,ω)+
γ·velocity(v,ω))。
(15)
式中:Heading(v,ω)为轨迹切线方向与目标点的夹角;dist(v,ω)为机器人与最近障碍物间的距离;velocity(v,ω)为当前轨迹速度大小;α、β、γ为各项的加权系数。
3.2 DWA算法的改进
在现实场景中的多移动机器人路径规划中往往存在交叉路径,在运用传统的DWA算法对多移动机器人进行路径规划时可能会因算法本身缺乏多机器人间的互动协调机制以及应对动态环境的有效策略而产生一定的规划问题,如DWA在动态避让其他机器人时可能选择绕行较长的路径,增加了路径规划时间和能量上的消耗,在存在交叉路径时也有可能会因避让不及时而产生碰撞的风险。为了解决此类问题,本文引入优先级避让策略以提高DWA算法的安全性和灵活性。
鉴于动态优先级的优越性和广泛应用性,本文引入基于碰撞距离的动态优先级避让策略,其避让策略具体步骤如下。
步骤1 移动机器人在进入到彼此障碍物检测范围后(可根据刹车距离自定义检测范围)先进行相互识别,如图7(a)所示。在识别完成后开始计算各自当前位置到达轨迹交点处的距离,并选取此距离作为后续优先级判断依据,如图7(b)所示。
图7 动态优先级避让
Figure 7 Dynamic priority avoidance
步骤2 距离轨迹交点越近的移动机器人优先级别越高,当它与其他移动机器人相遇时,将会忽视比其优先级低的机器人的位置冲突并继续行驶;相反距离轨迹交点越远的机器人的优先级越低,低优先级的移动机器人会将高优先级的移动机器人实时位置和其采样范围内每一个行程预测轨迹的终点位置视为障碍物进行处理,以实现主动避让优先级高的移动机器人的目的,如图7(c)所示。
步骤3 待高优先级的移动机器人通过后,低优先级的机器人开始加速通行直到恢复正常行驶,如图7(d)所示。
3.3 融合JPS算法和DWA算法
鉴于改进的JPS 算法在非网格的连续空间以及动态环境中对障碍物或机器人缺乏有效的应对措施,而改进的DWA 算法又容易陷入局部最优,因此,本文将改进的JPS 算法与改进的DWA 算法进行融合。此举旨在确保移动机器人在沿着全局路径行驶的同时,还能在动态环境中顺利且安全地抵达设定的目标点。融合算法的流程图如图8所示。
图8 算法融合流程图
Figure 8 Algorithm fusion flowchart
4 仿真分析
为验证本文算法的有效性,利用MATLAB 2022a软件分别对改进的JPS算法和改进的DWA算法进行仿真验证。首先对于改进的JPS算法,在3 种不同复杂程度的障碍物环境下对A*算法、传统JPS算法、文献[18]算法和改进的JPS算法进行仿真对比实验。实验地图分别为100×100像素的街道地图、100×100像素的仓库地图、100×100像素的商场地图,各地图障碍物膨胀栅格数为1,分别如图9～11所示,并选取各算法的运行搜索时间、路径长度、扩展节点数、节点数、轨迹节点数和路径拐点个数作为实验结果性能指标,各地图的算法性能指标如表2所示。使用的操作系统为Windows11,处理器为Intel Core i7-14650HX 2.20 GHz。
表2 不同算法性能对比
Table 2 Performance comparison of different algorithms
地图算法扩展节点数节点数轨迹节点数搜索时间/s路径拐点数路径长度/mA∗算法188118811050.4521113.11街道传统的JPS算法2320153290.2219109.50文献[18]算法87451290.1719110.08改进的JPS算法81964160.1512107.55A∗算法287428741210.6325136.57仓库传统的JPS算法3544334400.2523130.12文献[18]算法115544150.154160.83改进的JPS算法1522130250.1421125.46A∗算法299929991090.7422124.57商场传统的JPS算法3207191330.2319119.88文献[18]算法136161250.2117125.15改进的JPS算法133871170.1514117.31
图9 复杂街道路径规划图
Figure 9 Complex street path planning map
图10 仓库路径规划图
Figure 10 Warehouse path planning diagram
图11 商场路径规划图
Figure 11 Shopping mall path planning map
图9～11中,黑色栅格代表障碍物,绿色圆圈代表起点,黄色圆圈代表目标点,浅蓝色栅格代表各算法扩展的节点数,深蓝色方形代表改进的JPS算法的跳点,玫红色方形代表改进的JPS算法跳点的强迫邻居,其余栅格均代表可行区域;最后实线表示算法规划出的全局路径。表2中,节点数表示算法将访问过的栅格数筛选后收录到open列表中的栅格数。对于A*算法而言,因为没有定义特殊的筛选规则,所以A*算法的扩展节点数就等于节点数。
由表2可知,在地图的总体搜索规模上,改进的JPS算法和文献[18]算法在3个场景中扩展的节点数均显著减少,其中改进的JPS算法在街道和商场场景地图中扩展的节点数比文献[18]算法更少。在复杂街道场景中,改进的JPS算法相较于A*算法、传统的JPS算法和文献[18]算法分别减少了56.46%,64.70%和6.29%。在商场场景中,改进的JPS算法相较于A*、传统的JPS算法和文献[18]算法分别减少了55.39%,58.28%和1.70%。在仓库场景地图中,文献[18]算法扩展的节点数最少,但其规划出的路径长度相较于改进的JPS算法却增加了21.99%,具体的原因可能是算法在追求效率提升的过程中,忽略了一些潜在的更优路径,而这些路径恰恰需要通过搜索那些未被扩展的节点来实现。
在算法的轨迹节点搜索方面,改进的JPS算法的优化效果在复杂街道地图中最为明显,相对于A*减少了84.76%,相较于传统的JPS算法和文献[18]算法都减少了44.83%。在算法搜索用时方面,4种算法用时均较短,其中A*算法在3种地图场景中的搜索时间普遍比JPS类算法耗时长,而改进的JPS算法耗时与其他算法相比均用时最短。最后在输出路径的长度和平滑度方面,改进的JPS算法经过冗余节点的裁剪,输出的全局路径变得更加平滑和快捷。在复杂街道场景中,相较于A*算法、传统的JPS算法和文献[18]算法,改进的JPS算法的拐点数分别减少了42.86%,36.84%和36.84%,路径长度分别减少了4.92%,1.78%和2.30%;在仓库场景中,相对A*算法、传统的JPS算法,改进的JPS算法的拐点数分别减少了16.0%和8.70%,路径长度相较于A*算法、传统的JPS算法和文献[18]算法分别减少了8.13%,3.58%和21.99%;在商场场景中,相较于A*算法、传统的JPS算法和文献[18]算法,改进的JPS算法的拐点数分别减少了36.36%,26.31%和17.65%,路径长度分别减少了5.83%,2.14%和6.26%。
将改进的JPS算法与改进的DWA算法融合,对于融合算法,在同一个仿真环境中设置了3个同类型移动机器人R1、R2、R3进行路径规划,并设置了2个冲突路径以验证改进的DWA算法的有效性,如图12所示。图12中,黑色栅格表示静态障碍物,三角形和圆形分别表示各移动机器人的起点和目标点位置,红色的星形表示改进的DWA算法的局部目标点,黑色实线表示改进的JPS算法规划出的全局路径,而蓝色、玫红色和绿色等实线分别表示各移动机器人的改进的DWA算法规划出的路径轨迹。
图12 多机器人路径规划
Figure 12 Multi-robot path planning
由图12(a)可知,当改进的JPS算法和改进的DWA算法的融合算法在进行路径规划时,DWA算法将首先选取JPS规划出的全局路径中的某一个轨迹点作为局部目标点进行规划任务,当移动机器人即将抵达这一目标点时,局部目标点将再次递进至JPS全局路径中的下一个轨迹点,依次类推,直至最终目标点。从图12(b)可以看出,改进的JPS算法融合改进的DWA算法规划出的路径在确保安全性的同时,也提升了路径的平滑性,增强了路径规划的整体性能。在图12(c)和图12(d)中,经过改进后的DWA算法在遇到交叉路径时会根据基于碰撞距离的动态优先级避让策略自动做出行驶判断。在图12(d)中,R1与R2相遇时,改进后的DWA算法判断出了R1具有更高的优先级,并做出了让R2减速避让而R1继续行驶通行的决策。
图13为各机器人速度变化图。从图13可以看到,在400～500的步数段内,R2的速度经历了大幅度的减速和加速过程,而R1由于具有高优先级并未进行任何加速、减速操作,仍保持原有状态继续行驶。
图13 各机器人速度变化图
Figure 13 Speed variation chart of each robot
根据仿真结果可知,改进后的DWA算法可以很好地改善传统DWA算法在处理路径冲突等动态环境问题上的缺陷和不足,避免了传统算法因动态避障带来的较大的偏移角度和较长的避障路径等问题,同时也提高了DWA算法在进行多机器人路径规划时的协同灵活性和鲁棒适应性。
5 结论
在路径规划理论和技术领域,本文借助 MATLAB,模拟了同类型移动机器人在路径规划过程中出现的路径冲突现象。在此基础上,提出了基于碰撞距离的动态优先级避让策略,为机器人行驶提供了全新的避障思路和解决方案。同时,通过对 JPS 算法进行改进,有效削减了算法在搜索路径时扩展节点、节点以及轨迹节点的数量,消除了原有路径中存在的冗余节点。这不仅提升了算法的资源利用率和寻路效率,而且对于内存资源有限的嵌入式芯片而言,能够显著降低计算资源的消耗,提高算法运行的效率与实时性,进而优化系统的整体性能和响应速度。
[1] 卢凌霄,董乾鹏,张天乐,等.机器人运动学与运动规划算法综述[J].印刷与数字媒体技术研究,2023(5): 1-16.LU L X,DONG Q P,ZHANG T L,et al.A review of robot kinematics and motion planning algorithms[J].Printing and Digital Media Technology Study,2023(5): 1-16.
[2] 白晓兰,袁铮,周文全,等.移动机器人路径规划算法研究综述[J].机械工程师,2024(8): 24-28,33.BAI X L,YUAN Z,ZHOU W Q,et al.Survey of path planning algorithms for mobile robots[J].Mechanical Engineer,2024(8): 24-28,33.
[3] HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2): 100-107.
[4] WANG H,LI G Q,HOU J,et al.A path planning method for underground intelligent vehicles based on an improved RRT* algorithm[J].Electronics,2022,11(3): 294.
[5] 高岳林,武少华.基于自适应粒子群算法的机器人路径规划[J].郑州大学学报(工学版),2020,41(4):46-51.GAO Y L,WU S H.Robot path planning based on adaptive particle swarm optimization[J].Journal of Zhengzhou University (Engineering Science),2020,41(4): 46-51.
[6] HAO K,ZHAO J L,LI Z S,et al.Dynamic path planning of a three-dimensional underwater AUV based on an adaptive genetic algorithm[J].Ocean Engineering,2022,263: 112421.
[7] HARABOR D,GRASTIEN A,HARABOR D,et al.Online graph pruning for pathfinding on grid maps[C]∥Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence.New York:ACM,2011: 1114-1119.
[8] 丁承君,阎欣怡,冯玉伯,等.基于APF的AGV局部路径规划改进算法研究[J].计算机工程与应用,2022,58(22): 305-312.DING C J,YAN X Y,FENG Y B,et al.Improved algorithm of AGV local path planning based on APF[J].Computer Engineering and Applications,2022,58(22): 305-312.
[9] FOX D,BURGARD W,THRUN S.The dynamic window approach to collision avoidance[J].IEEE Robotics &Automation Magazine,1997,4(1): 23-33.
[10] MAGYAR B,TSIOGKAS N,DERAY J,et al.Timed-elastic bands for manipulation motion planning[J].IEEE Robotics and Automation Letters,2019,4(4): 3513-3520.
[11] SHEN D,CHEN Y B,LI L X,et al.Trajectory tracking for autonomous vehicles using robust model predictive control[J].IFAC-PapersOnLine,2024,58(10): 94-101.
[12] ZHENG X,TU X W,YANG Q H.Improved JPS algorithm using new jump point for path planning of mobile robot[C]∥2019 IEEE International Conference on Mechatronics and Automation (ICMA).Piscataway: IEEE,2019: 2463-2468.
[13] MA L,GAO X,FU Y X,et al.An improved jump point search algorithm for home service robot path planning[C]∥2019 Chinese Control and Decision Conference (CCDC).Piscataway:IEEE,2019: 2477-2482.
[14] 黄健萌,吴宇雄,林谢昭.移动机器人平滑JPS路径规划与轨迹优化方法[J].农业机械学报,2021,52(2): 21-29,121.HUANG J M,WU Y X,LIN X Z.Smooth JPS path planning and trajectory optimization method of mobile robot[J].Transactions of the Chinese Society for Agricultural Machinery,2021,52(2): 21-29,121.
[15] 秦齐,万熠,侯嘉瑞,等.基于双向动态跳点搜索算法的AGV路径规划研究[J].单片机与嵌入式系统应用,2021,21(8): 55-58,63.QIN Q,WAN Y,HOU J R,et al.AGV path planning based on bidirectional dynamic jumping search algorithm[J].Microcontrollers &Embedded Systems,2021,21(8): 55-58,63.
[16] SU Q H,MA S B,WANG L Y,et al.Artificial potential field guided JPS algorithm for fast optimal path planning in cluttered environments[J].Journal of the Brazilian Society of Mechanical Sciences and Engineering,2022,44(12): 602.
[17] CHEN T,CHEN S F,ZHANG K R,et al.A jump point search improved ant colony hybrid optimization algorithm for path planning of mobile robot[J].International Journal of Advanced Robotic Systems,2022,19(5): 17298806221127953.
[18] 张庆,刘旭,彭力,等.融合JPS和改进A*算法的移动机器人路径规划[J].计算机科学与探索,2021,15(11): 2233-2240.ZHANG Q,LIU X,PENG L,et al.Path planning for mobile robots based on JPS and improved A* algorithm[J].Journal of Frontiers of Computer Science and Technology,2021,15(11): 2233-2240.
[19] KOBAYASHI M,MOTOI N.Path planning method considering blind spots based on ROS navigation stack and dynamic window approach for wheeled mobile robot[C]∥2022 International Power Electronics Conference.Piscataway:IEEE,2022: 274-279.
[20] 刘宙浩,万超一,尹明锋,等.改进A*算法与DWA融合的移动机器人的路径规划算法研究[J].制造业自动化,2023,45(12): 55-60.LIU Z H,WAN C Y,YIN M F,et al.Research on path planning algorithm of mobile robot based on improved A* algorithm and dynamic window approach[J].Manufacturing Automation,2023,45(12): 55-60.
[21] BERTI H,SAPPA A D,AGAMENNONI O E.Improved dynamic window approach by using Lyapunov stability criteria[J].Latin American Applied Research,2008,38(4): 289-298.
[22] 王超,梅瑛,张溢,等.基于改进DWA算法的移动机器人避障研究[J].机械设计与研究,2024,40(1): 92-96.WANG C,MEI Y,ZHANG Y,et al.Research on obstacle avoidance of mobile robot based on improved DWA algorithm[J].Machine Design &Research,2024,40(1): 92-96.
[23] 蔡佳成,白克强,李旭春,等.基于JPS改进的移动机器人路径规划算法[J].计算机应用研究,2022,39(7): 1985-1991.CAI J C,BAI K Q,LI X C,et al.Improved path planning algorithm for mobile robot based on JPS[J].Application Research of Computers,2022,39(7): 1985-1991.
[24] 石英托,陈华,张连新,等.基于改进A*算法的AGV转运机器人路径规划研究[J].制造技术与机床,2022(5): 19-22.SHI Y T,CHEN H,ZHANG L X,et al.Research on path planning of AGV transport robot based on improved A* algorithm[J].Manufacturing Technology &Machine Tool,2022(5): 19-22.