The Maximum Weight Independent Set Problem for Data Association in Multiple Hypothesis Tracking

Multitarget tracking (MTT) hinges upon the solution of a data association problem in which observations across scans are partitioned into tracks and false alarms so that accurate estimates of true targets can be recovered. In this chapter, we describe a methodology for solving this data association problem as a maximum weight independent set problem (MWISP). This MWISP approach has been used successfully for almost a decade in fielded sensor systems using a multiple hypothesis tracking (MHT) framework, but has received virtually no attention in the tracking literature, nor has it been recognized as an application in the clique/independent set literature. The primary aim of this chapter is to simultaneously fill these two voids. Second, we show that the MWISP formulation is equivalent to the multidimensional assignment (MAP) formulation, one of the most widely documented approaches for solving the data association problem in MTT. Finally, we offer a qualitative comparison between the MWISP and MAP formulations, while highlighting other important practical issues in data association algorithms that are commonly overlooked by the optimization community.