Lesson 2

Probably, the first heuristic that comes to mind is the following. For every robot \(R_{i}\), run breadth-first search on the grid from its target \(t_{i}\), ignoring all other robots. This gives the distance \(d_{i}(v)\) from every free cell \(v\) to \(t_{i}\).

For a configuration \(P=(p_{1},\dotsc,p_{k})\), define \[h_{\max}(P)=\max_{1\le i\le k}d_{i}(p_{i}).\] It is easy to see that the heuristic \(h_{\max}\) is admissible.

However, the heuristic \(h_{\max}\) does not care about the positions of other robots. We can make it stronger by remembering exact solutions for pairs of robots.

Fix robots \(R_{i}\) and \(R_{j}\). For two different free cells \(u\) and \(v\), let \(D_{ij}(u,v)\) be the minimum number of steps needed to move just these two robots from \(u,v\) to their targets, subject to the same vertex- and edge-collision rules. All values of \(D_{ij}\) can be computed by one breadth-first search in the two-robot graph, starting from \((t_{i},t_{j})\) and running backwards. This graph has at most \(m(m-1)\) states and at most \(25\) candidate actions per state. So, we use \[h(P)=\max_{1\le i<j\le k}D_{ij}(p_{i},p_{j}).\] This heuristic is admissible, and you are asked to implement the \(A^{*}\) algorithm for motion planning in the next step.