A stochastic approach to solving the 2-1/2 dimensional weighted region problem
Loading...
Authors
Hilton, Cary Allen, Jr.
Subjects
Shortest path
Simulated annealing
Weighted region problem
Two-and-one-half-dimensional path planning
anisotropic path planning
Simulated annealing
Weighted region problem
Two-and-one-half-dimensional path planning
anisotropic path planning
Advisors
Shing, Man-Tak
Date of Issue
1991-06
Date
June 1991
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
This thesis describes a method of computing a feasible path solution for the anisotropic weighted region problem. Heuristics are used to locate an initial starting solution. This starting solution is iteratively improved using a golden ratio search to produce a solution within a specified tolerance. The path solution is then randomly perturbed or detoured through different region frontiers, and the golden ratio search is again applied. These random detours are controlled by a process known as simulated annealing, which determines the number of detours made and decides whether to accept or reject each path solution. Better solutions are always accepted and worse solutions are accepted based on a probability distribution. Accepting worse solutions allows an opportunity to escape from a local minimum condition and continue the search for the optimal path. Since an exhaustive search is not performed, the globally optimal path may not be found, but a feasible path can be found with this method.
Type
Thesis
Description
Series/Report No
Department
Department of Computer Science
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
121 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.