Fast Two-Robot Disk Evacuation with Wireless Communication



Martin, RA ORCID: 0000-0002-7043-503X, Lamprou, I ORCID: 0000-0001-5337-7336 and Schewe, S ORCID: 0000-0002-9093-9518
(2016) Fast Two-Robot Disk Evacuation with Wireless Communication. In: International Symposium on Distributed Computing (DISC), 2016-9-26 - 2016-9-30, Paris, France.

This is the latest version of this item.

[img] Text
tcs-evacuation-revision-1.pdf - Author Accepted Manuscript

Download (591kB) | 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, that is, the time till both of them evacuate. 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, i.e., using wireless communication, notify the other agent who will then follow a straight line to it. The problem has been studied for robots with the same speed [13]. We study a more general case where one robot has speed 1 and the other has speed s≥1. We provide optimal evacuation strategies in the case that s≥2.75 by showing matching upper and lower bounds on the worst-case evacuation time. For 1≤s<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 different-speeds generalization of the two-robot search strategy from [13] is outperformed by our proposed strategies for any s≥1.71.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Evacuation, Different speeds, Disk, Wireless, Fast robots
Depositing User: Symplectic Admin
Date Deposited: 30 Sep 2020 08:31
Last Modified: 18 Jan 2023 23:31
DOI: 10.1016/j.tcs.2020.09.019
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3103019

Available Versions of this Item