The Role of Occasional Assessment of Sensor Performance for Improved Subsea Search Efficiency

Harun Yetkin

Abstract


This study addresses the subsea search performance of an autonomous underwater vehicle equipped with a search sensor and an environment characterization sensor. The performance of the search sensor is assumed to be dependent on characteristics of the local environment, and thus sensor performance in some locations can be different than in other locations. For the case that the agent is able to occasionally characterize the environment, and therefore estimate the performance of its search sensor, we describe a method for selecting when and where to characterize the environment and when and where to search in order to maximize overall search effectiveness. Our work accounts for false positives, false negatives and uncertainty in the performance of the search sensor that varies geographically. We show that effort applied to characterizing the environment, and therefore the performance of the search sensor, can improve search performance. We derive a utility function that is used to compute the best path and when to switch between the tasks of search and environmental characterization. The objective of the subsea search mission is to maximize the probability of attaining a desired level of risk reduction, and we terminate the search mission as soon as it is found that the desired risk reduction cannot be attained. To the best of our knowledge, this is the first study that addresses the problem of attaining a desired level of risk and stopping the mission when the desired risk is found to be unachievable. Through numerical illustrations, we show realistic scenarios where the findings of this study can be useful to improve search effectiveness and attain the desired level of risk where the standard exhaustive search techniques will fail to achieve.

Keywords


Search Theory; Path Planning; Subsea Search; Attained Bayes Risk.

Full Text:

PDF

References


T. R. Clem, “Sensor technologies for hunting buried sea mines,” OCEANS ’02 MTS/IEEE, vol. 1, pp. 452-460, 2002, doi: 10.1109/OCEANS.2002.1193312.

H. Yetkin, C. Lutz and D. Stilwell, “Acquiring environmental information yields better anticipated search performance,” OCEANS 2016 MTS/IEEE Monterey, pp. 1-6, 2016, doi: 10.1109/OCEANS.2016.7761175.

J. McMahon, H. Yetkin, A. Wolek, Z. J. Waters and D. J. Stilwell, “Towards real-time search planning in subsea environments,” 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 87-94, 2017, doi: 10.1109/IROS.2017.8202142.

H. Yetkin, C. Lutz, and D. J. Stilwell, “A decision-theoretic approach to acquire environmental information for improved subsea search performance,” Ocean Engineering, vol. 204, p. 107280, 2020, doi: 10.1016/j.oceaneng.2020.107280.

J. A. Bucaro et al., “Acoustic identification of buried underwater unexploded ordnance using a numerically trained classifier (l),” The Journal of the Acoustical Society of America, vol. 132, no. 6, pp. 3614–3617, 2012, doi: 10.1121/1.4763997.

M. P. Hayes and P. T. Gough, “Broad-band synthetic aperture sonar,” in IEEE Journal of Oceanic Engineering, vol. 17, no. 1, pp. 80-94, 1992, doi: 10.1109/48.126957.

B. O. Koopman, “The theory of search: III. The optimum distribution of searching effort,” Operations Research, vol. 5, no. 5, pp. 613–738, 1957, doi: 10.1287/opre.5.5.613.

A. Charnes and W. W. Cooper, “The theory of search: optimum distribution of search effort,” Management Science, vol. 5, no. 1, pp. 44–50, 1958, doi: 10.1287/mnsc.5.1.44.

L. D. Stone, J. A. Stanshine, and C. A. Persinger, “Optimal search in the presence of Poisson-distributed false targets,” SIAM Journal on Applied Mathematics, vol. 23, no. 1, pp. 6–27, 1972, doi: 10.1137/0123002.

H. R. Richardson, Search theory, Center for Naval Analyses, 1986.

J. B. Kadane, “Discrete search and the Neyman-Pearson lemma,” Journal of Mathematical Analysis and Applications, vol. 22, no. 1, pp. 156–171, 1968, doi: 10.1016/0022-247X(68)90167-4.

