Lesson 1

In the 15 Puzzle, almost every cell is occupied, and the one empty cell controls all movement. Let us now reverse the situation: only a few cells contain moving objects, and every object has its own destination.

This is a basic model of a robotic warehouse. A single robot may have a short route to its destination, but several such routes must be chosen together. Otherwise, two robots may try to enter the same cell, meet head-on in a narrow passage, or block one another.

The resulting problem is called coordinated motion planning. It is much like the 15 Puzzle: a configuration is a vertex of a large implicit graph, a legal move is an edge, and the question is whether the initial and target configurations are connected by a path.