{'fraction_non_alphanumeric': 0.051027513435340746, 'fraction_numerical': 0.013908478994447322, 'mean_word_length': 4.286954880120823, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Resource-Constrained Adaptive Search and Tracking for Sparse Dynamic Targets

This paper considers the problem of resource-constrained and noise-limited localization and estimation of dynamic targets that are sparsely distributed over a large area. We generalize an existing framework [Bashan et al, 2008] for adaptive allocation of sensing resources to the dynamic case, accounting for time-varying target behavior such as transitions to neighboring cells and varying amplitudes over a potentially long time horizon. The proposed adaptive sensing policy is driven by minimization of a modified version of the previously introduced ARAP objective function, which is a surrogate function for mean squared error within locations containing targets. We provide theoretical upper bounds on the performance of adaptive sensing policies by analyzing solutions with oracle knowledge of target locations, gaining insight into the effect of target motion and amplitude variation as well as sparsity. Exact minimization of the multi-stage objective function is infeasible, but myopic optimization yields a closed-form solution. We propose a simple non-myopic extension, the Dynamic Adaptive Resource Allocation Policy (D-ARAP), that allocates a fraction of resources for exploring all locations rather than solely exploiting the current belief state. Our numerical studies indicate that D-ARAP has the following advantages: (a) it is more robust than the myopic policy to noise, missing data, and model mismatch; (b) it performs comparably to well-known approximate dynamic programming solutions but at significantly lower computational complexity; and (c) it improves greatly upon non-adaptive uniform resource allocation in terms of estimation error and probability of detection.

at significantly lower computational complexity; and (c) it improves greatly upon non-adaptive uniform resource allocation in terms of estimation error and probability of detection.

I. INTRODUCTION
Systems for wide area surveillance such as the Gotcha synthetic aperture radar and the Angel Fire electro-optical sensor currently offer near real-time imaging and surveillance of city-sized scenes. Generally, these systems perform continuous collection of data, followed by forensic analysis to detect and track targets within the scene. The amount of raw data collected by these systems is often very large, often collected uniformly over a large area, even though the interesting features (e.g. moving targets, etc.) exist only in a few locations. Due to such data collection inefficiencies, there is a high likelihood that much sensing and/or computational resources may be wasted by searching areas where targets are not located. Abidi et al [1] provides a comprehensive survey of recent work in wide-area surveillance, including topics in coverage analysis, optimal sensor positioning and sensor fusion. They stress the need for intelligent data collection and system analysis in order to deal with such data collection inefficiencies.
An alternative is adaptive sampling, for which past observations are used to inform the collection of future observations, with the goal of focusing effort onto the "interesting" regions of the search space. Adaptive sampling can be an important tool for efficiently managing the collection inefficiency problem faced by wide-area surveillance systems. Previous work has shown that, when constrained to use equal resources, adaptive sampling can significantly improve target localization performance [2]- [11] in comparison to a uniform policy that uses equal sensing effort across the scene. Benefits of adaptive sensing include: gains in estimation precision [4], [5]; provable detection of the targets often at faster convergence rates [7], [10]; and improved robustness in detection performance as measured by the minimum detectable amplitudes [8].
Bashan et al [4] provided an optimal two-stage policy called ARAP for adaptively localizing targets and estimating their amplitudes in noise under effort budget constraints. A multiscale approach was subsequently introduced in order to further reduce the total number of measurements [5]. Hitchings and Castanon [6] provided an online modification to [4] through Lagrangian constraint relaxation. Additionally, [9] extended the two-stage policy to an arbitrary number of stages using approximate dynamic programming, and generalized the framework to allow for a variety of measurement/estimation loss models. Using a similar model called Distilled Sensing, [7], [8] specified a methodology for locating targets in noise at much lower signal-to-noise ratios (SNR) than non-adaptive methods. Malloy et al [10] extends Distilled Sensing to non-Gaussian models, while [8], [11] consider compressive measurements.
In the above methods, it is assumed that the targets of interest remain stationary across sensing/observation epochs. In wide-area surveillance, however, many targets exhibit complex dynamic behavior such as movement, entering/leaving the scene, and obscuration. Krishnamurthy [12] considers the problem of selecting the direction to point an agile sensor in order to track P moving targets among a finite number of cells. When the state is fully observable, the problem can be posed as a Markov decision process (MDP). Krishnamurthy formulates the problem as a hidden Markov model (HMM) tracking problem in the more challenging case where the state is observed with noise. He discusses an optimal policy which depends on the individual target's belief state -the conditional density of the state given the observation history. Moreover, a suboptimal approach to approximating the optimal selection criterion is provided to combat the prohibitive computational complexity of the optimal solution.
Chong et al. [13] show that many adaptive sensing problems can be formulated as partially observable Markov decision processes (POMDPs). This general framework is concerned with selecting actions to maximize the sum of an immediate reward and an expected future reward, given a system with Markovian evolution but only partially observable state (e.g. due to noise). Unfortunately, the expected future reward is often difficult to compute, while the tractability of the optimal solution is further impaired when the state space and action space are large. Chong et al. [13] propose approximate methods that include parametric approximations, reinforcement learning techniques, and rollout policies. The last of these assumes that a base policy is available that may not be optimal but is simple to compute. Rollout policies then ensure policy improvement, i.e., they are guaranteed to do at least as well as the base policy. However, rollout policies still remain impractical in cases where the action space is large.
In this paper, we extend the Bayesian formulation of adaptive sampling [4] to targets that are dynamic as well as sparsely located in the scene. Our model encompasses target motion, appearance and disappearance, and target amplitude variation. This formulation can simultaneously account for multiple targets as well as allocation of continuous-valued sensing resources, such as energy, in contrast to the discrete resource allocation formulation in [12]. Our formulation is based on a simple approximation to the target posterior distribution and a multistage extension of the cost function in [4]. In the context of this framework we then introduce the Dynamic Adaptive Resource Allocation Policy (D-ARAP), a nonmyopic policy for adaptive sampling that achieves a favorable trade-off between performance and planning complexity. Our analysis suggests that as compared to approximate POMDP solutions, in particular rollout policies, D-ARAP performs well but at a fraction of the computational cost. Compared to myopic policies, D-ARAP has increased robustness to noise, missing data, and model mismatch. Lastly, compared to the non-adaptive uniform policy, D-ARAP continues to yield large improvements in estimation and detection performance similar to the static case [4], [9].
For static targets, it is known [4], [5], [14] that estimation gains due to adaptive sampling increase in the sparse target regime, where targets occupy few locations in the search area. The present work shows that the benefits of adaptive sensing framework [4] can be extended to the dynamic setting. We derive upper bounds on adaptive performance gains through analysis of omniscient and semi-omniscient policies with complete or partial knowledge of target locations over time, respectively. The bounds confirm the benefit of the sparse target regime for dynamic targets. They also characterize the effect of target motion and amplitude variation on the potential gain. We show simulations that indicate that D-ARAP can approach the semi-omniscient performance as the SNR and number of stages increase. Furthermore, comparison of the omniscient and semi-omniscient policies allows us to quantify the effect of partial and causal knowledge of target motion.
The rest of this paper is organized as follows. We formalize the problem in Section II and present adaptive sensing policies in Section III. We derive performance bounds for adaptive sensing of dynamic targets in Section IV. Numerical performance analysis is given in Section V. In Section VI, we conclude and discuss future directions.

II. PROBLEM FORMULATION
We consider a space X = {1, 2, . . . , Q} containing Q cells and a time-varying region of interest (ROI) Ψ(t) ⊂ X , t = 1, . . . , T . Let i be a location in X and define I i (t) to be the indicator that i is in the ROI at time t, i.e., I i (t) = 1 if i ∈ Ψ(t) and I i (t) = 0 otherwise. We use a probabilistic target model in which I i (1) = 1 with prior probability p i (1), independently of the other indicators. For I i (t) = 0, the corresponding signal amplitude θ i (t) is taken to be zero, while for I i (t) = 1, the amplitude θ i (t) is modeled as a Gaussian random variable. The initial amplitudes θ i (1), i ∈ Ψ(1) are drawn independently with means µ i (1) and variances σ 2 i (1). As in previous work [4], [9], a non-informative uniform prior on target locations/amplitudes is assumed with p i (1) = p 0 , µ i (1) = µ 0 and σ 2 i (1) = σ 2 0 for all i, although non-uniform priors could also be accommodated.
We generalize previous work [4], [9] by introducing a dynamic target state model with state transitions and a birth-death model for target appearance/disappearance. To describe the model, we index the targets by target number instead of by cell: Let s (n) (t) ∈ Ψ(t), n = 1, . . . , |Ψ(t)| be the position of the n-th target at time t and ϑ (n) (t) = θ s (n) (t) (t) be its associated amplitude. Let α be the probability that each target is removed from the scene at each time. The target transition model and amplitude update for remaining targets is where π 0 is the probability that a target remains in the same location, G(j) is the set of cells that are neighbors of cell j, and Z (n) (t) is a zero mean white Gaussian noise with variance ∆ 2 : ∆ 2 > 0 captures the variance of random perturbations to the target amplitudes. The model (2) can be used to approximate the effect of model mismatch, target fluctuations, or scattering of the radar signal.
In each of these cases, measurements at each stage are discounted by the increase in uncertainty due to the error sources.
Let B(t) be the event that a single new target enters the scene at time t with probability β. Then conditioned on B(t), We restrict our attention to the case where at most one target occupies a cell at any instant. In the sparse situations considered here (i.e. p 0 ≪ 1), this occurs with high probability.
Observations are made in T stages with effort levels λ i (t) that vary with location i and time t. In general, effort might be computing power, complexity, cost, or energy that is allocated to probing a particular cell. It is assumed that the quality of an observation increases with effort. Given λ i (t), the corresponding observation y i (t) takes the form where n i (t) represents i.i.d. zero-mean Gaussian noise with variance σ 2 . The total effort in each stage The goal is to estimate the target state Ψ(t), {θ i (t)} i∈Ψ(t) t=1,...,T over T stages. The posterior distribution of the target state conditioned on measurements is therefore of central interest. When the targets are static, the posterior distribution factors by cell and can be exactly represented by the posterior mean/variance of the target amplitude and the posterior probability of target existence in each cell.
In the dynamic case, there is no simple factorization that allows for efficient exact estimation of the posterior distribution, partly due to the fact that the posterior distribution of the amplitudes becomes a Gaussian mixture (due to nonzero transition probabilities to neighboring cells) rather than a simple univariate Gaussian. As an alternative, the posterior distribution may be approximated using several standard approaches including particle filters, extended Kalman filters, and Unscented Kalman filters, with varying tradeoffs between accuracy and computational burden.
Here we propose a simple approximation to the posterior that is accurate under two conditions: (a) at most one target occupies the vicinity of a cell at any one time; and (b) the Gaussian mixture is well represented by the most likely Gaussian mixture component; i.e., the component belonging to the most probable trajectory of the target given the measurements. Further details on this approximation are available in Chapter 3 of [15]. The first condition is valid when there is very low probability that targets will cross tracks. In practice, one could relax this condition by using methods such as the Joint Multitarget Probability Density Filter (JMPD) [16], which independently tracks targets when they are far apart, while jointly tracking targets that are close to each other. However, we do not address this generalization in this paper. The second condition is equivalent to the existence of a dominant mode in the Gaussian mixture characterizing the posterior density.
Under conditions (a) and (b), the posterior distribution can be approximated with the following: where Y (T ) = {y i (t)} i∈X ,t∈{1,...,T } is the sequence of observations. For brevity, we denote the collection of posterior probabilities, means, and variances as This representation may be combined with a particle filter, e.g. one using the JMPD [16], for target state estimation, while using the above model for resource planning.

III. SEARCH POLICY FOR DYNAMIC TARGETS UNDER RESOURCE CONSTRAINTS
In this section, we provide methods for determining for a sequence of effort allocations λ = {λ(t)} T t=1 where λ(t) = {λ 1 (t), . . . , λ Q (t)}. λ(t) is a mapping from the previous observations Y(t−1) to [0, Λ(t)] Q and is called the allocation policy.

A. Optimization objective
The following is a multistage extension of the cost function in [4], [9]: where {γ(t)} T t=1 is a set of known weights on different planning stages. The cost function (10) corresponds exactly to the MSE for estimating target amplitudes {θ i (t)} i∈Ψ(t) in two cases: (a) when targets are stationary (but amplitudes may vary); and (b) when target locations may change but are known exactly (i.e. p i (t) = I i (t)). We define the per-stage cost: Recalling from (6) , the expected per-stage cost can also be expressed where the expectation is taken over both Ψ(t) and Y(t − 1).

B. Optimal dynamic programming solution
The optimal effort allocation problem can be stated as where Dynamic programming (DP) can be used to exactly obtain an optimal policy that minimizes equation (10). In the case when γ(T ) = 1 and γ(t) = 0, t < T , this policy is given by a sequence of recursive minimizations that proceed as follows 1 1 As a minor technical point, if we consider general values for the weights γ(t), then equation (16) requires an additional term for the current cost at stage t. 8 and define recursively for t = T − 1, T − 2, . . . , 1 Wei and Hero [9] show that this solution is only tractable for T ≤ 2. This is an artifact of the difficulty in computing the expectation in (16), which is generally approximated with Monte Carlo samples, as well as the fact that λ(t) lies in a multi-dimensional space for t > 1. For T > 2, we therefore have to consider approximations to the optimal policy. In the next sections, we provide a myopic solution that optimizes M t (λ; x(t)) for t = 1, 2, . . . , T without recursion (i.e., assuming that t is the last stage) and an alternative policy that improves upon the myopic solution with low additional computational cost.

C. Myopic policy
The myopic optimization problem at time t is given by where λ(t) depends on previous observations Y(t − 1) through x(t). The optimal solution, similar to the one given in [9], begins by defining χ to be an index permutation that sorts the quantities p i (t)σ 2 i (t) in non-increasing rank order: Let c i (t) = σ 2 /σ 2 i (t). Then define g(k) to be the monotonically non-decreasing function of k = 0, 1, . . . , Q with g(0) = 0, g(Q) = ∞, and for k = 1, . . . , Q − 1. Then the solution to (17) is for i = 1, . . . , k * and λ m χ(i) (t) = 0 for i = k * + 1, . . . , Q. The number of nonzero components k * is determined by the interval (g(k − 1), g(k)] to which the budget parameter Λ(t) belongs. Since g(k) is monotonic, the mapping from Λ(t) to k * is well-defined.

D. Non-myopic extension
We propose a simple improvement to the myopic policy that combines exploitation of the current belief state and exploration of the scene at large. The proposed non-myopic allocation policy is called the Dynamic Adaptive Resource Allocation Policy, or D-ARAP, and is defined by where κ(t) ∈ [0, 1] is the exploration coefficient, λ u (t) = Λ(t)/Q is the uniform allocation policy, and λ m i (t) is given by (20). Note that the first term in (21) allocates a percentage of the resources uniformly to the scene, while the second term weights allocations according to the myopic solution (20).
We define the full set of exploration coefficients for a T -stage policy as κ(T ) = {κ T (t)} T t=1 , where the subscript T indicates the number of stages when needed for clarity. In the rest of the paper, we often use vector notation to represent the allocations to all T stages, defined as Without prior knowledge on the location of targets, the first stage should be purely exploratory, i.e., κ T (1) = 1. In addition, since the last stage should be purely exploitative or myopic, we set κ T (T ) = 0. To determine κ(T ), we consider both offline policies, which are determined prior to collecting observations, and online policies, which are determined adaptively as measurements are collected. Note that λ m i (t) is a function of previous measurements. Thus, the offline policies can still be data-dependent as long as κ T (t) < 1.

E. Rollout policy
We first describe an offline policy called the "offline rollout policy" that is recursive in the sense that a T -stage policy is created by building upon a previously defined (T − 1)-stage policy. This method also requires a "base" policy, φ(T 0 ) which pre-defines the last T 0 stages of a T -stage policy. Rollout policies for general dynamic programming problems are discussed in great detail in [17]. In this context, the simplest rollout policy is just φ(1) = {0}, which indicates that the last stage should be purely exploitative. The pseudocode for the offline rollout policy is given in Fig. 1 and yields policies for to be the first t values of the previous policy κ(τ − 1). Then in each iteration, a τ -stage policy is constructed as κ(τ ) = is a single parameter which we search over. The values of κ(τ − T 0 ) are chosen to minimize the full non-myopic cost in (10).

end for
Return {κ(τ )} T τ =T0+1 . end procedure The expectation in (10) is approximated with Monte Carlo samples from the belief state x(t) for t = 1, 2, . . . , τ . This process can be done efficiently by noting that the first τ − T 0 − 1 stages remain the same for κ(τ − 1) and κ(τ ). Therefore, we only need to draw samples for the last T 0 + 1 stages at each iteration, as well as perform a line search over the single parameter κ(τ − T 0 ). Thus, the offline rollout policy requires O(T T 0 ) Monte Carlo simulations to determine policies for {κ(τ )} T τ =T0+1 . This improves upon the approach [18] where a nested optimization procedure (aka, the "nested policy") required O(T 2 ) calculations. In our experiments (not shown), the offline rollout policy performed just as well as the nested policy, though with reduced computational complexity. We do not further discuss the nested policy.

F. Myopic+ policy
To further reduce the computational burden, we consider another policy which we call the "myopic+ policy" which requires only O(T ) expectations to be calculated (once again through Monte Carlo approximation.) Similar to the offline rollout policy, this policy is built in a sequential fashion. Whereas the τ -stage offline rollout policy iteratively optimizes over κ τ (τ − T 0 ) followed by a T 0 -stage base policy, the myopic+ policy chooses κ τ (τ ) directly without any subsequent rollout. In particular, we defineκ(τ ) = {κ(τ − 1), κ τ (τ )}. Note that givenκ(τ − 1), the current state x(τ ) is random only through the noisy measurements Y (τ − 1). Additionally, givenκ(τ − 1), minimization of J τ (λ d (κ(τ ))) is equivalent to minimization of the following over the single exploration coefficient κ τ (τ ): Note that the quantity within the expectation is always minimized by κ τ (τ ) = 0, since, by definition, this value optimizes the myopic cost. To promote exploration, i.e. κ τ (τ ) > 0, we adopt a (1 + ρ)-optimality criterion:κ where ρ > 0 is a tolerance and where To understand the optimality-criterion in equation (24), it is illustrative to look at Fig. 3 which plots B D 2 (1, κ) as a function of κ for low, medium, and high values of Λ(2) in (a), (b), and (c), respectively. It is seen that in all cases, the myopic cost is optimized when κ(2) = 0. To encourage exploration, (24) increases κ(2). The amount of increase becomes larger as the SNR decreases. The red dotted line shows a deviation of 10% from the minimum cost, while the yellow circle marks the point where κ attains the maximum deviation.
The offline rollout and myopic+ policy parameters are shown in Fig. 4 for various values of SNR 2 , T = 20, and model parameters given by Table I. It should be noted that the offline rollout policies require numerical optimization over the κ(t) parameters, which tend to be noisy unless a large number of Monte Carlo realizations are used. In contrast, experiments in Section V indicate that the myopic+ policy parameters tend to be less sensitive to noise and mismodeling errors.  , and (c), respectively. The myopic+ policy is given in (d), which performs more exploration in general for lower SNR than the rollout policies. In all four policies, κ(t) is nearly monotonically decreasing in t. The offline rollout policies all exhibit a phase transition from a low SNR regime (where κ(t) ≈ 0) to a higher SNR regime where significant exploration occurs.
The heatmaps indicate that higher values of T0 lead to more exploratory strategies at low SNR and t. The myopic+ policy is monotonically decreasing in both SNR and t.

IV. PERFORMANCE BOUNDS
In this section, we develop bounds on the performance gain that can be achieved with D-ARAP, and more generally any adaptive policy, compared to non-adaptive uniform allocation policies. The gain is measured using the cost function (10). The bounds result from analyzing two oracle policies that have exact knowledge of target locations. The first of these, the omniscient policy, has access to the target locations Ψ(t) for all t and is discussed in Sections IV-A and IV-C. The second, the semi-omniscient policy, has access to only the previous locations Ψ(t − 1) at stage t and is considered in Sections IV-B and IV-D.
We distinguish two qualitatively different cases corresponding to either constant or increasing target amplitude variance, characterized by the increment ∆ 2 = 0 or ∆ 2 > 0 respectively. For oracle policies, the definitions of the state variables (6)- (8) are modified by augmenting the observation history Y (t − 1) with the exact target positions In this case, it can be shown that the posterior variances evolve according to where H(j) = {j} ∪ G(j). Hence in the case of static target amplitudes (∆ 2 = 0, Sections IV-A and IV-B), the posterior variances decay to zero as t increases, while for ∆ 2 > 0 (Sections IV-C and IV-D), the posterior variances reach a nonzero steady state. For simplicity, we make the following assumption for derivation of the performance bounds: A. Omniscient policy, ∆ 2 = 0 In Sections IV-A and IV-B we make the additional assumption that the target amplitudes are constant: In this case, (26) reduces to a simple recursion for the posterior precisions c i (t) = σ 2 /σ 2 i (t): where c i (1) = σ 2 /σ 2 0 for all i. The omniscient policy has perfect knowledge of the target locations Ψ(t) at all times. Conditioned on Ψ(t), it follows that the target probabilities are atomic, p i (t) = I i (t), and the omniscient policy allocates effort solely and uniformly to targets: noting that |Ψ(t)| = |Ψ(1)| under Assumption 1. Given (27) and (28), the posterior precisions also remain uniform over targets: To verify (28), we begin with t = 1, in which case c i (1) is uniform over i ∈ Ψ(1). Specializing the optimal allocation given by (18)-(20) to the case p i (1) = I i (1), it is seen that the sequence g(k) (19) is equal to 0 for k < |Ψ(1)| and ∞ for k ≥ |Ψ(1)|. Hence the number of nonzero allocations k * = |Ψ(1)| and (28) follows from (20). For t > 1, (28) continues to hold by induction since We define the gain of a policy with respect to the uniform allocation policy as Using (28) and (29), the gain of the omniscient policy is characterized in Proposition 1. The following assumption is used to obtain a more interpretable expression.
Assumption 3. The stage weights γ(t) decay to zero as t decreases from T .
This assumption ensures that as T → ∞, the cost (10) becomes dominated by terms at large t. The assumption is satisfied by common "forgetting" schemes that emphasize performance in later stages.
. Under Assumptions 1 and 2, the gain of the omniscient policy relative to uniform allocation is bounded from above as 4 .
In the high-SNR limit (σ 2 → 0) or if Assumption 3 holds and the number of stages T → ∞, then r 0 (t) → 0 and the above expression simplifies to Proof: See Appendix II.
Proposition 1 shows that the omniscient gain is proportional to the sparsity of the scene, similar to [4], [5], [9]. In other words, the potential gain due to adaptation is higher when there are fewer targets.
We now turn to the semi-omniscient policy, which in stage t has knowledge only of the previous target locations Ψ(t − 1). In the semi-omniscient case, the target probabilities p i (t) = Pr(I i (t) = 1 | Ψ(t − 1)) are no longer binary but are given by the target dynamics (1) as where G(Ψ(t − 1)) = i∈Ψ(t−1) G(i) is the set of neighbors of all targets. We assume that the probability of target transitions is bounded.

Assumption 4.
The probability of a target remaining in the same location is no smaller than the probability of it transitioning to any one neighboring cell, Unlike in the omniscient case, under the semi-omniscient policy the posterior precisions c i (t) become random and non-uniform for t > 1 over the set of locations H( where p i (t) > 0. The non-uniformity arises because H(Ψ(t − 1)) contains both target and non-target locations, and even among targets, the precisions differ randomly depending on the number of times a target has stayed in the same cell or moved to a different one. This makes it difficult to determine the allocations analytically via (18)-(20). As an alternative, we focus on developing an upper bound c(t) on where the threshold c crit is defined as and e(π 0 , G) = |G|π0 1−π0 − 1 ≥ 0. We also use the following assumptions to determine the number of nonzero allocations under the semi-omniscient policy: Assumption 5. The posterior precisions are uniform in the vicinity of targets, Assumption 5 replaces c i (t) with an upper bound on its expected value and is therefore an optimistic approximation consistent with deriving the upper bound c(t). As t increases, the short-term deviations of c i (t) from its mean decrease relative to the long-term increase of the mean and the approximation corresponds to an upper bound on c i (t) itself with high probability. We note that Assumption 5 is used primarily to determine the number of nonzero allocations and only indirectly to determine the amount allocated.
Given Assumptions 4-6, the following lemma proves that the recursion in (32) where c(t) is defined by the recursion (32).

Proof: See Appendix III.
Remark. It can be shown that for c(t) < c crit , the coefficient multiplying c(t) in (32) is greater than or equal to 1, with equality if and only if Assumption 4 holds with equality. Hence c(t) increases geometrically with t if the inequality in Assumption 4 is strict. A closed-form expression can be derived for c(t) in the regime c(t) < c crit , for example by viewing (32) as specifying a first-order recursive system driven by a step input, but we do not pursue this here.
Using Lemma 1 and taking the limit t → ∞, we arrive at a simple characterization of the semiomniscient policy.

Proposition 2.
Under Assumptions 1, 2, and 4-6, in the limit t → ∞ the expected per-stage cost of the semi-omniscient policy is bounded as Proof: See Appendix IV.
Proposition 2 can be used to determine the gain of the semi-omniscient policy relative to uniform allocation in the limit T → ∞, again invoking Assumption 3 so that the total cost J T (λ) is dominated by terms at large t. In the special case γ(T ) = 1, γ(t) = 0 for t < T , the gain reduces to the ratio of the expected final-stage costs. From Proposition 2 and using (98) for the per-stage cost of the uniform policy withΛ(t) = Λt, the gain is bounded as Compared to Proposition 1 in the limit T → ∞, the analogous result for the omniscient policy, (34) shows that the performance of the semi-omniscient policy is discounted by the probability π 0 that target locations are constant from stage to stage.
In the remainder of this section, we relax Assumption 2 on the variance increment ∆ 2 . For ∆ 2 > 0, the evolution equation for posterior variances reverts to (26), from which it is difficult to obtain a closedform expression for σ 2 s (n) (t) (t), in contrast to the case ∆ 2 = 0. We focus instead on the steady-state behavior in the limit of large t. Using Assumption 3, in the limit T → ∞ the cost J T (λ) becomes wellapproximated by a sum of terms at large t, each of which is proportional to the steady-state expected . This simplification allows us to obtain the following bound on the gain of the omniscient policy.
. Under Assumptions 1, 3, and 6, in the steady-state limit T → ∞ the gain of the omniscient policy relative to uniform allocation is bounded from above as Proof: See Appendix V.  Table I. The upper horizontal axis indicates the equivalent values of r + , which is inversely proportional to SNR when ∆ 2 is fixed as in Table I. Besides confirming that the potential gain increases as p 0 decreases, the heat map shows that there are three regimes with respect to SNR. In Region (A), the SNR is insufficient to offset the degradation due to ∆ 2 and gains scale only as 1/ √ p 0 . In Region (C), the SNR is high and knowledge of target locations, which increases the of small r + , where r + is defined in Proposition 3, all c i (t) are guaranteed to be small. We can then derive the following bound on the gain of the semi-omniscient policy under the same assumptions as in Proposition 3.
Then in the steady-state limit T → ∞, the gain of the semi-omniscient policy relative to uniform allocation is bounded from above as with equality in the limit r + → 0.
Proof: See Appendix VI.
for some t with c(t) ≥ c crit , then (36) also holds for stage t + 1 with Proof: See Appendix VII.
Lemma 2 can be used to derive an upper bound on the expected posterior precisions in the steady state limit t → ∞. Define c ss = lim t→∞ E c s (n) (t) (t) | |Ψ(1)| to be the steady-state precision for targets.

Lemma 3. Under Assumptions 1 and 4-6, the steady-state precision c ss for targets is bounded from
above by a root c ss of the cubic equation provided that c ss ≥ c crit .
Proof: Initially, let c ss denote an upper bound on c ss such that c ss ≥ c crit . Then Lemma 2 implies that c ss is also bounded by To obtain a stationary upper bound on c ss , we equate c ss with the above expression, resulting in (38) after some algebraic manipulations. This stationary bound is valid provided that a root of (38) satisfies the initial assumption c ss ≥ c crit .
In general, it is difficult to obtain a tractable expression for c ss from (38). We consider two special cases. In the case π 0 = 1, the cubic polynomial can be factored into The first factor yields an infeasible negative root while the second factor can be shown to be proportional to the quadratic polynomial in (105) with λ s (n) (t) (t) = Λ/|Ψ(1)|, the effort allocation for targets under the omniscient policy. Thus setting π 0 = 1 recovers the omniscient case analyzed in Section IV-C. For π 0 < 1, a tractable solution can also be extracted if ∆ 2 is close to zero, as detailed in the following lemma.
Combining Lemmas 3 and 4, we arrive at the following steady-state characterization of the semiomniscient policy.
Proposition 5. Given Assumptions 1 and 3-6, assume in addition that ∆ 2 Λ/σ 2 ≪ 1 and π 0 is large enough so that Then in the steady-state limit T → ∞, the gain of the semi-omniscient policy relative to uniform allocation is bounded from above as Proof: See Appendix IX.
We again compare the above result to Proposition 3 on the omniscient policy, this time in the regime In this case, the gain of the omniscient policy is approximately given by 1/ √ p 0 and the performance loss due to causal knowledge of target motion is therefore √ π 0 .

A. Simulation set-up
In this section, we analyze the performance of the proposed rollout and myopic+ D-ARAP policies in a variety of situations that include model mismatch and missing measurements. We further examine the policies over a variety of performance metrics (MSE and probability of detection). With regard to rollout policies, we investigate the effects of using different base policies for offline rollout, and also compare the performance of offline and online rollout. We continue by investigating the sensitivity of the dynamical model by varying birth/death probabilities and transition probabilities. Simulation parameters are given by Table I unless stated otherwise.

B. Comparison to semi-omniscient/uniform policies
In this section, we examine the performance of all of the proposed policies (offline rollout, myopic+, and myopic) as well as the semi-omniscient oracle, which provides an upper bound on performance.   for different values of T with 0 dB and 10 dB SNR, respectively. Generally the offline rollout policy has the highest gains in MSE among non-oracle policies, with performance close to the semi-omniscient policy as T gets large. However, the performance gain of the offline rollout is small with respect to the myopic+ policy. Fig. 6(c) provides the gain in the objective function in (10) with respect to the uniform policy. Recall that (10) is used as a surrogate optimization objective for amplitude estimation MSE.

Comparing (b) and (c), it is clear that improvements in cost generally lead to improvements in MSE,
suggesting that (10) is a good surrogate function. In (c), the bound in Prop. 3 is also plotted (note that the condition (35) in Prop. 4 is not satisfied). In the next section, we empirically analyze the conditions which lead to tight oracle bounds as a function of model parameters and SNR.
Figs. 6 (d) and (e) show the probability of detection for a fixed probability of false alarm (P f a = 10 −4 ) as a function of T for 0 dB and 10 dB SNR, respectively. The probability of detection for D-ARAP (offline rollout and myopic+ policies) consistently approaches 1 as T gets large and does so significantly faster than for the uniform and myopic policies. Moreover, D-ARAP achieves perfect detection P d = 1 within just a few stages. This pattern is verified in Fig. 7(c) for fixed SNR=20 dB. The semi-omniscient policy performs the best, followed by the myopic+ and myopic policies. We also provide a theoretical upper bound as given in Chapter 3 of [15], which was derived under stronger assumptions than given in Section IV. There is an apparent bias between the semi-omniscient policy and this theoretical upper bound. In (d), we analyze this bias as a function of SNR while fixing β = 0.01. As SNR gets large, all policies approach the theoretical upper bound on performance.

D. Model Mismatch
In this section, we compare the non-myopic policies to the myopic and semi-omniscient oracle policy in cases where there might be model mismatch. In particular, we consider the case where the policy is derived under the model given in Table I with prior mean amplitude µ 0 = 1. This model is mismatched to the actual measurements where the target amplitudes are all identical and lower than expected for θ 0 ∈ [0.2, 1]. For θ 0 ≪ 1, noisy measurements from cells containing targets can be easily confused with the background noise. In these situations, the myopic policy will be more adversely affected by small posterior probability p i (t) in the ROI i ∈ Ψ as compared to the non-myopic policies. Fig. 8 shows the performance as a function of MSE (lower is better). When θ 0 < 0.45 (Region A), all policies perform worse than the uniform search, indicating severe model mismatch. Conversely all policies show positive performance for θ 0 > 0.45 (Regions B and C). Moreover, the performances of the non-myopic policies improve at a faster rate than the myopic policy, and quickly approach the theoretical bound as given by the semi-omniscient oracle policy.

E. Complex dynamic behavior: missing measurements
In the next simulation, we test the policies in the scenario where the sensor turns off periodically for several consecutive stages, creating time periods of missing data. This is representative of a modern radar system that must multi-task between different modes of operation, e.g., tracking, automated target recognition, and synthetic aperture radar [19], which compete for radar resources. In this simulation, 6 stages of data are collected followed by 3 stages of no measurements. Fig. 9 shows the resultant MSE (on a dB scale, lower is better) for the uniform, myopic, offline rollout, myopic+, and semi-omniscient policies and for various SNR (per-stage budgets of 0, 5, 10 and 15 dB).
All adaptive policies perform better than uniform search which has growing errors with t. In Fig. 9(a) and Fig. 9  of the base policy. We consider myopic base policies which set the exploration parameter κ(t) = 0 for T 0 = 1, 2, 5 consecutive stages. We compare performance for two SNR levels, with SNR=10 dB given by diamonds, and SNR=0 dB given by circles. All policies perform at least as well as the myopic policy.
Moreover, increasing T 0 generally improves performance in both estimation and detection. It should be noted that for low SNR, using T 0 = 1 did not noticeably improve performance over the myopic policy.
As discussed in the introduction, the full POMDP solution to the adaptive sensing problem is generally intractable due to the size of belief state and action spaces. As an alternative, we consider an approximate POMDP solution, namely the (online) rollout policy, in order to compare D-ARAP to online solutions.
Note that in online solutions, the optimal action at each stage must be chosen separately for each realization of the model. Thus, the online rollout policy likely will incur significant computational costs in comparison to the offline policies presented in this paper.  We compare offline and online policies using myopic base policies of various stage lengths, T 0 . In Fig. 11(a), we compare the performance of the offline and online rollout policies in the SNR=10dB case for parameters given in Table I. The online and offline rollout policies perform similarly in the standard model (a) without model mismatch or missed observations. The online policy has significantly noisier results, which is partly caused by computational limits on the number of realizations from which the average performance is computed. Nevertheless, the online policy clearly performs better than the myopic policy. In Fig. 11(b), we compare the performance of the offline and online rollout policies in the SNR=10 dB case where stages of measurements are missing as in Section V-E. It is seen that the online T 0 = 2 rollout policy performs similarly to the offline T 0 = 5 policy. On the other hand, the online T 0 = 5 policy performs significantly worse (and approximately the same as the myopic policy).
In our experience, the online rollout policies tend to be significantly noisier than their offline counterparts. This may be due to (a) necessary tradeoffs in computational (Monte Carlo) effort vs. accuracy or (b) difficulties in sampling from the belief state, particularly in sparse scenarios where the probability of targets existing at given locations is small. This indicates one advantage of the offline policies, which tend to be more robust to complex environments.

VI. DISCUSSION AND FUTURE WORK
This paper presented a framework for adaptive sampling that significantly extends previous work [4] to incorporate dynamic targets while providing a computationally tractable solution, namely D-ARAP.
A cost function related to mean squared error was proposed and upper bounds on the performance of adaptive sensing were derived through analysis of oracle policies. These bounds shed light on the impact of target motion and amplitude variation in addition to target sparsity. In terms of implementable policies, a myopic solution is given that has an analytical form, but suffers from being overly aggressive in the allocation of resources in cases of model mismatch or faulty measurements. We offer a nonmyopic extension of the myopic policy that balances exploration of the scene and exploitation of prior Future research directions include consideration of constraints on the number of measurements, which may include coarse-scale or compressed sensing measurements. Moreover, further analytical results are of interest, for example convergence rates (in comparison to exhaustive search) and/or minimum detectable amplitudes, and performance bounds that are more refined than the oracle bounds presented herein.
Finally, online policies that are computed as measurements are taken may be worthy of continued study since they could improve performance dramatically in some cases, including cases where targets will be obscured in the near future.

ACKNOWLEDGMENTS
The authors would like to thank Dr. Eran Bashan for his valuable insights and assistance in the development of this research.

APPENDIX I EFFICIENT POSTERIOR ESTIMATION FOR GIVEN DYNAMIC STATE MODEL
In order to use the algorithms provided in this work to adaptively estimate the state ξ(t) given the measurements, we need to be able to calculate the posterior probabilities for the indicator variables, given the measurements up until time t. To do this efficiently (which is required for planning purposes), we make the following assumptions: be the posterior probabilities that need to be calculated. For t = 1, we have under assumption 7. For t > 1, we have Pr(s (n) (t) = i|Y (t − 1)), where the last equation can be derived noting that Thus, in order to compute equation (46), we need to be able to estimate the state ξ(t) given Y (t − 1).

A. Recursive equations for updating ξ(t)
In general, we can compute the posteriors using the equations: Note that each target has an associated real-valued amplitude x (n) (t) and a location on a large discrete grid s (n) (t) ∈ {1, 2, . . . , Q} for large Q. Thus, the joint densities f (ξ(t)|Y (t − 1)) and f (ξ(t)|Y (t − 1)) are in general very high-dimensional functions that may be intractable to estimate exactly. Under certain assumptions, however, it may be possible to derive exact equations for these updates.

B. Static case
In the static case when α = β = 0 and π 0 = 1, we have the simple situation where Since targets are fixed in position and cannot occupy the same cell by Assumption 7, we can easily show that the joint density factors into: Moreover, Ψ(t) = Ψ and since the targets are independent across cells, we have: where y i (t) = {y i (t 0 )} t t0=1 . Note that θ i (t) is only defined if I i = 1. Conditioned on this event, we furthermore note that θ i (t) and y i (t)|θ i (t) are normally distributed given the allocations λ i (t). Thus, the posteriors f (θ i (t)|y i (t ′ ), I i ) for t ′ = t, t − 1 can be updated exactly through the Kalman filter equations: where δ i (t) is the residual measurement error, s i (t) is the update measurement error, Γ i (t) is the Kalman gain, and (θ i (t|t),σ 2 i (t|t)) are the updated state estimates. The predict equations are given by: Moreover, the posteriors on the indicator functions can be easily computed recursively as where we note that when I i = 0 and when I i = 1 where φ(x; µ, σ 2 ) is the Gaussian pdf with mean µ and variance σ 2 evaluated at x. From this equation we see that In the static case, we see that updating the posteriors for I i for all t = 1, 2, . . . , T involves (a) updating the conditional mean and variances for θ i (t) given the measurements, and (b) updating the posterior probability for I i = 1. This gives insight into an approximate method that we will use in the general case when the targets are allowed to move, enter, or leave the scene.

C. Approximations in the general case
Similar to the static case, we assume that there are no interacting targets so that we can factor our posterior density into a form that makes it tractable to estimate directly. In order to do this, we use This is clearly more restrictive than Assumption 7. Under this assumption, we have for t ′ = t, t − 1 Beginning with the target amplitudes, we note that where Ψ H(i) (t) = {I j (t)} j∈H(i) . Define E i,j (t) to be the event that assigns Ψ H(i) (t) as The event E i,0 (t) refers to the case where a target is added to the scene at location i at time t. Then, under the assumption that at most one target exists in the vicinity of a cell, we have where it is understood that in the case where a new target is added to the scene and In the static case, both f (θ i (t)|θ j (t − 1)) and f (θ j (t − 1)|I j (t − 1) = 1, Y (t − 1)) are Gaussian which makes it possible to analytically integrate equation (69). Indeed, at time t = 1, it can be easily seen that θ j (1) ∼ N (µ θ , σ 2 θ ). However, for t > 1, equation (69) shows that we get a Gaussian mixture model with mixing coefficients given by In order to make the estimation of the posterior distributions very simple, we make the assumption that for a single j * ∈ H(i) ∪ {0}. In other words, conditioned on the event that a target exists at cell i, it is known with probability 1 that the target transitioned from either a single neighboring cell or entered the scene at time t. This assumption is restrictive except at high SNR. However, it allows us to simplify equation (69) as which can easily seen to be Gaussian distributed as long as f (θ j (t)|I j (t) = 1, Y (t)) is Gaussian. Indeed, we see the recursion Using equations (74) and (75), it is simple to show that a simply modified Kalman filter will give the exact recursion required to update the posterior densities. In fact, it is the same recursion given in the static case, except that we havê Proposition 6. When (73) holds for all i ∈ Ψ(t) and for all t = 1, 2, . . . , T , then the cost function (10) is proportional to the minimum weighted mean squared error Proof: We first note that sinceθ i (t) is the conditional mean estimator by definition and using the definitions in (73) and (78).
Moreover, by the update equations (54)-(58), it can easily be shown that Thus we have where the last equality occurs because E {I i (t)|Y (t)} = p i (t).
Looking at the update equations for the target indicators, we get and where Similar to the derivation in the static case, it can easily be seen that and

D. Discussion of generalizations of state model and posterior estimation methods
As mentioned earlier, it is a difficult, if not intractable, problem to exactly estimate the posterior distribution of ξ(t) given Y (t−1) that is required for our adaptive algorithms. We have provided a simple algorithm that approximates the posterior distribution under some restrictive assumptions. A simple way to alleviate these restrictions is to use a particle filter implementation for ξ(t) or other approximate method (e.g., the extended and unscented Kalman filters).
Moreover, we have provided a particular state model that builds on our previous work with the inclusion of transition, birth, and death probabilities. However, there are many other models for dynamic state models, including linear and nonlinear motion models, targets that may occupy multiple adjacent cells, and various noise models. In any of these cases, one would have to use a different posterior estimation algorithm to provide estimates of Pr(I i (t) = 1|Y (t − 1)).
Future work plans to compare other posterior estimation algorithms such as the JMDP particle filter [16] to the one presented in this work, as well as generalizations to more interesting dynamic state models.

E. Unobservable targets
One particular generalization of the measurement model that is used in this work is the inclusion of indicator variables for observable/unobservable targets. In many applications, certain locations may be obscured for short durations, such as locations in the null of a radar beam. Define to be an indicator variable for the observability of the i-th location. Then the measurement model becomes It is assumed that O = {O i (t)} i,t is known to the user a priori. Thus, we are required to estimate the densities: for t ′ = t, t − 1. We make the simplifying assumption that if I i (t − 1) = 1, then It can easily be seen that when O i (t) = 1, we have the identical update equations to the fully observable case. However, when O i (t) = 0, the predict equations remain the same as before, but the update equations are changed in the following manner: and the target amplitudes when O i (t) = 0:θ APPENDIX II

PROOF OF PROPOSITION 1
Conditioned on the number of targets |Ψ(1)|, the per-stage cost of the omniscient policy can be determined by setting p i (t) = I i (t) and substituting (28) and (29) into (11), yielding .
As a function of |Ψ(1)|, M t (λ o ) is proportional to h 0 (z) = z 2 /(z +Λ(t)), where z = (σ 2 /σ 2 θ )|Ψ(1)|. The derivatives of the function h 0 are given by showing that h 0 has a positive fourth derivative for z ≥ 0. Hence by Taylor's theorem, h 0 is lower bounded by its third-order expansion, Letting the center of expansion z 0 = E[z] and taking expectations with respect to z, we obtain Noting that |Ψ(1)| ∼ Binomial(Q, p 0 ), the moments of z are Substituting (94) and (96) into (95) and using the definition r 0 (t) = σ 2 Q/(σ 2 θΛ (t)) to simplify, we obtain This bound holds for each t and therefore the total cost is bounded as For the uniform allocation policy defined by λ u i (t) = Λ(t)/Q for all i, a formula similar to (29) holds for c i (t) and the per-stage cost (11) is again conditioned on |Ψ(1)|. Hence the total cost is The result follows from the ratio of (97) and (99).

APPENDIX III PROOF OF LEMMA 1
By definition of c(1), the lemma is true for t = 1. We proceed by induction, considering first the case c(t) < c crit . First it is shown that under the assumptions of the lemma and c(t) < c crit , all locations in H(Ψ(t − 1)) receive nonzero allocations in stage t. Given (31) and Assumptions 4 and 5, the permutation χ in (18) ranks all of the indices i ∈ Ψ(t − 1) in the ROI equally, followed by i ∈ G(Ψ(t − 1)), again all equally. It is then straightforward to see that the sequence g(k) (19) that determines the number of nonzero allocations is as follows: In particular, given Assumption 6 and c(t) < c crit , we have g (|H(Ψ(1))| − 1) < c crit |Ψ(1)|e(π 0 , G) = Λ < g (|H(Ψ(1))|) , implying that the number of nonzero allocations k * = |H(Ψ(1))|.
The last line (102c) follows from the recursion (32), thus completing the induction.
Next we consider the case c(t) ≥ c crit , using induction as before. The base case, i.e., the first t such that c(t) ≥ c crit , is either true for t = 1 or follows eventually from the previous induction for c(t) < c crit .
Therefore the expected precision conditioned on |Ψ(1)| is given by using the inductive assumption on c(t) and (32) to complete the proof.
For t large enough such that c(t) ≥ c crit , Lemma 1 applies to provide a further lower bound, The recursion (32) for c(t) implies that Substituting (104) into (103) and recalling that |Ψ(1)| is binomially distributed with parameters Q and p 0 , we obtain APPENDIX V
Given that λ i (t) > 0 for all i ∈ H(Ψ(t − 1)), the per-stage cost for the semi-omniscient policy can be computed from (11) where the inequality follows from (111) and |H(Ψ(t − 1))| = 1 + |G| |Ψ(1)|. As a function of |Ψ(1)|, the right-hand side of (112) has the same form as the function h 0 (z) in the proof of Proposition 1 in Appendix II. Applying the same technique as before and simplifying the resulting expressions, the expectation with respect to |Ψ(1)| can be bounded as The result is obtained from the ratio of (113) and (108).
Substituting this into (111) results in The terms on the right-hand side are of the form ax/(a + x) with a > 0, which is a concave and increasing function of x. Applying Jensen's inequality and the assumption on c(t), we obtain First we show that (38) has three distinct real roots. This is equivalent to the discriminant of (38) being positive. Let a 1 = ∆ 2 /σ 2 and a 2 = |Ψ(1)|/Λ. Noting that (38) lacks a quadratic term, the discriminant can be simplified to D = π 0 a 3 1 4a 3 1 + 12a 2 1 a 2 + (12 − 27π 0 )a 1 a 2 2 + 4a 3 2 .
In the omniscient case π 0 = 1, it is known that (38) has three real roots and hence both D and the quantity in the outer parentheses in (114) are positive. As π 0 decreases from 1, the parenthesized quantity only increases and therefore D > 0 for 0 < π 0 < 1 as well. Now given that (38) has three real roots, it can be seen that one of the roots is positive and the other two are negative. This is because the coefficients of (38) constrain the product of the roots to be positive and their sum to be zero. The positive root can then be expressed in terms of trigonometric functions as c −1 ss = 2 a 1 (a 1 + a 2 ) 3π 0 cos 1 3 arccos 3 √ 3π 0 2 a 2 a 1 + a 2 a 1 a 1 + a 2 .
We now use the assumption that ∆ 2 Λ/σ 2 ≪ 1, implying that a 1 /a 2 ≪ 1, to simplify the expression in (115). First we expand the argument of the arccos function to lowest order in a 1 /a 2 : In the regime ∆ 2 Λ/σ 2 ≪ 1, the positive root of the cubic equation (38) is given by (39) in Lemma 4. We verify that c ss in (39) satisfies c ss ≥ c crit for |Ψ(1)| ≥ 1. Combined with Lemma 3, this will imply that c ss is a stationary upper bound on the steady-state precision c ss . Substituting (39) and (33) for c ss and c crit and neglecting higher-order terms, the condition c ss ≥ c crit is equivalent to π 0 σ 2 |Ψ(1)| ∆ 2 Λ e(π 0 , G) ≥ 1.
The above inequality is most stringent for |Ψ(1)| = 1, in which case it is ensured by assumption (40).
Hence we conclude that c ss ≥ c ss .