Back to search

Monterey, California. Naval Postgraduate School

Construction of optimal-path maps for homogeneous-cost-region path-planning problems.

Abstract

dc:description.abstract

Fast 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.

Degree

thesis:*
Name thesis:degree_name
Ph.D. in Computer Science
Level thesis:degree_level
Doctoral
Discipline thesis:degree_discipline
Computer Science
Department dc:contributor.department
Computer Science
College dc:contributor.school
Naval Postgraduate School
Grantor dc:publisher
Monterey, California. Naval Postgraduate School
Year dc:date.issued
1989

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Alexander, Robert S.
Advisor dc:contributor.advisor
  • Rowe, Neil C.

Rights

dc:rights
Statement dc:rights
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10945/26432

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-20
Source record
OAI-PMH GetRecord
related terms
citation

Alexander, Robert S.. Construction of optimal-path maps for homogeneous-cost-region path-planning problems.. Doctoral thesis, Monterey, California. Naval Postgraduate School, 1989. https://hdl.handle.net/10945/26432