To read the full version of this content please select one of the options below:

3D large grid route planner for the autonomous underwater vehicles

Hua Cao (Robotics Research Laboratory, Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana, USA)
Nathan E. Brener (Robotics Research Laboratory, Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana, USA)
S. Sitharama Iyengar (Robotics Research Laboratory, Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana, USA)

International Journal of Intelligent Computing and Cybernetics

ISSN: 1756-378X

Article publication date: 21 August 2009

207

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.

Keywords

Citation

Cao, H., Brener, N.E. and Sitharama Iyengar, S. (2009), "3D large grid route planner for the autonomous underwater vehicles", International Journal of Intelligent Computing and Cybernetics, Vol. 2 No. 3, pp. 455-476. https://doi.org/10.1108/17563780910982699

Publisher

:

Emerald Group Publishing Limited

Copyright © 2009, Emerald Group Publishing Limited

Related articles