Sage Journals: Discover world-class research

Abstract

In networks composed of moving robots or static sensing nodes, multitarget tracking is critical and fundamental for high-level applications, such as scene analysis or event detection. However, tracking multiple targets in the sensor network is challenging for two reasons: multisensor multitarget fusion itself is difficult and dynamic sensor scheduling is necessary to balance the tracking accuracy and energy consumption of the sensor network. In this article, we present a novel information-theoretic sensor selection method for multitarget tracking via the multi-Bernoulli filter. The sensor selection is based on the multi-Bernoulli filtering and a collection of subselection problems for individual target to avoid the combinatorial optimization. A subselection problem for each target is investigated under the framework of partially observed Markov decision process, and we propose to solve it by maximizing the information gain of the probability hypothesis density. Simulation results validate the effectiveness and efficiency of our method for multitarget tracking in sensor networks.

Keywords

Multitarget tracking sensor network information-theoretic sensor selection multi-Bernoulli filter

Introduction

Sensor networks composed of moving robots or static sensing nodes have emerged as an interesting issue in various applications, such as military defense, scene analysis, and so forth.^1
–3 Multisensor multitarget tracking, as one of the most critical low-level techniques, is difficult in twofold: multisensor fusion approach for multitarget tracking is challenging due to data association uncertainty including sensor noise, false alarm, and miss detection⁴; on the other hand, sensor scheduling is required to balance the tracking accuracy and energy consumption of the sensor network.^5,6

Recent advance in random finite set (RFS)-based Bayesian framework has been an unified solution for multisensor multitarget tracking in conjunction with sensor management. It provides the probability hypothesis density (PHD),⁷ cardinalized PHD (CPHD),⁸ and multi-Bernoulli filter that can be easily implemented for multisensor multitarget tracking other than conventional approach joint probabilistic data association and multiple hypothesis tracking. On the other hand, given the multitarget posterior in filter recursion, sensor scheduling for multitarget tracking can be modeled as a partially observed Markov decision process (POMDP)⁹ via finite set statistics (FISST).¹⁰

In the literature, different objective functions were proposed for the POMDP-based sensor management, for example, the Kullback–Leibler discrimination,⁹ posterior expected number of targets,¹¹ the Rényi divergence^,12 and the posterior cardinality.¹³ However, no matter what objective function is used, POMDP-based sensor management is essentially a global combinatorial optimization problem that is extremely challenging especially when the sensor network is quite large, unless only one sensor is selected in use as illustrated in the study by Gostar et al.¹⁴ A spatial nonmaximum suppression heuristics has been proposed recently to alleviate this issue,¹⁵ whereas it suffers from a tuning parameter of the suppress gate. Ma et al.¹⁶ proposed a suboptimal solution of the POMDP-based sensor control which is not suitable for sensor selection problem.

In this article, we consider the efficient sensor selection problem for multitarget tracking in sensor networks. The aim of this article is to select fewer sensors that still guarantee multitarget tracking performance. We adopt the sequential multi-Bernoulli filter as a centralized fusion scheme for multisensor multitarget tracking.¹⁷ An efficient sensor selection approach is proposed via the decomposition of the global POMDP using individual Bernoulli components obtained from multi-Bernoulli filter. We name this framework as the decomposed POMDP. We propose to maximize the information gain between prior and posterior PHD function as an objective function for the decomposed POMDP. Numerical simulation results validate the efficiency and effectiveness of our approach.

The reminder of this article is organized as follows. “Bayesian multisensor multitarget tracking” section includes the multitarget tracking problem formulation in sensor networks, RFS-based Bayesian filtering, and the sequential multi-Bernoulli filter. In “Information-theoretic sensor selection approach” section, we propose the information-theoretic sensor selection approach based on the decomposed POMDP and present sensor selection algorithm in sequential Monte Carlo (SMC) implementation. “Simulation” section provides simulation results that verify the proposed approach.

Bayesian multisensor multitarget tracking

Problem formulation

Our approach addresses the general problem of multitarget tracking in sensor networks. A sensor network is composed of sensors with known locations available to sensing target in its field of view (FoV). All the sensing data need to be transmitted to the fusion center for information fusion in a centralized manner. We assume the sensor network is homogeneous which means that sensors are of the same type.

Without loss of generality, we consider a two-dimensional coordinate tracking scene with range and bearing sensors as a particular interest. Typically, the FoV for a range and bearing sensor is given by [−φ₀, +φ₀] × [0, d₀] in polar coordinate. Figure 1 illustrates the tracking scenario in a range and bearing sensor network with φ₀ = π/2. Notice that our approach can also handle the moving sensors scenario.

Figure 1.

Multitarget tracking in a range and bearing sensor network. Only four sensors can detect targets. Target 1 can be detected by two sensors.

