M.Sc Thesis

M.Sc StudentSigalov Daniel
SubjectData Association in Multi Target Tracking Using Cross
Entropy Based Algorithms
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


In target tracking, data association is the problem of determining which observation is generated by which target or clutter. For highly cluttered and dense scenarios this turns out to be a formidable task computationally.  In the multi scan formulation, measurements from several scans are collected and processed together. Namely, states are updated upon receiving several sets of data. In this work we formulate the multi-scan problem via hard data association - looking for a partition of measurements into disjoint sets representing different targets and additional set of measurements classified as false alarms. The goal is to maximize the posterior probability of a partition, which may be determined by the dynamical and measurement models. Multi-scan data association may be stated as a multidimensional assignment problem which is known to be NP hard if the number of scans (sets of measurements) is greater or equal to three. Thus, we cannot expect to obtain an optimal solution in polynomial time and efficient heuristic or approximate solutions should be considered. We develop a family of algorithms based on the Cross Entropy (CE) method which find suboptimal solutions to the problem in polynomial time. The CE method is a recent optimization heuristic that has proved useful in many Combinatory al optimization problems such as the Traveling Salesman, MaxCut, Quadratic Assignment, etc. It is a global search method, thus the risk of getting trapped in a local extremum is reduced. Originally, the CE method was designed for estimation of probabilities of rare events, and later on as a generic optimization algorithm. It randomizes the deterministic problem by introducing a family of probability density functions parameterized by a parameter vector v. The goal is to converge to a density concentrated near the global optimum of the cost function. This is achieved by alternating between two successive steps - sampling from the current density and updating the parameter vector as a maximum likelihood of a small percentile of the better samples. We design our algorithms in the following steps. First, we define a parametric scheme to represent probability distributions over the solution space of the multi scan data association problem. Then, we propose an efficient sampling scheme which allows generation of feasible solutions to the problem. Using the parametric scheme and the sampling procedure we invoke the Cross Entropy method and its variants. Finally, we test the resulting algorithms via extensive simulation, and demonstrate their superior accuracy relative to other recent methods.