Document Open Access Logo

A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration

Authors Sebastian Brandt, Jara Uitto, Roger Wattenhofer

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.13.pdf
  • Filesize: 487 kB
  • 17 pages

Document Identifiers

Author Details

Sebastian Brandt
  • ETH Zürich, Switzerland
Jara Uitto
  • ETH Zürich, Switzerland
Roger Wattenhofer
  • ETH Zürich, Switzerland

Funding

  • Uitto, Jara: Partially supported by ERC Grant No. 336495 (ACDC).

Cite AsGet BibTex

Sebastian Brandt, Jara Uitto, and Roger Wattenhofer. A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.13

Abstract

Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look-compute-move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent's automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Mobile agents
Keywords
  • Finite automata
  • Graph exploration
  • Mobile robots

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Susanne Albers and Monika Henzinger. Exploring Unknown Environments. SIAM Journal on Computing, 29:1164-1188, 2000. Google Scholar
  2. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff. Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. In FOCS, pages 218-223, 1979. Google Scholar
  3. Igor Averbakh and Oded Berman. A Heuristic with Worst-case Analysis for Minimax Routing of Two Travelling Salesmen on a Tree. Discrete Appl. Math., 68(1-2):17-32, 1996. Google Scholar
  4. Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Searching in the Plane. Information and Computation, 106:234-252, 1993. Google Scholar
  5. M. A. Bender and D. K. Slonim. The Power of Team Exploration: Two Robots can Learn Unlabeled Directed Graphs. In FOCS, pages 75-85, 1994. Google Scholar
  6. M. Blum and W. J. Sakoda. On the capability of finite automata in 2 and 3 dimensional space. In FOCS, pages 147-161, 1977. Google Scholar
  7. Manuel Blum and Dexter Kozen. On the Power of the Compass (or, Why Mazes Are Easier to Search Than Graphs). In FOCS, pages 132-142, 1978. Google Scholar
  8. Sebastian Brandt, Jara Uitto, and Roger Wattenhofer. Tight Bounds for Asynchronous Collaborative Grid Exploration. CoRR, abs/1705.03834, 2017. URL: http://arxiv.org/abs/1705.03834.
  9. Lothar Budach. Automata and Labyrinths. Mathematische Nachrichten, 86(1):195-282, 1978. Google Scholar
  10. Marek Chrobak, Leszek Gasieniec, Thomas Gorry, and Russell Martin. Group Search on the Line, pages 164-176. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46078-8_14.
  11. Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. Exploring an Infinite Space with Finite Memory Scouts. In SODA, pages 207-224, 2017. Google Scholar
  12. Xiaotie Deng and Christos Papadimitriou. Exploring an Unknown Graph. Journal of Graph Theory, 32:265-297, 1999. Google Scholar
  13. Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, and Andrzej Pelc. Tree Exploration with Little Memory. Journal of Algorithms, 51:38-63, 2004. Google Scholar
  14. Yann Disser, Jan Hackfeld, and Max Klimm. Undirected Graph Exploration with Θ(log log n) Pebbles. In SODA, pages 25-39, 2016. Google Scholar
  15. Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar. Optimal Constrained Graph Exploration. ACM Trans. Algorithms, 2(3):380-402, 2006. Google Scholar
  16. Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. How Many Ants Does it Take to Find the Food? Theor. Comput. Sci., 608:255-267, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.05.054.
  17. Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. Solving the ANTS Problem with Asynchronous Finite State Machines. In ICALP, pages 471-482, 2014. Google Scholar
  18. Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sebastien Sereni. Collaborative Search on the Plane Without Communication. In PODC, pages 77-86, 2012. Google Scholar
  19. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Distributed Coordination of a Set of Autonomous Mobile Robots. In Intelligent Vehicles Symposium, pages 480-485, 2000. Google Scholar
  20. Pierre Fraigniaud and David Ilcinkas. Digraphs Exploration with Little Memory, pages 246-257. Springer Berlin Heidelberg, 2004. URL: http://dx.doi.org/10.1007/978-3-540-24749-4_22.
  21. Frank Hoffmann. One Pebble Does Not Suffice to Search Plane Labyrinths. In FCT, pages 433-444, 1981. Google Scholar
  22. Alejandro López-Ortiz and Graeme Sweet. Parallel Searching on a Lattice. In CCCG, pages 125-128, 2001. Google Scholar
  23. Petrişor Panaite and Andrzej Pelc. Exploring Unknown Undirected Graphs. In SODA, pages 316-322, 1998. Google Scholar
  24. H. A. Rollik. Automaten in Planaren Graphen, pages 266-275. Springer Berlin Heidelberg, Berlin, Heidelberg, 1979. URL: http://dx.doi.org/10.1007/3-540-09118-1_28.
  25. Kazuo Sugihara and Ichiro Suzuki. Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots. Journal of Robotic Systems, 13(3):127-139, 1996. Google Scholar
  26. Ichiro Suzuki and Masafumi Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. Google Scholar
  27. Ichiro Suzuki and Masafurni Yarnashita. Distributed Anonymous Mobile Robots - Formation and Agreement Problems. In SIROCCO, pages 1347-1363, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact