Search and rescue: detection, coverage and the best use of effort

Datums and probability maps

Figure 3-1. A point datum is a circular normal distribution of possible positions. The probability that the object is within R standard deviations of the datum is POC = 1 - exp(-R^2 / 2).

srchfig("3-1")

Figures 3-2, 3-3 and 3-5. The square circumscribed about a circle of radius R holds (2 Phi(R) - 1)^2 of the distribution: 47% for one standard deviation, 58% for the total probable error of position E = sqrt(2 ln 2) = 1.1774 standard deviations (the radius holding 50%), and 65% for the simplified method’s first search radius of 1.1 E.

srchfig("3-2")

srchfig("3-3")

srchfig("3-5")

Figure 3-4. A probability map lays a grid over the distribution. With cells 2E wide the centre holds 57.91%, a side cell 9.08% and a corner 1.42%.

srchfig("3-4")

Figures 3-6 and 3-7. The simplified method extended a point datum to a line by drawing circles at the two end points and boxing them in. The density this implies is drawn as a circular normal spread along the segment (datum = "line"), an approximation of the book’s plate.

srchfig("3-6")

srchfig("3-7")

Figures 3-8 to 3-10. A simpler line datum is normal across the line and uniform along it, with nothing beyond its ends (datum = "corridor"). A strip one standard deviation either side holds 68%, a strip of 2E holds 76.1%, and dividing strips into cells along the line gives the completed map of figure 3-10.

srchfig("3-8")

srchfig("3-9")

srchfig("3-10")

Figures 3-11 and 3-12. An area datum spreads the probability evenly: each of 20 equal cells holds 5%.

srchfig("3-11")

srchfig("3-12")

Figures 3-13 and 3-14. A generalized datum takes the planner’s own cell probabilities (datum = "general", wts =). The book’s surface is illustrative; here it is drawn from the cells of figure 3-14.

srchfig("3-13")

srchfig("3-14")

Lateral range curves and sweep width

Figure 4-1. A lateral range curve p(x) is the probability of detecting an object that passes at distance x from the track. The sweep width is its area, W = integral of p(x) dx; the dashed rectangles have the same area.

srchfig("4-1")

Figures 4-2 and 4-3. A definite range sensor sees everything within W / 2 of its track and nothing beyond: it sweeps a strip exactly W wide.

srchfig("4-2")

srchfig("4-3")

Figures 4-4 and 4-5. The M-Beta curve has height M over a width of W / M; with M = 0.5 and M = 0.25 the sweep width is unchanged.

srchfig("4-4")

srchfig("4-5")

Figures 4-6 and 4-7. Koopman’s inverse cube law takes the chance of a glimpse to be proportional to the solid angle of the wake, k h / r^3, which gives p(x) = 1 - exp(-W^2 / (4 pi x^2)). Its sweep width is W: the objects missed inside the sweep width (A) balance those seen outside it (B).

srchfig("4-6")

srchfig("4-7")

swpwdth(ltrlrng(seq(-500, 500, by = 0.01), W = 1))
#> [1] 0.9996817

Effort, coverage and probability of detection

Figure 5-1. Search effort is sweep width times track length, Z = W L, and coverage is effort over area, C = Z / A. A search whose path is random gives POD = 1 - exp(-C).

srchfig("5-1")

Figures 5-2 to 5-5. A parallel sweep at track spacing S has coverage C = W / S. With a definite range sensor the POD is min(C, 1): half the gap is seen at S = 2W, all of it at S = W.

srchfig("5-2")

srchfig("5-3")

srchfig("5-4")

srchfig("5-5")

Figures 5-6 and 5-7. M-Beta curves overlap once the tracks are closer than their width: POD = C below C = M and 1 - (1 - M)^(C / M) above it, 0.75 and 0.6836 at coverage 1 for M = 0.5 and M = 0.25, nearer the random search curve as M falls.

srchfig("5-6")

srchfig("5-7")

