A stochastic approach to the weighted-region problem
Subtitle: 1. the design of the path annealing algorithm
By: Mark R. Kindl, Man-Tak Shing, Neil C. Rowe
Contributors: Shing, Man-Tak; Rowe, Neil C.; Naval Postgraduate School (U.S.). Dept. of Computer Science
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1991
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 41
Subjects: Stochastic processes; Paths; Annealing; Heuristic methods; Algorithms
Other titles: NPS-CS-91-014.
Description: 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.
Notes: Title from cover.

"NPS-CS-91-014."

"June 1991."

AD A243 324.

Includes bibliographical references (p. 40-41).

aq/aq cc:9116 05/28/98