13 Data Association Using Multiple-Frame Assignments

The ever-increasing demand in surveillance is to produce highly accurate target identification and estimation in real time, even for dense target scenarios and in regions of high track contention. Past surveillance sensor systems have relied on individual sensors to solve this problem; however, current and future needs far exceed single sensor capabilities. The use of multiple sensors, through more varied information, has the potential to greatly improve state estimation and track identification. Fusion of information from multiple sensors is part of a much broader subject called data or information fusion, which for surveillance applications is defined as a multilevel, multifaceted process dealing with the detection, association, correlation, estimation, and combination of data and information from multiple sources to achieve refined state and identity estimation, and complete and timely assessments of situation and threat.¹ (A comprehensive discussion can be found in Waltz and Llinas.¹) Level 1 deals with single- and multisource information, involving tracking, correlation, alignment, and association by sampling the external environment with multiple sensors and exploiting other available sources. Numerical processes thus dominate level 1. Symbolic reasoning involving various techniques from artificial intelligence permeates levels 2 and 3.¹

Within level 1 fusion, architectures for single- and multiple-platform tracking must also be considered. These are generally delineated into centralized, distributed, and hybrid architectures,^{2, 3 and 4} each with its advantages and disadvantages. The architecture most appropriate to the current development is that of a centralized tracking, wherein all measurements are sent to one location and processed with tracks being transmitted back to the different platforms. This architecture is optimal in that it is capable of producing the best track quality (e.g., purity and accuracy) and a consistent air picture.^3,4 Although this architecture is appropriate for single-platform tracking, it may be unacceptable for multiple-platform tracking for several reasons. For example, communication loading and the single-point failure problems are important shortcomings. However, this architecture does provide a baseline against which other architectures should be compared. The case of distributed data association is discussed further in Section 13.6.

The methods for centralized tracking follow two different approaches: single-frame and multiple-frame processing. The three basic methods in single-frame processing are nearest neighbor, joint probabilistic data association (JPDA), and global nearest neighbor. The nearest neighbor works well when the objects are all far apart and with infrequent clutter. The JPDA works well for a few targets in moderate clutter, but is computationally expensive and may corrupt the target recognition or discrimination information.⁵ The global nearest neighbor approach is posed as a two-dimensional assignment problem (for which there are algorithms that solve the problem optimally in polynomial time) and it has been successful for cases of moderate target density and light clutter.

Deferred logic techniques consider several data sets or frames of data all at once in making data association decisions. At one extreme is batch processing in which all observations (from all time) are processed together. This method is too computationally intensive for real-time applications. The other extreme is sequential processing. This chapter examines deferred logic methods that fall between these two extremes. The most popular deferred logic method used to track large numbers of targets in low-to-moderate clutter is called multiple-hypothesis tracking (MHT) in which a tree of possibilities is built, likelihood scores are assigned to each track, an intricate pruning logic is developed, and the data association problem is solved using an explicit enumeration scheme. The use of these enumeration schemes to solve this nondeterministic polynomial (NP)-hard combinatorial optimization problem in real time is inevitably faulty in dense scenarios, because the time required to solve the problem optimally can grow exponentially with the size of the problem.

Over the past 10 years a new formulation and class of algorithms for data association have proven to be superior to all other deferred logic methods.^{3,6, 7, 8, 9, 10, 11, 12 and 13} This formulation is based on multidimensional assignment problems and the algorithms, on Lagrangian relaxation. The use of combinatorial optimization in multitarget tracking dates back to the pioneering work of Morefield,¹⁴ who used integer programming to solve set packing and covering problems arising from a data association problem. MHT has been popularized by the fundamental work of Reid.¹⁵ These works are further discussed in Blackman and Popoli,³ Bar-Shalom and Li,⁵ and Waltz and Llinas,¹ all of which also serve as excellent introductions to the field of multitarget tracking and multisensor data fusion. Bar-Shalom and coworkers^{16, 17, 18, 19 and 20} have also formulated sensor fusion problems in terms of these multidimensional assignment problems and have developed algorithms, as discussed in Section 13.4.

The performance of any tracking system is dependent on a large number of components. Having one component that is superior to all others does not guarantee a superior tracking system. To address some of these other issues, this chapter provides a brief overview of the many issues involved in the design of a tracking system, placing the problem within the context of the more general surveillance and fusion problem in Section 13.2. The formulation of the problem is presented in Section 13.3, and an overview of the Lagrangian relaxation–based methods appears in Section 13.4. Section 13.5 contains a summary of some opportunities for future investigation.

13.2 Problem Background

A question that often arises is that of the difference between air traffic control and surveillance. In the former, planes, through their beacon codes, generally identify themselves so that observations can be associated with the correct plane; whereas in surveillance, the objects being tracked do not identify themselves, requiring a figure of merit to be derived for the association of a sequence of observations to a particular target. The term target is used rather than object. This chapter addresses surveillance needs and describes the use of likelihood ratios for track association.

The targets under consideration are classified as point or small targets; measurements or observations of these targets are in the form of kinematic information, such as range, azimuth, elevation, and range rate. Future sensor systems will provide additional features or attribute information.³

A general surveillance problem involves the use of multiple platforms, such as ships, planes, or stationary ground-based radar systems, on which one or more sensors are located for tracking multiple objects. Optimization problems permeate the field of surveillance, particularly in the collection and fusion of information. First, there are the problems of routing and scheduling surveillance platforms and then dynamically retasking the platforms as more information becomes available. For each platform, the scarce sensor resources must be allocated and managed to maximize the information returned. The second area, information fusion, is the subject of this chapter.

Many issues are involved in the design of a fusion system for multiple surveillance platforms, such as fusion architectures, communication links between sensor platforms, misalignment problems, tracking coordinate systems, motion models, likelihood ratios, filtering and estimation, and the data association problem of partitioning reports into tracks and false alarms. The recent book, Design and Analysis of Modern Tracking Systems, by Blackman and Popoli³ presents an excellent overview of these topics and also puts forward an extensive list of other references.

One aspect of surveillance that is seldom discussed in the literature is the development of data structures required to put all of this information together efficiently. In reality, a tracking system is generally composed of a dynamic search tree that organizes this information and recycles the memory for real-time processing. However, the central problem is the data association problem.

To place the current data association problem within the context of the different architectures of multiple-platform tracking, a brief review of the architectures is helpful. The first architecture is centralized fusion, in which raw observations are sent from the multiple platforms to a central processing unit where they can be combined to give superior state estimation (compared to sensor-level fusion).³ At the other extreme is track fusion, wherein each sensor forms tracks along with the corresponding statistical information from its own reports and then sends this preprocessed information to a processing unit that correlates the tracks. Once the correlation is complete, the tracks can be combined and the statistics can be modified appropriately. In reality, many sensor systems are hybrids of these two architectures, in which some preprocessed data and some raw data are used and switches between the two are possible. A discussion of the advantages and disadvantages of these architectures is presented in the Blackman and Popoli book.³ The centralized and hybrid architectures are most applicable to the current data association problem.

13.3 Assignment Formulation of Some General Data Association Problems

The goal of this section is to formulate the data association problem for a large class of multiple-target tracking and sensor fusion applications as a multidimensional assignment problem. This development extracts the salient features and assumptions that occur in a large class of these problems and is a brief update to an earlier work.²¹ A general class of data association problems was posed as set packing problems by Morefield¹⁴ in 1977. Using an abstract view of Morefield’s work to include set coverings, packings, and partitionings, this section proceeds to formulate the assignment problem.

In tracking, a common surveillance challenge is to estimate the past, current, or future state of a collection of targets (e.g., airplanes in the air, ships on the sea, or automobiles on the ground) from a sequence of scans of the surveillance region by one or more sensors. This work specifically addresses small targets²² for which the sensors generally supply kinematic information such as range, azimuth, elevation, range rate, and some limited attribute or feature information.

Suppose that one or more sensors, either colocated or distributed, survey the surveillance region and produce a stream of observations (or measurements), each with a distinct time tag. These observations are then arranged into sets of observations called frames of data. Mathematically, let $Z (k) = {z_{i_{k}}^{k}}_{i_{k}}^{M_{k}} = 1$ $Z (k) = {z_{i_{k}}^{k}}_{i_{k}}^{M_{k}} = 1$ denote the kth frame of data, where each $Z_{l_{k}}^{k}$ $Z_{l_{k}}^{k}$ is a vector of noise-contaminated observations with an associated time tag $t_{i_{k}}^{k}$ $t_{i_{k}}^{k}$ . The index k represents the frame number and i_k represents the i_kth observation in frame k. An observation in the frame of data Z(k) may emanate from a true target or may be a false report.

This discussion assumes that each frame of data is a proper frame, in which each target is seen no more than once. For a rotating radar, one sweep or scan of the field of view generally constitutes a proper frame. For sensors such as electronically scanning phased array radar, wherein the sensor switches from surveillance to tracking mode, the partitioning of the data into proper frames of data is interesting as there are several choices. More efficient partitioning methods would be addressed in the forthcoming work.

The data association problem is that of determining which observations or sensor reports emanate from which targets and which reports are false alarms. The combinatorial optimization problem that governs a large number of data association problems in multitarget tracking and multisensor data fusion^{1,3,5,6,11, 12, 13 and 14,17, 18, 19 and 20,23} is generally posed as

Maximize