J. B. Kadane, “Optimal whereabouts search,” Operations Research, vol. 19, no. 4, pp. 845–1117, 1971, doi: 10.1287/opre.19.4.894.

M. C. Chew Jr, “Optimal stopping in a discrete search problem,” Operations Research, vol. 21, no. 3, pp. 661–865, 1973, doi: 10.1287/opre.21.3.741.

G. Kimeldorf and F. H. Smith, “Binomial searching for a random number of multinomially hidden objects,” Management Science, vol. 25, no. 11, pp. 1045–1174, 1979, doi: 10.1287/mnsc.25.11.1115.

M. Kress, K. Y. Lin, and R. Szechtman, “Optimal discrete search with imperfect specificity,” Mathematical Methods of Operations Research, vol. 68, no. 3, pp. 539–549, 2008, doi: 10.1007/s00186-007-0197-2.

T. H. Chung and J. W. Burdick, “Analysis of Search Decision Making Using Probabilistic Search Strategies,” in IEEE Transactions on Robotics, vol. 28, no. 1, pp. 132-144, 2012, doi: 10.1109/TRO.2011.2170333.

T. Cheng, B. Kriheli, E. Levner, and C. Ng, “Scheduling an autonomous robot searching for hidden targets,” Annals of Operations Research, vol. 298, no. 1, pp. 95–109, 2021, doi: 10.1007/s10479-019-03141-1.

C. Wang and C. Chen, “A heuristic lowest unknown-degree target search strategy under non-structured environment for multi-agent systems,” Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 24, no. 7, pp. 934–943, 2020, doi: 10.20965/jaciii.2020.p0934.

M. Dunbabin and L. Marques, “Robots for Environmental Monitoring: Significant Advancements and Applications,” in IEEE Robotics & Automation Magazine, vol. 19, no. 1, pp. 24-39, 2012, doi: 10.1109/MRA.2011.2181683.

R. Pyla et al., “Design and development of swarm AGV’s alliance for search and rescue operations,” Journal of Robotics and Control (JRC), vol. 4, no. 6, pp. 791–807, 2023, doi: 10.18196/jrc.v4i6.18392.

T. Furukawa, F. Bourgault, B. Lavis and H. F. Durrant-Whyte, “Recursive Bayesian search-and-tracking using coordinated uavs for lost targets,” Proceedings 2006 IEEE International Conference on Robotics and Automation, pp. 2521-2526, 2006, doi: 10.1109/ROBOT.2006.1642081.

B. Doroodgar, Y. Liu and G. Nejat, “A Learning-Based Semi-Autonomous Controller for Robotic Exploration of Unknown Disaster Scenes While Searching for Victims,” in IEEE Transactions on Cybernetics, vol. 44, no. 12, pp. 2719-2732, 2014, doi: 10.1109/TCYB.2014.2314294.

S. Y. Ku, G. Nejat, and B. Benhabib, “Wilderness search for lost persons using a multimodal aerial-terrestrial robot team,” Robotics, vol. 11, no. 3, p. 64, 2022, doi: 10.3390/robotics11030064.

S. C. Mohamed, A. Fung and G. Nejat, “A Multirobot Person Search System for Finding Multiple Dynamic Users in Human-Centered Environments,” in IEEE Transactions on Cybernetics, vol. 53, no. 1, pp. 628-640, 2023, doi: 10.1109/TCYB.2022.3166481.

B. AlKhlidi, A. T. Abdulsadda, and A. Al Bakri, “Optimal robotic path planning using intelligents search algorithms,” Journal of Robotics and Control (JRC), vol. 2, no. 6, pp. 519–526, 2021, doi: 10.18196/jrc.26132.

S. M. Pollock, Sequential search and detection, Massachusetts Institute of Technology, Dept. of Physics, 1964.

J. M. Dobbie, “Some search problems with false contacts,” Operations Research, vol. 21, no. 4, pp. 867–1016, 1973, doi: 10.1287/opre.21.4.907.

