Pebble motion problems

The general form of the pebble motion problem is Pebble Motion on Graphs[1] formulated as follows:

Let ${\displaystyle G=(V,E)}$ be a graph with ${\displaystyle n}$ vertices. Let ${\displaystyle P=\{1,\ldots ,k\}}$ be a set of pebbles with ${\displaystyle k<n}$. An arrangement of pebbles is a mapping ${\displaystyle S:P\rightarrow V}$ such that ${\displaystyle S(i)\neq S(j)}$ for ${\displaystyle i\neq j}$. A move ${\displaystyle m=(p,u,v)}$ consists of transferring pebble ${\displaystyle p}$ from vertex ${\displaystyle u}$ to adjacent unoccupied vertex ${\displaystyle v}$. The Pebble Motion on Graphs problem is to decide, given two arrangements ${\displaystyle S_{0}}$ and ${\displaystyle S_{+}}$, whether there is a sequence of moves that transforms ${\displaystyle S_{0}}$ into ${\displaystyle S_{+}}$.

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]