汽车工程

汽车工程 ›› 2023, Vol. 45 ›› Issue (3): 341-349.doi: 10.19562/j.chinasae.qcgc.2023.03.001

所属专题： 智能网联汽车技术专题-规划&决策2023年

• •    下一篇

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

胡满江1,2,牟斌杰1,杨泽宇1,2(),边有钢1,2,秦晓辉1,2,徐彪1,2   

  1. 1.湖南大学机械与运载工程学院，汽车车身先进设计制造国家重点实验室，长沙 　410082
    2.湖南大学无锡智能控制研究院，无锡 　214115
  • 收稿日期:2022-10-19 修回日期:2022-11-02 出版日期:2023-03-25 发布日期:2023-03-22
  • 通讯作者: 杨泽宇 E-mail:yangzeyu@wion.org
  • 基金资助:
    国家重点研发计划(2021YFB2501800);国家自然科学基金(52202493);湖南省自然科学基金(2021JJ40095)

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

Manjiang Hu1,2,Binjie Mou1,Zeyu Yang1,2(),Yougang Bian1,2,Xiaohui Qin1,2,Biao Xu1,2   

  1. 1.College of Mechanical and Vehicle Engineering，Hunan University，State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body，Changsha 　410082
    2.Wuxi Intelligent Control Research Institute of Hunan University，Wuxi 　214115
  • Received:2022-10-19 Revised:2022-11-02 Online:2023-03-25 Published:2023-03-22
  • Contact: Zeyu Yang E-mail:yangzeyu@wion.org

RichHTML

40

PDF (PC)

358

赞

摘要：

在多障碍物非结构化场景中，传统混合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