Reading — Optimal Path Planning

Reading — Optimal Path Planning#

By the end of this lesson you should be able to:

  1. Pose routing as a shortest path on a graph and run Dijkstra’s algorithm by hand and in MATLAB (graph, digraph, shortestpath).

  2. Design an edge cost — distance, exposure, or a blend — and explain why exposure must be written as \(-\ln(1-p)\).

  3. Trace the risk-versus-length Pareto front by sweeping the weight, and choose a route under a fuel limit.

  4. Explain why aspect makes the route graph directed, so that flying a leg one way costs something different from flying it back.

From a threat picture to a route#

Three lessons built the threat picture one layer at a time. L31 gave the survival metric: independent encounters multiply, \(P_S = \prod_i (1 - P_{K,i})\), so the log of survival adds, \(-\ln P_S = \sum_i -\ln(1-P_{K,i})\). L32 drew where each site can detect and engage — aspect-dependent detection contours inside MEZ rings. L33 mapped how well the adversary’s sensors can locate you across the same map. The map is finished; the aircraft still has to cross it. Which way do you fly?

Ask a room full of people and two answers come back: the shortest line, and a bend around the biggest ring. Each is right about something. The shortest route burns the least fuel and flies straight through the threat; the long way around is safe and may not get home. This lesson turns that argument into a calculation — one that states exactly what “best” means, finds the best route for that meaning, and shows what you give up for it. It is also the route engine of the Final Project (task T3), taught here on a different map with different sites and numbers.

Routes are paths on a graph#

A graph is a set of nodes joined by edges. For route planning, a node is a place the aircraft can be — a waypoint, or the center of a grid cell — and an edge is a leg it can fly between two of them. Each edge carries a weight \(c_e \ge 0\), the cost of flying that leg. A route from the ingress point IN to the target TGT is a path: a sequence of edges, end to end. Its cost is the sum of its edges’ weights,

\[ C(\text{route}) = \sum_{e \,\in\, \text{route}} c_e . \]

Once the weights are set, “find the best route” is “find the cheapest path from IN to TGT” — the shortest-path problem, one of the most thoroughly solved problems in computing. Everything interesting about route planning moves into one question the algorithm cannot answer for you: what should an edge cost? Before that question, the algorithm.

Dijkstra’s algorithm#

Edsger Dijkstra’s 1959 algorithm finds the cheapest path from one start node to every other node, provided no weight is negative. It keeps, for every node \(v\), a label \(g(v)\): the cheapest cost-to-come found so far. It grows a set of settled nodes whose labels are final, and a frontier of nodes that have a tentative label but are not settled yet.

  1. Initialize. \(g(\text{IN}) = 0\); every other label is \(\infty\). IN is the only node on the frontier.

  2. Settle the frontier node \(u\) with the smallest label. That label is now final.

  3. Relax every edge out of \(u\): for each neighbor \(v\), keep the cheaper of its old label and the new way in, \(g(v) \leftarrow \min\big(g(v),\ g(u) + c_{uv}\big)\), and remember \(u\) as \(v\)’s predecessor whenever the new way wins.

  4. Repeat from step 2 until TGT settles; then walk the predecessors back from TGT to read the route.

Why is it safe to freeze the smallest label in step 2? Every other way into \(u\) has to leave the frontier through some node whose label is already at least \(g(u)\), and then add weights that are never negative, so no later discovery can bring \(u\) in cheaper. That argument is also exactly why the weights must be non-negative: one negative edge could undercut a node after it had been settled. Both costs this lesson uses — lengths and \(-\ln(1-p)\) — are never negative.

Work it on the six-node network from the slides: IN–A 2, IN–B 5, A–B 2, A–C 7, B–C 3, B–D 6, C–TGT 4, D–TGT 2.

Step

Settle

Relaxation

Frontier afterward

1

IN (0)

A ← 2, B ← 5

A 2, B 5

2

