Cross-entropy based data association for multi target tracking
Article No.: 30, Pages 1 - 10
Abstract
Multiple-target tracking (MTT) in the presence of spurious measurements poses difficult computational challenges related to the measurement-to-track data association problem. Different approaches have been proposed to tackle this problem, including various approximations and heuristic optimization tools. The Cross Entropy (CE) and the related Parametric MinxEnt (PME) methods are recent optimization heuristics that have proved useful in many combinatorial optimization problems. They are akin to evolutionary algorithms in that a population of solutions is evolved, however the solution improvement mechanism is based on statistical methods of sampling and parameter estimation. In this work we apply the Cross-Entropy method and its recent MinxEnt variants to solve approximately the multiscan version of the data association problem in the presence of misdetections, false alarms, and unknown number of targets. We formulate the algorithms, and explore via simulation their efficiency and performance compared to other recently proposed algorithms.
References
[1]
Y. Bar-Shalom and T. E. Fortmann. Tracking and Data Association. Academic Press, San Diego, 1988.
[2]
Y. Bar-Shalom and X. Li. Multitarget-Multisensor Tracking: Principles and Techniques. 1995.
[3]
Y. Bar-Shalom, X. Li, and T. Kirubarajan. Estimation with Applications to Tracking and Navigation. New York: Wiley, 2001.
[4]
J. Collins and J. Uhlmann. Efficient gating in data association with multivariate distributed states. IEEE Trans. on Aerospace and Electronic Systems, 28(3):909--916, July 1992.
[5]
S. Deb, M. Yeddanapudi, K. Pattipati, and Y. Bar-Shalom. A generalized s-d assignment algorithm for multisensor-multitarget state estimation. IEEE Trans. on Aerospace and Electronic Systems, 33(2):523--538, April 1997.
[6]
M. Garey and D. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Bell Telephone Laboratories, 1979.
[7]
C. L. Morfield. Application of 0--1 integer programming to multitarget tracking problems. IEEE Trans. on Automatic Control, AC-22(3):302--312, June 1977.
[8]
W. Ng, J. Li, S. Godsill, and J. Vermaak. A review of recent result in multiple target tracking. In Proc. of the 4th International Symposium on Image and Signal Processing and Analysis, 2005.
[9]
S. Oh, S. Russel, and S. Sastry. Markov chain monte carlo data association for general multiple-target tracking problems. In Proceedings of the IEEE Conf. on Decision and Control, 2004.
[10]
D. B. Reid. An algorithm for tracking multiple targets. IEEE Trans. on Automatic Control, AC-24(6):843--854, December 1979.
[11]
R. Rubinstein. A stochastic minimum cross-entropy method for combinatorial optimization and rare-event estimation. Methodology and Computing in Applied Probability, (1):1--46, 2005.
[12]
R. Rubinstein. Semi-iterative minimum cross-entropy algorithms for rare-events, counting, combinatorial and integer programming. To appear in Methodology and Computing in Applied Probability, November 2007.
[13]
R. Rubinstein and D. Kroese. The Cross-Entropy Method - A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. Springer Science, 2004.
[14]
R. Rubinstein and D. Kroese. Simulation and the Monte Carlo Method. John Wiley & Sons, Inc., 2007.
[15]
D. Sigalov. Data association in multi target tracking using cross entropy based algorithms. Master's thesis, Technion-Israel Institute of Technology, 2008.
[16]
J. Spall. Introduction to Stochastic Search and Optimization. John Wiley & Sons, Inc., 2003.
Index Terms
- Cross-entropy based data association for multi target tracking
Recommendations
Data association and target identification using range profile
We present a new data association algorithm using range-profile, which has maneuver-following capability. In this approach, targets can be identified as a by-product of the data association, not requiring a separate step for target identification. Early ...
Particle filters for maneuvering target tracking problem
In this paper, we address the target tracking problem for the case of maneuvering target, including single target and multiple target tracking. We propose a suitable model to characterize the maneuvering acceleration and develop a state space model to ...
A Novel Data Association Method for Multi-target Tracking Based on IACA
Advances in Swarm IntelligenceAbstractAiming at the data association problem of multi-target tracking, a data association method for multi-target tracking is given based on an improved Ant Colony algorithm (IACA) in this paper. Firstly, according to the characteristics of multi-target ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Create-Net
Publisher
ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)
Brussels, Belgium
Publication History
Published: 20 October 2008
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 59Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in