Monterey, CA; Naval Postgraduate School
SAFE NAVIGATION: ROUTE PLANNING IN CONTESTED ENVIRONMENTS USING SHORTEST PATH ALGORITHMS
Abstract
dc:description.abstractTactical 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