## 2 Method
### Locally Improved A* Algorithm  
The A* algorithm is a standard path search algorithm, usually used to find the shortest path in a graph. It combines the advantages of the Dijkstra algorithm and the greedy best-first search and uses a heuristic function to guide the search process. The basic idea is to evaluate the cost of each node to determine the optimal path. During the search, nodes are selected through the two-state tables of \(\mathit{Openlist}\) and \(\mathit{Closelist}\). The search is based on the grid map and each node is examined. The path nodes to be examined are placed in the \(\mathit{Openlist}\) table, and the nodes that have been examined are placed in the \(\mathit{Closelist}\) table. The cost value evaluation function examines the nodes to find the optimal path. The path evaluation function is:  
\[F(n)=g(n)+h(n) \tag{3}\]  
where \(F(n)\) is the total cost from the starting point to point \(n\), \(g(n)\) is the actual cost from the starting point to point \(n\) in the running environment, and \(h(n)\) is the estimated cost of the best path from point \(n\) to the target point. There are four-directional search and eight-directional search patterns. Considering the movement characteristics of the USV in the ocean, this paper used the eight-directional search pattern to search the navigable waters, as shown in Figure 3, where \(g(n)\) is the distance from the starting point to the current node and \(h(n)\) is the estimated distance from the current node to the target node, calculated using the Euclidean distance:  
\[h(n)=\sqrt{\left(x_{g}-x_{c}\right)^{2}+\left(y_{g}-y_{c}\right)^{2}} \tag{4}\]  
where \((x_{g},y_{g})\) is the coordinate of the target point and \((x_{c},y_{c})\) is the coordinate of the current node. Generally speaking, the traditional A* algorithm evaluates many nodes with low overall efficiency. When planning a path, many redundant points are generated. In a complex search space, especially when the number of nodes and edges is large, the A* algorithm may require many computing resources, affecting performance and efficiency. This paper improves the algorithm from the following three aspects. * Add safety distance  
The traditional A* algorithm usually only considers path length as an evaluation function when finding a path, which may cause the planned path to be too close to the edge of an unnavigable area, such as a shoal, coral reef, or artificial obstacle, thereby increasing the risk of collision or of being affected by environmental factors, posing a potential threat  
Figure 3: Search pattern of A* algorithm. (**a**) Four-directional search pattern; (**b**) Eight-directional search pattern. to the safe navigation of the USV. To solve this problem, we introduced a \"safe distance\" constraint as part of the algorithm when finding the path, ensuring that the planned route is away from the edge of the dangerous area, significantly improving the safety of the route. In the improved A* algorithm, whenever the algorithm tries to expand from the current node to an adjacent node, it not only calculates the cost from the starting point to the node and the estimated cost from the node to the target point but also adds a judgment condition to ensure that the node maintains a specified safe distance from any known unnavigable area. This safe distance can be dynamically adjusted according to the size of the USV, its operational flexibility, and the environmental risk level. The safety distance is defined as the distance from the node to the nearest obstacle and it must be greater than or equal to the specified safety distance, which can be determined according to specific needs. During the path planning process, for the current coordinate point \(Current(x_{c},y_{c})\), the obstacle coordinate point \(Obstacle(x_{i},y_{i})\), and the neighbor node \(Neighbor_{i}(x_{n},y_{n})\) to be expanded, the shortest distance from the \(Neighbor_{i}\) to the nearest \(Obstacle\) is calculated first, as shown in Equation (5).