3D large grid route planner for the autonomous underwater vehicles Article

Cao, H, Brener, NE, Iyengar, SS. (2009). 3D large grid route planner for the autonomous underwater vehicles . 2(3), 455-476. 10.1108/17563780910982699

cited authors

  • Cao, H; Brener, NE; Iyengar, SS

fiu authors

abstract

  • Purpose: 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. Design/methodology/approach: 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. Findings: 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. Practical implications: 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. Originality/value: 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. © Emerald Group Publishing Limited.

publication date

  • August 21, 2009

Digital Object Identifier (DOI)

start page

  • 455

end page

  • 476

volume

  • 2

issue

  • 3