Back to search

McMaster University

EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING

Abstract

dc:description.abstract

In this work, we propose a novel convex dual approach to the multidimensional dimensional assignment problem, which is an NP-hard binary programming problem. It is shown that the proposed dual approach is equivalent to the Lagrangian relaxation method in terms of the best value attainable by the two approaches. However, the pure dual representation is not only more elegant, but also makes the theoretical analysis of the algorithm more tractable. In fact, we obtain a su cient and necessary condition for the duality gap to be zero, or equivalently, for the Lagrangian relaxation approach to nd the optimal solution to the assignment problem with a guarantee. Also, we establish a mild and easy-to-check condition, under which the dual problem is equivalent to the original one. In general cases, the optimal value of the dual problem can provide a satisfactory lower bound on the optimal value of the original assignment problem. We then extend the purely dual formulation to handle the more general multidimensional assignment problem. The convex dual representation is derived and its relationship to the Lagrangian relaxation method is investigated once again. Also, we discuss the condition under which the duality gap is zero. It is also pointed out that the process of Lagrangian relaxation is essentially equivalent to one of relaxing the binary constraint condition, thus necessitating the auction search operation to recover the binary constraint. Furthermore, a numerical algorithm based on the dual formulation along with a local search strategy is presented. Finally, the newly proposed algorithm is shown to outperform the Lagrangian relaxation method in a number of multi-target tracking simulations.

Degree

thesis:*
Department dc:contributor.department
Electrical and Computer Engineering
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Jingqun
Advisor dc:contributor.advisor
  • Kirubarajan, Thia

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Li, Jingqun. EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING. 2019. http://hdl.handle.net/11375/25001