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

doi:10.19562/j.chinasae.qcgc.2023.03.002

摘要/Abstract

摘要：

目前对于智能车全局路径规划的研究多数只针对从起点到终点的情况。针对该问题，本文中融合改进A*和模拟退火算法，设计了一种引入必经点约束的全局路径规划算法。首先，基于A*算法计算关键节点间的最短路径并保存。然后，基于启发式算法中的模拟退火算法对过必经节点的全局路径进行迭代随机优化。接着，基于真实高精度地图对算法的有效性以及时间复杂度进行实验分析。结果表明，设计的算法在求解质量和求解速度方面都有较好的表现。最后，通过实车实验，进一步验证了算法的有效性和适应性。

关键词: 智能汽车, 全局路径规划, 必经节点, A*算法, 模拟退火算法

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

胡杰,朱琪,陈锐鹏,张敏超,张志豪,刘昊岩. 引入必经点约束的智能汽车全局路径规划[J]. 汽车工程, 2023, 45(3): 350-360.

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.

图/表 18

图1

图2

图3

图4

表1

表2

图5

图6

图7

图8

表3

表4

图9

图10

图11

图12

图13

图14

参考文献 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		算法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]	郝建平,苏炎召,钟志华,黄晋. 面向智能汽车的SOA架构及服务调度机制研究[J]. 汽车工程, 2023, 45(9): 1563-1572.
[2]	赵高士,陈龙,蔡英凤,廉玉波,王海,刘擎超,滕成龙. 融合复杂网络和记忆增强网络的轨迹预测技术[J]. 汽车工程, 2023, 45(9): 1608-1616.
[3]	胡启慧,蔡英凤,王海,陈龙,董钊志,刘擎超. 基于层次图注意的异构多目标轨迹预测方法[J]. 汽车工程, 2023, 45(8): 1448-1456.
[4]	高翔,陈龙,王歆叶,熊晓夏,李祎承,陈月霞. 基于轨迹预测的智能汽车行驶风险评估方法[J]. 汽车工程, 2023, 45(4): 588-597.
[5]	胡满江,牟斌杰,杨泽宇,边有钢,秦晓辉,徐彪. 基于DBSCAN与二分法的混合A*路径规划方法[J]. 汽车工程, 2023, 45(3): 341-349.
[6]	张紫微,郑玲,李以农,乔旭强,郑浩,王戡. 考虑前车运动不确定性的多目标自适应巡航控制[J]. 汽车工程, 2023, 45(3): 361-371.
[7]	刘正发,吴亚,刘佩根,顾荣琦,陈广. 基于特征和标签联合分布匹配的智能驾驶跨域自适应目标检测[J]. 汽车工程, 2023, 45(11): 2082-2091.
[8]	赵树廉,来飞,李克强,陈涛,孟璋劼,唐逸超,吴思宇,田浩东. 基于数字孪生技术的智能汽车测试方法研究[J]. 汽车工程, 2023, 45(1): 42-51.
[9]	邵文博,李骏,张玉新,王红. 智能汽车预期功能安全保障关键技术[J]. 汽车工程, 2022, 44(9): 1289-1304.
[10]	汪梓豪,蔡英凤,王海,陈龙,熊晓夏. 基于单目视觉运动估计的周边多目标轨迹预测方法[J]. 汽车工程, 2022, 44(9): 1318-1326.
[11]	梁旺,秦兆博,陈亮,边有钢,胡满江. 基于改进BP神经网络的智能车纵向控制方法[J]. 汽车工程, 2022, 44(8): 1162-1172.
[12]	赵健,宋东鉴,朱冰,吴杭哲,韩嘉懿,刘宇翔. 数据机理混合驱动的交通车意图识别方法[J]. 汽车工程, 2022, 44(7): 997-1008.
[13]	余嘉星,Aliasghar Arab,裴晓飞,过学迅. 考虑路径平滑性和避撞稳定性的智能汽车弯道轨迹规划研究[J]. 汽车工程, 2022, 44(5): 656-663.
[14]	江浩斌,冯张棋,洪阳珂,韦奇志,皮健. 应用于车辆纵向控制的无模型自适应滑模预测控制方法[J]. 汽车工程, 2022, 44(3): 319-329.
[15]	宋东鉴,朱冰,赵健,韩嘉懿,刘彦辰. 基于驾驶行为生成机制的智能汽车类人行为决策[J]. 汽车工程, 2022, 44(12): 1797-1808.