Tracker and signal processing for the benchmark problem with unresolved targets

Radar signal processing is particularly important in tracking closely spaced targets and targets in the presence of sea-surface-induced multipath. Closely spaced targets can produce unresolved measurements when they occupy the same range cell of the radar. These issues are the salient features of the benchmark problem for tracking unresolved targets combined with radar management, for which this paper presents the only complete solution to date. In this paper a modified version of a recently developed maximum likelihood (ML) angle estimator, which can produce two measurements from a single (unresolved) detection, is presented. A modified generalized likelihood ratio test (GLRT) is also described to detect the presence of two unresolved targets. Sea-surface-induced multipath can produce a severe bias in the elevation angle measurement when the conventional monopulse ratio angle extractor method is used. A modified version of a recently developed ML angle extractor, which produces nearly unbiased elevation angle measurements and significantly improves the track accuracy, is presented. Efficient radar resource allocation algorithms for two closely spaced targets and targets flying close to the sea surface are also presented. Finally, the IMMPDAF (interacting multiple model estimator with probabilistic data association filter modules) is used to track these targets. It is found that a two-model IMMPDAF performs better than the three-model version used in the previous benchmark. Also, the IMMPDAF with a coordinated turn model works better than the one using a Wiener process acceleration model. The signal processing and tracking algorithms presented here, operating in a feedback manner, form a comprehensive solution to the most realistic tracking and radar management problem to date.     

Bayesian tracking of two possibly unresolved maneuvering targets

The paper studies the problem of maintaining tracks of two targets that may maneuver in and out formation flight, whereas the sensor and measurement extraction chain produces false and possibly unresolved or missing measurements. If the possibility of unresolved measurements is not modelled then it is quite likely that either the two tracks coalesce or that one of the two tracks diverges on false measurements. In literature a robust measurement resolution model has been incorporated within an interacting multiple model/multiple hypothesis tracking (IMM/MHT) track maintenance setting. A straightforward incorporation of the same model within an IMM and probabilistic data association (PDA)-like hypothesis merging approach suffers from track coalescence. In order to improve this situation, the paper develops a track-coalescence avoiding hypotheses merging version for the two target problem considered. Through Monte Carlo simulations, the novel filters are compared with applying hypotheses merging approaches that ignore the possibility of unresolved measurements or track-coalescence.     

Data association for deghosting in Y-shaped passive linear array sonars

This paper deals with data association using three sets of passive linear array sonars (PLAS) geometrically positioned in a Y-shaped configuration, fixed in an underwater environment. The data association problem is directly transformed into a 3D assignment, which is known to be NP hard. For generic passive sensors, it can be solved using conventional algorithms, while in PLAS, it becomes a formidable task due to the presence of bearing ambiguity. Thus, the central issue of the problem in PLAS is how to eliminate the bearing ambiguity without increasing tracking error. To solve this problem, the 3D assignment algorithm used the likelihood value of only those observed bearing measurements is modified by incorporating frequency information in consecutive time-aligned scans. The region of possible ghost targets is first established by the geometrical relation of PLAS with respect to target. The ghost targets are then confirmed and eliminated by generating multiple observations in consecutive scans. Representative simulations demonstrate the effectiveness of the proposed approach.     

Monopulse DOA estimation of two unresolved Rayleigh targets

This paper provides for new approaches to the processing of unresolved measurements as two direction-of-arrival (DOA) measurements for tracking closely spaced targets rather than the conventional single DOA measurement of the centroid. The measurements of the two-closely spaced targets are merged when the target echoes are not resolved in angle, range, or radial velocity (i.e., Doppler processing). The conditional Cramer Rao lower bound (CRLB) is developed for the DOA estimation of two unresolved Rayleigh targets using a standard monopulse radar. Then the modified CRLB is used to give insight into the boresight pointing for monopulse DOA estimation of two unresolved targets. Monopulse processing is considered for DOA estimation of two unresolved Rayleigh targets with known or estimated relative radar cross section (RCS). The performance of the DOA estimator is studied via Monte Carlo simulations and compared with the modified CRLB     

On joint track initiation and parameter estimation under measurement origin uncertainty

The problem of joint detection and estimation for track initiation under measurement origin uncertainty is studied. The two well-known approaches, namely the maximum likelihood estimator with probabilistic data association (ML-PDA) and the multiple hypotheses tracking (MHT) via multiframe assignment, are characterized as special cases of the generalized likelihood ratio test (GLRT) and their performance limits indicated. A new detection scheme based on the optimal gating is proposed and the associated parameter estimation scheme modified within the ML-PDA framework. A simplified example shows the effectiveness of the new algorithm in detection performance under heavy clutter. Extension of the results to state estimation with measurement origin uncertainty is also discussed with emphasis on joint detection and recursive state estimation.     

