An analytical comparison of random and exhaustive search of an expandıng ares with binary sensors

Bu çalışmada zaman ile birlikte genişleyen bir sahanın kesin menzilli sensörler ile aranması problemi incelenmiştir. Söz konusu problem bir hedefin süratinin ve zaman gecikmeli olarak mevkisinin bilindiği problemlere uygulanabilir. Çalışma kapsamında gelişigüzel ve tam olmak üzere iki tip arama modeli ele alnımış ve etkinliklerini birikimli tespit olasılığıyla ölçen formüller incelenmiştir. Ayrıca planlayıcıya arama gayretini planlama ve kullanmada destek sağlamak üzere faydalı analitik sonuçlar da elde edilmiştir. Elde edilen sonuçlar Monte Carlo simülasyonları ile doğrulanmıştır.

Genişleyen bir sahanın kesin menzilli sensörler ile gelişigüzel ve tam aranmasının analitik olarak karşılaştırılması

In this study we analyze the problem of searching an expanding area over time with binary sensors. This problem can be applied to scenarios where the searcher has the location information of a mobile target with a time delay and the target speed is known. We consider two basic search models, random and exhaustive, and analyze formulas to measure the effectiveness of search process in terms of cumulative detection probability and compare the results for both plans. We also derive analytical expressions that will assist the decision maker in planning and utilizing his/her search effort. The results are verified with Monte Carlo simulations.