A (2)

B ← min(5, 2+2) = 4; C ← 9

B 4, C 9

3

B (4)

C ← min(9, 4+3) = 7; D ← 10

C 7, D 10

4

C (7)

TGT ← 11

D 10, TGT 11

5

D (10)

TGT: 10 + 2 = 12, no improvement

TGT 11

6

TGT (11)

stop

—

Walking the predecessors back gives IN–A–B–C–TGT at cost 11; the next-best routes, IN–B–C–TGT and IN–A–B–D–TGT, cost 12. Two things in the table are worth a second look. The bold entries are relaxations that improved a tentative label — B was first reached at 5 directly and then at 4 through A — which is why a label is only a promise until its node settles. And D settles before TGT even though it is not on the final route: Dijkstra expands every node cheaper than the target before it can be sure about the target. With a heap (priority queue) holding the frontier, the whole search costs on the order of \((V + E)\log V\) operations for \(V\) nodes and \(E\) edges; the 1,200-node grids below solve in milliseconds.

Key Concept

Dijkstra settles the cheapest frontier node, relaxes its edges, and repeats until the target settles. It is exact for any non-negative weights and any graph — which means all of the planning judgment lives in the weights you give it, not in the algorithm.

Dijkstra in MATLAB#

MATLAB builds the graph from three vectors — the start node, the end node and the weight of each edge — and shortestpath runs Dijkstra on it. The worked example is four lines:

s = [1 1 2 2 3 3 4 5];  t = [2 3 3 4 4 5 6 6];   % IN=1 A=2 B=3 C=4 D=5 TGT=6
G = graph(s, t, [2 5 2 7 3 6 4 2]);
[route, cost] = shortestpath(G, 1, 6)            % route [1 2 3 4 6], cost 11
e = findedge(G, 2, 3);                           % the A-B edge's index

graph makes every edge two-way with one weight. When a leg costs something different in each direction, build a digraph instead — each edge is one-way, so a two-way leg is two edges, digraph([s t], [t s], [w_there w_back]). Two more tools matter for planning: findedge(G, a, b) finds an edge so its weight can be changed in place (G.Edges.Weight(e) = ...), and a third output, [route, cost, edges] = shortestpath(G, s, t), returns the edge indices along the route, so any other per-edge quantity — a length, a risk — can be summed along it.

What should an edge cost?#

Three candidate costs, each with an honest failure:

  • Distance only, \(c_e = \ell_e\). The shortest route — straight through whatever stands in the way. Fuel is minimized; survival is whatever it happens to be.

  • Exposure only, \(c_e = r_e\). The least-exposed route — and, because every unexposed leg costs nothing, no reason to stop wandering. A 1,000 km zero-exposure loop ties with a 300 km one, so the planner can return an absurd dogleg that no aircraft has the fuel to fly.

  • Blended, \(c_e = w_d\,\ell_e + w_r\,r_e\). Only the ratio matters (doubling both weights doubles every route’s cost and changes nothing), so there is one real knob: \(w = w_r/w_d\), in km per unit of exposure. With \(w_d = 1\), a weight of \(w = 200\) km says “I will fly 2 extra km to cut the exposure by 0.01” — about one point of \(P_S\) when survival is already high.

The Quick Problem below makes all three failures concrete on a four-node map. First, though, “exposure” needs a definition that the algorithm can actually use.

Exposure must add: why \(-\ln(1-p)\)#

Dijkstra minimizes a sum of edge weights. Survival along a route is a product: if leg \(e\) carries an independent kill probability \(p_e\), the route survives with

\[ P_S = \prod_{e \,\in\, \text{route}} (1 - p_e). \]

Take the negative logarithm of both sides and the product becomes a sum:

\[ -\ln P_S = \sum_{e \,\in\, \text{route}} -\ln(1 - p_e) = \sum_{e \,\in\, \text{route}} r_e, \qquad r_e = -\ln(1 - p_e) \ge 0 . \]

