I. INTRODUCTION
Efficient Multisensor Fusion Using Multidimensional Data Associ atio n T. KIRUBARAJAN, Member, IEEE H. WANG Y. BAR-SHALOM, Fellow, IEEE
K. R. PATTIPATI, Fellow, IEEE University of Connecticut
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 (electronicallyscanned 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 - I 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 2 3), i.e., maximum time-depth (S - I ) 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.
Manuscript received May 2, 1998; revised July 27, 1999, September 26 and December 2, 2000; released for publication December 2, 2000. IEEE Log No. T-AES/37/2/06318. Refereeing of this contribution was handled by X. R. Li. This work was supported under AFOSR Grant F49620-97-1-0198 and ONR Grant N00014-97-1-0502. Authors’ address: Department of Electrical and Systems Engineering, University of Connecticut, Box U-157, Storrs, CT 06269-2157, E-mail: (
[email protected]). 0018-9251/01/$10.00 @ 2001 IEEE 386
In many target tracking problems, for example, large-scale air surveillance or ground target tracking with multiple targets, measurements can be obtained using multiple sensors. Typically, the sensors, which may be on stationary or mobile platforms, are distributed to increase the coverage of the surveillance region. The sensors may be heterogeneous and asynchronous with time-varying revisit intervals-that is, the sequence in which these sensors revisit the targets and the interval between two consecutive revisits can be arbitrary. This is the situation with electronically scanned array (ESA) radars. Under such conditions, how to use the measurements, which are obtained at different times from different sensors, in a target tracking system or estimator becomes an important question 17, 12, 13, 261. In a multitarget scenario such as, for example, air traffic control (ATC), one needs a mechanism to decide which of the received measurements in each frame’ (set or scan of measurements) is used to update a particular track. That is, data association becomes a crucial aspect in multitarget tracking because of the “competition” among tracks for the measurements 11, 2, 41. This becomes even more complex in multitarget-multisensor scenarios, where one has to solve the sensor fusion problem as well. One straightforward approach to data association is the nearest neighbor (NN) algorithm where the measurement closest to a track is used to update it. More advanced approaches include the joint probabilistic data association filter (JPDAF) [4] and the multiple hypothesis tracking (MHT) algorithm [6, 10, 11, 231. The JPDAF updates each track by evaluating the measurement-to-track association probabilities for the latest frame and combining the estimates based on the individual associations, whereas the MHT algorithm handles this by evaluating the probability under the hypothesis that there is a target given a sequence of associations, typically for a sliding window of several frames [4, 8, 14, 19, 231. The MHT, in order to avoid the exponential explosion of the hypotheses it carries, operates typically with a limited sliding window of sensor frames. The size of this window determines the time-depth within which the hypotheses are evaluated. In the multisensor situation, with each sensor frame being used as it arrives, this time-depth can decrease to zero if the number of sensors equals or exceeds the window length. Due to the extreme complexity of the MHT, this issue has not even been mentioned in the literature. Another class of data association algorithms is the measurement-to-track assignment, where ‘Assuming the measurement has no ID code (it is from a “noncooperative” target) or the code is not reliable.
IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 37, NO. 2 APRIL 2001
the measurements from one or more frames (lists) are associated with established tracks by solving a global constrained optimization problem [5, 9, 12, 16, 18, 20-22, 25, 271. In [27], a large-scale multisensor ATC problem was handled using an interacting multiple model (IMM) estimator combined with a 2-dimensional assignment algorithm. The particular scenario consisted of about 800 aircraft and five FAA radars, which were geographically distributed in the northeastern United States. The data association approach was centralized and used an S = 2 dimensional assignment-the latest frame of measurements from a sensor was associated with the global list of tracks, yielding nearly perfect results in that scenario. This civilian ATC problem, where the targets are well separated, appears not to need a higher dimensional assignment approach. Here, we use for the sensor fusionldata association algorithm a multidimensional assignment, where the last S - 1 (S 2 3) frames of measurements are associated with the track list (an S-dimensional assignment algorithm). The motivation for this is to use multisensor fusion in a dense scenario where the contention among tracks for measurements is high, while improving upon the performance of 2-D assignment. Higher dimensional data association yields better performance because it allows increased time-depth. The standard approach is to use the most recent S - 1 frames of measurements, irrespective of the originating sensor, i.e., the association is across the sensors to the track. While this fusion-across-sensors approach does not pose any problem in 2-D association, it can reduce the time-depth of the association to as little as zero if there are S sensors. In this case, the advantage of using multidimensional data association is lost due to the lack of time-depth. To remedy this shortcoming, a new approach to multidimensional data association in multisensor fusion is presented here. A procedure, which guarantees maximum effectiveness for an S-D association, i.e., maximum time-depth (S - 1) for each sensor without sacrificing the fusion across sensors, is presented. The proposed data association algorithm alternates from one sensor to another and updates the tracks using a special sliding window technique. This approach yields the largest possible time-depth, in addition to sensor-width, outperforming the standard association across sensors. This special sliding window technique applies also to the multisensor MHT. Furthermore, the S-D assignment is a systematic approach that avoids the exhaustive enumeration of all the feasible joint hypotheses carried out by most implementations of MHT.~ 2Recently some of the MHT implementations [24] adopted sequential use of the m-best 2-D assignment approach [lo] as an approximation to the S-D assignment.
In Section 11, the multitarget-multisensor tracking problem and the necessary notations are introduced. The new sensor fusion algorithm is presented in Section 111. Automatic track formation, maintenance, and termination in the multitarget-multisensor, multidimensional-assignment framework are also discussed. Estimation results are given and compared with those of the standard multidimensional fusion-across-sensors algorithm in Section IV. Performance measures for comparing these algorithms are also given.
I I. MULTITARGET-MULTISENSOR TRACKING PROBLEM
The measurements are obtained from L asynchronous and geographically distributed sensors with time-varying revisit intervals (e.g., ESA radars). The measurements in each frame (sensor scan) can have different time stamps. The kth frame (k is a global index) consisting of M,(k) measurements is denoted by M,(k), where 1 = 1,. ..,L is the sensor used to obtain the measurements. The individual measurements in frame k are denoted by ~,,,~(t,~), mk = 1,. .. ,M,(k), where tmkis the time stamp of the m,th measurement of sensor 1. For example, with L = 2 , the latest frames are (backwards) M,(k),M,(k - I), M 2 ( k- 2),M,(k - 3), etc. Frame M2(k - 2 ) from sensor 2 is the one just before M2(k). The track list consisting of N ( k ) tracks after processing the measurements in M,(k) is denoted by I@). Each track %(IC), n = 1,.. . , N ( k ) in 7 ( k ) is represented by its “sufficient statistics” which best summarize the information content of the measurements M,, (I), ...,M,,(k). In the case of the IMM estimator, the sufficient statistics consist of a track-update time stamp tmk, mode-conditioned state estimates i,Jt,,,,), associated covariances P,,,(t,,) and the mode probabilities ~ ~ , ~ ( [3]. t , ~That ) is,
q k ) = { t , k , ~ ~ , ~ ( t ~ ~ ) , ~ , ~ (r ~= ~L...,R k ) , ~1~ n , ~ ( t ~ ~ ) ; (1)
where r = 1,...,R is the index of the ith IMM filter module. Alternatively, with the standard Kalman filter as the estimator, one has
%( k ) = Ifmk i,(tmk 7
)?
w,, 1).
(2)
A sample scenario from the large-scale ground target tracking problem, which motivated this work, is shown in Fig. 1. The scenario includes about 120 ground targets moving in different groups and 4 moving target indicator (MTI) sensors mounted on airborne platforms. Each target group consists of 10-15 targets traveling in a single file. The measurements consist of two-dimensional positions and the range rate. The measurements from different sensors are obtained asynchronously (with different
KIRUBARAJAN ET AL.: EFFICIENT MULTISENSOR FUSION USING MULTIDIMENSIONAL DATA ASSOCIATION
387
160-
Q
140-
1200
100-
E
r 80> 0
60 -
40 0
20 -
“0
20
40
60
BO X (W
100
120
140
160
Fig. 1. Sample multisensor-multitarget tracking scenario. target group trajectories (10-15 targets per group), . . . ’ . sensor trajectories, o trajectory initial points. ~
sampling intervals) and different measurements within the same frame from a sensor have different time stamps. Ill. MULTISENSOR FUSION USING ASSIGNMENT A.
Standard 5-D Assignment Across Sensors
The standard approach of data association via S-D assignment associates the latest S - 1 frames of measurements with the track list, irrespective of the originating sensor. When frame k is received, the association is performed between the track list (sufficient statistics) 7 ( k - S + 1 ) and frames M,-,+,(k - S + 2), ...,M,,(k). In this standard approach, the association is performed acruss sensors with the resulting time-depth being reduced. For example, with S = 3 and L = 2 sensors, one has M,(k), M,(k - 1) and 7 ( k - 2 ) . Note that ’T(k - 2 ) will have incorporated the previous frames (up to M,(k - 2 ) ) from sensors 2 and 1. Thus, with reference to M,(k) it has a time-depth of 1 only. Thus, the standard approach sacrifices time-depth (which could be S - 1 = 2 ) due to the sensor-width. We shall present in the sequel an approach that guarantees the maximum time-depth S - 1 regardless of the number of sensors. When frame M,,(k) is received, the sufficient statistics have incorporated the frame up to and including k - S + 1, and an S-D association between 7 ( k - S + 1) and frames M,,-?+?(k- S + 2),. ..,M,,(k) (the frames covered by the sliding window) is performed. Using the assignment results between the track list 7 ( k - S + 1) and the measurement 388
list Mlk-S+Z(k - S + 2), the sufficient statistics are updated to k - S + 2, i.e., with one frame only. That is, each track in 7 ( k - S + 1) is updated to the time stamp of the associated measurement in Mlk;S+2(k - S + 2 ) . When the next frame k + 1 is received, the window is advanced to cover frames Mlk-S+3(k - S + 3), . . .,Mlk+l ( k + 1) and the association is performed between I ( k - S + 2) and - S + 3), . ..,Mlk+,(k + l), and so on. In this sliding window approach, the sufficient statistics 7 ( k - S + 2) represent the track estimates that are frozen after processing frame Ml,(k)-these sufficient statistics are fixed and remain unchanged irrespective of subsequent measurements. While after processing frame M,, ( k ) , the association between 7 ( k - S + 1) and Mlk-S+2(k - S + 2) is a hard decision, the associations of frames M,,_,+,(k- S + 3), ...,MLk(k) are only tentative and can be changed in light of subsequent measurements. It is this soft-decision capability that gives multidimensional data association the advantage over 2-D assignment. Note that m-best MHT implementations also have this soft-decision capability [ 10, 241. In Fig. 2, the standard S-D data association across sensors using the sliding window approach is illustrated. Note that in this standard approach no distinction is made between the frames from different sensors, and, therefore, the frame list, which is associated with the track, is a single array of frames from all the sensors. The above S-D data association is formulated as a constrained global optimization problem, where the objective is to minimize the total “cost” of associating (or not associating) a particular sequence of measurements in frames Mlr-s+z(k - S + 2), . . .,M,,(k) to the tracks in 7 ( k - S + 1). The constraints, which are due to the physics of the problem, are as follows.
1) Associations are allowed only between a track and at most one of its validated3 measurements in each frame in the window. The constraint that each track be associated with at most one measurement from each frame assumes nonmultiplicity of target-originated measurements within a frame. 2) Each measurement in a frame is associated with at most one track, which assumes that the targets are nonoverlapping, i.e., the sensor resolution is better than target separation. These two constraints mean “one-to-one” association, i.e., one measurement per track and vice versa, which is reasonable for nonoverlapping targets. For overlapping targets, one-to-many and many-to-one associations are more appropriate [ 161. 3Validation,which is carried out as in [4,271, is required to limit the number of candidate associations and to prevent physically unlikely associations.
IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 37, NO. 2 APRIL 2001
(d)
Fig. 2. Standard S-D data association across multiple sensors (m track sufficient statistics, o measurement scans, - - - associations. - S + 2 ) , .. . ,Mlk(k).(b) S-D association between (a) Initial track sufficient statistics T ( k - S + 1) and measurement scans Mlk-S+Z(k I ( k - S + 1) and Mlk-s+Z(k - S + 2), . ,Mlk(k).(c) Updated sufficient statistics T(k - S + 2). (d) S-D association between T ( k - S + 2) and Mlk_s+3(k - S + 3),. . . ,Mlk+l ( k + 1) in the next revisit. I .
3) When a target is not associated with any of the measurements in a frame, say frame k , it is said to be associated with the "dummy" measurement (m, = 0) from that frame. The notion of "dummy" measurement represents missed detections. The dummy measurement in a frame can be associated with any number of tracks. That is, the number of tracks with no associations to the measurements in a certain frame is not restricted. 4) When a measurement in a frame is not associated with any track, is it said to be associated with the "dummy" track (n = 0), which represents a nonexisting track. Such a measurement will be deemed as false if it does not start a new track by the time the window slid past it. The dummy track can be associated with any number of measurements within a frame.
{ m s ) L + 2 3n ) is the joint likelihood that and the S - 1-tuple of measurements zl , (t,,), j = k I S + 2,. ..,k originated from the target represented by track I , ( k - S + 1). The likelihood that the same S - 1 -tuple of measurements are false is given by $(k, {m,)t=kpS+2r0),where n = 0 corresponds to the dummy track. The association likelihoods are given by
To specify the constrained optimization problem more formally, define the binary assignment variable a@,{ms):=k-S+p") such that
where (V,(j))-', j = k - S + 2,. ..,k is the spatial false alarm density in revisit j , Po is the detection probability of target-originated measurements, u(m)
4 k {ms):=,-S+2,n) =
and a cost given by
G
3
I 3
4(k,{ms):=k-S+Z>n) [l - P~]l-"(ms)[pnA(s,m~,n)]u(m~) n >0 -
c=k-S+Z
n=O
(5)
measurements ~ ~ , , , ~ ( t ,j ~=) ,k - S + 2,. ..,k are assigned to track I , ( k otherwise
1 0
c(k,{ms}t=k.s+2,n) associated with (3)
(g
;;;j=*s+2.n)
~(k,{m,)t=~-~+ = ~-1n ,n)
s
s=k-S+2'0)
-
S + 1) (3)
is a binary function such that u(m) =
)
ms = 0,. ..,M ( s ) ; s = k - S + 1,. . . ,k; n>O
d
(4)
{
1
m>O
0
m=O
(6)
and A(j,m,n), j = k - S + 2,. ..,k is the filtercalculated likelihood when measurement zl,(t,,) is associated with track I,(k - S + 1). The filter-calculated likelihoods A( .) are the IMM estimator likelihood functions evaluated as in [17, 271.
KIRUBARAJAN ET AL.: EFFICIENT MULTISENSOR FUSION USING MULTIDIMENSIONAL DATA ASSOCIATION
389
A complete set of valid associations satisfying all the constraints for each track in 7 ( k - S) and for each measurement in Ml,-,+,(k- S + l),...,Ml,(k) is denoted by a(k), i.e.,
klk-, is the frame number to which the track list was last updated (when frame Mlk-l(k- 1) from sensor Ik-1 was processed in the previous cycle). That is, 7 ( k l i - 1 )is the track list that includes all the frames (from all the sensors) prior to the S - 1 oldest frames a(k) = {a(k,{ms}t=k-s+2,n); ms = & I , . . . ,M,,“(s); of sensor 1, (the tail end of the window). Based on the association between ) and measurement frame s = k - S + 2,..., k; n = 0,1, ...,N ( k - S + l)} at the tail of the sliding window, each track is updated (7) to the time of the tail of the window. When the next where a(.) satisfy the constraints discussed above. The frame M,+, ( k + 1) from sensor lk+l is received, the cost of the complete set of associations a(k) is given association is between the latest S - 1 frames from bv sensor lk+l and the above updated track list. The approach is first illustrated in Fig. 3 for L = 3 sensors and described in detail later. n= 1 mk-S+.2=O mi-s+3=0 mk=o While Fig. 3 shows a “clean” scenario where k each sensor sends in the measurements in turn, a(k, {m,7}t=k-S+2)n)c(k7 {ms)s=k-S+2,n ) . a real multisensor tracking system can be quite (8) arbitrary-different sensors may have different Then, the objective of the S-D assignment is to find revisit intervals and the sensor order may not be the best set of associations, denoted by a*(k),with the sequential, i.e., one may not cycle through the lowest cost, i.e., sensors in a predetermined order. Also, there may be out-of-sequence measurements, in which case a a*(k)= argminC(k I a(k)) (9) a(k) frame with an earlier time stamp is received at the fusion center later than a frame with a more recent which is solved (nearly optimally with quantifiable time stamp [27]. Out-of-sequence measurements optimality via the duality gap) using the generalized are common in multisensor tracking systems S-D assignment algorithm with Lagrangian relaxation where the measurements are received in batches [5, 12, 20, 221. at the fusion center. Another issue is systematic track maintenance: in a dynamic tracking problem B. Maximum Time-Depth S-D Assignment new targets can enter or existing ones leave the surveillance region at any time. Thus, one needs a One major drawback of the above standard systematic approach for automatic track initiation, multidimensional fusion-across-sensors scheme is track maintenance, and track termination within that the advantage of time-depth, which provides the multitarget-multisensor-multidimensional the motivation for multidimensional data association assignment framework, considering all the multisensor in the first place, is, as discussed above, reduced idiosyncrasies. or, possibly, even lost. The time-depth is important In order to derive the maximum-depth multisensor because it requires some time for a target maneuver fusion algorithm using multidimensional assignment, to manifest itself through the measurements. In fact, define the following. it is shown later in Section IV that increasing the dimension of data association could even degrade Frame: List of measurements from a sensor, the performance of the standard multisensor fusion obtained at nearly the same time. Different approach (due to its “brute force” nature). Therefore, measurements within a frame may have slightly in fusing multisensor data using multidimensional data different time stamps due to the delay in radar association, it is vital to preserve the time-depth for processing. any sensor-width. Frame List: List of the latest S - 1 frames from A new approach which yields the maximum the same sensor (there will be L such lists). time depth, while maintaining the advantages of Track List: Global list of firm tracks with full multisensor fusion (sensor-width) is presented next. state estimates. Thus, the track list contains the tracks The idea is to perform the data association within each which have had at least two associations between sensor’s maximum number of consecutive frames. When measurements from different frames from the same the measurements are received at the fusion center, or different sensors. the frames are separated based on the originating Initial Track List: Global list of initial tracks sensor. The estimator alternates from one sensor to with initial estimates (typically position-only), i.e., another, performing S-D association to update the tracks which consist of only one measurement. These tracks using the sliding window approach. When the tracks do not yet have velocity estimates, which are latest frame of measurements M,,(k) is received from assumed to be zero. When an initial track gets another sensor I, the association is between the latest S - 1 association with a measurement, it becomes a regular frames from sensor 1, and the track list 7(k,k_l) where track, because then it will have a velocity estimate. 390
IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 37, NO. 2 APRIL 2001
...... 0
1 1
w
W 1
1
i)
Ma(k+l)
0
" " "
...... 0
M i ( k t 2)
0
" " "
(e) Fig. 3. Maximum-depth multisensor fusion using S-D assignment (a track sufficient statistics, o measurement scans, - - associations). (a) Sufficient statistics (a) and measurements (0).(b) Assignment using measurements from sensor 3. (c) Assignment using measurements from sensor 2. (d) Assignment using measurements from sensor 1. (e) Updated sufficient statistics.
Now, assuming L sensors in the system, define a track list 'T(kl,-,),which lags the latest (kth) frame M1, from sensor I, by S - 1 frames of this sensor, an initial track list Zand L different frame lists corresponding to each sensor, denoted by Fj, i= 1,....L. These are illustrated in Fig. 4. The frame of measurements in slot j of is denoted by
