Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)

DOI10.1007/978-3-319-18173-8_10MaRDI QIDQ2947016zbMATH OpenOpenAlexFDO

Authors

Publication date 21 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.04985

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Artificial intelligence for robotics (68T40)

Abstract: Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed $1$. The robots can cooperate by exchanging information whenever they meet. We study algorithms for the two robots to minimize the evacuation time: the time when both robots reach the exit. In [CGGKMP14] the authors gave an algorithm defining trajectories for the two robots yielding evacuation time at most $5.740$ and also proved that any algorithm has evacuation time at least $3+fracpi4+sqrt2approx5.199$. We improve both the upper and lower bound on the evacuation time of a unit disk. Namely, we present a new non-trivial algorithm whose evacuation time is at most $5.628$ and show that any algorithm has evacuation time at least $3+fracpi6+sqrt3approx5.255$. To achieve the upper bound, we designed an algorithm which proposes a forced meeting between the two robots, even if the exit has not been found by either of them. We also show that such a strategy is provably optimal for a related problem of searching for an exit placed at the vertices of a regular hexagon.

Recommendations

• Evacuating robots from a disk using face-to-face communication
• Collaboration without communication: evacuating two robots from a disk
• scientific article; zbMATH DE number 7088261
• Priority evacuation from a disk using mobile robots (extended abstract)
• Evacuating robots via unknown exit in a disk
• Evacuation from a disc in the presence of a faulty robot
• Average case -- worst case tradeoffs for evacuating 2 robots from the disk in the face-to-face model
• Distributed multi-robot evacuation incorporating human behavior

Cites work

• scientific article; zbMATH DE number 4209901 (Why is no real title available?)
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• A Survey of Search Theory
• Asymmetric Rendezvous on the Line Is a Double Linear Search Problem
• Chases and escapes. The mathematics of pursuit and evasion
• Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)
• Evacuating robots via unknown exit in a disk
• Gathering of asynchronous robots with limited visibility
• On the linear search problem
• Searching in the plane
• Solving the ANTS problem with asynchronous finite state machines
• The game of cops and robbers on graphs
• The theory of search games and rendezvous.
• Theory of optimal search
• Trade-offs between selection complexity and performance when searching the plane without communication

Cited in

(31)

• Priority evacuation from a disk: the case of \(n \geq 4\)
• Energy consumption of group search on a line
• Evacuating equilateral triangles and squares in the face-to-face model
• Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)
• Bike assisted evacuation on a line
• Priority evacuation from a disk: the case of \(n = 1,2,3\)
• Treasure evacuation with one robot on a disk
• Collaboration without communication: evacuating two robots from a disk
• God save the queen
• Searching for a Non-adversarial, Uncooperative Agent on a Cycle
• Evacuation from a disc in the presence of a faulty robot
• Evacuating two robots from a disk: a second cut
• Linear search by a pair of distinct-speed robots
• Search-and-fetch with one robot on a disk (track: wireless and geometry)
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
• Evacuating robots via unknown exit in a disk
• Distributed Evacuation in Graphs with Multiple Exits
• Delivery to safety with two cooperating robots
• Optimal circle search despite the presence of faulty robots
• Evacuating robots from a disk using face-to-face communication
• Searching for a non-adversarial, uncooperative agent on a cycle
• scientific article; zbMATH DE number 7088261 (Why is no real title available?)
• Linear Search with Terrain-Dependent Speeds
• Evacuating from \(\ell_p\) unit disks in the wireless model
• Evacuating two robots from multiple unknown exits in a circle
• Average case -- worst case tradeoffs for evacuating 2 robots from the disk in the face-to-face model
• Evacuating an equilateral triangle in the face-to-face model
• Wireless evacuation on \(m\) rays with \(k\) searchers
• Chauffeuring a crashed robot from a disk
• Evacuation of equilateral triangles by mobile agents of limited communication range
• Priority evacuation from a disk using mobile robots (extended abstract)

This page was built for publication: Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947016)