srchpod(c(0.5, 1, 2), "mbeta", m = 0.25)
#> ── Probability of detection ────────────────────────────────────── 
#>   M-Beta model, M = 0.25
#> 
#>  coverage      pod
#>       0.5 0.437500
#>       1.0 0.683594
#>       2.0 0.899887
#> ──────────────────────────────────────────────────────────────────

Figure 5-8. The inverse cube parallel sweep gives POD = erf(sqrt(pi) C / 2), 0.7899 at coverage 1, between the definite range and random search curves. pswppod() computes the same sweep directly, for any curve.

srchfig("5-8")

pswppod(W = 1, S = 1)
#> [1] 0.7899086

Figure 5-9. Poorer conditions shrink the sweep width, and a cross-track navigation error of standard deviation sigma flattens the curve: the expected curve is the convolution phi(x) = integral of p(x - t) Z(t, sigma) dt, whose area is still W (ltrlrng(..., navsd = )). The plate is blank in the published file; it is drawn from the text.

srchfig("5-9")

Optimal search

Figures 6-1 and 6-2. With half the probability in a 3 by 3 square inside a 5 by 5 one and effort for half the area, the trial squares of the whole area, half of it and a third of it hold 100%, 60.94% and 46.30%; at coverage 1 the middle trial succeeds most often.

srchfig("6-1")

srchfig("6-2")

Figures 6-3 and 6-4. For a point datum, optsqr() finds the square that an effort, spread evenly, should cover: the search factor is its half side in units of E. An effort of 4 E^2 gives a factor of 1.02, coverage 0.96 and POS 0.4578, as the book’s program found.

optsqr(4)
#>   search effort releff cumeff   factor     side       poc  coverage       pod
#> 1      1      4      4      4 1.021043 2.042086 0.5939919 0.9592059 0.7707087
#>         pos    cumpos
#> 1 0.4577947 0.4577947
srchfig("6-3")

srchfig("6-4")

Figure 6-5. By the additive principle, a series of searches each optimal for what the earlier ones left does as well as one optimal search with all the effort: the cumulative probability of success depends on the cumulative effort.

srchfig("6-5")

Figure 6-6. Searching in a series with random efforts between 0.1 and 50 E^2, the optimal factors cluster around the curve, except where a much smaller effort follows a large one and the best use of it is the remaining central peak.

srchfig("6-6")

Your own search

The figures use the book’s numbers; every function takes yours, and each result has a plot() method. srchfig() lists, for each of the 36 figures, the one line that draws it from your own numbers (replace the example inputs; a schematic gives the computation it pictures):

# an HTML table with each line in <code>: in a Markdown table a `$` starts a formula and a `|`
# ends the cell, so both are written as entities
tab <- srchfig()[, c("fig", "caption", "yours")]
esc <- function(x) {
  for (r in list(c("&", "&amp;"), c("<", "&lt;"), c(">", "&gt;"), c("$", "&#36;"), c("|", "&#124;"))) {
    x <- gsub(r[1], r[2], x, fixed = TRUE)
  }
  x
}
tab$caption <- esc(tab$caption)
tab$yours <- sprintf("<code>%s</code>", esc(tab$yours))
knitr::kable(tab, format = "html", escape = FALSE, row.names = FALSE,
             col.names = c("Figure", "Caption", "From your own numbers"))

The most used of them, step by step. Say a sensor’s sweep width is 0.8 nautical miles and its detection falls off as the inverse cube of the lateral range. Its lateral range curve, and the picture of what the sweep width means (the objects missed inside it equal those seen outside it, Figure 4-7):

lr <- ltrlrng(seq(-3, 3, by = 0.05), W = 0.8)
plot(lr)

plot(lr, equiv = TRUE)

A sweep width can also come from a field trial: the share of objects detected at each lateral range, measured on both sides of the track. swpwdth() integrates the curve.

d <- c(-3, -2, -1.5, -1, -0.5, -0.25, 0, 0.25, 0.5, 1, 1.5, 2, 3)
p <- c(0.01, 0.08, 0.2, 0.45, 0.75, 0.9, 0.95, 0.9, 0.75, 0.45, 0.2, 0.08, 0.01)
swpwdth(d, p)
#> [1] 2.03

