Application of 0-1 integer programming to multitarget tracking problems

TLDR

The paper proposes a novel approach to solving multi‑target tracking problems. It models multitarget tracking as an unsupervised pattern‑recognition problem and uses 0‑1 integer programming with a multiple‑hypothesis test to select the most likely track combinations, thereby reducing combinatorial complexity. The approach reformulates multitarget tracking as set‑packing/partitioning problems, enabling rapid solutions via established discrete optimization methods such as implicit enumeration.

Abstract

This paper presents a new approach to the solution of multi-target tracking problems. 0-1 integer programming methods are used to alleviate the combinatorial computing difficulties that accompany any but the smallest of such problems. Multitarget tracking is approached as an unsupervised pattern recognition problem. A multiple-hypothesis test is performed to determine which particular combination of the many feasible tracks is most likely to represent actual targets. This multiple hypothesis test is shown to have the computational structure of the set packing and set partitioning problems of 0-1 integer programming. Multitarget tracking problems that are translated into this form can be rapidly solved, using well-known discrete optimization techniques such as implicit enumeration.