基于DBSCAN与二分法的混合A*路径规划方法

doi:10.19562/j.chinasae.qcgc.2023.03.001

摘要/Abstract

摘要：

在多障碍物非结构化场景中，传统混合A*算法存在计算效率低、路径平滑性差的问题。针对该问题，本文提出了一种基于密度聚类算法（density-based clustering，简称DBSCAN）与二分法的混合A*路径规划方法。首先，设计基于DBSCAN算法的障碍物聚类方法，简化多障碍物非结构化场景，避免混合A*算法在类U形障碍物群附近的无效节点拓展，有效提高算法效率。然后，提出基于二分法的状态节点拓展策略，能够在不显著增加混合A*算法计算复杂度的前提下，搜索出一条更平滑的路径。最后，基于MATLAB进行仿真。结果表明，在多障碍物非结构化场景中，本文提出的改进混合A*算法可以显著提升计算效率并改善路径平滑性。

关键词: 自动驾驶, 路径规划, 混合A*算法, DBSCAN, 二分法

Abstract:

In the unstructured scene with multiple obstacles， the traditional hybrid A* algorithm has the problems of low computational efficiency and poor path smoothness. For these problems， this paper proposes a hybrid A* path planning method based on the density-based clustering （DBSCAN） and the dichotomy. Firstly， based on the DBSCAN algorithm， an obstacle clustering method is designed to simplify the multi-obstacle unstructured scene， so as to avoid invalid node expansion of the hybrid A* algorithm near the U-shaped obstacle group， and to effectively improve the efficiency of the algorithm. Then， a dichotomy-based state node expansion strategy is proposed， which can search a smoother path without significantly increasing the computational complexity of the hybrid A* algorithm. Finally， simulation is performed on MATLAB. The results show that in the multi-obstacle unstructured scene， the improved hybrid A* algorithm proposed in this paper can significantly improve the computational efficiency and the path smoothness.

Key words: automatic driving, path planning, hybrid A* algorithm, DBSCAN, dichotomy

胡满江,牟斌杰,杨泽宇,边有钢,秦晓辉,徐彪. 基于DBSCAN与二分法的混合A*路径规划方法[J]. 汽车工程, 2023, 45(3): 341-349.

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.

图/表 13

图1

图2

图3

图4

图5

图6

表1

图7

表2

图8

表3

图9

表4

参考文献 18

1	李柏.复杂约束下自动驾驶车辆运动规划的计算最优控制方法研究［D］. 杭州：浙江大学， 2018.
	LI B. Research on computational optimal control method for motion planning of autonomous vehicles under complex constraints ［D］. Hangzhou： Zhejiang University， 2018.
2	KUNCHEV V， JAIN L， IVANCEVIC V， et al. Path planning and obstacle avoidance for autonomous mobile robots： a review［C］. Knowledge-Based Intelligent Information and Engineering Systems： Vol. 4252. Berlin， Heidelberg： Springer Berlin Heidelberg， 2006： 537-544.
3	任秉韬，王淅淅，邓伟文，等. 基于混合A*和可变半径RS曲线的自动泊车路径优化方法［J］. 中国公路学报， 2022， 35（7）： 317-327.
	REN B T， WANG X X， DENG W W， et al. Automatic parking path optimization method based on hybrid A* and variable radius RS curve ［J］. Chinese Journal of Highways， 2022， 35（7）： 317-327.
4	SHENG W， LI B， ZHONG X. Autonomous parking trajectory planning with tiny passages： a combination of multistage hybrid A-star algorithm and numerical optimal control［J］. IEEE Access， 2021， 9： 102801-102810.
5	DOLGOV D， THRUN S， MONTEMERLO M， et al. Path planning for autonomous vehicles in unknown semi-structured environments［J］. The International Journal of Robotics Research， 2010， 29（5）： 485-501.
6	SEDIGHI S， NGUYEN D V， KUHNERT K D. Guided hybrid A-star path planning algorithm for valet parking applications［C］. Proceedings of the 2019 5th International Conference on Control， Automation and Robotics （ICCAR）. Beijing， China： IEEE， 2019： 570-575.
7	陈鑫鹏，徐彪，胡满江，等. 一种基于等步长分层拓展的混合A*路径规划方法［J］. 控制与信息技术， 2021（1）： 17-22，29.
	CHEN X P， XU B， HU M J， et al. A hybrid A* path planning method based on equal step hierarchical expansion ［J］. Control and Information Technology， 2021（1）： 17-22，29.
8	DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik， 1959， 1（1）： 269-271.
9	杨帆，徐彪. 多障碍物环境下智能车辆局部路径规划方法［J］. 控制与信息技术， 2019（5）： 1-6.
	YANG F， XU B. Local path planning method for intelligent vehicles in multiple obstacle environments ［J］. Control and Information Technology， 2019（5）： 1-6.
10	唐斌，许占祥，江浩斌，等. 基于分段优化的车辆换道避障轨迹规划［J］. 汽车工程， 2022， 44（6）： 831-841.
	TANG B， XU Z X， JIANG H B， et al. Vehicle lane changing and obstacle avoidance trajectory planning based on segmentation optimization ［J］. Automotive Engineering， 2022， 44（6）： 831-841.
11	KARAMAN S， FRAZZOLI E. Incremental sampling-based algorithms for optimal motion planning［J］. Robotics Science and Systems VI， 2010， 104（2）.
12	焦嵩鸣，陈雨溪，白健鹏. 改进Hybrid A*的拖挂式移动机器人路径规划算法［J］. 电子测量技术， 2022，45（16）：80-86.
	JIAO S M， CHEN Y X， BAI J P. Improved hybrid A* path planning algorithm for trailer mobile robot［J］. Electronic Measurement Technology， 2022，45（16）：80-86.
13	周维，过学迅，裴晓飞，等. 基于RRT与MPC的智能车辆路径规划与跟踪控制研究［J］. 汽车工程， 2020， 42（9）： 1151-1158.
	ZHOU W， GUO X X， PEI X F， et al. Research on intelligent vehicle path planning and tracking control based on RRT and MPC ［J］. Automotive Engineering， 2020， 42（9）： 1151-1158.
14	ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］. AAAI Press， 1996.
15	GRAHAM R L. An efficient algorith for determining the convex hull of a finite planar set［J］. Information Processing Letters， 1972， 1（4）： 132-133.
16	RAJAMANI R. Vehicle dynamics and control［M］. Springer Science & Business Media， 2011.
17	REEDS J， SHEPP L. Optimal paths for a car that goes both forwards and backwards［J］. Pacific Journal of Mathematics， 1990， 145（2）： 367-393.
18	EDELSBRUNNER H， KIRKPATRICK D， SEIDEL R. On the shape of a set of points in the plane［J］. IEEE Transactions on Information Theory， 1983， 29（4）： 551-559.

场景	参数	数值
构造场景（一般车辆模型）	轴距	2.85
	车长	4.94
	车宽	1.86
	左右单侧安全距离	0.1
矿区场景（矿卡模型）	轴距	4.675
	车长	9.308
	车宽	4.578
	左右单侧安全距离	0.4

场景地图	始末状态	算法类型	拓展节点数	计算时间/s
构造场景	状态1	传统混合A*	250	3.23
	状态1	聚类混合A*	100	1.91
	状态2	传统混合A*	580	3.73
	状态2	聚类混合A*	105	1.93
矿区场景	状态1	传统混合A*	170	2.65
	状态1	聚类混合A*	95	2.21
	状态2	传统混合A*	300	3.03
	状态2	聚类混合A*	100	2.25

