Back to search

Monterey, CA; Naval Postgraduate School

SAFE NAVIGATION: ROUTE PLANNING IN CONTESTED ENVIRONMENTS USING SHORTEST PATH ALGORITHMS

Abstract

dc:description.abstract

Tactical route planning in the military through complex road networks requires a robust knowledge of both the battlespace and the threat laydown in an area of operations. Threat positioning and engagement areas are crucial factors in deciding how friendly assets maneuver the battlespace, with exposure leading to asset loss or mission failure. This thesis investigates whether dynamic programming (DP) algorithms can be adapted to generate safe, optimal paths by integrating probabilistic risk into an urban road network. To model contested environments, we utilized open-source crime data from the cities of Oakland and Cleveland as a proxy for threat activity. A safety-annotated graph is then generated by assigning risk values to road segments for analysis. Utilizing DP algorithms Dijkstra and A*, we show safe-path finding (SPF) solutions across the two road networks. Our results demonstrate that the A* algorithm on safety-annotated graphs improves computational performance from baseline Dijkstra, and DP solutions can identify safe paths through the road network. This work provides a viable framework for military route planning, enabling safe traversal of friendly assets in contested environments.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Computer Science
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Computer Science
Department dc:contributor.department
Computer Science (CS)
Grantor dc:publisher
Monterey, CA; Naval Postgraduate School
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zimmer, Jason K.
Advisor dc:contributor.advisor
  • Barton, Armon C.
Committee member dc:contributor.committeemember
  • Litton, Matthew L.

Rights

dc:rights
Statement dc:rights
  • This 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.
  • Distribution Statement A. Approved for public release: Distribution is unlimited.

Identifiers

dc:identifier.*
Dc Identifier Programcode
368, Computer Science
Thesis Thesis Identifier
41326

Chain of custody

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

Zimmer, Jason K.. SAFE NAVIGATION: ROUTE PLANNING IN CONTESTED ENVIRONMENTS USING SHORTEST PATH ALGORITHMS. Masters thesis, Monterey, CA; Naval Postgraduate School, 2025. https://hdl.handle.net/10945/74751