Document Open Access Logo

Overcoming Obstacles with Ants

Authors Tobias Langner, Barbara Keller, Jara Uitto, Roger Wattenhofer

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.9.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Tobias Langner
Barbara Keller
Jara Uitto
Roger Wattenhofer

Cite As Get BibTex

Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.9

Abstract

Consider a group of mobile finite automata, referred to as agents, located in the origin of an infinite grid. The grid is occupied by obstacles, i.e., sets of cells that can not be entered by the agents. In every step, an agent can sense the states of the co-located agents and is allowed to move to any neighboring cell of the grid not blocked by an obstacle. We assume that the circumference of each obstacle is finite but allow the number of obstacles to be unbounded. The task of the agents is to cooperatively find a treasure, hidden in the grid by an adversary. 

In this work, we show how the agents can utilize their simple means of communication and their constant memory to systematically explore the grid and to locate the treasure in finite time. As integral part of the agents' behavior, we present a method that allows a group of six agents to follow a straight line, even if the line is partially obstructed by obstacles, and to discover all free cells along this line. In total, our search protocol requires nine agents.

Subject Classification

Keywords
  • Mobile agents
  • algorithms
  • treasure search

Metrics

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

References

  1. Susanne Albers and Monika Henzinger. Exploring Unknown Environments. SIAM Journal on Computing, 29:1164-1188, 2000. Google Scholar
  2. Baruch Awerbuch and Margrit Betke. Piecemeal Graph Exploration by a Mobile Robot. Information and Computation, 1999. Google Scholar
  3. Michael Bender, Antonio Fernandez, Dana Ron, Amit Sahai, and Salil Vadhan. The Power of a Pebble: Exploring and Mapping Directed Graphs. In Proceedings of the 30th annual ACM Symposium on Theory of Computing (STOC), 1998. Google Scholar
  4. Manuel Blum and Dexter Kozen. On the Power of the Compass (or, Why Mazes Are Easier to Search Than Graphs). In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 132-142, 1978. Google Scholar
  5. Manuel Blum and William J. Sakoda. On the Capability of Finite Automata in 2 and 3 Dimensional Space. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), pages 147-161, 1977. Google Scholar
  6. Lothar Budach. Automata and Labyrinths. Mathematische Nachrichten, pages 195-282, 1978. Google Scholar
  7. Xiaotie Deng and Christos Papadimitriou. Exploring an Unknown Graph. Journal of Graph Theory, 32:265-297, 1999. Google Scholar
  8. Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, and Andrzej Pelc. Tree Exploration with Little Memory. Journal of Algorithms, 51:38-63, 2004. Google Scholar
  9. Klemens Döpp. Automaten in Labyrinthen. Elektronische Informationsverarbeitung und Kybernetik, 7(2):79-94, 1971. Google Scholar
  10. Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar. Optimal Constrained Graph Exploration. ACM Transactions on Algorithms (TALG), 2(3):380-402, 2006. URL: http://dx.doi.org/10.1145/1159892.1159897.
  11. Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. How Many Ants Does it Take to Find the Food? In 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 263-278, 2014. Google Scholar
  12. Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. Solving the ANTS Problem with Asynchronous Finite State Machines. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 471-482, 2014. Google Scholar
  13. Ofer Feinerman and Amos Korman. Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology. In Proceedings of the 26th International Conference on Distributed Computing (DISC), pages 61-75, Berlin, Heidelberg, 2012. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-33651-5_5.
  14. Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sebastien Sereni. Collaborative Search on the Plane Without Communication. In Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pages 77-86, 2012. Google Scholar
  15. Pierre Fraigniaud and David Ilcinkas. Digraphs Exploration with Little Memory. In 21st Symposium on Theoretical Aspects of Computer Science (STACS), pages 246-257, 2004. Google Scholar
  16. Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, and David Peleg. Graph Exploration by a Finite Automaton. Theoretical Computer Science, 345(2-3):331-344, 2005. Google Scholar
  17. Frank Hoffmann. One Pebble Does Not Suffice to Search Plane Labyrinths. In Fundamentals of Computation Theory, pages 433-444. Springer Berlin Heidelberg, 1981. Google Scholar
  18. Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication. In Proceedings of the 33rd Symposium on Principles of Distributed Computing (PODC), pages 252-261, 2014. Google Scholar
  19. Saket Navlakha and Ziv Bar-Joseph. Distributed Information Processing in Biological and Computational Systems. Communications of the ACM, 58(1):94-102, 2014. Google Scholar
  20. Petrişor Panaite and Andrzej Pelc. Exploring Unknown Undirected Graphs. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 316-322, 1998. Google Scholar
  21. Noa Pinter-Wollman, Ashwin Bala, Andrew Merrell, Jovel Queirolo, Martin C Stumpe, Susan Holmes, and Deborah M Gordon. Harvester Ants Use Interactions to Regulate Forager Activation and Availability. Animal behaviour, 86(1):197-207, 2013. 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 About DROPS Imprint Privacy Contact