科技和产业

邻域数量	代价值	节点数	耗时/s
8	83.30	67	2.18
24	72.52	36	2.08
48	69.29	25	2.31

邻域数量	代价值	节点数	耗时/s
8	83.30	67	2.18
24	72.52	36	2.08
48	69.29	25	2.31

基于改进A^*算法和人工势场法的水面无人船全局路径规划

PDF下载

王亮亮 , 薛明明 , 王晓玲

科技和产业 | 科技创新 2025,25(14): 27-31

收起

科技和产业 | 科技创新 2025, 25(14): 27-31

基于改进A^*算法和人工势场法的水面无人船全局路径规划

全屏

王亮亮, 薛明明, 王晓玲

作者信息

中国建筑第八工程局有限公司, 上海 201131

王亮亮(1994—),男,安徽合肥人,工程师,研究方向为电机控制、建筑智能化;

薛明明(1988—),男,陕西延安人,中级工程师,研究方向为建筑智能化;

王晓玲(1988—),女,内蒙古赤峰人,高级工程师,研究方向为机电设计、技术管理。

Global Path Planning for Surface Unmanned Ships Based on Improved A^* Algorithm and Artificial Potential Field Method

Liangliang WANG, Mingming XUE, Xiaoling WANG

Affiliations

China Construction Eighth Engineering Division Co. Ltd., Shanghai 200131, China

出版时间: 2025-07-25

文章导航

摘要

收起

为提高无人船在实际复杂工作环境中完成水质监测的效率,提出改进A^*算法的全局静态路径规划算法以及改进A^*算法和人工势场法结合的局部动态路径规划算法。首先通过全局算法对障碍物做膨胀处理,采用扩大节点搜索邻域法对A^*算法完成改进,使当前路径点的搜索移动方向不再局限于45°的整数倍。为提高动态路径规划能力,将A^*算法规划的路径点作为人工势场法的局部目标点,通过引入距离因子和逃逸力对人工势场法进行改进,解决目标不可达且容易陷入最小值的问题。最后利用MATLAB验证方法有效性,结果表明,无人船能顺利到达并经过水质监测点,且相比传统A^*算法,得到的路径更加平滑,距离更短,有效地提高了水质监测效率。

关键词

径规划 / A^*算法 / 人工势场法 / 无人船 / 水质监测

Abstract

收起

To improve the efficiency of unmanned ships in completing water quality monitoring in complex working environments, an improved A^* algorithm for global static path planning and an improved A * algorithm combined with artificial potential field method for local dynamic path planning were proposed. Firstly, the obstacles were inflated using a global algorithm, and the A^* algorithm was improved by expanding the node search neighborhood method, so that the search movement direction of the current path point was no longer limited to integer multiples of 45 °. To improve the ability of dynamic path planning, the path points planned by the A^* algorithm were used as local target points in the artificial potential field method. The artificial potential field method was improved by introducing distance factors and escape forces to solve the problem of unreachable targets and easy getting stuck in the minimum value. Finally, the effectiveness of the method was verified using Matlab. The results show that the unmanned ship could smoothly reach and pass through the water quality monitoring point. Compared with the traditional A^* algorithm, the obtained path is smoother and the distance is shorter, effectively improving the efficiency of water quality monitoring.

Key words

path planning / A^* algorithm / artificial potential field method / unmanned ship / water quality monitoring

引用本文

王亮亮, 薛明明, 王晓玲. 基于改进A^*算法和人工势场法的水面无人船全局路径规划. 科技和产业, 2025 , 25 (14) : 27 -31 .

Liangliang WANG, Mingming XUE, Xiaoling WANG. Global Path Planning for Surface Unmanned Ships Based on Improved A^* Algorithm and Artificial Potential Field Method[J]. Science Technology and Industry, 2025 , 25 (14) : 27 -31 .

正文

收起

随着自动化技术的广泛渗透与快速发展,无人船作为一种集成了先进科技与智能化特性的水上平台,已经在诸如水质监测、水面垃圾清理、渔业饵料精准投放等多个环保与资源管理的关键领域展现巨大的应用潜力^[1]。然而,在实际作业中,无人船往往需要穿梭于复杂多变的水域环境之中,这些水域往往因地形起伏、水下洞穴密布、水流方向多变以及潮汐涨落等自然因素的交织影响,而呈现高度复杂的地形结构和水流动态特性。在这样的复杂环境中,传统的依靠人工操控或简单自动化设备的作业方式不仅效率低下,而且难以确保作业的安全性和精准度。因此,充分利用无人船的自主航行能力,对于大幅度减小人力物力、显著提高工作效率、保障安全作业有重要意义^[2]。

