An enhanced A* method incorporating an encrypted memory database for ASV efficient local path planning

1.   Introduction

In recent decades, the advancement of artificial intelligence research and the gradual maturity of unmanned technology both contribute to the enormous leap in unmanned systems ^[1,2,3]. As a multidisciplinary and comprehensive subject involving information technology, automation technology and system integration, unmanned technology has been widely utilized in drones ^[4,5], autonomous surface vehicles (ASVs) ^[6,7], flexible spacecrafts ^[8] and undersea robots ^[9]. Particularly, ASVs can replace humans to accomplish more complex and dangerous tasks in many fields: In the civilian field, ASV is widely used in meteorology ^[10], surveying and mapping ^[11,12], environmental protection ^[13], vessel train ^[14], and agriculture ^[15]; in military field, in addition to tactical simulation as a target ^[16], ASVs can also be used as enemy situation reconnaissance ^[17], communication relay ^[18] and effectiveness assessment ^[19]. The above tasks require ASVs to have higher autonomous capabilities, and the mission process's completion needs to consider actual constraints such as the shortest route and lowest loss ^[20]. Therefore, as the basis for completing the requirements, path planning plays a crucial role in the ASV system.

In general, path planning problems can be categorized as follows: traversal optimal path planning within discrete domains, including the traveling merchant problem ^[21] and its derivative issues; Shortest path planning within discrete domains, such as road network and routing problems; Traversal path planning in the continuous domain is mainly applied to cleaning robots ^[22,23], weeding robots ^[24], search and rescue robots ^[25], mineral detectors ^[26]. Path planning problems within the continuous domain are divided into global planning, which focuses on path optimization, and local planning, which focuses on safety. Global path planning avoids known solid obstacles based on prior knowledge of the environment to find the optimal path, and typical application scenarios include autonomous movement planning of robotic arms ^[27], path planning of drones ^[28], and trajectory planning of aerodynamic missiles ^[29]. However, it should be noted that the above literature is ideal because there are always unknown or dynamic obstacles in the navigation environment of the ASV system. It should be mentioned that the local planning algorithm can successfully overcome the limitations caused by global planning. As a real-time, efficient, and stable algorithm, the local planning algorithm can effectively use dynamic and actual environmental information and achieve timely obstacle avoidance. As a consequence, it is often necessary to model the environment using methods such as the grid method ^[30,31].

Standard path planning algorithms can be divided into geometric algorithms, bionic algorithms, and intelligent algorithms ^[32,33] according to their fundamental principles. For geometric algorithms, Yu ^[34] proposed an artificial potential field RRT* algorithm. The artificial potential field for sampling algorithm and the ocean current constraint function are implemented in the RRT* algorithm, and the modified Hungarian algorithm for multiobjective allocation is used; For bionic algorithms, Escario ^[35] used the swarm algorithm to address the path planning problem of ASVs, aiming to obtain optimal trajectories for kinematic of ASVs; for intelligent algorithms, Singh ^[36] introduced artificial potential fields for ASV path planning in real-time marine environments. Path cost and its length, calculation time are described to guarantee the effective planning of pathways.

In summary, path planning is necessary for ASVs to perform tasks. However, some of the existing algorithms have disadvantages such as slow exploration speed, repeated exploration, leakage of crucial information, and they are limited by the detection capabilities of ASVs themselves, which cannot be applied to application scenarios where the target point is too far away. For example, the deep learning algorithm needs a large amount of data training; the ant colony algorithm and the artificial potential field method need to carefully adjust the parameters; the genetic algorithm has slow convergence speed and is easy to falls into local optimum. To overcome these limitations, this paper chooses the A* algorithm which has simple structure but similar effect. Here, we proposed a local path planning method for ASVs based on an enhanced A* algorithm. First, an improved heuristic function is incorporated into the traditional A* algorithm to speed up exploration, and the obstacle-related function is added to increase path safety. Then, a temporary target within the detection range is created to improve the target point mechanism when the target point is too far to be detected. Besides, the additional memory function is introduced to store the frequently used or has been recorded water. When the same water area is reencountered, the corresponding path can be directly read and complete the voyage without the need to search for the path again. Furthermore, the memory database is encrypted to prevent information leakage. Finally, the feasibility and superiority of the simulation environment are verified.

