论文标题
非自适应的分辨率限制20个问题搜索移动目标
Resolution Limits of Non-Adaptive 20 Questions Search for a Moving Target
论文作者
论文摘要
使用具有与查询依赖性噪声的20个问题估计框架，我们研究了在单位立方体上移动目标的非自适应搜索策略，其初始位置和在分段恒定速度模型下的初始位置和速度未知。在这个搜索问题中，有一个甲骨文在任何时候都知道目标的瞬时位置。我们的任务是尽可能少数时间查询甲骨文，以在任何指定的时间准确估算目标的位置。我们首先研究了Oracle对每个查询的答案被离散噪声损坏，然后将我们的结果推广到添加剂白色高斯噪声的情况。在我们的公式中，性能标准是分辨率，该分辨率定义为真实位置和估计位置之间的最大$ l_ \ infty $距离。我们通过推导非肌电和渐近性界限来表征最佳的非自适应查询程序的最低分辨率，并具有有限数量的查询。当查询数量满足一定条件时，我们的边界在第一阶渐近含义上是紧密的，并且当目标以恒定速度移动时，我们的边界在更强的二阶渐近含义中紧密。为了证明我们的结果，我们将当前的问题与渠道编码联系起来，从有限的区块长度信息理论借用想法，并根据可能的量化目标轨迹的数量构建界限。
Using the 20 questions estimation framework with query-dependent noise, we study non-adaptive search strategies for a moving target over the unit cube with unknown initial location and velocities under a piecewise constant velocity model. In this search problem, there is an oracle who knows the instantaneous location of the target at any time. Our task is to query the oracle as few times as possible to accurately estimate the location of the target at any specified time. We first study the case where the oracle's answer to each query is corrupted by discrete noise and then generalize our results to the case of additive white Gaussian noise. In our formulation, the performance criterion is the resolution, which is defined as the maximal $L_\infty$ distance between the true locations and estimated locations. We characterize the minimal resolution of an optimal non-adaptive query procedure with a finite number of queries by deriving non-asymptotic and asymptotic bounds. Our bounds are tight in the first-order asymptotic sense when the number of queries satisfies a certain condition and our bounds are tight in the stronger second-order asymptotic sense when the target moves with a constant velocity. To prove our results, we relate the current problem to channel coding, borrow ideas from finite blocklength information theory and construct bounds on the number of possible quantized target trajectories.
