next up previous contents index
Next: 18.4.3 Algorithm Overview Up: 18.4.2 Tracking Techniques Previous: Single-Target Tracking

Multitarget Tracking

 

Given the preceding prescription for estimating the state of a single target from a sequence of two-dimensional observations, the central issue in multitarget tracking is that of associating observations with tracks or observations on one scan with those of a subsequent scan (e.g., in Figure 18.16, which x is paired with which o). There are, in a sense, two extreme schemes for attempting this trackhit association:

Track splitting:
All plausible associations of existing tracks with new data are maintained in the updated track file.
Optimal associations:
Only a single global association of tracks with incoming data is selected.

Each of these prescriptions has advantages and disadvantages.

The track splitting model is robust in the sense that the correct trackhit association is very likely to be generated and maintained at any step in track processing. The track extension task is also extremely ``localized,'' in the sense that splittings of any one track can be done independently of those for other tracks. This makes concurrent implementations of track splitting quite simple. The primary objections to track splitting are twofold:

  1. Track splitting does not provide an easily interperted ``answer'' as to the actual nature of the underlying scenario.
  2. Without (sometimes) elaborate mechanisms to identify and delete poor or duplicate entries in the track file, track splitting leads to an essentially exponential explosion in the track file size in dense target environments.
Track splitting is particularly useful at early times in the evolution of a target scenario, when the available data are too sparse to determine the ``correctness'' of any candidate track. As is discussed in more detail in Section 18.4.3, the primary role of Track Splitting in the Sim89 tracker is that of track initiation.

The optimal association prescription is orthogonal to track splitting in the sense that the single ``best'' pairing is maintained in place of all plausible pairings. This best TrackHit association is determined by a global optimization procedure, as follows. Let and be two lists of items (e.g., actual data and predicted data values). Let

 

be a cost for associating items and (e.g., the cartesian distance between predicted and actual data positions for the data coordinates defined above). The optimal association of the two lists is that particular permutation,

 

such that the total association score,

 

is minimized over all permutations of Equation 18.4.

Leaving aside, for now, the question of computational costs associated with the minimization of Equation 18.5, there are some fundamental difficulties associated with the use of optimal associators in multitarget tracking models. In particular

  1. Optimal associators perform poorly if the two lists and do not correspond to the same sets of underlying targets.
  2. Poor entries in the cost matrix can lead to global distortions of the globally optimal association.
The purely mathematical solution to the problem of minimizing Equation 18.5 need not be a reasonable solution to the problem of finding the best pairings of the two lists, and the points just noted are canonical failure modes by which blind optimal associations yield miserable solutions to ``real'' problems. Nonetheless, if one requires the ultimate output of the tracking function to be the single ``best guess'' as to the actual nature of the underlying target scenario, then some suitably massaged form of optimal association is clearly required.


next up previous contents index
Next: 18.4.3 Algorithm Overview Up: 18.4.2 Tracking Techniques Previous: Single-Target Tracking


Guy Robinson
Wed Mar 1 10:19:35 EST 1995