2.   The ASV system

2.1.   ASV model

Based on the existing ship modeling theory, the mathematical model widely used has been adopted ^[37], which is proposed by Fossen. The following assumptions need to be satisfied before modeling:

$(1)$ The overall mass of the ASV is evenly distributed;

$(2)$ ASVs are symmetrical left and right;

$(3)$ Ignoring the influence of Earth's rotation.

The motion coordinate system is the basis for analyzing the motion of ASVs. As shown in Figure 1(a), an inertial coordinate system $XOY$ and a coordinate system attached to the ASV $X_{b}O_{b}Y_{b}$ are defined. Somewhere on the Earth's surface is chosen as the coordinate origin $O$ of the inertial coordinate system, with the $OX$ axis pointing towards the north and the $OY$ axis pointing towards the east. When the ship is symmetrical, the ship's center of gravity $O_b$ is selected as the origin of the coordinate system attached to the ASV, with the axis $O_{b}X_{b}$ pointing to the bow along the ship's centerline and the axis $O_{b}Y_{b}$ pointing to the port side of the ship.

To simplify the analysis, the ASV's roll, pitch, and heave are usually ignored, and only the plane motion of the ASV is considered. The kinematic model can be described as.

where $\eta = [x, y, \psi]^T$ represents the position vector of the ASV in the inertial coordinate system, consisting of position $(x, y)$ and bow angle $\psi\in[0, 2 \pi]$. $\nu = [u, v, r]^T$ represents the velocity vector in the coordinate system attached to the ASV, consisting of longitudinal velocity $u$, lateral velocity $v$, and yaw angular velocity $r$. By defining the rotation matrix $M\left(\psi \right)$, which is shown as Eq (2.2).

Eqs (2.1) and (2.2) can be simplified to obtain Eq (2.3).

Moreover, the corresponding ASV dynamics model can be expressed as Eq (2.4).

In Eq (2.4), $A = \begin{bmatrix} a_{11} & 0 & 0\\ 0 & a_{22} & a_{23}\\ 0 & a_{23} & a_{33}\end{bmatrix}$ is a system inertia matrix; $S(\nu) = \begin{bmatrix} 0 & 0 & s_{13}\\ 0 & 0 & s_{23}\\ s_{31} & s_{32} & 0\end{bmatrix}$ is the Coriolis and centripetal force matrix; $L = \begin{bmatrix} l_{11} & 0 & 0\\ 0 & l_{22} & l_{23}\\ 0 & l_{32} & l_{33}\end{bmatrix}$ is a linear damping matrix; $T = \begin{bmatrix} t_{1}\\ t_{2}\\t_{3}\end{bmatrix}$ is a kinematic matrix including longitudinal control $t_{1}$, lateral control $t_{2}$, and yaw angle control $t_{3}$; $p = \begin{bmatrix} p_{1}\\ p_{2}\\p_{3}\end{bmatrix}$ stands for the unknown disturbance caused by wind, waves and ocean currents, and the value of $p$ is assumed as constant or slowly changing.

2.2.   ASV obstacle avoidance rules

In 1920, the International Maritime Organization proposed a set of maritime traffic rules to regulate ship traffic, the International Regulations for Preventing Collisions at Sea (COLREGS). This set of rules governs the navigation of ships piloted by humans and defines the different situations of ship traffic. Moreover, it has been updated in 1972 ^[38]. Although it is unreasonable for ASVs to sail entirely according to this scheme, it has a certain reference value. There are several important provisions in the COLREGS:

Article 13 of the COLREGS, overtaking:

$(1)$ When a ship overtakes another ship from a direction greater than 22.5 degrees directly behind another ship, i.e., the position of the ship it is overtaking, and at night it can see only the stern lights of the overtook ship, it cannot see any of the overtook ship's sidelights, it shall be considered to be in overtaking.

$(2)$ When a ship has any doubt as to whether it is overtaking another ship, the ship shall assume it is overtaking another ship and act accordingly.

$(3)$ Any subsequent change in the orientation between the two ships shall not treat the overtaking ship as a cross ship within the meaning of the various articles of the COLREGS or relieve it of its responsibility to yield the overtook ship until it has finally passed through the region.

Article 14 of the COLREGS, head-on:

$(1)$ When two ships meet in opposite or nearly opposite directions and pose a risk of collision, they shall turn to the right and each passes over the port side of the other ship.

$(2)$ When a ship sees another ship directly in front or the near front, and at night, only visible the masthead lights of another ship in a straight line or close to a straight line, and so are two sidelights; in the daytime, when the corresponding form of another ship is seen like above, the head-on situation should be considered to exist.

$(3)$ When a ship doubts the existence of the head-on situation, the ship shall assume that the situation does exist and act accordingly.

Article 15 of the COLREGS, crossing:

When two ships come across each other and pose a risk of collision, the ship with another ship on its starboard side shall give way to another ship, and if circumstances permit, it shall avoid crossing the front of the other ship.

Different navigation situations are divided based on the above rules of COLREGS, and the basic obstacle avoidance model of ASVs, as shown in Figure 1(b), is established.

2.3.   Encryption algorithm

With the maturity of information technology, computer networks have become one of the essential means for human beings to disseminate information. The ASVs share data and transmit messages through the web to bring great convenience and opportunities for navigation. However, as an open and shared environment, the network environment has various factors that affect security issues, resulting in data interception, theft, and tampering. Therefore, this article encrypts the map of ASV paths database to improve the security of data transmission in the network environment. As a result, the leakage of the map database with malicious third parties intercepting and attacking can be prevented, which contributes to the economy and security of the ASVs. Current encryption technology can be divided into symmetric encryption and asymmetric encryption according to its fundamental type, and the two encryption flowcharts are shown in Figure 2(a).

Asymmetric encryption is irreversible, as shown on the left of Figure 2(a). Its encryption key A is public, and anyone can use this encryption key A to encrypt data. However, the encrypted information can only be unlocked by the corresponding decryption key B, which differs from key A, and key B is not public. Symmetric encryption, on the other hand, is reversible in encryption and decryption uses the same key, meaning that the sender and receiver of the message must hold the same key. As an open algorithm, it has small computation, fast encryption speed, and high efficiency. To conform with ASV's small memory and low computing power, this paper adopts a simple method of symmetric encryption. Furthermore, the planned path is stored in the memory database and encrypted with a random key to increase security. The encryption and decryption calculation formula is as Eq (2.5).

where $L_i$ is the data of the encrypted map position $i$; $R_i$ is the decrypted map position $i$; $m$ is the key matrix; $Cal$ is the decryption formula, which is set in this article as the addition and subtraction set of values.

3.   Path planning algorithm

3.1.   Dijkstra's algorithm

The Dijkstra's algorithm, an algorithm for shortest paths from one point to hlanother point was proposed in 1959 by Dijkstra, a Dutch computer scientist. Dijkstra's algorithm is designed to find the shortest path in weight graph ^[39]. Based on the greedy algorithm, Dijkstra's algorithm starts from the starting point, and then each time traverses the not-visited neighboring nodes that are closest to the starting point until it extends to the final target point. The algorithm flow is shown in Figure 2(c).

