{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T00:41:27Z","timestamp":1768437687141,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T00:00:00Z","timestamp":1488844800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s00446-017-0296-0","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T10:52:51Z","timestamp":1488883971000},"page":"493-504","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Search on a line with faulty robots"],"prefix":"10.1007","volume":"32","author":[{"given":"Jurek","family":"Czyzowicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0941-4010","authenticated-orcid":false,"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lata","family":"Narayanan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaroslav","family":"Opatrny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,7]]},"reference":[{"issue":"1","key":"296_CR1","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/050645221","volume":"36","author":"N Agmon","year":"2006","unstructured":"Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56\u201382 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"296_CR2","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"296_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s00453-001-0067-x","volume":"32","author":"S Albers","year":"2002","unstructured":"Albers, S., Kursawe, K., Schuierer, S.: Exploring unknown environments with obstacles. Algorithmica 32(1), 123\u2013143 (2002)","journal-title":"Algorithmica"},{"key":"296_CR4","volume-title":"The Theory of Search Games and Rendezvous","author":"S Alpern","year":"2002","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous, vol. 55. Kluwer Academic Publishers, Alphen aan den Rijn (2002)"},{"key":"296_CR5","volume-title":"Search theory: a game-theoretic perspective","author":"S Alpern","year":"2014","unstructured":"Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., Subrahmanian, V.S.: Search theory: a game-theoretic perspective. Springer Science & Business Media, Berlin (2014)"},{"issue":"2","key":"296_CR6","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R Baeza Yates","year":"1993","unstructured":"Baeza Yates, R., Culberson, J., Rawlins, G.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"issue":"3","key":"296_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0925-7721(95)00003-R","volume":"5","author":"R Baeza-Yates","year":"1995","unstructured":"Baeza-Yates, R., Schott, R.: Parallel searching in the plane. Comput. Geom. 5(3), 143\u2013154 (1995)","journal-title":"Comput. Geom."},{"issue":"4","key":"296_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02759737","volume":"2","author":"A Beck","year":"1964","unstructured":"Beck, A.: On the linear search problem. Isr. J. Math. 2(4), 221\u2013228 (1964)","journal-title":"Isr. J. Math."},{"issue":"4","key":"296_CR9","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"A Beck","year":"1970","unstructured":"Beck, A., Newman, D.: Yet more on the linear search problem. Isr. J. Math. 8(4), 419\u2013429 (1970)","journal-title":"Isr. J. Math."},{"issue":"3","key":"296_CR10","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R.: An optimal search. SIAM Rev. 5(3), 274\u2013274 (1963)","journal-title":"SIAM Rev."},{"key":"296_CR11","doi-asserted-by":"crossref","unstructured":"Bose, P., De\u00a0Carufel, J.L., Durocher, S.: Revisiting the problem of searching on a line. In: 21st European Symposium on Algorithms (ESA 2013), LNCS, vol. 8125, pp. 205\u2013216. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_18"},{"issue":"34\u201336","key":"296_CR12","doi-asserted-by":"publisher","first-page":"3154","DOI":"10.1016\/j.tcs.2010.05.006","volume":"411","author":"Z Bouzid","year":"2010","unstructured":"Bouzid, Z., Potop-Butucaru, M., Tixeuil, S.: Optimal byzantine-rezilient convergence in uni-dimensional robot network. Theor. Comput. Sci. 411(34\u201336), 3154\u20133168 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"296_CR13","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1109\/TRO.2004.839232","volume":"21","author":"W Burgard","year":"2005","unstructured":"Burgard, W., Moors, M., Stachniss, C., Schneider, F.E.: Coordinated multi-robot exploration. IEEE Tran. Robot. 21(3), 376\u2013386 (2005)","journal-title":"IEEE Tran. Robot."},{"key":"296_CR14","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-642-22450-8_27","volume-title":"Ad-hoc, mobile, and wireless networks, LNCS","author":"A Casteigts","year":"2011","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. In: Frey, H., Li, X., Ruehrup, S. (eds.) Ad-hoc, mobile, and wireless networks, LNCS, vol. 6811, pp. 346\u2013359. Springer, Berlin (2011)"},{"key":"296_CR15","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Gasieniec, L., T., G., Martin, R.: Group search on the line. In: Proceedings of SOFSEM 2015, LNCS 8939, pp. 164\u2013176. Springer (2015)","DOI":"10.1007\/978-3-662-46078-8_14"},{"issue":"1","key":"296_CR16","doi-asserted-by":"publisher","first-page":"1516","DOI":"10.1137\/S0097539704446475","volume":"41","author":"R Cohen","year":"2005","unstructured":"Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 41(1), 1516\u20131528 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"296_CR17","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/060665257","volume":"38","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38(1), 276\u2013302 (2008)","journal-title":"SIAM J. Comput."},{"key":"296_CR18","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Taleb, N.: When patrolmen become corrupted: Monitoring a graph using faulty mobile robots. In: Algorithms and Computation\u2014Proceedings of 26th International Symposium, ISAAC 2015, pp. 343\u2013354 (2015)","DOI":"10.1007\/978-3-662-48971-0_30"},{"key":"296_CR19","first-page":"46","volume":"2006","author":"X D\u00e9fago","year":"2006","unstructured":"D\u00e9fago, X., Gradinariu, M., Messika, S., Parv\u00e9dy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. Proc. DISC 2006, 46\u201360 (2006)","journal-title":"Proc. DISC"},{"issue":"2","key":"296_CR20","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theor. Comput. Sci. 361(2), 342\u2013355 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"296_CR21","doi-asserted-by":"crossref","unstructured":"Deng, X., Kameda, T., Papadimitriou, C.: How to learn an unknown environment. In: Proceedings of 32nd Annual Symposium on FOCS, pp. 298\u2013303. IEEE Computer Society (1991)","DOI":"10.1109\/SFCS.1991.185382"},{"issue":"1","key":"296_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629656","volume":"11","author":"Y Dieudonn\u00e9","year":"2014","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms (TALG) 11(1), 1 (2014)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"296_CR23","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: Proceedings of the 2012 ACM symposium on Principles of distributed computing, pp. 77\u201386. ACM (2012)","DOI":"10.1145\/2332432.2332444"},{"key":"296_CR24","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1016\/j.ipl.2011.07.018","volume":"111","author":"P Flocchini","year":"2011","unstructured":"Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: How many oblivious robots can explore a line. Inf. Process. Lett. 111, 1027\u20131031 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"296_CR25","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1002\/nav.3800080108","volume":"8","author":"B Gluss","year":"1961","unstructured":"Gluss, B.: An alternative solution to the lost at sea problem. Naval Res. Logist. Quart. 8(1), 117\u2013122 (1961)","journal-title":"Naval Res. Logist. Quart."},{"issue":"2","key":"296_CR26","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1137\/S0097539799348670","volume":"31","author":"F Hoffmann","year":"2001","unstructured":"Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM J. Comput. 31(2), 577\u2013600 (2001)","journal-title":"SIAM J. Comput."},{"key":"296_CR27","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-1-4757-2491-2_5","volume-title":"Combinatorial network theory","author":"J Hromkovi\u010d","year":"1996","unstructured":"Hromkovi\u010d, J., Klasing, R., Monien, B., Peine, R.: Dissemination of information in interconnection networks (broadcasting & gossiping). In: Ding-Zhu, D., Hsu, F. (eds.) Combinatorial network theory, pp. 125\u2013212. Springer, Berlin (1996)"},{"issue":"4","key":"296_CR28","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1002\/nav.3800140411","volume":"14","author":"JR Isbell","year":"1967","unstructured":"Isbell, J.R.: Pursuit around a hole. Naval Res. Logist. Quart. 14(4), 569\u2013571 (1967)","journal-title":"Naval Res. Logist. Quart."},{"issue":"1","key":"296_CR29","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1137\/100797916","volume":"41","author":"T Izumi","year":"2012","unstructured":"Izumi, T., Souissi, S., Katayama, Y., Inuzuka, N., D\u00e9fago, X., Wada, K., Yamashita, M.: The gathering problem for two oblivious robots with unreliable compasses. SIAM J. Comput. 41(1), 26\u201346 (2012)","journal-title":"SIAM J. Comput."},{"key":"296_CR30","unstructured":"Kleinberg, J.: On-line search in a simple polygon. In: Proceedings of SODA, pp. 8\u201315. SIAM (1994)"},{"key":"296_CR31","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the forty-second ACM symposium on Theory of computing, pp. 513\u2013522. ACM (2010)","DOI":"10.1145\/1806689.1806760"},{"issue":"3","key":"296_CR32","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. (TOPLAS) 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"key":"296_CR33","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)"},{"key":"296_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"296_CR35","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. In: Proceedings of ICALP, LNCS, vol. 372, pp. 610\u2013620. Springer (1989)","DOI":"10.1007\/BFb0035787"},{"issue":"1","key":"296_CR36","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0925-7721(00)00030-4","volume":"18","author":"S Schuierer","year":"2001","unstructured":"Schuierer, S.: Lower bounds in on-line geometric searching. Comput. Geom. 18(1), 37\u201353 (2001)","journal-title":"Comput. Geom."},{"key":"296_CR37","doi-asserted-by":"crossref","unstructured":"Souissi, S., D\u00e9fago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. Principles of Distributed Systems pp. 333\u2013349 (2006)","DOI":"10.1007\/11945529_24"},{"issue":"5","key":"296_CR38","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1177\/02783640122067435","volume":"20","author":"S Thrun","year":"2001","unstructured":"Thrun, S.: A probabilistic on-line mapping algorithm for teams of mobile robots. Int. J. Robot. Res. 20(5), 335\u2013363 (2001)","journal-title":"Int. J. Robot. Res."},{"key":"296_CR39","doi-asserted-by":"crossref","unstructured":"Yamauchi, B.: Frontier-based exploration using multiple robots. In: Proceedings of 2nd international conference on Autonomous agents, pp. 47\u201353. ACM (1998)","DOI":"10.1145\/280765.280773"},{"issue":"1","key":"296_CR40","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.jss.2010.08.026","volume":"84","author":"Y Yang","year":"2011","unstructured":"Yang, Y., Souissi, S., D\u00e9fago, X., Takizawa, M.: Fault-tolerant flocking for a group of autonomous mobile robots. J. Syst. Softw. 84(1), 29\u201336 (2011)","journal-title":"J. Syst. Softw."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0296-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0296-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0296-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T03:02:05Z","timestamp":1750042925000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0296-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,7]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["296"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0296-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,7]]},"assertion":[{"value":"27 September 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}