Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Pebble motion problems
open-in-new
<p>The pebble motion problems, or pebble motion on graphs, are a set of related problems in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> 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-<a href="/facts/Robot/S5mDzWYk">robot</a> <a href="/facts/Motion_planning/DoSPv4dB">motion planning</a> (in which the pebbles are robots) and <a href="/facts/Network_routing/Ml6MVCaC">network routing</a> (in which the pebbles are <a href="/facts/Data_packet/xCYf8SJu">packets</a> of data). The best-known example of a pebble motion problem is the famous <a href="/facts/15_puzzle/kyFRwRWs">15 puzzle</a> where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time. </p>