License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2015.9
URN: urn:nbn:de:0030-drops-66005
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6600/
Go to the corresponding LIPIcs Volume Portal

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

Overcoming Obstacles with Ants

pdf-format:
LIPIcs-OPODIS-2015-9.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{langner_et_al:LIPIcs:2016:6600,
  author =	{Tobias Langner and Barbara Keller and Jara Uitto and Roger Wattenhofer},
  title =	{{Overcoming Obstacles with Ants}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6600},
  URN =		{urn:nbn:de:0030-drops-66005},
  doi =		{10.4230/LIPIcs.OPODIS.2015.9},
  annote =	{Keywords: Mobile agents, algorithms, treasure search}
}

Keywords: Mobile agents, algorithms, treasure search
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI