Evaluating Simulated Annealing for the Weighted-Region Path-Planning Problem

Abstract

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.