T. H. Chung and J. W. Burdick, “Analysis of Search Decision Making Using Probabilistic Search Strategies,” in IEEE Transactions on Robotics, vol. 28, no. 1, pp. 132-144, 2012, doi: 10.1109/TRO.2011.2170333.

B. Kriheli, E. Levner, and A. Spivak, “Optimal search for hidden targets by unmanned aerial vehicles under imperfect inspections,” American Journal of Operations Research, vol. 6, no. 2, pp. 153–166, 2016, doi: 10.4236/ajor.2016.62018.

J. De Guenin, “Optimum distribution of effort: an extension of the Koopman basic theory,” Operations Research, vol. 9, no. 1, pp. 1–144, 1961, doi: 10.1287/opre.9.1.1.

P. A. Elmore, W. E. Avera, M. M. Harris and K. M. Duvieilh, “Environmental Measurements Derived from Tactical MineHunting Sonar Data,” OCEANS 2007 - Europe, pp. 1-5, 2017, doi: 10.1109/OCEANSE.2007.4302463.

A. Zare and J. T. Cobb, “Sand ripple characterization using an extended synthetic aperture sonar model and MCMC sampling methods,” 2013 OCEANS - San Diego, pp. 1-7, 2013, doi: 10.23919/OCEANS.2013.6741000.

K. Takahashi, J. Igel and H. Preetz, “Clutter Modeling for GroundPenetrating Radar Measurements in Heterogeneous Soils,” in IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 4, no. 4, pp. 739-747, 2011, doi: 10.1109/JSTARS.2011.2106481.

K. Takahashi, H. Preetz, and J. Igel, “Soil properties and performance of landmine detection by metal detector and ground-penetrating radar—soil characterisation and its verification by a field test,” Journal of Applied Geophysics, vol. 73, no. 4, pp. 368–377, 2011, doi: 10.1016/j.jappgeo.2011.02.008.

P. D. Gader, M. Mystkowski and Yunxin Zhao, “Landmine detection with ground penetrating radar using hidden Markov models,” in IEEE Transactions on Geoscience and Remote Sensing, vol. 39, no. 6, pp. 1231- 1244, 2001, doi: 10.1109/36.927446.

S. J. Benkoski, M. G. Monticino, and J. R. Weisinger, “A survey of the search theory literature,” Naval Research Logistics (NRL), vol. 38, no. 4, pp. 469–494, 1991, doi: 10.1002/1520-6750.

T. H. Chung, G. A. Hollinger, and V. Isler, “Search and pursuit-evasion in mobile robotics,” Autonomous robots, vol. 31, no. 4, pp. 299–316, 2011, doi: 10.1007/s10514-011-9241-4.

P. Ghassemi and S. Chowdhury, “Decentralized informative path planning with balanced exploration-exploitation for swarm robotic search,” in Proceedings of the ASME 2019 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, vol. 1, pp. 1–11, doi: 10.1115/DETC2019-97887.

H. L. Kwa, J. Leong Kit, and R. Bouffanais, “Balancing collective exploration and exploitation in multi-agent and multi-robot systems: A review,” Frontiers in Robotics and AI, vol. 8, p. 771520, 2022, doi: 10.3389/frobt.2021.771520.

H. Bai et al., “A study of robotic search strategy for multi-radiation sources in unknown environments,” Robotics and Autonomous Systems, vol. 169, p. 104529, 2023, doi: 10.1016/j.robot.2023.104529.

A. Munir and R. Parasuraman, “Exploration–exploitation tradeoff in the adaptive information sampling of unknown spatial fields with mobile robots,” Sensors, vol. 23, no. 23, p. 9600, 2023, doi: 10.3390/s23239600.

M. Park, S. An, J. Seo and H. Oh, “Autonomous Source Search for UAVs Using Gaussian Mixture Model-Based Infotaxis: Algorithm and Flight Experiments,” in IEEE Transactions on Aerospace and Electronic Systems, vol. 57, no. 6, pp. 4238-4254, 2021, doi: 10.1109/TAES.2021.3098132.

