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

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

摘要/Abstract

摘要：

为提高规划主体在复杂环境中运动的通过可行性和安全可靠性, 解决路网环境通常不连续和主体大小普遍未计算的问题, 基于连续路网环境提出了一种实体化主体路径规划算法。首先根据环境信息和主体大小, 采用融合膨胀的策略构建实体化主体连续环境模型(model continuous environment with subject objective, MCESO), 然后采取路网优先(road network priority, RNP)策略, 在实体化主体连续环境下利用骨架提取技术得到路网信息, 最后以经典A* 算法为例, 将上述模型融合改进, 提出一种路径规划MCESO-RNP-A* 算法。仿真实验结果表明, 建模方案和规划算法能够使得实体化主体在连续路网环境下安全顺利到达规划指定目标点, 并且在大范围环境下相较MCE-A* 算法生成路径的时间可降低约30%, 验证了算法的可行性和有效性。

关键词: 连续路网环境, 实体化主体, 路径规划, 双向A* 算法

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

中图分类号:

TP242

刘钢, 安志镖, 张茂军, 刘煜, 李武. 基于连续路网环境的实体化主体路径规划算法[J]. 系统工程与电子技术, 2024, 46(4): 1346-1356.

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.

图/表 28

图1

图2

图3

图4

图5

图6

图7

图8

表1

图9

图10

图11

图12

图13

图14

图15

图16

图17

图18

图19

图20

图21

图22

图23

图24

图25

表2

表3

参考文献 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]	赵贵祥, 周健, 李云淼, 王晨旭. 改进双向快速搜索随机树的无人艇路径规划[J]. 系统工程与电子技术, 2024, 46(4): 1364-1371.
[2]	李广强, 董文超, 朱大庆, 于越, 陈浩, 于双和. 基于改进鲸鱼优化算法的AUV三维路径规划[J]. 系统工程与电子技术, 2023, 45(7): 2170-2182.
[3]	刘瑶, 夏阳升, 石建迈, 陈超, 黄金才. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45(5): 1380-1390.
[4]	韩维, 刘子玄, 苏析超, 崔凯凯, 刘洁. 结合启发式与最优控制的舰载机甲板路径规划算法[J]. 系统工程与电子技术, 2023, 45(4): 1098-1110.
[5]	张浩杰, 张玉东, 梁荣敏, 杨甜甜. 改进A^*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.
[6]	吴靖宇, 朱世强, 宋伟, 施浩磊, 吴泽南. 基于改进单元分解法的全覆盖路径规划[J]. 系统工程与电子技术, 2023, 45(12): 3949-3957.
[7]	赵贵祥, 王晨旭, 王贺平, 李云淼. 改进速度障碍法的无人艇局部路径规划[J]. 系统工程与电子技术, 2023, 45(12): 3975-3983.
[8]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[9]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[10]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[11]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[12]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[13]	王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
[14]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[15]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.