Approximate Track Automata - Combining the Best of MHT and GBT for High Value Target Tracking

Lucas Finn, Steven Schoenecker, Lake Bookman, John Grimes

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

1 Citation (Scopus)


Maintaining tracks on High-Value Targets (HVTs) in dense multi-target environments remains a computationally challenging problem. Approaches must trade off hypothesis management with state estimation accuracy in the presence of finite sensing and computational capabilities. This problem becomes more difficult when sensors provide additional, infrequent features: information that correlates track states over long timescales such as target size and color, or unique identifiers such as a license plate. Traditional real-time Multi-Hypothesis Tracking (MHT) algorithms must prune hypotheses before feature information arrives, often removing the correct association hypothesis from the solution space. Graph-Based Track stitching (GBT) algorithms suffer from two related problems: they rely on an upstream tracking algorithm to correctly associate measurements across short timescales, and must still associate tracks in the presence of infrequent feature information. As a result, the HVT tracking problem requires correctly assigning reports to tracks on both short and long timescales. In this paper, we extend the Approximate Track Automata (ATA) algorithm to perform dynamic hypothesis management given a set of HVT hypotheses and feature information models. The original ATA algorithm applied a single strategy to manage the entire hypothesis space; we tailor that approach here given HVTs and target features. We compare traditional tracking metrics such as root mean square error, probability of track, and track purity for HVT and background targets. In addition, we investigate the effect of scaling the number of Integer Linear Program (ILP) variables, i.e. the number of MHT and ATA hypotheses, on these metrics. Interestingly, we note that while solving ILPs is (in general) NP-complete, the ILP constraint matrices and cost vectors contain structure that often results in efficient runtimes in practice. We offer possible explanations as to why the ILP problem structure allows this near-polynomial runtime.

Original languageEnglish
Title of host publication2020 IEEE Aerospace Conference, AERO 2020
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages9
ISBN (Electronic)9781728127347
Publication statusPublished - Mar 2020
Externally publishedYes
Event2020 IEEE Aerospace Conference, AERO 2020 - Big Sky, United States of America
Duration: 7 Mar 202014 Mar 2020

Publication series

NameIEEE Aerospace Conference Proceedings
ISSN (Print)1095-323X


Conference2020 IEEE Aerospace Conference, AERO 2020
Country/TerritoryUnited States of America
CityBig Sky

Cite this