Show simple item record

dc.contributor.authorKindl, Mark R.
dc.contributor.authorRowe, Neil C.
dc.dateMarch 2012
dc.date.accessioned2013-09-18T17:39:23Z
dc.date.available2013-09-18T17:39:23Z
dc.date.issued2012-03
dc.identifier.urihttp://hdl.handle.net/10945/36455
dc.descriptionThis paper appeared in the International Workshop on Bio and Intelligent Computing, Fukuoka, Japan, March 2012.en_US
dc.description.abstractThis 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.en_US
dc.description.sponsorshipsupported by the Navy Center for Applied Research in Artificial Intelligence and by the Naval Postgraduate Schoolen_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.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.en_US
dc.titleEvaluating Simulated Annealing for the Weighted-Region Path-Planning Problemen_US
dc.typeConference Paperen_US
dc.contributor.departmentComputer Science (CS)
dc.subject.authorpath planningen_US
dc.subject.authorsimulated annealingen_US
dc.subject.authorweighted regionsen_US
dc.subject.authorminimum costen_US
dc.subject.authorstochastic algorithmsen_US
dc.description.funderfunds provided by the Chief for Naval Operationsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record