Document Open Access Logo

Building a Nest by an Automaton

Authors Jurek Czyzowicz, Dariusz Dereniowski , Andrzej Pelc

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.35.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Jurek Czyzowicz
  • Département d'informatique, Université du Québec en Outaouais, Canada
Dariusz Dereniowski
  • Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Poland
Andrzej Pelc
  • Département d'informatique, Université du Québec en Outaouais, Canada

Funding

  • Czyzowicz, Jurek: Supported in part by NSERC discovery grant.
  • Dereniowski, Dariusz: Partially supported by National Science Centre (Poland) grant number 2015/17/B/ST6/01887.
  • Pelc, Andrzej: Supported in part by NSERC discovery grant 2018-03899 and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.

Cite As Get BibTex

Jurek Czyzowicz, Dariusz Dereniowski, and Andrzej Pelc. Building a Nest by an Automaton. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.35

Abstract

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid Z x Z. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the field, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its span. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest. That is, the robot has to move all bricks in such a way that the span of the resulting field be the smallest. 
Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected field, in time O(sz), where s is the span of the initial field and z is the number of bricks. We show that this complexity is optimal.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • finite automaton
  • plane
  • grid
  • construction task
  • brick
  • mobile agent
  • robot

Metrics

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

Related Versions

References

  1. Susanne Albers and Monika Rauch Henzinger. Exploring Unknown Environments. SIAM J. Comput., 29(4):1164-1188, 2000. URL: https://doi.org/10.1137/S009753979732428X.
  2. Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, and Mona Singh. Piecemeal Graph Exploration by a Mobile Robot. Inf. Comput., 152(2):155-172, 1999. URL: https://doi.org/10.1006/inco.1999.2795.
  3. Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, and Salil P. Vadhan. The Power of a Pebble: Exploring and Mapping Directed Graphs. Inf. Comput., 176(1):1-21, 2002. URL: https://doi.org/10.1006/inco.2001.3081.
  4. Michael A. Bender and Donna K. Slonim. The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs. In 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 75-85, 1994. URL: https://doi.org/10.1109/SFCS.1994.365703.
  5. Margrit Betke, Ronald L. Rivest, and Mona Singh. Piecemeal Learning of an Unknown Environment. Machine Learning, 18(2-3):231-254, 1995. URL: https://doi.org/10.1007/BF00993411.
  6. Manuel Blum and Dexter Kozen. On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs). In 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 132-142, 1978. URL: https://doi.org/10.1109/SFCS.1978.30.
  7. Manuel Blum and William J. Sakoda. On the Capability of Finite Automata in 2 and 3 Dimensional Space. In 18th Annual Symposium on Foundations of Computer Science (FOCS), pages 147-161, 1977. URL: https://doi.org/10.1109/SFCS.1977.20.
  8. 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), pages 13:1-13:17, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.13.
  9. Lothar Budach. Automata and labyrinths. Math. Nachrichten, 86:195-282, 1978. Google Scholar
  10. Jérémie Chalopin, Shantanu Das, and Adrian Kosowski. Constructing a Map of an Anonymous Graph: Applications of Universal Sequences. In 14th International Conference on Principles of Distributed Systems (OPODIS), pages 119-134, 2010. URL: https://doi.org/10.1007/978-3-642-17653-1_10.
  11. Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. Exploring an Infinite Space with Finite Memory Scouts. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 207-224, 2017. URL: https://doi.org/10.1137/1.9781611974782.14.
  12. Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita. On the computational power of oblivious robots: forming a series of geometric patterns. In 29th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 267-276, 2010. URL: https://doi.org/10.1145/1835698.1835761.
  13. Xiaotie Deng and Christos H. Papadimitriou. Exploring an unknown graph. Journal of Graph Theory, 32(3):265-297, 1999. URL: https://doi.org/10.1002/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8.
  14. Yoann Dieudonné, Franck Petit, and Vincent Villain. Leader Election Problem versus Pattern Formation Problem. In 24th International Symposium on Distributed Computing (DISC), pages 267-281, 2010. URL: https://doi.org/10.1007/978-3-642-15763-9_26.
  15. Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, and Andrzej Pelc. Tree exploration with little memory. J. Algorithms, 51(1):38-63, 2004. URL: https://doi.org/10.1016/j.jalgor.2003.10.002.
  16. Gregory Dudek, Michael Jenkin, Evangelos E. Milios, and David Wilkes. Robotic exploration as graph construction. IEEE Trans. Robotics and Automation, 7(6):859-865, 1991. URL: https://doi.org/10.1109/70.105395.
  17. Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar. Optimal constrained graph exploration. ACM Trans. Algorithms, 2(3):380-402, 2006. URL: https://doi.org/10.1145/1159892.1159897.
  18. 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: https://doi.org/10.1016/j.tcs.2015.05.054.
  19. Pierre Fraigniaud and David Ilcinkas. Digraphs Exploration with Little Memory. In 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 246-257, 2004. URL: https://doi.org/10.1007/978-3-540-24749-4_22.
  20. Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, and David Peleg. Graph exploration by a finite automaton. Theor. Comput. Sci., 345(2-3):331-344, 2005. URL: https://doi.org/10.1016/j.tcs.2005.07.014.
  21. A. Hemmerling. Labyrinth Problems: Labyrinth-Searching Abilities of Automata. Teubner-Texte zur Mathematik. B. G. Teubner Verlagsgesellschaft, Leipzig, 114, 1989. Google Scholar
  22. Frank Hoffmann. One Pebble Does Not Suffice to Search Plane Labyrinths. In Fundamentals of Computation Theory (FCT), pages 433-444, 1981. URL: https://doi.org/10.1007/3-540-10854-8_47.
  23. Dexter Kozen. Automata and planar graphs. In Fundamentals of Computation Theory (FCT), pages 243-254, 1979. Google Scholar
  24. Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In 19th International Conference on Principles of Distributed Systems (OPODIS), pages 9:1-9:17, 2015. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2015.9.
  25. Petrisor Panaite and Andrzej Pelc. Exploring Unknown Undirected Graphs. J. Algorithms, 33(2):281-295, 1999. URL: https://doi.org/10.1006/jagm.1999.1043.
  26. N. Rao, S. Kareti, W. Shi, and S. Iyengar. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Technical Report ORNL/TM-12410, Oak Ridge National Lab., 1993. Google Scholar
  27. Hans-Anton Rollik. Automaten in planaren Graphen. Acta Informatica, 13:287-298, 1980. URL: https://doi.org/10.1007/BF00288647.
  28. Ichiro Suzuki and Masafumi Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM J. Comput., 28(4):1347-1363, 1999. URL: https://doi.org/10.1137/S009753979628292X.
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 About DROPS Imprint Privacy Contact