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

doi:10.19562/j.chinasae.qcgc.2023.03.001

Abstract

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

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.

Figures/Tables 13

References 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.

[1]	LI Huan, HUANG Ying, ZHANG Fu-Jun, ZHAO Yu, GE Yan-Wu. [J]. , 2016, 38(12): 1420 -1426 .
[2]	HAO Han, WANG Si-南, LI Xiao, LIU Zong-Wei, ZHAO Fu-Quan. [J]. , 2017, 39(1): 1 -8 .
[3]	XU Cheng-Shan, JIANG Fa-Chao, SONG Sen-Nan, TIAN Guang-Yu. [J]. , 2017, 39(1): 9 -14 .
[4]	JIANG Ting, DAI Bing. [J]. , 2016, 38(12): 1459 -1466 .
[5]	ZHANG Yi-Bing, 吕Jian-Jun , YUAN Guang-Hui. [J]. , 2016, 38(12): 1467 -1470 .
[6]	ZHANG Lei, ZHANG Jin-Qiu, LUO Tao, BI Zhan-Dong, YAO Jun. [J]. , 2016, 38(12): 1494 -1499 .
[7]	CUI An, LI Bin, WANG Xue-Liang, ZHANG Shi-Zhan. [J]. , 2016, 38(12): 1521 -1525 .
[8]	CHU Liang, ZHAO Di, LI Wen-Hui. [J]. , 2017, 39(1): 61 -65 .
[9]	FENG Chong, ZHANG Dong-Hao, LUO Yu-Gong, LI Ke-Qiang. [J]. , 2017, 39(1): 66 -72 .
[10]	YUAN Zhi-Qun, GU Zheng-Qi, YANG Ming-Zhi, PENG Qian, LIU Xian-Gui. [J]. , 2017, 39(1): 28 -34 .

场景	参数	数值
构造场景（一般车辆模型）	轴距	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]	Feng Gao,Defu Feng,Qiuxia Hu. Accelerating Technologies of Numerical Optimization for Motion Planning Designed by Nonlinear Model Predictive Control [J]. Automotive Engineering, 2023, 45(8): 1438-1447.
[2]	Tao Lu,Xin Jin,Yifei Liao,Shengjie Huang,Yilin Yang,Guotao Xie,Xiaohui Qin. Visual SLAM Based on Jacobian Null-space Marginalization [J]. Automotive Engineering, 2023, 45(8): 1457-1467.
[3]	Wenguang Wu,Shuangyue Tian,Zhiyong Zhang,Bin Zhang. Research on Semantic Segmentation of Uneven Features of Unpaved Road [J]. Automotive Engineering, 2023, 45(8): 1468-1478.
[4]	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.
[5]	Jie Hu,Haoyan Liu,Minchao Zhang,Zhihao Zhang,Qi Zhu,Ruipeng Chen,Man Luo. Research on the Decision and Planning System of Automated Valet Parking Based on Finite State Machine [J]. Automotive Engineering, 2023, 45(2): 243-252.
[6]	Minghui Ren,Jun Liang,Long Chen,Chun Zhang,Yun Wang. Multi-AGV Path Planning for Intelligent Garage Based on Improved Conflict Search [J]. Automotive Engineering, 2023, 45(10): 1933-1943.
[7]	Jie Hu,Linglei Zhu,Ruinan Chen,Xinkai Zhong,Wencai Xu,Minchao Zhang. Research on Parallel Parking Path Planning Method for Narrow Parking Space [J]. Automotive Engineering, 2022, 44(7): 1040-1048.
[8]	Lisheng Jin,Yang He,Huanhuan Wang,Zhen Huo,Xianyi Xie,Baicang Guo. Point Cloud Segmentation Algorithm Based on Adaptive Threshold DBSCAN for Roadside LiDAR [J]. Automotive Engineering, 2022, 44(7): 987-996.
[9]	Liang Chu,Cheng Chang,Xu Wang,Di Zhao,Yanwu Xu. Research on Brake-by-Wire System and Pressure Control Algorithm for Advanced Automatic Driving [J]. Automotive Engineering, 2022, 44(3): 308-318.
[10]	Yunfei Zha,Lü Xiaolong,Xinye Liu,Fangwu Ma. Fusion Estimation of Vehicle State Parameters Based on Dichotomy [J]. Automotive Engineering, 2022, 44(12): 1910-1918.
[11]	Zilong Liu,Xiangfei Shen. Small Target Detection Method for Dual-Modal Autonomous Driving with Yolo v5 and Lite-HRNet Fusion [J]. Automotive Engineering, 2022, 44(10): 1511-1520.
[12]	Linyan Wang,Huijun Zhang,Hongyu Hu. Effect of Driving Experience on Take-Over Performance of L3 Automatic Driving [J]. Automotive Engineering, 2022, 44(10): 1521-1526.
[13]	Xiaohui Qin,Zhewen Wang,Tao Pang,Weiqing Shi,Ning Sun,Manjiang Hu. Vehicle Positioning Method Based on Tight Coupling of Vehicle Model in Enclosed Environments [J]. Automotive Engineering, 2021, 43(9): 1328-1335.
[14]	Qiang Gao,Zhou Lu,Chendong Duan,Ting Xu. Research on Vehicle Vertical Parking Path Planning and Path Tracking [J]. Automotive Engineering, 2021, 43(7): 987-994.
[15]	Zhiyong Zhang,Kai Long,Ronghua Du,Caixia Huang. Trajectory Tracking Coordinated Control for Autonomous Vehicle in High⁃speed Overtaking [J]. Automotive Engineering, 2021, 43(7): 995-1004.

A Hybrid A* Path Planning Method Based on DBSCAN and Dichotomy

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 18

Related Articles 15

Metrics

Comments

Recommended 10