基于连续路网环境的实体化主体路径规划算法

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

Abstract

Abstract:

In order to improve the passage feasibility and safety reliability of the movement of the planning subject in a complex environment, and solve the problems of the usually discontinuous road network environment and the general uncalculated size of the subject, a subject objective path planning algorithm based on the continuous road network environment is proposed. Firstly, according to the environment information and subject size, the fusion expansion strategy is used to construct the model continuous environment (MCE) with subject objective (MCESO). Then, the road network priority (RNP) strategy is adopted, and the skeleton extraction technology is used to obtain the road network information in the continuous environment of the subject objective. Finally, the classical A* algorithm is taken as an example, the above model is fused and improved, and a path planning MCESO-RNP-A* algorithm is proposed. Simulation results show that the modeling scheme and planning algorithm can enable the subject objective to reach the target point specified in the planning smoothly in the continuous road network environment, and the time to generate the path can be reduced by about 30% compared with the MCE-A* algorithm in a large range environment, which verifies the feasibility and effectiveness of the algorithm.

Key words: continuous road network environment, subject objective, path planning, bidirectional A* algorithm

CLC Number:

TP242

Gang LIU, Zhibiao AN, Maojun ZHANG, Yu LIU, Wu LI. Subject objective path planning algorithm based on continuous road network environment[J]. Systems Engineering and Electronics, 2024, 46(4): 1346-1356.

Figures/Tables 28

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Table 1

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

Fig.19

Fig.20

Fig.21

Fig.22

Fig.23

Fig.24

Fig.25

Table 2

Table 3

References 32

1	周梦如, 陈慧岩, 熊光明, 等. 越野环境下无人履带平台的道路可通行性分析[J]. 兵工学报, 2022, 43 (10): 2485- 2496.
	ZHOU M R , CHEN H Y , XIONG G M , et al. Road traversability analysis of unmanned tracked platform in off-road environment[J]. Acta Armamentarii, 2022, 43 (10): 2485- 2496.
2	PAPADAKIS P . Terrain traversability analysis methods for unmanned ground vehicles: a survey[J]. Engineering Applications of Artificial Intelligence, 2013, 26 (4): 1373- 1385. doi: 10.1016/j.engappai.2013.01.006
3	HOSSEINPOOR S, TORRESEN J, MANTELLI M, et al. Traversability analysis by semantic terrain segmentation for mobile robots[C]//Proc. of the IEEE 17th International Conference on Automation Science and Engineering, 2021: 1407-1413.
4	ALIREZA M , VINCENT D , TONY W . Experimental study of path planning problem using EMCOA for a holonomic mobile robot[J]. Journal of Systems Engineering and Electronics, 2021, 32 (6): 1450- 1462. doi: 10.23919/JSEE.2021.000123
5	YAO X L , WANG F , WANG J F , et al. Bilevel optimization-based time-optimal path planning for AUVs[J]. Sensors, 2018, 18 (12): 4167- 4183. doi: 10.3390/s18124167
6	LOZANO-PEREZ T , WESLEY M A . An algorithm for planning collision-free paths among polyhedral obstacles[J]. Communications of the ACM, 1979, 22 (10): 560- 570. doi: 10.1145/359156.359164
7	马随阳, 余永周, 吕英豪. 动态规划算法对航道岸线中无人机测绘路径的优化[J]. 中国水运, 2022, 22 (10): 76- 78.
	MA S Y , YU Y Z , LYU Y H . Optimisation of UAV mapping paths in fairway shorelines by dynamic programming algorithms[J]. China Water Transport, 2022, 22 (10): 76- 78.
8	彭小丹. 改进可视图的路径规划算法[J]. 现代信息科技, 2021, 5 (3): 152-154, 158.
	PENG X D . Improved visibility graph path planning algorithm[J]. Modern Information Technology, 2021, 5 (3): 152-154, 158.
9	贾正荣, 王航宇, 卢发兴. 基于障碍凸化的改进环流APF路径规划[J]. 航空学报, 2019, 40 (10): 254- 268.
	JIA Z R , WANG H Y , LU F X . Improved circulating APF route planning based on obstacle convexification[J]. Acta Aeronautica et Astronautica Sinica, 2019, 40 (10): 254- 268.
10	NIU H , SAVVARIS A , TSOURDOS A , et al. Voronoi-visibility roadmap-based path planning algorithm for unmanned surface vehicles[J]. The Journal of Navigation, 2019, 72 (4): 850- 874. doi: 10.1017/S0373463318001005
11	朱建阳, 张旭阳, 蒋林, 等. 基于骨架关键点重规划的Voronoi图法路径规划[J]. 农业机械学报, 2022, 53 (3): 215-224, 250.
	ZHU J Y , ZHANG X Y , JIANG L , et al. Voronoi diagram path planning based on skeleton key points replanning[J]. Transactions of the Chinese Society for Agricultural Machinery, 2022, 53 (3): 215-224, 250.
