Analytic Combinatorics for Multi-Object Tracking & Higher-Level Fusion

Presenter
Title

Roy Streit

Country
USA
Affiliation
Metron Inc.

Presentation Menu

Abstract

Exact solutions of many problems in tracking have high computational complexity and are impractical for all but the smallest of problems. Practical implementations entail approximation. There is a bewildering variety of established trackers available and practicing engineers and/or researchers often study them almost in isolation of each other without fully understanding what these trackers are about and how they are inter-related. One reason for this is that these filters have different combinatorial problems which are approached by explicitly enumerating the feasible solutions. The enumeration is usually a highly detailed, hard to understand accounting scheme specific to the filter and the details cloud understanding the filter and make it hard to compare different filters. On the other hand, the analytic combinatoric approach presented in this tutorial avoids the heavy accounting burden and provides a solid tool to work with. This tool is the derivative of multivariate calculus, which all engineers easily understand.

This lecture is designed to facilitate understanding of the classical theory of Analytic Combinatorics (AC) and how to apply it to problems in multi-object tracking and higher level data fusion. AC is an economical technique for encoding combinatorial problems—without information loss—into the derivatives of a generating function (GF). Exact Bayesian filters derived from the GF avoid the heavy accounting burden required by traditional enumeration methods. Although AC is an established mathematical field, it is not widely known in either the academic engineering community or the practicing data fusion/tracking community. This tutorial lays the groundwork for understanding the methods of AC, starting with the GF for the classical Bayes-Markov filter. From this cornerstone, we derive many established filters (e.g., PDA, JPDA, JIPDA, PHD, CPHD, MultiBernoulli, MHT) with simplicity, economy, and insight. We also show how to use the saddle point method (method of stationary phase) to find low complexity approximations of probability distributions and summary statistics.