Pebble motion problems
{{Short description|Set of related problems in graph theory}}
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{{r|Kornhauser}} 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{{r|Auletta}}
- a square grid,{{r|Calinescu}}
- a bi-connected graph.{{r|Surynek}}
Another set of variations consider the case in which some{{r|Papadimitriou}} or all{{r|Calinescu}} 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{{r|Ratner}} and APX-hard.{{r|Calinescu}} 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.{{r|Calinescu}}
References
{{Reflist|refs=
| last1 = Auletta | first1 = V.
| last2 = Monti | first2 = A.
| last3 = Parente | first3 = M.
| last4 = Persiano | first4 = P.
| doi = 10.1007/PL00009259
| issue = 3
| journal = Algorithmica
| mr = 1664708
| pages = 223–245
| title = A linear-time algorithm for the feasibility of pebble motion on trees
| volume = 23
| year = 1999| s2cid = 672515
}}
| last1 = Călinescu | first1 = Gruia
| last2 = Dumitrescu | first2 = Adrian
| last3 = Pach | first3 = János | author3-link = János Pach
| doi = 10.1137/060652063
| issue = 1
| journal = SIAM Journal on Discrete Mathematics
| mr = 2383232
| pages = 124–138
| title = Reconfigurations in graphs and grids
| volume = 22
| year = 2008| citeseerx = 10.1.1.75.1525
}}
| last1 = Kornhauser | first1 = Daniel
| last2 = Miller | first2 = Gary | author2-link = Gary Miller (computer scientist)
| last3 = Spirakis | first3 = Paul | author3-link = Paul Spirakis
| contribution = Coordinating pebble motion on graphs, the diameter of permutation groups, and applications
| doi = 10.1109/sfcs.1984.715921
| publisher = IEEE Computer Society Press
| title = Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS 1984)
| pages = 241–250
| year = 1984| title-link = Symposium on Foundations of Computer Science
| isbn = 978-0-8186-0591-8
| citeseerx = 10.1.1.17.3556
| s2cid = 40949575
}}
| last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou
| last2 = Raghavan | first2 = Prabhakar | author2-link = Prabhakar Raghavan
| last3 = Sudan | first3 = Madhu | author3-link = Madhu Sudan
| last4 = Tamaki | first4 = Hisao
| contribution = Motion planning on a graph
| doi = 10.1109/sfcs.1994.365740
| publisher = IEEE Computer Society Press
| title = Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994)
| pages = 511–520 | year = 1994| title-link = Symposium on Foundations of Computer Science | isbn = 978-0-8186-6580-6 | s2cid = 1998334 }}
| last1 = Ratner | first1 = Daniel
| last2 = Warmuth | first2 = Manfred | author2-link = Manfred K. Warmuth
| doi = 10.1016/S0747-7171(08)80001-6
| issue = 2
| journal = Journal of Symbolic Computation
| mr = 1080669
| pages = 111–137
| title = The -puzzle and related relocation problems
| volume = 10
| year = 1990| doi-access = free
}}
| last = Surynek | first = Pavel
| contribution = A novel approach to path planning for multiple robots in bi-connected graphs
| doi = 10.1109/robot.2009.5152326
| publisher = IEEE
| title = Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2009)
| pages = 3613–3619
| year = 2009| title-link = International Conference on Robotics and Automation
| isbn = 978-1-4244-2788-8
| s2cid = 6621773
}}
}}
{{DEFAULTSORT:Pebble Motion Problems}}