Time optimal path planning method based on Gaussian mixture regression and improved A* algorithm

doi:10.11947/j.AGCS.2025.20240478

Abstract

Abstract:

Path planning plays an important role in emergency rescue and emergency rescue. In these scenarios, vehicles are often able to get faster routes through a combination of off-road and on-road routes. Therefore, a time optimal path planning method based on Gaussian mixture regression and improved A^* algorithm is proposed. First, a time optimal traffic cost model is constructed using the A^* algorithm combined with a vehicle speed coefficient, accounting for various factors affecting vehicle traffic, including road conditions. Second, the Gaussian mixture model is employed to collect trajectory information for the proposed rescue route. Combined with Gaussian mixture regression, this model constrains the search radius of the A^* algorithm, enhancing its search efficiency. Finally, experimental verification is conducted using data from Dengfeng, Henan province. The results show that compared with the four algorithms of 2D A^*, 3D A^*, 2D time optimal A^* and improved time optimal A^* without Gaussian mixture regression constraints, the proposed algorithm reduces the path passage time by 2.02% to 32.31%, decreases code running time by 38.76% to 83.6%, and reduces node traversal by 38.69% to 79.77%. When compared to the recommended path from AutoNavi, the proposed algorithm shortens the path distance by 6.86% to 9.53% and reduces passage time by 8.41% to 17.22%.

Key words: path planning with combination of road and non-road routes, toll cost modeling, optimal timing, Gaussian mixed regression, A^* algorithm

CLC Number:

P208

Ruixin ZHANG, Qing XU, Zheng LÜ, Guo ZHANG, Xia CHU, Xiang CHENG. Time optimal path planning method based on Gaussian mixture regression and improved A^* algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2025, 54(6): 1139-1151.

Figures/Tables 16

Tab. 1

Tab. 2

Tab. 3

Tab. 4

Tab. 5

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Tab. 6

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

References 48

[1]	朱冰, 贾士政, 赵健, 等. 自动驾驶车辆决策与规划研究综述[J]. 中国公路学报, 2024, 37(1): 215-240.
	ZHU Bing, JIA Shizheng, ZHAO Jian, et al. Review of research on decision-making and planning for automated vehicles[J]. China Journal of Highway and Transport, 2024, 37(1): 215-240.
[2]	DU Pengfei, HE Xiang, CAO Haotong, et al. AI-based energy-efficient path planning of multiple logistics UAVs in intelligent transportation systems[J]. Computer Communications, 2023, 207: 46-55.
[3]	QIANG Hao, OU Rui, HU Yanchun, et al. Path planning of an electric vehicle for logistics distribution considering carbon emissions and green power trading[J]. Sustainability, 2023, 15(22): 16045.
[4]	ZHOU Xiwei, YAN Jingwen, YAN Mei, et al. Path planning of rail-mounted logistics robots based on the improved Dijkstra algorithm[J]. Applied Sciences, 2023, 13(17): 9955.
[5]	ZHANG Xinhao, GUO Yu, YANG Jinqi, et al. Many-objective evolutionary algorithm based agricultural mobile robot route planning[J]. Computers and Electronics in Agriculture, 2022, 200: 107274.
[6]	UTAMIMA A, REINERS T, ANSARIPOOR A H. Evolutionary neighborhood discovery algorithm for agricultural routing planning in multiple fields[J]. Annals of Operations Research, 2022, 316(2): 955-977.
[7]	LIU Lixing, WANG Xu, WANG Xiaosa, et al. Path planning and tracking control of tracked agricultural machinery based on improved A^* and fuzzy control[J]. Electronics, 2024, 13(1): 188.
[8]	ZHAO Dequan, NI Li, ZHOU Kefa, et al. A study of the improved A^* algorithm incorporating road factors for path planning in off-road emergency rescue scenarios[J]. Sensors, 2024, 24(17): 5643.
[9]	YANG Bing, WU Lunwen, XIONG Jian, et al. Location and path planning for urban emergency rescue by a hybrid clustering and ant colony algorithm approach[J]. Applied Soft Computing, 2023, 147: 110783.
[10]	ZHU Jianming, LIU Shuyue, GHOSH S. Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update[J]. Journal of Combinatorial Optimization, 2019, 38(1): 208-223.
[11]	张过, 秦绪文, 朱春阳, 等. 从有路导航走向无路导航[J]. 自然资源遥感, 2024, 36(4):1-8.
	ZHANG Guo, QIN Xuwen, ZHU Chunyang, et al. From road-oriented to roadless-oriented[J]. Remote Sensing for Natural Resources, 2024, 36(4):1-8.
