$\rm{A}^{\rm{SAR}}$: $\varepsilon$-Optimal Graph Search for Minimum Expected-Detection-Time Paths with Path Budget Constraints for Search and Rescue (SAR)

AI summary

Overview

• Research area: Robotics / autonomous search planning, specifically optimal path planning for maritime Search and Rescue (SAR) using graph-search methods.
• Technical level: Intermediate. Readers need basic familiarity with A* search, graph representations, and probability belief states, but the paper explains its formulation step by step.
• Scope: The paper presents A^SAR, an A*-style, ε-optimal graph-search algorithm that computes minimum expected-detection-time searcher paths under a path budget in dynamic environments, validated on four OpenDrift maritime scenarios and one real-world Lake Ontario field trial.

What This Paper Is About

SAR planners must find missing persons or objects despite uncertain location information, imperfect sensors, and large search areas. Existing stochastic optimization methods (such as ant colony optimization and cross-entropy optimization) can tackle large problems but offer no formal guarantee on solution quality in finite time. This paper formulates the path-budget-constrained minimum time to detection (MTTD) problem as a graph search and solves it with a heuristic that is guaranteed to return a solution within a user-specified factor, ε, of the optimal path.

Key Contributions

1. An ε-optimal graph-search algorithm (A^SAR) based on A* that minimizes the finite-path-budget MTTD objective under a path budget, an initial position, a prior target probability distribution, target-motion model, and sensor model — without assuming a stationary target or a perfect sensor.
2. A new admissible heuristic for an order- and time-variant problem, computed by solving a relaxed problem in which the searcher may search any vertex reachable within the remaining steps without path continuity, greedily choosing the vertex maximizing the reduction in probability mass at each time step. The authors prove admissibility (Theorem 1) and note this extends a heuristic in prior work (Schlotfeldt et al. [29]) beyond order-invariant objectives and time-invariant environments.
3. A user-controlled optimality guarantee, achieved by weighting the heuristic with an inflation factor ε ≥ 1, as in Weighted A*, so the returned path is guaranteed to be within ε of the optimum while reducing vertex expansions.
4. Empirical and field validation: comparison against a max-min ant colony optimization (ACO) planner from Perez-Carabaza et al. [4] and certified parallel-track searches across four OpenDrift-generated maritime scenarios, plus a real-world fixed-wing UAV field trial on Lake Ontario, Canada.

Main Findings

• Better solutions than ACO and parallel track at ε = 1.0: The ε = 1.0 configuration achieved truncated MTTD objective values that were 3.18% lower on average than the median solutions produced by ACO, and 39% lower on average than the parallel-track searches.
• Near-optimal results even when weighted: The weighted setting ε = 1.1 produced a solution less than 101.5% of the optimal truncated MTTD objective on average, and outperformed the median ACO solution in all experiments.
• Parallel-track baselines were far from optimal: Figure 3 labels report parallel track at 134% (Bay of Fundy), 153% (Lake Ontario), 152% (Salish Sea), and 118% (Arctic Ocean).
• Fast run times: A^SAR found paths within 1.15% of optimum on average within 0.1 seconds. Wall-clock times ranged from 0.05 s (Salish Sea, ε = 1.1) to 35.26 s (Arctic Ocean, ε = 1.0); Lake Ontario ranged from 0.09 s to 0.86 s, Bay of Fundy from 0.10 s to 19.73 s, and Salish Sea from 0.05 s to 2.24 s across ε values from 1.1 down to 1.0.
• Deterministic behaviour: A^SAR is deterministic and returns one result for any given problem and suboptimality factor ε, with solution quality increasing as ε decreases — unlike the stochastic ACO method, which was measured in ant generations over 100 trials with nonparametric 99% confidence intervals.
• Comparable computational demand: The authors note that the experimental section of [4] runs ACO for 50 s before convergence on problems with significantly shorter path budgets, and that ants per generation scale with path budget.
• Real-world validation: In the Lake Ontario field trial, a fixed-wing UAV located a drifting manikin in 150 seconds, within 20% of the detection time forecast by the planner despite localization uncertainty.
• Qualitative path behaviour: A^SAR outperformed parallel track and ACO by prioritizing areas of high probability first and avoiding unnecessary revisits to recently explored vertices when moving toward other high-probability regions.

Methodology in Plain English

The search area is represented as a graph where vertices are cells and bidirectional edges connect spatially adjacent cells; the experiments use 4-connected motion, reflecting a fixed-wing UAV whose cell width equals the camera sweep width and for which diagonal motion would leave parts of a cell unobserved. The target location is a probability distribution over vertices, and each state in the search couples the searcher's position, the partial path taken, and a stored belief array that tracks the probability the target is present and undetected.

Belief evolves in two ways: a motion model moves probability between vertices over time (for example, ocean drift), and searching a vertex reduces its belief by the glimpse probability q(v), assumed i.i.d. with no false-positive detections. The objective is the truncated MTTD, J(σ) = sum over time steps up to the budget T of the total remaining belief mass, a non-Markovian objective because the remaining cost depends on the partial path taken.

