Accession Number:

ADA234492

Title:

A Stochastic Approach to Path Planning in the Weighted-Region Problem

Descriptive Note:

Doctoral thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1991-03-01

Pagination or Media Count:

270.0

Abstract:

Planning efficient long-range movement is a fundamental requirement of most military operations. Intelligent mobile autonomous vehicles designed for battlefield support missions must have this capability. We propose an efficient heuristic algorithm for planning near-optimal high-level routes through complex terrain maps, modeled by the Weighted-Region Problem WRP. The algorithm is driven by our adaption of the combinatorial optimization technique called stimulated annealing. The WRP provides a cartographically powerful representation for planar maps. Terrain features are modeled by polygonal homogenous-cost regions. A cost coefficient assigned to each region indicates the relative cost per unit distance for movement in that region by a point agent on the ground. Region cost coefficients are assumed to be invariant with direction of movement. Given a start and goal point, a solution not necessarily optimal is a set of piecewise-linear connected segments, spanning from start to goal. The cost of a solution path is the sum of the weighted lengths of all segments in the path, where the weighted length of each segment is the product of its Euclidean length and the cost coefficient of the region it crosses. Ideally, we seek the last cost path. However, as problem instances approach the actual complexity of the battlefield, faster solutions become more desirable than absolute optimality.

Subject Categories:

  • Navigation and Guidance

Distribution Statement:

APPROVED FOR PUBLIC RELEASE