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.2017.11
URN: urn:nbn:de:0030-drops-86310
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8631/
Chuangpishit, Huda ;
Mehrabi, Saeed ;
Narayanan, Lata ;
Opatrny, Jaroslav
Evacuating an Equilateral Triangle in the Face-to-Face Model
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.
BibTeX - Entry
@InProceedings{chuangpishit_et_al:LIPIcs:2018:8631,
author = {Huda Chuangpishit and Saeed Mehrabi and Lata Narayanan and Jaroslav Opatrny},
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 = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8631},
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}
}
|
Keywords: |
|
Distributed algorithms, Robots evacuation, Face-to-face communication, Equilateral triangle |
|
Collection: |
|
21st International Conference on Principles of Distributed Systems (OPODIS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
28.03.2018 |
