Skip to main content
EURASIP Journal on Advances in Signal Processing
Download PDF
  • Research Article
  • Open access
  • Published:

Nonmyopic Sensor Scheduling and its Efficient Implementation for Target Tracking Applications

EURASIP Journal on Advances in Signal Processing volume 2006, Article number: 031520 (2006) Cite this article

Abstract

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. Krishnamurthy V: Algorithms for optimal scheduling and management of hidden Markov model sensors. IEEE Transactions on Signal Processing 2002, 50(6):1382–1397. 10.1109/TSP.2002.1003062

    Article  MathSciNet  Google Scholar 

  2. Castanon DA: 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.

    Article  Google Scholar 

  3. Doucet A, Vo B-N, Andrieu C, Davy M: 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.

    Article  Google Scholar 

  4. Kreucher C, Kastella K, Hero AO 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.

    Google Scholar 

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

    Google Scholar 

  6. Singh S, Vo B-N, Doucet A, Evans R: 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.

    Google Scholar 

  7. Kalandros M, Pao LY: Covariance control for multisensor systems. IEEE Transactions on Aerospace and Electronic Systems 2002, 38(4):1138–1157. 10.1109/TAES.2002.1145739

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  10. Liu J, Petrovic D, Zhao F: 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.

    Google Scholar 

  11. Korf RE: Artificial intelligence search algorithms. In CRC Handbook of Algorithms and Theory of Computation. CRC Press, Boca Raton, Fla, USA; 1998:1–20. chapter 36

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  14. Gupta V, Chung T, Hassibi B, Murray RM: 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.

    Google Scholar 

  15. Short RD: Sting Ray—a sound-seeking missile. IEE Review 1989, 35(11):419–423. 10.1049/ir:19890177

    Article  Google Scholar 

  16. Chhetri AS, Morrell D, Chakrabarti C, Papandreou-Suppappola A, Spanias A, Zhang J: 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.

    Google Scholar 

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

    Article  Google Scholar 

  18. Bertsekas DP: Dynamic Programming and Optimal Control. Volume 1 & 2. Athena Scientific, Belmont, Mass, USA; 2001.

    MATH  Google Scholar 

  19. Ku R, Athans M: On the adaptive control of linear systems using the open-loop-feedback-optimal approach. IEEE Transactions on Automatic Control 1973, 18(5):489–493. 10.1109/TAC.1973.1100368

    Article  Google Scholar 

  20. Tse E, Athans M: Adaptive stochastic control for a class of linear systems. IEEE Transactions on Automatic Control 1972, 17(1):38–52. 10.1109/TAC.1972.1099867

    Article  MathSciNet  Google Scholar 

  21. Balduzzi F, Menga G: 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.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  25. Wang H, Yao K, Pottie G, Estrin D: 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.

    Google Scholar 

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

    Google Scholar 

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

    Book  Google Scholar 

  28. Chhetri AS, Morrell D, Papandreou-Suppappola A: 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.

    Google Scholar 

  29. Liu JRJ, Reich J, Zhao F: Collaborative in-network processing for target tracking. EURASIP Journal on Applied Signal Processing 2003, 2003(4):378–391. 10.1155/S111086570321204X

    MATH  Google Scholar 

  30. Chhetri AS, Morrell D, Papandreou-Suppappola A: 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.

    Google Scholar 

  31. Julier SJ, Uhlmann JK: 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.

    Google Scholar 

  32. Chhetri AS, Morrell D, Papandreou-Suppappola A: 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.

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  34. Fisher ML:Optimal solution of vehicle routing problems using minimum-trees. Operations Research 1994, 42(4):626–642. 10.1287/opre.42.4.626

    Article  MathSciNet  Google Scholar 

  35. Breuel TM: 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.

    MATH  Google Scholar 

  36. Bertsekas DP, Castanon DA: Rollout algorithms for stochastic scheduling problems. Journal of Heuristics 1999, 5(1):89–108. 10.1023/A:1009634810396

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Amit S Chhetri & Antonia Papandreou-Suppappola

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

    Darryl Morrell

Authors
  1. Amit S Chhetri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Darryl Morrell
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antonia Papandreou-Suppappola
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amit S Chhetri.

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions

About this article

Cite this article

Chhetri, A.S., Morrell, D. & Papandreou-Suppappola, A. Nonmyopic Sensor Scheduling and its Efficient Implementation for Target Tracking Applications. EURASIP J. Adv. Signal Process. 2006, 031520 (2006). https://doi.org/10.1155/ASP/2006/31520

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1155/ASP/2006/31520

Keywords