融合重力信息的优化A * 算法航路规划

doi:10.12305/j.issn.1001-506X.2025.04.29

Abstract

Abstract:

The technology of gravity matching navigation is a kind of underwater passive navigation and positioning method. Considering that the submarine cannot make large angle steering or frequent steering when sailing. This paper presents a route planning algorithm for navigable region with good overall adaptability, which aims to keep the planned route in the gravity navigable region. A sub-node optimization method based on azimuth judgment and obstacle classification is designed. A route bi-directional smoothing method based on Floyd algorithm is presented. The evaluation function introducing gravity complexity weights is optimized. The experimental results show that the proposed method can provide safe and effective planning route for submarines.

Key words: underwater navigation, gravity matching, route planning, A * algorithm

CLC Number:

P223

Jingwen ZONG, Peng CAI, Guojun ZHAI, Hairong ZHU, Cheng CHEN, Ruichen PAN. Optimized A * algorithm route planning by integrating gravity information[J]. Systems Engineering and Electronics, 2025, 47(4): 1327-1334.

Figures/Tables 13

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Table 1

References 22

1	党亚民, 蒋涛, 杨元喜, 等. 中国大地测量研究进展(2019-2023)[J]. 测绘学报, 2023, 52 (9): 1419- 1436.
	DANG Y M , JIANG T , YANG Y X , et al. Research progress of geodesy in China (2019-2023)[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52 (9): 1419- 1436.
2	TEIXEIRA F C , MANUEL P A . Geophysical navigation of autonmous underwater vehicles[J]. IFAC Proceedings, 2007, 40 (17): 117- 122.
3	郑伟, 李钊伟, 吴凡. 天海一体化水下重力辅助导航研究进展[J]. 国防科技大学学报, 2020, 42 (3): 39- 49.
	ZHENG W , LI Z W , WU F . Research progress of the underwater gravity-aided navigation based on the information of aerospace-marine integration[J]. Journal of National University of Defense Technology, 2020, 42 (3): 39- 49.
4	XI M H , WU L , LI Q Q , et al. Matching area selection for arctic gravity matching navigation based on adaptive all-field extended extremum algorithm[J]. IET Radar, Sonar & Navigation, 2024, 8 (18): 1307- 1317.
5	WANG B , ZHU J W , DENG Z H , et al. A characteristic parameter matching algorithm for gravity-aided navigation of underwater vehicles[J]. IEEE Trans.on Industrial Electronics, 2019, 66 (2): 1203- 1212. doi: 10.1109/TIE.2018.2831171
6	李兰玉, 熊凌, 李开寒. 一种结合匹配区选择和障碍物探测的水下路径规划方法[J]. 武汉科技大学学报, 2014, 37 (4): 305- 309.
	LI L Y , XIONG L , LI K H . An approach to underwater path planning based on adaptive area selection and obstacle detection[J]. Journal of Wuhan University of Science and Technology, 2014, 37 (4): 305- 309.
7	张浩杰, 张玉东, 梁荣敏, 等. 改进A * 算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45 (2): 513- 520. doi: 10.12305/j.issn.1001-506X.2023.02.23
	ZHANG H J , ZHANG Y D , LIANG R M , et al. Energy-efficient path planning method for robots based on improved A * algorithm[J]. Systems Engineering and Electronics, 2023, 45 (2): 513- 520. doi: 10.12305/j.issn.1001-506X.2023.02.23
8	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42 (10): 2312- 2319. doi: 10.3969/j.issn.1001-506X.2020.10.20
	ZHANG Q X , ZENG B , LI H P . Underway replenishment path planning method for distributed navel warfare under the influence of sea conditions[J]. Systems Engineering and Electronics, 2020, 42 (10): 2312- 2319. doi: 10.3969/j.issn.1001-506X.2020.10.20
9	PERSSON S M , SHARF I . Sampling-based A * algorithm for robot path-pathing[J]. The International Journal of Robotics Research, 2014, 33 (13): 1683- 1708. doi: 10.1177/0278364914547786
10	欧阳明达, 马越原. 基于改进A * 算法的水下重力匹配导航路径规划[J]. 地球物理学报, 2020, 63 (12): 4361- 4368.
	OUYANG M D , MA Y Y . Path planning for gravity aided navigation based on improved A * algorithm[J]. Chinese Journal of Geophysics, 2020, 63 (12): 4361- 4368.
11	张驰, 李姗姗, 史颜俊, 等. 蚁群-势场算法在水下重力辅助导航航路规划中的应用[J]. 测绘学报, 2020, 49 (7): 865- 873.
	ZHANG C , LI S S , SHI Y J , et al. Application of ant colony-potential field algorithm in underwater gravity matching navigation track planning[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49 (7): 865- 873.
12	张锦柏, 肖云, 陈垲宁. 多属性决策与改进A * 算法规划重力匹配导航航路[J]. 测绘科学, 2023, 48 (9): 38- 48.
	ZHANG J B , XIAO Y , CHEN K N . Multi-attribute decision theory and improved A * algorithm for planning gravity matching navigation tracks[J]. Science of Surveying and Mapping, 2023, 48 (9): 38- 48.
13	朱宇炜. 基于重力信息的航路规划方法研究[D]. 北京: 北京理工大学, 2016.
	ZHU Y W. Route planning research based on gravity information[D]. Beijing: Beijing Institute of Technology, 2016.
14	宗敬文. 海洋重力场精化方法与重力匹配导航应用研究[D]. 武汉: 海军工程大学, 2023.
	ZONG J W. Research on marine gravity field refining method and gravity matching navigation application[D]. Wuhan: Naval University of Engineering, 2023.
15	赖荣燊, 窦磊, 巫志勇, 等. 融合改进A * 算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36 (8): 1884- 1894.
	LAI R Y , DOU L , WU Z Y , et al. Fusion of improved A * and dynamic window approach for mobile robot path planning[J]. Journal of System Simulation, 2024, 36 (8): 1884- 1894.
16	吴鹏, 桑成军, 陆忠华, 等. 基于改进A * 算法的移动机器人路径规划研究[J]. 计算机工程与应用, 2019, 55 (21): 227- 233.
	WU P , SANG C J , LU Z H , et al. Research on mobile robot path planning based on improved A * algorithm[J]. Computer Engineering and Applications, 2019, 55 (21): 227- 233.
17	张岩, 杨龙. 最短路问题的Floyd算法优化及分析[J]. 信息技术, 2017 (10): 30- 32.
	ZHANG Y , YANG L . Optimization and analysis of floyd algorithmic for the shortest path problem[J]. Information Technology, 2017 (10): 30- 32.
18	LI Q , BAO L , SHUM C K . Altimeter-derived marine gravity variations reveal the magma mass motions within the subaqueous Nishinoshima volcano, Izu-Bonin Arc, Japan[J]. Journal of Geodesy, 2021, 95 (5): 46.
19	WANG H B , WU L , CHAI H , et al. Characteristics of marine gravity anomaly reference maps and accuracy analysis of gravity matching-aided navigation[J]. Sensors, 2017, 17 (8): 1851.
20	SANDWELL D T , MULLER R D , SMITH W H F , et al. New global marine gravity model from CryoSat-2 and Jason-1 reveals buried tectonic structure[J]. Science, 2014, 346 (6205): 65- 67.
21	TOZER B , SANDWELL D T , SMITH W H F , et al. Global bathymetry and topography at 15 arc sec: SRTM15+[J]. Earth and Space Science, 2019, 6 (10): 1847- 1864.
22	ZONG J W , BIAN S F , TONG Y D , et al. Classification of gravity matching areas using PSO-BP neural networks based on PCA and satellite altimetry data over the western pacific[J]. Sensors, 2022, 22 (24): 9892.

航路	算法名称	耗时/s	转折度数/(°)	转折次数	路径长/nmile	遍历节点数
航路1	蚁群算法	4.788 9	1 395	31	27.97	-
	Dijkstra算法	0.007 5	450	10	27.56	199
	传统A*算法	0.005 8	450	10	27.56	126
	优化A*算法	0.005 7	530	11	27.23	73
航路2	蚁群算法	5.536 40	810	18	32.799	-
	Dijkstra算法	0.028 44	495	11	28.899	210
	传统A*算法	0.020 66	450	10	28.899	125
	优化A*算法	0.028 26	397	10	28.467	104
航路3	蚁群算法	3.858 40	135	3	18.142	-
	Dijkstra算法	0.031 85	135	3	18.142	188
	传统A*算法	0.027 04	180	4	18.142	65
	优化A*算法	0.027 76	92	4	17.590	47

[1]	Zhipeng YANG, Zihao CHEN, Chang ZENG, Song LIN, Jindi MAO, Kai ZHANG. Online route planning decision-making method of aircraft in complex environment [J]. Systems Engineering and Electronics, 2024, 46(9): 3166-3175.
[2]	Xiaocao YANG, Yanli DU, Yunong BU, Yanbin LIU, Cheng GAO. Online three-dimensional RRT^* cooperative route planning based on hierarchical decomposition [J]. Systems Engineering and Electronics, 2023, 45(5): 1409-1419.
[3]	Lei LAI, Dewei WU, Kun ZOU, Kun HAN, Hailin LI. Three dimensional route planning of UAV based on the multi-criterion interactive membrane evolutionary algorithm [J]. Systems Engineering and Electronics, 2021, 43(1): 138-146.
[4]	ZENG Guoqi, BAI Yu, LIN Wei, DING Wenrui. Multi-UAV cooperative search method for ground moving targets [J]. Systems Engineering and Electronics, 2018, 40(7): 1498-1505.
[5]	WU Jian, SHU Jiansheng, LI Yaxiong, SU Guohua, HE Yanping. Three-dimensional planning of unmanned aerial vehicle based on AICS [J]. Systems Engineering and Electronics, 2018, 40(1): 86-90.
[6]	ZHANG Huan, YANG Rennong, WU Jun, LI Qiuni, FU Xiuzhu, SUN Changyue. Research on multi-aircraft cooperative suppressing jamming embattling in electronic warfare planning [J]. Systems Engineering and Electronics, 2017, 39(3): 542-548.
[7]	SI Wei-chao, QI Yu-dong, HAN Wei. Carrier plane transportation in hangar based on convex hull algorithm combined with Dijkstra [J]. Systems Engineering and Electronics, 2015, 37(3): 583-588.
[8]	LIU Li， YU Cheng-long， WANG Zhu， QI Zhu-chang， LONG Teng. Fast 3D route planning method for small UAV [J]. Systems Engineering and Electronics, 2013, 35(12): 2521-2526.
[9]	LI Meng, WANG Dao-bo, SHENG Shou-zhao, SHEN Zi-ran. Multiple route planning based on particle swarm optimization and weighted k-means clustering [J]. Journal of Systems Engineering and Electronics, 2012, 34(3): 512-516.
[10]	ZHANG Li-chuan, XU De-min, LIU Ming-yong. Cooperative navigation for multiple autonomous underwater vehicles based on two hydrophones [J]. Journal of Systems Engineering and Electronics, 2011, 33(7): 1603-1606.
[11]	NI Tian-quan， WANG Jian-dong， LIU Yi-an. Application of particle swarm algorithm in route planning of UAV [J]. Journal of Systems Engineering and Electronics, 2011, 33(4): 806-810.
[12]	LIU Juan,TANG Su-yan,LI Qun,WANG Wei-ping. Research and application of an ontology for aircraft route planning [J]. Journal of Systems Engineering and Electronics, 2010, 32(6): 1258-1262.
[13]	TANG Xin-min, WANG Yu-ting, HAN Song-chen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS [J]. Journal of Systems Engineering and Electronics, 2010, 32(12): 2669-2675.
[14]	LIU Juan，ZHANG Wei，LI Qun，WANG Weiping. Heuristic route planning approach based on threat points [J]. Journal of Systems Engineering and Electronics, 2010, 32(10): 2171-2175.

Optimized A * algorithm route planning by integrating gravity information

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 22

Related Articles 14

Recommended Articles

Metrics

Comments