= Simultaneous rendezvous distance
{title2=$\lceil d(p,q)/2\rceil$}
Two controlled walkers on the same connected <undirected graph> can each traverse one <edge> or wait in each unit-cost step. If they meet only by occupying the same <vertex> at the same time, their minimum meeting time is
$$
\left\lceil\frac{d(p,q)}2\right\rceil,
$$
where $d$ is the <shortest path> distance. A common meeting point after $t$ steps implies $d(p,q)\le2t$ by the <triangle inequality>. Conversely, choose a middle <vertex> of a shortest connecting <graph path>; both walkers reach it within $\lceil d/2\rceil$ steps, and the earlier arrival waits. The wait is essential when the path length is an <odd integer>. This distance on the joint <Cartesian product> <state space> is a <consistent heuristic>: each joint move changes the walkers’ separation by at most two. Replacing $d$ by an obstacle-free <Manhattan distance> preserves <admissible heuristic> and <consistent heuristic> guarantees.
Back to article page