[12]	唐继州. 面向大规模路网的路径规划方法研究[D]. 长春: 吉林大学, 2024.
	TANG Jizhou. Research on path planning methods for large-scale road networks[D]. Changchun: Jilin University, 2024.
[13]	HUANG Bingsheng, ZHANG Fusheng, LEI Linlong. Dynamic path planning based on service level of road network[J]. Electronics, 2022, 11(20): 3267.
[14]	刘钢, 安志镖, 张茂军, 等. 基于连续路网环境的实体化主体路径规划算法[J]. 系统工程与电子技术, 2024, 46(4): 1346-1356.
	LIU Gang, AN Zhibiao, ZHANG Maojun, et al. Subject objective path planning algorithm based on continuous road network environment[J]. Systems Engineering and Electronics, 2024, 46(4): 1346-1356.
[15]	赵德群, 段建英, 陈鹏宇, 等. 基于A^*算法的三维地图最优路径规划[J]. 计算机系统应用, 2017, 26(7): 146-152.
	ZHAO Dequn, DUAN Jianying, CHEN Pengyu, et al. Optimal path planning for 3D map based on A^* algorithm[J]. Computer Systems & Applications, 2017, 26(7): 146-152.
[16]	王逸康. 越野环境智能特种车轨迹规划与跟踪控制研究[D]. 长春: 吉林大学, 2024.
	WANG Yikang. Research on path planning and tracking control of intelligent military vehicle in off-road environment[D]. Changchun: Jilin University, 2024.
