×

Data association based on optimization in graphical models with application to sensor networks. (English) Zbl 1138.62367

Summary: We propose techniques based on graphical models for efficiently solving data association problems arising in multiple target tracking with distributed sensor networks. Graphical models provide a powerful framework for representing the statistical dependencies among a collection of random variables, and are widely used in many applications (e.g., computer vision, error-correcting codes). We consider two different types of data association problems, corresponding to whether or not it is known a priori which targets are within the surveillance range of each sensor. We first demonstrate how to transform these two problems to inference problems on graphical models. With this transformation, both problems can be solved efficiently by local message-passing algorithms for graphical models, which solve optimization problems in a distributed manner by exchange of information among neighboring nodes on the graph.
Moreover, a suitably reweighted version of the max-product algorithm yields provably optimal data associations. These approaches scale well with the number of sensors in the network, and moreover are well suited to being realized in a distributed fashion. So as to address trade-offs between performance and communication costs, we propose a communication-sensitive form of message-passing that is capable of achieving near-optimal performance using far less communication. We demonstrate the effectiveness of our approach with experiments on simulated data.

MSC:

62P30 Applications of statistics in engineering and industry; control charts
90B18 Communication networks in operations research
62-07 Data analysis (statistics) (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
90C90 Applications of mathematical programming
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chong, C. Y.; Kumar, S., Sensor networks: evolution, opportunities, and challenges, Proc. IEEE, 91, August, 1247-1256 (2003)
[2] (Zhao, F.; Guibas, L., Information Processing in Sensor Networks (2003), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1018.68868
[3] Bar-Shalom, Y.; Fortmann, T. E., Tracking and Data Association (1988), Academic Press: Academic Press Orlando · Zbl 0634.93001
[4] Blackman, S. S., Multiple-Target Tracking with Radar Applications (1986), Artech House: Artech House Dedham, MA
[5] Reid, D. B., An algorithm for tracking multiple targets, IEEE Trans. Automat. Control, AC-24, 843-854 (1979)
[6] Chong, C. Y.; Mori, S.; Chang, K. C., Distributed multitarget multisensor tracking, (Bar-Shalom, Y., Multitarget-Multisensor Tracking: Advanced Applications, vol. 1 (1990), Artech House: Artech House Norwood, MA), 247-295
[7] Liggins, M. E.; Chong, C. Y.; Kadar, I.; Alford, M. G.; Vannicola, V.; Thomopoulos, S., Distributed fusion architectures and algorithms for target tracking, Proc. IEEE, 85, 95-107 (1997)
[8] (Jordan, M. I., Learning in Graphical Models (1999), MIT Press: MIT Press Cambridge, MA)
[9] Cowell, R. G.; Dawid, A. P.; Lauritzen, S. L.; Spiegelhalter, D. J., Probabilistic Networks and Expert Systems (1999), Springer-Verlag · Zbl 0937.68121
[10] Freeman, W. T.; Pasztor, E. C.; Carmichael, O. T., Learning low-level vision, Int. J. Comput. Vis., 40, October, 24-57 (2000) · Zbl 1012.68700
[11] Rabiner, L.; Juang, B. H., A tutorial on hidden Markov models, Proc. IEEE, 77, 257-286 (1989)
[12] McEliece, R. J.; Mckay, D. J.; Cheng, J. F., Turbo decoding as an instance of Pearl’s belief propagation algorithm, IEEE J. Sel. Commun., 16, February, 140-152 (1998)
[13] Pearl, J., Probabilistic Reasoning in Intelligent Systems (1988), Morgan Kaufman: Morgan Kaufman San Mateo
[14] Chou, K. C.; Willsky, A. S.; Benveniste, A., Multiscale recursive estimation, data fusion, and regularization, IEEE Trans. Automat. Control, 39, March, 464-478 (1994) · Zbl 0828.93062
[15] Weiss, Y., Correctness of local probability propagation in graphical models with loops, Neural Comput., 12, 1-41 (2000)
[16] Freeman, W. T.; Weiss, Y., On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs, IEEE Trans. Inform. Theory, 47, 736-744 (2001) · Zbl 1002.94057
[17] Wainwright, M. J.; Jaakkola, T. S.; Willsky, A. S., Tree consistency and bounds on the max-product algorithm and its generalizations, Stat. Comput., 14, April, 143-166 (2004)
[18] Wainwright, M. J.; Jaakkola, T. S.; Willsky, A. S., Tree-based reparameterization framework for analysis of sum-product and related algorithms, IEEE Trans. Inform. Theory, 49, May, 1120-1146 (2003) · Zbl 1063.68079
[19] M.J. Wainwright, T.S. Jaakkola, A.S. Willsky, MAP estimation via agreement on (hyper)trees: message-passing and linear programming approaches, in: Proc. Allerton Conference on Communication, Control and Computing, Monticello, IL, October 2002; M.J. Wainwright, T.S. Jaakkola, A.S. Willsky, MAP estimation via agreement on (hyper)trees: message-passing and linear programming approaches, in: Proc. Allerton Conference on Communication, Control and Computing, Monticello, IL, October 2002 · Zbl 1318.94025
[20] Kurien, T., Issues in the design of practical multitarget tracking algorithms, (Bar-Shalom, Y., Multitarget-Multisensor Tracking: Advanced Applications, vol. 1 (1990), Artech House: Artech House Norwood, MA), 43-83
[21] Brémaud, P., Markov Chains, Gibbs Fields, Monte Carlo Simulations, and Queues (1991), Springer-Verlag
[22] Yedidia, J.; Freeman, W. T.; Weiss, Y., Generalized belief propagation, (Advances in Neural Information Processing Systems, vol. 13 (2001), MIT Press: MIT Press Cambridge, MA), 689-695
[23] Aji, S. M.; McEliece, R. J., The generalized distributive law, IEEE Trans. Inform. Theory, 46, March, 325-343 (2000) · Zbl 0998.65146
[24] Kschichang, F. R.; Frey, B. J.; Loeliger, H., Factor graphs and the sum-product algorithm, IEEE Trans. Inform. Theory, 47, February, 498-519 (2001) · Zbl 0998.68234
[25] Gallager, R. G., Low-Density Parity Check Codes (1963), MIT Press: MIT Press Cambridge, MA · Zbl 0107.11802
[26] Cover, T. M.; Thomas, J. A., Elements of Information Theory (1991), John Wiley: John Wiley New York · Zbl 0762.94001
[27] Ghahramani, Z., Learning dynamic Bayesian networks, (Giles, C. L.; Gori, M., Adaptive Processing of Sequences and Data Structures (1998), Springer-Verlag: Springer-Verlag Berlin), 168-197
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.