A^SAR orders its priority queue by f(x) = g(x) + ε·ĥ(x), where g(x) is the objective accrued so far and ĥ(x) is the admissible heuristic of the objective remaining. It has no fixed goal: a goal is any vertex whose path uses exactly the budget T. The algorithm ends when a goal vertex is removed from the queue, and it prunes successors whose f-value cannot improve the best solution found so far, saving memory. The heuristic is calculated by relaxing path continuity and greedily searching the reachable vertex with the highest q(v)·b[v] at each remaining time step, which is proven to never overestimate the true remaining objective.

Experiments used OpenDrift, an open-source ocean drift framework, with its Leeway model derived from the US Coast Guard's SAR model, combining empirical object coefficients with environmental data to produce particle trajectory ensembles. Particles define the belief state, each carrying a probability of not detected (PND) that is reduced by the glimpse probability when the searcher path crosses its cell; cell belief is the sum of its particles' PNDs. Four scenarios were built across the Bay of Fundy, Lake Ontario, the Salish Sea, and Hudson's Bay (Arctic Ocean), using four search objects: a person in water in an unknown state (PIW-1), a conscious person in water positioned vertically and wearing a PFD (PIW-2), a fishing vessel, and a deep-ballast life raft with unknown capacity and loading. The glimpse probability was 0.78 for all vertices in all experiments, and the searcher parameters matched fixed-wing aircraft at 300 ft travelling at 20 m/s. A^SAR was implemented in C++ and run on a 3.2 GHz M1 Pro processor.

Why This Matters

The paper addresses a problem the authors note is NP-complete when minimizing MTTD, and it is the first approach described here that optimizes MTTD directly while offering a formal bound on solution quality. Because survival probability decreases with time, especially in cold or maritime environments, reducing expected detection time can directly increase the likelihood that a missing person survives. The work also matters because UAVs are cheaper and faster to launch than manned aircraft, and their manoeuvrability makes complex, scenario-optimized search patterns feasible rather than the simple parallel-track patterns flown by crewed platforms.

Real-world applications:

• Maritime SAR for persons in water: the four scenarios model PIW-1 and PIW-2 objects with realistic wind and current models across the Bay of Fundy, Lake Ontario, the Salish Sea, and the Arctic Ocean.
• Search for missing vessels and life rafts: the fishing vessel and deep-ballast life raft scenarios represent drifting-object searches for larger targets.
• UAV-based aerial search: the field trial used a fixed-wing UAV with downward-facing RGB and infrared cameras and a 0.1 Nm sweep width to locate a drifting manikin.
• Drift-informed planning: the use of OpenDrift, Leeway coefficients, and regional current models (GoMOFS, LOOFS, CIOPS Salish Sea, ESPC-D-V02) means the planner consumes the same drift-model products SAR professionals already use.

Industry relevance: SAR agencies, coast guards, and UAV operators gain a planning tool with a tunable speed-versus-optimality dial (ε), deterministic results that are easy to certify, and sub-second run times in most tested configurations — properties that matter for operational time pressure and for the formal justification of search decisions.

Future Directions

• Anytime planning and replanning: the authors list this as future work, which would let the planner update paths as new information arrives during a search.
• Multi-agent coordination: extending A^SAR from a single searcher to coordinated teams of searchers is named as a future direction.
• Searcher kinematic constraints: incorporating the motion limits of the searching vehicle into the plan is listed as future work; the current experiments use 4-connected motion as a simplified reflection of fixed-wing constraints.
• Open questions raised by the results: how A^SAR behaves with uncertain or time-varying sensor models beyond a fixed glimpse probability (the authors state any sensor model could be used, but only q(v) = 0.78 is tested), and how the reported 20% gap between forecast and actual detection time in the field trial would behave across other real-world targets and conditions.

Target Audience

This paper is most useful to robotics and path-planning researchers working on probabilistic search and informative path planning, and to SAR practitioners and UAV operators who plan searches at sea. It also suits graduate students studying graph search, heuristic admissibility, and ε-optimal algorithms, and researchers comparing deterministic graph-search guarantees against stochastic optimization methods such as ACO, cross-entropy optimization, and Bayesian optimization.

Authors’ abstract

Searches are conducted to find missing persons and/or objects given uncertain information, imperfect observers and large search areas in Search and Rescue (SAR). In many scenarios, such as Maritime SAR, expected survival times are short and optimal search could increase the likelihood of success. This optimization problem is complex for nontrivial problems given its probabilistic nature. Stochastic optimization methods search large problems by nondeterministically sampling the space to reduce the effective size of the problem. This has been used in SAR planning to search otherwise intractably large problems but the stochastic nature provides no formal guarantees on the quality of solutions found in finite time. This paper instead presents $\rm{A}^{\rm{SAR}}$, an $\varepsilon$-optimal search algorithm for SAR planning. It calculates a heuristic to bound the search space and uses graph-search methods to find solutions that are formally guaranteed to be within a user-specified factor, $\varepsilon$, of the optimal solution. It finds better solutions faster than existing optimization approaches in operational simulations. It is also demonstrated with a real-world field trial on Lake Ontario, Canada, where it was used to locate a drifting manikin in only 150s.