Three-dimensional route planning for large grids

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.