优化机器人在有限时间内搜寻目标的路径，提升发现概率。
Provable Methods for Searching with an Imperfect Sensor
- 设计带时间约束的搜索路径算法，考虑移动与探测耗时。
- 在非均匀移动时间下，实现可证明的最优探测概率保障。
- 适用于搜救等实际场景，算法高效且性能可验证。
假设目标位于平面上有限个位置中的某一处，但具体位置未知。我们使用一台具有不完美感知能力的移动机器人进行搜索，移动和探测每个位置均需耗时，且总时间受限。本文研究如何计算使目标被发现概率最大的搜索路径或策略。考虑到点间移动时间不均（如基于距离）对搜救应用至关重要，但此类问题因复杂性研究有限。本文提出具有性能保证的快速算法及其变体，给出复杂性分析，并通过实验验证其效果。
原文摘要 · Abstract (English)
Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e.g., based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to observe their performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。