Evaluating Simulated Annealing for the Weighted-Region Path-Planning Problem
Kindl, Mark R.
Rowe, Neil C.
MetadataShow full item record
This paper describes an efficient stochastic algorithm for planning near-optimal paths for a point agent moving through twodimensional weighted-region terrain from a specified start point to a specified goal point. Weighted-region terrain consists of polygonal regions with a constant traversal cost within each region, and models differences in vegetation and terrain that affect traversal. Our algorithm combines heuristic search with probabilistic optimization by simulated annealing. A key advantage of our approach is that it can be more easily implemented efficiently by distributed processing than other algorithms. It finds constrained random perturbations to the sequence of region edges that a class of paths cross, and for each sequence, opti!mizes a convex function to find the locally-optimal path. Test results show an implementation of our algorithm even on a single processor runs faster than representative implementations of the three major algorithms for this problem, with similar space requirements and a minimal penalty in optimality.
This paper appeared in the International Workshop on Bio and Intelligent Computing, Fukuoka, Japan, March 2012.
RightsThis 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.
Showing items related by title, author, creator and subject.
Shaffer, Brenda (2017-10-27);With Guest Lecturer Professor Brenda Shaffer, Center for Eurasian, Russian and Eastern European Studies (CERES), Georgetown University
Al Kaabi, Yousef H.; Al Kaabi, Khaled M. (Monterey, California. Naval Postgraduate School, 2011-12);The Arabian Gulf represents a significant part in the world because of its oil wealth. During the last thirty years, three wars have taken place in the region resulting in regional and global instability: the Iran-Iraq ...
Kittrie, Orde F. (Arizona State University, 2017-03);A “Track II” Middle East Chemical Weapons Task Force (Task Force) comprised of policy and technical experts from ten countries in the Middle East convened in 2016-17 to discuss chemical weapons acquisition and use in the ...