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

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

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

• 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
• scientific article; zbMATH DE number 4209901 (Why is no real title available?)
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• 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)

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

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)