{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T07:26:22Z","timestamp":1748071582479,"version":"3.38.0"},"reference-count":54,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"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":[[2000,1]]},"abstract":"<jats:p> Three methods are described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. We formalize the problem, prove that its off-line version is NP-hard, and show a lower bound on the length of any solution. Then a deterministic mark and cover (MAC) algorithm is described for the on-line problem using short-lived navigational markers as a means of navigation and indirect communication. The convergence of the algorithm is proved, and its cover time is shown to be the asymptotically optimal O(A\/a), where A is the total area and a is the area covered by the robot in a single step. The MAC algorithm is tested against an alternative randomized probabilistic covering (PC) method, which does not rely on sensors but is still able to cover an unknown region in an expected time that depends polynomially on the dimensions of the region. Both algorithms enable cooperation of several robots to achieve faster coverage. Finally, we show that the two methods can be combined to yield a third, hybrid algorithm with a better trade-off between performance and robustness. <\/jats:p>","DOI":"10.1177\/02783640022066716","type":"journal-article","created":{"date-parts":[[2003,7,19]],"date-time":"2003-07-19T06:59:46Z","timestamp":1058597986000},"page":"12-31","source":"Crossref","is-referenced-by-count":47,"title":["MAC Versus PC: Determinism and Randomness as Complementary Approaches to                 Robotic Exploration of Continuous Unknown Domains"],"prefix":"10.1177","volume":"19","author":[{"given":"Israel A.","family":"Wagner","sequence":"first","affiliation":[{"name":"IBM Haifa Research Laboratory, Matam, Haifa 31905, Israel"}]},{"given":"Michael","family":"Lindenbaum","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion City, Haifa 32000, Israel"}]},{"given":"Alfred M.","family":"Bruckstein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion City, Haifa 32000, Israel"}]}],"member":"179","published-online":{"date-parts":[[2000,1,1]]},"reference":[{"doi-asserted-by":"publisher","key":"atypb1","DOI":"10.1007\/BF01047002"},{"unstructured":"Aldous, D. J., and Fill, J. A. 1996. Reversible Markov chains and random walks on graphs. A book in preparation, available via the Web at http:\/\/www.stat.Berkeley.EDU\/users\/aldous\/book.html.","key":"atypb2"},{"doi-asserted-by":"crossref","unstructured":"Aleliunas, R., et al. 1979 (Oct. 29\u201331, San Juan, Puerto Rico). Random walks, universal traversal sequences, and the complexity of maze problems . Proc. of the 20th Annual Symp. on Found. of Comp. Science, pp. 218\u2013223 .","key":"atypb3","DOI":"10.1109\/SFCS.1979.34"},{"doi-asserted-by":"publisher","key":"atypb4","DOI":"10.1016\/0166-218X(94)90008-6"},{"doi-asserted-by":"publisher","key":"atypb5","DOI":"10.1006\/inco.1993.1054"},{"doi-asserted-by":"publisher","key":"atypb6","DOI":"10.1016\/0925-7721(95)00003-R"},{"doi-asserted-by":"publisher","key":"atypb7","DOI":"10.1007\/BF00735341"},{"doi-asserted-by":"crossref","unstructured":"Barnes, G., and Feige, U. 1993. (May 16-18, San Diego, CA). Short random walks on graphs . Proc. of the 25th ACM Symp. on Theory of Computing. New York: ACM, pp. 728\u2013737 .","key":"atypb8","DOI":"10.1145\/167088.167275"},{"doi-asserted-by":"publisher","key":"atypb9","DOI":"10.1137\/0218018"},{"unstructured":"Berger, M. 1987. Geometry II. Berlin-Heidelberg: Springer-Verlag .","key":"atypb10"},{"unstructured":"Bessiere, P., Ahuactzin, J. M., Talbi, E. G., and Mazer, E. 1995. The \u201cAriadne\u2019s clew\u201d algorithm: Global planning with local methods. Algorithmic Foundation of Robotics. Wellesley, MA: A. K. Peters , pp. 39\u201347.","key":"atypb11"},{"unstructured":"Bollobas, B. 1990. Graph Theory: An Introductory Course. Berlin-Heidlberg: Springer-Verlag .","key":"atypb12"},{"unstructured":"Borenstein, J., Everett, H. R., and Feng, L. 1996. Navigating Mobile Robots: Systems and Techniques. Wellesley, MA: A. K. Peters .","key":"atypb13"},{"doi-asserted-by":"publisher","key":"atypb14","DOI":"10.1109\/70.544770"},{"doi-asserted-by":"publisher","key":"atypb15","DOI":"10.1016\/0196-6774(87)90019-8"},{"doi-asserted-by":"publisher","key":"atypb16","DOI":"10.1137\/S0097539790190144"},{"doi-asserted-by":"crossref","unstructured":"Chandra, A. K. et al. 1997. The electrical resistance of a graph captures its commute and cover times . Computational Complexity 6: 312\u2013340 .","key":"atypb17","DOI":"10.1007\/BF01270385"},{"doi-asserted-by":"crossref","unstructured":"Chin, W. P., and Ntafos S. 1986 (June 2\u20134, Yorktown Heights, NY). Optimum watchman routes . Proc. of the 2nd Annual Symp. on Computational Geometry, pp. 24\u201333 .","key":"atypb18","DOI":"10.1145\/10515.10518"},{"doi-asserted-by":"publisher","key":"atypb19","DOI":"10.1109\/70.508436"},{"unstructured":"Do-Carmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Englewood Cliffs, NJ: Prentice-Hall .","key":"atypb20"},{"doi-asserted-by":"publisher","key":"atypb21","DOI":"10.1109\/70.105395"},{"doi-asserted-by":"publisher","key":"atypb22","DOI":"10.1109\/5.533954"},{"doi-asserted-by":"publisher","key":"atypb23","DOI":"10.1177\/027836499201100501"},{"unstructured":"Even, S. 1979. Graph Algorithms. Rockville, MD: Computer Science Press .","key":"atypb24"},{"unstructured":"Feller, W. 1968. An Introduction to Probability Theory and Its Applications, third ed., vol. 1. New York: Wiley .","key":"atypb25"},{"doi-asserted-by":"crossref","unstructured":"Gage, D. W. 1993 (Sept. 9\u201310, Boston, MA). Randomized search strategies with imperfect sensors . Proc. of SPIE Mobile Robots VIII, vol. 2058, pp. 270\u2013279 .","key":"atypb26","DOI":"10.1117\/12.167503"},{"doi-asserted-by":"publisher","key":"atypb27","DOI":"10.1007\/BF00710793"},{"unstructured":"Graham, R. L., Knuth, D. E., and Patashnik, O. 1991. Concrete Mathematics. Reading, MA: Addison-Wesley .","key":"atypb28"},{"unstructured":"Hall, P. 1988. Introduction to the Theory of Coverage Processes. New York: Wiley .","key":"atypb29"},{"doi-asserted-by":"crossref","unstructured":"Held, M. 1991. On the Computational Geometry of Pocket Machining, a vol. of Lecture Notes in Computer Science. Berlin-Heidelberg: Springer-Verlag .","key":"atypb30","DOI":"10.1007\/3-540-54103-9"},{"doi-asserted-by":"publisher","key":"atypb31","DOI":"10.1007\/BF00141150"},{"doi-asserted-by":"publisher","key":"atypb32","DOI":"10.1016\/0921-8890(94)00034-Y"},{"doi-asserted-by":"publisher","key":"atypb33","DOI":"10.1137\/0211056"},{"unstructured":"Kaplan, W. 1984. Advanced Calculus, 3rd ed. Reading, MA: Addison-Wesley .","key":"atypb34"},{"doi-asserted-by":"publisher","key":"atypb35","DOI":"10.2307\/2371320"},{"doi-asserted-by":"crossref","unstructured":"Kuipers, B., and Byun, Y. T. 1981. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations . Robot. Autonomous Sys. 8: 47\u201363 .","key":"atypb36","DOI":"10.1016\/0921-8890(91)90014-C"},{"doi-asserted-by":"crossref","unstructured":"LaValle, S. M., and Hutchinson, S. A. 1996. Evaluating motion strategies under nondeterministic or probabilistic uncertainties in sensing and control. Proc. of the 1996 IEEE Intl. Conf. on Robot. and Automat. Washington, DC: IEEE , pp. 3034\u20133039.","key":"atypb37","DOI":"10.1109\/ROBOT.1996.509173"},{"unstructured":"Lovasz, L. 1996. Random walks on graphs: A survey. In Miklos, D., Sos, V. T., and Szony, T. (eds.): Combinatorics, Paul Erd\u00f6s is Eighty, vol. 2. Budapest: Janos Bolyai Mathematical Society , pp. 353\u2013398.","key":"atypb38"},{"doi-asserted-by":"publisher","key":"atypb39","DOI":"10.1007\/BF01840369"},{"doi-asserted-by":"crossref","unstructured":"Matthews, P. 1989. Covering problems for Brownian motion on spheres . Annals Probability 16(1): 189\u2013199 .","key":"atypb40","DOI":"10.1214\/aop\/1176991894"},{"doi-asserted-by":"crossref","unstructured":"Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge: Cambridge University Press .","key":"atypb41","DOI":"10.1017\/CBO9780511814075"},{"doi-asserted-by":"publisher","key":"atypb42","DOI":"10.1016\/0925-7721(92)90014-J"},{"doi-asserted-by":"crossref","unstructured":"Parker, L. E. 1996. On the design of behavior-based multi-robot teams . Adv. Robot. 10(6): 547\u2013578 .","key":"atypb43","DOI":"10.1163\/156855396X00228"},{"doi-asserted-by":"publisher","key":"atypb44","DOI":"10.1109\/100.414920"},{"doi-asserted-by":"crossref","unstructured":"Russell, R. A. 1997. Heat trails as short-lived navigational markers for mobile robots. Proc. of the 1997 IEEE Intl. Conf. on Robot. and Automat. Washington, DC: IEEE , pp. 3534\u20133539.","key":"atypb45","DOI":"10.1109\/ROBOT.1997.606882"},{"doi-asserted-by":"crossref","unstructured":"Sagan, H. 1994. Space-Filling Curves. New York: Springer-Verlag .","key":"atypb46","DOI":"10.1007\/978-1-4612-0871-6"},{"doi-asserted-by":"publisher","key":"atypb47","DOI":"10.1016\/0925-4005(96)80047-5"},{"unstructured":"Traub, J. F., Wasilkowski, G. W., and Wozniakowski, H. 1988. Information-Based Complexity. San Diego, CA: Academic Press .","key":"atypb48"},{"unstructured":"Virgil, 1971. The Aeneid of Virgil, trans. by A. Mandelbaum. New York: Bantam Books .","key":"atypb49"},{"unstructured":"Wagner, I. A. 1997. MAC, PC, and other gadgets\u2014a JAVA online simulator. Available via the World Wide Web at http:\/\/www.cs.technion.ac.il\/wagner\/pub\/mac.html.","key":"atypb50"},{"unstructured":"Wagner, I. A., and Bruckstein, A. M. 1997. Cooperative cleaners: A study in ant robotics. In Paulraj, A., Roychowdhury, V., and Schaper, C. D. (eds.): Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath. The Netherlands: Kluwer Academic .","key":"atypb51"},{"unstructured":"Wagner, I. A., Lindenbaum, M., and Bruckstein, A. M. 1996 (June 10\u201312, Jerusalem). Smell as a computational resource\u2014a lesson we can learn from the ant . Proc. of the 4th Israeli Symp. on the Theory of Comp. and Sys. (Also Technical Report CIS-9610, Center for Intelligent Systems, Technion, Haifa, April 1996.)","key":"atypb52"},{"unstructured":"Wagner, I. A., Lindenbaum, M., and Bruckstein, A. M. 1997 (July 28, Providence, RI). On-line graph searching by a smell-oriented vertex process . Working Notes from the AAAI\u201997 Workshop on On-Line Search, pp. 122\u2013125 .","key":"atypb53"},{"doi-asserted-by":"crossref","unstructured":"Yaguchi, H. 1996. Robot introduction to cleaning work in the East Japan Railway Company . Adv. Robot. 10(4): 403\u2013414 .","key":"atypb54","DOI":"10.1163\/156855396X00066"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066716","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066716","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T17:43:39Z","timestamp":1741023819000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783640022066716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1177\/02783640022066716"],"URL":"https:\/\/doi.org\/10.1177\/02783640022066716","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}