Because \(-\ln\) is monotone decreasing, the route with the smallest \(\sum r_e\) is exactly — not approximately — the route with the largest \(P_S\). So the edge weight that makes Dijkstra maximize survival is \(r_e = -\ln(1-p_e)\), and a planner’s answer converts back with \(P_S = e^{-\sum r_e}\).

L31’s hazard model hands you \(r_e\) directly as a length. A site in engagement takes a shot every \(\Delta s\) km of track, each killing with probability \(p_\text{shot}\); over \(\ell\) km inside its lethal zone the aircraft survives \((1-p_\text{shot})^{\ell/\Delta s} = e^{-\lambda \ell}\), with hazard

\[ \lambda = \frac{-\ln(1 - p_\text{shot})}{\Delta s}\quad \text{per km}. \]

The lethal zone is the part of the map inside both the site’s detection range and its MEZ — detected and within reach. An edge that spends \(\ell_{i,e}\) km inside site \(i\)’s lethal zone therefore carries \(r_e = \sum_i \lambda_i\,\ell_{i,e}\), additive across sites and across edges, and the route’s survival is \(P_S = \exp\!\big(-\sum_i \lambda_i \ell_i\big)\).

Why not simply add the \(p\)’s? Because \(p \approx -\ln(1-p)\) only while \(p\) is small, and the legs a planner is choosing between are exactly the ones where it is not. Compare one leg at \(p = 0.40\) with two legs at \(p = 0.22\) each. Adding raw probabilities says the single leg is safer (\(0.40 < 0.44\)), but its survival is \(0.600\) against \(0.78^2 = 0.608\) for the pair; the log costs get it right (\(0.511 > 0.497\)). The raw-\(p\) planner is wrong in exactly the case that matters — one heavy leg against several light ones.

Key Concept

Survival multiplies along a route; Dijkstra adds. The edge weight \(r_e = -\ln(1-p_e) = \sum_i \lambda_i \ell_{i,e}\) turns the product into a sum, so the minimum-cost route is the maximum-\(P_S\) route. Make risk additive and the safest route is just the shortest path.

Sweeping the weight: the Pareto front#

A single weight gives a single route. Sweep \(w\) from 0 upward, run Dijkstra once per value, and record each route’s length \(L\) and survival \(P_S\). At \(w = 0\) you get the shortest route; as \(w\) grows the route peels away from the rings, getting longer and safer; at large \(w\) it becomes the least-exposed route the map allows. Plotted as \(P_S\) against \(L\), the points trace the Pareto front: the set of routes that no other route beats on both length and survival at once. Any route below the front is simply a worse choice — a shorter route exists with the same survival, or a safer one of the same length.

The front is the honest answer to “shorter or safer?”: it shows the price of each increment of survival in kilometers. The fuel limit \(L_\text{max}\) then turns the front into a decision — fly the safest route on the front whose length fits, \(\max P_S\) subject to \(L \le L_\text{max}\). If even the \(w = 0\) route is longer than \(L_\text{max}\), the mission is infeasible as planned.

Notice where the limit is enforced: in the sweep, not inside Dijkstra. Dijkstra is exact because each node needs only one label, its best cost so far. A length budget adds a second quantity — length used — that has to be carried alongside the cost, and “cheapest path within a budget” is the resource-constrained shortest-path problem, which is hard in general. The sweep keeps each Dijkstra run exact on a single cost and moves the constraint to a choice among its answers. The price is a small blind spot: a weighted-sum sweep finds the front’s outward corners but can miss a route sitting in a dent of the front, which is worth one sentence in any report that relies on it.

A grid over the battlespace#

