Show simple item record

dc.contributor.advisorShing, Man-Tak
dc.contributor.authorKindl, Mark Richard
dc.dateMarch 1991
dc.date.accessioned2013-01-23T22:05:48Z
dc.date.available2013-01-23T22:05:48Z
dc.date.issued1991-03
dc.identifier.urihttp://hdl.handle.net/10945/26789
dc.descriptionApproved for public release; distribution is unlimiteden_US
dc.description.abstractPlanning efficient long-range movement is a fundamental requirement of most military operations. Intelligent mobile autonomous vehicles designed for battlefield support missions must have this capability. We propose an efficient heuristic algorithm for planning near-optimal high-level routes through complex terrain maps, modeled by the Weighted-Region Problem (WRP). The algorithm is driven by our adaptation of the combinatorial optimization technique called simulated annealing. The WRP provides a cartographically powerful representation for planar maps. Terrain features are modeled by polygonal homogenous-cost regions. A cost efficient assigned to each region indicates the relative cost per unit distance for movement in the region by a point agent no the ground. Region cost coefficients are assumed to be invariant with direction of movement. Given a start and a goal point, a solution (not necessarily optimal) is a set of piecewise-linear connected segments, spanning from start to goal. The cost of a solution path is the sum of the weighted lengths of all segments in the path, where the weighted length of each segment is the product of it Euclidian length and the cost coefficient of the region it crosses. Ideally, we seek the least cost path. However, as problem instances approach the actual complexity of the battlefield, faster solutions become more desirable than absolute optimality. We introduce heuristics designed to replace the search space independently of start and goal locations, thus allowing map preprocessing. We use other heuristics to improve the efficiency of local cost function optimization as well as the annealing process itself.en_US
dc.description.urihttp://archive.org/details/stochasticapproa00kind
dc.format.extent261 p.en_US
dc.language.isoen_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. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.en_US
dc.titleA stochastic approach to path planning in the Weighted-Region Problemen_US
dc.typeThesisen_US
dc.contributor.departmentDepartment of Computer Science
dc.subject.authorPath planningen_US
dc.subject.authorRoute planningen_US
dc.subject.authorShortest pathen_US
dc.subject.authorOptimizationen_US
dc.subject.authorSpatial reasoningen_US
dc.subject.authorSnell's Lawen_US
dc.subject.authorSimulated annealingen_US
dc.subject.authorWeighted-region problemen_US
dc.subject.authorPath annealingen_US
dc.subject.authorA* searchen_US
dc.description.serviceMajor, United States Armyen_US
etd.thesisdegree.namePh.D. in Computer Scienceen_US
etd.thesisdegree.levelDoctoralen_US
etd.thesisdegree.disciplineComputer Scienceen_US
etd.thesisdegree.grantorNaval Postgraduate Schoolen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record