Lesson 34 Flashcards

Click a question to reveal the answer.

1. How does route planning become a shortest-path problem?

Lay a graph over the map: nodes are places the aircraft can be (waypoints or grid-cell centers), edges are legs it can fly, and each edge carries a non-negative weight — what that leg costs. A route's cost is the sum of its legs' weights, so the best route is the cheapest path from ingress to target.

2. State the two operations Dijkstra's algorithm repeats.

Settle the frontier node with the smallest label \(g(u)\) — that label is now final — then relax every edge out of it: \(g(v) \leftarrow \min\big(g(v),\ g(u) + c_{uv}\big)\). Repeat until the target settles, then walk the predecessors back to read the route.

3. Why must Dijkstra's edge weights be non-negative?

Settling the smallest label is safe only because every other way into that node starts at a label at least as large and adds weights that cannot be negative. A negative edge could undercut a node after it was settled, and the algorithm would return a wrong answer.

4. What is the difference between a tentative label and a settled one?

A tentative label is the cheapest cost-to-come found so far, and relaxation can still lower it when a cheaper way in turns up. A settled label is final. In the lesson's worked example, B is first reached at 5 directly and then drops to 4 through A before it settles.

5. When do you use graph and when digraph in MATLAB?

graph(s, t, w) stores one weight per node pair, usable both ways — right when a leg costs the same in each direction. digraph stores one-way edges, so a leg that costs something different each way is two edges with two weights. shortestpath(G, s, t) runs Dijkstra on either.

6. What goes wrong with a distance-only cost? With an exposure-only cost?

Distance only finds the shortest route — straight through whatever threat is in the way. Exposure only has no reason to stop wandering: every unexposed leg is free, so any zero-exposure dogleg ties for best however long it is, and the planner can return a route no aircraft has the fuel to fly.

7. What does the weight \(w = w_r/w_d\) mean in the blended cost?

In \(c_e = w_d\,\ell_e + w_r\,r_e\) only the ratio matters, so set \(w_d = 1\): \(w\) is the number of km of extra flying you will accept to cut the exposure \(\sum r\) by one unit. At \(w = 200\) km the planner flies 2 km farther to cut the exposure by 0.01.

8. Why is the exposure edge weight \(-\ln(1-p)\)?

Survival multiplies along a route, \(P_S = \prod(1-p_e)\), but Dijkstra adds. Taking \(-\ln\) turns the product into a sum, \(-\ln P_S = \sum -\ln(1-p_e)\), and because the log is monotone the minimum-sum route is exactly the maximum-\(P_S\) route.

9. Why not just add the raw \(p\)'s along a route?

\(p \approx -\ln(1-p)\) only while \(p\) is small. With one heavy leg against several light ones the raw sum can pick the wrong route: one leg at 0.40 sums lower than two at 0.22 (0.40 against 0.44), yet its survival is 0.600 against 0.608.

10. How does L31's hazard turn a threat into an edge weight?

A site takes a shot every \(\Delta s\) km, each killing with \(p_\text{shot}\), so its hazard is \(\lambda = -\ln(1-p_\text{shot})/\Delta s\) per km. An edge that spends \(\ell_{i,e}\) km inside site \(i\)'s lethal zone (detection range and MEZ both) carries \(r_e = \sum_i \lambda_i \ell_{i,e}\), and the route survives with \(P_S = e^{-\sum r_e}\).

11. What is the Pareto front, and how do you trace it?

Run Dijkstra once for each weight \(w\) in a sweep and plot each route's survival against its length. The front is the set of routes no other route beats on both at once; it shows what each increment of \(P_S\) costs in kilometers.

12. How is a fuel limit applied, and why not inside Dijkstra?

Apply it to the sweep's answers: fly the highest-\(P_S\) route whose length fits under \(L_\text{max}\), or call the mission infeasible if even the shortest route does not fit. A length budget inside Dijkstra would need a second label per node (length used), which breaks its one-label exactness — the hard resource-constrained shortest-path problem.

13. What does an 8-connected grid give you, and what does it cost?

Cell centers become nodes, each linked to 8 neighbors by 10 km legs and \(10\sqrt{2} = 14.1\) km diagonals, so any map becomes a graph. The caveats: headings only every 45°, routes that zig-zag and run up to about 8% long, rings that snap to cells, and many equal-length ties.

14. Why does aspect make the route graph directed?

A leg's heading sets the aspect each radar sees, \(\theta = \phi + 180^\circ - \psi\). Flown toward a radar the leg shows the nose; flown away it shows the tail. The RCS differs, so \(R_\text{det} \propto \sigma^{1/4}\), the lethal length and the risk differ, and one node pair carries two costs — a digraph.

15. What goes wrong if you plan aspect-blind?

With the worst-case \(\sigma\) it is always pessimistic: every ring is at its largest and it pays length to avoid threats it could have slipped past. With the nose-on \(\sigma\) it is optimistic wherever the aircraft is louder than its nose (it flies past radars beam-on) and pessimistic wherever it is quieter. Re-score the route with the real pattern.

16. What does "low cost is not low risk" mean for a planner?

Dijkstra is exact for the cost it is given, and that cost is a model's promise — a \(\sigma\), hazards, rings and a grid. In the demo, a nose-on plan promises \(P_S = 1.000\) through a gap that the aspect-aware model re-scores at 0.077. Re-score every plan under a better model than the one that chose it.