← Past problems · 2011 set

2011 · Problem B — Search and Find

Read the official problem page →

The prompt, restated

A searcher must find a lost object in a wooded park at night carrying only a small penlight. Teams are asked: (1) Build a model for the probability of finding the object as a function of search time, light cone geometry, walker pace, and the area of the park. (2) Apply the model to a small dropped item (e.g., car keys ~5 cm) inside a known sub-area of the park. (3) Apply the model to a missing jogger who left for a run at dusk and has not returned — the jogger may be lying injured (a stationary target with a larger silhouette) or may still be moving and disoriented (a target that drifts during the search). (4) Compare a single searcher versus a small volunteer team. (5) Recommend a search pattern and time budget to the park ranger in a one-page note. The grade comes from being explicit about detection physics — illumination falls off with distance, foliage occludes line-of-sight, small targets need closer passes than human-sized ones — and from translating those physics into a defensible probability of success per hour of searching.

Key modeling idea

This is a classical search-theory problem (Koopman, 1956; Stone, 1975). The two foundational quantities are sweep width $W$ — the effective lateral distance over which the searcher would detect the target with certainty — and coverage $C = W L / A$, where $L$ is the searcher's track length and $A$ is the area being swept. Under the standard random-search assumption, $$P_\text{detect}(t) = 1 - \exp\!\left(-\frac{W\, v\, t}{A}\right)$$ where $v$ is walking speed and $t$ is search time. For a structured parallel-track ("ladder") pattern with track spacing $s$, an empirical "exponential detection function" yields $P_\text{detect} \approx 1 - e^{-W/s}$ per sweep, which is much more efficient than random search when $s \lesssim W$. Sweep width itself depends on target size, target contrast, illuminance at the target ($\propto 1/d^2$ from the penlight), and foliage density — fit it from a small calibration experiment or borrow Coast Guard tabulated values and adjust.

Suggested approach

• Step 1 — Model the penlight cone. A small penlight delivers roughly 10–30 lumens with a cone half-angle of 10–15° [illustrative]. Compute illuminance $E(d) = I/d^2$ at target distance $d$; detection threshold for a 5 cm object on leaf litter is roughly 1–5 lux [illustrative]. Solve for effective detection radius $r^*$.
• Step 2 — Estimate sweep width $W$. Use the lateral range curve: $W = \int_{-\infty}^\infty p(y)\,dy$, where $p(y)$ is the probability of detecting a target at lateral offset $y$. For a penlight in woods at night, $W$ is on the order of $1$–$3$ m for keys and $5$–$10$ m for a human-sized target [illustrative] (technique 4 — fitting empirical curves).
• Step 3 — Pick a pattern. Parallel-track sweeps with spacing $s \approx W$ give the best $P_\text{detect}$ per hour. Compute coverage $C = W L / A$ and the per-sweep detection $1 - e^{-W/s}$ for the small-object scenario.
• Step 4 — Simulate the jogger scenario. Place the jogger at a random point with probability weighted by trail proximity (most lost joggers are within ~100 m of the trail [illustrative]). For the "still moving" case, model a 2-D random walk with step size scaled by injury severity (technique 10 — Monte Carlo). Run 10,000 trials per pattern.
• Step 5 — Compare team sizes. $k$ searchers walking parallel tracks multiply effective $L$ by $k$; the detection time to a target probability $p^*$ scales like $-\ln(1-p^*) \cdot A / (k W v)$. Use this to size the volunteer call-out.

Data sources to consider

Common pitfalls

• Treating the park as uniform. The lost-person prior is concentrated near trails, water features, and downhill from the last known point. Uniform priors enormously overstate search time. Use a Bayesian probability map.
• Ignoring the inverse-square illuminance law. A penlight's effective detection radius is set by illuminance, not by raw luminous flux. Doubling lumens only multiplies effective radius by $\sqrt{2}$.
• Confusing sweep width with cone width. Sweep width is an effective quantity averaging detection over offset; it accounts for missed detections near the cone edge and partial occlusion. It is typically smaller than the geometric cone width at the detection-threshold distance.
• No moving-target model. If the jogger is still moving, the "fixed target on a 2-D area" formula understates search time. Model drift explicitly or pay the price in sensitivity analysis.
• Random-search formula misapplied to a planned pattern. Koopman's $1-e^{-Wvt/A}$ assumes random tracks. A well-executed parallel-track sweep is substantially more efficient — use the per-sweep exponential model instead.
• No fatigue / cognitive-load adjustment. Empirical SAR studies show detection probability drops ~30% after two hours of nighttime searching [illustrative]. Tag the time budget with a fatigue caveat.

