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.

Report Date:

1987-06-01

Pagination or Media Count:

429.0

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 Snells 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 Snells-law-based algorithm is compared to that of a dynamic-programming, wavefront-propagation technique. Test results show average-case superiority of the Snells-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 Snells-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 Snells 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