Real maps have no hand-picked waypoints, so the planner lays a grid over the whole battlespace. This lesson’s demo and companion script use a 400 km (East) × 300 km (North) box in 10 km cells: 1,200 nodes at the cell centers, each joined to its 8 neighbors — four legs of 10 km and four diagonals of \(10\sqrt{2} = 14.1\) km, 9,184 directed edges in all. Each edge’s length is its weight’s distance term; its exposure \(r_e\) comes from checking five evenly spaced points along it against every site’s lethal zone, each point standing for a fifth of the edge.

The grid is a model, and it has a model’s caveats:

  • Headings come only every 45°. A route toward a target at 22.5° has to zig-zag, and an 8-connected route can be up to about 8% longer than the straight line it stands in for.

  • Rings snap to cells. A 10 km cell cannot resolve where a 45 km ring really falls; finer cells fix that at more computing cost.

  • Many routes tie. On a grid, a long straight leg can be flown as many equally long staircases. The demo and script break ties toward the safer route by adding a negligible \(10^{-6}\,r_e\) to every weight.

None of these changes the method; all of them are reasons to read a planned route as a corridor, not a flight-plan line.

Aspect makes the graph directed#

Block 1’s range law says detection range grows as the fourth root of the radar cross-section, \(R_\text{det} = R_\text{ref}(\sigma/\sigma_\text{ref})^{1/4}\), and Block 3 showed that an aircraft’s \(\sigma\) depends strongly on aspect. L32 combined them into a detection contour that depends on the aircraft’s heading. On a graph, every edge is a heading. With bearings clockwise from North, an aircraft at bearing \(\phi\) from a radar and flying heading \(\psi\) sees the radar at bearing \(\phi + 180^\circ\), so the aspect the radar sees is

\[ \theta = \operatorname{wrap}(\phi + 180^\circ - \psi), \]

\(0^\circ\) nose-on and \(180^\circ\) tail-on. Flying toward the radar shows it the nose; flying the same leg the other way shows it the tail. If the tail is brighter than the nose — as it is for almost any real aircraft — the detection range, the length of the leg that is lethal, and therefore \(r_e\) all differ between \(a \to b\) and \(b \to a\). One pair of nodes now carries two costs, so the graph must be a directed graph: in MATLAB, digraph with both directions listed, not graph.

The demo makes this concrete with a simple two-lobe signature: relative to the nose, the tail is 6 dB brighter and the two beam lobes 16 dB brighter, blended smoothly between. Its readout “same path reversed” flies the planned route backward: in the aspect-aware mode the survival changes, and in either aspect-blind mode it cannot. The aspect-aware planner also does something that looks odd until you see why — it weaves, turning its nose toward a radar for a leg to shrink that radar’s detection range as it squeezes past. On a 45° grid the weave shows up as a zig-zag.

The alternative is to ignore aspect and give the planner one \(\sigma\) for every heading. There are two ways to choose it. The worst-case value is always pessimistic: every ring is as large as it ever gets, and the planner pays length to avoid threats it could have slipped past. The nose-on value is optimistic wherever the aircraft is louder than its nose — for the demo’s two-lobe model that is every other aspect, so the planner happily flies past radars beam-on. A real low-observable pattern need not have its quietest aspect at the nose, though: where the quarters are quieter than the nose, the nose-on planner overestimates those rings, so its error runs both ways. Either way, only re-scoring the route with the real pattern tells you what it flew.

Low cost is not low risk#

Dijkstra is exact — for the cost you gave it. The cost is a promise made by a model: a \(\sigma\), a set of hazards, a set of rings, a grid. When the model is wrong, the planner is confidently wrong. In the demo’s default map, planning with the nose-on \(\sigma\) finds a way between the small nose-on rings and promises \(P_S = 1.000\); re-scored with the aspect-dependent signature, that same route survives with \(P_S = 0.077\), because it skirts one site and threads between two others beam-on to all three. Nothing about Dijkstra failed. The cost described a different aircraft from the one flying.

The discipline that follows is simple and worth making a habit: re-score every planned route under a better model than the one that chose it, and report both numbers.