An undirected graph $G = \left\{V, E\right\}$ is built, where $V$ is the set of vertices in $G$, and $E$ is the set of arcs. Initially, let $S = \left\{V_0\right\}$, $T = V-S$. If the distance value corresponding to the vertex $T$ exists, $d(V_0, V_i)$ is set to the weight on the arc; If it does not exist, $d(V_0, V_i) = \infty$. Select the vertex with the smallest value from $T$ connected to the vertex in $S$. If the vertex's weight is more minor than that has been used as the middle vertex and the distance value from $V_0$ to $V_i$ is shortened, the previously used vertex will be modified. In addition, repeat the above steps until $S$ contains all vertices.

When Dijkstra's algorithm searches for paths, it needs to expand from the starting point to all surrounding nodes and obtain all paths to the target point. Then the optimal way can be achieved. The path obtained by Dijkstra's algorithm must tend to be optimal, but it needs to expand many useless nodes when searching for the optimal way. Therefore, Dijkstra's algorithm is resource-consuming and low efficiency, especially in the case of a large map environment.

3.2.   A* algorithm

The A* algorithm, published in 1968 by Peter Hart of the Stanford Institute ^[40], can be considered an expansion of Dijkstra's algorithm. As a heuristic algorithm, the A* algorithm works by using heuristic information to find the best path to travel, which searches nodes in the map and sets the appropriate heuristic function. Through estimating each node's value, the optimal node for the next expansion is obtained unless it achieves the final target point. A* algorithm is one of the commonly used path finding and graph traversal algorithms, with good performance and accuracy, and its algorithm flow is shown in Figure 2(d).

When running the A* algorithm, the best and value-optimal node which is selected from the priority queue each time is the first node to be explored. Besides, the A* algorithm has two sets of lists, namely open-list, representing the nodes that should be traversed, and close-list for the nodes that have been traversed, respectively. The A* algorithm calculates the priority of each node through Eq (3.1).

where $f(n)$ is the comprehensive prioritization of node $n$; $g(n)$ is the charge of node $n$ from the starting point; $h(n)$ is the estimated charge of node $n$ from the final target point, also called the heuristic function. When $h(n) = 0$ and $f(n) = g(n)$, the algorithm degenerates into the Dijkstra's algorithm.

The actual charge of node $n$ to the final target point is assumed as $Z(n)$. If $h(n) < Z(n)$, then the A* algorithm ensures that the shortest path will always be found. However, the smaller the $h(n)$ value is, the more nodes the algorithm will traverse, and the slower the compute speed. If $h(n) = Z(n)$, the A* algorithm will get the optimal path, and the operation speed will be faster. However, $Z(n)$ cannot be accurately calculated in actual operation. If $h(n) > Z(n)$, then the A* algorithm does not always find the shortest path, but it is the fastest.

It can be concluded that the speed and accuracy of the A* algorithm can be controlled by adjusting the heuristic. In practical application, the path priority needs to be considered, different tasks require different weights, and the impact of the characteristics of ASVs is also significant. For example, the cost of different sailing states of ASVs needs to be considered when finding the shortest path. If building the environment with a grid map, the distance between each point represents the loss, and there are three forms of motion, as shown in Figure 3(a)–(c).

If we allow only the ASV to move back and forth, left and right, as shown in Figure 3(a), the Manhattan distance is more accessible; If the eight directions shown in Figure 3(b) are permitted, then the Chebyshev distance is more appropriate; If ASV is allowed in any direction as shown in Figure 3(c), Euclidean distance can be used.

3.3.   Enhanced A* algorithm

Based on the A* algorithm, this paper proposed an enhanced A* algorithm which improves the temporary target setting under extreme conditions, heuristic function and encrypted map database of the region have been explored.

In detail, if only partial information is available, for example, the approximate direction of the target point due to external or internal factors, the proposed enhanced A* algorithm can newly create a temporary target according to the approximate position of the final target point and the detection range of the ASV. The temporary target planning is shown in Figure 3(d), the calculation formula is as Eq (3.2).

