{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:24:36Z","timestamp":1759335876027,"version":"3.44.0"},"reference-count":66,"publisher":"IEEE","license":[{"start":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T00:00:00Z","timestamp":1747612800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T00:00:00Z","timestamp":1747612800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,5,19]]},"DOI":"10.1109\/icra55743.2025.11128471","type":"proceedings-article","created":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T17:28:56Z","timestamp":1756834136000},"page":"3028-3035","source":"Crossref","is-referenced-by-count":1,"title":["Provable Methods for Searching with an Imperfect Sensor"],"prefix":"10.1109","author":[{"given":"Prahlad Narasimhan","family":"Kasthurirangan","sequence":"first","affiliation":[{"name":"Stony Brook University,New York,USA"}]},{"given":"Linh","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Stony Brook University,New York,USA"}]},{"given":"Michael","family":"Perk","sequence":"additional","affiliation":[{"name":"TU Braunschweig,Lower Saxony,DE"}]},{"given":"Nilanjan","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Stony Brook University,New York,USA"}]},{"given":"Joseph S.B.","family":"Mitchell","sequence":"additional","affiliation":[{"name":"Stony Brook University,New York,USA"}]}],"member":"263","reference":[{"doi-asserted-by":"publisher","key":"ref1","DOI":"10.1007\/978-3-540-30301-5_51"},{"key":"ref2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-29746-6","volume-title":"Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits, ser. EURO Advanced Tutorials on Operational Research. Cham: Springer","author":"Vansteenwegen","year":"2019"},{"key":"ref3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems. Berlin, Heidelberg:Springer","author":"Kellerer","year":"2004"},{"issue":"2","key":"ref4","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","article-title":"Orienteering Problem: A survey of recent variants, solution approaches and applications","volume":"255","author":"Gunawan","year":"2016","journal-title":"European Journal of Operational Research"},{"doi-asserted-by":"publisher","key":"ref5","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"volume-title":"The Traveling Salesman Problem: A Computational Study","year":"2006","author":"Applegate","key":"ref6"},{"doi-asserted-by":"publisher","key":"ref7","DOI":"10.1201\/9781420035315.ch27"},{"year":"2024","author":"Saller","journal-title":"A Systematic Review of Approximability Results for Traveling Salesman Problems leveraging the TSP-T3CO Definition Scheme","key":"ref8"},{"doi-asserted-by":"publisher","key":"ref9","DOI":"10.1287\/opre.4.3.324"},{"issue":"5","key":"ref10","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1287\/opre.4.5.503","article-title":"The Theory of Search. II. Target Detection","volume":"4","author":"Koopman","year":"1956","journal-title":"Operations Research"},{"issue":"5","key":"ref11","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1287\/opre.5.5.613","article-title":"The Theory of Search","volume":"5","author":"Koopman","year":"1957","journal-title":"Operations Research"},{"doi-asserted-by":"publisher","key":"ref12","DOI":"10.1214\/aoms\/1177698965"},{"issue":"1","key":"ref13","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-247X(68)90167-4","article-title":"Discrete search and the Neyman-Pearson Lemma","volume":"22","author":"Kadane","year":"1968","journal-title":"Journal of Mathematical Analysis and Applications"},{"volume-title":"Theory of Optimal Search","year":"1976","author":"Stone","key":"ref14"},{"doi-asserted-by":"publisher","key":"ref15","DOI":"10.1002\/1520-6750(199108)38:4<469::AID-NAV3220380404>3.0.CO;2-E"},{"doi-asserted-by":"publisher","key":"ref16","DOI":"10.15807\/jorsj.59.1"},{"volume-title":"Cartopy: a cartographic python library with a Matplotlib interface, Exeter, Devon","author":"Office","first-page":"2010","key":"ref17"},{"volume-title":"Planet dump","year":"2017","key":"ref18"},{"doi-asserted-by":"publisher","key":"ref19","DOI":"10.1287\/moor.7.3.426"},{"issue":"1","key":"ref20","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0020-0190(85)90108-5","article-title":"Optimal search with positive switch cost is NP-hard","volume":"21","author":"Wegener","year":"1985","journal-title":"Information Processing Letters"},{"issue":"2","key":"ref21","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1287\/opre.34.2.324","article-title":"The Complexity of the Optimal Searcher Path Problem","volume":"34","author":"Trummel","year":"1986","journal-title":"Operations Research"},{"doi-asserted-by":"publisher","key":"ref22","DOI":"10.1109\/ROBOT.2007.364155"},{"doi-asserted-by":"publisher","key":"ref23","DOI":"10.1109\/ROBOT.2008.4543200"},{"issue":"3","key":"ref24","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/s00186-007-0197-2","article-title":"Optimal discrete search with imperfect specificity","volume":"68","author":"Kress","year":"2008","journal-title":"Mathematical Methods of Operations Research"},{"doi-asserted-by":"publisher","key":"ref25","DOI":"10.1109\/TRO.2011.2170333"},{"key":"ref26","first-page":"266","article-title":"Exact Solution for Search-and-Rescue Path Planning","volume-title":"International Journal of Computer and Communication Engineering","author":"Berger","year":"2013"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"e8865381","DOI":"10.1155\/2020\/8865381","article-title":"Bayesian-Based Search Decision Framework and Search Strategy Analysis in Probabilistic Search","volume":"2020","author":"Yu","year":"2020","journal-title":"Scientific Programming"},{"issue":"1","key":"ref28","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10479-019-03141-1","article-title":"Scheduling an autonomous robot searching for hidden targets","volume":"298","author":"Cheng","year":"2021","journal-title":"Annals of Operations Research"},{"issue":"9","key":"ref29","first-page":"1656","article-title":"Optimal Search and Detection of Clustered Hidden Targets under Imperfect Inspections","volume-title":"IFAC Proceedings Volumes","volume":"46","author":"Kriheli","year":"2013"},{"key":"ref30","doi-asserted-by":"crossref","first-page":"117857","DOI":"10.1016\/j.eswa.2022.117857","article-title":"Supervised learning for maritime search operations: An artificial intelligence approach to search efficiency evaluation","volume":"206","author":"Laperri\u00e8re-Robillard","year":"2022","journal-title":"Expert Systems with Applications"},{"doi-asserted-by":"publisher","key":"ref31","DOI":"10.1007\/s001860400360"},{"doi-asserted-by":"publisher","key":"ref32","DOI":"10.1007\/3-540-61440-0_135"},{"key":"ref33","first-page":"1","article-title":"On Sales-men, Repairmen, Spiders, and Other Traveling Agents","volume-title":"Algorithms and Complexity, G. Bongiovanni, R. Petreschi, and G. Gambosi, Eds. Berlin, Heidelberg","author":"Ausiello","year":"2000"},{"key":"ref34","doi-asserted-by":"crossref","first-page":"3740","DOI":"10.1109\/IROS.2005.1544986","article-title":"Optimal search for multiple targets in a built environment","volume-title":"2005 IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Lau","year":"2005"},{"key":"ref35","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.tcs.2018.04.022","article-title":"Approximation and complexity of multi-target graph search and the Canadian traveler problem","volume":"732","author":"van Ee","year":"2018","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"publisher","key":"ref36","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D"},{"doi-asserted-by":"publisher","key":"ref37","DOI":"10.1109\/TASE.2019.2928774"},{"volume-title":"Provable methods for searching with an imperfect sensor supplementary document","author":"Kasthurirangan","key":"ref38"},{"key":"ref39","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among Combinatorial Problems","volume-title":"Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20\u201322, 1972. at the IBM","author":"Karp","year":"1972"},{"volume-title":"The hamptons\u2019 billionaire lane: Where wall street\u2019s richest retreat for the summer","year":"2015","author":"Brennan","key":"ref40"},{"issue":"1","key":"ref41","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.ejor.2022.06.019","article-title":"Ant colony optimization for path planning in search and rescue operations","volume":"305","author":"Morin","year":"2023","journal-title":"European Journal of Operational Research"},{"issue":"5","key":"ref42","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","article-title":"Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems","volume":"45","author":"Arora","year":"1998","journal-title":"Journal of the ACM"},{"issue":"4","key":"ref43","first-page":"1298","article-title":"Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems","volume-title":"SIAM Journal on Computing","volume":"28","author":"Mitchell","year":"1999"},{"doi-asserted-by":"publisher","key":"ref44","DOI":"10.1016\/j.ejor.2016.04.059"},{"doi-asserted-by":"publisher","key":"ref45","DOI":"10.1057\/jors.1984.162"},{"doi-asserted-by":"publisher","key":"ref46","DOI":"10.1016\/0377-2217(95)00035-6"},{"issue":"1","key":"ref47","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s43069-021-00101-z","article-title":"Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem","volume":"3","author":"Christofides","year":"2022","journal-title":"Operations Research Forum"},{"key":"ref48","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/ICAdLT.2014.6864073","article-title":"An information-theoretic-based evolutionary approach for the dynamic search path planning problem","volume-title":"2014 International Conference on Advanced Logistics and Transport (ICALT)","author":"Barkaoui","year":"2014"},{"issue":"8","key":"ref49","doi-asserted-by":"crossref","first-page":"1585","DOI":"10.1007\/s11590-015-0874-7","article-title":"An information theoretic based integer linear programming approach for the discrete search path planning problem","volume":"9","author":"Berger","year":"2015","journal-title":"Optimization Letters"},{"issue":"2","key":"ref50","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s10589-019-00121-w","article-title":"Minimizing the average searching time for an object within a graph","volume":"74","author":"Teller","year":"2019","journal-title":"Computational Optimization and Applications"},{"issue":"3","key":"ref51","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1007\/s10878-019-00413-1","article-title":"An evolutionary approach for the target search problem in uncertain environment","volume":"38","author":"Barkaoui","year":"2019","journal-title":"Journal of Combinatorial Optimization"},{"doi-asserted-by":"publisher","key":"ref52","DOI":"10.1016\/j.robot.2015.08.010"},{"key":"ref53","doi-asserted-by":"crossref","first-page":"3169","DOI":"10.1109\/ROBOT.2005.1570598","article-title":"Multi-vehicle Bayesian Search for Multiple Lost Targets","volume-title":"Proceedings of the 2005 IEEE International Conference on Robotics and Automation","author":"Wong","year":"2005"},{"key":"ref54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/CISDA.2012.6291538","article-title":"Toward optimizing static target search path planning","volume-title":"2012 IEEE Symposium on Computational Intelligence for Security and Defence Applications","author":"Lo","year":"2012"},{"issue":"1","key":"ref55","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1504\/IJOR.2014.060513","article-title":"Discrete search allocation with object uncertainty","volume":"20","author":"Wettergren","year":"2014","journal-title":"International Journal of Operational Research"},{"doi-asserted-by":"publisher","key":"ref56","DOI":"10.1002\/(SICI)1520-6750(199606)43:4<463::AID-NAV1>3.0.CO;2-5"},{"issue":"2","key":"ref57","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/j.ejor.2007.06.043","article-title":"Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times","volume":"190","author":"Lau","year":"2008","journal-title":"European Journal of Operational Research"},{"key":"ref58","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.cor.2019.01.004","article-title":"Moving target search optimization - A literature review","volume":"105","author":"Raap","year":"2019","journal-title":"Computers & Operations Research"},{"issue":"2","key":"ref59","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/j.ejor.2020.11.012","article-title":"Planning a multi-sensors search for a moving target considering traveling costs","volume":"292","author":"Delavernhe","year":"2021","journal-title":"European Journal of Operational Research"},{"key":"ref60","doi-asserted-by":"crossref","first-page":"1202","DOI":"10.23919\/ACC.2004.1386736","article-title":"Aggregation-based approaches to honey-pot searching with local sensory information","volume-title":"Proceedings of the 2004 American Control Conference","volume":"2","author":"Dasgupta","year":"2004"},{"key":"ref61","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1109\/SSRR.2016.7784323","article-title":"Multi-target search strategies","volume-title":"2016 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR)","author":"Meghjani","year":"2016"},{"key":"ref62","first-page":"27:1","article-title":"Optimizing Visibility-Based Search in Polygonal Domains","volume-title":"19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), H. L. Bodlaender, Ed.","volume":"294","author":"Huynh","year":"2024"},{"doi-asserted-by":"publisher","key":"ref63","DOI":"10.1002\/nav.20411"},{"key":"ref64","doi-asserted-by":"crossref","first-page":"5988","DOI":"10.1109\/IROS.2013.6697225","article-title":"A hybrid algorithm for coverage path planning with imperfect sensors","volume-title":"2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Morin","year":"2013"},{"doi-asserted-by":"publisher","key":"ref65","DOI":"10.1109\/ICRA48891.2023.10161017"},{"key":"ref66","article-title":"Probabilistically Informed Robot Object Search with Multiple Regions","author":"Collins","year":"2024","journal-title":"arXiv"}],"event":{"name":"2025 IEEE International Conference on Robotics and Automation (ICRA)","start":{"date-parts":[[2025,5,19]]},"location":"Atlanta, GA, USA","end":{"date-parts":[[2025,5,23]]}},"container-title":["2025 IEEE International Conference on Robotics and Automation (ICRA)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/11127273\/11127223\/11128471.pdf?arnumber=11128471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T06:07:56Z","timestamp":1756879676000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/11128471\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,19]]},"references-count":66,"URL":"https:\/\/doi.org\/10.1109\/icra55743.2025.11128471","relation":{},"subject":[],"published":{"date-parts":[[2025,5,19]]}}}