Accession Number : ADA194370

Title :   Hierarchical Route Planner.

Descriptive Note : Research rept.,

Corporate Author : ARMY ENGINEER TOPOGRAPHIC LABS FORT BELVOIR VA

Personal Author(s) : Benton, John R

PDF Url : ADA194370

Report Date : 28 Jan 1988

Pagination or Media Count : 7

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. Keywords: Mobility; Automated terrain reasoning; Route planning; Autonomous vehicles.

Descriptors :   *ALGORITHMS, *ROUTING, ARMY RESEARCH, AUTOMATION, COMPUTER PROGRAMS, DATA PROCESSING, EXPLOSIONS, GRAPHS, INPUT, PATHS, PRECISION, REASONING, ROBOTICS, TERRAIN, THEORY, VEHICLES

Subject Categories : Land and Riverine Navigation and Guidance

Distribution Statement : APPROVED FOR PUBLIC RELEASE