Open Access Research Article

Nonmyopic Sensor Scheduling and its Efficient Implementation for Target Tracking Applications

Amit S Chhetri1*, Darryl Morrell2 and Antonia Papandreou-Suppappola1

Author Affiliations

1 Department of Electrical Engineering, Arizona State University, Tempe, AZ 85287, USA

2 Department of Engineering, Arizona State University, Tempe, AZ 85287, USA

For all author emails, please log on.

EURASIP Journal on Advances in Signal Processing 2006, 2006:031520  doi:10.1155/ASP/2006/31520


The electronic version of this article is the complete one and can be found online at: http://asp.eurasipjournals.com/content/2006/1/031520


Received:12 May 2005
Revisions received:1 October 2005
Accepted:8 November 2005
Published:6 April 2006

© 2006 Chhetri et al.

We propose two nonmyopic sensor scheduling algorithms for target tracking applications. We consider a scenario where a bearing-only sensor is constrained to move in a finite number of directions to track a target in a two-dimensional plane. Both algorithms provide the best sensor sequence by minimizing a predicted expected scheduler cost over a finite time-horizon. The first algorithm approximately computes the scheduler costs based on the predicted covariance matrix of the tracker error. The second algorithm uses the unscented transform in conjunction with a particle filter to approximate covariance-based costs or information-theoretic costs. We also propose the use of two branch-and-bound-based optimal pruning algorithms for efficient implementation of the scheduling algorithms. We design the first pruning algorithm by combining branch-and-bound with a breadth-first search and a greedy-search; the second pruning algorithm combines branch-and-bound with a uniform-cost search. Simulation results demonstrate the advantage of nonmyopic scheduling over myopic scheduling and the significant savings in computational and memory resources when using the pruning algorithms.