Dijkstra on a grid is not the only way to plan. Continuous formulations treat the waypoints themselves as variables and optimize them directly with tools such as fmincon or particle swarm; they smooth away the grid’s zig-zag, at the cost of local minima and no guarantee of the global best. They are beyond this lesson.

Type-along

The six-node network from the worked example, now with a kill probability on each leg instead of an integer cost: node 1 is the ingress, node 6 the target. Plan the safest route, then a pop-up SAM raises one leg’s kill probability to 0.40 — plan again.

% 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))

Then answer these two:

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

  2. Make \(p\) itself the weight. Same routes? Same \(P_S\)?

Solution

[1 3 5 6]  P_S = 0.787
[1 3 4 6]  P_S = 0.673

  1. Along 1–3–5–6 the legs carry \(p = 0.10, 0.05, 0.08\), so \(P_S = 0.90 \times 0.95 \times 0.92 = 0.787\) — the same number the log-sum gave, because \(e^{-\sum r} = \prod(1-p)\). After the pop-up, 1–3–5–6 falls to \(0.90 \times 0.60 \times 0.92 = 0.497\) and the best way on from node 3 is 3–4–6: \(0.90 \times 0.85 \times 0.88 = 0.673\). The route changed only past node 3, because 1–3 is still the cheapest way to get there.

  2. The routes come out the same here — every \(p\) is small, so \(p \approx -\ln(1-p)\) — but the numbers are wrong. The raw sums are 0.23 and 0.37, so \(e^{-\sum p}\) reads 0.795 and 0.691 and \(1 - \sum p\) reads 0.770 and 0.630, against the true 0.787 and 0.673. With one heavy leg against several light ones, the raw-\(p\) planner can pick the wrong route outright.

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

(a) Distance only: the route, and its \(P_S\).
(b) Exposure only: the route, and its length.
(c) The blend: the route, its length and its \(P_S\).

Solution

List the four routes once, then score them three ways:

Route

\(\ell\) (km)

\(\sum r\)

\(\ell + 250\sum r\)

\(P_S = e^{-\sum r}\)

IN–A–TGT

200

0.15

237.5

0.861

IN–B–TGT

165

0.40

265.0

0.670

IN–A–B–TGT

230

0.55

367.5

0.577

IN–B–A–TGT

295

0

295.0

1.000

(a) Distance only picks IN–B–TGT, 165 km, with \(P_S = e^{-0.40} =\) 0.670.

(b) Exposure only picks IN–B–A–TGT, the only route with no exposure — 295 km, nearly twice the shortest.

(c) The blend picks IN–A–TGT at a cost of 237.5: 200 km, \(P_S = e^{-0.15} =\) 0.861.

So what: each pure cost picks an extreme — the short lethal leg, or the dogleg no aircraft could afford — and the blend picks the route a planner would actually fly. The blend prefers IN–A–TGT to IN–B–TGT once \(w > 35/0.25 = 140\) km, and would switch to the dogleg only past \(w = 95/0.15 \approx 633\) km.

Wrap-Up#

Routing is a shortest-path problem: lay a graph over the map, give every leg a non-negative cost, and Dijkstra settles the cheapest node, relaxes its edges, and returns the cheapest route exactly. The planning judgment lives in the cost. Distance alone flies through the threat, exposure alone wanders without limit, and the blend \(c_e = \ell_e + w\,r_e\) has one knob; sweeping it traces the risk-versus-length Pareto front, and the fuel limit picks the route off that front. Exposure has to be \(r_e = -\ln(1-p_e) = \sum\lambda\ell\), because survival multiplies and Dijkstra adds — make risk additive and the safest route is just the shortest path. Aspect makes each leg’s cost depend on its heading, so the graph is directed. And the cost is the model’s promise, not the outcome: re-score every plan under a better model. Next, L35 follows a pop-up threat that is not on the map at all, and tracks it from bearings alone.

Contents