Tracking multiple objects with particle filtering

We address the problem of multitarget tracking (MTT) encountered in many situations in signal or image processing. We consider stochastic dynamic systems detected by observation processes. The difficulty lies in the fact that the estimation of the states requires the assignment of the observations to the multiple targets. We propose an extension of the classical particle filter where the stochastic vector of assignment is estimated by a Gibbs sampler. This algorithm is used to estimate the trajectories of multiple targets from their noisy bearings, thus showing its ability to solve the data association problem. Moreover this algorithm is easily extended to multireceiver observations where the receivers can produce measurements of various nature with different frequencies.     

Suboptimal joint probabilistic data association

A significant problem in multiple target tracking is the hit-to-track data association. A hit is a received signal from a target or background clutter which provides positional information. If an incorrect hit is associated with a track, that track could diverge and terminate. Prior methods for this data association problem include various optimal and suboptimal two-dimensional assignment algorithms which make hit-to-track associations. Another method is to assign a weight for the reasonable hits and use a weighted centroid of those hits to update the track. The method of weighting the hits is known as joint probabilistic data association (JPDA). The authors review the JPDA approach and a simple ad hoc approximation and then introduce a new suboptimal JPDA algorithm. Examples which compare an optimal two-dimensional assignment algorithm with the ad hoc and the new suboptimal JPDA formulation are given     

A class of near optimal JPDA algorithms

The crucial problem in multiple target tracking is the hit-to-track data association. A hit is a received signal from a target or background clutter which provides positional information If an incorrect hit is associated with a track, that track could diverge and prematurely terminate or cause other tracks to also diverge. Most methods for hit-to-track data association fall into two categories: multiple hypothesis tracking (MHT) and joint probabilistic data association (JPDA). Versions of MHT use all or some reasonable hits to update a track and delay the decision on which hit was correct. JPDA uses a weighted sum of the reasonable hits to update a track. These weights are the probability that the hit originated from the target in track. The computational load for the joint probabilities increases exponentially as the number of targets increases and therefore, is not an attractive algorithm when expecting to track many targets. Reviewed here is the JPDA filter and two simple approximations of the joint probabilities which increase linearly in computational load as the number of targets increase. Then a new class of near optimal JPDA algorithms is introduced which run in polynomial time. The power of the polynomial is an input to the algorithm. This algorithm bridges the gap in computational load and accuracy between the very fast simple approximations and the efficient optimal algorithms     

Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes

The task assignment problem of multiple heterogeneous unmanned aerial vehicles （UAVs）, concerned with cooperative decision making and control, is studied in this paper. The heterogeneous vehicles have different operational capabilities and kinematic constraints, and carry limited resources （e.g., weapons） onboard. They are designated to perform multiple consecutive tasks cooperatively on multiple ground targets. The problem becomes much more complicated because of these terms of heterogeneity. In order to tackle the challenge, we modify the former genetic algorithm with multi-type genes to stochastically search a best solution. Genes of chromo- somes are different, and they are assorted into several types according to the tasks that must be performed on targets. Different types of genes are processed specifically in the improved genetic operators including initialization, crossover, and mutation. We also present a mirror representation of vehicles to deal with the limited resource constraint. Feasible chromosomes that vehicles could perform tasks using their limited resources under the assignment are created and evolved by genetic operators. The effect of the proposed algorithm is demonstrated in numerical simulations. The results show that it effectively provides good feasible solutions and finds an optimal one.     

Efficient multisensor fusion using multidimensional dataassociation

We present the development of a multisensor fusion algorithm using multidimensional data association for multitarget tracking. The work is motivated by a large scale surveillance problem, where observations from multiple asynchronous sensors with time-varying sampling intervals (electronically scanned array (ESA) radars) are used for centralized fusion. The combination of multisensor fusion with multidimensional assignment is done so as to maximize the “time-depth” in addition to “sensor-width” for the number S of lists handled by the assignment algorithm. The standard procedure, which associates measurements from the most recently arrived S-1 frames to established tracks, can have, in the case of S sensors, a time-depth of zero. A new technique, which guarantees maximum effectiveness for an S-dimensional data association (S⩾3), i.e., maximum time-depth (S-1) for each sensor without sacrificing the fusion across sensors, is presented. Using a sliding window technique (of length S), the estimates are updated after each frame of measurements. The algorithm provides a systematic approach to automatic track formation, maintenance, and termination for multitarget tracking using multisensor fusion with multidimensional assignment for data association. Estimation results are presented for simulated data for a large scale air-to-ground target tracking problem     

