Oblivious agents take longer to meet on a line with limited memory
Oblivious Self-Distance Symmetric Rendezvous on the Integer Line
Discrete Mathematics
Summary
The problem is about two agents starting at some distance apart on a line trying to find each other following the same set of rules. Normally, they use all past information to meet quickly in time proportional to their starting distance. This work studies what happens if each agent forgets everything except their own position relative to where they started. The authors find that meeting takes much longer—around the square of the distance—and provide mathematical tools to find the best such strategies. They also show a way to meet almost as efficiently without knowing the initial distance.
What this means in practice
- •For robot navigation engineers: Design coordination strategies for autonomous robots with limited memory to locate each other efficiently in linear environments.
- •For distributed system designers: Develop protocols for simple networked agents to synchronize positions without full history tracking, improving feasibility in memory-constrained settings.
A theory result. No direct application yet.
Authors
Konstantinos Georgiou, Claude Gravel, Lazar Mandic, Joey Kapusin
Abstract
Symmetric rendezvous on the line is a search problem in which two agents, initially placed at distance $2d$, must follow the same randomized strategy to meet as quickly as possible. In the standard model, agents may condition their actions on the entire execution history, and both the known- and unknown-distance variants admit expected rendezvous time $Θ(d)$. We study the role of memory by introducing oblivious self-distance strategies, in which an agent's decision depends only on her position relative to her own starting location. For an initial separation of $2d$, let $R_d$ denote the optimal oblivious expected rendezvous time in the known-distance setting. We develop two finite-state frameworks based on absorbing Markov chains. Truncated chains give computable upper bounds through finite-support strategies, while weak-peek chains give lower bounds through a revealed-information relaxation. Together, they provide a mechanism for certifying optimality. Using that mechanism, we determine $R_1$ exactly and prove that it is attained by a finite-support strategy. For $d=2,\ldots,6$, numerical optimization gives the same truncation structure and objective values, yielding rigorous upper bounds below $7.83d^2$. We do not prove that the computed weak-peek minimizers are global, but the stability of the computations leads us to conjecture that they are, in which case the corresponding truncated strategies are optimal. We also prove that $R_d=Θ(d^2)$. In the unknown-distance setting, we construct a universal strategy, independent of $d$, with expected rendezvous time $O(d^{2+η})$ for every fixed $η>0$. Thus, under the memory restriction, the known-distance rendezvous time becomes quadratic, while near-quadratic performance remains possible even without knowing $d$. The asymptotic analysis uses birth-death Markov chains and their electrical-network interpretation.