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

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

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

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.