= Solution
Let $D(p,q)=|p_x-q_x|+|p_y-q_y|$ be their <Manhattan distance>. Each joint action can reduce $D$ by at most two, so use the <simultaneous rendezvous distance>
$$
\boxed{h(p,q)=\left\lceil\frac{D(p,q)}2\right\rceil.}
$$
This <heuristic function> is nonzero whenever the robots are apart. For a transition $(p,q)\to(p',q')$, the <triangle inequality> gives
$$
D(p,q)\le D(p,p')+D(p',q')+D(q',q)\le2+D(p',q').
$$
Applying the <ceiling function> yields $h(p,q)\le1+h(p',q')$, and $h(p,p)=0$. Thus \b[$h$ is a <consistent heuristic>], hence an <admissible heuristic>.
In the unobstructed grid this estimate is exact. Along a shortest route of length $D$, both robots approach a middle room, taking at most $\lceil D/2\rceil$ steps each; when $D$ is an <odd integer>, the robot with the shorter route waits once. That final wait prevents a crossing from being mistaken for a meeting. With obstacles the same formula remains a <relaxation heuristic>, though it need not be exact.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2022/artificial-intelligence-rendezvous-distance.png]
{title=An original nine-edge route needs five simultaneous steps: the last wait produces a meeting rather than a crossing}
Back to article page