密集杂波环境下的数据关联快速算法

基于联合概率数据互联（JPDA）的思想,提出了一种新的数据关联快速算法（Fast Al-gorithm for Data Association,简称FAFDA算法）.该方法不需象在最优JPDA算法中那样生成所有可能的联合互联假设,因而具有计算量小,易于工程实现的特点。仿真结果表明,与最优JPDA算法相比,FAFDA算法的跟踪性能令人满意,并且在密集杂波环境下可实时、有效地跟踪100批次以上的目标。     

一种基于模糊遗传算法的多传感器多目标跟踪数据关联算法

基于模糊遗传算法发展了一种新的数据关联算法。数据关联的静态部分靠一个模糊遗传算法来得出量测组合序列和S-D分配的m个最优解。在数据关联的动态部分，将得到的S-D分配的m个最优解在一个基于多种群模糊遗传算法的动态2D分配算法中依靠一个卡尔曼滤波估计器估计出移动目标各个时刻的状态。这一基于分配的数据关联算法的仿真试验内容为被动式传感器的航迹形成和维持的问题。仿真试验的结果表明该算法在多传感器多目标跟踪中应用的可行性。另外，对算法发展和实时性问题进行了简单讨论。     

A New Probabilistic Transformation in Generalized Power Space

The mapping from the belief to the probability domain is a controversial issue, whose original purpose is to make (hard) decision, but for contrariwise to erroneous widespread idea/claim, this is not the only interest for using such mappings nowadays. Actually the probabilistic transformations of belief mass assignments are very useful in modern multitarget multisensor tracking systems where one deals with soft decisions, especially when precise belief structures are not always available due to the existence of uncertainty in human being's subjective judgments. Therefore, a new probabilistic transformation of interval-valued belief structure is put forward in the generalized power space, in order to build a subjective probability measure from any basic belief assignment defined on any model of the frame of discernment. Several examples are given to show how the new transformation works and we compare it to the main existing transformations proposed in the literature so far. Results are provided to illustrate the rationality and efficiency of this new proposed method making the decision problem simpler.     

Multiassignment for tracking a large number of overlapping objects[and application to fibroblast cells]

In this paper we present a new technique for data association using multiassignment for tracking a large number of closely spaced (and overlapping) objects. The algorithm is illustrated on a biomedical problem, namely the tracking of a group of fibroblast (tissue) cells from an image sequence, which motivated this work. Because of their proximity to one another and due to the difficulties in segmenting the images accurately from a poor-quality image sequence, the cells are effectively closely spaced objects (CSOs). The algorithm presents a novel dichotomous, iterated approach to multiassignment using successive one-to-one assignments of decreasing size with modified costs. The cost functions, which are adjusted depending on the “depth” of the current assignment level and on the tracking results, are derived. The resulting assignments are used to form, maintain and terminate tracks with a modified version of the probabilistic data association (PDA) filter, which can handle the contention for a single measurement among multiple tracks in addition to the association of multiple measurements to a single track. Estimation results are given and compared with those of the standard 2D one-to-one assignment algorithm. It is shown that iterated multiassignment results in superior measurement-to-track association. The algorithms presented can be used for other general tracking problems, including dense air traffic surveillance and control     

Track segment association, fine-step IMM and initialization with Doppler for improved track performance

In this work we present a new track segment association technique to improve track continuity in large-scale target tracking problems where track breakages are common. A representative airborne early warning (AEW) system scenario, which is a challenging environment due to highly maneuvering targets, close target formations, large measurement errors, long sampling intervals, and low detection probabilities, provides the motivation for the new technique. Previously, a tracker using the interacting multiple model (IMM) estimator combined with an assignment algorithm was shown to be more reliable than a conventional Kalman filter based approach in tracking similar targets but it still yielded track breakages due to the difficult environment. In order to combine the broken track segments and improve track continuity, a new track segment association algorithm using a discrete optimization approach is presented. Simulation results show that track segment association yields significant improvements in mean track life as well as in position, speed, and course rms errors. Also presented is a modified one-point initialization technique with range rate measurements, which are typically ignored by other initialization techniques, and a fine-step IMM estimator, which improves performance in the presence of long revisit intervals. Another aspect that is investigated is the benefit of "deep" (multiframe or N-dimensional, with N > 2) association, which is shown to yield significant benefit in reducing the number of false tracks.     

