A Stochastic Approach to Path Planning in the Weighted-Region Problem
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1991
- Accession Number
- ADA234492
Entities
People
- Mark R. Kindl
Organizations
- Naval Postgraduate School