{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T15:40:45Z","timestamp":1785512445253,"version":"3.56.0"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"2-4","license":[{"start":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T00:00:00Z","timestamp":1207008000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1007\/s10472-009-9120-2","type":"journal-article","created":{"date-parts":[[2009,3,16]],"date-time":"2009-03-16T06:18:16Z","timestamp":1237184296000},"page":"109-142","source":"Crossref","is-referenced-by-count":174,"title":["Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach"],"prefix":"10.1007","volume":"52","author":[{"given":"Ioannis","family":"Rekleitis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ai Peng","family":"New","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edward Samuel","family":"Rankin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Howie","family":"Choset","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,3,17]]},"reference":[{"key":"9120_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1016639210559","volume":"31","author":"H. Choset","year":"2001","unstructured":"Choset, H.: Coverage for robotics\u2014a survey of recent results. Ann. Math. Artif. Intell. 31, 113\u2013126 (2001)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9120_CR2","doi-asserted-by":"crossref","unstructured":"Latimer-IV, D., Srinivasa, S., Lee-Shue, V., Sonne, S.S., Choset, H., Hurst, A.: Toward sensor based coverage with robot teams. In: Proc. 2002 IEEE International Conference on Robotics & Automation (2002)","DOI":"10.1117\/12.457455"},{"key":"9120_CR3","doi-asserted-by":"crossref","unstructured":"Rekleitis, I., Lee-Shue, V., New, A.P., Choset, H.: Limited communication, multi-robot team based coverage. In: IEEE International Conference on Robotics and Automation, pp. 3462\u20133468. New Orleasn, LA (2004)","DOI":"10.1109\/ROBOT.2004.1308789"},{"key":"9120_CR4","doi-asserted-by":"crossref","unstructured":"Dias, M.B., Stentz, A.T.: A market approach to multirobot coordination. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU-RI -TR-01-26 (2001)","DOI":"10.21236\/ADA531275"},{"key":"9120_CR5","doi-asserted-by":"crossref","unstructured":"Choset, H., Pignon, P.: Coverage path planning: the Boustrophedon cellular decomposition. In: International Conference on Field and Service Robotics, Canberra, Australia (1997)","DOI":"10.1007\/978-1-4471-1273-0_32"},{"key":"9120_CR6","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0004-3702(88)90055-0","volume":"37","author":"J. Canny","year":"1988","unstructured":"Canny, J.: Constructing roadmaps of semi-algebraic sets i : completeness. Artif. Intell. 37, 203\u2013222 (1988)","journal-title":"Artif. Intell."},{"key":"9120_CR7","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/BF01891836","volume":"10","author":"J. Canny","year":"1993","unstructured":"Canny, J., Lin, M.: An opportunistic global path planner. Algorithmica 10, 102\u2013120 (1993)","journal-title":"Algorithmica"},{"key":"9120_CR8","doi-asserted-by":"crossref","unstructured":"Acar, E.U., Choset, H.: Critical point sensing in unknown environments. In: Proc. of the IEEE International Conference on Robotics & Automation (2000)","DOI":"10.1109\/ROBOT.2000.845324"},{"key":"9120_CR9","doi-asserted-by":"crossref","unstructured":"Oh, J.S., Park, J.B., Choi, Y.H.: Complete coverage navigation of clean robot based on triangularcell map. In: IEEE International Symposium on Industrial Electronics, vol. 3, pp. 2089\u20132093. Pusan, South Korea (2001)","DOI":"10.1109\/ISIE.2001.932038"},{"key":"9120_CR10","unstructured":"Butler, Z.: CC R: a complete algorithm for contact-sensor based coverage of rectilinear environments. The Robotics Institute, Carnegie Mellon University, Tech. Rep. CMU-RI-TR-98-27 (1998)"},{"key":"9120_CR11","unstructured":"Butler, Z., Rizzi, A., Hollis, R.: Distributed coverage of rectilinear environments. In: Proc. of the Workshop on the Algorithmic Foundations of Robotics (2001)"},{"key":"9120_CR12","doi-asserted-by":"crossref","unstructured":"Kurabayashi, D., Ota, J., Arai, T., Yoshida, E.: An algorithm of dividing a work area to multiple mobile robots. In: 1995 IEEE\/RSJ International Conference on Intelligent Robots and Systems, 5\u20139 Aug 1995, vol. 2, pp. 286\u2013291 (1995)","DOI":"10.1109\/IROS.1995.526174"},{"key":"9120_CR13","doi-asserted-by":"crossref","unstructured":"Kurabayashi, D., Ota, J., Arai, T., Yoshida, E.: Cooperative sweeping by multiple mobile robots. In: 1996 IEEE International Conference on Robotics and Automation, 22\u201328 April 1996, vol. 2, pp. 1744\u20131749 (1996)","DOI":"10.1109\/ROBOT.1996.506964"},{"key":"9120_CR14","doi-asserted-by":"crossref","unstructured":"Min, T.W., Yin, H.K.: A decentralized approach for cooperative sweeping by multiple mobile robots. In: 1998 IEEE\/RSJ International Conference on Intelligent Robots and Systems, 13\u201317 Oct. 1998, vol. 1, pp. 380\u2013385 (1998)","DOI":"10.1109\/IROS.1998.724649"},{"key":"9120_CR15","unstructured":"Luo, C., Yang, S.: A real-time cooperative sweeping strategy for multiple cleaning robots. In: IEEE Internatinal Symposium on Intelligent Control, pp. 660\u2013665 (2002)"},{"key":"9120_CR16","doi-asserted-by":"crossref","unstructured":"Luo, C., Yang, S., Stacey, D.: Real-time path planning with deadlock avoidance of multiple cleaning robots. In: Proceedings 2003 IEEE International Conference on Robotics and Automation (ICRA), 14\u201319 Sept. 2003, vol. 3, pp. 4080\u20134085 (2003)","DOI":"10.1109\/ROBOT.2003.1242224"},{"key":"9120_CR17","doi-asserted-by":"crossref","unstructured":"Ichikawa, S., Hara, F.: Characteristics of object-searching and object-fetching behaviors of multi-robot system using local communication. In: IEEE International Conference on Systems, Man, and Cybernetics, (IEEE SMC \u201999), vol. 4, pp. 775\u2013781 (1999)","DOI":"10.1109\/ICSMC.1999.812502"},{"issue":"5","key":"9120_CR18","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1109\/70.795795","volume":"15","author":"I. Wagner","year":"1999","unstructured":"Wagner, I., Lindenbaum, M., Bruckstein, A.: Distributed covering by ant-robots using evaporating traces. IEEE Trans. Robot. Autom. 15(5), 918\u2013933 (1999)","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"1","key":"9120_CR19","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1177\/02783640022066716","volume":"19","author":"I.A. Wagner","year":"2000","unstructured":"Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Mac vs. pc\u2014determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains. Int. J. Rob. Res. 19(1), 12\u201331 (2000)","journal-title":"Int. J. Rob. Res."},{"issue":"1","key":"9120_CR20","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1177\/0278364907085789","volume":"27","author":"I.A. Wagner","year":"2008","unstructured":"Wagner, I.A., Altshuler, Y., Yanovski, V., Bruckstein, A.M.: Cooperative cleaners: a study in ant robotics. Int. J. Rob. Res. 27(1), 127\u2013151 (2008)","journal-title":"Int. J. Rob. Res."},{"key":"9120_CR21","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1145\/1244002.1244164","volume-title":"Proceedings of the 2007 ACM symposium on Applied computing (SAC07)","author":"R. Menezes","year":"2007","unstructured":"Menezes, R., Martins, F., Vieira, F.E., Silva, R., Braga, M.: A model for terrain coverage inspired by ant\u2019s alarm pheromones. In: Proceedings of the 2007 ACM symposium on Applied computing (SAC07), pp. 728\u2013732. New York, NY, USA: ACM (2007)"},{"issue":"1\u20134","key":"9120_CR22","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1016665115585","volume":"31","author":"S. Koenig","year":"2001","unstructured":"Koenig, S., Szymanski, B.K., Liu, Y.: Efficient and inefficient ant coverage methods. Ann. Math. Artif. Intell. 31(1\u20134), 41\u201376 (2001). [Online]. Available: citeseer.ist.psu.edu\/553035.html","journal-title":"Ann. Math. Artif. Intell."},{"key":"9120_CR23","unstructured":"Ge, S.S., Fua, C.: Complete multi-robot coverage of unknown environments with minimum repeated coverage. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA), 18\u201322 April 2005, pp. 715\u2013720 (2005)"},{"key":"9120_CR24","unstructured":"Bruemmer, D.J., Dudenhoeffer, D.D., Anderson, M.O., McKay, M.D.: A robotic swarm for spill finding and perimeter formation. International Conference on Nuclear and Hazardous Waste Management, Spectrum (2002)"},{"key":"9120_CR25","doi-asserted-by":"crossref","unstructured":"Batalin, M.A., Sukhatme, G.S.: Spreading out: a local approach to multi-robot coverage. In: 6th International Symposium on Distributed Autonomous Robotics Systems, Fukuoka, Japan (2002), June","DOI":"10.1007\/978-4-431-65941-9_37"},{"issue":"3","key":"9120_CR26","first-page":"124","volume":"11","author":"D. Spears","year":"2006","unstructured":"Spears, D., Kerr, W., Spears, W.: Physics-based robot swarms for coverage problems. Int. J. Intell. Control Syst. 11(3), 124\u2013140 (2006)","journal-title":"Int. J. Intell. Control Syst."},{"key":"9120_CR27","doi-asserted-by":"crossref","unstructured":"Hazon, N., Kaminka, G.: Redundancy, efficiency and robustness in multi-robot coverage. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA), 18\u201322 April 2005, pp. 735\u2013741 (2005)","DOI":"10.1109\/ROBOT.2005.1570205"},{"key":"9120_CR28","doi-asserted-by":"crossref","unstructured":"Hazon, N., Mieli, F., Kaminka, G.: Towards robust on-line multi-robot coverage. In: Proceedings 2006 IEEE International Conference on Robotics and Automation (ICRA), 15\u201319 May 2006, pp. 1710\u20131715 (2006)","DOI":"10.1109\/ROBOT.2006.1641953"},{"key":"9120_CR29","doi-asserted-by":"crossref","unstructured":"Agmon, N., Hazon, N., Kaminka, G.: Constructing spanning trees for efficient multi-robot coverage. In: Proceedings 2006 IEEE International Conference on Robotics and Automation (ICRA), 15\u201319 May 2006, pp. 1698\u20131703 (2006)","DOI":"10.1109\/ROBOT.2006.1641951"},{"key":"9120_CR30","doi-asserted-by":"crossref","unstructured":"Solanas, A., Garcia, M.: Coordinated multi-robot exploration through unsupervised clustering of unknown space. In: Proceedings 2004 IEEE\/RSJ International Conference on Intelligent Robots and Systems, vol. 1, 28 Sept\u20132 Oct. 2004, pp. 717\u2013721 (2004)","DOI":"10.1109\/IROS.2004.1389437"},{"key":"9120_CR31","doi-asserted-by":"crossref","unstructured":"Williams, K., Burdick, J.: Multi-robot boundary coverage with plan revision. In: Proceedings 2006 IEEE International Conference on Robotics and Automation (ICRA), 15\u201319 May 2006, pp. 1716\u20131723 (2006)","DOI":"10.1109\/ROBOT.2006.1641954"},{"key":"9120_CR32","doi-asserted-by":"crossref","unstructured":"Zheng, X., Jain, S., Koenig, S., Kempe, D.: Multi-robot forest coverage. In: Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pp. 3852\u20133857. Edmonton Alberta, Canada (2005)","DOI":"10.1109\/IROS.2005.1545323"},{"key":"9120_CR33","doi-asserted-by":"crossref","unstructured":"Dias, M.B., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. Robotics Institute, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, Tech. Rep. CMU-RI-TR-05-13 (2005)","DOI":"10.21236\/ADA526116"},{"key":"9120_CR34","unstructured":"Goldberg, D., Cicirello, V., Dias, M.B., Simmons, R., Smith, S.F., Stenz, A.: Market-based multi-robot planning in a distributed layered architecture. In: Multi-Robot Systems: From Swarms to Intelligent Automata: Proceedings from the 2003 International Workshop on Multi-Robot Systems, vol. 2, pp. 27\u201338. Kluwer Academic, Boston (2003)"},{"key":"9120_CR35","doi-asserted-by":"crossref","unstructured":"Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., Kleywegt, A.: Robot exploration with combinatorial auctions. In: IEEE\/RSJ Int. Conference on Intelligent Robots and Systems, vol. 2, pp. 1957\u20131962 (2003)","DOI":"10.1109\/IROS.2003.1248932"},{"key":"9120_CR36","unstructured":"Dias, M.B., Stentz, A.T.: Traderbots: a market-based approach for resource, role, and task allocation in multirobot coordination. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-03-19 (2003)"},{"key":"9120_CR37","doi-asserted-by":"crossref","unstructured":"Dias, M.B., Zinck, M., Zlot, R., Stentz, A.T.: Robust multirobot coordination in dynamic environments. In: International Conference on Robotics & Automation, pp. 3435\u20133442. New Orleans, LA (2004)","DOI":"10.1109\/ROBOT.2004.1308785"},{"issue":"5","key":"9120_CR38","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1109\/TRA.2002.803462","volume":"18","author":"B. Gerkey","year":"2002","unstructured":"Gerkey, B., Mataric, M.: Sold!: auction methods for multirobot coordination. IEEE Trans. Robot. Autom. 18(5), 758\u2013768 (2002)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"9120_CR39","doi-asserted-by":"crossref","unstructured":"Zlot, R., Stentz, A.: Market-based multirobot coordination for complex tasks. International Journal of Robotics Research Special Issue on the 5th International Conference on Field and Service Robotics, vol. 25, no. 1, (2006)","DOI":"10.1177\/0278364906061160"},{"issue":"4","key":"9120_CR40","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1177\/027836402320556359","volume":"21","author":"E.U. Acar","year":"2002","unstructured":"Acar, E.U., Choset, H., Rizzi, A.A., Atkar, P.N., Hull, D.: Morse decompositions for coverage tasks. Int. J. Rob. Res. 21(4), 331\u2013344 (2002)","journal-title":"Int. J. Rob. Res."},{"issue":"4","key":"9120_CR41","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1177\/027836402320556368","volume":"21","author":"E.U. Acar","year":"2002","unstructured":"Acar, E.U., Choset, H.: Sensor-based coverage of unknown environments: Incremental construction of morse decompositions. Int. J. Rob. Res. 21(4), 345\u2013366 (2002)","journal-title":"Int. J. Rob. Res."},{"key":"9120_CR42","doi-asserted-by":"crossref","unstructured":"Fomenko, A., Kunii, T.L.: Topological Modeling for Visualization. Tokio: Springer, New York (1997)","DOI":"10.1007\/978-4-431-66956-2"},{"issue":"1\u20134","key":"9120_CR43","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1016636024246","volume":"31","author":"I.M. Rekleitis","year":"2001","unstructured":"Rekleitis, I.M., Dudek, G., Milios, E.: Multi-robot collaboration for robust exploration. Ann. Math. Artif. Intell. 31(1\u20134), 7\u201340 (2001)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9120_CR44","doi-asserted-by":"crossref","unstructured":"Dellaert, F., Alegre, F., Martinson, E.B.: Intrinsic localization and mapping with 2 applications: diffusion mapping and marco polo localization. In: Proceedings of the 2003 IEEE International Conference on Robotics & Automation, Taipei, Taiwan, 14\u201319 September 2003, pp. 2344\u20132349 (2003)","DOI":"10.1109\/ROBOT.2003.1241943"},{"key":"9120_CR45","doi-asserted-by":"crossref","unstructured":"Grabowski, R., P.Khosla, Choset, H.: Autonomous exploration via regions of interest. In: IEEE\/RSJ Int. Conference on Intelligent Robots and Systems, vol. 1 (2003)","DOI":"10.1109\/IROS.2003.1248887"},{"key":"9120_CR46","unstructured":"Vaughan, R.T.: Stage: a multiple robot simulator. Institute for Robotics and Intelligent Systems, School of Engineering, University of Southern California, Tech. Rep. IRIS-00-394 (2000)"},{"key":"9120_CR47","volume-title":"Selected Topics in Graph Theory 3","author":"L.W. Beineke","year":"1988","unstructured":"Beineke, L.W., Wilson, R.J.: Selected Topics in Graph Theory 3. Academic, Boston (1988)"},{"issue":"6","key":"9120_CR48","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","volume":"28","author":"J. Hershberger","year":"1999","unstructured":"Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28(6), 2215\u20132256 (1999)","journal-title":"SIAM J. Comput."},{"key":"9120_CR49","doi-asserted-by":"crossref","unstructured":"Gerkey, B.P., Vaughan, R.T., Sty, K., Howard, A., Sukhatme, G.S., Mataric, M.J.: Most valuable player: a robot device server for distributed control. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS 2001), October 29\u2013November 3 2001, pp. 1226\u20131231. Wailea, Hawaii (2001)","DOI":"10.1109\/IROS.2001.977150"},{"key":"9120_CR50","doi-asserted-by":"crossref","unstructured":"Schreckenghost, D., Bonasso, P., Kortenkamp, D., Ryan, D.: Three tier architecture for controlling space life support systems. In: IEEE Int. Joint Symposia on Intelligence and Systems, 21\u201323 May 1998, pp. 195\u2013201 (1998)","DOI":"10.1109\/IJSIS.1998.685444"},{"key":"9120_CR51","doi-asserted-by":"crossref","unstructured":"Wagner, M., Apostolopoulos, D., Shillcutt, K., Shamah, B., Simmons, R., Whittaker, W.: The science autonomy system of the nomad robot. In: IEEE International Conference on Robotics and Automation, vol. 2, pp. 1742\u20131749 (2001)","DOI":"10.1109\/ROBOT.2001.932862"},{"key":"9120_CR52","unstructured":"Rtc, RTC, CMU, Pittsburgh, Pa (2000)"},{"key":"9120_CR53","unstructured":"Raitner, M.: GTL\u2014Graph Template Library Documentation, 1st edn. University of Passau\u2013FMI\u2013Theoretical Computer Science (2002)"},{"key":"9120_CR54","unstructured":"Kong, C.S., New, A.P., Rekleitis, I.: Distributed coverage with multi-robot system. in Proc. of the IEEE International Conference on Robotics and Automation, pp. 2423\u20132429. Orlando, Florida (2006)"},{"key":"9120_CR55","doi-asserted-by":"crossref","unstructured":"Rekleitis, I.M., New, A.P., Choset, H.: Distributed coverage of unknown\/unstructured environments by mobile sensor networks. In: Schultz, A.C., Parker, L.E., Schneider, F. (eds.) 3rd International NRL Workshop on Multi-Robot Systems, 14\u201316 March 2005, pp. 145\u2013155. Kluwer, Washington, D.C. (2005)","DOI":"10.1007\/1-4020-3389-3_12"},{"issue":"1","key":"9120_CR56","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/B:AURO.0000032937.98087.91","volume":"17","author":"S.I. Roumeliotis","year":"2004","unstructured":"Roumeliotis, S.I., Rekleitis, I.M.: Propagation of uncertainty in cooperative multirobot localization: analysis and experimental results. Auton. Robots 17(1), 41\u201354 (2004)","journal-title":"Auton. Robots"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-009-9120-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-009-9120-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-009-9120-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T11:26:40Z","timestamp":1739014000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-009-9120-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4]]},"references-count":56,"journal-issue":{"issue":"2-4","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["9120"],"URL":"https:\/\/doi.org\/10.1007\/s10472-009-9120-2","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4]]}}}