{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:59:40Z","timestamp":1777715980600,"version":"3.51.4"},"reference-count":27,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T00:00:00Z","timestamp":1272931200000},"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":[[2010,7]]},"abstract":"<jats:p>We present an anytime algorithm for coordinating multiple autonomous searchers to find a potentially adversarial target on a graphical representation of a physical environment. This problem is closely related to the mathematical problem of searching for an adversary on a graph. Prior methods in the literature treat multi-agent search as either a worst-case problem (i.e. clear an environment of an adversarial evader with potentially infinite speed), or an average-case problem (i.e. minimize average capture time given a model of the target\u2019s motion). Both of these problems have been shown to be NP-hard, and optimal solutions typically scale exponentially in the number of searchers. We propose treating search as a resource allocation problem, which leads to a scalable anytime algorithm for generating schedules that clear the environment of a worst-case adversarial target and have good average-case performance considering a non-adversarial motion model. Our algorithm yields theoretically bounded average-case performance and allows for online and decentralized operation, making it applicable to real-world search tasks. We validate our proposed algorithm through a large number of experiments in simulation and with a team of robot and human searchers in an office building.<\/jats:p>","DOI":"10.1177\/0278364910369949","type":"journal-article","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T21:50:51Z","timestamp":1273009851000},"page":"1088-1105","source":"Crossref","is-referenced-by-count":19,"title":["Improving the Efficiency of Clearing with Multi-agent Teams"],"prefix":"10.1177","volume":"29","author":[{"given":"Geoffrey","family":"Hollinger","sequence":"first","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213,                         USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjiv","family":"Singh","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213,                         USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2010,5,4]]},"reference":[{"key":"atypb1","first-page":"5","volume":"59","author":"Alspach, B.","year":"2006","journal-title":"Matematiche"},{"key":"atypb2","volume-title":"Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures","author":"Barri\u00e8re, L."},{"key":"atypb3","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Borie, R."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20216"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.040"},{"key":"atypb6","volume-title":"Proceedings of the 3rd International NRL Workshop Multi-Robot Systems","author":"Gerkey, B."},{"key":"atypb7","volume-title":"Proceedings of the International Conference on Advanced Robotics","author":"Gerkey, B."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"atypb9","volume-title":"Proceedings of the Robotics: Science and Systems Conference","author":"Hollinger, G."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-010-9189-9"},{"key":"atypb11","volume-title":"Anytime guaranteed search using spanning trees. Technical Report CMU-RI-TR-08-36","author":"Hollinger, G.","year":"2008"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908099853"},{"key":"atypb13","volume-title":"Searching the Nodes of a Graph: Theory and Algorithms. arXiv Repository Technical Report 0905.3359 [cs.DM], May 2009","author":"Kehagias, A.","year":"2009"},{"key":"atypb14","volume-title":"Proceedings of the International Conference on Intelligent Robots and Systems","author":"Kolling, A."},{"key":"atypb15","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Kolling, A."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2035737"},{"key":"atypb17","volume-title":"Proceedings of Neural Information Processing Systems","author":"Krause, A."},{"key":"atypb18","first-page":"2761","volume":"9","author":"Krause, A.","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2004.17"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42268"},{"key":"atypb21","volume-title":"Proceedings of the Robotics: Science and Systems Conference","author":"Ong, S."},{"key":"atypb22","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":"atypb23","volume-title":"Proceedings of the International Conference on Field and Service Robotics","author":"Roy, N."},{"key":"atypb24","volume-title":"Proceedings of the 9th Ibero-American Conference Artificial Intelligence","author":"Sarmiento, A."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00047-5"},{"key":"atypb26","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Singh, A."},{"key":"atypb27","volume-title":"Probabilistic Planning for Robotic Exploration. PhD Thesis","author":"Smith, T.","year":"2007"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364910369949","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364910369949","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:04Z","timestamp":1777457824000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364910369949"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,4]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1177\/0278364910369949"],"URL":"https:\/\/doi.org\/10.1177\/0278364910369949","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,4]]}}}