License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.57
URN: urn:nbn:de:0030-drops-154903
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15490/
Czyzowicz, Jurek ;
Killick, Ryan ;
Kranakis, Evangelos ;
Krizanc, Danny ;
Narayanan, Lata ;
Opatrny, Jaroslav ;
Pankratov, Denis ;
Shende, Sunil
Group Evacuation on a Line by Agents with Different Communication Abilities
Abstract
We consider evacuation of a group of n ≥ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target.
We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2√2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR ∈ [2+√5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR ∈ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.
BibTeX - Entry
@InProceedings{czyzowicz_et_al:LIPIcs.ISAAC.2021.57,
author = {Czyzowicz, Jurek and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Pankratov, Denis and Shende, Sunil},
title = {{Group Evacuation on a Line by Agents with Different Communication Abilities}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {57:1--57:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15490},
URN = {urn:nbn:de:0030-drops-154903},
doi = {10.4230/LIPIcs.ISAAC.2021.57},
annote = {Keywords: Agent, Communication, Evacuation, Mobile, Receiver, Search, Sender}
}
|
Keywords: |
|
Agent, Communication, Evacuation, Mobile, Receiver, Search, Sender |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
