Three-dimensional route planning for large grids Article

Brener, NE, Iyengar, SS, Looney, HC et al. (2004). Three-dimensional route planning for large grids . 84(3-4), 67-76.

cited authors

  • Brener, NE; Iyengar, SS; Looney, HC; Vakamudi, N; Yu, D; Huang, Q; Barhen, J

fiu authors

abstract

  • We have developed a 3D route planner, called 3DPLAN, which employs the A* algorithm to find optimum paths. The 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 as far as we are aware. The probable reason for this is the belief that the computational cost of using A* for 3D route planning would be prohibitive. In this paper we show that, on the contrary, it is quite feasible to use A* for 3D searches if one employs the new mobility and threat heuristics that we have developed. 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.

publication date

  • May 1, 2004

start page

  • 67

end page

  • 76

volume

  • 84

issue

  • 3-4