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 $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 $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:

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

↑
↑ "A Linear-Time Algorithm for the Feasibility of Pebble Motion on Trees". Algorithmica. 23: 223–245. doi:10.1007/PL00009259. Retrieved 2013-09-27.
1 2 3 4 "Reconfigurations in Graphs and Grids". Lecture Notes in Computer Science: 262–273. doi:10.1007/11682462_27. Retrieved 2013-09-27.
↑ First Name Middle Name Last Name (2009-05-17). "IEEE Xplore - A novel approach to path planning for multiple robots in bi-connected graphs". Ieeexplore.ieee.org. doi:10.1109/ROBOT.2009.5152326. Retrieved 2013-09-27.
↑
↑ "The (n2-1)-puzzle and related relocation problems". Portal.acm.org. doi:10.1016/S0747-7171(08)80001-6. Retrieved 2013-09-27.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.