where $x_0$ and $y_0$ are the current positions of the ASV; $k$ is the orientation of the target point; $r$ is the maximum radius that the ASV can detect; $x$ and $y$ are the coordinates of the temporary target of the ASV.

The A* algorithm exploration mode is improved, and the actual cost function is modified by using the lower limit of the turning radius, the lower restraint of the path length, and the constraint of the driving speed condition of the ASV. As a result, the obtained planned path is more in line with the kinematic model of the ASV, as shown in Figure 3(e), (f). $r_{\min}$ is the minimum turning radius with center $O$ of the ASV; $\alpha$ is the maximum angle of rotation, less than $35°$^[41]; and the two blue arcs form the maximum sailing area of the ASV.

By considering the simplified diagram of the kinematic model of the ASV above shown in Figure 3(f) and the relation between the ASV and the obstacle position, the A* algorithm with improved heuristic function is proposed to modify the obstacle avoidance problem during path planning, which contributes to the increase of safety and efficiency of navigation. The proposed heuristic function is defined as follows.

where $\alpha$ is the discount parameter, $\alpha > 0$; and $C$ is the relationship between the ASV and nearby obstacles, expressed by Euclidean distance in this paper.

To determine a better value of $\alpha$, the algorithm in this paper randomly generates the initial environment in Figure 4 with pink obstacles and green start and finish points and carries out several tests. As shown in Table 1, when $\alpha = 0.1$, the algorithm performs better in terms of search time and running time. Therefore, 0.1 is chosen as the discount parameter.

Besides, the memory function is considered to store the map data and their corresponding paths that have been obtained, and when the same map occurs in the future, the path can be directly read. Furthermore, the map database can be encrypted. The whole map storing and reading procedures are shown in Figure 2(b). First, a two-dimensional (2D) map is built by the grid method. Then, compare the current 2D map with the map in memory database, and if they are identical, its corresponding path will be directly read as the voyage path; if they are not identical, a new path will be planned as the navigation route, and then the current 2D map will be saved with its corresponding navigation path in the memory database.

4.   Simulation experiments

4.1.   Environment establishment

A grid map is built that scales the 2D environment and it is assumed each grid state is independent. For the group of grids in the environment, the value of grids without obstacles, i.e., available through grids should be assumed to be 0. If there is an obstacle at the grid, its value is set to non-0, and the solid obstacle is set to 1; the dynamic obstacle is set to 4; the dynamic obstacle's path is set to 3; and the algorithm planning path is set to 2.

By setting different colors for grids with different values, the solid obstacle's value 1 is set to pink; the dynamic obstacle's 4 is set to orange, and its path 3 is yellow; the algorithm planning path 2 is set to blue. Plotted by the python matplotlib function, the overall environment is shown in Figure 5(a).

4.2.   Path search

Based on the above, the 2D map environment is constructed. The through regions are generated by combining the ASV kinematics model and COLREGS in Section 2. As shown in Figure 5(b) the region framed by the x-axis $(13, 28)$ and y-axis $(12, 27)$ in Figure 5(a) is enlarged. In terms of points $(x_i, y_i)$ and $(x_j, y_j)$, the red arrow is the moving direction of the ASV at point $(x_i, y_i)$, while the yellow arrow is the moving direction of the ASV at point $(x_j, y_j)$. The angle $\theta$ between the two arrows is the moving trend angle of the ASV when it moves from $(x_i, y_i)$ to $(x_j, y_j)$. Additionally, the moving trend angle $\theta$ is limited to the maximum turn angle of ASV, i.e., less than $35°$.

By combining the generated path and Eq (4.1), the moving trend angle $\theta$ between neighboring points $(x_i, y_i)$ and $(x_j, y_j)$ can be calculated via the following equation.

The trend angle result is shown in Table 2.

4.3.   Encryption and decryption

