J.R. BENTON
Modeling and Simulation Division, U.S. Army Topographic Engineering Center, 7701 Telegraph Road Alexandria, VA 22315–3864, USA
S.S. IYENGAR
Department of Computer Science & Robotics Research Laboratory, Louisiana State University, Baton Rouge, LA 70803–4020, USA
W. DENG
Department of Computer Science & Robotics Research Laboratory, Louisiana State University, Baton Rouge, LA 70803–4020, USA
N. BRENER
Department of Computer Science & Robotics Research Laboratory, Louisiana State University, Baton Rouge, LA 70803–4020, USA
V.S. SUBRAHMANIAN
Department of Computer Science & Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA

Received 17 April 1995
Revised 10 January 1996

This paper defines a new approach and investigates a fundamental problem in route planners. This capability is important for robotic vehicles(Martian Rovers, etc.) and for planning off-road military maneuvers. The emphasis throughout this paper will be on the design and analysis and hieiaichical implementation of our route planner. This work was motivated by anticipation of the need to search a grid of a trillion points for optimum routes. This cannot be done simply by scaling upward from the algorithms used to search a grid of 10,000 points. Algorithms sufficient for the small grid are totally inadequate for the large grid. Soon, the challenge will be to compute off-road routes more than 100 km long and with a one or two-meter grid. Previous efforts are reviewed and the data structures, decomposition methods and search algorithms are analyzed and limitations are discussed. A detailed discussion of a hieraichical implementation is provided and the experimental results are analyzed.

Route planning; heirarchical planning; A* algorithm; robotic vehicles