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

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.