A dual- ascent algorithm for the multi-dimensional assignment problem: Application to multi-target tracking

Samhita Vadrevu, Rakesh Nagi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recently we proposed a new Mixed-Integer Linear Programming formulation for the Multi-Target Tracking (MTT) problem and used a standard optimization solver to demonstrate its viability [1]. Subsequently, we provided Graphics Processing Unit (GPU) accelerated algorithms for the underlying Multidimensional Assignment Problem (MAP) with decomposable costs or triplet costs using a Lagrangian Relaxation (LR) framework. Here, we present a Dual-Ascent algorithm that provides monotonically increasing lower bounds and converges in a fraction of iterations required for a subgradient scheme. This approach can handle a large number of targets for many time steps with massive parallelism and computational efficiency. The dual-ascent framework decomposes the MAP into a set of Linear Assignment Problems (LAPs) for adjacent time-steps, which can be solved in parallel using the GPU-accelerated method of [2], [3]. The overall dual-ascent algorithm is able to efficiently solve problems with 100 targets and 100 time-frames with high accuracy. We demonstrate the applicability of our new algorithm to MTT by including realistic issues of missed detections and false alarms. Computational results demonstrate the robustness of the algorithm with good MMEP and ITCP scores and solution times for the larger problems in less than 6 seconds.

Original languageEnglish (US)
Title of host publicationProceedings of 2020 23rd International Conference on Information Fusion, FUSION 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9780578647098
DOIs
StatePublished - Jul 2020
Event23rd International Conference on Information Fusion, FUSION 2020 - Virtual, Pretoria, South Africa
Duration: Jul 6 2020Jul 9 2020

Publication series

NameProceedings of 2020 23rd International Conference on Information Fusion, FUSION 2020

Conference

Conference23rd International Conference on Information Fusion, FUSION 2020
CountrySouth Africa
CityVirtual, Pretoria
Period7/6/207/9/20

Keywords

  • Data Association
  • GPU computing
  • Lagrangian Relaxation
  • Mixed-Integer Linear Programming
  • Multi-dimensional Assignment
  • Multi-target tracking

ASJC Scopus subject areas

  • Computer Vision and Pattern Recognition
  • Information Systems
  • Information Systems and Management
  • Instrumentation

Fingerprint Dive into the research topics of 'A dual- ascent algorithm for the multi-dimensional assignment problem: Application to multi-target tracking'. Together they form a unique fingerprint.

Cite this