{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T17:41:24Z","timestamp":1780594884560,"version":"3.54.1"},"reference-count":31,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>This paper examines the problem of locating a mobile, non-adversarial target in an indoor environment using multiple robotic searchers. One way to formulate this problem is to assume a known environment and choose searcher paths most likely to intersect with the path taken by the target. We refer to this as the multi-robot efficient search path planning (MESPP) problem. Such path planning prob lems are NP-hard, and optimal solutions typically scale exponentially in the number of searchers. We present an approximation al gorithm that utilizes finite-horizon planning and implicit coordination to achieve linear scalability in the number of searchers. We prove that solving the MESPP problem requires maximizing a non-decreasing, submodular objective function, which leads to theoretical bounds on the performance of our approximation algorithm. We extend our analysis by considering the scenario where searchers are given noisy non-line-of-sight ranging measurements to the target. For this scenario, we derive and integrate online Bayesian measurement updating into our framework. We demonstrate the performance of our framework in two large-scale simulated environments, and we further validate our results using data from a novel ultra-wideband ranging sensor. Finally, we provide an analysis that demonstrates the relationship between MESPP and the intuitive average capture time metric. Results show that our proposed linearly scalable approximation algorithm generates searcher paths that are competitive with those generated by exponential algorithms.<\/jats:p>","DOI":"10.1177\/0278364908099853","type":"journal-article","created":{"date-parts":[[2009,1,22]],"date-time":"2009-01-22T09:53:13Z","timestamp":1232617993000},"page":"201-219","source":"Crossref","is-referenced-by-count":137,"title":["Efficient Multi-robot Search for a Moving Target"],"prefix":"10.1177","volume":"28","author":[{"given":"Geoffrey","family":"Hollinger","sequence":"first","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15217, USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjiv","family":"Singh","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15217, USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Djugash","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15217, USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Athanasios","family":"Kehagias","sequence":"additional","affiliation":[{"name":"Division of Mathematics, Department of Mathematics, Physics, and Computer Sciences Aristotle University of Thessaloniki, Thessaloniki GR54124, Greece,"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2009,2,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303005625"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20216"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1115\/1.3657260"},{"key":"atypb4","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence","author":"Ferris, B."},{"key":"atypb5","volume-title":"Proceedings of the 2nd Robotics Science and Systems Conference","author":"Ferris, B."},{"key":"atypb6","volume-title":"Proceedings of the International Conference on Intelligent Robots and Systems","author":"Furukawa, T."},{"key":"atypb7","volume-title":"Proceedings of the 3rd International NRL Workshop on Multi-Robot Systems","author":"Gerkey, B."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906065023"},{"key":"atypb9","volume-title":"Proceedings of the International Conference on Advanced Robotics","author":"Gerkey, B."},{"key":"atypb10","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Guestrin, C."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"atypb12","volume-title":"Proceedings of the 6th International Conference on Field and Service Robotics","author":"Hollinger, G."},{"key":"atypb13","volume-title":"Proceedings of the International Conference on Robotics and Automation","author":"Hollinger, G."},{"key":"atypb14","volume-title":"Proceedings of the International Conference on Robotics and Automation","author":"Hollinger, G."},{"key":"atypb15","volume-title":"Proceedings of the Robotics: Science and Systems Conference","author":"Hollinger, G."},{"issue":"21","key":"atypb16","first-page":"864","volume":"5","author":"Isler, V.","year":"2005","journal-title":"IEEE Transactions on Robotics"},{"key":"atypb17","volume-title":"A market-based framework for tightly-coupled planned coordination in multirobot teams. PhD Thesis","author":"Kalra, N.","year":"2006"},{"key":"atypb18","volume-title":"Proceedings of the 22nd Conference on Artificial Intelligence","author":"Krause, A."},{"key":"atypb19","volume-title":"Proceedings of Neural Information Processing Systems","author":"Krause, A."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2004.17"},{"key":"atypb21","volume-title":"Proceedings of the International Conference on Intelligent Robots and Systems","author":"Lau, H."},{"key":"atypb22","volume-title":"Proceedings of the International Conference on Intelligent Robots and Systems","author":"Lau, H."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42268"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"Parsons, T. (1976). Pursuit-evasion in a graph. Theory and Applications of Graphs, Alavi, Y. and Lick, D. (eds). Berlin, Springer, pp. 426-441.","DOI":"10.1007\/BFb0070400"},{"key":"atypb25","volume-title":"Execution-time communication decisions for coordination of multi-agent teams. PhD Thesis","author":"Roth, M.","year":"2007"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1496"},{"key":"atypb27","volume-title":"Proceedings of the 9th Ibero-American Conference on Artificial Intelligence","author":"Sarmiento, A."},{"key":"atypb28","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Singh, A."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1987.1087080"},{"key":"atypb30","volume-title":"Probabilistic planning for robotic exploration. PhD Thesis","author":"Smith, T.","year":"2007"},{"key":"atypb31","volume-title":"Probabilistic Robotics","author":"Thrun, S.","year":"2005"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364908099853","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364908099853","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:37Z","timestamp":1777457797000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364908099853"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["10.1177\/0278364908099853"],"URL":"https:\/\/doi.org\/10.1177\/0278364908099853","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2]]}}}