3D large grid route planner for the autonomous underwater vehicles

The purpose of this paper is to develop a 3D route planner, called 3DPLAN, which employs the Fast‐Pass A* algorithm to find optimum paths in the large grid.

The Fast‐Pass A* algorithm, an improved best‐first search A* algorithm, has a major advantage compared to other search methods because it is guaranteed to give the optimum path.

In spite of this significant advantage, no one has previously used A* in 3D searches. Most researchers think that the computational cost of using A* for 3D route planning would be prohibitive. This paper shows that it is quite feasible to use A* for 3D searches if one employs the new mobility and threat heuristics that have been developed.

This paper reviews the modification of the previous 3DPLAN in the ocean dynamical environment. The test mobility map is replaced with more realistic mobility map that consists of travel times of each grid point to each of its 26 neighbors using the actual current velocity data from the Navy Coastal Ocean Model – East Asian Seas version. Numerical comparison between the A* and genetic algorithms (GA) shows that the A* algorithm has significantly faster running time than GA.

These new heuristics substantially speed up the A* algorithm so that the run times are quite reasonable for the large grids that are typical of 3D searches.