# Message Delivery in the Plane by Robots with Different Speeds

@inproceedings{Coleman2021MessageDI, title={Message Delivery in the Plane by Robots with Different Speeds}, author={J. Coleman and Evangelos Kranakis and Danny Krizanc and Oscar Morales-Ponce}, booktitle={SSS}, year={2021} }

We study a fundamental cooperative message-delivery problem on the plane. Assume n robots which can move in any direction, are placed arbitrarily on the plane. Robots each have their own maximum speed and can communicate with each other face-to-face (i.e., when they are at the same location at the same time). There are also two designated points on the plane, S (the source) and D (the destination). The robots are required to transmit the message from the source to the destination as quickly as… Expand

#### Figures from this paper

#### References

SHOWING 1-10 OF 27 REFERENCES

The Pony Express Communication Problem

- Computer Science
- IWOCA
- 2021

The Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment is studied and an FPTAS in the offline case and an online algorithm that attains a competitive ratio of 9 5 is given, which is shown is tight. Expand

Optimal rendezvous on a line by location-aware robots in the presence of spies

- Discrete Mathematics, Algorithms and Applications
- 2021

A set of mobile robots is placed at arbitrary points of an infinite line. The robots are equipped with GPS devices and they may communicate their positions on the line to a central authority. The… Expand

Gathering in the Plane of Location-Aware Robots in the Presence of Spies

- Computer Science
- SIROCCO
- 2018

The role of the byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized. Expand

On the fast delivery problem with one or two packages

- Computer Science
- J. Comput. Syst. Sci.
- 2021

For two packages, it is shown that the problem of minimizing the maximum or the sum of the delivery times is NP-hard for arbitrary agent velocities, but polynomial-time solvable for agents with equal velocity. Expand

An Efficient Algorithm for the Fast Delivery Problem

- Computer Science
- FCT
- 2019

This paper proposes an O(kn log n + km) time algorithm, which improves the previous state-of-the-art O(k^2 m + k n^2 + APSP) time algorithms for this problem, where APSP stands for the running-time of an algorithm for the All-Pairs Shortest Paths problem. Expand

Collaborative Exploration of Trees by Energy-Constrained Mobile Robots

- Mathematics, Computer Science
- Theory of Computing Systems
- 2017

An exploration algorithm for visiting all nodes of the unknown tree is provided and this algorithm has a competitive ratio of O(log B), independent of the number of nodes in the tree. Expand

On the robustness of a synchronized multi-robot system

- Computer Science
- J. Comb. Optim.
- 2020

It is proved that the three resilience measures of a synchronized system with respect to coverage and communication on realistic topologies including grid and cycle configurations can be efficiently computed for these configurations. Expand

Collective Fast Delivery by Energy-Efficient Agents

- Computer Science, Mathematics
- MFCS
- 2018

K mobile agents initially located at distinct nodes of an undirected graph that have to deliver a single item from a given source node s to a given target node t are considered, and (i) and (ii) are solvable in polynomial time and (iii) is NP-hard even on planar graphs. Expand

Convergecast and Broadcast by Power-Aware Mobile Agents

- Computer Science
- Algorithmica
- 2014

The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved, and to study this question in the centralized and the distributed settings. Expand

Collaborative Exploration by Energy-Constrained Mobile Robots

- Mathematics, Computer Science
- SIROCCO
- 2015

This work provides an exploration algorithm without any knowledge about the tree and compares it with the optimal offline algorithm that has complete knowledge of the tree, which has a competitive ratio of OlogB, independent of the number of nodes in the tree. Expand