\begin{matrix} {p (Γ = γ | Z^{N}) | λ \in Γ^{*}} & (13.1) \end{matrix}

$\begin{matrix} {p (Γ = γ | Z^{N}) | λ \in Γ^{*}} & (13.1) \end{matrix}$

where Z^N represents N data sets (Equation 13.2), γ is a partition of indices of the data (Equations 13.3 and 13.4a, 13.4b, 13.4c and 13.4d), Γ^* the finite collection of all such partitions (Equations 13.4a, 13.4a, 13.4b, 13.4c and 13.4d), Γ a discrete random element defined on Γ^*, γ⁰ a reference partition, and P(Γ = γ|Z^N) the posterior probability of a partition γ being true given the data Z^N. Each of these terms must be defined. The objective then is to formulate a reasonably general class of these data association problems (Equation 13.1) as multidimensional assignment problems (Equation 13.15).

In the surveillance example, the data sets were observations of the objects in the surveillance region, including false reports. Including more general types of data, such as tracks and track-observation combinations, as well as observations, Reid¹⁵ used the term reports for the contents of the data sets. Thus, let Z(k) denote a data set of M_k reports ${z_{i_{k}}^{k}}_{i_{k}}^{M_{k}} = 1$ ${z_{i_{k}}^{k}}_{i_{k}}^{M_{k}} = 1$ , and Z^N the cumulative data set of N such sets defined, respectively, by

\begin{matrix} Z (k) = {z_{i_{k}}^{k}}_{i_{k}}^{M_{k}} = 1 & and & Z^{N} = {Z (1), ..., Z (N)} & (13.2) \end{matrix}

$\begin{matrix} Z (k) = {z_{i_{k}}^{k}}_{i_{k}}^{M_{k}} = 1 & and & Z^{N} = {Z (1), ..., Z (N)} & (13.2) \end{matrix}$

In multisensor data fusion and multitarget tracking, the data sets Z(k) may represent different classes of objects. For track initiation in multitarget tracking, the objects are observations that must be partitioned into tracks and false alarms. In this formulation of track maintenance (Section 13.4), one data set is comprised of tracks and the remaining data sets include observations that are assigned either to existing tracks, false observations, or observations of new tracks. In sensor-level tracking, the objects to be fused are tracks.¹ In centralized fusion,^1,3 the objects can all be observations that represent targets or false reports, and the problem is to determine which observations emanate from a common source.

The next task is to define what is meant by a partition of the cumulative data set, Z^N, in Equation 13.2. Because this definition is independent of the actual data in the cumulative data set Z^N, a partition of the indices in Z^N must first be defined. Let

\begin{matrix} 1^{N} = {I (1), I (2), ..., I (N)}, & Where I (k) = {i_{k}}_{i_{k}}^{M_{k}} = 1 & (13.3) \end{matrix}

$\begin{matrix} 1^{N} = {I (1), I (2), ..., I (N)}, & Where I (k) = {i_{k}}_{i_{k}}^{M_{k}} = 1 & (13.3) \end{matrix}$

denote the indices in the data sets (Equation 13.2). A partition γ of I^N and the collection of all such partitions Γ∗ are defined by

\begin{matrix} γ = {γ_{1}, ..., γ_{n (γ)} | γ_{i} \neq \emptyset for each i} & (13.4 a) \end{matrix}

$\begin{matrix} γ = {γ_{1}, ..., γ_{n (γ)} | γ_{i} \neq \emptyset for each i} & (13.4 a) \end{matrix}$

\begin{matrix} γ_{i} \cap γ_{j} = \emptyset for i \neq j & (13.4 b) \end{matrix}

$\begin{matrix} γ_{i} \cap γ_{j} = \emptyset for i \neq j & (13.4 b) \end{matrix}$

\begin{matrix} I^{N} = \cup_{j = 1}^{n (γ)} γ_{j} & (13.4 c) \end{matrix}

$\begin{matrix} I^{N} = \cup_{j = 1}^{n (γ)} γ_{j} & (13.4 c) \end{matrix}$

\begin{matrix} Γ^{*} = {γ | γ satisfies Equations 13.4a and 13.4b} & (13.4 d) \end{matrix}

$\begin{matrix} Γ^{*} = {γ | γ satisfies Equations 13.4a and 13.4b} & (13.4 d) \end{matrix}$

Here, γ_i ⊂ I^N in Equation 13.4a will be called a track, so that n(γ) denotes the number of tracks (or elements) in the partition γ. A γ ∈ Γ∗ is called a set partitioning of the indices I^N, if the properties in Equations 13.4a, 13.14b and 13.4c are valid; a set covering of I^N, if the property in Equation 13.4b is omitted, but the other two properties in Equations 13.4a and 13.4c are retained; and a set packing if the property in Equation 13.4c is omitted, but Equations 13.4a and 13.4b are retained.²⁴ A partition γ ∈ Γ∗ of the index set I^N induces a partition of the data Z^N via

\begin{matrix} Z_{γ} = {Z_{γ_{1}}, ..., Z_{γ n (γ)}} & where Z_{γ_{i}} \subset Z^{N} & (13.5) \end{matrix}

$\begin{matrix} Z_{γ} = {Z_{γ_{1}}, ..., Z_{γ n (γ)}} & where Z_{γ_{i}} \subset Z^{N} & (13.5) \end{matrix}$

Clearly, Z_γi ∩ Z_γj = ∅ for i ≠ j and $Z^{N} = \cup_{j = 1}^{n (γ)} Z γ_{i}$ $Z^{N} = \cup_{j = 1}^{n (γ)} Z γ_{i}$ . Each Z_γ is considered to be a track of data. Note that a Z_γi need not have observations from each frame of data, Z(k), but it must, by definition, have at least one observation.

Under several independence assumptions between tracks,²¹ a probabilistic framework can be established in which

\begin{matrix} P (Γ = γ | Z^{N}) = \frac{C}{p (Z^{N})} \underset{γ_{i} \in γ}{Π} p (Z_{γ_{i}}) G (γ_{i}) & (13.6) \end{matrix}

$\begin{matrix} P (Γ = γ | Z^{N}) = \frac{C}{p (Z^{N})} \underset{γ_{i} \in γ}{Π} p (Z_{γ_{i}}) G (γ_{i}) & (13.6) \end{matrix}$

where C is a constant and G is a function. This completes the formulation of the general data association problem as presented in the works of Poore²¹ and Morefield.¹⁴

The next objective is to refine this formulation in a way that is amenable to the assignment problem. For notational convenience in representing tracks, add a zero index to each of the index sets I(k) (k = 1, …, N) in Equation 13.3 and a dummy report $z_{0}^{k}$ $z_{0}^{k}$ to each of the data sets Z(k) in Equation 13.2, and require that each

\begin{matrix} γ_{i} = (i_{1}, ..., i_{N}) & (13.7) \\ Z_{γ_{i}} = Z_{i_{1} ... i_{n}} \equiv (z_{i_{1}}^{1}, ... z_{i_{N}}^{N}) \end{matrix}

$\begin{matrix} γ_{i} = (i_{1}, ..., i_{N}) & (13.7) \\ Z_{γ_{i}} = Z_{i_{1} ... i_{n}} \equiv (z_{i_{1}}^{1}, ... z_{i_{N}}^{N}) \end{matrix}$

where i_k and $z_{i_{k}}^{k}$ $z_{i_{k}}^{k}$ can assume the values of 0 and $z_{0}^{k}$ $z_{0}^{k}$ , respectively. The dummy report $z_{0}^{k}$ $z_{0}^{k}$ serves several purposes in the representation of missing data, false reports, initiating tracks, and terminating tracks. If Z_γi is missing an actual report from the data set Z(k), then γ_i = (i₁, …, i_k−1, 0, i_k+1, …, i_N) and $Z_{γ_{i}} = {z_{i_{1}}^{1}, ..., z_{k - 1}^{k - 1}, z_{i_{k}}^{k}, z_{0}^{k}, z_{i_{k + 1}}^{k + 1}, ..., z_{i_{N}}^{N}}$ $Z_{γ_{i}} = {z_{i_{1}}^{1}, ..., z_{k - 1}^{k - 1}, z_{i_{k}}^{k}, z_{0}^{k}, z_{i_{k + 1}}^{k + 1}, ..., z_{i_{N}}^{N}}$ . A false report $z_{i_{k}}^{k} (i_{k} > 0)$ $z_{i_{k}}^{k} (i_{k} > 0)$ is represented by γ_i = (0, …, 0, i_k, 0, …, 0) and $Z_{γ_{i}} = {z_{0}^{1}, ..., z_{0}^{k - 1}, z_{i_{k}}^{k}, z_{0}^{k + 1}, ..., z_{0}^{N}}$ $Z_{γ_{i}} = {z_{0}^{1}, ..., z_{0}^{k - 1}, z_{i_{k}}^{k}, z_{0}^{k + 1}, ..., z_{0}^{N}}$ , in which there is only one actual report. The partition γ⁰ of the data in which all reports are declared to be false reports is defined by

\begin{matrix} Z_{γ^{0}} = {Z_{0...0 i_{k} 0...0} \equiv (z_{0}^{1}, ..., z_{0}^{k - 1}, z_{i_{k}}^{k}, z_{0}^{k + 1}, ..., z_{0}^{N}) | i_{k} = 1, ..., M_{k} k = 1, ..., N} & (13.8) \end{matrix}

$\begin{matrix} Z_{γ^{0}} = {Z_{0...0 i_{k} 0...0} \equiv (z_{0}^{1}, ..., z_{0}^{k - 1}, z_{i_{k}}^{k}, z_{0}^{k + 1}, ..., z_{0}^{N}) | i_{k} = 1, ..., M_{k} k = 1, ..., N} & (13.8) \end{matrix}$

If each data set, Z(k), represents a “proper frame” of observations, a track that initiates on frame m > 1 will contain only the dummy report $z_{0}^{k}$ $z_{0}^{k}$ from each of the data sets, Z(k), for each k = 1, …, m − 1. Likewise, a track that terminates on frame m would have only the dummy report from each of the data sets for k > m. These representations are discussed further in Section 13.3 for both track initiation and track maintenance.

The use of the 0–1 variable

\begin{matrix} z_{i_{1}, ... i_{N}} = {\begin{matrix} 1 & if (i_{1}, ..., i_{N}) \in γ \\ 0 & otherwise \end{matrix} & (13.9) \end{matrix}

$\begin{matrix} z_{i_{1}, ... i_{N}} = {\begin{matrix} 1 & if (i_{1}, ..., i_{N}) \in γ \\ 0 & otherwise \end{matrix} & (13.9) \end{matrix}$

yields an equivalent characterization of a partition (Equations 13.4a, 13.4b, 13.4c and 13.4d and 13.7) as a solution of the equations:

\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{k - 1} = 0}^{M_{k - 1}} \sum_{i_{k + 1} = 0}^{M_{k + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & (13.10) \end{matrix}

$\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{k - 1} = 0}^{M_{k - 1}} \sum_{i_{k + 1} = 0}^{M_{k + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & (13.10) \end{matrix}$

With this characterization of a partition of the cumulative data set Z^N as a set of equality constraints (Equation 13.10), the multidimensional assignment problem can then be formulated.

Observe that for γ_i = (i₁, …, i_N), as in Equation 13.7, and the reference partition (Equation 13.8),

\begin{matrix} \frac{P (Γ = γ | Z^{N})}{P (Γ = γ^{0} | Z^{N})} \equiv L_{γ} \equiv \underset{(i_{1}, ..., i_{N}) \in γ}{Π} L_{i_{1} ... i_{N}} & (13.11) \end{matrix}

$\begin{matrix} \frac{P (Γ = γ | Z^{N})}{P (Γ = γ^{0} | Z^{N})} \equiv L_{γ} \equiv \underset{(i_{1}, ..., i_{N}) \in γ}{Π} L_{i_{1} ... i_{N}} & (13.11) \end{matrix}$

where

\begin{matrix} L_{i_{1} ... i_{N}} = \frac{p (Z_{i_{i} ... i_{N}}) G (Z_{i_{1} ... i_{N}})}{Π p (Z_{0...0 i_{k} 0...0}) G (Z_{0...0 i_{k} 0...0})} & (13.12) \end{matrix}

$\begin{matrix} L_{i_{1} ... i_{N}} = \frac{p (Z_{i_{i} ... i_{N}}) G (Z_{i_{1} ... i_{N}})}{Π p (Z_{0...0 i_{k} 0...0}) G (Z_{0...0 i_{k} 0...0})} & (13.12) \end{matrix}$

Here, the index i_k in the denominator corresponds to the kth index of Z_{i₁… i_N} in the numerator. Next, define

\begin{matrix} c_{i_{1} ... i_{N} = - ln L_{i_{1} ... i_{N}}} & (13.13) \end{matrix}

$\begin{matrix} c_{i_{1} ... i_{N} = - ln L_{i_{1} ... i_{N}}} & (13.13) \end{matrix}$

so that

\begin{matrix} - ln [\frac{P (γ | Z^{N})}{P (γ^{0} | Z^{N})}] = \sum_{(i_{1}, ... i_{N}) \in γ} c_{i_{1} ... i_{N}} & (13.14) \end{matrix}

$\begin{matrix} - ln [\frac{P (γ | Z^{N})}{P (γ^{0} | Z^{N})}] = \sum_{(i_{1}, ... i_{N}) \in γ} c_{i_{1} ... i_{N}} & (13.14) \end{matrix}$

Thus, in view of the characterization of a partition (Equations 13.4a, 13.4b, 13.4c and 13.4d and 13.5) specialized by Equation 13.7 as a solution of Equation 13.10, the independence assumptions²¹ and the expansion (Equation 13.6) problem (Equation 13.1) are equivalently characterized as the following N-dimensional assignment problem:

Minimize

\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N} = 0}^{M_{N}} c_{i_{1} ... i_{N}} z_{i_{1} ... i_{N}} & (13.15) \end{matrix}

$\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N} = 0}^{M_{N}} c_{i_{1} ... i_{N}} z_{i_{1} ... i_{N}} & (13.15) \end{matrix}$

Subject to

\begin{matrix} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i = 1, ..., M_{1} & \begin{matrix} (13.16) \end{matrix} \end{matrix}

$\begin{matrix} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i = 1, ..., M_{1} & \begin{matrix} (13.16) \end{matrix} \end{matrix}$

\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{k - 1} = 0}^{M_{k - 1}} \sum_{i_{k + 1} = 0}^{M_{K + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & (13.17) \end{matrix}

$\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{k - 1} = 0}^{M_{k - 1}} \sum_{i_{k + 1} = 0}^{M_{K + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & (13.17) \end{matrix}$

for i_k = 1, …, M_k and k = 2, …, N − 1

\begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N - 1} = 0}^{M_{N - 1}} z_{i_{1} ... i_{N}} = 1 \end{matrix} & i_{N} = 1, ..., M_{N} \end{matrix} & (13.18) \end{matrix}

$\begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N - 1} = 0}^{M_{N - 1}} z_{i_{1} ... i_{N}} = 1 \end{matrix} & i_{N} = 1, ..., M_{N} \end{matrix} & (13.18) \end{matrix}$

\begin{matrix} \begin{matrix} z_{i_{1} ... i_{N}} \in {0, 1} & for all i_{1}, ..., i_{N} \end{matrix} & (13.19) \end{matrix}

$\begin{matrix} \begin{matrix} z_{i_{1} ... i_{N}} \in {0, 1} & for all i_{1}, ..., i_{N} \end{matrix} & (13.19) \end{matrix}$

where c_0…0 is arbitrarily defined to be zero. Note that the definition of a partition and the 0–1 variable z_{i₁…i_N} in Equation 13.9 imply z_0…0 = 0. (If z_0…0 is not preassigned to zero and c_0…0 is defined arbitrarily, then z_0…0 is determined directly from the value of c_0…0, because it does not enter the constraints other than being a 0–1 variable.) Also, each cost coefficient with exactly one nonzero index is zero (i.e., c_{0…0i_k 0…0} = 0 for all i_k = 1, …, M_k and k = 1, …, N) based on the use of the normalizing partition γ⁰ in the likelihood ratio in Equations 13.11 and 13.12. Deriving the same problem formulation is possible when not assuming that the cost coefficients with exactly one nonzero index are zero;²¹ however, other formulations can be reduced to the above-mentioned using the invariance theorem presented in Section 13.5.1.

Derivation of the assignment problem (Equation 13.15) leads to several pertinent remarks. The definition of a partition in Equations 13.4 and 13.5 implies that each actual report belongs to, at most, one track of reports Z_{γ_i} in a partition Z_γ of the cumulative data set. This can be modified to allow multiassignments of one, some, or all of the actual reports. The assignment problem changes accordingly. For example, if $z_{i_{k}}^{k}$ $z_{i_{k}}^{k}$ is to be assigned no more than, exactly, or no less than $n_{i_{k}}^{k}$ $n_{i_{k}}^{k}$ times, then the “=1” in the constraint (Equation 13.15) is changed to $″ \leq, =, \geq n_{i_{k^{'}}}^{k} ″$ $″ \leq, =, \geq n_{i_{k^{'}}}^{k} ″$ respectively. (This allows both set coverings and packings in the formulation.) In making these changes, one must pay careful attention to the independence assumptions.²¹ Inequality constraint problems, in addition to the problem of unresolved closely spaced objects, are common elements of the sensor fusion multiresolution problem.

The likelihood ratio, L_{i₁…i_N} is a complicated expression containing probabilities for detection, termination, model maneuvers, and density functions for an expected number of false alarms and initiating targets. The likelihood that an observation arises from a particular target is also included; this requires target dynamics to be estimated through the corresponding sequence of observations ${z_{i_{1}}^{1}, ..., z_{i k}^{k}, ..., z_{i N}^{N}}$ ${z_{i_{1}}^{1}, ..., z_{i k}^{k}, ..., z_{i N}^{N}}$ . Filtering such sequences is the most time-consuming part of the problem formulation and considerably exceeds the time required to solve the data association problem. Derivations for appropriate likelihood ratios can be found in the works of Poore²¹ and Blackman and Popoli.³

13.4 Multiple-Frame Track Initiation and Track Maintenance

A general expression has been developed for the data association problem arising from tracking. The underlying tracking application is a dynamic one in that information from one or more sensors continually arrives at the processing unit where the data is partitioned into frames of data for the assignment problem. Thus, the dimension of the assignment problem grows with the number of frames of data, N. Processing all the data at once, called batch processing, eventually becomes computationally unacceptable as the dimension N increases. To circumvent this problem, a sliding window can be used, wherein changes to data association decisions are limited to those within the window. The first sliding window (single pane) formulation was presented in 1992²⁵ and refined in 1997²⁶ to include a dual-pane window. The single-pane sliding window and its refinements are described in this section.

The moving window and the resulting search tree are truly the heart of a tracking system. The importance of the underlying data structures to the efficiency of a tracking system cannot be overemphasized; however, these data structures can be very complex and are not discussed here.

13.4.1 Track Initiation

The pure track initiation problem is to formulate and solve the assignment problem described in the previous section with an appropriate number of frames of data N. The choice of the number of frames N is not trivial. Choices of N = 4, 5, 6 have worked well in many problems; however, a good research topic would involve the development of a method that adaptively chooses the number of frames on the basis of the problem complexity.

13.4.2 Track Maintenance Using a Sliding Window

The term track maintenance as used in this section includes three functions: (1) extending existing tracks, (2) terminating existing tracks, and (3) initiating new ones. Suppose that the observations on P frames of observations have been partitioned into tracks and false alarms. and that K new frames of observations are to be added. One approach to solving the resulting data association problem is to formulate it as a track initiation problem with P + K frames. This is the previously mentioned batch approach.

The deferred logic approach adopted here would treat the track extension problem within the framework of a window, sliding over the frames of observations. The P frames are partitioned into two components: the first H frames, in which hard data association decisions are made, and the next S frames, in which soft decisions are made. The K new frames of observations are added, making the number of frames in the sliding window N = S + K, whereas the number of frames in which data association decisions are hard is H = P − S. Various sliding windows can be developed, including single-pane, double-pane, and multiple-pane windows. The intent of each of these is efficiency in solving the underlying tracking problem.

13.4.2.1 Single-Pane Sliding Window

Assuming K = 1, let M₀ denote the number of confirmed tracks (i.e., tracks that arise from the solution of the data association problem) on frame k constructed from a solution of the data association problem utilizing frames up to k + N − 1. Data association decisions are fixed on frames up to k. Now a new frame of data is added. Thus, frame k denotes a list of tracks and frames k + 1 to k + N denote observations. For i₀ = 1, …, M₀, the i₀th such track is denoted by T_i₀ and the (N + 1)-tuple ${T_{i_{0}}, z_{l_{1}}^{1}, ..., z_{i N}^{N}}$ ${T_{i_{0}}, z_{l_{1}}^{1}, ..., z_{i N}^{N}}$ denotes a track T_i₀ plus a set of observations ${z_{i_{1}}^{1}, ..., z_{i N}^{N}}$ ${z_{i_{1}}^{1}, ..., z_{i N}^{N}}$ , actual or dummy, that are feasible with the track T_i₀. The (N + 1)-tuple ${T_{0}, z_{i_{1}}^{1}, ..., z_{i N}^{N}}$ ${T_{0}, z_{i_{1}}^{1}, ..., z_{i N}^{N}}$ denotes a track that initiates in the sliding window. A false report in the sliding window is one in which all indices except one are zero in the (N + 1)-tuple ${T_{0}, z_{i_{1}}^{1}, ..., z_{i N}^{N}}$ ${T_{0}, z_{i_{1}}^{1}, ..., z_{i N}^{N}}$ .

The hypothesis about a partition γ ∈ Γ∗ being true is now conditioned on the truth of the M₀ tracks entering the N-scan window. (Thus, the assignments before reaching this sliding window are fixed.) The likelihood function is given by $L_{γ} = Π_{{T_{i_{0}}, z_{i_{1}}, \dots, {z_{i}}_{N} \in γ}} L_{i_{0} i_{1} \dots i_{N}},$ $L_{γ} = Π_{{T_{i_{0}}, z_{i_{1}}, \dots, {z_{i}}_{N} \in γ}} L_{i_{0} i_{1} \dots i_{N}},$ , where L_{i₀i₁…i_N} = L_{T_i0}L_{i₁…i_N}, L_{T_i0} is the composite likelihood from the discarded frames just before the first scan in the window for i₀ > 0, L_T₀ = 1, and L_{i₁…i_N} is defined as in Equation 13.8 for the N-scan window. (L_T₀ = 1 is used for any tracks that initiate in the sliding window.) Thus, the track extension problem can be formulated as Maximize {Lγ|γ ∈ Γ∗}. With the same convention as in Section 13.3, a feasible partition is one that is defined by the properties in Equations 13.4 and 13.7. Analogously, the definition of the 0–1 variable

z_{i_{0} i_{1} ... i_{N}} = {\begin{matrix} 1 & if {T_{i_{0}}, z_{i_{1}}^{1}, ..., z_{i_{N}}^{N}} is assigned as a unit \\ 0 & otherwise \end{matrix}

$z_{i_{0} i_{1} ... i_{N}} = {\begin{matrix} 1 & if {T_{i_{0}}, z_{i_{1}}^{1}, ..., z_{i_{N}}^{N}} is assigned as a unit \\ 0 & otherwise \end{matrix}$

and the corresponding cost for the assignment of the sequence {T_i₀, z_i₁, …, z_{i_N}} to a track by c_{i₀i₁…i_N} = –lnL_{i₀i₁…i_N} yield the following multidimensional assignment formulation of the data association problem for track maintenance:

Minimize

\begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{N} = 0}^{M_{N}} c_{i_{0} ... i_{N}} z_{i_{0} \dots i_{N}} & (13.20) \end{matrix}

$\begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{N} = 0}^{M_{N}} c_{i_{0} ... i_{N}} z_{i_{0} \dots i_{N}} & (13.20) \end{matrix}$

Subject to

\begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{0} ... i_{N}} = 1 & i_{0} = 1, ..., M_{0} \end{matrix} & (13.21) \end{matrix}

$\begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{0} ... i_{N}} = 1 & i_{0} = 1, ..., M_{0} \end{matrix} & (13.21) \end{matrix}$

\begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{M} = 0}^{M_{N}} z_{i_{1_{0} i_{1}} ... i_{N}} = 1 & i = 1, ..., M_{1} \end{matrix} & (13.22) \end{matrix}

$\begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{M} = 0}^{M_{N}} z_{i_{1_{0} i_{1}} ... i_{N}} = 1 & i = 1, ..., M_{1} \end{matrix} & (13.22) \end{matrix}$

\begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{k - 1} = 0}^{M_{k - 1}} \sum_{i_{k + 1} = 0}^{M_{k + 1}} ... \sum_{i_{M} = 0}^{M_{N}} z_{i_{0} ... i_{N}} = 1 \end{matrix} & (13.23) \end{matrix}

$\begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{k - 1} = 0}^{M_{k - 1}} \sum_{i_{k + 1} = 0}^{M_{k + 1}} ... \sum_{i_{M} = 0}^{M_{N}} z_{i_{0} ... i_{N}} = 1 \end{matrix} & (13.23) \end{matrix}$

for i_k = 1,…,M_k and k = 2,…,N – 1

\begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{N - 1} = 0}^{M_{N - 1}} z_{i_{0} ... i_{N}} = 1 \end{matrix} \end{matrix} & i_{N} = 1, ..., M_{N} \end{matrix} & (13.24) \end{matrix}

$\begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{0} = 0}^{M_{0}} ... \sum_{i_{N - 1} = 0}^{M_{N - 1}} z_{i_{0} ... i_{N}} = 1 \end{matrix} \end{matrix} & i_{N} = 1, ..., M_{N} \end{matrix} & (13.24) \end{matrix}$

\begin{matrix} z_{i_{0} ... i_{N}} \in {0, 1} & for all i_{0}, ..., i_{N} & (13.25) \end{matrix}

$\begin{matrix} z_{i_{0} ... i_{N}} \in {0, 1} & for all i_{0}, ..., i_{N} & (13.25) \end{matrix}$

Note that the association problem involving N frames of observations is an N-dimensional assignment problem for track initiation and an (N + 1)-dimensional assignment problem for track maintenance.

13.4.2.2 Double- and Multiple-Pane Window

In the single-pane window, the first frame contains a list of tracks and the remaining N frames contain observations. The assignment problem is of dimension N + 1, where N is the number of frames of observations in front of the existing tracks. The same window is being used to initiate new tracks and continue existing ones. A newer approach is based on the belief that once a track is well established, only a few frames are needed to benefit from the soft decisions on track continuation, whereas a longer window is needed for track initiation. Thus, if the current frame is numbered k with frames k + 1, …, k + N being for track continuation, one can go back to frames k – M, …, k and allow observations not attached to tracks that exist through frame k, to be used to initiate new tracks. Indeed, this concept works extremely well in practice and was initially proposed in the work of Poore and Drummond.²⁶ The next approach to evolve is that of a multiple-pane window, in which the position of hard data association decisions of observations to tracks can vary within the frames k − 1, …, k, …, k + N, depending on the difficulty of the problem as measured by track contention. The efficiency of this approach is yet to be determined.

13.5 Algorithms

The multidimensional assignment problem for data association is one of combinatorial optimization and is NP-hard,²⁷ even for the case N = 3. The data association problems arising in tracking are generally sparse, large-scale, and noisy with real-time needs. Given the noise in the problem, the objective is generally to solve the problem to within the noise level. Thus, heuristic methods are recommended; however, efficient branch and bound schemes are potentially applicable to this problem because they provide the baseline against which other heuristic algorithms are judged. Lagrangian relaxation methods have worked extremely well, probably due to the efficiency of nonsmooth optimization methods^28,29 and the fact that the relaxed problem is the two-dimensional assignment problem for which there are some very efficient algorithms, such as the auction³⁰ and Jonker–Volbenant (JV) algorithms.³¹ Another advantage is that these relaxation methods provide both a lower and upper bound on the optimal solution and, thus, some measure of closeness to optimality. (This is obviously limited by the duality gap.)

This section surveys some of the algorithms that have been particularly successful in solving the data association problems arising from tracking. There are, however, many potential algorithms that could be used. For example, greedy randomized adaptive local search procedure (GRASP)^{32, 33 and 34} also has been used successfully.

13.5.1 Preprocessing

Two frequently used preprocessing techniques, fine gating and problem decomposition, are presented in this section. These two methods can substantially reduce the complexity of the multidimensional assignment problem.

13.5.1.1 Fine Gating

The term fine gating is used because this method is the last in a sequence of techniques used to reduce the unlikely paths in the layered graph or pairings of combinations of reports. This method is based on the following theorem.²¹

Theorem 1 (Invariance property)

Let N > 1 and M_k > 0 for k = 1, …, N, and assume ${\hat{c}}_{0...0} = 0$ ${\hat{c}}_{0...0} = 0$ and $u_{0}^{k} = 0$ $u_{0}^{k} = 0$ k = 1, …, N. Then the minimizing solution and objective function value of the following multidimensional assignment problem are independent of any choice of $u_{i_{k}}^{k} = 1$ $u_{i_{k}}^{k} = 1$ for i_k = 1, …, M_k and k = 1, …, N.

Minimize

\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N} = 0}^{M_{N}} ({\hat{c}}_{i_{1} ... i_{N}} - \sum_{k = 1}^{N} u_{i_{k}}^{k}) z_{i_{0} ... i_{N}} + \sum_{k = 1}^{N} \sum_{i_{k = 0}}^{M_{K}} u_{i_{k}}^{k} & (13.26) \end{matrix}

$\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N} = 0}^{M_{N}} ({\hat{c}}_{i_{1} ... i_{N}} - \sum_{k = 1}^{N} u_{i_{k}}^{k}) z_{i_{0} ... i_{N}} + \sum_{k = 1}^{N} \sum_{i_{k = 0}}^{M_{K}} u_{i_{k}}^{k} & (13.26) \end{matrix}$

Subject to

\begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 \end{matrix} & i_{1} = 1, ..., M_{1} \end{matrix} & (13.27) \end{matrix}

$\begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 \end{matrix} & i_{1} = 1, ..., M_{1} \end{matrix} & (13.27) \end{matrix}$

\begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{K - 1} = 0}^{M_{K - 1}} \sum_{i_{K + 1} = 0}^{M_{K + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 \end{matrix} \end{matrix} & (13.28) \end{matrix}

$\begin{matrix} \begin{matrix} \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{K - 1} = 0}^{M_{K - 1}} \sum_{i_{K + 1} = 0}^{M_{K + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 \end{matrix} \end{matrix} & (13.28) \end{matrix}$

for i_k = 1, …, M_k and k = 2, …, N − 1

\begin{matrix} {\begin{matrix} \sum \end{matrix}}_{i_{1} = 0}^{M_{1}} ... {\begin{matrix} \sum \end{matrix}}_{i_{N - 1} = 0}^{M_{N - 1}} z_{i_{1} ... i_{N}} = 1 & i_{N} = 1, ..., M_{N} & (13.29) \end{matrix}

$\begin{matrix} {\begin{matrix} \sum \end{matrix}}_{i_{1} = 0}^{M_{1}} ... {\begin{matrix} \sum \end{matrix}}_{i_{N - 1} = 0}^{M_{N - 1}} z_{i_{1} ... i_{N}} = 1 & i_{N} = 1, ..., M_{N} & (13.29) \end{matrix}$

\begin{matrix} \begin{matrix} z_{i_{1} ... i_{N}} \in {0, 1} & for all i_{1}, ..., i_{N} \end{matrix} & (13.30) \end{matrix}

$\begin{matrix} \begin{matrix} z_{i_{1} ... i_{N}} \in {0, 1} & for all i_{1}, ..., i_{N} \end{matrix} & (13.30) \end{matrix}$

If ${\hat{c}}_{i_{1} ... i_{N}} = c_{i_{1} ... i_{N}}$ ${\hat{c}}_{i_{1} ... i_{N}} = c_{i_{1} ... i_{N}}$ and $u_{i k}^{k} C_{0... 0_{i_{k}} 0...0}$ $u_{i k}^{k} C_{0... 0_{i_{k}} 0...0}$ is identified in this theorem, then

\begin{matrix} c_{i_{1... i_{N}}} - \sum_{k = 1}^{N} C_{{0...0}_{i_{k}} 0...0} > 0 & (13.31) \end{matrix}

$\begin{matrix} c_{i_{1... i_{N}}} - \sum_{k = 1}^{N} C_{{0...0}_{i_{k}} 0...0} > 0 & (13.31) \end{matrix}$

implies that the corresponding 0–1 variable z_{i₁…i_N} and cost c_{i₁…i_N} can be removed from the problem because a lower cost can be achieved with the use of the variables z_{0…0i_k0…0} = 1. (This does not mean that one should set z_{0…0i_k0…0} = 1 for k = 1, …, N.)

In the special case in which all costs with exactly one nonzero index are zero, this test is equivalent to

\begin{matrix} c_{i_{1... i_{N}}} > 0 & (13.32) \end{matrix}

$\begin{matrix} c_{i_{1... i_{N}}} > 0 & (13.32) \end{matrix}$

13.5.1.2 Problem Decomposition

Decomposition of the multidimensional assignment problem into a sequence of disjoint problems can improve the solution quality and the speed of the algorithm, even on a serial machine. The following decomposition method, originally presented in the work of Poore et al.,³⁵ uses graph theoretic methods.

Decomposition of the multidimensional assignment problem is accomplished by determining the connected components of the associated layered graph. Let

\begin{matrix} Ƶ = {z_{i_{1} i_{2} ... i_{N}} | z_{i_{1} i_{2} ... i_{N}} is not preassigned to zero} & (13.33) \end{matrix}

$\begin{matrix} Ƶ = {z_{i_{1} i_{2} ... i_{N}} | z_{i_{1} i_{2} ... i_{N}} is not preassigned to zero} & (13.33) \end{matrix}$

denote the set of assignable variables. Define an undirected graph G(N, A) where the set of nodes is

\begin{matrix} N = {z_{i_{k}}^{k} | i_{k} = 1, ..., M_{k}; k = 1, ..., N} & (13.34) \end{matrix}

$\begin{matrix} N = {z_{i_{k}}^{k} | i_{k} = 1, ..., M_{k}; k = 1, ..., N} & (13.34) \end{matrix}$

and the set of arcs is

\begin{matrix} A = {\begin{cases} (z_{j k}^{k}, z_{j t}^{t}) | k \neq 1, j_{k} \neq 0, j_{t} \neq 0, \\ and there exists z_{i_{1} i_{2} ... i_{N}} \in Ƶ such that j_{k} = i_{k} and j_{t} = i_{t} \end{cases}} & (13.35) \end{matrix}

$\begin{matrix} A = {\begin{cases} (z_{j k}^{k}, z_{j t}^{t}) | k \neq 1, j_{k} \neq 0, j_{t} \neq 0, \\ and there exists z_{i_{1} i_{2} ... i_{N}} \in Ƶ such that j_{k} = i_{k} and j_{t} = i_{t} \end{cases}} & (13.35) \end{matrix}$

The nodes corresponding to zero index have not been included in this graph because two variables that have only the zero index in common can be assigned independently. Connected components of the graph are easily found by constructing a spanning forest through a depth-first search. Furthermore, this procedure can be used at each level in the relaxation (i.e., applied to each assignment problem for k = 3,…, N). Note that the decomposition algorithm depends only on the problem structure (i.e., the feasibility of the variables) and not on the cost function.

As an aside, this decomposition often yields small problems that are best and more efficiently handled by a branch and bound or an explicit enumeration procedure to avoid the overhead associated with relaxation. The remaining components are solved by relaxation. However, extensive decomposition can be time-consuming and limiting the number of components to approximately ten is desirable, unless one is using a parallel machine.

13.5.2 Lagrangian Relaxation Algorithm for the Assignment Problem

This section presents Lagrangian relaxation algorithms for multidimensional assignment, which have proven to be computationally efficient and accurate for tracking purposes. The N-dimensional assignment problem has M₁ + … + M_N individual constraints, which can be grouped into N constraint sets. Let $u_{k} = (u_{0}^{k}, u_{1}^{k}, ..., u^{k} M_{k})$ $u_{k} = (u_{0}^{k}, u_{1}^{k}, ..., u^{k} M_{k})$ , denote the (M_k + 1)-dimensional Lagrange multiplier vector associated with the kth constraint set, with $u_{0}^{k} = 0$ $u_{0}^{k} = 0$ and k = 1, …, N. The full set of multipliers is denoted by the vector u = [u¹,…, u^N]. The multidimensional assignment problem is relaxed to an n-dimensional assignment problem by incorporating N − n constraint sets into the objective function. There are several choices of n. The case n = 0 yields the linear programming dual; n = 2 yields a two-dimensional assignment problem and has been highly successful in practice.

Although any constraint sets can be relaxed, sets n + 1, …, N are chosen for convenience. In the tracking problem using a sliding window, these are the correct sets given the data structures that arise from the construction of tracks.

The relaxed problem for multiplier vector u is given by

\begin{matrix} L_{n} (u^{n + 1}, ... u^{N}) = & (13.36) \end{matrix}

$\begin{matrix} L_{n} (u^{n + 1}, ... u^{N}) = & (13.36) \end{matrix}$

Minimize

\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N} = 0}^{M_{N}} (c_{i_{1} ... i_{N}} + \sum_{k = n + 1}^{N} u_{i_{k}}^{k}) z_{i_{1} ... i_{N}} - \sum_{k = n + 1}^{N} \sum_{i_{k} = 0}^{M_{k}} u_{i_{k}}^{k} & (13.37) \end{matrix}

$\begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{N} = 0}^{M_{N}} (c_{i_{1} ... i_{N}} + \sum_{k = n + 1}^{N} u_{i_{k}}^{k}) z_{i_{1} ... i_{N}} - \sum_{k = n + 1}^{N} \sum_{i_{k} = 0}^{M_{k}} u_{i_{k}}^{k} & (13.37) \end{matrix}$

