{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:56:36Z","timestamp":1777715796693,"version":"3.51.4"},"reference-count":28,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"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":[[2008,7]]},"abstract":"<jats:p>We propose a new `Mark-Ant-Walk' algorithm for robust and efficient covering of continuous domains by ant-like robots with very limited capabilities. The robots can mark places visited with pheromone marks and sense the level of the pheromone in their local neighborhood. In the case of multiple robots, these pheromone marks can be sensed by all robots and provide the only way of (indirect) communication between the robots. The robots are assumed to be memoryless, and to have no information besides that mentioned above. Despite the robots' simplicity we show that they are able, by running a very simple rule of behavior, to ensure efficient covering of arbitrary connected domains, including non-planar and multidimensional domains. The novelty of our algorithm lies in the fact that, unlike previously proposed methods, our algorithm works on continuous domains without relying on some induced underlying graph effectively reducing the problem to a discrete case of graph covering. In addition, we demonstrate various benefits of our algorithm such as ability to cope with arbitrary initial pheromone profile and a bounded constant time between two successive visits of the robot at the same location, making it suitable for patrolling. Finally, we provide a new theoretical bound on covering time of a wide family of such mark and walk algorithms.<\/jats:p>","DOI":"10.1177\/0278364908092465","type":"journal-article","created":{"date-parts":[[2008,6,24]],"date-time":"2008-06-24T11:15:04Z","timestamp":1214306104000},"page":"815-831","source":"Crossref","is-referenced-by-count":8,"title":["Robust and Efficient Covering of Unknown Continuous Domains with Simple, Ant-Like A(ge)nts"],"prefix":"10.1177","volume":"27","author":[{"given":"Eliyahu","family":"Osherovich","sequence":"first","affiliation":[{"name":"The Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Yanovki","sequence":"additional","affiliation":[{"name":"The Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Israel A.","family":"Wagner","sequence":"additional","affiliation":[{"name":"IBM Haifa Research Lab, Haifa, 31905, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alfred M.","family":"Bruckstein","sequence":"additional","affiliation":[{"name":"The Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649030227002"},{"key":"atypb2","volume-title":"STOC '98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing","author":"Bender, M.A."},{"key":"atypb3","volume-title":"Proceedings of the 19th Annual Symposium on Foundations in Computer Science","author":"Blum, M."},{"key":"atypb4","volume-title":"Proceedings of Annual Symposium on Foundations in Computer Science","author":"Blum, M."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0300-72"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF03024195"},{"key":"atypb7","volume-title":"Distributed coverage of rectilinear environments. Ph. D. thesis","author":"Butler, Z.J.","year":"2000"},{"key":"atypb8","volume-title":"STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing","author":"Chandra, A.K."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016639210559"},{"key":"atypb10","volume-title":"Proceedings of International Conference on Field and Service Robotics","author":"Choset, H."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906072252"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1162\/106454699568728"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/3477.484436"},{"key":"atypb14","first-page":"270","volume":"2058","author":"Gage, D.W.","year":"1994","journal-title":"Proceedings of International Society of Optical Engineering (SPIE)"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1038\/438302a"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-10306-7"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500106"},{"key":"atypb18","volume-title":"AGENTS '01: Proceedings of the fifth international conference on Autonomous agents","author":"Koenig, S."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016665115585"},{"key":"atypb20","volume-title":"Introduction to Algorithms","author":"Rivest, R.L.","year":"1990"},{"key":"atypb21","volume-title":"Proceedings 1999 IEEE International Conference on Robotics and Automation","author":"Russell, R.A."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1515\/9781400856848"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018957401093"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1177\/02783640022066716"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016666118983"},{"key":"atypb26","volume-title":"Proceedings of the 4th Israel Symposium on Theory of Computing and Systems, ISTCS'96","author":"Wagner, I.A."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016688707365"},{"key":"atypb28","volume-title":"Proceedings of International Conference on Advanced Robotics (ICAR)","author":"Zelinsky, A."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364908092465","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364908092465","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:26Z","timestamp":1777457786000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364908092465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":28,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1177\/0278364908092465"],"URL":"https:\/\/doi.org\/10.1177\/0278364908092465","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]}}}