{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T17:20:06Z","timestamp":1780593606988,"version":"3.54.1"},"reference-count":18,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T00:00:00Z","timestamp":1584403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a $\\bf(2,2)$-Grid (resp. a $\\bf(3,3)$-Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the $\\bf(2,2)$-Grid and five for the $\\bf(3,3)$-Grid, respectively.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz166","type":"journal-article","created":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T12:08:38Z","timestamp":1576670918000},"page":"132-154","source":"Crossref","is-referenced-by-count":18,"title":["Terminating Exploration Of A Grid By An Optimal Number Of Asynchronous Oblivious Robots"],"prefix":"10.1093","volume":"64","author":[{"given":"St\u00e9phane","family":"Devismes","sequence":"first","affiliation":[{"name":"VERIMAG UMR 5104, Universit\u00e9 Grenoble Alpes, 700 avenue centrale, F-38401, Saint Martin d\u2019H\u00e8res, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anissa","family":"Lamani","sequence":"additional","affiliation":[{"name":"Ecole Internationale des Sciences du Traitement de l\u2019Information, 4 place Jussieu, 75252 Paris CEDEX 05, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franck","family":"Petit","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, Inria, LIP6, 4 place Jussieu, 75252 Paris CEDEX 05, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pascal","family":"Raymond","sequence":"additional","affiliation":[{"name":"VERIMAG UMR 5104, CNRS, 700 avenue centrale, F-38401, Saint Martin d\u2019H\u00e8res, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e9bastien","family":"Tixeuil","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, CNRS, LIP6, 4 place Jussieu, 75252 Paris CEDEX 05, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,3,17]]},"reference":[{"key":"2021011807350882900_ref1","volume-title":"Distributed Computing by Oblivious Mobile Robots","author":"Flocchini","year":"2000"},{"key":"2021011807350882900_ref2","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.tcs.2013.05.031","article-title":"Optimal probabilistic ring exploration by semi-synchronous oblivious robots","volume":"498","author":"Devismes","year":"2013","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807350882900_ref3","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/s00453-011-9611-5","article-title":"Computing without communicating: ring exploration by asynchronous oblivious robots","volume":"65","author":"Flocchini","year":"2013","journal-title":"Algorithmica"},{"key":"2021011807350882900_ref4","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.ipl.2008.08.011","article-title":"Anonymous graph exploration without collision by mobile robots","volume":"109","author":"Baldoni","year":"2008","journal-title":"Inform. Process. Lett."},{"key":"2021011807350882900_ref5","first-page":"208","article-title":"Network Exploration by Silent and Oblivious Robots","volume-title":"Graph Theoretic Concepts in Computer Science\u201436th Int. Workshop, WG 2010 (Revised Papers)","author":"Chalopin","year":"2010"},{"key":"2021011807350882900_ref6","doi-asserted-by":"crossref","first-page":"1583","DOI":"10.1016\/j.tcs.2010.01.007","article-title":"Remembering without memory: tree exploration by asynchronous oblivious robots","volume":"411","author":"Flocchini","year":"2010","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807350882900_ref7","first-page":"5:1","article-title":"A Foundational Framework for Certified Impossibility Results with Mobile Robots on Graphs","volume-title":"Proc. 19th Int. Conf. Distributed Computing and Networking, ICDCN 2018","author":"Balabonski","year":"2018"},{"key":"2021011807350882900_ref8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-642-13284-1_15","article-title":"Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots","volume-title":"17th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"Lamani","year":"2010"},{"key":"2021011807350882900_ref9","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","article-title":"Distributed anonymous mobile robots: formation of geometric patterns","volume":"28","author":"Suzuki","year":"1999","journal-title":"SIAM J. Comput."},{"key":"2021011807350882900_ref10","first-page":"154","article-title":"Instantaneous Actions vs. Full Asynchronicity: Controlling and Coordinating a Set of Autonomous Mobile Robots","volume-title":"Theoretical Computer Science, 7th Italian Conference (ICTCS 2001)","author":"Prencipe","year":"2001"},{"key":"2021011807350882900_ref11","first-page":"301","article-title":"Ring Exploration with Myopic Luminous Robots","volume-title":"Stabilization, Safety, and Security of Distributed Systems\u201420th Int. Symposium, SSS 2018","author":"Ooshita","year":"2018"},{"key":"2021011807350882900_ref12","doi-asserted-by":"crossref","first-page":"1241","DOI":"10.1007\/s00607-018-0595-8","article-title":"Optimal torus exploration by oblivious robots","volume":"101","author":"Devismes","year":"2019","journal-title":"Computing"},{"key":"2021011807350882900_ref13","first-page":"428","article-title":"On the Solvability of Anonymous Partial Grids Exploration by Mobile Robots","volume-title":"Principles of Distributed Systems, 12th Int. Conf., OPODIS 2008","author":"Baldoni","year":"2008"},{"key":"2021011807350882900_ref14","first-page":"251","article-title":"Asynchronous Exclusive Perpetual Grid Exploration Without Sense of Direction","volume-title":"Principles of Distributed Systems\u201415th Int. Conf., OPODIS 2011","author":"Bonnet","year":"2011"},{"key":"2021011807350882900_ref15","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1016\/j.tcs.2008.04.042","article-title":"Distributed algorithms for partitioning a swarm of autonomous mobile robots","volume":"410","author":"Efrima","year":"2009","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807350882900_ref16","first-page":"667","article-title":"A Unified Approach for Different Tasks on Rings in Robot-Based Computing Systems","volume-title":"IPDPS Workshops","author":"D\u2019Angelo","year":"2013"},{"key":"2021011807350882900_ref17","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1109\/5.97300","article-title":"The synchronous dataflow programming language lustre","volume":"79","author":"Halbwachs","year":"1991","journal-title":"Proc. IEEE"},{"key":"2021011807350882900_ref18","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1002\/9780470611012.ch6","article-title":"Synchronous Program Verification with Lustre\/Lesar","volume-title":"Modeling and Verification of Real-Time Systems","author":"Raymond","year":"2008"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/132\/35886333\/bxz166.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/132\/35886333\/bxz166.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T14:01:38Z","timestamp":1610978498000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/1\/132\/5808802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,17]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,3,17]]},"published-print":{"date-parts":[[2021,1,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz166","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,1]]},"published":{"date-parts":[[2020,3,17]]}}}