{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T13:41:38Z","timestamp":1762954898981},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633075"},{"type":"electronic","value":"9783540694229"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63307-3_73","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T15:22:48Z","timestamp":1270480968000},"page":"345-353","source":"Crossref","is-referenced-by-count":16,"title":["On a simple depth-first search strategy for exploring unknown graphs"],"prefix":"10.1007","author":[{"given":"Stephen","family":"Kwek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"31_CR1","first-page":"321","volume-title":"Proc. 8th Annu. Conf. on Comput. Learning Theory","author":"B. Awerbuch","year":"1995","unstructured":"B. Awerbuch, M. Betke, R. Rivest, and M. Singh. Piecemeal graph exploration by a mobile robot. In Proc. 8th Annu. Conf. on Comput. Learning Theory, pages 321\u2013328. ACM Press, New York, NY, 1995."},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"S. Albers and M. Henzinger. Exploring unknown environments. In Proc. 29th Annu. ACM Sympos. Theory Comput., pages 416\u2013425, 1997.","DOI":"10.1145\/258533.258630"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"D. Angluin, J. Westbrook, and W. Zhu.Robot navigation with range queries. In Proc. 28th Annu. ACM Sympos. Theory Comput., 1996. 469\u2013478.","DOI":"10.1145\/237814.237995"},{"key":"31_CR4","unstructured":"P. Berman, A. Blum, A. Fiat, H. Karloff, A. Rosen, and M. Saks. Randomized robot navigation algorithms. In Proceedings SODA 96, 1996. to appear."},{"key":"31_CR5","first-page":"2","volume-title":"Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci.","author":"A. Blum","year":"1993","unstructured":"A. Blum and P. Chalasani. An on-line algorithm for improving performance in navigation. In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci., pages 2\u201311. IEEE Computer Society Press, Los Alamitos, CA, 1993."},{"key":"31_CR6","unstructured":"A. Bar-Noy, S. Kutten, B. Scieber, and D. Peleg. Competitive unidirectional learning. Unpublished Manuscript, 1997."},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Raghavan, and B. Schieber. Navigating in unfamiliar geometric terrain. In Proc. 23th Annu. ACM Sympos. Theory Comput., pages 494\u2013504. ACM, 1991.","DOI":"10.1145\/103418.103419"},{"issue":"2\/3","key":"31_CR8","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1023\/A:1022803514157","volume":"18","author":"M. Betke","year":"1995","unstructured":"M. Betke, R. Rivest, and M. Singh. Piecemeal learning of an unknown environment. Machine Learning, 18(2\/3):231\u2013254, 1995.","journal-title":"Machine Learning"},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/SFCS.1994.365703","volume-title":"Proceedings of the 35rd Annual Symposium on Foundations of Computer Science","author":"M. Bender","year":"1994","unstructured":"M. Bender and D. Slonim. The power of team exploration: two robots can learn unlabeled directed graphs. In Proceedings of the 35rd Annual Symposium on Foundations of Computer Science, pages 75\u201385. IEEE Computer Society Press, Los Alamitos, CA, 1994."},{"key":"31_CR10","first-page":"298","volume-title":"Proc. of the 32nd Symposium on the Foundations of Comp. Sci.","author":"X. Deng","year":"1991","unstructured":"X. Deng, T. Kameda, and C. Papadimitriou. How to learn in an unknown environment. In Proc. of the 32nd Symposium on the Foundations of Comp. Sci., pages 298\u2013303. IEEE Computer Society Press, Los Alamitos, CA, 1991."},{"key":"31_CR11","first-page":"355","volume":"I","author":"X. Deng","year":"1990","unstructured":"X. Deng and C. H. Papadimitriou. Exploring an unknown graph. In Proc. 31th Annu. IEEE Sympos. Found. Comput. Sci., volume I, pages 355\u2013361, 1990.","journal-title":"Proc. 31th Annu. IEEE Sympos. Found. Comput. Sci."},{"key":"31_CR12","unstructured":"A. Fiat E. Bar-Eli, P. Berman and P. Yan. On-line navigation in a room. In Proc. 3rd SODA, pages 75\u201384, 1992."},{"issue":"3","key":"31_CR13","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0004-3702(90)90054-4","volume":"42","author":"R. E. Korf","year":"1990","unstructured":"R. E. Korf. Real-time heuristic search. Artificial Intelligence, 42(3):189\u2013211, 1990.","journal-title":"Artificial Intelligence"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"S. Keonig and Y. Smirnov. Graph learning with a nearest neighbor approach. In Proceedings of the 9th Conference on Computaitonal Learning Theory, pages 19\u201328, 1996.","DOI":"10.1145\/238061.238065"},{"key":"31_CR15","unstructured":"S. Kutten. Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks. In 9th International Conference on Computer Communication, Tel Aviv, Israel, pages 446\u2013452, 1988."},{"key":"31_CR16","first-page":"1059","volume":"AC-31","author":"V. Lumelsky","year":"1986","unstructured":"V. Lumelsky and A. Stepanov. Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Trans. on Automatic Control, AC-31:1059\u20131063, 1986.","journal-title":"IEEE Trans. on Automatic Control"},{"key":"31_CR17","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/BF01840369","volume":"2","author":"V. Lumelsky","year":"1987","unstructured":"V. Lumelsky and A. Stepanov. Path planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shapes. Algorithmica, 2:403\u2013430, 1987.","journal-title":"Algorithmica"},{"key":"31_CR18","doi-asserted-by":"crossref","unstructured":"V. Lumelsky and S. Tiwari. An algorithm for maze searching with azimuth input. In IEEE Conference on Robotics and Automation, pages 111\u2013116, 1994.","DOI":"10.1109\/ROBOT.1994.351002"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"J.C. Pemberton and R.E. Korf. Incremental path planning on graphs with cycles. In Proceedings of the AI Planning Systems Conference, pages 179\u2013188, 1992.","DOI":"10.1016\/B978-0-08-049944-4.50026-4"},{"key":"31_CR20","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and C. Yannakakis. Shortest path wothout a map. Theoretical Computer Science, 84:127\u2013150, 1991.","journal-title":"Theoretical Computer Science"},{"key":"31_CR21","unstructured":"Y. Smirnov, S. Keonig, M. Veloso, and R. Simmons. Efficient goal-directed exploration. In Proceedings of the National Conference on AI, 1996. 292\u2013297."},{"key":"31_CR22","unstructured":"Stentz. The focussed d\n* algorithm for real-time replanning. In Proceedings of the International Joint Conf. on AI, pages 1652\u20131659, 1995."},{"key":"31_CR23","unstructured":"C. J. Taylor and D. J. Kriegman. Vision-based motion planning and exploration algorithms for mobile robots. In Proc. of the Workshop on Algorithmic Foundation of Robotics, 1994."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63307-3_73","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,3]],"date-time":"2019-02-03T10:47:16Z","timestamp":1549190836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63307-3_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633075","9783540694229"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-63307-3_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}