Accession Number : ADA183900

Title :   Solving a Class of Spatial Reasoning Problems: Minimal-Cost Path Planning in the Cartesian Plane.

Descriptive Note : Doctoral thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Richbourg,Robert F

PDF Url : ADA183900

Report Date : Jun 1987

Pagination or Media Count : 429

Abstract : This work presents an algorithm to solve a two-dimensional weighted-region problem that requires finding the least-cost regions. Such regions have a constant cost rate per unit distance accrued by paths passing through them. Conventional graph search applies standard search strategies to graphs whose links represent the only possible paths. We use Snell's law as a local-optimality criterion to create corresponding graphs for the weighted-region problem; the nodes in our graphs represent areal subdivisions of the physical environment. The performance of our Snell's-law-based algorithm is compared to that of a dynamic-programming, wavefront-propagation technique. Test results show average-case superiority of the Snell's-law-based algorithm, as measured by time, space and solution-path cost. We present a criterion to predict the time for the wavefront-propagation algorithm and the Snell's-law algorithm to solve problems; this allow the selection of the fastest algorithm. We also develop improvements to the wavefront-propagation algorithm that decrease its average-case time requirements and we prove properties of Snell's law when applied to the weighted-region problem.

Descriptors :   *ALGORITHMS, *PROBLEM SOLVING, *ARTIFICIAL INTELLIGENCE, PATHS, THESES, ALGORITHMS, COSTS, GRAPHS, PHYSICAL PROPERTIES, RANGE(DISTANCE), RATES, REASONING, SEARCHING, SNELLS LAW, STRATEGY, TWO DIMENSIONAL, WAVEFRONTS

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE