An interior point linear programming approach to two-scan data association

L. I. Xinliang, Zhi Quan Luo, K. Max Wong, Eloibosse

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


We present an efficient two-scan data association method (TSDA) based on an interior point linear programming (LP) approach. In this approach, the TSDA problem is first formulated as a 3-dimensional assignment problem, and then relaxed to a linear program; the latter is subsequently solved by the highly efficient homogeneous, self-dual interior point LP algorithm. When the LP algorithm generates a fractional optimal solution, we use a technique similar to the joint probabilistic data association method (JPDA) to compute a weighted average of the resulting fractional assignments, and use it to update the states of the existing tracks generated by Kaiman filters. Unlike the traditional single scan JPDA method, our TSDA method provides an explicit mechanism for track initiation. Extensive computer simulations have demonstrated that the new TSDA method is not only far more efficient in terms of low computational complexity, but also considerably more accurate than the existing single-scan JPDA method.

Original languageEnglish (US)
Pages (from-to)474-490
Number of pages17
JournalIEEE Transactions on Aerospace and Electronic Systems
Issue number2
StatePublished - 1999

Bibliographical note

Funding Information:
This research is supported by a grant from the Defense Research Establishment of Canada at Valcartier, Quebec, Canada.

Fingerprint Dive into the research topics of 'An interior point linear programming approach to two-scan data association'. Together they form a unique fingerprint.

Cite this