In this paper, the memory database is encrypted by symmetric encryption algorithms. If there is no correct key, the wrong path is obtained. Our experience can be shared with third parties to show the routes we have taken through the waters. The encrypted maps are protected from competitors and malicious third parties who may cause damage. For example, the path before encryption is shown in Figure 6(a), and it is encrypted using a symmetric encryption algorithm. The path map after encryption is shown in Figure 6(b), and the ASV path can no longer be distinguished. The path map after decryption is shown in Figure 6(c), where the path of the ASV can be easily observed.

4.4.   Results comparison

In the following, the comparison among Dijkstra's algorithm, A* algorithm, the other A* algorithm in ^[42] and enhanced A* algorithm will be demonstrated. There are some indicators for the comparison: Whether the path can be planned; the length of planned path; the number of searches; the number of second searches; and the calculating time of algorithms. There are three experimental environments: The maze environment; the narrow water area, taking the water near the Garden Expo Park in Xiamen City, Fujian Province, as an example; and the complex water area, like the area between Xiamen Island and Xiaojinmen Island.

4.4.1.   Maze environment

First, the maze environment is built. As shown in Figure 7(a), the map size is $20 \times 20$. The green circle at the bottom of the map is used as the starting point with the coordinates $(3, 2)$, and the green circle at the top is the final target point with the coordinates $(16, 15)$.

Four algorithms are used for path planning, and the planning results are shown in Figure 7(b)–(e). The algorithms discussed in the previous were evaluated for their efficiency in finding the optimal path. The results showed that the enhanced A* algorithm, as shown in Figure 7(e), outperformed Dijkstra's algorithm, A* algorithm, and the other A* algorithm in ^[42], as shown in Figure 7(b)–(d), respectively. Specifically, the search times for the enhanced A* algorithm were 51 times faster than the search times for Dijkstra's algorithm, A* algorithm, and the other A* algorithm in ^[42], which are 73 times, 101 times, and 197 times, respectively. Moreover, the enhanced A* algorithm also had the shortest path length and the calculating time, as shown in Table 4. Furthermore, the enhanced A* addition memory function can give this path without searching when reencountering the same map, effectively saving resources.

4.4.2.   Narrow water environment

To increase the complexity of the map, the narrow water environment with the size of $50 \times 50$ is built as shown in Figure 8(a) based on the water around the Garden Expo Park in Xiamen, Fujian Province. The ASV sails from the river below to the upper right corner through this area. The planning paths of each algorithm are shown in Figure 8(b)–(d), and the algorithm order is identical to that of Figure 7.

In Table 4, although the complexity of the environment increases, all four algorithms can plan the path to the final target point. Still, the number of Dijkstra's algorithm searches is larger than the other two algorithms and the A* algorithm is explored 1.5 times more than the enhanced A* algorithm. On the second search, the number of explorations of the enhanced A* algorithm is only 0. Moreover, the path length is reduced compared to other algorithms, and the algorithmic computation is accelerated by a third or more. In a word, the resources required for path planning are significantly saved.

4.4.3.   Extreme conditions

The maps are the same as in Figures 8(a) and 7(a), including the start and target points. Due to inclement weather or equipment limitations, only partial information such as the orientation of the target point may be available. The ASV's maximum visibility is represented by the red circle, while the calculated temporary target is gray and the final target point is displayed by the black circle, as shown in Figures 9(a) and 10(a). In such situations, the heuristic function $h(n)$ of A* algorithm and the other A* algorithm in ^[42] cannot be computed and will degenerate into the Dijkstra algorithm. However, since Dijkstra is a global search algorithm, it will give the same results as in Figures 7(b) and 8(b). As for the enhanced A* algorithm, temporary targets play a crucial role.

