Kubishi Research Group

Backlinks

  • Welcome
Home

❯

Publications

❯

The Pony Express Communication Problem

The Pony Express Communication Problem

  • cooperative-robots
  • online-algorithms
Jared Coleman, Evangelos Kranakis, Oscar Morales-Ponce, Danny Krizanc
IWOCA 2021 - 32nd International Workshop on Combinatorial Algorithms
January 1, 2021
10.1007/978-3-030-79987-8_15
PDF

Abstract

We introduce a new problem which we call the Pony Express problem. n robots with differing speeds are situated over some domain. A message is placed at some commonly known point. Robots can acquire the message either by visiting its initial position, or by encountering another robot that has already acquired it. The robots must collaborate to deliver the message to a given destination. The objective is to deliver the message in minimum time. In this paper we study the Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment. The robots have different speeds and can move in both directions. We are interested in both offline centralized and online distributed algorithms. In the online case, we assume the robots have limited knowledge of the initial configuration. In particular, the robots do not know the initial positions and speeds of the other robots nor even their own position and speed. They do, however, know the direction on the line in which to find the message and have the ability to compare speeds when they meet. First, we study the Pony Express problem where the message is initially placed at one endpoint of a segment and must be delivered to the other endpoint. We provide an O(n log n) running time offline algorithm as well as an optimal online algorithm. Then we study the Half-Broadcast problem where the message is at the center and must be delivered to either one of the endpoints of the segment. We provide an O(n² log n) time offline algorithm and an online algorithm that attains a competitive ratio of 3/2 which we show is the best possible. Finally, we study the Broadcast problem where the message is at the center and must be delivered to both endpoints of the segment. We give an offline algorithm with runtime O(n² log n) and prove that the best possible competitive ratio for the online case is 9/5.


Created with Quartz v4.5.2 © 2025

  • GitHub
  • Discord Community