平均场网络在航迹关联中的应用

在多节点分布式多传感器融合系统中,航迹关联问题可以化为多维分配问题。多维分配问题是一个典型的组合优化问题,很难得到问题的最优解,而且其计算量会随着问题维数和目标数的增加容易呈现指数爆炸现象。在二维平均场人工神经网络的基础上提出了一种三维平均场网络模型用于解决此三维分配问题。仿真结果表明,该人工神经网络模型,能够有效解决多维分配问题,具有较高的关联正确率,当目标数不是很多时,可满足工程上的要求。另外,提出的三维网络模型可以推广到多维情况用于解决多维分配问题。     

Multitarget tracking in clutter: fast algorithms for dataassociation

Three fast algorithms have been developed to solve the problem of data association in multitarget tracking in clutter. In the first algorithm, the problem of data association is identified as an exhaustive search problem in general. Subsequently, a mathematical model is proposed for the problem of data association in the joint probabilistic data association filter (JPDAF). Based on the model, a depth-first search (DFS) approach is developed for the fast generation of data association hypotheses and the computation of the conditional probabilities of the hypotheses in the JPDAF. When the density of targets is moderate, a second algorithm is developed to directly compute a posteriori probabilities in the JPDAF without generating the data association hypotheses. In the third algorithm, the effect of interference due to closely spaced targets is simplified. An approach to approximately compute the a posteriori probabilities in the JPDAF is developed. The computational complexity of the algorithms is analyzed in the worst case, as well as in the average case     

Multiple-Model Probability Hypothesis Density Filter for Tracking Maneuvering Targets

Tracking multiple targets with uncertain target dynamics is a difficult problem, especially with nonlinear state and/or measurement equations. With multiple targets, representing the full posterior distribution over target states is not practical. The problem becomes even more complicated when the number of targets varies, in which case the dimensionality of the state space itself becomes a discrete random variable. The probability hypothesis density (PHD) filter, which propagates only the first-order statistical moment (the PHD) of the full target posterior, has been shown to be a computationally efficient solution to multitarget tracking problems with a varying number of targets. The integral of PHD in any region of the state space gives the expected number of targets in that region. With maneuvering targets, detecting and tracking the changes in the target motion model also become important. The target dynamic model uncertainty can be resolved by assuming multiple models for possible motion modes and then combining the mode-dependent estimates in a manner similar to the one used in the interacting multiple model (IMM) estimator. This paper propose a multiple-model implementation of the PHD filter, which approximates the PHD by a set of weighted random samples propagated over time using sequential Monte Carlo (SMC) methods. The resulting filter can handle nonlinear, non-Gaussian dynamics with uncertain model parameters in multisensor-multitarget tracking scenarios. Simulation results are presented to show the effectiveness of the proposed filter over single-model PHD filters.     

资源分配的混合式决策支持系统

本文研究静态资源分配问题。首先利用统计报表的硬数据和代表经理人员经验的软数据来建立资源分配问题的数学模型,然后用有约束非线性优化的方法作出最优资源分配的决策。     

Monte Carlo filtering for multi target tracking and data association

We present Monte Carlo methods for multi-target tracking and data association. The methods are applicable to general nonlinear and non-Gaussian models for the target dynamics and measurement likelihood. We provide efficient solutions to two very pertinent problems: the data association problem that arises due to unlabelled measurements in the presence of clutter, and the curse of dimensionality that arises due to the increased size of the state-space associated with multiple targets. We develop a number of algorithms to achieve this. The first, which we refer to as the Monte Carlo joint probabilistic data association filter (MC-JPDAF), is a generalisation of the strategy proposed by Schulz et al. (2001) and Schulz et al. (2003). As is the case for the JPDAF, the distributions of interest are the marginal filtering distributions for each of the targets, but these are approximated with particles rather than Gaussians. We also develop two extensions to the standard particle filtering methodology for tracking multiple targets. The first, which we refer to as the sequential sampling particle filter (SSPF), samples the individual targets sequentially by utilising a factorisation of the importance weights. The second, which we refer to as the independent partition particle filter (IPPF), assumes the associations to be independent over the individual targets, leading to an efficient component-wise sampling strategy to construct new particles. We evaluate and compare the proposed methods on a challenging synthetic tracking problem.