As shown in Figure 1, only a small percentage of sensors can perceive targets while most sensors observe only clutter which is redundant for tracking. To alleviate communication bandwidth and computational cost, sensor selection is essential to choose a sensor subset that provides sufficient and minimal information for tracking purpose.

Assume that target motion model is the nearly constant velocity model¹⁸ given by

x_{k} = F x_{k - 1} + G v_{k}

where $x_{k} = [p_{x, k}, v_{x, k}, p_{y, k}, v_{y, k}]^{T}$ ; $p_{x, k}, p_{y, k}, v_{x, k}, v_{y, k}$ are position and velocity, respectively, along the x, y coordinate. $F = I_{2} \otimes [\begin{matrix} 1 & Δ \\ 0 & 1 \end{matrix}]$ ; $G = I_{2} \otimes [\begin{matrix} Δ^{2} / 2 \\ Δ \end{matrix}]$ . I₂ is 2 × 2 identity matrix, ⊗ is Kronecker product, Δ is the sampling period, and $v_{k} \sim N (0, Q_{k})$ is a 2 × 1 Gaussian noise.

Assume there are m sensors available in the sensor network, target with state x_k generates observation $z_{k}^{l}$ in sensor l(l = 1, ⋯, m) and the measurement model is given by

z_{k}^{l} = h^{l} (x_{k}) + w^{l}

where w^l is zero mean Gaussian noise $N (w^{l}; 0, R^{l})$ and h^l(x_k) is dependent on the position of the lth sensor $s_{l} = {[x_{l} \cdot y_{l}]}^{T}$ and given by

h^{l} (x_{k}) = [\begin{matrix} ‖ p_{k} - s_{l} ‖ \\ arctan \frac{y_{l} - p_{y, k}}{x_{l} - p_{x, k}} \end{matrix}]

where $‖ p_{k} - s_{l} ‖ = \sqrt{{(x_{l} - p_{x, k})}^{2} + {(y_{l} - p_{y, k})}^{2}}$ . Measurement noise w^l is composed of range noise $w_{d}^{l}$ and bearing noise $w_{φ}^{l}$ . The standard derivation of $w_{d}^{l}$ and $w_{φ}^{l}$ are $σ_{d}^{l}$ and $σ_{φ}^{l}$ , respectively, and $R^{l} = diag ([{(σ_{d}^{l})}^{2}, {(σ_{φ}^{l})}^{2}])$ .

RFS-based Bayesian filtering

Recently, the RFS-based Bayesian filtering offers an elegant solution to multitarget tracking that outperforms traditional vector representation. With different assumptions of the RFS form, the PHD, CPHD, and multi-Bernoulli filter are derived and widely used. Here, we give a brief description of the RFS-based Bayesian filtering framework. Let X_k and Z_k denote the multitarget state set and a sensor observation set with cardinalities N_k and W_k, respectively

X_{k} = {x_{k,1}, \dots, x_{k, N_{k}}}

Z_{k} = {z_{k,1}, \dots, z_{k, W_{k}}}

At time k, the prediction of the multitarget state RFS is X_k = S_k ∪ Γ_k, in which S_k is the RFS for persisting targets and Γ_k is the RFS for new born targets. The RFS for current measurements is Z_k = Θ_k ∪ K_k, in which Θ_k is for target-generated measurements and K_k is for clutter, respectively. Then, the RFS-based Bayesian recursion is given as follows

f_{k | k - 1} (X | Z_{1 : k - 1}) = \int f_{k | k - 1} (X | X') f_{k - 1} (X' | Z_{1 : k - 1}) δ X'

f_{k} (X | Z_{1 : k}) = \frac{f_{k} (Z_{k} | X) f_{k | k - 1} (X | Z_{1 : k - 1})}{\int f_{k} (Z_{k} | X) f_{k | k - 1} (X | Z_{1 : k - 1}) δ X}

which represent the prediction and update process. Notice that the RFS-based Bayesian recursion is given by set integrals that solved via FISST¹⁰ and thus results in different filters.

Sequential multi-Bernoulli filter

Assume that each target is modeled as a single Bernoulli set, r^(j) and p^(j) represent the existence probability and distribution of the jth Bernoulli set Ξ^(j), respectively, and then the multitarget state is a multi-Bernoulli RFS $Ξ = \cup_{j = 1}^{M} Ξ^{(j)}$ , where M is the number of the Bernoulli sets. The PHD is propagated recursively in the multi-Bernoulli filter as approximations of the full posterior f(X|Z),¹⁰ which is referred as “density” for short in the following content.