Python sketch

Monte Carlo of parallel-track penlight search; small-object and lost-jogger scenarios.

import numpy as np

rng = np.random.default_rng(0)

# --- Search parameters [illustrative] ---
A_sub   = 200.0 * 200.0     # 4 ha sub-area for the small object (m^2)
A_park  = 1_000.0 * 1_000.0 # 1 km^2 park for the jogger
v       = 0.8               # searcher speed at night (m/s) -- slow!
W_key   = 1.5               # sweep width for keys (m)
W_human = 8.0               # sweep width for a human (m)

def sweep_detect(W, s, n_sweeps):
    """Per-sweep detection prob, accumulated over n parallel sweeps spaced s."""
    return 1.0 - (1.0 - (1.0 - np.exp(-W/s)))**n_sweeps

# --- Scenario 1: small object, 4-ha sub-area, parallel tracks spaced s = W ---
s = W_key
L_per_sweep = np.sqrt(A_sub)         # track length per sweep
n_sweeps    = int(np.sqrt(A_sub) / s)
t_total     = n_sweeps * L_per_sweep / v / 60   # minutes
p_detect    = sweep_detect(W_key, s, n_sweeps)
print(f"Keys: {n_sweeps} sweeps, ~{t_total:.0f} min, P(detect) = {p_detect:.2f}")

# --- Scenario 2: lost jogger, Bayesian prior weighted toward trail ---
N = 10_000
# 70% within 100 m of trail (modeled as a horizontal line y=500), 30% uniform
on_trail   = rng.random(N) < 0.7
x_jogger   = rng.uniform(0, 1000, N)
y_jogger   = np.where(on_trail,
                      500 + rng.normal(0, 50, N),         # near trail
                      rng.uniform(0, 1000, N))            # uniform fallback
# Searcher pattern: parallel tracks every s = W_human across full park
s = W_human
track_ys = np.arange(s/2, 1000, s)
# probability of detection per jogger = 1 - product over tracks of (miss)
miss = np.ones(N)
for ty in track_ys:
    p_hit_per_track = np.exp(-((y_jogger-ty)**2) / (2*(W_human/2)**2))
    miss *= (1 - 0.9*p_hit_per_track)   # 0.9 = detection ceiling per close pass
p_detect_jogger = 1 - miss.mean()
L_total = len(track_ys) * 1000           # m walked
t_total = L_total / v / 3600
print(f"Jogger: {len(track_ys)} tracks, ~{t_total:.1f} h, P(detect) = {p_detect_jogger:.2f}")

# --- Scenario 3: k volunteers in parallel ---
for k in (1, 3, 6):
    t_k = t_total / k
    print(f"k={k} searchers: ~{t_k:.2f} h to same coverage")

Sensitivity & validation checklist

• Vary $W$ by $\pm 50\%$ — the dominant uncertainty in any search-theory model is sweep width, not pattern. Report $P_\text{detect}$ versus $W$ as the headline chart.
• Sweep track spacing $s$ from $W/2$ to $2W$; $s \approx W$ should be near-optimal. If your simulation says otherwise, debug the detection function.
• Compare the random-search formula $1-e^{-Wvt/A}$ against the parallel-track simulation; the gap quantifies the value of planning over wandering.
• Stress the jogger prior: move 30% of probability mass off-trail and re-solve — does the recommended pattern change from "trail-following" to "area sweep"?
• Add a 30% fatigue penalty to $W$ for the second hour and re-rank patterns; this often promotes shorter, faster sweeps over thorough slow ones.
• Validate against Coast Guard tabulated sweep widths for visual ground search at night with a flashlight: your fitted $W$ for a human target should land in the 4–10 m band [illustrative].

Related pages

• Techniques — Monte Carlo simulation
• Techniques — Fitting empirical curves
• Techniques — Optimal search allocation
• Anatomy of a winning paper