C. Tholen, T. A. El-Mihoub, L. Nolle, and O. Zielinski, “Artificial intelligence search strategies for autonomous underwater vehicles applied for submarine groundwater discharge site investigation,” Journal of Marine Science and Engineering, vol. 10, no. 1, 2021, doi: 10.3390/jmse10010007.

C. Rhodes, C. Liu and W. -H. Chen, “Autonomous Source Term Estimation in Unknown Environments: From a Dual Control Concept to UAV Deployment,” in IEEE Robotics and Automation Letters, vol. 7, no. 2, pp. 2274-2281, 2022, doi: 10.1109/LRA.2022.3143890.

J. C. Gittins, “Bandit processes and dynamic allocation indices,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 41, no. 2, pp. 148–164, 1979, doi: 10.1111/j.2517-6161.1979.tb01068.x.

T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Advances in Applied Mathematics, vol. 6, no. 1, pp. 4–22, 1985, doi: 10.1016/0196-8858(85)90002-8.

O. Besbes, Y. Gur, and A. Z. Chen, “Optimal exploration-exploitation in a multi-armed-bandit problem with non-stationary rewards,” Stochastic Systems, vol. 9, no. 4, pp. 319–337, 2019, doi: 10.2139/ssrn.2436629.

I. Q. Lordeiro, D. B. Haddad and D. O. Cardoso, “Multi-Armed Bandits for Minesweeper: Profiting From Exploration–Exploitation Synergy,” in IEEE Transactions on Games, vol. 14, no. 3, pp. 403-412, 2022, doi: 10.1109/TG.2021.3082909.

M. Tajik, B. M. Tosarkani, A. Makui, and R. Ghousi, “A novel two-stage dynamic pricing model for logistics planning using an exploration–exploitation framework: A multi-armed bandit problem,” Expert Systems with Applications, vol. 246, p. 123060, 2024, doi: 10.1016/j.eswa.2023.123060.

X. Li, Y. Li, and X. Wu, “Empirical gittins index strategies with ε-explorations for multi-armed bandit problems,” Computational Statistics & Data Analysis, vol. 180, p. 107610, 2023, doi: 10.1016/j.csda.2022.107610.

S. Jamieson, J. P. How, and Y. Girdhar, “Finding the optimal explorationexploitation trade-off online through Bayesian risk estimation and minimization,” Artificial Intelligence, vol. 130, p. 104096, 2024, doi: 10.1016/j.artint.2024.104096.

G. Elena, K. Milos, and I. Eugene, “Survey of multiarmed bandit algorithms applied to recommendation systems,” International Journal of Open Information Technologies, vol. 9, no. 4, pp. 12–27, 2021.

D. Padmanabhan, S. Bhat, K. Prabuchandran, S. Shevade, and Y. Narahari, “Dominant strategy truthful, deterministic multi-armed bandit mechanisms with logarithmic regret for sponsored search auctions,” Applied Intelligence, vol. 52, no. 3, pp. 3209–3226, 2022, doi: 10.1007/s10489- 021-02387-2.

D. Markovic, H. Stoji ´ c, S. Schw ´ obel, and S. J. Kiebel, “An empirical ¨ evaluation of active inference in multi-armed bandits,” Neural Networks, vol. 144, pp. 229–246, 2021, doi: 10.1016/j.neunet.2021.08.018.

I. Nasim, A. S. Ibrahim and S. Kim, “Learning-Based Beamforming for Multi-User Vehicular Communications: A Combinatorial Multi-Armed Bandit Approach,” in IEEE Access, vol. 8, pp. 219891-219902, 2020, doi: 10.1109/ACCESS.2020.3043301.

K. K. Damghani, M. Taghavifard, and R. T. Moghaddam, “Decision making under uncertain and risky situations,” in Enterprise Risk Management Symposium Monograph Society of Actuaries-Schaumburg, Illinois, vol. 15, 2009.

J. Bowen and Z.-l. Qiu, “Satisficing when buying information,” Organizational Behavior and Human Decision Processes, vol. 51, no. 3, pp. 471–481, 1992, doi: 10.1016/0749-5978(92)90022-Y.

