Fastest way to meet, without communication, in a toroidal palace?

Question

I was interested by a similar question asked here, but wanted to pose a slightly different variant that avoids some of the pitfalls and ambiguities in the first question in order to ask something more likely to get a concrete answer.

Suppose two robots are dropped in a palace built on a toroidal planet. The palace covers the entire surface and is broken into equal sized rooms arranged in a grid fashion. The torus is well proportioned, allowing for an equal number of rooms in both directions: that is to say, the palace has n x n rooms and, due to being on a torus, wraps in both directions.

Each robot is equipped with a teleporter. The teleporter can be programmed once per time period and will simultaneously move the robots to their target room. In order for the robots to find each other, they must either end up in same room for a given time period (either by moving to it, or remaining in it), or they may 'run into each other' by cross-teleporting to/from the same pair of rooms at the same time. The robots have no way of leaving marks or otherwise communicating with each other.

Each robot has an in-built GPS system that is pre-programmed with the size of the palace and able to track their position relative to their starting room, although their orientation is random and not guaranteed to match that of their counterpart. They also both come programmed with a strategy, however the strategy is identical for both and cannot be varied between the two robots. You do, however, have access to a random number generator.

What is the optimal strategy for the robots to find each other? If the robots could only teleport themselves to adjacent rooms, is the problem any different?

Answer 1

Sometimes I worry there aren't any better solutions than this because it's such a bad solution: just choose rooms at random.

We can label the rooms 1..n. The robots teleport to a room at random each time interval, so a robot has a 1/n chance of landing in any specific room. If landing in the same room is the only win condition, the chance of them both selecting the same room in a given time period is 1/n (much like the chance of rolling doubles with two dice).

The added condition of 'swapping' room being a win boils down to the chance that bot A and bot B simultaneously rolls each other's previous number, which multiplies out to 1/n², giving us a sum total chance of success per roll of (n + 1)/n². Naturally, the average time is the reciprocal: n²/(n + 1)

Answer 2

I think even as specified this is still a very hard problem. I'm going to do the teleport to adjacent rooms variant, but nothing substantive changes if this is modified. This is by no means an answer, the only contribution I can really add is a demonstration this problem is well-posed and an optimal strategy exists and some thoughts about what an optimal strategy might look like. I leave finding the actual optimal strategies to those cleverer who come after.

A few pieces of notation:

• Denote the finite set representing the palace by $X$.
• For any compact Hausdorff set $Y$, let $\Delta(Y)$ denote the set of all regular Borel probability measures on $Y$. It is a standard result that $Y$ compact, Hausdorff implies the same for $\Delta(Y)$ endowed with the weak-$*$ topology.
• Let $A$ denote the five-point set of allowable per-period actions $\{\textrm{North, South, East, West, No Movement}\}$

A (pure) strategy for a robot, given a starting position, is $\sigma: \mathbb{N} \to A$. The space of all pure strategies is then $A^\mathbb{N}$ endowed with the (compact) product topology, and the space of all mixed strategies $\Delta(A^\mathbb{N})$.

Define the location function $l: \mathbb{N} \times X \times A^\mathbb{N} \to X$ as the map that takes a starting location and pure strategy and returns the location in $X$ of the robot at a given time. Since we are assuming the two robots follow the same strategy, define, for starting configuration $(x_1, x_2)$:

$$ T(\sigma; x_1, x_2) = \min_{n\in \mathbb{N}}\{l(n; x_1, \sigma) = l(n; x_2, \sigma)\} $$ as the earliest meeting time of the two robots for fixed starting configuration. Further, define:

$$ \bar{T}(\sigma) = \frac{1}{|X|^2}\int_X \int_X T(\sigma, x_1, x_2) dx_1 dx_2 $$ as the earliest expected meeting time (under the assumption of both being uniformly placed down in the palace).

Then we can formalize this problem as:

$$ \inf_{\mu \in \Delta(A^\mathbb{N})} \int_{A^\mathbb{N}} \bar{T}(\sigma) \, d\mu(\sigma) \tag{$\ast$} $$

Considering for a moment the function $T(\cdot ; x_1, x_2)$ for fixed $(x_1, x_2)$, we can see that it is lower semicontinuous as for any $n$ $\{\sigma \in A^\mathbb{N} : T(\sigma; x_1, x_2) > n\}$ is open as it is product of finitely many open subsets of $A$ with infinite copies of $A$. Thus by the extreme value theorem we may replace the inf from ($\ast$) with a min as an optimal strategy necessarily exists.

---

As for finding an optimal strategy, the one nice thing that a uniform distribution on initial locations buys us is a form of stationarity effectively via translation-invariance. If, conditional on the robots not having met at a time $t$, then the best guess of each of the other's relative location is unchanged from time zero. Beyond that, would love to see if anyone can exhibit strategies that are optimal.

---

For the case of rooms arranged in a circle, I suspect using the above we can conjecture the form of optimal strategies. At time 0, each robot picks a random direction, left or right, with even probability. After traversing a certain number of rooms along the straight path given by the initial direction choice, the robots will effectively 'become sufficiently certain their counterpart picked the same direction,' and they are chasing each other indefinitely. When such a threshold is passed, the robots simply stop and re-choose 50-50 left right. If they always traverse at least a 'quarter of the circle' before changing directions then clearly they meet in finite time with probability one.