By planning the path within the range of visibility, the navigation process is shown in Figures 9 and 10, and the comparison is shown in Table 5. From the starting position as shown in Figure 10(a), the ASV firstly detects the visible area. If there is no final target point, use Eq (3.2) to calculate the temporary target point, and substitute its position into the heuristic function to calculate the priority of nodes in the visible area until the temporary target point is reached. Continue to explore the visible area until the final target point is seen, and the final target point position is substituted into the heuristic function calculation as in other common A* algorithms. The enhanced A* algorithm performs better than Dijkstra algorithm in terms of search times, path length, and algorithm computation time.

In Figure 10(c), the temporary target should have been located on $O_1$, which is on the line between the target point and the ASV. But its position was covered by an obstacle, in which case the temporary target would be moved laterally in the direction of ASV, that is, exit the obstacle area to $O_2$.

4.4.4.   Complex water environment

The basic map with the size of $50\times50$ is shown in Figure 11(A), taking the water area between Xiamen Island and Xiaojinmen Island as an example. The ASV passes through the water from the bottom left to the upper right. A dynamic obstacle is placed, and conducts three conditions of head-on, overtaking and crossing with the ASV, as shown in Figure 11(B), (C). Furthermore, their (a) is the overall path planning diagram, and their (b)–(d) is the obstacle avoidance process.

The proposed algorithm considers the motion mode of ASV and explores the next node from the far right, which is more suitable to the real navigation situation of ASV. In detail, according to Article 14 of the COLREGS, when two ships meet head-on and have the risk of collision, they should take the right turn to avoid the danger. It can be seen in Figure 11(B), (c) that the ASV with the blue track indeed passes over the left side of the dynamic obstacle. Figure 11(C) references Article 13 of the COLREGS. When the ASV intends to overtake the forward dynamic target, it takes a rightward overtaking path. Figure 11(D) references Article 15 of the COLREGS, that is, when an ASV encounters a crossing dynamic obstacle, the ASV with the obstacle on the right is the avoiding side and takes a rightward path adjustment.

5.   Conclusions

Aiming at the path planning problems of ASVs in various environments such as a maze, narrow water, complex water, and extreme conditions, we summarizes the three practical situations in the COLREGS. Then the simulation environment is built using the programming language and the validity of the proposed enhanced A* algorithm is verified. The major contributions can be easily summarized in:

$1)$ The enhanced A* method incorporating encrypted memory database for ASV efficient local path planning can deal with three fundamental ASV encounter problems with high performance, including head-on, overtaking, and crossing in the natural water environment.

$2)$ After modifying the heuristic function, the enhanced A* algorithm can effectively accelerate the search efficiency. In particular, compared to Dijkstra's algorithm, the A* algorithm, and the other A* algorithm in ^[42], the proposed algorithm has a better advantage in the first exploration when the results are similar.

$3)$ Temporary targets can be generated to aid navigation when final target point information is partial. Particularly, in comparison with the Dijkstra algorithm, the A* algorithm and the other A* algorithm in ^[42], which are degraded to the Dijkstra algorithm since only the approximate direction of the final target point is known. The proposed A* algorithm can achieve advantages in the number of searches, the path length, and the algorithm computation time.

$4)$ In this paper, we consider adding the memory function and saving the compute resource for searching the optimal path when reencountering the same environment. In addition, the memory is encrypted to deal with the transmission leakage problem.

The future research will focus on four major areas: The first goal is to improve the algorithm toward faster computation and safer planning paths. Then, enrich the structure of the proposed algorithm to deal with more complex environments. Furthermore, compress stored map databases to prevent them from requiring too much memory space and taking too much time to search. Moreover, how to apply it in reality, send the path to the real ASV correctly and timely, and control it to navigate according to the path are also the future research areas.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the National Natural Science Foundation of China (52171309, 51809113), Natural Science Foundation of Fujian Province, China (2022J06025, 2021J01843), Fujian Provincial Young Top-Notch Talent Plan (Z02101), and the Research Launch Funding of Jimei University (C623018).

Conflict of interest

The authors declare that there are is no conflicts of interest.