12	LIU C G , MAO Q Z , CHU X M , et al. An improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning[J]. Applied Sciences, 2019, 9 (6): 1057- 1074. doi: 10.3390/app9061057
13	LUO M , HOU X R , YANG J . Surface optimal path planning using an extended Dijkstra algorithm[J]. IEEE Access, 2020, 8, 147827- 147838. doi: 10.1109/ACCESS.2020.3015976
14	李文刚, 汪流江, 方德翔, 等. 联合A* 与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43 (12): 3694- 3702.
	LI W G , WANG L J , FANG D X , et al. Path planning algotithm combining A* with DWA[J]. Systems Engineering and Electronics, 2021, 43 (12): 3694- 3702.
15	张浩杰, 张玉东, 梁荣敏, 等. 改进A* 算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45 (2): 513- 520.
	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.
16	张伟民, 张月, 张辉. 基于改进A* 算法的煤矿救援机器人路径规划[J]. 煤田地质与勘探, 2022, 50 (12): 185- 193.
	ZHANG W M , ZHANG Y , ZHANG H . Path planning of coal mine rescue robote based on improved A* algorithm[J]. Coal Geology & Exploration, 2022, 50 (12): 185- 193.
17	TANG G , TANG C Q , CLARAMUNT C , et al. Geometric A-star algorithm: an improved A-star algorithm for AGV path planning in a port environment[J]. IEEE Access, 2021, 9, 59196- 59210. doi: 10.1109/ACCESS.2021.3070054
18	刘钢, 老松杨, 袁灿, 等. 反舰导弹航路规划的OACRR-PSO算法[J]. 自动化学报, 2012, 38 (9): 1528- 1537.
	LIU G , LAO S Y , YUAN C , et al. OACRR-PSO algorithm for anti-ship missile path planning[J]. Acta Automatica Sinica, 2012, 38 (9): 1528- 1537.
19	LUO Q , WANG H B , ZHENG Y , et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Neural Computing Applications, 2020, 32 (6): 1555- 1566. doi: 10.1007/s00521-019-04172-2
20	ZHANG L Y , ZHANG R X . Research on UAV cloud control system based on ant colony algorithm[J]. Journal of Systems Engineering and Electronics, 2022, 33 (4): 805- 811. doi: 10.23919/JSEE.2022.000080
21	LAMINI C , BENHLIMA S , ELBEKRI A . Genetic algorithm based approach for autonomous mobile robot path planning[J]. Procedia Computer Science, 2018, 127, 180- 189. doi: 10.1016/j.procs.2018.01.113
22	LIANG S B , JIAO T T , DU W C , et al. An improved ant co-lony optimization algorithm based on context for tourism route planning[J]. PLoS One, 2021, 16 (9): e0257317. doi: 10.1371/journal.pone.0257317
23	LIN Z N , YUE M , CHEN G Y , et al. Path planning of mobile robot with PSO-based APF and fuzzy-based DWA subject to moving obstacles[J]. Transactions of the Institute of Measurement, 2022, 44 (1): 121- 132. doi: 10.1177/01423312211024798
24	XU B J , ZHAO K X , LUO Q Z , et al. A GV-drone arc routing approach for urban traffic patrol by coordinating a ground vehicle and multiple drones[J]. Swarm Evolutionary Computation, 2023, 77, 101246. doi: 10.1016/j.swevo.2023.101246
25	LIU H , LI X M , FAN M F , et al. An autonomous path planning method for unmanned aerial vehicle based on a tangent intersection and target guidance strategy[J]. IEEE Trans.on Intelligent Transportation Systems, 2020, 23 (4): 3061- 3073.
26	LIU H , LI X M , WU G H , et al. An iterative two-phase optimization method based on divide and conquer framework for integrated scheduling of multiple UAVs[J]. IEEE Trans.on Intelligent Transportation Systems, 2020, 22 (9): 5926- 5938.
27	YANG Y , LI J T , PENG L L . Multi-robot path planning based on a deep reinforcement learning DQN algorithm[J]. CAAI Transactions on Intelligence Technology, 2020, 5 (3): 177- 183. doi: 10.1049/trit.2020.0024
28	LEI X Y , ZHANG Z A , DONG P F . Dynamic path planning of unknown environment based on deep reinforcement learning[J]. Journal of Robotics, 2018, 5781591.
29	GUO S Y , ZHANG X G , ZHENG Y S , et al. An autonomous path planning model for unmanned ships based on deep reinforcement learning[J]. Sensors, 2020, 20 (2): 426- 461. doi: 10.3390/s20020426
30	WANG B Y , LIU Z , LI Q B , et al. Mobile robot path planning in dynamic environments through globally guided reinforcement learning[J]. IEEE Robotics, 2020, 5 (4): 6932- 6939.
31	杨清清, 高盈盈, 郭玙, 等. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44 (11): 3486- 3495.
	YANG Q Q , GAO Y Y , GUO Y , et al. Target search path planning for naval battel field based on deep reinforcement learning[J]. Systems Engineering and Electronics, 2022, 44 (11): 3486- 3495.
