Tactical route planning: new algorithms for decomposing the map

John Benton*, S. S. Iyengar, W. Deng, N. Brener, V. S. Subrahmanian

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations

Abstract

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 hierarchical 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 hierarchical implementation is provided and the experimental results are analyzed. The principal contributions of the paper are (1) new algorithms for decomposing the map and new search methods, (2) analysis of new approaches, and (3) the use of expert systems, deductive databases and mediators. Experimental results are included of a detailed implementation.

Original languageEnglish (US)
Pages (from-to)268-277
Number of pages10
JournalProceedings of the International Conference on Tools with Artificial Intelligence
StatePublished - 1995
Externally publishedYes
EventProceedings of the 1995 IEEE 7th International Conference on Tools with Artificial Intelligence - Herndon, VA, USA
Duration: Nov 5 1995Nov 8 1995

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Tactical route planning: new algorithms for decomposing the map'. Together they form a unique fingerprint.

Cite this