Symmetric Rendezvous with Advice: How to Rendezvous in a Disk

Konstantinos Georgiou, Jay Griffiths, Yuval Yakubov

Abstract

This paper investigates a geometric variation of the classic Symmetric Rendezvous Problem (SRP) by introducing a common reference point—the center of a disk. In the traditional linear version of the problem, two robots must meet on an infinite line without a shared coordinate system, a task constrained by a conjectured theoretical limit of 4.25 times the half-distance. By providing the robots with "advice" in the form of a disk's center, the authors prove that robots can not only beat this 4.25 barrier but also ensure rendezvous within a finite amount of time and bounded energy, which is impossible in the classic linear model.

Introduction

The Symmetric Rendezvous Problem asks how two autonomous agents, placed at a known distance from each other on an infinite line, can meet as quickly as possible when they lack a common sense of direction. Because the problem is symmetric, both agents must execute the exact same randomized algorithm. For decades, the "psychological threshold" for the expected rendezvous time has been 4.25.

This research introduces the Symmetric Rendezvous in a Disk (SRD). By adding a common reference point (the center of a disk) that both robots can perceive, the authors explore how this additional information—or advice—can be leveraged to optimize coordination and energy consumption.

Methodology

The authors employ a combination of geometric analysis and non-linear optimization to develop a suite of algorithms tailored for the disk environment:

  1. Markovian Strategies: The researchers adapted "k-Markovian" strategies from linear rendezvous theory. In these models, robots move in randomized steps; if a meeting does not occur, the robots reset their positions and initiate a new round.
  2. Darting Algorithms ($1RB_\beta$ and $k-RB_{\beta,\gamma}$): The primary innovation is the "darting" move. Instead of restricted movement along a perimeter or line, robots "dart" toward a bisector—a potential meeting point—at a specific optimized angle ($\beta$).
  3. Optimization of Critical Angles: The efficiency of these strategies depends on the selection of movement angles. The authors modeled this as a non-linear optimization problem, using symbolic computation to identify the "critical angles" that minimize the expected rendezvous time.
  4. Energy Analysis: The paper defines "energy" as the worst-case distance traveled by an agent. While classic linear algorithms have a non-zero probability of never meeting (resulting in infinite energy), the authors demonstrate that the disk's center allows for algorithms with finite, bounded energy.

Key Insights and Ideas

Beating the 4.25 Barrier

The most significant finding is that the presence of a reference point allows robots to coordinate more effectively than on a line. Even when the center point is extremely distant (a large radius $\rho$), the robots can use it to synchronize their movements and meet in an expected time lower than the 4.25 limit conjectured for the line.

The Shrinking Disk Effect

In the proposed infinite-step algorithms, a failure to meet in one round is not a total reset. Because of the geometry of the disk, robots end up closer to the center after an unsuccessful attempt. This effectively "shrinks" the disk for the next round, making subsequent rendezvous attempts progressively easier.

The Time-Energy Tradeoff

There is a fundamental tension between minimizing the average meeting time and ensuring the robots do not exhaust their fuel in a worst-case scenario. The authors quantify this tradeoff: seeking the absolute minimum expected time requires $O(\rho^2)$ energy, but by accepting a slightly slower expected meeting time, the energy requirement can be reduced to $O(\rho)$.

Results

  • Algorithm Hierarchy: The authors developed a hierarchy of algorithms, culminating in the $\infty-RB_{\beta,\gamma}$ version, which significantly outperforms naive strategies such as simply meeting at the center point.
  • Convergence to Linear Limits: As the distance to the center ($\rho$) approaches infinity, the competitive ratio of the disk algorithm converges to 5. This matches the performance of Alpern’s classic 3-Markovian strategy for the line, providing a theoretical bridge between the two models.
  • $\delta$-Effectiveness: The authors introduced a measure of effectiveness to determine when the disk advice is most useful. Their primary algorithm is "7.13678-effective," meaning it outperforms the best-known line strategies for any disk with a radius up to approximately 7.13.
  • Quantitative Energy Bounds: For the optimal expected-time algorithm, the worst-case energy expenditure was calculated to be exactly $\frac{18}{79}\rho^2$ as $\rho \to \infty$.

Limitations and Future Work

While the paper breaks new ground in rendezvous theory, several avenues for future research remain. The authors primarily adapted "suboptimal" line algorithms (like the 3-Markovian version) because the current world-record line algorithms are mathematically too complex to adapt easily. Future work could attempt to integrate these more complex strategies to further lower the expected time.

Additionally, the study is currently limited to 2D disks. Extending these proofs to 3D spheres or other topological surfaces remains an open question. Finally, the researchers suggest exploring how other types of "advice"—such as a shared clock with an offset or a common sense of direction—might impact the efficiency of multi-agent rendezvous systems.

Summary updated

BibTeX
@article{georgiou2019symmetric,
  author = {Konstantinos Georgiou and Jay Griffiths and Yuval Yakubov},
  title = {{Symmetric Rendezvous with Advice: How to Rendezvous in a Disk}},
  journal = {J. Parallel Distributed Comput.},
  year = {2019},
  doi = {10.1016/j.jpdc.2019.07.006},
}
Figure