The pebble motion problems, or pebble motion on graphs, are a set of related problems in

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

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 A robot is a machine—especially one Computer program, programmable by a computer—capable of carrying out a complex series of actions Automation, automatically. A robot can be guided by an external control device, or the robot control, co ...

motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...

(in which the pebbles are robots) and

network routing Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone netw ...

(in which the pebbles are packets of data). The best-known example of a pebble motion problem is the famous

15 puzzle The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and more) is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied pos ...

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 formulated as follows: Let

G = (V,E)

be a graph with

n

vertices. Let

P = \

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

m = (p, u, v)

consists of transferring pebble

p

from vertex

u

to adjacent unoccupied vertex

v

. The Pebble Motion on Graphs 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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

* a

square grid In geometry, the square tiling, square tessellation or square grid is a regular tiling of the Euclidean plane consisting of four squares around every vertex. John Horton Conway called it a quadrille. Structure and properties The square tiling ...

, * a bi-connected graph. Another set of variations consider the case in which some or all 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 solution sequence in the pebble motion on graphs problem (with labeled pebbles) is known to be

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

and

APX-hard In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor a ...

. 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

for other natural cost metrics.

References

{{DEFAULTSORT:Pebble Motion Problems Multi-agent systems Automated planning and scheduling Computational problems in graph theory