Pebble motion problems

Template:New unreviewed article The pebble motion problems are a set of related problems in algorithimic graph theory dealing with the movement of multiple objects ('pebbles') from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-robot motion planning (in which the pebbles are robots) and network routing (in which the pebbles are packets of data). The best known example of a pebble motion problem is Sam Loyd's famous 15-puzzle.

Theoretical formulation

The general form of the pebble motion problem is Pebble Motion on a Graph (PMG) formulated as follows:

Let $G=(V,E)$ be a graph with $n$ vertices. Let $P=\{1,\ldots ,k\}$ be a set of pebbles with $k<n$. An arrangement of pebbles is a mapping $S:P\rightarrow V$ such that $S(i)\neq S(j)$ for $i\neq j$. A move consists $m=(p,u,v)$ of transferring pebble $p$ from vertex $u$ to adjacent unoccupied vertex $v$. The PMG problem is to decide, given two arrangements $S_{0}$ and $S_{+}$, whether there is a sequence of moves that transforms $S_{0}$ into $S_{+}$.

Variations

Common variations on the problem limit the structure of the graph to be:

• a tree
• a square grid,
• a bi-connected graph.

Another set of variations consider the case in which some or all of the pebbles are unlabelled and interchangeable.

Other versions of the problem seek not only to prove reachability but to find a (potentially optimal) sequence of moves (i.e. a plan) which performs the transformation.

Complexity

Finding the shortest path in the pebble motion on graphs problem (with labeled pebbles) is known to be NP-hard and APX-hard. The same applies to the unlabelled problem .