A stochastic approach to the weighted-region problem : 1. the design of the path annealing algorithm
Kindl, Mark R.
Rowe, Neil C.
MetadataShow full item record
This 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 a set of non-overlapping convex homogeneous-cost regions on a two dimensional plane. Each region is associated with a cost coefficient (or weight), which indicates the relative cost per unit distance of movement in that region by the point agent. The weighted distance between two points in a convex region is the product of the corresponding cost coefficient and the Euclidean distance between them. Given a start and a goal point on the plane, the objective of the Weighted-Region Problem is to find a minimum cost path from start to goal through the weighted regions. We have designed and developed a very efficient algorithm for finding near-optimal solutions for the Weighted-Region Problem using a combination of the classical artificial intelligence heuristic search techniques and the probabilistic combinatorial optimization technique called simulated annealing. Extensive test results (to be presented in Part II of the paper) indicate that the new algorithm runs much faster than previous known techniques with a very minimal sacrifice in optimality
NPS Report NumberNPS-CS-91-014
Showing items related by title, author, creator and subject.
Kindl, Mark Richard (Monterey, California. Naval Postgraduate School, 1991-03);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 grid based techniques for solving the weighted region least cost path problem on multicomputers Ekin, Cengiz (Monterey, California. Naval Postgraduate School, 1992-12);This thesis explores the possibilities of developing fast grid parallel algorithms to solve the Weighted Region Least Cost Path problem. Two complimentary steps have been undertaken. First, an efficient sequential algorithm ...
Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects Rowe, Neil C.; Ross, Ron S. (Monterey, California. Naval Postgraduate School, 1990-10);Anisotropic (heading-dependent) phenomena arise in the "two-and-one-half-dimensional" path-planning problem of finding minimum-energy routes for a mobile agent across some hilly terrain. We address anisotropic friction ...