A stochastic approach to path planning in the Weighted-Region Problem
Kindl, Mark Richard
MetadataShow full item record
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 adaptation of the combinatorial optimization technique called simulated annealing. The WRP provides a cartographically powerful representation for planar maps. Terrain features are modeled by polygonal homogenous-cost regions. A cost efficient assigned to each region indicates the relative cost per unit distance for movement in the region by a point agent no the ground. Region cost coefficients are assumed to be invariant with direction of movement. Given a start and a 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 it Euclidian length and the cost coefficient of the region it crosses. Ideally, we seek the least cost path. However, as problem instances approach the actual complexity of the battlefield, faster solutions become more desirable than absolute optimality. We introduce heuristics designed to replace the search space independently of start and goal locations, thus allowing map preprocessing. We use other heuristics to improve the efficiency of local cost function optimization as well as the annealing process itself.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
A stochastic approach to the weighted-region problem : 1. the design of the path annealing algorithm Kindl, Mark R.; Rowe, Neil C.; Shing, Man-Tak (Monterey, California. Naval Postgraduate School, 1991-06); NPS-CS-91-014This paper presents an efficient heuristic algorithm for planning near-optimal high-level paths for a point agent through complex terrain modeled by the Weighted-Region Problem. The input to the Weighted-Region Problem is ...
Leban, Frank A. (Monterey, California. Naval Postgraduate School, 2008., 2008-12);In this dissertation a control scheme that provides motion compensation for a ship-based two-crane system suspending a single payload is developed. Historical experience during the conflict in Vietnam, along with the ...
Davis, George P., Jr. (Monterey, California. Naval Postgraduate School, 1988-06);Mesoscale vortices generated by western boundary currents are well observed and documented, particularly in the case of the Gulf Stream System. The movement of these rings in the region of the Gulf Stream is well studied ...