[17]	HU Jiaming, HU Yuhui, LU Chao, et al. Integrated path planning for unmanned differential steering vehicles in off-road environment with 3D terrains and obstacles[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(6): 5562-5572.
[18]	冯世盛, 徐青, 朱新铭, 等. 基于地形数据的长距离越野路径快速规划方法研究[J]. 地球信息科学学报, 2022, 24(9): 1742-1754.
	FENG Shisheng, XU Qing, ZHU Xinming, et al. Fast method for long-distance off-road path planning based on terrain data[J]. Journal of Geo-information Science, 2022, 24(9): 1742-1754.
[19]	LIU Qingyun, YOU Xiong, ZHANG Xin, et al. Unmanned vehicle off-road path-planning method with comprehensive constraints on multiple environmental factors[J]. International Journal of Digital Earth, 2024, 17(1): 2408453.
[20]	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.
[21]	DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
[22]	DORIGO M. Optimization, learning and natural algorithms[J]. Milano: Politecnico Di Milano, 1992.
[23]	NOGUCHI N, TERAO H. Path planning of an agricultural mobile robot by neural network and genetic algorithm[J]. Computers and Electronics in Agriculture, 1997, 18(2/3): 187-204.
[24]	LAVALLE S. Rapidly-exploring random trees: a new tool for path planning[EB/OL]. [2024-05-03]. https://www.semanticscholar.org/paper/Rapidly-exploring-random-trees-%3A-a-new-tool-for-LaValle/d967d9550f831a8b3f5cb00f8835a4c866da60ad.
[25]	XU Guiping, CUI Quanlong, SHI Xiaohu, et al. Particle swarm optimization based on dimensional learning strategy[J]. Swarm and Evolutionary Computation, 2019, 45: 33-51.
[26]	LÜ Zhihong, NI Li, PENG Hongchun, et al. Research on global off-road path planning based on improved A^* algorithm[J]. ISPRS International Journal of Geo-Information, 2024, 13(10): 362.
[27]	ZHENG Xudong, MA Mengyu, ZHONG Zhinong, et al. Two-stage path planning for long-distance off-road path planning based on terrain data[J]. ISPRS International Journal of Geo-Information, 2024, 13(6): 184.
[28]	陈占龙, 吴贝贝, 王润, 等. 面向越野路径规划的多层次六角格网通行模型[J]. 测绘学报, 2023, 52(9): 1562-1573. DOI: . doi: 10.11947/j.AGCS.2023.20220159
	CHEN Zhanlong, WU Beibei, WANG Run, et al. Multi-hierarchy hexagonal grid traffic model for off-road path planning[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(9): 1562-1573. DOI: . doi: 10.11947/j.AGCS.2023.20220159
[29]	CALINON S. A tutorial on task-parameterized movement learning and retrieval[J]. Intelligent Service Robotics, 2016, 9(1): 1-29.
[30]	李平, 李利娜, 侯志利. 协作机器人运动轨迹模仿学习方法研究[J]. 组合机床与自动化加工技术, 2024(10): 120-125.
	LI Ping, LI Lina, HOU Zhili. Research on imitation learning method of cooperative robot motion trajectory[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2024(10): 120-125.
[31]	HU Yudie, WANG Yuqi, HU Kaixiong, et al. Adaptive obstacle avoidance in path planning of collaborative robots for dynamic manufacturing[J]. Journal of Intelligent Manufacturing, 2023, 34(2): 789-807.
[32]	WANG Jiankun, LI Tingguang, LI Baopu, et al. GMR-RRT^*: sampling-based path planning using Gaussian mixture regression[J]. IEEE Transactions on Intelligent Vehicles, 2022, 7(3): 690-700.
[33]	聂士达, 刘辉, 廖志昊, 等. 考虑复杂地形的越野环境无人车辆路径规划研究[J]. 机械工程学报, 2024, 60(10): 261-272.
	NIE Shida, LIU Hui, LIAO Zhihao, et al. Study on path planning for off-road autonomous vehicles in complex terrains[J]. Journal of Mechanical Engineering, 2024, 60(10): 261-272.
[34]	冯世盛, 徐青, 李华孝杨, 等. 顾及对象性能的越野路径规划系统设计与实现[J]. 测绘与空间地理信息, 2022, 45(8): 107-110.
	FENG Shisheng, XU Qing, LI Huaxiaoyang, et al. Design and implementation of off-road path planning system considering object performance[J]. Geomatics & Spatial Information Technology, 2022, 45(8): 107-110.
[35]	WANG Mingchang, ZHU Chunyu, WANG Fengyan, et al. Multi-factor of path planning based on an ant colony optimization algorithm[J]. Annals of GIS, 2020, 26(2): 101-112.
[36]	XU Qing, FENG Shisheng, SUN Qun, et al. A method of planning disaster emergency rescue paths in road-free environment[J]. Computational Intelligence and Neuroscience, 2022, 2022: 2987852.
[37]	RYBANSKY M, HOFMANN A, HUBACEK M, et al. Modelling of cross-country transport in raster format[J]. Environmental Earth Sciences, 2015, 74(10): 7049-7058.
[38]	RYBANSKY M. Trafficability analysis through vegetation[C]//Proceedings of 2017 International Conference on Military Technologies. Brno: IEEE, 2017: 207-210.
[39]	交通运输部. 交通运输部关于发布《公路工程技术标准》的公告[EB/OL]. [2024-05-03]. https://xxgk.mot.gov.cn/2020/jigou/glj/202006/t20200623_3312197.html.
	Ministry of Transport. Announcement of the Ministry of Transport on the issuance of the technical standards for highway engineering[EB/OL]. [2024-05-03]. https://xxgk.mot.gov.cn/2020/jigou/glj/202006/t20200623_3312197.html.
[40]	SAATY T L. A scaling method for priorities in hierarchical structures[J]. Journal of Mathematical Psychology, 1977, 15(3): 234-281.
[41]	LIU Yuanmin, GAO Xinyu, WANG Bo, et al. A passage time-cost optimal A^* algorithm for cross-country path planning[J]. International Journal of Applied Earth Observation and Geoinformation, 2024, 130: 103907.
[42]	SAATY T L. What is the analytic hierarchy process?[M]//MITRA G, GREENBERG H J, LOOTSMA F A, et al. Mathematical models for decision support. Berlin: Springer, 1988: 109-121.
[43]	KIM C, KIM Y, YI H. Fuzzy analytic hierarchy process-based mobile robot path planning[J]. Electronics, 2020, 9(2): 290.
[44]	曾海洋. 越野轮胎沙石路面行驶性能仿真分析与试验评价研究[D]. 广州: 华南理工大学, 2020.
	ZENG Haiyang. The research on simulation analysis and experimental evaluation for off-road tires driving performance on sand terrain[D]. Guangzhou: South China University of Technology, 2020.
[45]	刘常青, 沈阿荣. 影响车辆越野机动能力的因素研究[J]. 汽车实用技术, 2018, 43(19): 259-260.
	LIU Changqing, SHEN Arong. Study on the factors affecting the maneuverability of vehicle cross-country[J]. Automobile Applied Technology, 2018, 43(19): 259-260.
[46]	王璋, 王磊, 张鸣凤, 等. 某越野车辆机动性仿真分析及评价[J]. 车辆与动力技术, 2021(2): 7-10, 17.
	WANG Zhang, WANG Lei, ZHANG Mingfeng, et al. The research on mobility of an off-road vehicle[J]. Vehicle & Power Technology, 2021(2): 7-10, 17.
[47]	FRANSEN K, VAN EEKELEN J. Efficient path planning for automated guided vehicles using A^* (Astar) algorithm incorporating turning costs in search heuristic[J]. International Journal of Production Research, 2023, 61(3): 707-725.
[48]	SUGIANTI N, MARDHIYAH A, FADILAH N R. Komparasi kinerja algoritma BFS, Dijkstra, greedy BFS, dan A^* dalam melakukan pathfinding[J]. JISKA (Jurnal Informatika Sunan Kalijaga), 2020, 5(3): 194-205.

一级分类	二级分类	描述
地表影响因子	土壤性质	土壤砾石、沙粒、粉粒、黏粒、容重、含水量等
地表影响因子	地表覆盖类型道路	建筑物、草地、林地、裸地、水系等高速公路、省道、普通公路等
地形影响因子	高程	某点沿垂线方向至绝对基准面的距离
地形影响因子	地表起伏坡度	单位面积内最大相对高程差地面某点法线与铅垂线之间的夹角

准则要素	影响权重	子准则要素	子影响权重
土壤性质	0.042	土壤砾石含量	0.030
		土壤沙粒含量	0.030
		土壤粉粒含量	0.113
		土壤黏粒含量	0.198
		土壤容重	0.568
		土壤含水量	0.061
地表覆盖类型	0.212	草地	0.202
		林地（密）	0.021
		林地（疏）	0.078
		裸地	0.388
		水田	0.031
		旱地	0.280
道路	0.516
高程	0.029
地表起伏	0.075
坡度	0.127

准则要素	土壤性质	地表覆盖类型	道路	高程	地表起伏	坡度
土壤性质	1.000	0.200	0.125	2.000	0.333	0.250
地表覆盖类型	5.000	1.000	0.200	6.000	4.000	3.000
道路	8.000	5.000	1.000	9.000	7.000	6.000
高程	0.500	0.167	0.111	1.000	0.250	0.200
地表起伏	3.000	0.250	0.143	4.000	1.000	0.333
坡度	4.000	0.333	0.167	5.000	3.000	1.000

准则要素	一致性检验
土壤性质	λ_max=6.574
土壤性质	C. R.=0.092
地表覆盖类型	λ_max=6.417
地表覆盖类型	C. R.=0.067

准则要素	界定范围	速度系数
高程	<2000 m	0.800 4
	[2000，5000]m	0.124 4
	>5000 m	0.075 3
地表起伏	（0，20]m	0.900 0
地表起伏	（20，150]m	0.100 0
坡度	（0°，10°]	0.900 0
坡度	（10°，25°]	0.100 0