Abstract: Aiming at the safety and smoothness problems of path planning for Unmanned Surface Vehicle (USV) in complex marine environment, a multi-directional A^* path planning algorithm was proposed for obtaining global optimal path. Firstly, combining the electronic chart, the rasterized environment information was established, and a safe area model of USV was established according to the safety nevigation distance constraint. And the A^* heuristic function with safety distance constraint was designed based on the traditional A^* algorithm to ensure the safety of the generated path nodes. Secondly, a multi-directional search mode was proposed by improving the eight-directional search mode of the traditional A^* algorithm to adjust the redundant points and inflection points in the generated path. Finally, the path smoothing algorithm was used to smooth the inflection points to obtain the continuous smooth path that meets the actual navigation requirements. In the simulation experiment, the path distance planned by the improved A^* algorithm is 7 043 m, which is 9.7%, 26.6% and 7.9% lower than those of Dijkstra algorithm, traditional A^* four-directional search algorithm and traditional A^* eight-directional search algorithm. The simulation results show that the improved multi-directional A^* search algorithm can effectively reduce the path distance, and is more suitable for the path planning of USV.

Key words: A^* algorithm, path planning, Unmanned Surface Vehicle (USV), safety constraint, path smoothing

摘要： 针对海洋环境下无人水面艇路径（USV）规划安全性与平滑性问题，提出一种多方向A^*路径规划算法以获得全局最优路径。首先，结合电子海图生成栅格化环境信息，并根据安全航行距离约束建立USV安全区域模型，在传统A^*算法基础上设计一种带安全距离约束的A^*启发函数来保证生成的路径节点的安全；其次，改进传统A^*算法的八方向搜索模式，提出一种多方向搜索模式来调整生成路径中的冗余点与拐点；最后，采用路径平滑算法对路径拐点进行平滑处理以获得满足实际航行要求的连续平滑路径。在仿真实验中，改进A^*算法规划的路径距离为7 043 m，相较于Dijkstra算法、传统A^*四方向搜索算法和传统A^*八方向搜索算法分别降低了9.7%、26.6%和7.9%。仿真结果表明改进后的多方向A^*搜索算法能够有效减小路径距离，更适用于USV路径规划问题。

关键词: A^*算法, 路径规划, 无人水面艇, 安全约束, 路径平滑