引入必经点约束的智能汽车全局路径规划

doi:10.19562/j.chinasae.qcgc.2023.03.002

Abstract

Abstract:

At present， most of the research on the global path planning of intelligent vehicles only focuses on the situation from the beginning to the end. To solve this problem， this paper combines the improved A* and simulated annealing algorithm， and designs a global path planning algorithm that introduces in the constraint of must-pass nodes. Firstly， the shortest path between key nodes is calculated and saved based on the A* algorithm. Then， based on the simulated annealing algorithm in the heuristic algorithm， the global path through the must-pass nodes is iteratively and randomly optimized. Then， the validity and time complexity of the algorithm are tested and analyzed based on the real high-precision map. The results show that the designed algorithm has good performance in solving speed and solving quality. Finally， the effectiveness and adaptability of the algorithm are further verified by the real vehicle test.

Key words: intelligent vehicle, global path planning, must-pass nodes, A* algorithm, simulated annealing algorithm

Jie Hu,Qi Zhu,Ruipeng Chen,Minchao Zhang,Zhihao Zhang,Haoyan Liu. Global Path Planning of Intelligent Vehicle with Must-Pass Nodes[J].Automotive Engineering, 2023, 45(3): 350-360.

Figures/Tables 18

References 19

1	王梓强，胡晓光，李晓筱，等. 移动机器人全局路径规划算法综述［J］. 计算机科学， 2021， 48（10）： 19-29.
	WANG Z Q， HU X G， LI X X， et al. Overview of global path planning algorithms for mobile robots［J］. Computer Science， 2021， 48（10）： 19-29.
2	DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik， 1959， 1：269-271.
3	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.
4	LAVALLE S M. Rapidly-exploring random trees： a new tool for path planning［J］. Computer Science Dept. Iowa State University， Tech. Rep. TR 98-11， 1998.
5	SUN J， TANG J， LAO S. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm［J］. IEEE Access， 2017， 5： 18382-18390.
6	李文刚，汪流江，方德翔，等. 联合A*与动态窗口法的路径规划算法［J］. 系统工程与电子技术， 2021， 43（12）： 3694-3702.
	LI W G， WANG S J， FANG D X， et al. Path planning algorithm combining A* with DWA［J］. Systems Engineering and Electronics， 2021， 43（12）： 3694-3702.
7	李全勇，李波，张瑞，等. 基于改进Dijkstra算法的AGV路径规划研究［J］. 机械工程与自动化， 2021（1）： 23-25， 28.
	LI Q Y， LI B， ZHANG R， et al. Research on AGV path planning based on improved Dijkstra algorithm［J］. Mechanical Engineering & Automation， 2021（1）： 23-25， 28.
8	XUE Y， ZHANG X， JIA S， et al. Hybrid bidirectional rapidly-exploring random trees algorithm with heuristic target graviton［C］. 2017 Chinese Automation Congress （CAC） 2017： 4357-4361.
9	JEONG I B， LEE S J， KIM J H. Quick-RRT： triangular inequality-based implementation of RRT with improved initial solution and convergence rate［J］. Expert Systems with Applications， 2019， 123： 82-90.
10	周盛世，单梁，常路，等. 基于改进DDPG算法的机器人路径规划算法研究［J］. 南京理工大学学报（自然科学版）， 2021， 45（3）： 265-270， 287.
	ZHOU S S， SHAN L， CHANG L， et al. Robot path planning algorithm based on improved DDPG algorithm［J］. Journal of Nanjing University of Science and Technology， 2021， 45（3）： 265-270， 287.
11	李瑞林. 基于深度强化学习的无人车路径规划研究［D］. 哈尔滨：哈尔滨工业大学， 2020.
	LI R L. Research on path planning method of unmanned vehicle based on deep reinforcement learning［D］.Harbin ： Harbin Institute of Technology，2020.
12	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法［J］. 计算机工程与应用， 2015（11）： 41-46.
	HUANG S L， HU D S， JIANG Y M. Algorithm for finding shortest path which must go through specified intermediate node set［J］. Computer Engineering and Applications， 2015（11）： 41-46.
13	康文雄，许耀钊. 节点约束型最短路径的分层Dijkstra算法［J］. 华南理工大学学报（自然科学版）， 2017， 45（1）： 66-73.
	KANG W X， XU Y Z. A hierarchical Dijkstra algorithm for solving shortest path from constrained nodes［J］. Journal of South China University of Technology （Natural Science Edition）， 2017， 45（1）： 66-73.
14	张军琛. 启发式算法求解带必经节点最短路问题研究［D］. 武汉：华中科技大学， 2018.
	ZHANG J C. A Heuristic algorithm for shortest path problem with must-pass nodes［D］. Wuhan： Huazhong University of Science and Technology， 2018.