The probability of detection for the coverage a plan gives (coverage is sweep width times track length over the area), and for parallel sweeps at a track spacing of 1 with a navigation error of 0.1:

pd <- srchpod(seq(0, 3, by = 0.1), model = "invcube")
plot(pd)

pswppod(W = 0.8, S = 1, navsd = 0.1)
#> [1] 0.6806056

After a search of three areas that found nothing, the chance the object is in each area is updated by what each search could have detected:

srchscs(poc = c(0.5, 0.3, 0.2), pod = c(0.8, 0.5, 0))
#> ── Probability of success ──────────────────────────────────────── 
#>   POS 0.55 after 1 search
#> 
#>  area poc cumpod posarea pocupd
#>     1 0.5    0.8    0.40 0.2222
#>     2 0.3    0.5    0.15 0.3333
#>     3 0.2    0.0    0.00 0.4444
#> ──────────────────────────────────────────────────────────────────

Planning a search, start to finish

The same steps plan a real search. A hiker is overdue; the last known position is 2 km east and 3 km north of the base, and with the time and terrain since then the position could be off by about 1.5 km (one standard deviation). Lay a grid over the area, in kilometres, and put the probability of where the hiker may be on it:

xe <- seq(-4, 8, by = 0.5)
ye <- seq(-3, 9, by = 0.5)
m <- datumpmap(xe, ye, center = c(2, 3), sigma = 1.5)
plot(m)

The ground teams’ sweep width is 0.6 km (from a published table for the terrain and object, or from a trial of your own as above), and they can walk 40 km of track today. opteffort() spreads those 40 km over the cells to make the chance of finding the hiker as large as possible:

day1 <- opteffort(m, W = 0.6, effort = 40)
day1$pos
#> [1] 0.5471492
plot(day1)

day1$effort is the track length to walk in each cell, and day1$pod the chance of detection there. If the day ends without a find, each cell’s probability is updated by what was searched (cells searched hard become less likely, the rest more likely), and the next day is planned on the updated map:

upd <- srchscs(as.vector(m$poc), as.vector(day1$pod))
poc2 <- matrix(upd$pocupd, nrow = nrow(m$poc))
day2 <- opteffort(poc2, area = rep(0.25, length(poc2)), W = 0.6, effort = 40)
day2$pos
#> [1] 0.4068465

On a grid of your own

The same functions take any grid and datum. opteffort() spreads a total track length over the cells to make the probability of success as large as possible (Stone 1975), and srchscs() updates the containment after a search that finds nothing.

m <- datumpmap(seq(-6, 6, by = 0.5), seq(-6, 6, by = 0.5), sigma = 2)
a <- opteffort(m, W = 1, effort = 30)
a$pos
#> [1] 0.455821
optcrcsrch(sigma = 2, W = 1, effort = 30)$pos
#> [1] 0.4571532
plot(a)

srchscs(c(0.5, 0.3, 0.2), c(0.8, 0.5, 0))
#> ── Probability of success ──────────────────────────────────────── 
#>   POS 0.55 after 1 search
#> 
#>  area poc cumpod posarea pocupd
#>     1 0.5    0.8    0.40 0.2222
#>     2 0.3    0.5    0.15 0.3333
#>     3 0.2    0.0    0.00 0.4444
#> ──────────────────────────────────────────────────────────────────

References

Frost, J. R. (1996). The Theory of Search: A Simplified Explanation. Soza and Company and U.S. Coast Guard Office of Search and Rescue. Chapters 3-6 and their figures.

Koopman, B. O. (1946). Search and Screening. OEG Report 56, Office of the Chief of Naval Operations.

Koopman, B. O. (1956-1957). The theory of search, parts I-III. Operations Research 4(3), 324-346; 4(5), 503-531; 5(5), 613-626.

Stone, L. D. (1975). Theory of Optimal Search. Academic Press.