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

DOI10.1007/978-3-319-18173-8_10zbMATH Open1459.68212arXiv1501.04985OpenAlexW2187411536MaRDI QIDQ2947016FDOQ2947016

Authors:

Publication date: 21 September 2015

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (30)

• Priority evacuation from a disk: the case of \(n \geq 4\)
• Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)
• Evacuating equilateral triangles and squares in the face-to-face model
• Bike assisted evacuation on a line
• Priority evacuation from a disk: the case of \(n = 1,2,3\)
• Collaboration without communication: evacuating two robots from a disk
• Treasure evacuation with one robot on 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
• Linear search by a pair of distinct-speed robots
• Search-and-fetch with one robot on a disk (track: wireless and geometry)
• Evacuating robots via unknown exit in a disk
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
• 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
• Title not available (Why is that?)
• 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
• Wireless evacuation on \(m\) rays with \(k\) searchers
• Evacuating an equilateral triangle in the face-to-face model
• 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)
• Energy consumption of group search 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)