M. I. Henig, “Risk criteria in a stochastic knapsack problem,” Operations Research, vol. 38, no. 5, pp. 820–825, 1990, doi: 10.1287/opre.38.5.820.

K. E. Wilson, R. Szechtman, and M. P. Atkinson, “A sequential perspective on searching for static targets,” European Journal of Operational Research, vol. 215, no. 1, pp. 218–226, 2011, doi: 10.1016/j.ejor.2011.05.045.

M. Kress, K. Y. Lin, and R. Szechtman, “Optimal discrete search with imperfect specificity,” Mathematical methods of operations research, vol. 68, no. 3, pp. 539–549, 2008, doi: 10.1007/s00186-007-0197-2.

H. Yetkin, C. Lutz and D. Stilwell, “Utility-based adaptive path planning for subsea search,” OCEANS 2015 - MTS/IEEE Washington, pp. 1-6, 2015, doi: 10.23919/OCEANS.2015.7404367.

S. Jaramillo and G. Pawlak, “AUV-based bed roughness mapping over a tropical reef,” Coral Reefs, vol. 30, no. 1, pp. 11–23, 2011, doi: 10.1007/s00338-011-0731-9.

J. Binney and G. S. Sukhatme, “Branch and bound for informative path planning,” 2012 IEEE International Conference on Robotics and Automation, pp. 2147-2154, 2012, doi: 10.1109/ICRA.2012.6224902.

B. W. Wah and Chee Fen Yu, “Stochastic Modeling of Branch-andBound Algorithms with Best-First Search,” in IEEE Transactions on Software Engineering, vol. SE-11, no. 9, pp. 922-934, 1985, doi: 10.1109/TSE.1985.232550.

W. Zhang, “Depth-first branch-and-bound versus local search: A case study,” in National Conference on Artificial Intelligence, pp. 930–935, 2000.

T. Calogiuri, G. Ghiani, E. Guerriero, and R. Mansini, “A branchand-bound algorithm for the time-dependent rural postman problem,” Computers & Operations Research, vol. 102, pp. 150–157, 2019, doi: 10.1016/j.cor.2018.07.016.

J. Ahn and H. -J. Kim, “A Branch and Bound Algorithm for Scheduling of Flexible Manufacturing Systems,” in IEEE Transactions on Automation Science and Engineering, 2023, doi: 10.1109/TASE.2023.3296087.

H. Wang, X. Zhao, S. Huang, Q. Li, and Y. Liu, “A branch-andbound based globally optimal solution to 2d multi-robot relative pose estimation problems,” Automatica, vol. 164, p. 111654, 2024, doi: 10.1016/j.automatica.2024.111654.

J. G. Martin et al., “Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms,” Intelligent Service Robotics, vol. 14, pp. 707–727, 2021, doi: 10.1007/s11370- 021-00393-4.

L. Hong, Y. Wang, Y. Du, X. Chen, and Y. Zheng, “UAV searchand-rescue planning using an adaptive memetic algorithm,” Frontiers of Information Technology & Electronic Engineering, vol. 22, no. 11, pp. 1477–1491, 2021, doi: 10.1631/FITEE.2000632.

S. Saha, A. E. Vasegaard, I. Nielsen, A. Hapka, and H. Budzisz, “UAVs path planning under a bi-objective optimization framework for smart cities,” Electronics, vol. 10, no. 10, p. 1193, 2021, doi: 10.3390/electronics10101193.

B. Hermans, R. Leus, and J. Matuschke, “Exact and approximation algorithms for the expanding search problem,” INFORMS Journal on Computing, vol. 34, no. 1, pp. 281–296, 2022, doi: 10.1287/ijoc.2020.1047.




DOI: https://doi.org/10.18196/jrc.v5i5.22298

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Harun Yetkin

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 

Journal of Robotics and Control (JRC)

P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com

Kuliah Teknik Elektro Terbaik