Unifying Multi-Hypothesis and Graph-Based Tracking with Approximate Track Automata

Multi-target tracking remains a challenging problem, with various approaches addressing different regimes of scenario difficulties. Multi-Hypothesis Tracking (MHT) is often used for short-timescale tracking, while Graph-Based Track stitching (GBT) is often used as a second-stage processor to associate MHT tracks together over time. However, it is often the case that MHT must aggressively prune hypotheses to remain computationally tractable. Moreover, GBT makes strict assumptions about its input, namely Markov or path independence, and is therefore unable to process non-local information such as intermittent attributes on input data. Therefore, both approaches make drastic trade-offs between data association and state estimation: MHT prunes while GBT assumes path independence. We present an approach to the multi-target tracking problem that occupies a “middle” ground between MHT and GBT, reducing to each as a special case. To do this, we represent the current hypothesis set as all those report strings accepted by some automaton: Depending on input statistics (to what extent assignment probabilities are path independent) and on an approximation-fidelity parameter, the automaton will naturally be either an MHT forest, or a min-cost-flow graph, or some intermediate structure. We introduce the formulation, describe algorithms to construct so-called Track Automata, give an Integer Linear Program (ILP) to extract globally optimal tracks from these automata, illustrate key special cases, including where the problem is solvable in polynomial time, and show results for simulated sensor data. In exchange for some user-specified approximation error and polynomial increase in ILP size, the technique is able to delay pruning and improve track purity by implicitly representing many more hypotheses than an MHT forest can.