Due to the fact that the multi-Bernoulli filter is favorable for direct multitarget state extraction, we present the sequential multi-Bernoulli filter here as the multisensor fusion approach for multitarget tracking.¹⁷ We first give the original “single-senor version” multi-Bernoulli filter and then present how the “multisensor version” works for better understanding. Remark that the state extraction convenience of the multi-Bernoulli filter is the key to the decomposed POMDP sensor selection in the following content.

Prediction: At time k, given the posterior multitarget density $π_{k} = {(r_{k}^{(j)}, p_{k}^{(j)} {)}}_{j = 1}^{M_{k}}$ , and the new births density $π_{Γ, k + 1} = {(r_{Γ, k + 1}^{(j)}, p_{Γ, k + 1}^{(j)} {)}}_{j = 1}^{M_{Γ, k + 1}}$ , then the predicted density is given by

π_{k + 1 | k} = {(r_{k + 1 | k}^{(j)}, p_{k + 1 | k}^{(j)} {)}}_{j = 1}^{M_{k}} \cup {(r_{Γ, k + 1}^{(j)}, p_{Γ, k + 1}^{(j)})}_{j = 1}^{M_{Γ, k + 1}}

where for survival targets

r_{k + 1 | k}^{(j)} = r_{k}^{(j)} \cdot 〈 p_{k}^{(j)}, p_{S, k} 〉

p_{k + 1 | k}^{(j)} (x) = 〈 f_{k + 1 | k} (x | \cdot), p_{k}^{(j)} p_{S, k} 〉 / 〈 p_{k}^{(j)}, p_{S, k} 〉

and for new born targets, $r_{Γ, k + 1}^{(j)} and p_{Γ, k + 1}^{(j)} (x)$ are prior existence probability and distribution of birth model.

Update: At time k + 1, given the predicted multitarget density $π_{k + 1 | k} = {(r_{k + 1 | k}^{(j)}, p_{k + 1 | k}^{(j)} {)}}_{j = 1}^{M_{k + 1 | k}}$ , then the updated density is composed of legacy tracks and measurement-updated tracks

π_{k + 1} = {(r_{L, k + 1}^{(j)}, p_{L, k + 1}^{(j)} {)}}_{j = 1}^{M_{k + 1 | k}} \cup {(r_{U, k + 1} (z), p_{U, k + 1} (\cdot | z))}_{z \in Z_{k}}

where

r_{L, k + 1}^{(j)} = r_{k + 1 | k}^{(j)} \frac{1 - 〈 p_{k + 1 | k}^{(j)}, p_{D, k + 1} 〉}{1 - r_{k + 1 | k}^{(j)} 〈 p_{k + 1 | k}^{(j)}, p_{D, k + 1} 〉}

p_{L, k + 1}^{(j)} (x) = p_{k + 1 | k}^{(j)} (x) \frac{1 - p_{D, k + 1} (x)}{1 - 〈 p_{k + 1 | k}^{(j)}, p_{D, k + 1} 〉}

r_{U, k + 1} (z) = \frac{\sum_{j = 1}^{M_{k + 1 | k}} \frac{r_{k + 1 | k}^{(j)} (1 - r_{k + 1 | k}^{(j)}) 〈 p_{k + 1 | k}^{(j)}, ψ_{k + 1, z} 〉}{{(1 - r_{k + 1 | k}^{(j)} 〈 p_{k + 1 | k}^{(j)}, p_{D, k + 1} 〉)}^{2}}}{κ_{k + 1} (z) + \sum_{j = 1}^{M_{k + 1 | k}} \frac{r_{k + 1 | k}^{(j)} 〈 p_{k + 1 | k}^{(j)}, ψ_{k + 1, z} 〉}{1 - r_{k + 1 | k}^{(j)} 〈 p_{k + 1 | k}^{(j)}, p_{D, k + 1} 〉}}

p_{U, k + 1} (z) = \frac{\sum_{M_{k + 1 | k}}^{j = 1} \frac{r_{k + 1 | k}^{(j)}}{1 - r_{k + 1 | k}^{(j)}} p_{k + 1 | k}^{(j)} (x) ψ_{k + 1, z} (x)}{\sum_{M_{k + 1 | k}}^{j = 1} \frac{r_{k + 1 | k}^{(j)}}{1 - r_{k + 1 | k}^{(j)}} 〈 p_{k + 1 | k}^{(j)}, ψ_{k + 1, z} 〉}

ψ_{k + 1, z} (x) = g_{k + 1} (z | x) p_{D, k + 1} (x)

p_S(⋅) and p_D(⋅) are probability of target survival and sensor detection, respectively. The inner product 〈⋅, ⋅〉 is defined on two real-valued functions β and γ by $〈 β, γ 〉 = \int β (x) γ (x) d x$ .