15	徐庆征，柯熙政. 必经点最短路径问题模型及相应遗传算法研究［J］. 系统工程与电子技术， 2009， 31（2）： 459-462.
	XU Q Z， KE X Z. Models and genetic algorithm for designated-points shortest path problem［J］. Systems Engineering and Electronics， 2009， 31（2）： 459-462.
16	刘志，林坚海，金拓. 基于改进遗传算法的必经点最短路径算法［J］. 信息通信， 2017（2）： 46-48.
	LIU Z， LIN J H， JIN T. The shortest path algorithm based on improved genetic algorithm［J］. Information & Communications， 2017（2）： 46-48.
17	冯琳耀，袁林旺，罗文，等. 节点约束型最短路径的几何代数算法［J］. 电子学报， 2014（5）： 846-851.
	FENG L Y， YUAN L W， LUO W， et al. Geometric algebra-based algorithm for solving nodes constrained shortest path［J］. Acta Electronica Sinica， 2014（5）： 846-851.
18	GOMES T， MARTINS L， FERREIRA S， et al. Algorithms for determining a node-disjoint path pair visiting specified nodes［J］. Optical Switching and Networking， 2017， 23（2）： 189-204.
19	王磊，孙力帆. 引入必经点约束的路径规划算法研究［J］. 计算机工程与应用， 2020， 56（21）： 25-29.
	WANG L， SUN L F. Research on path planning algorithm with obligatory node constraint［J］. Computer Engineering and Applications， 2020， 56（21）： 25-29.

[1]	LI Ling, MA Li, MOU Yu, XU Chao, LI Wen-Ru, SHI Shu-Ming. [J]. , 2016, 38(12): 1508 -1514 .
[2]	QIN Xiao-Hui, WANG Jian-Qiang, XIE Bo-Yuan, HU Man-Jiang, LI Ke-Qiang. [J]. , 2017, 39(1): 73 -78 .
[3]	SU Chang, FU Li-Ming, WEI Jun, CAO Yue, HUANG Lei, LI Shuo. [J]. , 2017, 39(1): 35 -40 .
[4]	ZHANG Jian, ZHOU Dao-Kui, TONG Rui, QI Hao-Chen. [J]. , 2017, 39(1): 47 -51 .
[5]	ZHENG Wei. [J]. , 2017, 39(1): 107 -112 .
[6]	SHAO Shi-Ping, HUANG Ju-Hua, CAO Ming. [J]. , 2017, 39(2): 200 -205 .
[7]	Chen-Xin, FENG Xiao, SHEN Chuan-Liang, WANG Shuo, HU Cui-Song, LI Yan-Yang, YANG Chang-Hai-　. [J]. , 2017, 39(2): 206 -213 .
[8]	CAO Li-Bo, CHEN Zheng, YAN Ling-Bo, QIN Qin, ZHANG Rui-Feng. [J]. , 2017, 39(2): 225 -231 .
[9]	HONG Qiu-Cai, LIU Wei-Guo, ZHOU Da-Yong. [J]. , 2017, 39(2): 232 -236 .
[10]	XU Feng-Xiang, TIAN Xuan-Yi. [J]. , 2017, 39(2): 237 -242 .

必经节点数量	最优解	算法1		算法2		算法3		算法4		本文算法
必经节点数量	长度/m	平均长度/m	平均耗时/s	平均长度/m	平均耗时/s	平均长度/m	平均耗时/s	平均长度/m	平均耗时/s	平均长度/m	平均耗时/s
5	773.4	773.4	0.113	773.4	0.004	773.4	0.021	773.4	0.009	773.4	0.011
6	921.7	921.7	0.723	921.7	0.008	921.7	0.156	961.3	0.022	921.7	0.019
7	980.3	980.3	5.659	980.3	0.028	980.3	0.493	980.3	0.021	980.3	0.026
8	1 042.3	1 042.3	50.25	1 042.3	0.198	1 042.3	0.726	1 042.3	0.155	1 042.3	0.145
9	1 101.5		>180	1 101.5	1.729	1 101.5	0.981	1 140.3	0.236	1 101.5	0.279
10	1 110.8		>180	1 110.8	16.22	1 110.8	1.079	1 110.8	0.291	1 110.8	0.319
15	1 365.7		>180		>180	1 504.7	2.936	1 472.3	0.622	1 365.7	0.501
20	1 760.1		>180		>180	1 926.4	6.143	1 904.1	1.020	1 885.3	0.922

