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.