References

  1. V Krishnamurthy, Algorithms for optimal scheduling and management of hidden Markov model sensors. IEEE Transactions on Signal Processing 50(6), 1382–1397 (2002). Publisher Full Text OpenURL

  2. DA Castanon, Approximate dynamic programming for sensor management. Proceedings of the 36th IEEE International Conference on Decision and Control, December 1997, San Diego, Calif, USA 2, 1202–1207

  3. A Doucet, B-N Vo, C Andrieu, M Davy, Particle filtering for multi-target tracking and sensor management. Proceedings of the 5th International Conference on Information Fusion, July 2002, Annapolis, Md, USA 1, 474–481

  4. C Kreucher, K Kastella, AO Hero III., A Bayesian method for integrated multitarget tracking and sensor management. Proceedings of the 6th International Conference on Information Fusion, July 2003, Cairns, Qld., Australia, 132–139

  5. A Logothetis, A Isaksson, On sensor scheduling via information theoretic criteria. Proceedings of the American Control Conference, June 1999, San Diego, Calif, USA 4, 2402–2406

  6. S Singh, B-N Vo, A Doucet, R Evans, Stochastic approximation for optimal observer trajectory planning. Proceedings of 42nd IEEE International Conference on Decision and Control, December 2003, Maui, Hawaii, USA 6, 6313–6318

  7. M Kalandros, LY Pao, Covariance control for multisensor systems. IEEE Transactions on Aerospace and Electronic Systems 38(4), 1138–1157 (2002). Publisher Full Text OpenURL

  8. ML Hernandez, T Kirubarajan, Y Bar-Shalom, Multisensor resource deployment using posterior Cramér-Rao bounds. IEEE Transactions on Aerospace and Electronic Systems 40(2), 399–416 (2004). Publisher Full Text OpenURL

  9. ML Hernandez, Optimal sensor trajectories in bearings-only tracking. Proceedings of the 7th International Conference on Information Fusion, June-July 2004, Stockholm, Sweden 2, 893–900

  10. J Liu, D Petrovic, F Zhao, Multi-step information-directed sensor querying in distributed sensor networks. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '03), April 2003, Hong Kong 5, 145–148

  11. RE Korf, Artificial intelligence search algorithms. CRC Handbook of Algorithms and Theory of Computation (CRC Press, Boca Raton, Fla, USA, 1998), pp. 1–20 chapter 36 OpenURL

  12. NR Vempaty, V Kumar, RE Korf, Depth-first vs. best-first search. Proceedings of 9th National Conference on Artificial Intelligence (AAAI '91), July 1991, Anaheim, Calif, USA 1, 434–440

  13. R Battiti, G Tecchiolli, The reactive Tabu search. ORSA Journal on Computing 6(2), 126–140 (1994)

  14. V Gupta, T Chung, B Hassibi, RM Murray, Sensor scheduling algorithms requiring limited computation [vehicle sonar range-finder example]. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '04), May 2004, Montreal, Quebec, Canada 3, 825–828

  15. RD Short, Sting Ray—a sound-seeking missile. IEE Review 35(11), 419–423 (1989). Publisher Full Text OpenURL

  16. AS Chhetri, D Morrell, C Chakrabarti, A Papandreou-Suppappola, A Spanias, J Zhang, A unified Bayesian decision theory perspective to sensor networks. Proceedings of the Joint International Symposium on Intelligent Control & 13th Mediterranean Conference on Control and Automation (ISIC-MED '05), June 2005, Limassol, Cyprus, 598–603

  17. MS Arulampalam, S Maskell, N Gordon, T Clapp, A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing 50(2), 174–188 (2002). Publisher Full Text OpenURL

  18. DP Bertsekas, Dynamic Programming and Optimal Control (Athena Scientific, Belmont, Mass, USA, 2001) 1 & 2

  19. R Ku, M Athans, On the adaptive control of linear systems using the open-loop-feedback-optimal approach. IEEE Transactions on Automatic Control 18(5), 489–493 (1973). Publisher Full Text OpenURL

  20. E Tse, M Athans, Adaptive stochastic control for a class of linear systems. IEEE Transactions on Automatic Control 17(1), 38–52 (1972). Publisher Full Text OpenURL

  21. F Balduzzi, G Menga, Open-loop feedback control for hybrid manufacturing systems. Proceedings of the 39th IEEE International Conference on Decision and Control, December 2000, Sydney, NSW, Australia 4, 3144–3150

  22. E Mosca, Optimal, Predictive, and Adaptive Control (Prentice-Hall, Upper Saddle River, NJ, USA, 1994)

  23. Y Nakamura, Geometric fusion: minimizing uncertainty volumes. Data Fusion in Robotics and Machine Intelligence (Academic Press, Boston, Mass, USA, 1992), pp. 457–480

  24. F Zhao, J Liu, J Liu, L Guibas, J Reich, Collaborative signal and information processing: an information-directed approach. Proceedings of the IEEE 91(8), 1199–1209 (2003). Publisher Full Text OpenURL

  25. H Wang, K Yao, G Pottie, D Estrin, Entropy-based sensor selection heuristic for target localization. Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04), April 2004, Berkeley, Calif, USA, 36–45

  26. JS Manyika, HF Durrant-Whyte, Data Fusion and Sensor Management: A Decentralized Information-Theoretic Approach (Ellis Horwood, New York, NY, USA, 1994)

  27. TM Cover, JA Thomas, Elements of Information Theory (John Wiley & Sons, New York, NY, USA, 1991)

  28. AS Chhetri, D Morrell, A Papandreou-Suppappola, Scheduling multiple sensors using particle filters in target tracking. Proceedings of IEEE Workshop on Statistical Signal Processing, September 2003, St. Louis, Mo, USA, 529–532

  29. JRJ Liu, J Reich, F Zhao, Collaborative in-network processing for target tracking. EURASIP Journal on Applied Signal Processing 2003(4), 378–391 (2003). Publisher Full Text OpenURL

  30. AS Chhetri, D Morrell, A Papandreou-Suppappola, The use of particle filtering with the unscented transform to schedule sensors multiple steps ahead. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '04), May 2004, Montreal, Quebec, Canada 2, 301–304

  31. SJ Julier, JK Uhlmann, Reduced sigma point filters for the propagation of means and covariances through nonlinear transformations. Proceedings of the American Control Conference, May 2002, Anchorage, Alaska, USA 2, 887–892

  32. AS Chhetri, D Morrell, A Papandreou-Suppappola, Efficient search strategies for non-myopic sensor scheduling in target tracking. Conference Record of the 38th Asilomar Conference on Signals, Systems and Computers, November 2004, Pacific Grove, Calif, USA 2, 2106–2110

  33. D Applegate, R Bixby, V Chvátal, W Cook, On the solution of traveling salesman problems. Documenta Mathematica. Deutsche Mathematiker-Vereinigung 3, 645–656 (1998)

  34. ML Fisher, Optimal solution of vehicle routing problems using minimum -trees. Operations Research 42(4), 626–642 (1994). Publisher Full Text OpenURL

  35. TM Breuel, A comparison of search strategies for geometric branch and bound algorithms. Proceedings of 7th European Conference on Computer Vision (ECCV '02), May 2002, Copenhagen, Denmark 3, 837–850

  36. DP Bertsekas, DA Castanon, Rollout algorithms for stochastic scheduling problems. Journal of Heuristics 5(1), 89–108 (1999). Publisher Full Text OpenURL