7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Some clarifications, correct me if I misunderstood something. The palace has toroidal topology but no curvature. The “GPS system” is more like an inertial compass, since it only tracks relative movement. The robots are dropped simultaneously, so they have synchronized clocks. The “random direction” is a random multiple of 90°, so one of four possible directions. The optimization should minimize the expected time till the meet, since we know that in the worst case they will never meet, no matter the program. $\endgroup$ – MvG Apr 3 '15 at 18:54
  • 1
    $\begingroup$ This still sounds like a hard problem, but now it would be well suited for Code Golf SE. We wouldn't even need a central judge to match different implementations; each participant could run his code 1000 times with differently seeded PRNGs to estimate the expected value and variance. Do you want me to post this there? $\endgroup$ – MvG Apr 3 '15 at 19:00
  • $\begingroup$ I'm not even sure what the best strategy on a circle (i.e. $n$ rooms arranged in a cycle) is, let alone a torus! $\endgroup$ – Milo Brandt Apr 4 '15 at 0:18
  • 1
    $\begingroup$ I've drafted a challenge for the Programming Puzzles and Code Golf Stack Exchange. Feel free to edit that as you see fit, to clarify things. Also feel free to upvote the draft if you want to see it posted as a challenge. $\endgroup$ – MvG Apr 4 '15 at 9:29
1
$\begingroup$

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/n2, giving us a sum total chance of success per roll of (n + 1)/n2. Naturally, the average time is the reciprocal: n2/(n + 1)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'd be curious if the restriction of only being able to move into adjacent squares (say allowing diagonals) rather than teleport anywhere actually affects anything. On the one hand it means that if you start 'further' apart it takes longer to traverse the distance. On the other, it means that once we're close there are 'fewer ways to mis-coordinate.' If $n=3$ the two methods coincide due to the topology of the torus (ever pair of squares is adjacent) but I'd be curious to see if a given type of randomization does better in one context than the other. $\endgroup$ – Pete Caradonna Jun 22 '17 at 17:49
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I had considered the circle form as an even simpler version of the problem that might hint at optimal solutions for more complex spaces. I'm not convinced there is a deterministic solution to serve as an upper bound. For a circle, if you form a 2d strategy lattice (one being the position, the other being time units), you are limited to one position per time unit. There is no rigid lattice that is guaranteed to overlap with another lattice as a simple +1 displacement guarantees no overlap. Any strategy must be probabilistic, which means they cannot be guaranteed to ever meet in finite time. $\endgroup$ – Danikov Jun 22 '17 at 14:22
  • $\begingroup$ @Danikov Well certainly in the symmetric case for the circle I'd agree. (Note we can pass to a continuous case by considering Lipschitz paths from $[0,\infty) \to S^1$ with a Lipschitz constant of lets say 1 (so no one moves too fast). A suitable Arzela Ascoli gives compactness of pure strategies hence the space of mixtures over paths is compact as well.) Given our local coordinate systems are consistent, then if we both pick left then our distance from each other remains constant, and similarly right. As the above shows though we can guarantee meeting in finite time with probability 1. $\endgroup$ – Pete Caradonna Jun 22 '17 at 17:28
  • $\begingroup$ @Danikov Even more simply, say we both know we are place antipodally. Then I'd wager 50-50 starting, then re-evaluating after going 1 quarter circle is optimal. The 50-50 comes from symmetry and us minimizing the probability we are both traveling clock or counter-clockwise. Re-evaluation using the same strategy as if there were something that beat it, we would have been better off doing it at time zero, and 50-50 at time zero can't be beat. $\endgroup$ – Pete Caradonna Jun 22 '17 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.