DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2023.8

Treasure Hunt with Volatile Pheromones

Authors: Evangelos Bampas, Joffroy Beauquier, Janna Burman, and William Guy--Obé

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

In the treasure hunt problem, a team of mobile agents need to locate a single treasure that is hidden in their environment. We consider the problem in the discrete setting of an oriented infinite rectangular grid, where agents are modeled as synchronous identical deterministic time-limited finite-state automata, originating at a rate of one agent per round from the origin. Agents perish τ rounds after their creation, where τ ≥ 1 is a parameter of the model. An algorithm solves the treasure hunt problem if every grid position at distance τ or less from the origin is visited by at least one agent. Agents may communicate only by leaving indistinguishable traces (pheromone) on the nodes of the grid, which can be sensed by agents in adjacent nodes and thus modify their behavior. The novelty of our approach is that, in contrast to existing literature that uses permanent pheromone markers, we assume that pheromone traces evaporate over μ rounds from the moment they were placed on a node, where μ ≥ 1 is another parameter of the model. We look for uniform algorithms that solve the problem without knowledge of the parameter values, and we investigate the implications of this very weak communication mechanism to the treasure hunt problem. We show that, if pheromone persists for at least two rounds (μ ≥ 2), then there exists a treasure hunt algorithm for all values of agent lifetime. We also develop a more sophisticated algorithm that works for all values of μ, hence also for the fastest possible pheromone evaporation of μ = 1, but only if agent lifetime is at least 16.

Cite as

Evangelos Bampas, Joffroy Beauquier, Janna Burman, and William Guy--Obé. Treasure Hunt with Volatile Pheromones. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bampas_et_al:LIPIcs.DISC.2023.8,
  author =	{Bampas, Evangelos and Beauquier, Joffroy and Burman, Janna and Guy--Ob\'{e}, William},
  title =	{{Treasure Hunt with Volatile Pheromones}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.8},
  URN =		{urn:nbn:de:0030-drops-191343},
  doi =		{10.4230/LIPIcs.DISC.2023.8},
  annote =	{Keywords: Mobile Agents, Exploration, Search, Treasure Hunt, Pheromone, Evaporation}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2006.684

Periodic Metro Scheduling

Authors: Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis

Published in: OASIcs, Volume 5, 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (2006)

Abstract

We introduce the { extsc{Periodic Metro Sched-ul-ing}} ({ extsc{PMS}}) problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive trains that pass from the same point of the network is maximized. This can be particularly useful in cases where trains use the same rail segment quite often, as happens in metropolitan rail networks. We present exact algorithms for ({ extsc{PMS}}) in chain and spider networks, and constant ratio approximation algorithms for ring networks and for a special class of tree networks. Some of our algorithms are based on a reduction to the { extsc{Path Coloring}} problem, while others rely on techniques specially designed for the new problem.

Cite as

Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis. Periodic Metro Scheduling. In 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06). Open Access Series in Informatics (OASIcs), Volume 5, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{bampas_et_al:OASIcs.ATMOS.2006.684,
  author =	{Bampas, Evangelos and Kaouri, Georgia and Lampis, Michael and Pagourtzis, Aris},
  title =	{{Periodic Metro Scheduling}},
  booktitle =	{6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-01-9},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{5},
  editor =	{Jacob, Riko and M\"{u}ller-Hannemann, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2006.684},
  URN =		{urn:nbn:de:0030-drops-6841},
  doi =		{10.4230/OASIcs.ATMOS.2006.684},
  annote =	{Keywords: Train scheduling, path coloring, delay-tolerant scheduling, periodic timetabling}
}

Search Results

Documents authored by Bampas, Evangelos

Treasure Hunt with Volatile Pheromones

Abstract

Cite as

Periodic Metro Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message