
Accession Number : ADA183900
Title : Solving a Class of Spatial Reasoning Problems: MinimalCost 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 twodimensional weightedregion problem that requires finding the leastcost 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 localoptimality criterion to create corresponding graphs for the weightedregion problem; the nodes in our graphs represent areal subdivisions of the physical environment. The performance of our Snell'slawbased algorithm is compared to that of a dynamicprogramming, wavefrontpropagation technique. Test results show averagecase superiority of the Snell'slawbased algorithm, as measured by time, space and solutionpath cost. We present a criterion to predict the time for the wavefrontpropagation algorithm and the Snell'slaw algorithm to solve problems; this allow the selection of the fastest algorithm. We also develop improvements to the wavefrontpropagation algorithm that decrease its averagecase time requirements and we prove properties of Snell's law when applied to the weightedregion 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