DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2017.11

Evacuating an Equilateral Triangle in the Face-to-Face Model

Authors: Huda Chuangpishit, Saeed Mehrabi, Lata Narayanan, and Jaroslav Opatrny

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract

Consider k robots initially located at the centroid of an equilateral triangle T of sides of length one. The goal of the robots is to evacuate T through an exit at an unknown location on the boundary of T. Each robot can move anywhere in T independently of other robots with maximum speed one. The objective is to minimize the evacuation time, which is defined as the time required for all k robots to reach the exit. We consider the face-to-face communication model for the robots: a robot can communicate with another robot only when they meet in T. In this paper, we give upper and lower bounds for the face-to-face evacuation time by k robots. We show that for any k, any algorithm for evacuating k >= 1 robots from T requires at least sqrt(3) time. This bound is asymptotically optimal, as we show that a straightforward strategy of evacuation by k robots gives an upper bound of sqrt(3) + 3/k. For k = 3, 4, 5, 6, we show significant improvements on the obvious upper bound by giving algorithms with evacuation times of 2.0887, 1.9816, 1.876, and 1.827, respectively. For k = 2 robots, we give a lower bound of 1 + 2/sqrt(3) ~= 2.154, and an algorithm with upper bound of 2.3367 on the evacuation time.

Cite as

Huda Chuangpishit, Saeed Mehrabi, Lata Narayanan, and Jaroslav Opatrny. Evacuating an Equilateral Triangle in the Face-to-Face Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chuangpishit_et_al:LIPIcs.OPODIS.2017.11,
  author =	{Chuangpishit, Huda and Mehrabi, Saeed and Narayanan, Lata and Opatrny, Jaroslav},
  title =	{{Evacuating an Equilateral Triangle in the Face-to-Face Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.11},
  URN =		{urn:nbn:de:0030-drops-86310},
  doi =		{10.4230/LIPIcs.OPODIS.2017.11},
  annote =	{Keywords: Distributed algorithms, Robots evacuation, Face-to-face communication, Equilateral triangle}
}

Search Results

Documents authored by Chuangpishit, Huda

Evacuating an Equilateral Triangle in the Face-to-Face Model

Abstract

Cite as

Thanks for your feedback!

Could not send message