汽车工程 ›› 2023, Vol. 45 ›› Issue (3): 350-360.doi: 10.19562/j.chinasae.qcgc.2023.03.002
所属专题: 智能网联汽车技术专题-规划&决策2023年
收稿日期:
2022-08-04
修回日期:
2022-09-04
出版日期:
2023-03-25
发布日期:
2023-03-22
通讯作者:
胡杰
E-mail:auto_hj@163.com
基金资助:
Jie Hu(),Qi Zhu,Ruipeng Chen,Minchao Zhang,Zhihao Zhang,Haoyan Liu
Received:
2022-08-04
Revised:
2022-09-04
Online:
2023-03-25
Published:
2023-03-22
Contact:
Jie Hu
E-mail:auto_hj@163.com
摘要:
目前对于智能车全局路径规划的研究多数只针对从起点到终点的情况。针对该问题,本文中融合改进A*和模拟退火算法,设计了一种引入必经点约束的全局路径规划算法。首先,基于A*算法计算关键节点间的最短路径并保存。然后,基于启发式算法中的模拟退火算法对过必经节点的全局路径进行迭代随机优化。接着,基于真实高精度地图对算法的有效性以及时间复杂度进行实验分析。结果表明,设计的算法在求解质量和求解速度方面都有较好的表现。最后,通过实车实验,进一步验证了算法的有效性和适应性。
胡杰,朱琪,陈锐鹏,张敏超,张志豪,刘昊岩. 引入必经点约束的智能汽车全局路径规划[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.
表1
算法第1部分的伪代码"
算法第1部分:求解关键路径并保存 | |
---|---|
输入:存有地图的邻接链表G,必经节点集Vm,起始节点Nbegin,目标节点Nend 输出:存有关键路径的哈希表key_path_map | |
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: | Vm_length=len(Vm) fori in range(Vm_length) do forj in range(Vm_length) do ifi==jthen continue end if mid_key_path=A_star(Vm[i], Vm[j], G) key_path_map[{Vm[i], Vm[j]}]=mid_key_path end for end for for each node N in Vmdo begin_key_path=A_star(Nbegin, N, G) end_key_path=A_star(N, Nend, G) key_path_map[{Nbegin, N}]=begin_key_path key_path_map[{N, Nend}]=end_key_path end for |
表2
算法第2部分的伪代码"
算法第2部分:对待选全局路径进行迭代随机优化 | |
---|---|
输入:存有关键路径的哈希表key_path_map, 模拟退火算法的参数T、α、L、Ts,必经节点集Vm,起始节点Nbegin,目标节点Nend 输出:最短路径及其对应长度path0 | |
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: | S0=Vm length=len(S0) begin_path=key_path_map[{Nbegin, S0[0]}] mid_path=get_mid_path(S0) end_path=key_path_map[{S0[length-1], Nend}] path0=path_splice(begin_path,mid_path,end_path) cost0=res_path[0] whileT >= Ts do k=0 whilek<Ldo Snew=get_next_sequence(S0) b_path=key_path_map[{Nbegin, Snew[0]}] m_path=get_mid_path(Snew) e_path=key_path_map[{Snew[length-1],Nend}] pathnew=path_splice(b_path,m_path,e_path) costnew=t_path[0] ifcostnew<cost0 or random(0,1)<Pthen path0= pathnew S0=Snew cost0=costnew end if k=k+1 end while T=T*α end while |
表3
算法对比实验结果"
必经节 点数量 | 最优解 | 算法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 |
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] | 郝建平,苏炎召,钟志华,黄晋. 面向智能汽车的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. |
|