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.
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
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 ...
Kilic, Sedat (Monterey, California: Naval Postgraduate School, 2016-12);East Asia is an important region for global stability. Major economies—China, Japan, and South Korea—are located in the region. The phenomenon of a rising China, the response of the United States to a rising China, and the ...