Skip Navigation Links
Journal of Vibration Testing and System Dynamics

C. Steve Suh (editor), Pawel Olejnik (editor),

Xianguo Tuo (editor)

Pawel Olejnik (editor)

Lodz University of Technology, Poland

Email: pawel.olejnik@p.lodz.pl

C. Steve Suh (editor)

Texas A&M University, USA

Email: ssuh@tamu.edu

Xiangguo Tuo (editor)

Sichuan University of Science and Engineering, China

Email: tuoxianguo@suse.edu.cn


A Novel Decision-Making Framework for Probabilistic Search

Journal of Vcibration Testing and System Dynamics 3(4) (2019) 469--480 | DOI:10.5890/JVTSD.2019.12.005

Liang Yu$^{1}$,$^{2}$, Yongchun Liu$^{3}$, Da Lin$^{4}$

$^{1}$ School of Automation & Information Engineering, Sichuan University of Science & Engineering, Yibin, 644000, P.R. China

$^{2}$ Artificial Intelligence Key Laboratory of Sichuan Province, Sichuan University of Science & Engineering, Yibin, 644000, P.R. China

$^{3}$ School of Physics & Electronics Engineering, Sichuan University of Science & Engineering, Yibin, 644000, P.R. China

$^{4}$ School of Information Engineering, Xuzhou University of Technology, Xuzhou, 221000, P.R. China

Download Full Text PDF

 

Abstract

In this paper, we present the search problem formulated as a decision making problem, the search agent decides whether the target is present in the search region, and if so, where it is located. Then we propose a sequential decision-making framework for a search agent to find a lost target within a bounded region with the searcher motion constraints and imperfect observations being considered. This framework enables the theoretical study to the evolution of the search decision, then we propose two effective adaptive search strategies, which have the advantage of requiring less computation than traditional search strategy. Simulation results shows that the proposed adaptive search strategies have a better performance. Finally, the proposed control strategies are analyzed from different perspectives in detail.

Acknowledgments

This work is supported by National Natural Science Foundation of China (No. 61640223), the Open Research Project from SKLMCCS (No. 20160106), Sichuan Provincial Natural Science Foundation (No. 2016JY0179), and The Key Project of Artificial Intelligence Key Laboratory of Sichuan Province (No. 2016RZJ02), the Innovation Fund of Postgraduate, Sichuan University of Science & Engineering (No. y2018042), Xuzhou Engineering College Cultivation Project (XKY2018126).

References

  1. [1]  Koopman, B.O. (1957), The theory of search, part III. the optimum distribution of searching effort, Operations Research, 5, 613-626.
  2. [2]  Stone, L.D. (1989), Theory of Optimal Search, 2-nd ed, Operations Research Society of America, Arlington, VA, 38, 415-422.
  3. [3]  Washburn, A.R. (2002), Search and detection, Institute for Operations Research and the Management Sciences.
  4. [4]  Chung, T.H. and Burdick, J.W. (2007), A decision-making framework for control strategies in probabilistic search, Proceedings 2007 IEEE International Conference on Robotics and Automation, 4386-4393.
  5. [5]  Chung, T.H. and Burdick, J.W. (2008), Multi-agent probabilistic search in a sequential decision-theoretic framework, 2008 IEEE International Conference on Robotics and Automation, 146-151.
  6. [6]  Lanillos, P., Gan, S.K., Besada-Portas, E., et al. (2014),Multi-UAV target search using decentralized gradientbased negotiation with expected observation, Information Sciences, 282, 92-110.
  7. [7]  Kress, M., Lin, K.Y., and Szechtman, R. (2008), Optimal discrete search with imperfect specificity, Mathematical methods of operations research, 68(3), 539-549.
  8. [8]  Wong, E.M, Bourgault, F., and Furukawa, T. (2005), Multi-vehicle Bayesian search for multiple lost targets, Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 3169-3174.
  9. [9]  Bourgault, F., Furukawa, T., and Durrant-Whyte, H.F. (2003), Optimal search for a lost target in a bayesian world, Field and service robotics, Springer, Berlin, Heidelberg, 209-222.
  10. [10]  Berger, J.O. (2013), Statistical decision theory and Bayesian analysis, Springer Science & Business Media.
  11. [11]  Thrun, S., Burgard, W., and Fox, D. (2005), Probabilistic robotics, MIT press.
  12. [12]  Assaf, D. and Zamir, S. (1985), Optimal sequential search: a Bayesian approach, The Annals of Statistics, 1213-1221.
  13. [13]  Vidal, R., Shakernia, O., Kim, H.J., et al. (2002), Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation, IEEE Transactions on Robotics and Automation, 18(5), 662-669.
  14. [14]  Acar, E.U., Choset, H., Zhang, Y., et al. (2003), Path planning for robotic demining: Robust sensor-based coverage of unstructured environments and probabilistic methods, The International Journal of Robotics Research, 22(7-8): 441-466.
  15. [15]  Chung, T.H. and Burdick J.W. (2012), Analysis of search decision making using probabilistic search strategies, IEEE Transactions on Robotics, 28(1), 132-144.