32	闫星宇, 杜伟伟, 石昊. 基于通行性分析的分层越野路径规划方法[J]. 火力与指挥控制, 2022, 47 (5): 153- 158.
	YAN X Y , DU W W , SHI H . Research on hierarchical off-road path planning method based on trafficability analysis[J]. Fire Control and Command Control, 2022, 47 (5): 153- 158.

算法	环境建模	道路权重图
文献[21]	未进行环境建模	否
MCE-A*	连续环境模型	否
MCESO-A*	MCESO	否
MCESO-RNP-A*	MCESO	是

地图尺寸/m	经历的节点数			搜索时间/s			路径长度/m
地图尺寸/m	文献[21]算法	MCE-A*算法	MCESO-A*算法	文献[21]算法	MCE-A*算法	MCESO-A*算法	文献[21]算法	MCE-A*算法	MCESO-A*算法
100×100	364	345	547	1.353 1	0.149 3	0.132 6	582.45	509.36	843.82
250×250	802	781	829	2.307 2	0.262 4	0.229 2	1 126.18	1 067.58	1 292.26
500×500	765	680	1 321	4.808 2	0.562 8	0.525 8	1 436.28	1 386.73	1 868.76
750×750	3 358	3 287	3 536	6.482 4	2.615 9	1.450 4	4 792.63	4 745.84	4 409.34
1 500×1 500	6 924	5 655	8 716	9.547 5	3.974 8	2.387 2	8 290.12	7 266.2	1 1675.88

地图尺寸/m	MCE-A*	MCESO-A*	MCESO-RNP-A*	双向MCESO-RNP-A*
100×100	0.149 3	0.132 6	0.189 4	0.125 9
250×250	0.262 4	0.229 2	0.464 9	0.365 8
500×500	0.562 8	0.525 8	0.621 1	0.431 4
750×750	2.615 9	1.450 4	1.033 9	0.697 2
1 500×1 500	3.974 8	2.387 2	1.795 3	1.326 9

[1]	Guixiang ZHAO, Jian ZHOU, Yunmiao LI, Chenxu WANG. Improved bi-directional rapidly-exploring random tree path planning for USV [J]. Systems Engineering and Electronics, 2024, 46(4): 1364-1371.
[2]	Zihao CHEN, Juan LI, Chang LIU, Jie LI, Xiaoyu LIU. Task planning method for coordinated attacks on ground targets under time constraints [J]. Systems Engineering and Electronics, 2023, 45(8): 2353-2360.
[3]	Guangqiang LI, Wenchao DONG, Daqing ZHU, Yue YU, Hao CHEN, Shuanghe YU. 3D path planning for AUV based on improved whaleoptimization algorithm [J]. Systems Engineering and Electronics, 2023, 45(7): 2170-2182.
[4]	Liyao WU, Xichao SU, Lei WANG, Zishuang PAN. Research of formation rendezvous control for manned/unmanned aerial vehicles formation [J]. Systems Engineering and Electronics, 2023, 45(7): 2192-2202.
[5]	Yao LIU, Yangsheng XIA, Jianmai SHI, Chao CHEN, Jincai HUANG. Path planning method for multi-area coverage by cooperated ground vehicle multi-drone [J]. Systems Engineering and Electronics, 2023, 45(5): 1380-1390.
[6]	Qinglu WANG, Fengguo WU, Chengchen ZHENG, Hui LI. UAV path planning based on optimized artificial potential field method [J]. Systems Engineering and Electronics, 2023, 45(5): 1461-1468.
[7]	Wei HAN, Zixuan LIU, Xichao SU, Kaikai CUI, Jie LIU. Deck path planning algorithm of carrier-based aircraft based on heuristic and optimal control [J]. Systems Engineering and Electronics, 2023, 45(4): 1098-1110.
[8]	Haojie ZHANG, Yudong ZHANG, Rongmin LIANG, Tiantian YANG. Energy-efficient path planning method for robots based on improved A^* algorithm [J]. Systems Engineering and Electronics, 2023, 45(2): 513-520.
[9]	Jingyu WU, Shiqiang ZHU, Wei SONG, Haolei SHI, Zenan WU. Coverage path planning based on improved cellular decomposition [J]. Systems Engineering and Electronics, 2023, 45(12): 3949-3957.
[10]	Guixiang ZHAO, Chenxu WANG, Heping WANG, Yunmiao LI. Local path planning for unmanned surface vehicle using improved velocity obstacle method [J]. Systems Engineering and Electronics, 2023, 45(12): 3975-3983.
[11]	Zhi REN, Dong ZHANG, Shuo TANG. Improved three-dimensional A^* algorithm of real-time path planning based on reinforcement learning [J]. Systems Engineering and Electronics, 2023, 45(1): 193-201.
[12]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[13]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[14]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[15]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.

Subject objective path planning algorithm based on continuous road network environment

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 28

References 32

Related Articles 15

Recommended Articles

Metrics

Comments