Subject to

\begin{matrix} \begin{matrix} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i_{1} = 1, ..., M_{1} \end{matrix} & (13.38) \end{matrix}

$\begin{matrix} \begin{matrix} \sum_{i_{2} = 0}^{M_{2}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i_{1} = 1, ..., M_{1} \end{matrix} & (13.38) \end{matrix}$

\begin{matrix} \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} \sum_{i_{3} = 0}^{M_{3}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i_{1} = 1, ..., M_{2} \end{matrix} & (13.39) \end{matrix}

$\begin{matrix} \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} \sum_{i_{3} = 0}^{M_{3}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i_{1} = 1, ..., M_{2} \end{matrix} & (13.39) \end{matrix}$

\begin{matrix} ._{.}^{.} \\ \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{n - 1} = 0}^{M_{n - 1}} \sum_{i_{n + 1} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i_{n} = 1, ..., M_{n} \end{matrix} (13.40) \end{matrix}

$\begin{matrix} ._{.}^{.} \\ \begin{matrix} \sum_{i_{1} = 0}^{M_{1}} ... \sum_{i_{n - 1} = 0}^{M_{n - 1}} \sum_{i_{n + 1} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{N}} = 1 & i_{n} = 1, ..., M_{n} \end{matrix} (13.40) \end{matrix}$

\begin{matrix} \begin{matrix} z_{i_{1} .. i_{N}} \in {10, 1} & for all {i_{1}, ..., i_{N}} \end{matrix} & (13.41) \end{matrix}

$\begin{matrix} \begin{matrix} z_{i_{1} .. i_{N}} \in {10, 1} & for all {i_{1}, ..., i_{N}} \end{matrix} & (13.41) \end{matrix}$

The above-mentioned problem can be reduced to an n-dimensional assignment problem using the transformation

\begin{matrix} x_{i_{1} i_{2} ... i_{n}} = \sum_{i_{n_{+ 1}} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{n} i_{n + 1... i_{N}}} & for all i_{1}, i_{2}, ..., i_{n} & (13.42) \end{matrix}

$\begin{matrix} x_{i_{1} i_{2} ... i_{n}} = \sum_{i_{n_{+ 1}} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} z_{i_{1} ... i_{n} i_{n + 1... i_{N}}} & for all i_{1}, i_{2}, ..., i_{n} & (13.42) \end{matrix}$

\begin{matrix} c_{i_{1} i_{2} ... i_{n}} = Min {c_{i_{1} ... i_{N}} + \sum_{k = n + 1}^{N} u_{i_{k}}^{u} | & for all i_{n + 1}, ... i_{N}} & (13.43) \end{matrix}

$\begin{matrix} c_{i_{1} i_{2} ... i_{n}} = Min {c_{i_{1} ... i_{N}} + \sum_{k = n + 1}^{N} u_{i_{k}}^{u} | & for all i_{n + 1}, ... i_{N}} & (13.43) \end{matrix}$

\begin{matrix} \begin{matrix} c_{0...0} = \sum_{i_{n + 1} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} Min {0, c_{0...0 i_{n + 1... i_{N}}} + \sum_{k = n + 1}^{N} u_{i_{k}}^{u}} \end{matrix} & (13.44) \end{matrix}

$\begin{matrix} \begin{matrix} c_{0...0} = \sum_{i_{n + 1} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} Min {0, c_{0...0 i_{n + 1... i_{N}}} + \sum_{k = n + 1}^{N} u_{i_{k}}^{u}} \end{matrix} & (13.44) \end{matrix}$

Thus, the Lagrangian relaxation algorithm can be summarized as follows:

Solve the problem

Maximize

$\begin{matrix} L_{n} (u^{n + 1}, ... u^{N}) & (13.45) \end{matrix}$ $\begin{matrix} L_{n} (u^{n + 1}, ... u^{N}) & (13.45) \end{matrix}$
Give an optimal or near-optimal solution (uⁿ⁺¹, …, u^N); solve the above-mentioned assignment problem for this given multiplier vector. This produces an alignment of the first n indices. Let these be enumerated by ${(i_{1}^{j}, ..., i_{n}^{j})}_{j}^{J} = 0$ ${(i_{1}^{j}, ..., i_{n}^{j})}_{j}^{J} = 0$ , where $(i_{1}^{0}, ..., l_{n}^{0}) = (0, ..., 0)$ $(i_{1}^{0}, ..., l_{n}^{0}) = (0, ..., 0)$ . Then, the variable and cost coefficient

\begin{matrix} x_{{j i}_{n + 1} ... i_{N}} = z_{i_{1}^{j} ... i_{n}^{j} i_{n + 1} ... i_{N}} & (13.46) \end{matrix}

$\begin{matrix} x_{{j i}_{n + 1} ... i_{N}} = z_{i_{1}^{j} ... i_{n}^{j} i_{n + 1} ... i_{N}} & (13.46) \end{matrix}$

\begin{matrix} c_{{j i}_{n + 1} ... i_{N}} = c_{i_{1}^{j} ... i_{n}^{j} i_{n + 1} ... i_{N}} & (13.47) \end{matrix}

$\begin{matrix} c_{{j i}_{n + 1} ... i_{N}} = c_{i_{1}^{j} ... i_{n}^{j} i_{n + 1} ... i_{N}} & (13.47) \end{matrix}$

satisfy the following (N − n + 1)-dimensional assignment problem.

Minimize

\begin{matrix} \sum_{j = 0}^{J} \end{matrix} \begin{matrix} \sum_{i_{n + 1} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} c_{j i_{n + 1} ... i_{N}} z_{j i_{n + 1} ... i_{N}} & (13.48) \end{matrix}

$\begin{matrix} \sum_{j = 0}^{J} \end{matrix} \begin{matrix} \sum_{i_{n + 1} = 0}^{M_{n + 1}} ... \sum_{i_{N} = 0}^{M_{N}} c_{j i_{n + 1} ... i_{N}} z_{j i_{n + 1} ... i_{N}} & (13.48) \end{matrix}$

Subject to

\begin{matrix} \begin{matrix} \sum_{i_{n + 1} = 0}^{M_{n + 1}} \end{matrix} ... \begin{matrix} \sum_{i_{N} = 0}^{M_{N}} z_{j i_{n + 1} ... i_{N}} = 1 & j = 1, ..., j \end{matrix} & (13.49) \end{matrix}

$\begin{matrix} \begin{matrix} \sum_{i_{n + 1} = 0}^{M_{n + 1}} \end{matrix} ... \begin{matrix} \sum_{i_{N} = 0}^{M_{N}} z_{j i_{n + 1} ... i_{N}} = 1 & j = 1, ..., j \end{matrix} & (13.49) \end{matrix}$

\begin{matrix} \sum_{j = 0}^{J} & \begin{matrix} \sum_{i_{n + 2} = 0}^{M_{3}} \end{matrix} ... \begin{matrix} \sum_{i_{N} = 0}^{M_{N}} z_{j i_{n + 1} ... i_{N}} = 1 & for i_{n + 1} = 1, ..., M_{n + 1} \end{matrix} & (13.50) \end{matrix}

$\begin{matrix} \sum_{j = 0}^{J} & \begin{matrix} \sum_{i_{n + 2} = 0}^{M_{3}} \end{matrix} ... \begin{matrix} \sum_{i_{N} = 0}^{M_{N}} z_{j i_{n + 1} ... i_{N}} = 1 & for i_{n + 1} = 1, ..., M_{n + 1} \end{matrix} & (13.50) \end{matrix}$

\begin{matrix} \begin{matrix} ⋮ \\ \sum_{j = 0}^{J} ... \begin{matrix} \sum_{i_{N - 1} = 0}^{M_{N - 1}} z_{j i_{n + 1} ... i_{N}} = 1 & i_{N} = 1, ..., M_{N} \end{matrix} \end{matrix} & \begin{matrix} (13.51) \end{matrix} \end{matrix}

$\begin{matrix} \begin{matrix} ⋮ \\ \sum_{j = 0}^{J} ... \begin{matrix} \sum_{i_{N - 1} = 0}^{M_{N - 1}} z_{j i_{n + 1} ... i_{N}} = 1 & i_{N} = 1, ..., M_{N} \end{matrix} \end{matrix} & \begin{matrix} (13.51) \end{matrix} \end{matrix}$

\begin{matrix} \begin{matrix} z_{j i_{n + 1} ... i_{N}} \in {0, 1} & for all {j, i_{n + 1}, ..., i_{}} \end{matrix} & (13.52) \end{matrix}

$\begin{matrix} \begin{matrix} z_{j i_{n + 1} ... i_{N}} \in {0, 1} & for all {j, i_{n + 1}, ..., i_{}} \end{matrix} & (13.52) \end{matrix}$

Let the nonzero 0–1 variables in a solution be denoted by $z_{j i_{n + 1...}^{j} i_{N}^{j} = 1}$ $z_{j i_{n + 1...}^{j} i_{N}^{j} = 1}$ , then the solution of the original problem is $z_{i_{1..}^{j} i_{n}^{j} i_{n + 1}^{j} ... i_{N}^{j}} = 1$ $z_{i_{1..}^{j} i_{n}^{j} i_{n + 1}^{j} ... i_{N}^{j}} = 1$ with all remaining values of z being zero.

In summary, this algorithm is the result of the N-dimensional assignment problem being relaxed to an n-dimensional assignment problem by relaxing N – n constraint sets. The problem of restoring feasibility is defined as an (N − n + 1)-dimensional problem.

Notice that the problem of maximizing L_n(u^n + 1, …, u^N) is one of nonsmooth optimization. Bundle methods^36,37 have proven to be particularly successful for this purpose.

13.5.2.1 Class of Algorithms

Earlier work^7,11,38,39 involved relaxing an N-dimensional assignment problem to an N-dimensional one, which is NP-hard for N > 2, by relaxing one set of constraints. The corresponding dual function L_n(u^n + 1, …, u^N) is piecewise linear and concave, but the evaluation of the function and subgradients, as needed by the nonsmooth maximization, requires an optimal solution of an NP-hard n-dimensional assignment problem when n > 2. To address the real-time needs, suboptimal solutions to the relaxed problem must be used; however, suboptimal solutions only provide approximate function and subgradient values. To moderate this difficulty, Poore and Rijavec³⁹ used a concave, piecewise affine merit function to provide guidance for the function values for the nonsmooth optimization phase. This approach computed approximate subgradients from good-quality feasible solutions obtained from multiple relaxation and recovery cycles executed at lower levels in a recursive fashion. (The number of cycles can be any fixed number greater than or equal to 1 or it can be chosen adaptively by allowing the nonsmooth optimization solver to converge to within user-defined tolerances.) Despite these approximations, the numerical performance of these previous algorithms has been quite good.³⁹

A variation on the N-to-(N – 1) relaxation algorithm using one cycle is attributable to Deb et al.¹⁶ Similar approximate function and subgradient values are used at each level of the relaxation process. To moderate this difficulty, they modify the accelerated subgradient method of Shor⁴⁰ by further weighting the search direction in the direction of violated constraints, and they report improvement over the accelerated subgradient method. They do not, however, use problem decomposition and a merit function as in Poore and Rijavec’s previous work.³⁹

When relaxing an N-dimensional assignment problem to an n-dimensional one, the one case in which the aforementioned difficulties are resolved is for n = 2; this is the algorithm that is currently used in the Poore and Rijavec tracking system.

13.5.3 Algorithm Complexity

In the absence of a complexity analysis, computational experience shows that between 90 and 95% of all the computation time is consumed in the search to find the minimizer in the list of feasible arcs that are present in the assignment problem. Thus, the time required to solve an assignment problem appears to be computationally linear in the number of feasible arcs (i.e., tracks) in the assignment problem. Obviously, the gating techniques used in tracking to control the number of feasible tracks are fundamental to managing complexity.

13.5.4 Improvement Methods

The above-mentioned relaxation methods have been enormously successful in providing quality solutions to the assignment problem. Improvement techniques are fundamentally important. On the basis of the relaxation and a branch and bound framework,¹⁰ significant improvements in the quality of the solution have been achieved for tracking problems. On difficult problems in tracking, the improvement can be significant. Although straight relaxation can produce solutions to within 3% of optimality, the improvement techniques can produce solutions to within 0.5% of optimal on at least one class of very difficult tracking problems. Given the ever-increasing need for more accurate solutions, further improvements, such as local search methods, should be developed.

13.6 Future Directions

Following the previous sections’ overview of the problem formulation and presentation of highly successful algorithms, this section summarizes some of the open issues that should be addressed in the future.

13.6.1 Other Data Association Problems and Formulations

Several alternate formulations, such as more general set packings and coverings of the data, should be pursued. The current formulation is sufficiently general to include other important cases, such as multisensor resolution problems and unresolved closely spaced objects in which an observation is necessarily assigned to more than one target. The assigning of a report to more than one target can be accomplished within the context of the multidimensional assignment problems by using inequality constraints. The formulation, algorithms, and testing are yet to be systematically developed. Although allowing an observation to be assigned to more than one target is easy to model mathematically, allowing a target to be assigned to more than one observation is difficult and may introduce nonlinearity into the objective function due to a loss of the independence assumptions discussed in Section 13.3. Certainly, the original formulation of Morefield¹⁴ is worth revisiting.

13.6.2 Frames of Data

The use of the multidimensional assignment problems to solve the central data association problem rests on the assumption that each target is seen at most once in each frame of data (i.e., the frame is a “proper” frame). For a mechanically rotating radar, this is reasonably easy to approximate as a sweep of the surveillance region. For electronically scanning sensors, which can switch from searching mode to tracking mode, the solution to this partitioning problem is less obvious. Although one such solution has been developed, the formulation and solution are not yet optimal.

13.6.3 Sliding Windows

The batch approach to the data association problem of partitioning the observations into tracks and false alarms is to add a frame of data (observations) to the existing frames and then formulate and solve the corresponding multidimensional assignment problem. The dimension of the assignment problem increases by the number of frames added. To avoid the intractability of this approach, a moving window approach was developed in 1992 wherein the data association problem is resolved over the window of a limited number of frames of data.²⁵ This was revised in 1996²⁶ to use different length windows for track continuation (maintenance) and initiation. This approach improves the efficiency of the multiframe processing and maintains the longer window needed for track initiation. Indeed, numerical experiments to date show it to be far more efficient than a single-pane window. One can easily imagine using different depths in the window for continuing tracks, depending on the complexity of the problem. The efficiency of this approach in practice is yet to be determined.

A fundamental question relates to determining the dimension of the assignment problem that is most appropriate for a particular tracking problem. The goal of future research will be the development of a method that adapts the dimension to the difficulty of the problem or to the need in the surveillance problem.

13.6.4 Algorithms

Several Lagrangian relaxation methods were outlined in the previous section. The method that has been most successful involves relaxation to a two-dimensional assignment problem, maximization of the resulting relaxed problem with respect to the multipliers, and restoration of feasibility to the original problem by formulating this recovery problem as a multidimensional assignment problem of one dimension lower than the original. The process is then repeated until a two-dimensional assignment problem is reached that can be solved optimally.

Such an algorithm can generally produce solutions that are accurate to within 3% of optimal on very difficult problems and optimal for easy problems. The use of an improvement algorithm based on branch and bound can considerably improve the performance to within 0.5% of optimal, at least on some classes of difficult tracking problems.¹⁰ Other techniques, such as local search, should equally improve the solution quality.

Speed enhancements, using the decomposition and clustering discussed in the previous section and as presented in 1992³⁵ can improve the speed of the assignment solvers by an order of magnitude on large-scale and difficult problems. Further work on distributed and parallel computing should enhance both the solution quality and speed.

Another direction of work is the computation of K-near optimal solutions similar to K-best solutions for two-dimensional assignment problems.¹⁰ The K-near optimal solutions provide important information about the reliability of the computed tracks, which is not available with K-best solutions.

Finally, other approaches to the assignment problem, such as GRASP,^{32, 33 and 34} have also been successful, but not to the extent that relaxation has been.

13.6.5 Network-Centric Multiple-Frame Assignments

Multiple-platform tracking, like single-platform, multiple-sensor tracking, also has the potential to significantly improve track estimation by providing geometric diversity and sensor variety. The architecture for data association methods discussed in the previous sections can be applied to multiple-platform tracking in a centralized manner, wherein all measurements are sent to one location for processing and then tracks are transmitted back to the different platforms. The centralized architecture is probably optimal in that it is capable of producing the best track quality (e.g., purity and accuracy) and a consistent air picture; however, it is unacceptable in many applications as a result of issues such as communication loading and single-point failure. Thus, a distributed architecture is needed for both estimation/fusion² and data association. Although much has been achieved in the area of distributed fusion, few efforts have been extended to distributed, multiple-frame, data association.

The objectives for a distributed, multiple-frame data association approach to multiple-platform tracking are to achieve a performance, approaching that of the centralized architecture and to achieve a consistent or single integrated air picture (SIAP) across multiple platforms while maintaining communications loads to within a practical limit. Achieving these objectives will require researchers to address a host of problems or topics, including (1) distributed data association and estimation; (2) SIAP; (3) management of communication loading by using techniques such as data pruning, data compression (e.g., tracklets,⁴ push/request schemes, and target prioritization; (4) network topology of the communication architecture, including the design of new communication architectures and the incorporation of legacy systems; (5) types of information (e.g., measurements, tracks, tracklets) sent across the network; (6) sensor location and registration errors (i.e., “gridlock”); (7) pedigree problems; and (8) out-of-order, latent, and missing data caused by both sensor and communication problems.

The network-centric algorithm architecture of the Navy’s Cooperative Engagement Capability and Joint Composite Tracking Network provides a consistent or single integrated air picture across multiple platforms. This approach limits the communications loads to within a practical limit.⁴ This was designed with single-frame data association in mind and has not been extended to multiple-frame approaches. Thus, the development of a “network multiple-frame assignment” approach to data association remains an open and fundamentally important problem.

Acknowledgments

This work was partially supported by the Air Force Office of Scientific Research through AFOSR grant numbers F49620-97-1-0273 and F49620-00-1-0108 and by the Office of Naval Research through ONR grant number N00014-99-1-0118.

References

1. Waltz, E. and Llinas, J., Multisensor Data Fusion, Artech House, Boston, MA, 1990.

2. Drummond, O.E., A hybrid fusion algorithm architecture and tracklets, In Proceedings of SPIE Conference: Signal and Data Processing of Small Targets, Vol. 3136, San Diego, CA, pp. 485–502, 1997.

3. Blackman, S. and Popoli, R., Design and Analysis of Modern Tracking Systems, Artech House Inc., Norwood, MA, 1999.

4. Moore, J.R. and Blair, W.D., Practical aspects of multisensor tracking, In Multitarget-Multisensor Tracking: Applications and Advances III, Bar-Shalom, Y. and Blair, W.D. (Eds.) Artech House, Norwood, MA, 2000.

5. Bar-Shalom, Y. and Li, X.R., Multitarget-Multisensor Tracking: Principles and Techniques, OPAMP Tech. Books, Los Angeles, CA, 1995.

6. Poore, A.B. and Rijavec, N., Multitarget tracking and multidimensional assignment problems, In Proceedings of 1991 SPIE Conference: Signal and Data Processing of Small Targets, Vol. 1481, pp. 345–356, 1991.

7. Poore, A.B. and Rijavec, N., A Lagrangian relaxation algorithm for multi-dimensional assignment problems arising from multitarget tracking, SIAM Journal on Optimization, 3(3), 544–563, 1993.

8. Poore, A.B. and Robertson, A.J. III, A new class of Lagrangian relaxation based algorithms for a class of multidimensional assignment problems, Computational Optimization and Applications, 8(2), 129–150, 1997.

9. Shea, P.J. and Poore, A.B., Computational experiences with hot starts for a moving window implementation of track maintenance, In Proceedings of 1998 SPIE Conference: Signal and Data Processing of Small Targets, Vol. 3373, 1998.

10. Poore, A.B. and Yan, X., Use of K-near optimal solutions to improve data association in multiframe processing, In Proceedings of SPIE: Signal and Data Processing of Small Targets, Drummond, O.E. (Ed.), SPIE, Bellingham, WA, Vol. 3809, pp. 435–443, 1999.

11. Barker, T.N., Persichetti, J.A., Poore, A.B. Jr., and Rijavec, N., Method and system for tracking multiple regional objects, U.S. Patent No. 5,406,289, issued on April 11, 1995.

12. Poore, A.B. Jr., Method and system for tracking multiple regional objects by multi-dimensional relaxation, U.S. Patent No. 5,537,119, issued on July 16, 1996.

13. Poore, A.B. Jr., Method and system for tracking multiple regional objects by multi-dimensional relaxation, CIP, U.S. Patent No. 5,959,574, issued on September 28, 1999.

14. Morefield, C.L., Application of 0–1 integer programming to multitarget tracking problems, IEEE Transaction on Automatic Control, 22(3), 302–312, 1977.

15. Reid, D.B., An algorithm for tracking multiple targets, IEEE Transaction on Automatic Control, 24(6), 843–854, 1979.

16. Deb, S., Pattipati, K.R., Bar-Shalom, Y., and Yeddanapudi, M., A generalized s-dimensional assignment algorithm for multisensor multitarget state estimation, IEEE Transactions on Aerospace and Electronic Systems, 33(2), 523, 1997.

17. Kirubarajan, T., Bar-Shalom, Y., and Pattipati, K.R., Multiassignment for tracking a large number of overlapping objects, In Proceedings of SPIE Conference: Signal and Data Processing of Small Targets, Vol. 3163, 1997.

18. Kirubarajan, T., Wang, H., Bar-Shalom, Y., and Pattipati, K.R., Efficient multisensor fusion using multidimensional assignment for multitarget tracking, In Proceedings of SPIE Conference: Signal Processing, Sensor Fusion and Target Recognition, Vol. 3374, pp. 14–25, 1998.

19. Popp, R., Pattipati, K., Bar-Shalom, Y., and Gassner, R., An adaptive m-best assignment algorithm and parallelization for multitarget tracking, In Proceedings of 1998 IEEE Aerospace Conference, Snowmass, CO, Vol. 5, pp. 71–84, 1998.

20. Chummun, M., Kirubarajan, T., Pattipati, K.R., and Bar-Shalom, Y., Efficient multidimensional data association for multisensor-multitarget tracking using clustering and assignment algorithms, In Proceedings of 2nd International Conference on Information Fusion, 1999.

21. Poore, A.B., Multidimensional assignment formulation of data association problems arising from multitarget tracking and multisensor data fusion, Computational Optimization and Applications, 3(1), 27–57, 1994.

22. Drummond, O.E., Target tracking, In Wiley Encyclopedia of Electrical and Electronics Engineering, Vol. 21, Wiley, New York, NY, pp. 377–391, 1999.

23. Sittler, R.W., An optimal data association problem in surveillance theory, IEEE Transaction on Military Electronics, 8(2), 125, 1964.

24. Nemhauser, G.L. and Wolsey, L.A., Integer and Combinatorial Optimization, Wiley, New York, NY, 1988.

25. Poore, A.B., Rijavec, N., and Barker, T., Data association for track initiation and extension using multiscan windows, In Proceedings of SPIE Conference: Signal and Data Processing of Small Targets, Vol. 1698, pp. 432–437, 1992.

26. Poore, A.B. and Drummond, O.E., Track initiation and maintenance using multidimensional assignment problems, In Lecture Notes in Economics and Mathematical Systems, Pardalos, P.M., Hearn, D., and Hager, W. (Eds.) Vol. 450, Springer-Verlag, New York, NY, p. 407, 1997.

27. Garvey, M. and Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., San Francisco, CA, 1979.

28. Hiriart-Urruty, J.B. and Lemaréchal, C., Convex Analysis and Minimization Algorithms I, Springer-Verlag, Berlin, 1993.

29. Hiriart-Urruty, J.-B. and Lemaréchal, C., Convex Analysis and Minimization Algorithms II, Springer-Verlag, Berlin, 1993.

30. Bertsekas, D.P., Network Optimization, Athena Scientific, Belmont, MA, 1998.

31. Jonker, R. and Volgenant, A., A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing, 38(4), 325–340, 1987.

32. Murphey, R., Pardalos, P., and Pitsoulis, L., A GRASP for the multi-target multi-sensor tracking problem, In Networks, Discrete Mathematics and Theoretical Computer Science Series, Vol. 40, American Mathematical Society, pp. 277–302, 1998.

33. Murphey, R., Pardalos, P., and Pitsoulis, L., A parallel GRASP for the data association multidimensional assignment problem, In Parallel Processing of Discrete Problems, IMA Volumes in Mathematics and its Applications, Vol. 106, Springer-Verlag, New York, NY, pp. 159–180, 1998.

34. Robertson, A., A set of greedy randomized adaptive local search procedure (GRASP) implementations for the multidimensional assignment problem, Computational Optimization and Applications, 19(2), 145–164, 2001.

35. Poore, A.B., Rijavec, N., Barker, T., and Munger, M., Data association problems posed as multidimensional assignment problems: numerical simulations, In Proceedings of SPIE Conference: Signal and Data Processing of Small Targets, Drummond, O.E. (Ed.) Vol. 1954, pp. 564–571, 1993.

36. Schramm, H. and Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM Journal on Optimization, 2, 121, 1992.

37. Kiwiel, K.C., Methods of descent for nondifferentiable optimization, In Lecture Notes in Mathematics, Vol. 1133, Springer-Verlag, Berlin, 1985.

38. Poore, A.B. and Rijavec, N., Multidimensional assignment problems, and Lagrangian relaxation, In Proceedings of The SDI Panels on Tracking, Issue 2, Institute for Defense Analyses, pp. 3–51 to 3–74, 1991.

39. Poore, A.B. and Rijavec, N., A numerical study of some data association problems arising in multitarget tracking, In Large Scale Optimization: State of the Art, Hager, W.W., Hearn, D.W., and Pardalos, P.M. (Eds.), Kluwer Academic Publishers B.V., Boston, MA, pp. 347–370, 1994.

40. Shor, N.Z., Minimization Methods for Non-Differentiable Functions, Springer-Verlag, New York, NY, 1985.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 13 Data Association Using Multiple-Frame Assignments

Create new playlist

Sign In

Sign Up

Table of Contents for
13 Data Association Using Multiple-Frame Assignments