ASAR: ε-Optimal Graph Search for Minimum Expected-Detection-Time Paths with Path Budget Constraints for Search and Rescue (SAR)
Eric Mugford, Jonathan Gammell
AI summary
Problem
Search and rescue path planning is computationally complex and probabilistic, yet existing stochastic optimization methods lack formal guarantees on solution quality within finite time and budgets.
Approach
ASAR adapts A* graph search with a custom admissible heuristic and an inflation factor to efficiently explore the search space, guaranteeing that the computed path is within a user-defined factor of the optimal minimum expected detection time.
Key results
- Formally guarantees ε-optimal solutions for minimum expected detection time under path budget constraints
- Outperforms leading stochastic optimization methods and traditional search patterns in operational simulations
- Successfully validated in a real-world Lake Ontario field trial, locating a drifting manikin in 150 seconds
- Handles moving targets and imperfect sensors without requiring unrealistic assumptions
Why it matters
Provides SAR operators and UAV planners with a reliable, provably near-optimal planning tool to maximize survival rates in time-critical maritime and land searches.
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 ASAR, an ε-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, ε, 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.