Given the “single-senor version” multi-Bernoulli filter, we adopt sequential update fusion as a centralized scheme given in algorithm 1. In the prediction process of the sequential multi-Bernoulli filer, it predicts target state given dynamic model for the first sensor, and for any other sensors, it performs pseudopredict which treats the posterior from pervious time step as the prior right now. Then, the observations from each sensor are applied to update target state recursively. The SMC implementation details can be found in the study by Ma et al.¹⁵ We refer the readers to the study by Ma et al.¹⁷ for other alternative centralized schemes, such as parallel update and random update. Besides, the consensus approach can be applied in a distributed manner.¹⁹

Information-theoretic sensor selection approach

In this section, we first illustrate global sensor selection in the framework of a POMDP in “POMDP-based global sensor selection” section. By incorporating multi-Bernoulli density into the global sensor selection, we propose a decomposed sensor selection approach for multitarget tracking in “Decomposed POMDP” section. “Information-theoretic objective function” section provides maximizing expected Rényi divergence between prior and posterior PHD as the objective function for proposed subselection scheme.

POMDP-based global sensor selection

A POMDP models an agent decision process in which the system dynamics are determined by a Markov decision process, but the agent cannot directly observe the underlying state. The POMDP framework has been used for planning under uncertainty in different applications, especially for robot navigation. Sensor management can be carried out in the framework of a POMDP which includes three key elements¹²:

an information state represented by the multi-object posterior distribution;

an action belonging to a set of admissible actions; and

a reward function associated with different action.

We begin with the notations of using a POMDP as the solution for global sensor selection. At time k, let $S_{k} \in Ω_{k}$ denote selected sensor set, where Ω_k is the set of all possible sensor selection combinations. Define $D (U, f, Z)$ as the objective function dependent on sensor set U, multitarget posterior f, and the associated measurement set Z if sensor set U was applied to selection.

At time k, the aim of sensor selection is to find the sensor subset S_k that maximizes/minimizes the statistical expectation of predefined objective function $D (U, f, Z)$

S_{k} = arg \underset{U \in Ω_{k}}{max (min)} E [D (U, f_{k - 1} (X_{k - 1} | Z_{0 : k - 1}, S_{0 : k - 1}), Z_{k} (U))]

where $f_{k - 1} (X_{k - 1} | Z_{0 : k - 1}, S_{0 : k - 1})$ represents the multitarget posterior after applying sensor selection sequence $S_{0}, \dots, S_{k - 1}$ . Notice that the general formulation of POMDP is a p-step future decision process, whereas, in this article, we only consider a one-step future decision described as equation (17) for convenience.

Even though sensor selection issue can be described as a POMDP given by equation (17), it is still intractable to achieve the global optima of defined objective function since searching all possible sensor combinations is an NP-hard combinatorial optimization problem.^20,21 Several heuristic techniques have been proposed to search for approximation of global optima.^6,22,23 However, these methods are still time-consuming due to the nature of combinatorial searching and consequently difficult to perform real-time sensor selection for tracking. Hence, we propose a decomposed sensor selection method in the following which is computationally tractable and convenient to implement by taking advantage of the multi-Bernoulli filtering.

Decomposed POMDP

As mentioned in “Sequential multi-Bernoulli filter” section, multi-Bernoulli filter propagates multitarget density as approximation of multitarget full posterior to make Bayesian recursion tractable.⁷ Hence, it is reasonable to substitute the multitarget posterior with multitarget density in equation (17), and we obtain

S_{k} = arg \underset{U \in Ω_{k}}{max (min)} E [D (U, π_{k - 1} (X_{k - 1} | Z_{0 : k - 1}, S_{0 : k - 1}), Z_{k} (U))]

where $π_{k - 1} (X_{k - 1} | Z_{0 : k - 1}, S_{0 : k - 1}) = {(r_{k - 1}^{(j)}, p_{k - 1}^{(j)} {)}}_{j = 1}^{M_{k - 1}}$ in multi-Bernoulli filter. Given the multitarget density in multi-Bernoulli filter, we can obtain individual target density $π^{j} = {(r^{(j)}, p^{(j)})}$ from the multitarget density and propose an efficient sensor selection approach based on the decomposed POMDP, that is, select sensors with respect to individual target and then merge into the total selection set given as follows

S_{k}^{(j)} = arg \underset{U \in Ω_{k}}{max (min)} E [D (U, π_{k - 1}^{j} (X_{k - 1} | Z_{0 : k - 1}, S_{0 : k - 1}), Z_{k} (U))]

and

S_{k} = \cup_{j = 1}^{M_{k}} S_{k}^{(j)}