无人船路径规划技术是一种高级导航策略,它专注于在特定的作业水域范围内,依据一系列既定的性能指标,诸如寻求最短的行驶路径或是最短的航行时间等,来智能化地搜索并确定一条从起始位置到目标地点的无碰撞安全路径^[3]。早期的研究主要集中在基本的路径规划算法上,如A^*算法和Dijkstra算法等用于有效地找到最短路径或最优路径。其中A^*算法应用简单,操作容易,对平面的路径规划效果较好。Duchon等^[4]提出跳点搜索策略,减少了遍历节点数目,提高了算法的效率,但路径转折点仍然较多,且无法获得令人满意的最优路径。程传奇等^[5]设计全局最优路径的动态窗口评价函数,借助动态窗口算法实现了局部路径规划,避免了动态障碍物对路径规划的干扰。陈万通等^[6]提出一种同步双向扩展的A^*算法,动态定义正、反向搜索的目标节点,同时提出扇形邻域扩展策略,提高算法的搜索效率,但该方法只能在二维平面使用,很难应用与指导三维空间内的布线。Liu等^[7]提出一种改进的人工势场法,通过调整斥力函数,确保目标点成为全局极小点,进而避免出现路径规划中的死锁现象。从上述分析中可知,传统的A^*算法存在路径不够平滑、节点较多和距离较远等不足,而传统的人工势场法存在目标不可达和容易陷入局部最优的问题。

因此,本文针对A^*算法在全局路径规划过程中节点搜索移动方向少、得到的路径节点较多等问题,提出一种基于扩大节点搜索领域法的改进A^*算法全局路径规划算法。该算法增加了下一个可访问节点的数量,使节点移动方向不再受到45°整数倍限制。尽管A^*算法在静态环境中能有效寻找最优路径,但在动态环境下需频繁计算全图,计算量大且响应慢。因此提出一种将改进A^*和人工势场法相结合的局部路径规划算法,在过程中引入距离因子和逃逸力,提高算法的搜索范围和动态规划能力。最后仿真验证本方法能够保证无人船在运行过程中主动避障,并以最优方式进行水质采样与监测。

1 改进A^*算法的全局静态路径规划

收起

传统的A^*算法结合实际代价和启发式函数,具有搜索效率和准确性较好的优点,在二维静态环境下能较好地解决最短路径问题。算法可通过持续搜索邻近节点,并计算代价函数之和,选择代价最小的节点来扩展,直到找到目标节点或无法继续扩展为止。传统A^*算法表达式为

(1)F(n)=G(n)+H(n)

式中:F(n)为起始点到目标点的代价估算;G(n)为付出的实际代价;H(n)为剩余距离的代价。然而,传统A^*算法存在路径不够平滑、节点较多和距离较远等不足。因此,为了克服传统A^*算法的限制性,采用扩大节点邻域搜索范围的方法来进行改进,改进后的24邻域A^*算法如图1所示。

由于节点邻域的第二层也被计入待扩展节点,所以待扩展的节点数量增至24个,路径点运动的角度共有16个。同理,通过增加A^*算法的节点搜索范围,使得当前节点邻域的第三层也被计入待扩展节点。改进后的48邻域A^*算法如图2所示,待扩展的节点数量增至48个,路径点运动的角度共有32个。

由图2可知,通过引入节点搜索策略,可将A^*算法的节点搜索范围显著增大,并提高路径点运动的角度范围。改进A^*算法流程图如图3所示。在该流程中,将起点加入开放列表,选其中代价F最小的节点n作为当前节点并加入关闭列表,重复选择,直到找到目标节点或开放列表为空。否则,对当前节点的邻居节点进行处理^[8]。对于每个相邻节点,如果已经在关闭列表中,就跳过;如果不在待处理列表中,则将其添加,并计算其总代价。当开放列表为空,表示搜索失败,找不到路径,这就表示改进的A^*算法搜索完成。

2 基于改进A^*和人工势场法结合的局部动态路径规划

收起

尽管改进A^*算法可以完成扩大搜索范围,实现无人船在二维水面路径规划。但是当水面存在突发情况或局部障碍物时,无法很好地处理路径并确保船只安全航行。因此,将人工势场法与改进A^*算法相结合,人工势场法可以考虑到无人船的运动性能;不需要对环境建立复杂的模型或进行复杂的计算,计算效率高和实时性好。

2.1 基于改进人工势场法的避障模型建立

