{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:50Z","timestamp":1759637990502},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540649175"},{"type":"electronic","value":"9783540683117"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0029571","type":"book-chapter","created":{"date-parts":[[2005,12,6]],"date-time":"2005-12-06T14:47:06Z","timestamp":1133880426000},"page":"232-241","source":"Crossref","is-referenced-by-count":25,"title":["On-line searching and navigation"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,11,22]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"S. Albers and M.R. Henzinger, Exploring unknown environments, Proc. 29th STOC, 416\u2013425 (1997).","DOI":"10.1145\/258533.258630"},{"key":"10_CR2","unstructured":"Ariadne and Theseus, Path planning for a hero moving in an unknown labyrinth, Proc. Panhellenic Symp. on Attic Antics and Antiquities (1300 B.C.)."},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"D. Angluin, J. Westbrook and W. Zhu, Robot Navigation with range queries, Proc. 28th STOC, 469\u2013478 (1996).","DOI":"10.1145\/237814.237995"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R. A. Baeza-Yates","year":"1993","unstructured":"R. A. Baeza-Yates, J. C. Coulbertson and G. J. E. Rawlings, Searching in the plane, Information and Computation, 106, 234\u2013252 (1993).","journal-title":"Information and Computation"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1006\/jagm.1994.1039","volume":"17","author":"E. Bar-Eli","year":"1994","unstructured":"E. Bar-Eli, P. Berman, A. Fiat and P. Yan, On-line navigation in a room, Journal of Algorithms 17, 319\u2013341 (1994).","journal-title":"Journal of Algorithms"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"M. A. Bender and D. K. Slonim, The power of team exploration: two robots can learn unlabeled directed graphs, Proc. 35th FOCS, 75\u201385 (1994).","DOI":"10.1109\/SFCS.1994.365703"},{"key":"10_CR7","unstructured":"P. Berman, A. Blum, A. Fiat, H. Karloff, A. Rosen and M. Saks, Randomized robot navigation algorithms, Proc. 7th SODA, 75\u201384 (1996)."},{"key":"10_CR8","unstructured":"P. Berman and M. Karpinski, Randomized Navigation to a Wall through Convex Obstacles, Bonn University Tech. Rep. 85118-CS (1994)."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Blum, C. Burch and A. Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proc. 29th STOC, 711\u2013719 (1997).","DOI":"10.1145\/258533.258667"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"A. Blum and P. Chalasani, An on-line algorithm for improving performance in navigation, Proc. 34th FOCS, 2\u201311 (1993).","DOI":"10.1109\/SFCS.1993.366887"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Raghavan, and B. Schieber, Navigation in unfamiliar terrain, Proc. 23rd STOC, 494\u2013504 (1991).","DOI":"10.1145\/103418.103419"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"A. Datta and C. Icking, Competitive searching in a generalized street, Proc. 10th ACM Symp. on Computational Geometry, 175\u2013182 (1994).","DOI":"10.1145\/177424.177622"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"A. Datta, C. Hipke and S. Schuierer, Competitive searching in polygons-beyond generalized streets, Proc. 6th ISAAC, 32\u201341 (1995).","DOI":"10.1007\/BFb0015406"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"X. Deng, T. Kameda and C. Papadimitriou, How to learn an unknown environment, Proc. 32nd FOCS, 298\u2013303 (1991).","DOI":"10.1109\/SFCS.1991.185382"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"X. Deng, C. H. Papadimitriou, Exploring an unknown graph, Proc. 31st FOCS, 355\u2013361 (1990).","DOI":"10.1109\/FSCS.1990.89554"},{"key":"10_CR16","unstructured":"G. Dudek, K. Romanik and S. Whitesides, Localizing a robot with minimum travel, Proc. 6th SODA, 437\u2013446 (1995)."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"A. Fiat, D. Foster, H. Karloff, Y. Rabani, Y. Ravid and S. Vishwanathan, Competitive algorithms for layered graph traversal, Proc. 32nd FOCS, 288\u2013297 (1991).","DOI":"10.1109\/SFCS.1991.185381"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1137\/S0097539792233257","volume":"26","author":"L. J. Guibas","year":"1997","unstructured":"L. J. Guibas, R. Motwani and P. Raghavan, The robot localization problem in two dimensions, SIAM J. of Computing, 26, 1120\u20131138 (1997).","journal-title":"SIAM J. of Computing"},{"key":"10_CR19","unstructured":"F. Hoffmann, C. Icking, R. Klein and K. Kriegel, A competitive strategy for learning a polygon, Proc. 8th SODA, 166\u2013174 (1997)."},{"key":"10_CR20","unstructured":"F. Hoffmann, C. Icking, R. Klein and K. Kriegel, The polygon exploration problem: a new strategy and a new analysis technique, to appear in Proc. Workshop on the Algorithmic Foundations of Robotics, (1998)"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"C. Icking and R. Klein, Searching for the kernel of a polygon \u2014 a competitive strategy, Proc. 11th ACM Symp. on Computational Geometry, 258\u2013266 (1995).","DOI":"10.1145\/220279.220307"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and K. R. Pruhs, Constructing competitive tours from local information, Proc. 20th ICALP, 102\u2013113 (1993).","DOI":"10.1007\/3-540-56939-1_65"},{"key":"10_CR23","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0925-7721(92)90010-P","volume":"1","author":"R. Klein","year":"1992","unstructured":"R. Klein, Walking an unknown street with bounded detour, Computational Geometry: Theory and Applications, 1, 325\u2013351 (1992).","journal-title":"Computational Geometry: Theory and Applications"},{"key":"10_CR24","unstructured":"J. M. Kleinberg, On-line search in a simple polygon, Proc. 5th SODA, 8\u201315 (1994)."},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg, The localization problem for mobile robots, Proc. 35th FOCS, 521\u2013531 (1994).","DOI":"10.1109\/SFCS.1994.365739"},{"key":"10_CR26","unstructured":"M. Kao, J. H. Reif and S. R. Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow path problem, Proc. 4th SODA, 441\u2013447 (1993)."},{"key":"10_CR27","unstructured":"H. J. Karloff, Y. Rabani and Y. Ravid, Lower bounds for randomized server algorithms, Proc. 23rd STOC, 278\u2013288 (1991)."},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"A. Lopez-Ortiz and S. Schuierer, Generalized streets revisited Proc. 4th ESA, 546\u2013558 (1996).","DOI":"10.1007\/3-540-61680-2_81"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1109\/TAC.1986.1104175","volume":"AC-31","author":"V. J. Lumelsky","year":"1986","unstructured":"V. J. Lumelsky, A. A. Stepanov, Dynamic path planning for a mobile automaton with limited information on the environment, IEEE Transactions on Automatic Control, AC-31, 1058\u20131063, 1986.","journal-title":"IEEE Transactions on Automatic Control"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/BF01840369","volume":"2","author":"V. J. Lumelsky","year":"1987","unstructured":"V. J. Lumelsky and A. A. Stepanov, Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape, Algorithmica, 2, 403\u2013430. (1987).","journal-title":"Algorithmica"},{"key":"10_CR31","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0020-0190(94)90140-6","volume":"52","author":"A. Mei","year":"1994","unstructured":"A. Mei and Y. Igarashi, Efficient strategies for robot navigation in unknown environment, Information Processing Letters, 52, 51\u201356 (1994).","journal-title":"Information Processing Letters"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis, Shortest paths without a map, Theoretical Computer Science, 84, 127\u2013150 (1991).","journal-title":"Theoretical Computer Science"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1006\/jagm.1995.1019","volume":"18","author":"H. Ramesh","year":"1995","unstructured":"H. Ramesh, On traversing layered graphs on-line, Journal of Algorithms, 18, 480\u2013512 (1995).","journal-title":"Journal of Algorithms"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"C. N. Shen and G. Nagy, Autonomous navigation to provide long distance surface traverses for Mars rover sample return mission, Proc. IEEE Symp. on Intelligent Control, 362\u2013367 (1989).","DOI":"10.1109\/ISIC.1989.238673"}],"container-title":["Lecture Notes in Computer Science","Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T11:17:21Z","timestamp":1586603841000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540649175","9783540683117"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/bfb0029571","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}