where $π_{k - 1}^{j} (X_{k - 1} | Z_{0 : k - 1}, S_{0 : k - 1}) = {(r_{k - 1}^{(j)}, p_{k - 1}^{(j)})}$ and $S_{k}^{(j)}$ is the selected sensor set with respect to the density of target j. Notice that this decomposition is straightforward since the state extraction is direct in the multi-Bernoulli filter, and this accounts for the choice of the multi-Bernoulli filter.

Remark that the decomposed POMDP-based sensor selection given by equations (19) and (20) selects sensors with respect to subgoals dependent on individual target density instead of a global goal dependent on multitarget density as described in equation (18). However, for any two selection subsets $S_{k}^{(i)}$ and $S_{k}^{(j)}$ (i ≠ j), sensors may be selected repeatedly if targets i and j come across.

To alleviate communication bandwidth and computational cost, $S_{k}^{(j)}$ should contain the minimum number of sensors to track each individual target. In this article, $S_{k}^{(j)}$ is set to be singleton since one range and bearing sensor is adequate to resolve a target. Therefore, the computation complexity of our decomposed sensor selection approach is $O (M \cdot m)$ which is much smaller than $O {(2}^{m})$ by searching all sensor selection combinations in large-scale sensor network. Regarding less informative sensor type that requires q sensors to resolve a target, the computation complexity of the decomposed sensor selection increases to $O (M \cdot (\begin{matrix} m \\ q \end{matrix}))$ with $(\begin{matrix} m \\ q \end{matrix}) = \frac{m!}{q! (m - q)!}$ . Existing searching heuristics⁶ can be applied in searching $S_{k}^{(j)}$ to further reduce the computational cost.

Information-theoretic objective function

As mentioned above, the objective function plays a crucial role in POMDP-based sensor selection problem. Information theoretic method is a typical objective function for sensor scheduling. Here, we propose to maximize the information gain of PHD as the subgoal of decomposed sensor selection, which is the product of existence probability and state distribution given in the study by Mahler¹⁰ as follows

π_{k}^{(j)} = r_{k}^{(j)} \cdot p_{k}^{(j)}

for Bernoulli set ${r_{k}^{(j)}, p_{k}^{(j)}}$ . Notice that the density is the product of a scalar and a probability distribution. The Rényi divergence, also known as alpha divergence, measures the information gain between any two probability densities. Hence, the objective function for target j with respect to sensor l is given as follows

D_{k + 1}^{(j), l} = \frac{r_{k + 1}^{(j), l}}{r_{k + 1 | k}^{(j)}} R^{l} (p_{k + 1}^{(j), l} | | p_{k + 1 | k}^{(j)})

where $R^{l} (p_{k + 1}^{(j), l} | | p_{k + 1 | k}^{(j)})$ is the Rényi divergence between the prior and posterior distribution of target j denoted by $R^{(j), l}$ for short. Given the Bayesian recursion, $R^{(j), l}$ is given in the study by Ristic and Vo¹² as follows

R^{(j), l} = \frac{1}{α - 1} log \frac{\int {[g_{k + 1}^{l} (z | x_{k + 1}^{(j)})]}^{α} p_{k + 1 | k}^{(j)} (x) d x_{k + 1}^{(j)}}{{[p (z | Z_{k})]}^{α}}

where $p (z | Z_{k}) = \int g_{k + 1}^{l} (z | x_{k + 1}^{(j)}) p_{k + 1 | k}^{(j)} (x) d x_{k + 1}^{(j)}$ and α is a parameter that determines how much we emphasize the tails of two density in the metric. The Rényi divergence becomes the Kullback–Leibler discrimination and Hellinger affinity, respectively, when α → 1 and α = 0.5.²⁴ To compute the expectation of equation (22), we only generate one future measurement z for sensor l based on the predicted state assuming no clutter and unity detection rate as illustrated in the study by Gia Hoang and Vo¹³ and $r_{k + 1}^{(j), l} = r_{U, k + 1}^{(j), l} (z)$ for unity detection rate.

To introduce the SMC implementation of the objective function, we assume that at time k, the predicted multitarget density $π_{k + 1 | k} = {r_{k + 1 | k}^{(j)}, p_{k + 1 | k}^{(j)}}_{j = 1}^{M_{k + 1 | k}}$ is given in SMC form where $p_{k + 1 | k}^{(j)} (x) = \sum_{i = 1}^{L_{k + 1 | k}^{(j)}} ω_{i, k + 1 | k}^{(j)} \cdot δ_{x_{i, k + 1 | k}^{(j)}} (x)$ . Substitute SMC form of $p_{k + 1 | k}^{(j)} (x)$ into equation (23), then we obtain

