This paper describes a decentralized low communication approach to multi-platform sensor management. The
method is based on a physicomimetic relaxation to a joint information theoretic optimization, which inherits the
benefits of information theoretic scheduling while maintaining tractability. The method uses only limited message
passing, only neighboring nodes communicate, and each node makes its own sensor management decisions.
We show by simulation that the method allows a network of sensor nodes to automatically self organize
and perform a global task. In the model problem, a group of unmanned aerial vehicles (UAVs) hover above a
ground surveillance region. An initially unknown number of moving ground targets inhabit the region. Each
UAV is capable of making noisy measurements of the patch of ground directly below, which provide evidence as
to the presence or absence of targets in that sub-region. The goal of the network is to determine the number of
targets and their individual states (positions and velocities) in the entire surveillance region through repeated
interrogation by the individual nodes. As the individual nodes can only see a small portion of the ground, they
must move in a manner that is both responsive to measurements and coordinated with other nodes.
Factors affecting the performance of an algorithm for tracking multiple targets observed using a pixelized sensor are studied. A pixelized sensor divides the surveillance region into a grid of cells with targets generating returns on the grid according to some known probabilistic model. In previous work an efficient particle filtering algorithm was developed for multiple target tracking using such a sensor. This algorithm is the focus of the study. The performance of the algorithm is affected by several considerations. The pixelized sensor model can be used with either thresholded or non-thresholded measurements. While it is known that information is lost when measurements are thresholded, quantitative results have not been established. The development of a tractable algorithm requires that closely-spaced targets are processed jointly while targets which are far apart are processed separately. Selection of the clustering distance involves a trade-off between performance and computational expense. A final issue concerns the computation of the proposal density used in the particle filter. Variations in a certain parameter enable a trade-off between performance and computational expense. The various issues are studied using a mixture of theoretical results and Monte Carlo simulations.
This paper shows how information-directed diffusion can be used to manage the trajectories of hundreds of smart mobile sensors. This is an artificial physics method in which the sensors move stochastically in response to an information gradient and artificial inter-sensor forces that serve to coordinate their actions.
Measurements received by the sensors are centrally fused using a particle filter to estimate the Joint Multitarget Probability Density (JMPD) for the surveillance volume. The JMPD is used to construct an information surface which gives the expected gain for sensor dwells as a function of position. The updated sensor position is obtained by moving it in response to artificial forces derived from the information surface, which acts as a potential, and inter-sensor forces derived from a Lennard-Jones-like potential. The combination of information gradient and inter-sensor forces work to move the sensors to areas of high information gain while simultaneously ensuring sufficient spacing between the sensors. We evaluate the performance of this approach using a simulation study for an idealized Micro Air Vehicle with a simple EO detector and collected target trajectories. We find that this method provides a factor of 5 to 10 improvement in performance when compared to random uncoordinated search.
We present in this paper an information based method for sensor management that is based on tasking a sensor to make the measurement that maximizes the <i>expected</i> gain in information. The method is applied to the problem of tracking multiple targets. The underlying tracking methodology is a multiple target tracking scheme based
on recursive estimation of a Joint Multitarget Probability Density (JMPD), which is implemented using particle ﬁltering methods. This Bayesian method for tracking multiple targets allows nonlinear, non-Gaussian target motion and measurement-to-state coupling. The sensor management scheme is predicated on maximizing the expected Renyi Information Divergence between the current JMPD and the JMPD after a measurement has been made. The Renyi Information Divergence, a generalization of the Kullback-Leibler Distance, provides a way to measure the dissimilarity between two densities. We use the Renyi Information Divergence to evaluate the expected information gain for each of the possible measurement decisions, and select the measurement that maximizes the expected information gain for each sample.
This paper addresses the problem of tracking multiple moving targets by estimating their joint multitarget probability density (JMPD). The JMPD technique is a Bayesian method for tracking multiple targets that allows nonlinear, non-Gaussian target motions and measurement to state coupling. JMPD simultaneously estimates both the target states and the number of targets. In this paper, we give a new grid-free implementation of JMPD based on particle filtering techniques and explore several particle proposal strategies, resampling techniques, and particle diversification methods. We report the effect of these techniques on tracker performance in terms of tracks lost, mean squared error, and computational burden.
This paper analyzes the impact on target detection of several alternative sensor management schemes. Past work in this area has shown that myopic discrimination optimization can be a useful heuristic. In this paper we compare the performance obtained using discrimination with direct optimization of the detection error rate using both myopic and non-myopic optimization techniques. Our model consists of a gridded region containing a set of targets with known priors. Each grid location contains at most one target. At each time step, the sensor can sample a grid location, returning sample values that may or may not be thresholded. The sensor output distribution conditioned on the content of the location is known. Bayesian methods are used to recursively update the posterior probability that each location contains a target. These probabilities can then in turn be used to classify each location as either containing a target or not. At each time step, sensor management is used to determine which location to test next. For non-myopic optimization, graph search techniques are used. When the sensor output is thresholded, the performance obtained using myopic optimization of the expected error rate is worse then that obtained using our other three approaches. Interestingly, we find that for non-thresholded measurements on symmetric distributions, the performance is the same for the four cases tested (myopic/non-myopic discrimination gain/expected error rate). This supports that discrimination is a useful heuristic that provides near-optimal performance under the given assumptions.
This paper describes the design and implementation of multiple model nonlinear filters (MMNLF) for ground target tracking using Ground Moving Target Indicator (GMTI) radar measurements. The MMNLF is based on a general theory of hybrid continuous-discrete dynamics. The motion model state is discrete and its stochastic dynamics are a continuous- time Markov chain. For each motion model, the continuum dynamics are a continuous-state Markov process described here by appropriate Fokker-Plank equations. This is illustrated here by a specific two-model MMNLF in which one motion model incorporates terrain, road, and vehicle motion constraints derived from battlefield observations. The second model is slow diffusion in speed and heading. The target state conditional probability density is discretized on a moving grid and recursively updated with sensor measurements via Bayes' formula. The conditional density is time updated between sensor measurements using Alternating Direction Implicit (ADI) finite difference methods. In simulation testing against low signal to clutter + noise Ratio (SNCR) targets, the MMNLF is able to maintain track in situations where single model filters based on either of the component models fail. Potential applications of this work include detection and tracking of foliage-obscured moving targets.
Previous nonlinear filtering research has shown that by directly estimating the probability density of the target state, weak and closely spaced targets can be tracked without performing data association. Data association imposes a heavy burden, both in its design where complex data management structures are required and in its execution which often requires many computer cycles. Therefore, avoiding data association can have advantages. However, some have suggested that data association is required to estimate and correct sensor biases that are nearly always present so avoiding it is not a practical option. This paper demonstrates that target numbers, target tracks, and sensor biases can all be estimated simultaneously using association-free nonlinear methods, thereby extending the useful range of these methods while preserving their inherent advantages.
This paper describes a nonlinear filter for ground target tracking. Hospitability for maneuver derived from terrain, road and vehicle dynamics constraints is incorporated directly into the filter's motion model. The conditional probability density for the target state is maintained and updated with sensor measurements as soon as they become available. The conditional density is time updated between sensor measurements using finite difference methods. In simulations using square-law detected measurements the filter is able to track maneuvering ground targets when the Signal to Interference + Noise Ratio (SINR) os between 6 and 9 dB.
Monopulse radar tracking of target elevation for objects flying close to a reflecting surface is difficult due to interference between the direct echo and surface-reflected target echoes. Ideally, target height could be estimated directly from the probability density for monopulse measurements given target range and height. This direct approach is usually unfeasible because the density generally has many false peaks so there are multiple solutions for target height. This paper describes a nonlinear filter that exploits this behavior to estimate target height. The filter recursively computes the probability density for height and vertical velocity conditioned on the monopulse measurement sequence. The time evolution of this density between measurements is determined by a Fokker-Planck partial differential equation. This is solved in real-time using a finite difference scheme. The monopulse measurement probability density is computed from a physical model and used to update the conditional target state density using Bayes' rule. In simulation testing for a generic C-band shipboard radar the filter is able to reliably acquire and track transonic targets through mild maneuvers with about 12 m root-mean-square height accuracy.
This paper describes an algorithm using a discrimination- based sensor effectiveness metric for sensor assignment in multisensor multitarget tracking applications. The algorithm uses interacting multiple model Kalman filters to track airborne targets with measurements obtained from two or more agile-beam radar systems. Each radar has capacity constraints on the number of targets it can observe on each scan. For each scan the expected discrimination gain is computed for the sensor target pairings. The constrained globally optimum assignment of sensor to targets is then computed and applied. This is compared to a fixed assignment schedule in simulation testing. We find that discrimination based assignment improves track accuracy as measured by both the root-mean-square position error and a measure of the total covariance.
A Joint Multitarget Probability (JMP) is a posterior probability density p<SUB>T</SUB>(x<SUB>1</SUB>,...,x<SUB>T</SUB>Z) that there are T targets (T an unknown number) with unknown locations specified by the multitarget state X equals (x<SUB>1</SUB>,...,x<SUB>T</SUB>)<SUP>T</SUP> conditioned on a set of observations Z. This paper presents a numerical approximation for implementing JMP in detection, tracking and sensor management applications. A problem with direct implementation of JMP is that, if each x<SUB>t</SUB>, t equals 1,...,T, is discretized on a grid of N elements, N<SUP>T</SUP> variables are required to represent JMP on the T-target sector. This produces a large computational requirement even for small values of N and T. However, when the sensor easily separates targets, the resulting JMP factorizes and can be approximated by a product representation requiring only O(T<SUP>2</SUP>N) variables. Implementation of JMP for multitarget tracking requires a Bayes' rule step for measurement update and a Markov transition step for time update. If the measuring sensor is only influenced by the cell it observes, the JMP product representation is preserved under measurement update. However, the product form is not quite preserved by the Markov time update, but can be restored using a minimum discrimination approach. All steps for the approximation can be performed with O(N) effort. This notion is developed and demonstrated in numerical examples with at most two targets in a 1-dimensional surveillance region. In this case, numerical results for detection and tracking for the product approximation and the full JMP are very similar.
This paper presents an approach to detection, tracking, classification and sensor management based on recursive evaluation of a joint multitarget probability. This joint multitarget probability is the conditional probability p<SUB>c(subscript 1</SUB><SUP>n</SUP>,...,c<SUB>n</SUB>(x<SUB>1</SUB>,...,x<SUB>n</SUB>/Z) that there are exactly n targets of class c<SUB>1</SUB>,...,c<SUB>n</SUB> located in cells x<SUB>1</SUB>,...,x<SUB>n</SUB> based on a set of observations Z. This is applied to the problem of estimating the state of a collection of targets moving between discrete cells on a line. A cell can contain more than one target. For the model problem, there are two target classes and the number of targets is not known a priori. The targets are modeled as moving independently with Markov transitions to nearest- neighbor cells. There is one sensor with two modes that can only be used one at a time. These are: a detection mode which can determine whether a cell contains targets but provides no information about target class; and a classification mode that provides little information about the presence or absence of targets but can differentiate between the target classes. For each sensor dwell, the sensor samples a single cell. The conditional probability p<SUB>m</SUB><SUP>n</SUP>,c<SUB>1</SUB>,...,c<SUB>n</SUB>(z/x<SUB>1</SUB>,...,x<SUB>n</SUB>) for sensor output z when mode m is used, given the target location and classes is known. Bayes' rule is applied directly to update the multitarget density for each output. As a basis for sensor management, the expected discrimination gain when a cell is sampled with a particular sensor can be computed. The sensor and cell to maximize the expected gain for each dwell can then be selected. In comparison to directly sampling all of the cells, optimizing the discrimination significantly increases the probability of detecting and localizing the targets.
Several sensor management schemes based on information theoretic metrics such as discrimination gain have been proposed, motivated by the generality of such schemes and their ability to accommodate mixed types of information such as kinematic and classification data. On the other hand, there are many methods for managing a single sensor to optimize detection. This paper compares the performance against low signal-noise ratio targets of a discrimination gain scheme with three such single sensor detection schemes: the Wald test, an index policy that is optimal under certain circumstances and an 'alert-confirm' scheme modeled on methods used in some existing radars. For the situation where the index policy is optimal, it outperforms discrimination gain by a slight margin. However, the index policy assumes that there is only one target present. It performs poorly when there are multiple targets while discrimination gain and the Wald test continue to perform well. In addition, we show how discrimination gain can be extended to multisensor/multitarget detection and classification problems that are difficult for these other methods. One issue that arises with the use of discrimination gain as a metric is that it depends on both the current density and an a priori distribution. We examine the dependence of discrimination gain on this prior and find that while the discrimination depends on the prior, the gain is prior-independent.
A method for managing agile sensors to optimize detection and classification based on discrimination gain is presented. Expected discrimination gain is used to determine threshold settings and search order for a collection of discrete detection cells. This is applied in a low signal-to-noise environment where target-containing cells must be sampled many times before a target can be detected or classified with high confidence. Bayes rule is used to compute the expected discrimination gain for each sample region using estimated probability that it contains a target. This gain is used to select the optimal cell for the next sample. The effectiveness of this approach was assessed in a simple test case by comparing the result of discrimination optimized search with direct search. For a single 0 dB Gaussian target, the error rate for discrimination optimized search was similar to the direct search result against a 6 dB target.
This paper briefly reviews the development of the mean-field event-averaged maximum likelihood estimation (MFEAMLE) tracker and compares its tracking performance with that of a joint probabilistic data association (JPDA) filter. The JPDA and MFEAMLE approaches are similar in that they both average over measurement to track associations. However, there are several features of MFEAMLE that improve its estimation performance at high target and clutter densities while simplifying the required computation enough to make real-time performance feasible. To enhance tracking of close targets, the filter explicitly models the error correlations that occur between such target pairs, rather than assuming that they are independent. These error correlations arise from the measurement to track association ambiguity present when target separations are comparable to the measurement errors in the sensors. In order to reduce the computational load, a mean-field approximation is used to perform the summation over all associations. In performance comparison on simulated data, smaller average errors and less track loss were obtained for the MFEAMLE tracker than with JPDA.
Proc. SPIE. 2561, Signal and Data Processing of Small Targets 1995
KEYWORDS: Target detection, Detection and tracking algorithms, Error analysis, Computing systems, Telecommunications, Signal processing, Palladium, Algorithm development, Signal detection, Probability theory
This article characterizes asymptotic limits for the error probabilities that arise while testing for the detection of targets in the presence of clutter. The hypothesis test decision regions are determined by the discrimination function. The function is the basic measure of the information contained in the measurements. While the Neyman-Pearson Theorem specifies the optimum decision regions, it does not specify the detection performance in terms of the error probabilities. Asymptotic bounds expressed as analytical functions allows us to determine the effect of the decision threshold, the clutter density, and the number of measurements on the error probabilities; thus indicating the effectiveness of the testing procedure.
This paper presents a novel Kalman filter for track maintenance in multitarget tracking using thresholded sensor data at high target/clutter densities and low detection levels. The filter is robust against tracking errors induced by crossing tracks, clutter and missed detections and the computational complexity of the filter scales well with problem size. There are two key features that differentiate this approach from earlier work. First, in order to enhance tracking of close tracks, the filter explicitly models the error correlations that occur between such target pairs. These error correlations arise due to the measurement to track association ambiguity present when target separations are comparable to the measurement errors in the sensors. Second, in order to reduce the computational load, the filter exploits techniques from statistical field theory to simplify the combinatorial complexity of measurement to track association. This is accomplished by developing a mean-field approximation to the summation over all associations.
This paper present an information-theoretic approach to sensor management for multitarget tracking using a sensor that operates in one of two modes: a fast, low-resolution mode and a slow, high-resolution mode. The error correlations between nearby target pairs, the sensor rates, the sensor resolutions and the target plant noise all play a role in the optimum choice of mode. The error correlations occur in the target location estimates even when the individual measurement errors are uncorrelated, as in the model considered here. When a filter that models these error correlations is used, such as event-averaged maximum likelihood estimation, a sensor management strategy can be developed to reduce them. This is illustrated with a model two- target problem. In the model problem, the target plant noise is such that the low resolution mode produces the optimum result when the targets are widely separated, due to its higher report rate. If the error correlations are not modeled, then over a certain parameter range the low resolution mode would be selected for all target separations. When the effect of error correlations is included, it is shown the slow, high resolution mode produces a better result when the targets are close together. This suggests that systems that must track closely spaced targets could benefit from adaptively adjusting their integration times based on target plant noise and separation.
Proc. SPIE. 1954, Signal and Data Processing of Small Targets 1993
KEYWORDS: Statistical analysis, Detection and tracking algorithms, Data modeling, Sensors, Digital filtering, Error analysis, Personal digital assistants, Solids, Electronic filtering, Filtering (signal processing)
A widely used estimator for multi-target tracking, conventionally referred to as a maximum likelihood estimator, is analyzed. For the problem of locating closely spaced fixed, untagged objects using a noiseless sensor, the conventional estimator's mean and variance estimates are inconsistent, i.e. asymptotically biased. We propose an alternative maximum likelihood estimator that corrects this problem. This estimator uses a coherent sum over report to track associations to evaluate the track likelihood function. The resulting estimator is efficient in the sense that it achieves the Cramer-Rao lower bound (CRLB) on the variance asymptotically. A novel feature of this approach is that it entails estimation of track error correlations in addition to the variance estimates generated in the usual Kalman filter based methods. These motions are used to develop a filter for a pair of uncorrelated Brownian walkers. It successfully estimates the error correlations that must be present in an optimal filter.