Resolution Limits of Non-Adaptive 20 Questions Search for a Moving Target
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.