E [D_{k + 1}^{(j), l}] = \frac{r_{U, k + 1}^{(j), l} (z)}{(α - 1) r_{k + 1 | k}^{(j)}} log \frac{\sum_{i = 1}^{L_{k + 1 | k}^{(j)}} ω_{i, k + 1 | k}^{(j)} {[g_{k + 1}^{l} (z | x_{k + 1}^{(j)})]}^{α}}{[\sum_{i = 1}^{L_{k + 1 | k}^{(j)}} ω_{i, k + 1 | k}^{(j)} g_{k + 1}^{l} (z | x_{k + 1}^{(j)} {)]}^{α}}

Remark that equation (24) is the same with the “individual hypothesis information gain” in the study by Ma et al.,¹⁵ whereas the underlying rationale of sensor selection is different. In the study by Ma et al.,¹⁵ noninformative sensors are eliminated by spatial suppression while redundant sensors are selected for update. On the other hand, the decomposed POMDP-based approach only selects minimal number of sensors for tracking. Therefore, the decomposed POMDP-based sensor selection is more general and suitable for large-scale sensor networks.

Assume the sensor network contains m candidate sensors with fixed and known position s^l(l = 1, ⋯, m), then algorithm 2 provides the SMC implementation of sensor selection by maximizing proposed objective function. At each time step, given the prior individual target state, we predict the measurement for each sensor and then compute the expected information gain $E [D_{k + 1}^{(j), l}]$ given by equation (24). Hence, we can select a subset for each individual target that contains more information, then these subsets are merged together to form the overall sensor selection set. The unique() function eliminates repeatedly chosen sensor afterwards in order to ensure each sensor will only be update once during information fusion process.

Simulation

In this section, we present numerical results for a multitarget tracking scenario in sensor networks, in which 9 × 9 sensors laid out uniformly over a square of size (−1000 m, 1000 m) × (−1000 m, 1000 m) divided into 200 × 200 m² blocks. There are unknown and time-varying number of targets observed in clutter while range and bearing measurements from each sensor are available.

The FoV of each node is (−π, 0) × (0, 300 m) with clutter uniformly distributed over this interval. The clutter rate of each sensor node is λ^c = 5 per scan. The probability of detection is modeled by

