# Pebble motion problems

The **pebble motion problems**, or **pebble motion on graphs**, are a set of related problems in 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 the famous 15 puzzle where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time.

## Theoretical formulation

The general form of the pebble motion problem is Pebble Motion on Graphs^{[1]} formulated as follows:

Let be a graph with vertices. Let be a set of pebbles with . An arrangement of pebbles is a mapping such that for . A move consists of transferring pebble from vertex to adjacent unoccupied vertex . The Pebble Motion on Graphs problem is to decide, given two arrangements and , whether there is a sequence of moves that transforms into .

### Variations

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

- a tree
^{[2]} - a square grid,
^{[3]} - a bi-connected
^{[4]}graph.

Another set of variations consider the case in which some^{[5]} or all^{[3]} of the pebbles are unlabeled 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^{[6]} and APX-hard.^{[3]} The unlabeled problem can be solved in polynomial time when using the cost metric mentioned above (minimizing the total number of moves to adjacent vertices), but is NP-hard for other natural cost metrics.^{[3]}

## References

- ↑ [1]Template:Dead link
- ↑ Template:Cite web
- ↑
^{3.0}^{3.1}^{3.2}^{3.3}Template:Cite web - ↑ Template:Cite web
- ↑ [2]Template:Dead link
- ↑ Template:Cite web