## 2 Related Works
Over the years, many modifications have been proposed to improve the efficiency of the standard A* solution, such as JPS (A*) [18], variable-step based A* [19], geometric A* [20], EBHSA* algorithm [21], IMOA* [22], RJA* [23], ORMBA* [24], APF-A* [25], and other improvements [26; 27; 28; 29; 30; 31; 32; 33; 34; 35]. The comprehensive review of the latest literature on the methods aimed at optimising the A* algorithm is presented in Table 1. Each approach modifies the basic A* algorithm to improve the computational efficiency, obtain a shorter or smoother path, or improve path safety. A significant improvement in one of these parameters does not allow for a significant improvement in the other (JPS-A*, Geometric A*). Therefore, each algorithm optimisation is associated with a compromise between computational performance and the calculated path length. In most of the studies presented in Table 1, tests were carried out on relatively small maps. In most cases, computational performance was not improved significantly, or the algorithm did not consider the vehicle's safety. The A* algorithm with the map processing approach presented in this article primarily focuses on reducing the computation time and providing a safety path feasible for AUVs/ASVs. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Source**} & \multirow{2}{*}{**Method**} & \multirow{2}{*}{**Brief Description**} & \multirow{2}{*}{**Map Size**} & **Path Length** & **Max. Calculation** \\  & & & **(Proposed/Basic** & **A*)—The Worst** & **A*/Proposed—** \\  & & & & **Cases**) & **The Best Cases** \\ \hline \multirow{4}{*}{[18]} & \multirow{4}{*}{JPS (A*)} & JPS A* speeds up pathfinding by & \multirow{4}{*}{From} & \multirow{4}{*}{100\%} & \multirow{4}{*}{215} \\  & & expanding only pivotal nodes called & & & \\ \cline{1-1}  & & “jump points”, which are directly & & 30 \(\times\) 21 & \\ \cline{1-1}  & & reachable in a straight line or after & & To & \\ \cline{1-1}  & & encountering forced neighbours, & \(1104\times 1260\) & & \\ \cline{1-1}  & & bypassing redundant intermediate nodes. & & & \\ \hline \multirow{4}{*}{[19]} & \multirow{4}{*}{Variable} & The Variable Step A* algorithm & \multirow{4}{*}{NA} & \multirow{4}{*}{97.8\%} & \multirow{4}{*}{28} \\ \cline{1-1}  & & dynamically adjusts its search step size & & & \\ \cline{1-1}  & & based on obstacle distribution to & & & \\ \cline{1-1}  & & optimise pathfinding efficiency and & & & \\ \cline{1-1}  & & accuracy for autonomous land vehicles. & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: A comparison of modifications of the A* algorithm available in the literature. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Source**} & \multirow{2}{*}{**Method**} & \multirow{2}{*}{**Brief Description**} & \multirow{2}{*}{**Map Size**} & \multicolumn{2}{c}{**Path Length**} & \multirow{2}{*}{**Max. Calculation**} \\  & & & **(Proposed/Basic** & **Time Ratio (Basic** \\  & & **[pixels]** & **A*)–The Worst** & **A*/Proposed)–** \\  & & & & **Cases)** & **The Best Cases)** \\ \hline \multirow{4}{*}{**[20]**} & \multirow{4}{*}{Geometric A*} & The Geometric A* algorithm generates a grid map for initial pathfinding with A*, optimises by eliminating irregular nodes for smoother turns, and then applies cubic B-spline interpolation to smooth the path for realistic navigation. & \multirow{4}{*}{\(20\times 20\)} & \multirow{4}{*}{\(58.9\%\)} & \multirow{4}{*}{\(1.6\)} \\  & & The EBHSA* method enhances the A* algorithm by integrating expansion distance, using bidirectional search, optimising heuristic function, and smoothing to improve path robustness and efficiency while reducing collision risks and unnecessary turns for autonomous land vehicles.