  This paper considers the problem of acquiring an unknown target location
(among a finite number of locations) via a sequence of measurements, where each
measurement consists of simultaneously probing a group of locations. The
resulting observation consists of a sum of an indicator of the target's
presence in the probed region, and a zero mean Gaussian noise term whose
variance is a function of the measurement vector. An equivalence between the
target acquisition problem and channel coding over a binary input additive
white Gaussian noise (BAWGN) channel with state and feedback is established.
Utilizing this information theoretic perspective, a two-stage adaptive target
search strategy based on the sorted Posterior Matching channel coding strategy
is proposed. Furthermore, using information theoretic converses, the
fundamental limits on the target acquisition rate for adaptive and non-adaptive
strategies are characterized. As a corollary to the non-asymptotic upper bound
of the expected number of measurements under the proposed two-stage strategy,
and to non-asymptotic lower bound of the expected number of measurements for
optimal non-adaptive search strategy, a lower bound on the adaptivity gain is
obtained. The adaptivity gain is further investigated in different asymptotic
regimes of interest.