___

  • 1. Anastasio, V., Colone, F., Lallo,A.D., Farina, A., Gumi- ero, F., Lombardo, P. 2010. “Optimization of Multistatic Passive Radar Geometry Based on CRLB with Uncertain Observations,” Proceedings of the 7th European Radar Conference.
  • 2. Barrett, S.R. 2007. “Optimizing Sensor Placement for Intruder Detection with Genetic Algorithms,” Intelligence and Security Informatics, 23-24 May, 2007, pp.185-188.
  • 3. Benkoski, S., Monticino, M., Weisinger, J. 1991. “A Survey of the Search Theory Literature,” Naval Research Logistics, Vol. 38, pp. 469-494.
  • 4. Cardei, M., Wu, J. 2004. “Handbook of Sensor Networks,” Chapter: Coverage in Wireless Sensor Networks, CRC Press.
  • 5. Coggins, P.B. 1971. “Detection Probability Computations for Random Search of an Expanding Area,” Committee on Undersea Warfare, National Research Council, National Academy of Scieaces, 2101 Constitution Avenue, N.W., Washington, D.C. 20418
  • 6. Cooper, D.C., Frost, J.R., Robe, R.Q. 2003. “Compatibility of Land SAR Procedures with Search Theory,” Potomac Management Group, Inc.
  • 7. Daun, M., Ehlers, F. 2010. “Tracking Algorithms for Mul- tistatic Sonar Systems,” EURASIP Journal on Advances in Signal Processing.
  • 8. David, W.K., Warren, L.J.F., Mohamed, A.E. 2009. “Probability of Target Presence for Multistatic Sonar Ping Sequencing,” IEEE Journal of Oceanic Engineering, Vol. 34, No.4.
  • 9. DelBalzo, D.R., Kierstead, D.P., Stangl, K.C. 2005. “Oce- anographic Effects on Optimized Multistatic Sonobuoy Fields,” Proceedings of MTS/IEEE, Vol 2, pp. 1319-1324.
  • 10. Douglas, W.G. 1993. “Randomized search strategies with imperfect sensors,” Proceedings of SPIE Mobile Robots VIII, Boston, vol 2058, pp 270-279.
  • 11. Ehlers, F., Daun, M., Ulmke, M. 2009. “System Design and Fusion Techniques for Multistatic Active Sonar,” IEEE Oceans.
  • 12. El-Jaber, M., Osman, A., Mellema, G.R., Nourledin, A. 2009. “Target Tracking in Multi-Static Active Sonar Systems Using Dynamic Programming and Hough Trans- form,” 12th International Conference on Information Fusion.
  • 13. Erdinc, O., Willett, P., Coraluppi, S. 2006. “Multistatic Sensor Placement: A Tracking Approach,” Information Fusion Conference.
  • 14. Golen, E.F. 2009. “Intelligent Deployment Strategies For Passive Underwater Sensor Networks,” PhD Thesis, Rochester Institute of Technology.
  • 15. Holland, J.H. 1975. “Adaptation in Natural and Artificial Systems,” University of Michigan, Ann Arbor.
  • 16. Jourdan, D.B., Weck, O.L. 2004. “Layout Optimization for a Wireless Sensor Network Using a Multi-objective Genetic Algorithm,” Vehicular Technology Conference. p. 2466-2470.
  • 17. Karataş, M. 2012. “Optimization of Distributed Under- water Sensor Networks with Mixed Integer Non-Linear Programming,” Marmara University Journal of Science, Vol. 24(3), pp. 77-92.
  • 18. Kierstead, D.P. 2003. “A Genetic Algorithm Applied to Search Paths in Complicated Environments,” Military Operations Research, V8, N2.
  • 19. Koopman, B.O. 1946. “Search and screening (OEG Report No. 56, The Summary Reports Group of the Columbia University Division of War Research),” Alexandria, Virgi- nia: Center for Naval Analyses.
  • 20. Koopman, B.O. 1953. “The Optimum Distribution of Effort,” Operations Research, 1, pp. 52-63.
  • 21. Koopman, B.O. 1980. “Search and Screening: General Principles with Historical Applications,” Revised. New York, NY: Pergamon Press.
  • 22. Koopman, B.O. 1999. “Search and Screening, General Principles with Historical Applications. Rev. ed.,” Military Operations Research Society: Alexandria, Virginia
  • 23. Lance, C., Carl, G. and Fill, R. 2003. “Search Theory, Agent-Based Simulation, and U-Boats in the Bay of Biscay,” Proceedings of the 2003 Winter Simulation Conference S. Chick, P. J. Sánchez, D. Ferrin, and D. J. Morrice, eds.
  • 24. McCue, B. 1990. “U-Boats in the Bay of Biscay,” National Defense University: Washington, DC.
  • 25. Orlando, D., Ehlers, F. and Ricci, G. 2010. “A Maximum Likelihood Tracker for Multistatic Sonars,” 13th Conferen- ce on Information Fusion.
  • 26. Orlando, D. and Ehlers, F. 2011. “Advances in Multistatic Sonar,” Book Chapter in Sonar Systems, INTECH.
  • 27. Oxford Dictionary. 2010. Oxford University Press, New York, Third Edition.
  • 28. Patrick, N.N., Warren, L.J.F. and Mohamed, A.E. 2006. “Multiobjective Multistatic Sonar Sensor Placement,” IEEE Congress on Evolutionary Computations.
  • 29. Raisanen, L. and Whitaker, R.M. 2003. “Multi-objective Optimization in Area Coverage Problems for Cellular Communication Networks: Evaluation of an Elitist Evolutionary Strategy,” ACM Symposium on Applied Computing, SAC ’03, Melbourne, FL, March 9-12, 2003, p. 714-720.
  • 30. Ranganathan, P., Ranganathan, A., Minai, A. and Berman, K. 2006. “A Self-Organizing Heuristic for Building Optimal Heterogeneous Ad-Hoc Sensor Networks,” IEEE Interna- tional Conference on Networking, Sensing, and Control, ICNSC ’06, p. 774-779.
  • 31. Saksena, A. and Wang, I.J. 2008. “Dynamic Ping Optimization for Surveillance in Multistatic Sonar Buoy Networks with Energy Constraints,” IEEE Conference on Decision and Control.
  • 32. Skip, R. and Stoffel, B.C. 2008. “The Initial and Other Planning Points for Search” SAR Spotlight Forum
  • 33. Spanache, S., Escobet, T. and Trave-Massuyes, L.2004.“Sensor Placement Optimisation Using Genetic Algorithms,” 15th International Workshop on Principles of Diagnosis, Carcassonne, France.
  • 34. Stone, L.D. 1989. “Theory of Optimal Search,” 2nd edition, Military Applications Section Operations Research Society of America, Academic Press:New York
  • 35. Tharmarasa, R., Kirubarajan, T. and Lang, T. 2009. “Joint Path Planning and Sensor Subset Selection for Multis- tatic Sensor Networks,” Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Security and Defense Applications.
  • 36. Wagner, D.H., Mylander, C.W. and Sanders, T.H. 1999. “Naval Operations Analysis,” Naval Institute Press, 3rd edition.
  • 37. Walsh, M.J. and Wettergren, T.A. 2008. “Search Performance Prediction for Multistatic Sensor Fields,” Technical Report, Naval Undersea Warfare Center, Newport, RI.
  • 38. Wang, I.J., Lim, J.H. ve Terzis, A. 2008. “Energy-Effi- cient Sensor Management in Multi-Static Active Sonar Networks,” IEEE Signals, Systems and Computers, 42nd Asilomar Conference.
  • 39. Washburn, A.R. 1980. “Expanding Area Search Experiments,” Technical Report, NPS55-80-017, Naval Postgra- duate School, Monterey, CA.
  • 40. Washburn, A.R. 1981. “An Upper Bound Useful in Optimizing Search for a Moving Target,” Operations Research, 29, pp. 1227-1230.
  • 41. Washburn, A.R. 1983. “Search for a Moving Target: The FAB Algorithm,” Operations Research, 31, pp. 739-751.
  • 42. Washburn, A.R. 2002. “Search and Detection,” Fourth ed. Linthicum, Maryland: Institute for Operations Research and the Management Sciences.
  • 43. Washburn, A.R. 2010. “A Multistatic Sonobuoy Theory,” Technical Report, Naval Postgraduate School, Monterey, CA.
  • 44. Xue, W., Aiguo, J. and Sheng, W. 2005. “Mobile Agent Based Moving Target Monitoring Methods in Wireless Sensor Networks,” IEEE International Symposium on Communications and Information Technology, ISCIT 2005, October 12-14, 2005, p. 21-25.