Stochastic Approach to Solving the 2 1/2 Dimensional Weighted Region Problem.

摘要

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.