p_{D}^{l} (x_{k}) = {\begin{matrix} 0.99 & ‖ p_{k} - s_{l} ‖ \leq R_{1} \\ 0.99 - c ‖ p_{k} - s_{l} ‖ & R_{1} < ‖ p_{k} - s_{l} ‖ \leq R_{2} \\ 0 & ‖ p_{k} - s_{l} ‖ > R_{2} \end{matrix}

with R₁ = 100 m, R₂ = 300 m, and c = 0.002 m⁻¹. The covariance of measurement noise for sensor l at time k is $R_{k}^{l} = diag ([(σ_{d, k}^{l})^{2}, (σ_{φ, k}^{l})^{2}])$ , where

σ_{d, k}^{l} = σ_{0} + β_{d} {‖ p_{k} - s_{l} ‖}^{2}

σ_{φ, k}^{l} = σ_{1} + β_{φ} ‖ p_{k} - s_{l} ‖

with σ₀ = 1 m, β_d = 5 × 10⁻⁵ m⁻¹, σ₁ = π/180 rad, and β_φ = 10⁻⁵ rad ⋅ m⁻¹.

Targets can appear or disappear in the scene at any time and survival probability p_S = 0.95 for each existing target. New born targets appear spontaneously according to $γ_{k} = 0.2 N (\cdot; \bar{x}, Q)$ . The tracker, composed of decomposed sensor selection and multisensor multi-Bernoulli filter, runs for 50 scans with sampling period Δ = 1 s. Each target moves according to the constant velocity model given by equation (1). The standard derivation of process noise is σ_v = 1 m/s for both v_x,k and v_y,k. Three targets are presented as illustrated in Figure 2. The coverage of the sensor network is shown in Figure 3.

Figure 2.

Target tracks. Start/stop positions for each track are shown with •/+.

Figure 3.

The yellow area represents the FoV of each sensing node. FoV: field of view.

Birth parameters for the multi-Bernoulli filter are prior locations with ${\bar{x}}_{1} = [200 m; - 10 m/s; 600 m; - 20 m/s]^{T}$ , ${\bar{x}}_{2} = [- 300 m; 15 m/s; 200 m; - 10 m/s]^{T}$ , and ${\bar{x}}_{3} = [- 850 m; 25 m/s; - 450 m; 5 m/s]^{T}$ , respectively, for each location, and Q = diag([(50 m, 2 m/s, 50 m, 2 m/s)]²) is identical for all three locations. L_min = 300 and L_max = 500 are the minimum and maximum particle number of each Bernoulli set for track maintenance.

We first illustrate the decomposed sensor selection and multisensor multitarget tracking procedure. Three consecutive tracking frames in one run are presented in Figure 4. All three figures contain more than three sensors selected while there are only three real targets. This is because, in multi-Bernoulli filter sets, Bernoulli filter sets for existing targets only occupies part of all Bernoulli sets. There are birth sets for new born targets and legacy sets for temporally undetected targets as well. As shown in Figure 4, there are always selected sensors standing by for birth sets. Besides, the legacy sets account for that the multi-Bernoulli filter lost target 1 in Figure 4(b) and picked it up later as shown in Figure 4(c).

Figure 4.

Consecutive tracking frames. Blue and red dots, respectively, stand for sensors that targets fall off and in sensor’s FoV, blue line and ∘ for target track and current position, W for selected sensor, and red ∗ for target estimation. FoV: field of view. (a) Time k = 22. (b) Time k = 23. (c) Time k = 24.

Since the nearest neighboring strategy has been widely used in sensor selection, we implement minimum expected distance as another objective function for comparison. Moreover, we also compare the two spatial nonmaximum suppression selection method described in the study by Ma et al.¹⁵ with gate ε = 500 m, referred as “sum HIG” suppression and “individual HIG” suppression, respectively. It is intuitive for this scenario that to select the proper sensor with respect to a target should choose the nearest sensor that target falls in its FoV.

The optimal subpattern assignment (OSPA) metric, composed of location error and cardinality error, is adopted for multitarget tracking performance evaluation.²⁵ The OSPA metric can be computed efficiently using the Hungarian method for optimal point assignment between two point patterns. We refer the readers of “Information-theoretic sensor selection approach” section in the study by Schuhmacher et al.²⁵ for equations and parameter explanations of the OSPA metric.

Figure 5 shows the OSPA distance (c = 300 m, p = 1) comparison from 500 Monte Carlo runs. It is obvious that the proposed tracker with maximizing the expected information gain of PHD has similar performance with “individual HIG” suppression approach, which outweighs nearest neighboring strategy and “sum HIG” suppression. Our decomposed selection with maximizing the PHD can choose proper sensors to perform effective multitarget tracking. However, the nearest neighboring strategy ignores sensor’s FoV and may choose sensors cannot observe targets instead. With respect to the suppression method, the performance of both “sum HIG” and “individual HIG” relies on the tuning of parameter gate ε. In this case, ε = 500 m makes the “sum HIG” suppression cannot select enough sensors and leads to inferior tracking performance.

Figure 5.

Comparison of OSPA distance. OSPA: optimal subpattern assignment.

The comparison concerning total particle number and computation time from 500 Monte Carlo runs is demonstrated in Figure 6. Both trackers were implemented in MATLAB R2012a on a computer with an Intel Core E5500 CPU and 2 GB of RAM. It is clear that the computation time of both trackers is acceptable for an actual fusion center to perform centralized multisensor multitarget tracking in real time. Nevertheless, the “individual HIG” suppression method with ε = 500 m is slower since redundant sensors are selected in use for multisensor sequential update. The sample size of nearest neighboring strategy and “sum HIG” suppression is much larger because “ghost” particles are maintained in multisensor multi-Bernoulli filter when sensors that cannot observe targets are selected frequently. On the other hand, maximizing the PHD and “individual HIG” suppression can eliminate “ghost” particles quickly by selecting proper sensors.

Figure 6.

Comparison of sample size and computation time.

To summarize, suppression gate ε is critical for the suppression selection method. If the suppression gate ε is not set properly, the spatial nonmaximum suppression selection method may leads to very poor tracking performance or selecting too much sensors. On the other hand, the proposed information-theoretic sensor selection approach based on decomposed POMDP can provide sufficient and minimal information for multitarget tracking.

Conclusion

This article outlines a novel suboptimal sensor selection approach for individual target to avoid combinatorial search over all sensor combinations by global POMDP decomposition. The multisensor multitarget tracking is performed using the sequential multi-Bernoulli filter in SMC implementation. The implementation of proposed decomposed sensor selection is based on maximizing the information gain of the PHD. Simulation results demonstrate that the proposed approach is capable of effective multitarget tracking via efficient sensor selection.

There are some potential extensions of this work. For example, the performance of our approach needs to be further evaluated compared with searching for global optima method, which requires further research on heuristic searching techniques. Besides, for practical sensor network that is composed of heterogeneous sensors of different types, the selection $S_{k}^{(j)}$ for each target should be dynamically determined with respect to available sensor type.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflict of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is sponsored by the National Natural Science Foundation of China (No. 51405096) and the Fundamental Research Funds for the Central Universities (HEUCF130703).

References

Yick

Mukherjee

Ghosal

. Wireless sensor network survey. Comput Netw 2008; 52(12): 2292–2330.

Farmani

Sun

Pack

. Optimal UAV sensor management and path planning for tracking multiple mobile targets. In: ASME 2014 dynamic systems and control conference, San Antonio, TX, USA, 22–24 October 2014, pp. 1–8.

Sun

Baek

Pack

. Distributed probabilistic search and tracking of agile mobile ground targets using a network of unmanned aerial vehicles. Switzerland: Springer International Publishing, 2014, pp. 301–319.

Khaleghi

Khamis

Karray

. Multisensor data fusion: a review of the state-of-the-art. Inf Fusion 2013; 14(1): 28–44.

Tharmarasa

Kirubarajan

Hernandez

. Large-scale optimal sensor array management for multitarget tracking. IEEE Trans Syst Man Cybern C 2007; 37(5): 803–814.

Joshi

Boyd

. Sensor selection via convex optimization. IEEE Trans Signal Process 2009; 57(2): 451–462.

Mahler

. Multitarget Bayes filtering via first-order multitarget moments. IEEE Trans Aerosp Electron Syst 2003; 39(4): 1152–1178.

Mahler

. PHD filters of higher order in target number. IEEE Trans Aerosp Electron Syst 2007; 43(4): 1523–1543.

Mahler

. Global posterior densities for sensor management. In: Aerospace/defense sensing and controls. Proceedings of the international society for optics and photonics, Orlando, Florida, USA, April 1998, pp. 252–263.

10.

Mahler

. Statistical multisource-multitarget information fusion, vol. 685. Norwood, MA: Artech House, Inc., 2007.

11.

Mahler

Multitarget sensor management of dispersed mobile sensors. In: Grundel

Murphey

Pardalos

(eds) Theory and algorithm for cooperative systems. River Edge, NJ, USA, 2004, pp. 239–310.

12.

Ristic

. Sensor control for multi-object state-space estimation using random finite sets. Automatica 2010; 46(11): 1812–1818.

13.

Gia Hoang

. Sensor management for multi-target tracking via multi-Bernoulli filtering. Automatica 2013; 50(4): 1135–1142.

14.

Gostar

Hoseinnezhad

Bab-Hadiashar

. Robust multi-Bernoulli sensor selection for multi-target tracking in sensor networks. IEEE Signal Process Lett 2013; 20(12): 1167–1170.

15.

Xue

Wang

. Multitarget tracking with spatial nonmaximum suppressed sensor selection. Math Probl Eng 2014; 2015(Article ID 148081): 1–10.

16.

Xue

Wang

. Distributed multiagent control approach for multitarget tracking. Math Probl Eng 2014; 2015;(Article ID 903682): 1–10.

17.

Kim

DY,

and Xue

Kai

. Multi-Bernoulli filter for target tracking with multi-static Doppler only measurement. Signal Processing, 108:102–110, 2015.

18.

BN,

Cantoni

. The cardinality balanced multi-target multi-Bernoulli filter and its implementations. IEEE Trans Signal Process 2009; 57(2): 409–423.

19.

Battistelli

Chisci

Fantacci

. Consensus CPHD filter for distributed multitarget tracking. IEEE J Sel Topics Signal Process 2013; 7(3): 508–520.

20.

Yoo

Lafortune

. NP-completeness of sensor selection problems arising in partially observed discrete-event systems. IEEE Trans Autom Control 2002; 47(9): 1495–1499.

21.

Bian

Kempe

Govindan

. Utility based sensor selection. In: Proceedings of the 5th international conference on Information processing in sensor networks, Nashville, Tennessee, USA, 19–21 April 2006, pp. 11–18. New York, NY: ACM.

22.

Nguyen

Miller

. A review of some exchange algorithms for constructing discrete d-optimal designs. Comput Stat Data Anal 1992; 14(4): 489–498.

23.

Yao

Sethares

WA,

Kammer

. Sensor placement for on-orbit modal identification via a genetic algorithm. AIAA J 1993; 31(10): 1922–1928.

24.

Hero

III AO

Kreucher

CM,

Blatt

. Information theoretic approaches to sensor management. In: Hero

III AO

Castañón

Cochran

Kastella

(eds) Foundations and Applications of Sensor Management. Springer US, 2008, pp. 35–57.

25.

Schuhmacher

BT,

. A consistent metric for performance evaluation of multi-object filters. IEEE Trans Signal Process 2008; 56(8): 3447–3457.

Multitarget tracking in sensor networks via efficient information-theoretic sensor selection

Abstract

Keywords

Introduction

Bayesian multisensor multitarget tracking

Problem formulation

RFS-based Bayesian filtering

Sequential multi-Bernoulli filter

Information-theoretic sensor selection approach

POMDP-based global sensor selection

Decomposed POMDP

Information-theoretic objective function

Simulation

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References