Hierarchical Route Planner

John R. Benton

doi:10.1117/12.947003

29 March 1988 Hierarchical Route Planner

John R. Benton

Proceedings Volume 0937, Applications of Artificial Intelligence VI; (1988) https://doi.org/10.1117/12.947003
Event: 1988 Technical Symposium on Optics, Electro-Optics, and Sensors, 1988, Orlando, FL, United States

Abstract

A two-level hierarchical route planner has been developed. The data input to the system is a cross-country mobility map. For a given vehicle type, this map specifies regions which are "GO" or "NO-GO." A line-thinning algorithm is used to generate a skeleton of the "GO" areas. This skeleton is then converted into a graph-theoretic structure. A first-level route planner using elevation-grid data is used to compute the traversal time of each arc of the graph. These traversal times become the weights used by the second level route planner. This route planner is an A* algorithm that is used to search for a specified number of non-competing routes, i.e., routes that have no arc-segments in common. Thus, the first level route planner does detailed planning over a small area but is subject to combinatorial explosion when a search over a wider area is required. The second level graph-search algorithm provides the capability to efficiently plan a route over a larger area but without detail about the precise path followed. This system was implemented in Common Lisp on a Lisp machine. The software has also been integrated into a workstation that was developed to provide support to Army robotic vehicle research. The workstation provides support for comparing the capabilities of alternative route finding algorithms.

Citation Download Citation

John R. Benton "Hierarchical Route Planner", Proc. SPIE 0937, Applications of Artificial Intelligence VI, (29 March 1988); https://doi.org/10.1117/12.947003

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available