提出可保证搜索质量的算法，加速搜救路径规划。
$\rm{A}^{\rm{SAR}}$: $\varepsilon$-Optimal Graph Search for Minimum Expected-Detection-Time Paths with Path Budget Constraints for Search and Rescue (SAR)
- 基于启发式剪枝和图搜索，约束搜索空间。
- 在150秒内找到漂浮假人，优于现有方法。
- 适合对可靠性要求高的实时搜救任务。
搜救（SAR）中常面临信息不确定、观测不完整及搜索区域广阔等挑战。在海上搜救等场景中，受困者存活时间短，优化搜索路径能显著提升成功率。传统随机优化方法虽能处理大规模问题，但无法在有限时间内提供解的质量保证。本文提出 $ m{A}^{ m{SAR}}$ 算法，一种 $oldsymbol{ ext{ε}}$-最优的搜救路径规划方法。该算法通过启发式方法界定搜索空间，并利用图搜索技术，确保所求解在用户指定的误差因子 $oldsymbol{ ext{ε}}$ 范围内接近最优。在实际操作模拟中，$ m{A}^{ m{SAR}}$ 比现有优化方法更快找到更优解。此外，在加拿大安大略湖的真实野外试验中，成功于150秒内定位一个漂流假人，验证了其高效性与实用性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。