View source for Pebble motion problem

In [[mathematics]], a pebble motion problem, or pebble motion on graphs, is one of a set of related problems in [[graph theory]] dealing with the movement of multiple objects ("pebbles") from [[Vertex (graph theory)|vertex]] to vertex in a graph with a [[Constraint (mathematics)|constraint]] on the number of pebbles that can occupy a vertex at any time.

== Description ==

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.

== See also ==

* [[Constraint (mathematics)]]
* [[Graph theory]]
* [[Vertex (graph theory)]]

== External links ==

* [https://en.wikipedia.org/wiki/Pebble_motion_problems Pebble motion problems] @ Wikipedia


[[Category:Mathematics]]