USAFA DFEC

ECE 495 — Electromagnetic Warfare and Survivability

Block 4: Aircraft Survivability and Mission Planning
Lesson 34: Optimal Path Planning
Juan Jurado, Col, USAF, Ph.D.
Permanent Professor and Head
Electrical and Computer Engineering
Fall 2026
←→ navigate · C draw · B board · S speaker view · F fullscreen · ? all shortcuts

Block 4 · Lesson 34 · Where We Left Off

Where We Left Off

Three lessons built the threat picture one layer at a time:

  • L31: survival multiplies, so risk adds — $r = -\ln P_S$
  • L32: detection contours and MEZ rings drew where each site can kill
  • L33: information geometry showed where their sensors see you well
The map is finished. The aircraft still has to cross it: which way do you fly?

Block 4 · Lesson 34 · Objectives

Lesson Objectives

By the end of this lesson, you will be able to:

  • Pose routing as a shortest path and run Dijkstra by hand and in MATLAB
  • Design an edge cost — distance, exposure, and why exposure is $-\ln(1-p)$
  • Trace the risk-versus-length Pareto front and fly it under a fuel limit
  • Explain why aspect makes the route graph directed
Make risk additive and the safest route is just the shortest path.

Block 4 · Lesson 34 · Graphs

The Map Becomes a Graph

IN TGT node edge weight
  • A node is a place to be; an edge is a leg to fly
  • Each edge carries a weight: what that leg costs
  • A route's cost is the sum of its legs' weights

So the best route is the cheapest path — once you decide what "cost" means.

Block 4 · Lesson 34 · Dijkstra

Dijkstra's Algorithm: Settle the Cheapest, Relax Its Edges

1
Label the start 0 and every other node $\infty$ — the best cost-to-come known so far:
$g(\text{IN}) = 0,\quad g(v) = \infty$
2
From the frontier, settle the node with the smallest label — it can never get cheaper:
$u = \arg\min_{v \in \text{frontier}} g(v)$
3
Relax each edge out of $u$ — keep whichever way in is cheaper:
$g(v) \leftarrow \min\big(g(v),\ g(u) + c_{uv}\big)$
4
Stop when the target settles, then walk the predecessors back.
weights must be $\ge 0$

Block 4 · Lesson 34 · Dijkstra

Dijkstra by Hand

2 5 2 7 3 6 4 2 IN A B C D TGT
1
Settle IN (0)
A 2 · B 5
2
Settle A (2): B drops to 4
B 4 · C 9
3
Settle B (4): C drops to 7
C 7 · D 10
4
Settle C (7)
D 10 · TGT 11
5
Settle D (10): 10 + 2 = 12, no gain
TGT 11
6
Settle TGT (11); walk back
IN–A–B–C–TGT

Block 4 · Lesson 34 · Cost Design

What Should an Edge Cost?

Distance only
$c_e = \ell_e$
Exposure only
$c_e = r_e$
Blended
$c_e = w_d\,\ell_e + w_r\,r_e$
  • Distance finds the shortest route — straight through whatever is in the way
  • Exposure ignores fuel — any zero-risk wander, however long, ties for best
  • The blend has one real knob, $w = w_r/w_d$: the km you would fly to cut risk by one unit

Block 4 · Lesson 34 · Cost Design

Exposure Must Add: Why $-\ln(1-p)$

1
Survive every leg (independent, L31) — survival multiplies:
$P_S = \prod_e (1 - p_e)$
2
Take $-\ln$ and the product becomes a sum — Dijkstra adds:
$-\ln P_S = \sum_e -\ln(1 - p_e) = \sum_e r_e$
3
The L31 hazard makes it a length: $\lambda_i = -\ln(1-p_\text{shot})/\Delta s$ over the lethal zone:
$r_e = \sum_i \lambda_i\,\ell_{i,e}$
Why not just add the $p$'s? One leg at 0.40 or two at 0.22: $\sum p$ picks the single leg, but $P_S$ is 0.600 against 0.608.

Block 4 · Lesson 34 · Trade-off

Sweep the Weight, Trace the Front

0.5 1.0 0 440 480 520 560 route length (km) PS fuel limit w = 0: shortest each point: one w, one Dijkstra run
  • Each weight $w$ gives one route — one point of length and $P_S$
  • Sweeping $w$ traces the Pareto front: no route beats these on both at once
  • The fuel limit $L_\text{max}$ is not a Dijkstra weight — it is applied to the sweep's answers

Fly the safest point that still fits left of the line.

Block 4 · Lesson 34 · Grid

A Grid Over the Battlespace

  • Cell centers are nodes; each links to its 8 neighbors
  • Legs are 10 km, or $10\sqrt{2} = 14.1$ km on a diagonal
  • Each edge's risk sums $\lambda\ell$ over the lethal zones it crosses
  • Caveats: headings only every 45°, routes zig-zag, rings snap to cells
400 × 300 km at 10 km = 1,200 nodes — shortestpath takes milliseconds.
10 14.1

Block 4 · Lesson 34 · Aspect

Aspect Makes the Graph Directed

a → b: nose-on b → a: tail-on nose-on range tail-on range b radar a
  • An edge's heading sets the aspect each radar sees: $\theta = \phi + 180^\circ - \psi$
  • Aspect sets $\sigma$, and $R_\text{det} \propto \sigma^{1/4}$ sets how much of the leg is lethal
  • Toward a radar shows the nose; away shows the tail — so $c_{a\to b} \ne c_{b\to a}$

Same two nodes, two costs: a digraph, not a graph.

Block 4 · Lesson 34 · Honesty

Low Cost Is Not Low Risk

Dijkstra is exact — for the cost you gave it. The cost is only as honest as the model:

  • Plan with the nose-on $\sigma$ and the planner promises a clean route through a gap
  • Re-score that same route with aspect and the gap closes at the beam
  • Check every plan against a better model than the one that chose it
Cost is the model's promise, not the outcome.

Beyond Dijkstra: continuous optimization (fmincon, particle swarm) smooths the route off the grid.

Block 4 · Lesson 34 · Quick Exercise

Quick Exercise / Type-along: Reroute Around a Pop-Up

Type this with me — six nodes, eight legs, one kill probability per leg.

% L34 -- the safest route is a shortest path on -ln(1-p)
s = [1 1 2 2 3 3 4 5];                  % leg start nodes
t = [2 3 3 4 4 5 6 6];                  % leg end nodes
p = [.20 .10 .05 .25 .15 .05 .12 .08];  % P_K on each leg
G = graph(s, t, -log(1-p));             % additive risk cost
[route, r] = shortestpath(G, 1, 6);
fprintf('%-10s P_S = %.3f\n', mat2str(route), exp(-r))
G.Edges.Weight(findedge(G,3,5)) = -log(1-0.40);   % pop-up on 3-5
[route, r] = shortestpath(G, 1, 6);
fprintf('%-10s P_S = %.3f\n', mat2str(route), exp(-r))

Check the first line by hand: multiply $(1-p)$ along the route.

Then: make $p$ itself the weight. Same routes? Same $P_S$?

Block 4 · Lesson 34 · Quick Problem

Quick Problem: Three Costs, Three Routes

A four-node ingress: IN, turn points A and B, and TGT. Each leg has a length $\ell$ and an exposure $r = \sum\lambda\ell$.

  • IN–A: 80 km, $r = 0.15$
  • IN–B: 95 km, $r = 0$
  • A–B: 80 km, $r = 0$
  • A–TGT: 120 km, $r = 0$
  • B–TGT: 70 km, $r = 0.40$
  • Blend: $c = \ell + w\,r$ with $w = 250$ km
  1. (a) Distance only: the route, and its $P_S$.
  2. (b) Exposure only: the route, and its length.
  3. (c) The blend: the route, its length and its $P_S$.
(a) IN–B–TGT, 165 km, $P_S = 0.670$  ·  (b) IN–B–A–TGT, 295 km  ·  (c) IN–A–TGT, 200 km, $P_S = 0.861$

Today's Interactive Demo: Route Planner

Companion script: L34_RoutePlanner.m
Live demo

Route Planner

usafa-ece.github.io/ece-495-ew

Block 4 · Lesson 34 · Wrap-Up

Wrap-Up

Key ideas
  • Routing is a shortest path: Dijkstra settles the cheapest node and relaxes its edges
  • Exposure must be additive: $r_e = -\ln(1-p_e) = \sum\lambda\ell$, so min $\sum r$ is max $P_S$
  • Sweep $w$ for the Pareto front; the fuel limit picks the route off it
  • Aspect makes costs depend on heading — a digraph
Next lesson
  • L35: Fusion Under Threat — tracking a pop-up threat from bearings alone
  • Final Project: this lesson builds the route engine for T3
  • Work the L35 pre-flight before class