必经节点数量	实验次数	获最优解次数	解的平均长度/m	解的标准差	最优解的长度/m
5	20	20	773.4	0	773.4
6	20	20	921.7	0	921.7
7	20	20	980.3	0	980.3
8	20	20	1 042.3	0	1 042.3
9	20	20	1 101.5	0	1 101.5
10	20	20	1 110.8	0	1 110.8
15	20	17	1 393.6	74.9	1 365.7
20	20	13	1 839.5	136.1	1 760.1

[1]	Jianping Hao,Yanzhao Su,Zhihua Zhong,Jin Huang. Service-Oriented Architecture and Service Scheduling Mechanism for Intelligent Vehicles [J]. Automotive Engineering, 2023, 45(9): 1563-1572.
[2]	Gaoshi Zhao,Long Chen,Yingfeng Cai,Yubo Lian,Hai Wang,Qingchao Liu,Chenglong Teng. Trajectory Prediction Technology Integrating Complex Network and Memory-Augmented Network [J]. Automotive Engineering, 2023, 45(9): 1608-1616.
[3]	Lin Hu,Gen Li,Fang Wang,Miao Lin,Ning Wu. Research on Test Scenarios of Passenger Cars and Two-Wheelers at Intersections Based on CIDAS Accident Data [J]. Automotive Engineering, 2023, 45(8): 1417-1427.
[4]	Qihui Hu,Yingfeng Cai,Hai Wang,Long Chen,Zhaozhi Dong,Qingchao Liu. Heterogeneous Multi-object Trajectory Prediction Method Based on Hierarchical Graph Attention [J]. Automotive Engineering, 2023, 45(8): 1448-1456.
[5]	Shiju Pan, Jianshi Li, Hua Li, Jingtao Lou, Youchun Xu. Path Following Method of Intelligent Vehicles Based on Feedback Pure Tracking Method [J]. Automotive Engineering, 2023, 45(7): 1134-1144.
[6]	Jun Li, Wei Zhou, Shuang Tang. Lane Change and Obstacle Avoidance Trajectory Planning of Intelligent Vehicle Based on Adaptive Fitting [J]. Automotive Engineering, 2023, 45(7): 1174-1183.
[7]	Zixian Li,Shiju Pan,Yuan Zhu,Binbing He,Youchun Xu. Semi-active Suspension Control for Intelligent Vehicles Based on State Feedback and Preview Feedforward [J]. Automotive Engineering, 2023, 45(5): 735-745.
[8]	Xiang Gao,Long Chen,Xinye Wang,Xiaoxia Xiong,Yicheng Li,Yuexia Chen. Intelligent Vehicle Driving Risk Assessment Method Based on Trajectory Prediction [J]. Automotive Engineering, 2023, 45(4): 588-597.
[9]	Manjiang Hu,Binjie Mou,Zeyu Yang,Yougang Bian,Xiaohui Qin,Biao Xu. A Hybrid A* Path Planning Method Based on DBSCAN and Dichotomy [J]. Automotive Engineering, 2023, 45(3): 341-349.
[10]	Lü Yanzhi,Chao Wei,Yuanhao He. An End-to-End Lane Change Method for Autonomous Driving Based on GCN and CIL [J]. Automotive Engineering, 2023, 45(12): 2310-2317.
[11]	Shiju Pan,Yongle Li,Zixian Li,Binbing He,Yuan Zhu,Youchun Xu. Path Following Method of Intelligent Vehicles Based on Improved Pure Tracking [J]. Automotive Engineering, 2023, 45(1): 1-8.
[12]	Shulian Zhao,Fei Lai,Keqiang Li,Tao Chen,Zhangjie Meng,Yichao Tang,Siyu Wu,Haodong Tian. Research on Intelligent Vehicle Test Method Based on Digital Twin Technology [J]. Automotive Engineering, 2023, 45(1): 42-51.
[13]	Wenbo Shao,Jun Li,Yuxin Zhang,Hong Wang. Key Technologies to Ensure the Safety of the Intended Functionality for Intelligent Vehicles [J]. Automotive Engineering, 2022, 44(9): 1289-1304.
[14]	Zihao Wang,Yingfeng Cai,Hai Wang,Long Chen,Xiaoxia Xiong. Surrounding Multi-Target Trajectory Prediction Method Based on Monocular Visual Motion Estimation [J]. Automotive Engineering, 2022, 44(9): 1318-1326.
[15]	Wang Liang,Zhaobo Qin,Liang Chen,Yougang Bian,Manjiang Hu. Longitudinal Control Method of Intelligent Vehicles Based on the Improved BP Neural Network [J]. Automotive Engineering, 2022, 44(8): 1162-1172.

Global Path Planning of Intelligent Vehicle with Must-Pass Nodes

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 19

Related Articles 15

Metrics

Comments

Recommended 10