基于多臂老虎机的路径约束移动传感器自适应搜索
Adaptive search with path-constrained mobile sensors using multi-arm bandits
Abraham P. Vinod, Parth K. Thaker, Gautam Dasarathy, Stefano Di Cairano
AI 速览：将能量受限移动传感器团队的主动路径选择建模为多臂老虎机问题，提出带置信界与路径覆盖构造的自适应搜索算法，并给出有限时间与任意时间概率正确性保证及匹配下界的检测时间上界。
We study a constrained sequential decision problem for detecting regions of interest from noisy online measurements collected by a team of energy-constrained mobile sensors. The sensor motion is restricted to a precomputed set of feasible paths that satisfy mobility constraints, limited available energy by requiring return to charging stations, and avoidance of known obstacles. We cast the resulting active path selection as a multi-armed bandit problem and propose an iterative search algorithm that adaptively assigns paths using confidence bounds computed from the collected data. We also propose a graph-based method to construct low-cardinality path covers under the team's constraints. We establish finite-time and anytime probabilistic correctness guarantees for the proposed algorithm, derive non-asymptotic upper bounds on the times required to detect all regions of interest and to label all nodes, and show that these bounds match algorithm-independent lower bounds up to constant factors for a broad class of problem instances. Using numerical simulations, we illustrate the behavior of the proposed approach and the effect of path redundancy and team size on search performance.