Lesson 4

Current configuration of robots can be represented by a \(k\)-tuple \[P=(p_{1},\dotsc,p_{k}),\] where \(p_{i}\) is the cell occupied by robot \(R_{i}\).

To generate all neighboring configurations, we choose one of at most five actions for every robot: wait, move up, move down, move left, or move right. We then discard every action that leaves the grid, enters a blocked cell, creates a common destination, or exchanges the positions of two robots.

This gives an ordinary unweighted graph of configurations. Hence, breadth-first search determines whether the target configuration is reachable. It also finds a schedule with the minimum number of time steps.