Suppose two friends live in different cities on a map, such as the Romania map shown in Figure $3\mathrm{.}2.$ On every turn, we can simultaneously move each friend to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road distance d$($i$,$ j$)$ between the cities, but on each turn the friend that arrives first must wait until the other one arrives $($and calls the first on his$/$her cell phone$)$ before the next turn can begin. We want the two friends to meet as quickly as possible.

a$.$ Write a detailed formulation for this search problem. $($You will find it helpful to define

some formal notation here.$)$

b$.$ Let D$($i$,$ j$)$ be the straight$-$line distance between cities i and j$.$ Which of the following

heuristic functions are admissible? $($i$)$ D$($i$,$ j$)$; $($ii$)2$ D$($i$,$ j$)$; $($iii$)$ D$($i$,$ j$)/2.$

c$.$ Are there completely connected maps for which no solution exists?

d$.$ Are there maps in which all solutions require one friend to visit the same city twice?

Which of the following are true and which are false? Explain your answers.

a$.$ Depth$-$first search always expands at least as many nodes as A$$ search with an admissible heuristic.

b$.$ h$($n$)=0$ is an admissible heuristic for the $8-$puzzle.

c$.$ A$$ is of no use in robotics because percepts, states, and actions are continuous.

d$.$ Breadth$-$first search is complete even if zero step costs are allowed.

e$.$ Assume that a rook can move on a chessboard any number of squares in a straight line,vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from square A to square B in

the smallest number of moves.