A New Coarse Gating Strategy Driven Multidimensional Assignment for Two-Stage MHT of Bearings-Only Multisensor-Multitarget Tracking
The problem of two-dimensional bearings-only multisensor-multitarget tracking is addressed in this work. For this type of target tracking problem, the multidimensional assignment (MDA) is crucial for identifying measurements originating from the same targets. However, the computation of the assignment cost of all possible associations is extremely high. To reduce the computational complexity of MDA, a new coarse gating strategy is proposed. This is realized by comparing the Mahalanobis distance between the current estimate and initial estimate in an iterative process for the maximum likelihood estimation of the target position with a certain threshold to eliminate potential infeasible associations. When the Mahalanobis distance is less than the threshold, the iteration will exit in advance so as to avoid the expensive computational costs caused by invalid iteration. Furthermore, the proposed strategy is combined with the two-stage multiple hypothesis tracking framework for bearings-only multisensor-multitarget tracking. Numerical experimental results verify its effectiveness.
Keywords: bearings-only multisensor-multitarget tracking; multidimensional assignment (MDA); coarse gating; Mahalanobis distance; maximum likelihood estimation; multiple hypothesis tracking
1. Introduction
Multitarget tracking (MTT) refers to jointly estimating the number of targets and their states in the presence of false alarms and missed detections using single or multiple sensors [[1]]. It has been widely used in many fields such as surveillance and tracking of ground moving targets [[2]], maritime surveillance [[3]], sonar tracking of submarines [[4]], simultaneous localization and mapping [[5]], unmanned air vehicles [[6]], etc. For different application scenarios, tracked targets can be considered as point targets or extended targets [[7]]. If the distance between the sensor and target is large enough as in radar-based air surveillance applications, the target can be treated as a point target. In this case, it is usually assumed that a target can give rise to at most one measurement in a scan [[8]]. However, if multiple resolution cells of the sensor are occupied by a target, for example, in vehicle tracking using automotive radar, the target is regarded as an extended target [[9]]. In such a case, each target can give rise to multiple measurements [[10]]. Only point targets will be discussed below.
Multitarget tracking has been studied for decades and many effective algorithms are available. The earliest and simplest MTT algorithm is the global nearest neighbor (GNN) algorithm [[11]], which attempts to search for the single most likely hypothesis for track update and new track initiation [[12]]. Although the GNN algorithm is intuitively attractive and easy to implement, it is prone to track loss in scenarios with closely spaced targets and high false alarm density [[13]]. The joint probabilistic data association (JPDA) algorithm is an extension of the probabilistic data association (PDA) algorithm to the multitarget case [[14]]. The standard JPDA algorithm evaluates the association probabilities of measurement-to-track and combines them to obtain the state estimate of the target [[15]], which means that one observation may contribute to updating multiple tracks [[16]]. Many variants of the JPDA algorithm are abundant, such as the joint integrated PDA (JIPDA) algorithm [[17]] and multiscan JPDA (MS-JPDA) algorithm [[18]]. Multiple hypothesis tracking (MHT) is a deferred decision algorithm for MTT. It handles uncertainty of measurement-to-track associations by considering all possible association hypotheses in subsequent multiple scans [[19]]. Compared with GNN and JPDA algorithms that rely on the current scan, the MHT algorithm is computationally expensive, but it has significantly better tracking performance [[20]]. There are two different implementations of MHT algorithm, namely hypothesis-oriented MHT [[21]] and track-oriented MHT [[22]]. Between them, the track-oriented MHT algorithm, which uses the score function to evaluate the quality of tracks, is considered a more effective alternative to a hypothesis-oriented MHT [[21]]. Among the above three data association-based MTT algorithms, i.e., GNN, JPDA, and MHT, MHT is considered as a leading algorithm in high false alarm density and dense target scenarios [[23]].
The random finite set (RFS) algorithm [[24]] represents the multitarget state and measurements as a random finite set, which allows multitarget tracking to be cast in a Bayesian framework to obtain an optimal multitarget Bayes filter. Due to the high computational complexity of a multitarget Bayes filter [[25]], many approximate filters have been developed, such as probability hypothesis density (PHD) [[26]], cardinalized PHD (CPHD) [[27]], second-order PHD [[28]], and multitarget multi-Bernoulli (MeMBer) [[29]] filters. It should be note that none of these filters can obtain distinguishable target tracks. The generalized labeled multi-Bernoulli (GLMB) [[20]] is the RFS based MTT algorithm that produces tracks. In recent years, the GLMB filter has been widely studied, and fruitful achievements have been achieved in both theory and application [[30]]. In addition, the GLMB filter has been used to develop an MTT algorithm with structures similar to MHT [[19]].
Multisensor-multitarget tracking (MSMTT) has two basic architectures: centralized and distributed tracking [[7]]. In centralized MSMTT, the raw measurements from all sensors are sent to the fusion center (FC) where data association is followed by filtering, while in distributed MSMTT, each sensor first processes its own measurements and then sends the results to FC for further processing. Both frameworks have their own advantages and disadvantages in terms of communication requirements, computational complexity, performance, robustness, etc. In general, the centralized MSMTT framework has higher accuracy [[31]]. However, in practical applications, due to network bandwidth limitations, it is often not feasible to communicate all measurements to FC. Comparatively, the distributed MSMTT framework can reduce communication cost and has better flexibility and reliability, but it is more challenging.
For distributed MSMTT based on data association, one approach is that each sensor sends the local track estimates to the FC, which performs track-to-track association and fusion [[32]]. Another type of approach is to perform measurement space tracking at individual local sensors to suppress clutter and then send the associated measurements to the FC where the measurement-to-track association is performed [[33]]. In addition, distributed MSMTT based on RFS has also been widely studied in recent years [[34]].
Depending on the types of sensors used, target tracking can be split into two classes: active and passive tracking [[35]]. The sensors used for active tracking first transmit signals (such as acoustic waves, electromagnetic waves) into the environment and then obtains range, bearing, elevation, and other measurements of the target of interest from the received echo [[36]]. Passive sensors sense the signal from the target of interest to acquire bearing, elevation, and other measurements. In comparison, passive tracking has the advantages of strong anti-interference and good concealment [[37]].
Passive tracking also involves a unique set of challenges. One of the key challenges in bearings-only tracking is that the range between the passive sensor and the target is unavailable. This results in an unobservability of the target state [[38]]. A basic observable condition is that the sensor performs a higher order maneuver than all targets [[39]]. An alternative approach is to use multiple spatially separated sensors for triangulation, that is, the passive MSMTT [[40]]. But for this approach, the attendant problem is the well-known ghosting. In order to reduce the number of ghosts, three or more sensors should be used [[41]]. In this case, multidimensional assignment (MDA) can be used to associate the measurements from different sensors to identify common targets, which also makes this approach computationally costly for a large number of measurements. One of the main reasons is that in MDA, most of the time (at least up to 80%), is spent in calculating the association cost [[42]]. To reduce calculation times, many fast MDA methods have been proposed. Among them, it was proposed in [[43]] to cluster the measurements of different sensors before forming possible association hypotheses, thus reducing the requirement for calculating the association cost. In addition, two improved MDA methods using prior track information were proposed in [[44]].
A new coarse gating strategy is studied for the passive MSMTT. First, in order to reduce the computational complexity of MDA, a new coarse gating strategy is proposed. Second, the proposed strategy is combined with a two-stage MHT (TS-MHT) framework for distributed MSMTT. The remainder of the paper is organized as follows. Section 2 formulates the problems of bearings-only MSMTT. Section 3 briefly summarizes MDA for measurement-to-measurement association. In Section 4, a new coarse gating is proposed. Section 5 presents the combination of the proposed new coarse gating driven MDA with the TS-MHT framework. Section 6 provides numerical examples to illustrate the effectiveness of the proposed coarse gating strategy. Section 7 concludes the paper.
2. Problem Formulation and Notations
The two-dimensional (2D) bearings-only MSMTT is considered. The bearing measurement is shown in Figure 1.
Assume that there are S synchronous passive sensors and sensor s, , can acquire bearing measurements at time k. Here, may not be equal to the number of true targets due to false alarms and nonunity detection probability of sensor s. For the sake of simplicity, each target is assumed to move with nearly constant velocity (NCV) in the XY-plane. Then, the discrete-time dynamic system can be written as follows:
(1)
(2)
where is the state vector consisting of the target position and velocity , i.e., , is the state transition matrix for NCV motion model, is a sequence of zero-mean white Gaussian process noise, is the position of the sensor s, is a sequence of zero-mean white Gaussian bearing measurement noise with variance , and the measurement noises across sensors are independent; h is a nonlinear function. The nonlinear relationship among , and is given by the following:
(3)
where refers to the four-quadrant inverse tangent function [[45]].
The purpose is to estimate the number of targets and their corresponding states in real time. A list of nomenclatures is provided in Nomenclatures.
3. Measurement-to-Measurement Association
A brief description of measurement-to-measurement association is required to illustrate the proposed strategy more clearly. For a single passive sensor, the range measurement between target and sensor is not available, which makes the target state unobservable. During target tracking, especially for track initiation, at least two passive sensors are needed to obtain the full position of the potential target. It should be noted that, in a two-dimensional multitarget tracking scenario with only two sensors, one of the major problems is the occurrence of false intersections or ghosts. For example, as shown in Figure 2, the dashed lines of different colors indicate bearing measurements originating from target 1, and the solid lines of different colors indicate bearing measurements originating from target 2. Obviously, the correct association pair cannot be identified with only two bearings-only sensors.
Therefore, it is necessary to use three or more sensors if possible. However, the consequent problem is that this also makes it computationally expensive for a large number of measurements. Taking Figure 3 as an example, it shows the situation of two targets observed by three passive sensors with measurement errors.
As shown in the above figure, the sets of measurements obtained by different sensors originating from the targets can be denoted by , , and , respectively. For measurement-to-measurement associations, each candidate association, consisting one measurement from each sensor, is denoted as the S-tuple of measurements . Even in the case where there are no false alarms or missed detections, the number of S-tuples is as follows:
(4)
where denotes the number of combinations of selecting n choices from m choices. The corresponding geometric relationship is shown in Figure 4.
Each S-tuple of measurements is an association hypothesis. Obviously, only S-tuples and (as in Figure 4a,h) originate from the targets, and the others are spurious association hypotheses. Note that when there are false alarms or missed detections, and the number of S-tuples that can be formed will increase.
The process of associating the S-tuples of measurements to targets is the well-known measurement-to-measurement association problem. MDA based on likelihood ratio is widely considered to be the most efficient method to deal with this problem, which formulates the association between measurements from different sensors as a discrete optimization problem given by the following:
(5)
subject to
(6)
where is the index of dummy measurement to indicate sensor s's missed detection, is the cost of associating the S-tuple of measurements to a target, and is a binary decision variable such that the following is the case.
(7)
The equality constraints in Equation (6) are to ensure that each measurement is associated with a unique target, or declared false, and that each target is assigned to at most one measurement from each sensor. In Equation (5), cost is defined as the following negative log-likelihood ratio:
(8)
where is the likelihood that measurements in S-tuple are all spurious, and is the likelihood that these measurements originate from a common target at position . They can be calculated as follows, respectively:
(9)
(10)
where is the volume of the field of view of sensor s, and is a binary indicator function.
(11)
It should be noted that, in Equation (10), is unknown. Therefore, in order to calculate likelihood , the corresponding is used to obtain the maximum likelihood estimation (MLE) of the target position.
(12)
Substituting Equations (9), (10) and (12) into Equation (8), required cost can be calculated. Note that the optimization problem given by Equations (5) and (6) is NP-hard for . However, a number of efficient methods to obtain sub-optimal solution have been proposed [[46], [48]].
4. A New Coarse Gating Strategy for MDA
The MLE of the position of potential target in Equation (12) is a nonlinear optimization problem. In this section, a new coarse gating strategy is proposed to eliminate infeasible association hypotheses by comparing the Mahalanobis distance between the current estimate and initial estimate in an iterative process for the MLE of the target position.
Each S-tuple of measurements can form a corresponding stacked measurement vector denoted by . The relationship between the stacked measurement vector and position of the corresponding target can be written as follows:
(13)
where is the position of target in -plane, is the position of sensor s, and is the stacked measurement vector of measurement noises with covariance .
The MLE of the target position can be solved by iteration, and the iterative process can be denoted [[50]] by the following:
(14)
where the following is the Jacobian matrix:
(15)
and is the position estimation of target after iteration l. The initial estimate can be obtained from the intersection of the bearing measurements of any two of all sensors.
The mean square error of final target position estimate can be calculated by the following.
(16)
For stacked measurement vectors formed by incorrect associations, their elements do not originate from common targets. Therefore, in this case, it is irrational to solve the position estimation given in Equation (12). A natural idea is to analyze the differences of different measurement vectors in the iterative process so as to roughly delete some infeasible associations.
In the iteration, the initial position estimate can be obtained from the intersection of any two bearing components of stacked measurement vector. Moreover, the corresponding covariance can be computed by Equation (16). Note that the initial estimate is determined by the measurements of only two sensors, while the estimate after l iterations, , is determined by the measurements of all sensors together. That is, these two estimates are not generated by the same measurements. If these measurements are not originated from a common target, the position estimate will deviate from the initial estimate in the iterative process. This will easily result in inconsistencies between these two estimates. Here, the inconsistency between two estimates refers to the fact that the difference between their means is greater than what can be expected based on their respective error covariance estimates [[51]].
Taking Figure 4c in Section 3 as an example, the stacked measurement vector formed by the S-tuple of measurements is . Suppose that, in the iterative process, the initial position estimate is obtained by the bearing measurements of sensors 1 and 3. If the initial estimate and the estimate after l iterations, , are as shown in Figure 5, it means that the two estimates are inconsistent with each other. It should be noted that Figure 5 is only a schematic diagram and not a real experimental result. Numerical experiments will be presented in Section 6.
Therefore, it is necessary to quantitatively analyze the difference between the two estimates. One mechanism for detecting statistically significant deviations between estimates is to calculate the Mahalanobis distance [[52]]. The Mahalanobis distance between estimates and is defined as follows.
(17)
It can be roughly interpreted to mean that lies within an ellipsoid centered around [[53]]. A larger Mahalanobis distance tends to indicate that the two estimates are inconsistent; that is, the components in the corresponding stacked measurement vector do not originate from the common target [[51]]. Therefore, it is necessary to set an appropriate threshold T according to the measurement accuracy of the sensors. When , it means that the components may originate from the common target. In this case, iteration (14) will be repeated until or the following occurs:
(18)
where is preset maximum number of iterations, is the norm of a vector, is a sufficiently small positive real number. Final position estimate will be used to calculate assignment cost . When , this means that measurements in the vector originate from different targets. Therefore, the iteration will be terminated and the corresponding association cost will be assigned to infinity.
A threshold T is required to detect inconsistencies between the two estimates and , , which decides whether it is necessary to further calculate the association cost for MDA. The choice of the threshold T is inherently problem dependent [[54]]. In bearings-only MSMTT, it is closely related to the position and measurement accuracy of the passive sensors. In order to avoid deleting incorrect associations, the threshold should not be too small. For a small number of remaining incorrect associations, the subsequent MDA can be used for further identification. In practical applications, an a priori threshold can be determined in advance with the help of cooperative targets.
For some infeasible associations, terminating the iterations when the Mahalanobis distance between the initial estimate of the iterative estimate is greater than a set threshold T can effectively save computational cost. The proposed strategy is denoted by coarse gating in iterations (CGI). The CGI-driven MDA is summarized in Algorithm 1.
Algorithm 1: CGI driven MDA |
![]() |
5. Two-Stage MSMTT
In this section, the CGI-driven MDA is combined with a TS-MHT framework to perform bearings-only MSMTT. The framework is given in Figure 6.
First, MHT is performed at each sensor, and only the measurements used to update the tracks are sent to the FC. Here, these measurements are referred to as "effective measurements." Second, the effective measurements from different sensors are combined and augmented to form stacked measurement vectors. Note that each measurement vector is a potential association hypothesis. The proposed CGI is then used to eliminate infeasible association hypotheses. After this, the measurement-to-measurement association is performed using the MDA algorithm. Finally, target tracks are obtained by using the second stage MHT.
The advantages of the above framework are mainly in the following aspects. In the framework shown in Figure 6, using the first stage MHT can eliminate most of the false measurements obtained by individual sensors, thus reducing the number of stacked measurement vectors. This further reduces the computational requirement of associations, and it also helps improve the accuracy of MDA. In turn, accurate data association facilitates track initialization in the second stage MHT and avoids infeasible hypothesis generation.
5.1. First Stage MHT
For the first stage, bearings-only multitarget tracking needs to be performed at each local passive sensor. Many existing methods are available [[23], [33], [55]]. Since this part is not the focus of this work, only one of the methods is considered.
The method proposed in [[33]] is to define the target state in Cartesian coordinates, thus performing single sensor state-space tracking. It should be noted that in [[33]], the target moves in three-dimensional space, and frequency information is available. In order to use the strategy for two-dimensional bearings-only MSMTT, it is simplified so that the dynamical system of the target can be described by Equations (1) and (2).
First, the one-point initialization approach is performed by combining the detection range of the sensor and all measurements at the initial time. Suppose that the detection range of sensor s is within the interval . Correspondingly, the initial range between the target and the sensor and the corresponding variance can be calculated [[33]] as follows.
(19)
Then, the estimate of the initial state vector and the associated covariance are the following:
(20)
(21)
where the following is the case:
(22)
(23)
and represents the measurement noise variance of sensor s, and and are the velocity variances based on their a priori maximum values.
It should be noted that, for this method, parameter is only used for track initiation. That is to say that only bearing measurements are used to update tracks during the course of track maintenance. In addition, the measurements used for updating will be sent to the second stage.
5.2. Second Stage MHT
After the first stage MHT, most false measurements from each local sensor are eliminated, and the effective measurements are sent to the FC. Considering that the tracking performance of single passive sensor is quite limited in the first stage, these effective measurements can be divided into three categories: measurements originated from the target, false measurements due to false association, and dummy measurements due to missed detection. Therefore, in the second stage, the measurement-to-measurement association still needs to be performed.
First, all effective measurements from different sensors are combined and augmented to form stacked measurement vectors. Each stacked measurement vector is a potential association hypothesis. Then, the proposed CGI is used to delete infeasible associations. For each stacked measurement vector, in the iterative process of obtaining the MLE of target position, if the Mahalanobis distance between the initial estimate and the iterative estimate is greater than threshold T, then the association is determined as infeasible and deleted. When , the estimate from the final iteration is naturally regarded as the MLE of the target position in the -plane, i.e., the solution of Equation (12). At the same time, it can be used for subsequent MDA. Finally, target tracks are obtained through the second stage MHT.
6. Illustrative Examples
In this section, five illustrative examples are presented. First, a scenario with three stationary targets (Scenario 1) is used to illustrate that, for incorrect associations, the initial estimation and iterative estimation generated in the iterative process are often inconsistent so as to verify the rationality and feasibility of the proposed strategy CGI. Second, a scenario with 18 stationary targets (Scenario 2) is used to compare the performance difference of three methods, MDA, CGI-driven MDA, and clustering-based MDA [[43]], to verify the effectiveness of the proposed strategy. Finally, a single-target tracking scenario (scenario 3) and multi-target tracking scenarios (scenarios 4 and 5) are used to further validate the performance of the framework shown in Figure 6.
6.1. Verification of Inconsistency
This subsection uses a numerical example about stationary targets to illustrate the difference in Mahalanobis distance between the current and initial estimates in an iterative process for the MLE of different target positions so as to verify the feasibility of the CGI proposed in Section 4.
Suppose there are three fixed passive sensors located at (0 m, 0 m), (1000 m, 600 m), and (3000 m, 0 m) in the XY-plane. At time k, sensor acquires bearing measurements , where and represents the measurements originated from the targets 1 and 2, respectively. The positions of these two targets in the -plane are (1500 m, 200 m) and (1800 m, 500 m). The standard deviations of the measurement errors of these three sensors are mrad, .
In the absence of false alarms and missed detections, eight stacked measurement vectors, i.e., association hypotheses, can be obtained. Figure 7 shows the bearing measurements of each sensor in one of the Monte Carlo runs, where the dashed lines represent the measurements originated from target 1, and the solid lines represent the measurements originated from target 2. Figure 8, Figure 9 and Figure 10 show initial estimate and iterative estimate , obtained using these stacked measurement vectors. Note that the only condition for iteration termination in this scenario is . The uncertainty of the position estimates in the -plane is represented by the 95% probability ellipses.
From Figure 8a,f, when all components of the stacked measurement vector originate from the same target, the uncertainty ellipse of the iterative estimate is smaller than that of the initial estimate, and these two estimates are consistent. From Figure 8b,d,e, it can be observed that these two estimates obtained by , , and are inconsistent. For the other two stacked measurement vectors and , since the initial and iterative estimates are too far away from each other, they are shown in the subfigures of Figure 9 and Figure 10, respectively. It can be observed that the uncertainty ellipses of the iterative estimates are extremely large. For this two cases, the initial and iterative estimates are also obviously inconsistent.
It can be demonstrated through the above experiments that for many infeasible associations, the two estimates, and , obtained in the iterations are often inconsistent.
Furthermore, for each stacked measurement vector, the Mahalanobis distances between initial estimate and all iterative estimates , are calculated. Table 1 presents the minimum and maximum Mahalanobis distances obtained in the iterative process with the different stacked measurement vectors. It is the statistic obtained from 2000 Monte Carlo runs.
It can be observed that, throughout the iterative process, the Mahalanobis distances obtained by using correctly associated vectors and are significantly smaller. Therefore, infeasible associations can be effectively eliminated by setting an appropriate threshold T.
6.2. CGI Driven MDA for Stationary Targets
In this subsection, the impact of the proposed CGI on the performance of MDA will be analyzed. This scenario, as illustrated in Figure 11, consists of 3 bearing-only passive sensors, 1 cooperative target, and 18 unknown non-cooperative targets.
The positions of three passive sensors in the -plane are (−2000 m, −2500 m), (2500 m, −2750 m), and (200 m, −3500 m), respectively. The standard deviations of the measurement errors for all sensors are mrad, . The position of the cooperative target is (600 m, −1600 m). The positions of other unknown non-cooperative targets are shown in Table 2. For the sake of simplicity, it is assumed that all sensors have unity detection probability for each target and there are no false measurements. It is also supposed that, at some point before these unknown targets are detected, three passive sensors can only acquire the bearing measurements originating from the cooperative target.
In order to set a reasonable threshold T for the proposed CGI, the bearing measurements originating from the cooperative target are used iteration of Equations (14) and (16). The maximum Mahalanobis distance between the initial estimate and each iterative estimate , was over 2000 Monte Carlo runs. Considering that the Mahalanobis distance is closely related to the geometric structure between the sensors and the cooperative target, threshold T should not be less than . In order to avoid deleting the correct association, the threshold in this scenario is set to .
The Lagrangian relaxation method in [[48]] is used to obtain suboptimal solutions of the MDA problem in Equation (5). Table 3 presents the performance comparison of three different methods, MDA, CGI driven MDA, and clustering-based MDA [[43]], based on a 2000-run Monte Carlo average. The experimental results are obtained on MATLAB R2020b with Intel(R) Core(TM) i5-9500 CPU @3.00GHz and RAM of 8 GB.
It can be observed from Table 3 that the number of S-tuples reduced from 5832 to 83.82 after CGI. Moreover, the correct association rate of CGI-driven MDA is 99.61%, much higher than that of the other two methods. This means that CGI can effectively eliminate a large number of infeasible associations and can significantly improve the correct association rate of MDA. In addition, for MDA, the execution time to calculate the assignment costs of all S-tuples is 3.9069 s. This takes about 81% of the total execution time. For CGI-driven MDA, the execution time for calculating all assignment costs is only 3 s, which accounts for about 50% of the total execution time. Obviously, the proposed CGI driven MDA has a significant improvement in both computational efficiency and correct association probability. For the clustering-based MDA method, the execution time of obtaining the suboptimal solution of Equation (5) by the Lagrangian relaxation algorithm is less than that of the proposed CGI-driven MDA method. This is due to the fact that the clustering method decomposes the entire assignment problem into smaller subproblems, thus improving computational efficiency.
Table 4 illustrates the impact of five different thresholds on the performance of the proposed CGI-driven MDA. It can be observed that the larger T is, the larger the number of S-tuples obtained after CGI, and the more execution time is required. The correct association rate when is 78.14%, which is less than the correct association rate when . Therefore, it is not the case that the smaller the threshold is, the better. Smaller thresholds may result in the removal of some correct associations. Moreover, it can be found that when , the correct association rate is significantly smaller than the other two groups. This is mainly due to the large number of retained S-tuples, which results in the degradation of the performance of the Lagrangian relaxation algorithm used.
6.3. TS-MHT for Single Target Tracking in Clutter
In this subsection, a single target tracking scenario is considered to verify the performance of the TS-MHT framework shown in Figure 6.
There are four passive sensors located at (1000 m, 2250 m), (1000 m, −2250 m), (6000 m, 2250 m), and (6000 m, −2250 m), respectively. Each sensor can only measure the bearing to the target, and the sampling interval is 10 s. Their measurement errors are modeled as zero-mean Gaussian white noises with same standard deviations mrad, . The maximum detection range of each sensor is 5 km and the detection probability is , . False measurements are uniformly distributed over the detection range and their number is Poisson distributed with an average of 4 false measurements per sensor per scan. Target moves in two dimensions with NCV, and its initial position and velocity are [3500 m, −4000 m] and [0 m/s, 7.2 m/s], respectively. The process noise covariance is . The true trajectory of the target motion and the sensor positions are shown in Figure 12, where the detection range of each sensor is indicated by dashed lines of different colors.
Figure 13 shows the tracking results of each sensor at the first stage. Here, threshold T is set to 16. Superficially, there are significant differences between the tracking results of each sensor and the true track of the target. This is due to the unobservability of target state for single passive sensor. Although, in track initiation, the initial position estimate of the target can be obtained by the detection range of the sensor, it is also inaccurate.
It should be noted that, for the first stage of the TS-MHT framework shown in Figure 6, its main purpose is to eliminate as many false measurements as possible by using preliminary tracking. Moreover, only the measurements used to update these tracks are sent to the second stage in real time. That is to say that it is more interested in whether the measurements sent to the second stage originate from the true target than in the accuracy of target state estimation. From Figure 13, it can be observed that the number of tracks obtained by sensors are all one. These estimated numbers of tracks are close to the number of true target. In addition, the estimated tracks by each sensor and the true track of the target are on the same side of the corresponding sensor, and their orientations with respect to the sensors are roughly the same. This means that the tracking results of the first stage may not be that bad, although the tracking results still need to be further improved by the measurements from other sensors during the second stage.
Figure 14 shows the tracking result of the second stage. It can be observed that the second stage MHT can effectively track the target in clutter. At the same time, this in turn shows that CGI-driven MDA can effectively delete infeasible associations.
The execution time of each stage is calculated over 2000 Monte Carlo runs. For the first stage, the average execution time per frame of the MHT algorithm in each sensor is approximately equal, and it is about 1.0741 s. For the second stage, the average execution time of MHT algorithm is 0.1782 s per frame. Obviously, the execution time of the second stage MHT is significantly smaller than that of the first stage MHT. This is due to the fact that the first stage can effectively eliminate a large number of false measurements, thus effectively reducing the number of feasible assumptions in the second stage. It should be noted that the effective measurements in the first stage are sent to the second stage in real time.
In addition, to verify the effect of different thresholds T on tracking performance, the root mean square error (RMSE) is used to measure the performance of target tracking, as shown in Figure 15. It can be observed that when , tracking performance is significantly better than the other two groups. Combined with the experimental results of Scenario 2, it can be further demonstrated that when preset threshold T is too large or too small, and it may result in a decrease in the correct association rate of MDA, which further affects tracking performance.
6.4. TS-MHT for Multitarget Tracking in Clutter
Consider two multitarget tracking scenarios with four sensors. For scenario 4, as shown in Figure 16a, the two targets move simultaneously along the Y direction with a nearly constant speed of 6.2 m/s, and their initial positions are [3500 m, −3500 m] and [6500 m, −3500 m], respectively. For scenario 5 as shown in Figure 16b, the initial positions of the two targets are [5000 m, −3500 m] and [8500 m, 0 m], and their initial velocities are [0 m/s, 7.2 m/s] and [−5.2 m/s, 0 m/s], respectively. The other parameters are the same as in Scenario 2.
By comparing Figure 16 and Figure 17, it can be observed that the proposed strategy can effectively tackle MSMTT.
7. Conclusions
The bearings-only multitarget tracking problem is investigated for synchronous passive sensors. In the target tracking process, especially for track initiation, MDA can be used to identify the measurements originating from common targets. In order to reduce the computational cost of the multidimensional assignment and improve its correct association rate, a new coarse gating strategy, the CGI, has been proposed first. For MDA, iterative processes can be used to obtain the MLE of target position corresponding to each possible association and, thus, further calculate the assignment cost of that association. Since the initial estimate and the iterative estimate are not obtained by the same measurements, it has been proposed to eliminate infeasible associations by using the Mahalanobis distance between the initial estimate and the iterative estimate as a measure. The feasibility and effectiveness of the proposed CGI is verified by two scenarios, i.e., scenarios 1 and 2, respectively. In addition, MDA driven by this strategy is combined with the TS-MHT framework for distributed MSMTT. Numerical examples have verified the performance of the proposed strategy. Moreover, the effectiveness of the proposed strategy in the tracking process is further verified by two scenarios of single target and multitarget in clutter.
Figures and Tables
Graph: Figure 1 Illustration of two-dimensional bearing measurement.
Graph: Figure 2 A scenario with 2 passive sensors and 2 targets.
Graph: Figure 3 A scenario with 3 passive sensors and 2 targets.
Graph: Figure 4 Geometric relationship between sensors and S-tuples of measurements (a) Zk111. (b) Zk112. (c) Zk121. (d) Zk122. (e) Zk211. (f) Zk212. (g) Zk221. (h) Zk222.
Graph: Figure 5 An illustration of the inconsistency between the two estimates. (p^ki,0,Rki,0) is the initial estimate and (p^ki,l,Rki,l) is the estimate after l iterations.
Graph: Figure 6 Framework of TS-MHT.
Graph: Figure 7 Scenario 1 with 2 stationary targets and 3 passive sensors.
Graph: Figure 8 The initial estimate and the estimate after l iterations obtained using different stacked measurement vectors. (a) zk111. (b) zk121. (c) zk122. (d) zk211. (e) zk221. (f) zk222.
Graph: Figure 9 The initial estimate and the estimate after l iterations obtained using the stacked measurement vector zk112. (a) Initial estimate. (b) Estimate after l iterations.
Graph: Figure 10 The initial estimate and the estimate after l iterations obtained using the stacked measurement vector zk212. (a) Initial estimate. (b) Estimate after l iterations.
Graph: Figure 11 Scenario 2 with 18 stationary targets and 3 passive sensors.
Graph: Figure 12 Scenario 3 for single target tracking with 4 passive sensors.
Graph: Figure 13 Tracking results of first stage MHT in each local sensor. (a) Sensor 1. (b) Sensor 2. (c) Sensor 3. (d) Sensor 4.
Graph: Figure 14 Tracking results of second stage MHT.
Graph: Figure 15 Position RMSE of different threshold T.
Graph: Figure 16 Multitarget tracking scenarios with 4 passive sensors. (a) Scenarios 4. (b) Scenarios 5.
Graph: Figure 17 Tracking results. (a) Scenarios 4. (b) Scenarios 5.
Table 1 Mahalanobis distances between the initial estimate and the iterative estimates.
| | | | | | | | |
---|
Minimum Mahalanobis distances | 0.8336 | 80.9022 | 17.9394 | 3.8289 | 4.7382 | 102.5766 | 15.8057 | 0.4970 |
Maximum Mahalanobis distances | 1.1744 | | 45.7706 | 4.7942 | 7.0418 | | 56.0292 | 0.5112 |
Table 2 Positions of all targets in XY-plane.
(−1500 m, −500 m) | (−900 m, −500 m) | (−300 m, −500 m) | (900 m, −500 m) | (1500 m, −500 m) | (−1500 m, −500 m) |
(−1500 m, −1000 m) | (−900 m, −1000 m) | (−300 m, −1000 m) | (900 m, −1000 m) | (1500 m, −1000 m) | (−1500 m, −1000 m) |
(−1500 m, −1500 m) | (−900 m, −1500 m) | (−300 m, −1500 m) | (900 m, −1500 m) | (1500 m, −1500 m) | (−1500 m, −1500 m) |
Table 3 The performance comparison of different methods.
| MDA | Clustering-Based MDA | CGI Driven MDA |
---|
Number of all S-tuples | 5832 | 5832 | 5832 |
Number of S-tuples after coarse gating | - | 103.74 | 83.82 |
Number of identified targets | 19.58 | 18.97 | 18.02 |
Percent correct association | 33.35% | 81.67% | 99.61% |
Execution time to calculate assignment costs | 3.9069 s | 0.3917 s | 0.3625 s |
Execution time to obtain suboptimal solution | 0.9163 s | 0.1457 s | 0.3543 s |
Table 4 The effect of different threshold T on the performance of CGI driven MDA.
| | | | | |
---|
Number of all S-tuples | 5832 | 5832 | 5832 | 5832 | 5832 |
Number of S-tuples after CGI | 29.43 | 61.03 | 83.82 | 95.89 | 114.93 |
Number of identified targets | 18.27 | 18.01 | 18.02 | 18.37 | 19.68 |
Percent correct association | 78.14% | 99.33% | 99.61% | 87.61% | 69.39% |
Execution time to calculate assignment costs | 0.3597 | 0.3397 s | 0.3625 s | 0.3472 s | 0.3439 s |
Execution time to obtain suboptimal solution | 0.0164 | 0.0964 s | 0.3543 s | 0.8761 s | 1.3270 s |
Author Contributions
Conceptualization, Z.W., Z.D. and M.M.; methodology, Z.W., Z.D. and M.M.; software, Z.W.; validation, Z.W., Z.D. and Y.H.; writing—original draft preparation, Z.W., Z.D. and M.M.; writing—review and editing, Z.D., Y.H. and M.M. All authors have read and agreed to the published version of the manuscript.
Funding
This work is supported in part by National Key Research and Development Plan under Grants 2021YFC2202600 and 2021YFC2202603, and National Natural Science Foundation of China through Grants 62033010, 61773147 and 61673317.
Institutional Review Board Statement
Not applicable.
Informed Consent Statement
Not applicable.
Data Availability Statement
Not applicable.
Conflicts of Interest
The authors declare no conflict of interest.
Abbreviations
The following abbreviations are used in this manuscript:
MSMTT | Multisensor-multitarget tracking; |
MDA | Multidimensional assignment; |
MLE | Maximum likelihood estimation; |
TS-MHT | Two-stage multiple hypothesis tracking; |
MTT | Multitarget tracking; |
GNN | Global nearest neighbor; |
PDA | Probabilistic data association; |
JPDA | Joint probabilistic data association; |
JIPDA | Joint integrated probabilistic data association; |
MS-JPDA | Multiscan joint probabilistic data association; |
MHT | Multiple hypothesis tracking; |
RFS | Random finite set; |
PHD | Probability hypothesis density; |
CPHD | Cardinalized probability hypothesis density; |
GLMB | Generalized labeled multi-Bernoulli; |
FC | Fusion center; |
CGI | Coarse gating in iterations; |
2D | Two-dimensional; |
RMSE | Root mean square error; |
NCV | Nearly constant velocity. |
Nomenclatures
Notations | Definitions |
S | Number of sensors |
s | Sensor index, |
i | Target index |
k | Time index |
| Bearing measurement index acquired by sensor s |
| Number of bearing measurements acquired by sensor s |
| The th bearing measurement acquired by sensor s at time k |
| True bearing between target i and sensor s |
| False measurements |
| State vector of target i at time k |
| Position vector of sensor s |
| State transition matrix at time k |
| Process noise vector of target i at time k |
| Measurement noise of sensor s at time k |
| Measurement noise variance of sensor s |
| An S-tuple of measurements, one from each sensor |
| Cost of associating S-tuple of measurements with a target |
| Binary decision variables |
| Detection probability of sensor s |
| Volume of the field of view of sensor s |
| Binary indicator function |
l | iteration index |
| Stacked measurement vector corresponding to S-tuple |
| Position vector of target i |
| Initial position estimate of target i |
| Position estimation of target i after iteration l |
| Covariance matrix corresponding to the position estimate |
| Jacobian matrix |
| Mahalanobis distance |
T | Threshold |
[
Footnotes
1
Publisher's Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
]
[
References
Mallick M., Vo B.N., Kirubarajan T., Arulampalam S. Introduction to the issue on multitarget tracking. IEEE J. Sel. Top. Signal Process. 2013; 7: 373-375. 10.1109/JSTSP.2013.2254034
2
Mallick M., Bar-Shalom Y., Kirubarajan T., Moreland M. An improved single-point track initiation using GMTI measurements. IEEE Trans. Aerosp. Electron. Syst. 2015; 51: 2697-2714. 10.1109/TAES.2015.140599
3
Lima K.M.D., Costa R.R. Cooperative-PHD Tracking Based on Distributed Sensors for Naval Surveillance Area. Sensors. 2022; 22729. 10.3390/s22030729. 35161477
4
Luo J., Han Y., Fan L. Underwater Acoustic Target Tracking: A Review. Sensors. 2018; 18112. 10.3390/s18010112. 29301318
5
Bahraini M.S., Rad A.B., Bozorg M. SLAM in Dynamic Environments: A Deep Learning Approach for Moving Object Tracking Using ML-RANSAC Algorithm. Sensors. 2019; 193699. 10.3390/s19173699
6
Panicker S., Gostar A.K., Bab-Hadiashar A., Hoseinnezhad R. Recent Advances in Stochastic Sensor Control for Multi-Object Tracking. Sensors. 2019; 193790. 10.3390/s19173790
7
Mallick M., Krishnamurthy V., Vo B.N. Multitarget Tracking Using Multiple Hypothesis Tracking. Integrated Tracking, Classification, and Sensor Management: Theory and Applications; Wiley: Piscataway, NJ, USA. 2012: 163-202. 10.1002/9781118450550.ch5
8
Lundquist C., Granström K., Orguner U. An Extended Target CPHD Filter and a Gamma Gaussian Inverse Wishart Implementation. IEEE J. Sel. Top. Signal Process. 2013; 7: 472-483. 10.1109/JSTSP.2013.2245632
9
Tang X., Li M., Tharmarasa R., Kirubarajan T. Seamless Tracking of Apparent Point and Extended Targets Using Gaussian Process PMHT. IEEE Trans. Signal Process. 2019; 67: 4825-4838. 10.1109/TSP.2019.2932873
Hoher P., Wirtensohn S., Baur T., Reuter J., Govaers F., Koch W. Extended Target Tracking with a Lidar Sensor Using Random Matrices and a Virtual Measurement Model. IEEE Trans. Signal Process. 2022; 70: 228-239. 10.1109/TSP.2021.3138006
Smith J., Particke F., Hiller M., Thielecke J. Systematic Analysis of the PMBM, PHD, JPDA and GNN Multi-Target Tracking Filters. Proceedings of the 2019 International Conference on Information Fusion. Ottawa, ON, Canada. 2–5 July 2019
Ishtiaq S., Wang X., Hassan S. Multi-Target Tracking Algorithm Based on 2-D Velocity Measurements Using Dual-Frequency Interferometric Radar. Electronics. 2021; 101969. 10.3390/electronics10161969
Blackman S.S., Popoli R.. Design and Analysis of Modern Tracking Systems; Radar Library: Norwood, MA, USA. 1999
Bar-Shalom B.Y., Willett P.K., Tian A.X.. Tracking and Data Fusion: A Handbook of Algorithms; YBS Publishing: Storrs, CT, USA. 2011
He S., Shin H.S., Tsourdos A. Joint Probabilistic Data Association Filter with Unknown Detection Probability and Clutter Rate. Sensors. 2018; 18269. 10.3390/s18010269
Blackman S. Multiple hypothesis tracking for multiple target tracking. IEEE Aerosp. Electron. Syst. Mag. 2004; 19: 5-18. 10.1109/MAES.2004.1263228
Musicki D., Evans R. Joint integrated probabilistic data association: JIPDA. IEEE Trans. Aerosp. Electron. Syst. 2004; 40: 1093-1099. 10.1109/TAES.2004.1337482
Roecker J. Multiple scan joint probabilistic data association. IEEE Trans. Aerosp. Electron. Syst. 1995; 31: 1204-1210. 10.1109/7.395216
Chong C.Y., Mori S., Reid D.B. Forty Years of Multiple Hypothesis Tracking. J. Adv. Inf. Fusion. 2019; 14: 131-153
Vo B.N., Mallick M., bar Shalom Y., Coraluppi S. III, Osborne R., Mahler R., Vo B.T.. Multitarget Tracking; Wiley: Hoboken, NJ, USA. 2015. 10.1002/047134608X.W8275
Reid D. An algorithm for tracking multiple targets. IEEE Trans. Autom. Control. 1979; 24: 843-854. 10.1109/TAC.1979.1102177
Bar-Shalom Y., Blackman S.S., Fitzgerald R.J. Dimensionless score function for multiple hypothesis tracking. IEEE Trans. Aerosp. Electron. Syst. 2007; 43: 392-400. 10.1109/TAES.2007.357141
Coraluppi S., Rago C., Carthel C., Bale B. Distributed MHT with Passive Sensors. Proceedings of the 2021 International Conference on Information Fusion. Sun City, South Africa. 1–4 November 2021
Mahler R.P.S.. Advances in Statistical Multisource-Multitarget Information Fusion; Artech House: Norwood, MA, USA. 2014
Moratuwage D., Adams M., Inostroza F. δ-Generalized Labeled Multi-Bernoulli Simultaneous Localization and Mapping with an Optimal Kernel-Based Particle Filtering Approach. Sensors. 2019; 192290. 10.3390/s19102290
Mahler R. Multitarget Bayes filtering via first-order multitarget moments. IEEE Trans. Aerosp. Electron. Syst. 2003; 39: 1152-1178. 10.1109/TAES.2003.1261119
Mahler R. PHD filters of higher order in target number. IEEE Trans. Aerosp. Electron. Syst. 2007; 43: 1523-1543. 10.1109/TAES.2007.4441756
Schlangen I., Delande E.D., Houssineau J., Clark D.E. A Second-Order PHD Filter With Mean and Variance in Target Number. IEEE Trans. Signal Process. 2018; 66: 48-63. 10.1109/TSP.2017.2757905
Vo B.T., Vo B.N., Cantoni A. The Cardinality Balanced Multi-Target Multi-Bernoulli Filter and Its Implementations. IEEE Trans. Signal Process. 2009; 57: 409-423. 10.1109/TSP.2008.2007924
Beard M., Vo B.T., Vo B.N. A Solution for Large-Scale Multi-Object Tracking. IEEE Trans. Signal Process. 2020; 68: 2754-2769. 10.1109/TSP.2020.2986136
Chen H., Kirubarajan T., Bar-Shalom Y. Performance limits of track-to-track fusion versus centralized estimation: Theory and application [sensor fusion]. IEEE Trans. Aerosp. Electron. Syst. 2003; 39: 386-400. 10.1109/TAES.2003.1207252
Yu Y., Hou Q., Zhang W., Zhang J. A Sequential Two-Stage Track-to-Track Association Method in Asynchronous Bearings-Only Sensor Networks for Aerial Targets Surveillance. Sensors. 2019; 193185. 10.3390/s19143185. 31331045
Lexa M., Coraluppi S., Carthel C., Willett P. Distributed MHT and ML-PMHT Approaches to Multi-Sensor Passive Sonar Tracking. Proceedings of the 2020 IEEE Aerospace Conference. Big Sky, MT, USA. 7–14 March 2020. 10.1109/AERO47225.2020.9172674
Shen K., Dong P., Jing Z., Leung H. Consensus-Based Labeled Multi-Bernoulli Filter for Multitarget Tracking in Distributed Sensor Network. IEEE Trans. Cybern. 2021: 1-12. 10.1109/TCYB.2021.3087521
Kazimierski W., Zaniewicz G. Determination of Process Noise for Underwater Target Tracking with Forward Looking Sonar. Remote Sens. 2021; 131014. 10.3390/rs13051014
Wang M., Qiu B., Zhu Z., Xue H., Zhou C. Study on Active Tracking of Underwater Acoustic Target Based on Deep Convolution Neural Network. Appl. Sci. 2021; 117530. 10.3390/app11167530
Li X., Lu B., Ali W., Jin H. Passive Tracking of Multiple Underwater Targets in Incomplete Detection and Clutter Environment. Entropy. 2021; 231082. 10.3390/e23081082. 34441221
Zhang Y., Lan J., Mallick M., Li X.R. Bearings-Only Filtering Using Uncorrelated Conversion Based Filters. IEEE Trans. Aerosp. Electron. Syst. 2021; 57: 882-896. 10.1109/TAES.2020.3034023
Mušicki D. Bearings only single-sensor target tracking using Gaussian mixtures. Automatica. 2009; 45: 2088-2092. 10.1016/j.automatica.2009.05.008
Do C.T., Nguyen T.T.D., Nguyen H.V. Robust multi-sensor generalized labeled multi-Bernoulli filter. Signal Process. 2022; 192: 108368. 10.1016/j.sigpro.2021.108368
Bar-Shalom Y., Li X.. Multitarget-Multisensor Tracking: Principles and Techniques; YBS Publishing: Storrs, CT, USA. 1995
Deb S., Pattipati K., Bar-Shalom Y. A multisensor-multitarget data association algorithm for heterogeneous sensors. IEEE Trans. Aerosp. Electron. Syst. 1993; 29: 560-568. 10.1109/7.210094
Chummun M., Kirubarajan T., Pattipati K., Bar-Shalom Y. Fast data association using multidimensional assignment with clustering. IEEE Trans. Aerosp. Electron. Syst. 2001; 37: 898-913. 10.1109/7.953245
Sathyan T., Sinha A., Kirubarajan T., Mcdonald M., Lang T. MDA-Based Data Association with Prior Track Information for Passive Multitarget Tracking. IEEE Trans. Aerosp. Electron. Syst. 2011; 47: 539-556. 10.1109/TAES.2011.5705690
Mallick M. A Note on Bearing Measurement Model. Mach. Eng. 2018. 10.13140/RG.2.2.13441.35681
Leung H. Neural network data association with application to multiple-target tracking. Opt. Eng. 1996; 35: 693-700. 10.1117/1.600661
Carrier J.Y., Litva J., Leung H., Lo T.K.Y. Genetic algorithm for multiple-target-tracking data association. Proceedings of the SPIE Conference on Acquisition, Tracking, Pointing. Orlando, FL, USA. 7 June 1996; Volume 2739. 10.1117/12.241914
Deb S., Yeddanapudi M., Pattipati K., Bar-Shalom Y. A generalized S-D assignment algorithm for multisensor-multitarget state estimation. IEEE Trans. Aerosp. Electron. Syst. 1997; 33: 523-538. 10.1109/7.575891
Poore A.B., Robertson A.J. A New Lagrangian Relaxation Based Algorithm for a Class of Multidimensional Assignment Problems. Comput. Optim. Appl. 1997; 8: 129-150. 10.1023/A:1008669120497
Bar-Shalom Y., Kirubarajan T., Li X.R.. Estimation with Applications to Tracking and Navigation; Wiley: New York, NY, USA. 2001
Uhlmann J.K. Covariance consistency methods for fault-tolerant distributed data fusion. Inf. Fusion. 2003; 4: 201-215. 10.1016/S1566-2535(03)00036-8
Uhlmann J. Introduction to the Algorithmics of Data Association in Multiple-Target Tracking. Handbook of Multisensor Data Fusion; CRC Press: Boca Raton, FL, USA. 2008Chapter 3. 10.1201/9781420053098.ch4
Collins J., Uhlmann J. Efficient gating in data association with multivariate Gaussian distributed states. IEEE Trans. Aerosp. Electron. Syst. 1992; 28: 909-916. 10.1109/7.256316
Klingner J., Ahmed N., Correll N. Fault-tolerant Covariance Intersection for localizing robot swarms. Robot. Auton. Syst. 2019; 122: 103306. 10.1016/j.robot.2019.103306
Coraluppi S., Carthel C., Coon A. An MHT Approach to Multi-Sensor Passive Sonar Tracking. Proceedings of the 2018 International Conference on Information Fusion. Cambridge, UK. 10–13 July 2018. 10.23919/ICIF.2018.8455402
]
By Zheng Wei; Zhansheng Duan; Yina Han and Mahendra Mallick
Reported by Author; Author; Author; Author