场景	始末状态	拓展方式	航向角变化量累加值/rad
构造场景	始末状态1	传统拓展	4.073 4
	始末状态1	二分拓展	3.084 8
	始末状态2	传统拓展	4.918 1
	始末状态2	二分拓展	3.125 6
	始末状态3	传统拓展	8.293 1
	始末状态3	二分拓展	4.848 2
	始末状态4	传统拓展	4.389 6
	始末状态4	二分拓展	3.154 9
矿区场景	始末状态1	传统拓展	5.759 4
	始末状态1	二分拓展	4.969 5
	始末状态2	传统拓展	4.674 1
	始末状态2	二分拓展	3.683 0

场景	拓展方式	拓展子节点数	航向角变化量累加值/rad
构造场景	传统拓展（n=5）	100	4.073 4
	传统拓展（n=9）	180	3.166 6
	二分拓展	110	3.084 8
矿区场景	传统拓展（n=5）	105	5.759 4
	传统拓展（n=9）	180	4.790 2
	二分拓展	124	4.625 7

[1]	付新科,蔡英凤,陈龙,王海,刘擎超. 不确定性环境下的自动驾驶汽车行为决策方法[J]. 汽车工程, 2024, 46(2): 211-221.
[2]	赵晓聪,房世玉,李子睿,孙剑. 社会性驾驶交互关键效用析取与应用[J]. 汽车工程, 2024, 46(2): 230-240.
[3]	马艳丽, 秦钦, 董方琦, 娄艺苧. 基于风险场的不同认知次任务下接管风险评估模型[J]. 汽车工程, 2024, 46(1): 9-17.
[4]	刘卫国,项志宇,刘伟平,齐道新,王子旭. 基于分布式强化学习的车辆控制算法研究[J]. 汽车工程, 2023, 45(9): 1637-1645.
[5]	王明,唐小林,杨凯,李国法,胡晓松. 考虑预测风险的自动驾驶车辆运动规划方法[J]. 汽车工程, 2023, 45(8): 1362-1372.
[6]	朱向雷,吴志新,张宇飞,赵帅,李克秋,孙博华. 基于场景降维及采样方法的场景库优化方法研究[J]. 汽车工程, 2023, 45(8): 1408-1416.
[7]	吴新政,邢星宇,刘力豪,沈勇,陈君毅. 基于错误注入的决策规划系统抗扰性测试与分析[J]. 汽车工程, 2023, 45(8): 1428-1437.
[8]	高锋,冯德福,胡秋霞. 面向NMPC运动规划系统的数值优化加速技术[J]. 汽车工程, 2023, 45(8): 1438-1447.
[9]	芦涛,金馨,廖毅霏,黄圣杰,杨依琳,谢国涛,秦晓辉. 基于雅克比域零空间边缘化的视觉SLAM[J]. 汽车工程, 2023, 45(8): 1457-1467.
[10]	伍文广,田双岳,张志勇,张斌. 非铺装道路凹凸不平特征语义分割方法研究[J]. 汽车工程, 2023, 45(8): 1468-1478.
[11]	林程, 汪博文, 吕沛原, 宫新乐, 于潇. 面向变曲率道路的自动驾驶汽车换道博弈运动规划与协同控制研究[J]. 汽车工程, 2023, 45(7): 1099-1111.
[12]	赵东宇, 赵树恩. 基于级联YOLOv7的自动驾驶三维目标检测[J]. 汽车工程, 2023, 45(7): 1112-1122.
[13]	李军, 周伟, 唐爽. 基于自适应拟合的智能车换道避障轨迹规划[J]. 汽车工程, 2023, 45(7): 1174-1183.
[14]	赵嘉豪,齐志权,齐智峰,王皓,何磊. 基于轮胎特征点的并行大型车辆朝向角计算[J]. 汽车工程, 2023, 45(6): 1031-1039.
[15]	金立生,韩广德,谢宪毅,郭柏苍,刘国峰,朱文涛. 基于强化学习的自动驾驶决策研究综述[J]. 汽车工程, 2023, 45(4): 527-540.