{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T15:22:52Z","timestamp":1785511372708,"version":"3.56.0"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,2,6]],"date-time":"2017-02-06T00:00:00Z","timestamp":1486339200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,2,6]],"date-time":"2017-02-06T00:00:00Z","timestamp":1486339200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1254906"],"award-info":[{"award-number":["1254906"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["1361538"],"award-info":[{"award-number":["1361538"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Robot"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10514-017-9616-2","type":"journal-article","created":{"date-parts":[[2017,2,6]],"date-time":"2017-02-06T21:16:00Z","timestamp":1486415760000},"page":"329-351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Near-optimal probabilistic search using spatial Fourier sparse set"],"prefix":"10.1007","volume":"42","author":[{"given":"Kuo-Shih","family":"Tseng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B\u00e9r\u00e9nice","family":"Mettler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,2,6]]},"reference":[{"key":"9616_CR1","unstructured":"Aggarwal, A. (1984). The art gallery theorem: Its variations, applications, and algorithmic aspects,. Ph.D. thesis, Johns Hopkins University."},{"key":"9616_CR2","doi-asserted-by":"crossref","unstructured":"Balcan, M. F., & Harvey, N. J. (2011). Learning submodular functions. In Proceedings of the 43rd annual ACM symposium on theory of computing.","DOI":"10.1145\/1993636.1993741"},{"key":"9616_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., & Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2, 183\u2013202.","journal-title":"SIAM Journal on Imaging Sciences"},{"key":"9616_CR4","first-page":"3741","volume":"5","author":"J Bellingham","year":"2002","unstructured":"Bellingham, J., Richards, A., & How, J. P. (2002). Receding horizon control of autonomous aerial vehicles. American Control Conference, 5, 3741\u20133746.","journal-title":"American Control Conference"},{"key":"9616_CR5","doi-asserted-by":"crossref","unstructured":"Binney, J., & Sukhatme, G. S. (2012). Branch and bound for informative path planning. In IEEE international conference on robotics and automation (pp. 2147\u20132154).","DOI":"10.1109\/ICRA.2012.6224902"},{"issue":"3","key":"9616_CR6","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1109\/70.88137","volume":"7","author":"J Borenstein","year":"1991","unstructured":"Borenstein, J., & Koren, Y. (1991). The vector field histogram-fast obstacle avoidance for mobile robots. IEEE Transactions on Robotics and Automation, 7(3), 278\u2013288.","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"9616_CR7","doi-asserted-by":"crossref","unstructured":"Bourgault, F., Furukawa, T., & Durrant-Whyte, H. F. (2003). Coordinated decentralized search for a lost target in a bayesian world. In IEEE\/RSJ international intelligent robots and systems (pp. 979\u20131000).","DOI":"10.1109\/IROS.2003.1250604"},{"issue":"2","key":"9616_CR8","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Candes","year":"2006","unstructured":"Candes, E., Romberg, J., & Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transaction on Information Theory, 52(2), 489\u2013509.","journal-title":"IEEE Transaction on Information Theory"},{"key":"9616_CR9","doi-asserted-by":"crossref","unstructured":"Charrow, B., Liu, S., Kumar, V., & Michael, N. (2015). Information-theoretic mapping using Cauchy\u2013Schwarz quadratic mutual information. In IEEE international conference on robotics and automation (pp. 4791\u20134798).","DOI":"10.1109\/ICRA.2015.7139865"},{"key":"9616_CR10","doi-asserted-by":"crossref","unstructured":"Chen, W., Rodrigues, M. R. D., & Wassell, I. J. (2011). Distributed compressive sensing reconstruction via common support discovery. In IEEE international conference on communications (pp. 1\u20135).","DOI":"10.1109\/icc.2011.5962798"},{"key":"9616_CR11","doi-asserted-by":"crossref","unstructured":"Chung, T. H., & Carpin, S. (2011). Multiscale search using probabilistic quadtrees. In IEEE international conference on robotics and automation (pp. 2546\u20132553).","DOI":"10.1109\/ICRA.2011.5980262"},{"key":"9616_CR12","doi-asserted-by":"crossref","unstructured":"Cortes, J., Martinez, S., Karatas, T., & Bullo, F. (2004). Coverage control for mobile sensing networks. In IEEE international conference on robotics and automation (pp. 243\u2013255).","DOI":"10.1109\/TRA.2004.824698"},{"issue":"5","key":"9616_CR13","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1287\/opre.32.5.1107","volume":"32","author":"JN Eagle","year":"1984","unstructured":"Eagle, J. N. (1984). The optimal search for a moving target when the search path is constrained. Operations Research, 32(5), 1107\u20131115.","journal-title":"Operations Research"},{"issue":"4","key":"9616_CR14","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U. (1998). A threshold of ln n for approximating set cover. Journal of the ACM, 45(4), 634\u2013652.","journal-title":"Journal of the ACM"},{"issue":"4","key":"9616_CR15","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1177\/0278364906065023","volume":"25","author":"BP Gerkey","year":"2006","unstructured":"Gerkey, B. P., Thrun, S., & Gordon, G. (2006). Visibility-based pursuit-evasion with limited field of view. The International Journal of Robotics Research, 25(4), 299\u2013315.","journal-title":"The International Journal of Robotics Research"},{"key":"9616_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10846-009-9383-1","volume":"57","author":"C Goerzen","year":"2010","unstructured":"Goerzen, C., Kong, Z., & Mettler, B. (2010). A survey of motion planning algorithms from the perspective of autonomous UAV guidance. Journal of Intelligent and Robotic Systems, 57, 65. doi:\n                    10.1007\/s10846-009-9383-1\n                    \n                  .","journal-title":"Journal of Intelligent and Robotic Systems"},{"key":"9616_CR17","doi-asserted-by":"crossref","unstructured":"Hayashi, K., Nagahara, M., & Tanaka, T. (2013). A user\u2019s guide to compressed sensing for communications systems. In IEICE transactions on communications\n                    E96-B(3), 685\u2013712.","DOI":"10.1587\/transcom.E96.B.685"},{"key":"9616_CR18","doi-asserted-by":"crossref","unstructured":"Heng, L., Gotovos, A., Krause, A., & Pollefeys, M. (2015). Efficient visual exploration and coverage with a micro aerial vehicle in unknown environments. In IEEE international conference on robotics and automation (pp. 1071\u20131078).","DOI":"10.1109\/ICRA.2015.7139309"},{"key":"9616_CR19","doi-asserted-by":"crossref","unstructured":"Hollinger, G., Choudhuri, C., Mitra, U., & Sukhatme, G. S. (2013). Squared error distortion metrics for motion planning in robotic sensor networks. In Proceedings of the international workshop wireless networking for unmanned autonomous vehicles (pp. 1426\u20131431).","DOI":"10.1109\/GLOCOMW.2013.6825195"},{"issue":"1","key":"9616_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10514-010-9189-9","volume":"29","author":"G Hollinger","year":"2010","unstructured":"Hollinger, G., Kehagias, A., & Singh, S. (2010). Gsst: Anytime guaranteed search. Autonomous Robots, 29(1), 99\u2013118.","journal-title":"Autonomous Robots"},{"key":"9616_CR21","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2008.IV.027","author":"G Hollinger","year":"2008","unstructured":"Hollinger, G., & Singh, S. (2008). Proofs and experiments in scalable, near-optimal search by multiple robots. Robotics: Science and Systems,. doi:\n                    10.15607\/RSS.2008.IV.027\n                    \n                  .","journal-title":"Robotics: Science and Systems"},{"key":"9616_CR22","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2013.IX.051","author":"G Hollinger","year":"2013","unstructured":"Hollinger, G., & Sukhatme, G. S. (2013). Sampling-based motion planning for robotic information gathering. Robotics: Science and Systems Conference,. doi:\n                    10.15607\/RSS.2013.IX.051\n                    \n                  .","journal-title":"Robotics: Science and Systems Conference"},{"issue":"2","key":"9616_CR23","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1214\/aos\/1176343791","volume":"5","author":"JB Kadane","year":"1977","unstructured":"Kadane, J. B., & Simon, H. A. (1977). Optimal strategies for a class of constrained sequential problems. The Annals of Statistics, 5(2), 237\u2013255.","journal-title":"The Annals of Statistics"},{"issue":"1","key":"9616_CR24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., & Naor, J. (1999). The budgeted maximum coverage problem. Information Processing Letters, 70(1), 39\u201345.","journal-title":"Information Processing Letters"},{"issue":"2","key":"9616_CR25","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/s00454-011-9352-x","volume":"46","author":"J King","year":"2011","unstructured":"King, J., & Kirkpatrick, D. (2011). Improved approximation for guarding simple galleries from the perimeter. Journal Discrete and Computational Geometry, 46(2), 252\u2013269.","journal-title":"Journal Discrete and Computational Geometry"},{"key":"9616_CR26","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1023\/A:1008806422571","volume":"4","author":"K Konolige","year":"1997","unstructured":"Konolige, K. (1997). Improved occupancy grids for map building. Autonomous Robots, 4, 351\u2013367.","journal-title":"Autonomous Robots"},{"issue":"3","key":"9616_CR27","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1016\/j.automatica.2008.09.014","volume":"45","author":"EB Kosmatopoulos","year":"2009","unstructured":"Kosmatopoulos, E. B. (2009). An adaptive optimization scheme with satisfactory transient performance. Automatica, 45(3), 716\u2013723.","journal-title":"Automatica"},{"key":"9616_CR28","unstructured":"Krause, A., & Guestrin, C. (2005). Near-optimal nonmyopic value of information in graphical models. In Twenty-First conference on uncertainty in artificial intelligence (pp. 324\u2013331)."},{"key":"9616_CR29","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A., & Guestrin, C. (2008). Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. The Journal of Machine Learning Research, 9, 235\u2013284.","journal-title":"The Journal of Machine Learning Research"},{"key":"9616_CR30","doi-asserted-by":"crossref","unstructured":"Lau, H., Huang, S., & Dissanayake, G. (2006). Probabilistic search for a moving target in an indoor environment. In IEEE\/RSJ international conference on intelligent robots and systems (pp. 3393\u20133398).","DOI":"10.1109\/IROS.2006.282575"},{"issue":"2","key":"9616_CR31","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/j.ejor.2007.06.043","volume":"190","author":"H Lau","year":"2008","unstructured":"Lau, H., Huang, S., & Dissanayake, G. (2008). Discounted mean bound for the optimal searcher path problem with non-uniform travel times. European Journal of Operational Research, 190(2), 383\u2013397.","journal-title":"European Journal of Operational Research"},{"key":"9616_CR32","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1109\/ROBOT.1999.770022","volume":"1","author":"SM LaValle","year":"1999","unstructured":"LaValle, S. M., & Kuffner, J. J. (1999). Randomized kinodynamic planning. IEEE International Conference on Robotics and Automation, 1, 473\u2013479.","journal-title":"IEEE International Conference on Robotics and Automation"},{"key":"9616_CR33","doi-asserted-by":"crossref","unstructured":"Lloyd, S. P. (1982). Least-squares quantization in pcm. In IEEE transactions on information theory (pp. 129\u2013137).","DOI":"10.1109\/TIT.1982.1056489"},{"key":"9616_CR34","doi-asserted-by":"crossref","unstructured":"Lo, N., Berger, J., Noel, M. (2012). Toward optimizing static target search path planning. In IEEE symposium on computational intelligence for security and defence applications (pp. 1\u20137).","DOI":"10.1109\/CISDA.2012.6291538"},{"key":"9616_CR35","unstructured":"McCue, B. (1990). U-boats in the bay of biscay: An essay in operations analysis. Washington: National Defense University Press."},{"key":"9616_CR36","doi-asserted-by":"crossref","unstructured":"Mettler, B., & Kong, Z. (2008). Receding horizon trajectory optimization with a finite-state value function approximation. In American control conference (pp. 3810\u20133816)","DOI":"10.1109\/ACC.2008.4587087"},{"issue":"7","key":"9616_CR37","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/j.conengprac.2010.02.013","volume":"18","author":"B Mettler","year":"2010","unstructured":"Mettler, B., Tehrani, N. D., & Kong, Z. (2010). Agile autonomous guidance using spatial value functions. Control Engineering Practice, 18(7), 773\u2013788.","journal-title":"Control Engineering Practice"},{"key":"9616_CR38","unstructured":"Montemerlo, M., Thrun, S., Koller, D., Wegbreit, B. (2003). Fastslam 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges. In Proceedings of the sixteenth international joint conference on artificial intelligence (pp. 1151\u20131156)."},{"key":"9616_CR39","unstructured":"Narasimhan, M., & Bilmes, J. (2007). Local search for balanced submodular clusterings. In Proceedings of the 20th international joint conference on artifical intelligence (pp. 981\u2013986)."},{"issue":"1","key":"9616_CR40","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions. I. Mathematical Programming, 14(1), 265\u2013294.","journal-title":"Mathematical Programming"},{"issue":"2","key":"9616_CR41","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"29","author":"J ORourke","year":"1983","unstructured":"ORourke, J., & Supowit, K. (1983). Some NP-hard polygon decomposition problems. IEEE Transactions on Information Theory, 29(2), 181\u2013190.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9616_CR42","unstructured":"Pimenta, L. C. A., Schwager, M., Lindsey, Q., Kumar, V., Rus, D., Mesquita, R. C., et al. (2009). Simultaneous coverage and tracking (scat) of moving targets with robot networks, Algorithmic foundation of robotics VIII (pp. 85\u201399). Berlin: Springer."},{"key":"9616_CR43","doi-asserted-by":"crossref","unstructured":"Renzaglia, A., Doitsidis, L., Martinelli, A., Kosmatopoulos, E. B. (2010). Cognitive-based adaptive control for cooperative multi-robot coverage. In IEEE\/RSJ international intelligent robots and systems (pp. 3314\u20133320).","DOI":"10.1109\/IROS.2010.5649249"},{"key":"9616_CR44","doi-asserted-by":"crossref","unstructured":"Renzaglia, A., Doitsidis, L., Martinelli, A., Kosmatopoulos, E. B. (2011). Adaptive-based distributed cooperative multi-robot coverage. In American control conference (pp. 468\u2013473).","DOI":"10.1109\/ACC.2011.5990822"},{"issue":"6","key":"9616_CR45","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1177\/0278364912439332","volume":"31","author":"A Renzaglia","year":"2012","unstructured":"Renzaglia, A., Doitsidis, L., Martinelli, A., & Kosmatopoulos, E. B. (2012). Multi-robot three dimensional coverage of unknown areas. The International Journal of Robotics Research, 31(6), 738\u2013752.","journal-title":"The International Journal of Robotics Research"},{"key":"9616_CR46","doi-asserted-by":"crossref","unstructured":"Richards, A., Boyle, P. (2010). Combining planning and learning for autonomous vehicle navigation. In AIAA guidance, navigation and control conference.","DOI":"10.2514\/6.2010-7866"},{"key":"9616_CR47","doi-asserted-by":"crossref","unstructured":"Schwager, M., Julian, B. J., & Rus, D. (2009). Optimal coverage for multiple hovering robots with downward facing cameras. In IEEE international conference on robotics and automation (pp. 3515\u20133522).","DOI":"10.1109\/ROBOT.2009.5152815"},{"key":"9616_CR48","unstructured":"Singh, A., Krause, A., Guestrin, C., Kaiser, W., & Batalin, M. (2007). Efficient planning of informative paths for multiple robots. In Proceedings of the 20th international joint conference on artificial intelligence (pp. 2204\u20132211)."},{"key":"9616_CR49","unstructured":"Singh, A., Krause, A., & Kaiser, W. (2009). Nonmyopic adaptive informative path planning for multiple robots. In International joint conference on artificial intelligence (pp. 1843\u20131850)."},{"key":"9616_CR50","unstructured":"Stobbe, P., & Krause, A. (2012). Learning Fourier sparse set functions. In Proceedings of the fifteenth international conference on artificial intelligence and statistics (pp. 1125\u20131133)."},{"key":"9616_CR51","unstructured":"Stone, L. D. (1975). The theory of optimal search. Operations Research Society of America."},{"key":"9616_CR52","doi-asserted-by":"crossref","unstructured":"Tokekar, P., & Isler, V. (2014). Polygon guarding with orientation. In IEEE international conference on robotics and automation (pp. 1014\u20131019).","DOI":"10.1109\/ICRA.2014.6906978"},{"issue":"2","key":"9616_CR53","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1287\/opre.34.2.324","volume":"34","author":"KE Trummel","year":"1986","unstructured":"Trummel, K. E., & Weisinger, J. R. (1986). The complexity of the optimal searcher path problem. Operations Research, 34(2), 324\u2013327.","journal-title":"Operations Research"},{"key":"9616_CR54","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-015-9521-5","author":"KS Tseng","year":"2015","unstructured":"Tseng, K. S., & Mettler, B. (2015). Near-optimal probabilistic search via submodularity and sparse regression. Autonomous Robots,. doi:\n                    10.1007\/s10514-015-9521-5\n                    \n                  .","journal-title":"Autonomous Robots"},{"key":"9616_CR55","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10846-007-9150-0","volume":"1","author":"L Vig","year":"2007","unstructured":"Vig, L., & Adams, J. A. (2007). Coalition formation: From software agents to robots. Journal of Intelligent and Robotic Systems, 1, 85\u2013118.","journal-title":"Journal of Intelligent and Robotic Systems"}],"container-title":["Autonomous Robots"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10514-017-9616-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-017-9616-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-017-9616-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T08:46:53Z","timestamp":1589705213000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10514-017-9616-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,6]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9616"],"URL":"https:\/\/doi.org\/10.1007\/s10514-017-9616-2","relation":{},"ISSN":["0929-5593","1573-7527"],"issn-type":[{"value":"0929-5593","type":"print"},{"value":"1573-7527","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,6]]},"assertion":[{"value":"29 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}