人工势场法思路是将无人船运动的环境看作虚拟的一个势场,其移动角度是由合力决定,每前行一段距离就计算无人船在该位置所受合力的大小和方向^[9]。当无人船与目标点位置重合时,势能和引力都为零,全场势能函数为

(2)U_p=U_att+U_rep

式中:U_p为合力势能,其指向无人船接下来的运动方向;U_att为无人船受到的引力势能;U_rep为其受到的斥力势能。

其中,无人船受到的引力势能函数U_att表达式为

(3)U_att= $\frac{1}{2}$K_att ${d}^{{}^{2}}$(P,G)

式中:P为无人船的位置;G为目标点;K_att为引力系数。

无人船的斥力势能函数U_rep表达式为

(4)U_rep= $U_{\mathrm{rep}}=\left\{\begin{array}{ll} \frac{1}{2} K_{\mathrm{rep}}\left[\frac{1}{d(P, O)}-\frac{1}{d_{0}}\right]^{2}, & 0<d(P, O)<d_{0} \\ 0, & d_{0} \leqslant d(P, O) \end{array}\right.$

式中:K_rep为斥力系数;O为障碍物;d(P,O)为无人船与障碍物的欧氏距离;d₀为障碍物对无人船产生斥力的最远距离。

通过上述模型可知,当无人船靠近目标点时,受障碍物的斥力过大,会产生目标不可达问题^[10]。因此,对人工势场法进行改进,添加一个距离因子dⁿ(P,G)到斥力势能函数。其中,n为调节因子,可根据无人船实际行进情况调整,得到d(P,G)对斥力势能函数的影响程度。改进后的斥力势能函数为

(5)U_rep= $U_{\mathrm{rep}}=\left\{\begin{array}{l} \frac{1}{2} K_{\mathrm{rep}}\left[\frac{1}{d(P, O)}-\frac{1}{d_{0}}\right]^{2} d^{n}(P, G), \\ 0<d(P, O)<d_{0} \\ 0, \quad d_{0} \leqslant d(P, 0) \end{array}\right.$

式中:d(P,G)为无人船到目标点的距离。在无人船接近目标点时,受到的斥力会减小,解决目标不可达问题。

此外,无人船在朝目标点移动时,在距离目标较远时,障碍物斥力与目标引力相等、反向,合力为零,失去了运动方向的指引,可能会停滞或者在附近振荡,误以为已到达终点,陷入局部最小陷阱。因此,由无人船与障碍物距离的远近动态调整斥力函数参数、增加逃逸力,使陷入局部极小值点的无人船摆脱陷阱,抵达目标点。首先判断无人船是否进入极小值点,若5个连续步长小于A*iter-Step时,iter-Step为基本步长,通过调节A,可较快地检测无人船是否陷入局部最小。由无人船与障碍物的距离,调整斥力函数的参数d₀;当判断无人船已经陷入局部最小时,按式(6)设计逃逸力。

(6)F_rep=δF_rep

式中:δ为系数。改进A^*算法的流程图如图3所示。

2.2 基于改进A^*和人工势场法结合的局部动态路径规划

在全局静态环境中,利用栅格化模型和改进A^*算法规划无人船依次经过水质监测点的最优路径。随后,将路径拐点转换为局部坐标,使用改进的人工势场法进行局部路径规划,利用逃逸力和距离因子解决目标不可达且容易陷入最小值的问题,逐步向终点推进,直至无人船到达目标位置,确保无人船在未知水域自主避障,实现动态路径最优规划。总体流程如图4所示。

3 仿真实验与分析

收起

运用MATLAB仿真软件对本文提出的改进A^*算法和人工势场法进行仿真,验证方法的可行性。首先,在路径规划的初步阶段充分考虑船舶自身的尺寸因素。为确保规划出的航行路径既安全又高效,对地图中的障碍物进行了膨胀处理。通过适当增加障碍物的边界范围,来预防船舶在航行过程中可能发生的拐角碰撞等安全隐患,还可以进一步减少路径规划过程中的计算量,从而提升规划效率。然后使用栅格法对水质监测无人船水域环境进行建模,将地图环境划分为二维40×40网络,白色区域为可行区域,黑色为障碍物即不可行区域。起点终点分别用绿、红色方格表示,中途三个水质监测点用黄色圆圈表示。起点坐标为(1,40),终点坐标为(40,1),水质监测点坐标为(17,27)、(32,17)、(27,3)。

3.1 全局路径规划仿真

在上述环境中进行静态路径规划仿真,对比的仿真轨迹绘制如图5所示。可知,改进的48邻域相比于8邻域和24邻域得到的路径更加平滑,证明扩大搜索范围对于静态路径规划的有效性。此外,添加静态障碍物以验证自主避障能力,所得的仿真轨迹如图6所示。其中红色、黑色和绿色曲线分别代表传统的8邻域A^*算法、改进的24邻域和48邻域A^*算法规划下的轨迹。

表1是有障碍物地图环境下三种算法规划路径的数据信息,可见相较于8和24邻域,48邻域A^*算法的代价值、节点数都是最小的。通过算法得到的路径长度越短,可以提高无人船进行水质监测的效率、节省资源和监测数据的质量。因此,在实际水域环境下,改进的24邻域和48邻域A^*算法比传统的8邻域A^*算法更具有优越性。

3.2 局部路径规划仿真

由于在实际情况中,水域可能会出现垃圾和突出的礁石等,在路径规划时需要考虑到动态的障碍物。图7为应用混合算法得到的路径图,其中蓝色曲线为动态轨迹规划路径。与静态路径规划相似,地图中的静态障碍物、起终点和水质监测点一致,蓝色方格为动态障碍物。在局部路径规划中添加了两个动态障碍物,采用改进A^*和改进人工势场法相结合的混合算法进行水质监测无人船的局部动态路径规划。由图7可知,由混合算法进行的无人船局部路径规划得到的路径较光滑,且能顺利避开障碍物,完成对水质的监测任务。

4 结论

收起

为提高水质监测无人船的自主避障能力,实现静态、动态路径规划,本文在构建的二维栅格地图中依次使用改进的A^*算法、改进的A^*和人工势场法相结合的算法来进行研究。通过仿真验证,可得本文的创新点如下。

(1)在全局研究中,改进后的A^*算法能够有效地扩大节点搜索邻域,与传统的A^*算法得出的结果进行比较,改进后距离更短,路径节点更少,路线更加平滑,且能很好地到达并经过水质监测点。

(2)局部研究中,利用混合算法能够有效避开静态和动态的障碍物,提高动态路径规划能力,确保无人船顺利完成水质监测的任务。

因此,本方法可以提升路径规划的精度,增强避碰能力,从而提高全局规划效率,保证无人船在有限时间内完成路径规划任务,并迅速投入航行。该方法具有广阔的应用前景,可用于海洋资源开发、水面交通管理、环境保护检测以及海上应急救援等,随着技术的不断发展与完善,该方法将在未来发挥更加重要的作用。

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

申燚, 赵泽钰, 袁明新, 等. 基于四叉树扇形层值聚类的无人船障碍物检测[J]. 科学技术与工程, 2024, 24(13): 5427-5435.

[2]

J L

, ZHANG

J Q

. Global path planning of unmanned boat based on improved ant colony algorithm[J]. IEEE Transactions on Power Apparatus and Systems, 2021, 45: 19156-19165.

[3]

常兴国, 吴峻. 基于变分贝叶斯的容积H∞滤波在无人船载低成本MIMU对准的应用[J]. 科学技术与工程, 2024, 24(13): 5427-5435.

[4]

DUCHON

, BABINEC

, KAJAN

, et al. Path planning with modified a star algorithm for a mobile robot[J]. Procedia Engineering, 2014, 96: 59-69.

[5]

程传奇, 郝向阳, 李建胜, 等. 融合改进A^*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报, 2017, 51(11): 137-143.

[6]

陈万通, 刁天茹, 贾吉庆, 等. 基于扇形领域扩展的同步双向A^*算法[J]. 计算机应用研究, 2022, 39(1): 118-122.

[7]

LIU

, YAO

, HE

, et al. Global dynamic path planning fusion algorithm combining jump A^* algorithm and dynamic window approach[J]. IEEE Access, 2021, 9: 19632-19638.

[8]

梁超. 基于深度学习和A^*算法的智能车路径规划研究[J]. 汽车实用技术, 2023, 48(15): 87-94.

[9]

CARISZA

, WANG

I L

, GUNWAN

. Optimal collaborative path planning for unmanned surface vehicles carried by a parent boat along a planned route[J]. International Journal of Operations Research, 2020, 17(4): 101-116.

[10]

张琪, 田甜, 栾天宇, 等. 基于改进人工势场算法的无人船路径规划[J]. 舰船科学技术, 2022(9): 63-68.

2025年第25卷第14期

PDF下载

293

141

引用本文

BibTeX

文章信息

接收时间：2025-02-28
首发时间：2025-09-15
出版时间：2025-07-25

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2025-02-28

基金

作者信息

中国建筑第八工程局有限公司, 上海 201131

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kjhcy/CN/1174385910406852869

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT