Lamprou, Ioannis 
ORCID: 0000-0001-5337-7336, Martin, Russell ORCID: 0000-0002-7043-503X and Schewe, Sven ORCID: 0000-0002-9093-9518
(2016)
Fast Two-Robot Disk Evacuation with Wireless Communication.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9888 L.
pp. 1-15.
|
PDF
1604.04217v1.pdf - Submitted version Download (657kB) | Preview |
Abstract
In the fast evacuation problem, we study the path planning problem for two robots who want to minimize the worst-case evacuation time on the unit disk. The robots are initially placed at the center of the disk. In order to evacuate, they need to reach an unknown point, the exit, on the boundary of the disk. Once one of the robots finds the exit, it will instantaneously notify the other agent, who will make a beeline to it. The problem has been studied for robots with the same speed~\cite{s1}. We study a more general case where one robot has speed $1$ and the other has speed $s \geq 1$. We provide optimal evacuation strategies in the case that $s \geq c_{2.75} \approx 2.75$ by showing matching upper and lower bounds on the worst-case evacuation time. For $1\leq s < c_{2.75}$, we show (non-matching) upper and lower bounds on the evacuation time with a ratio less than $1.22$. Moreover, we demonstrate that a generalization of the two-robot search strategy from~\cite{s1} is outperformed by our proposed strategies for any $s \geq c_{1.71} \approx 1.71$.
| Item Type: | Article |
|---|---|
| Additional Information: | 18 pages, 10 figures |
| Uncontrolled Keywords: | cs.DC, cs.DC |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 23 Sep 2022 09:20 |
| Last Modified: | 18 Jan 2023 20:41 |
| DOI: | 10.1007/978-3-662-53426-7_1 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3164967 |
Dimensions
Dimensions
