Show simple item record

dc.contributor.advisorRowe, Neil C.
dc.contributor.authorAlexander, Robert S.
dc.date.accessioned2013-01-23T21:59:27Z
dc.date.available2013-01-23T21:59:27Z
dc.date.issued1989-09
dc.identifier.urihttp://hdl.handle.net/10945/26432
dc.descriptionApproved for public release; distribution is unlimited.en_US
dc.description.abstractFast path-planning algorithms are needed for autonomous vehicles and tactical terrain-analysis tools. We explore a new approach using "optimal-path maps", that give the best path to a goal point from any given start point in cross-country two-dimensional terrain for a moving agent of negligible size. Such maps allow fast point-location algorithms at run-time to categorize die start point according to the behavior of the optimal path to the goal, from which the path can be reconstructed. We study terrain modelled by piecewise-linear roads and rivers, polygonal obstacles, and by convex polygonal homogeneous-cost areas ("weighted regions"). We explore two methods for constructing optimal-path maps, one based on wavefront-propagation point-to-point path planning, and a more exact divide-and-conquer algorithm that reasons about how optimal paths must behave. In the exact approach, boundaries caused by terrain features are characterized using analytical geometry and optimal-path principles, and partial optimal-path maps are merged into complete ones.en_US
dc.description.urihttp://archive.org/details/constructionofop00alex
dc.format.extent288 p.en_US
dc.language.isoen_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.titleConstruction of optimal-path maps for homogeneous-cost-region path-planning problems.en_US
dc.typeThesisen_US
dc.contributor.schoolNaval Postgraduate School
dc.contributor.departmentComputer Science
dc.subject.authorPathsen_US
dc.subject.authorRoutesen_US
dc.subject.authorPath-Planningen_US
dc.subject.authorShortest-Path Mapsen_US
dc.subject.authorOptimal-Path Mapsen_US
dc.subject.authorWeighted Region Problemen_US
dc.subject.authorWavefront Propagationen_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