While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such problems have not been well studied in the motion planning area (imagine for example a chain of linked carriages or robots). The games are well known, however this is a short description of the related reconfiguration model:
Input: given a planar graph $G = (V,E)$, $l$ pebbles $p_1,...,p_l$ are placed on nodes $u_1,...,u_l$ that form a simple path. The pebbles represent the snake, and the first one $p_1$ is his head. The head can be moved from its current position to an adjacent free node, and the body follows it. Some nodes are marked with a dot; when the head reaches a node with a dot, the body will increase by $e$ pebbles in the following $e$ moves of the head. The dot on the node is deleted after the traversal of the snake.
Problem: We ask if the snake can be moved along the graph and reach a target configuration $T$ where the target configuration is the full description of the snake position, i.e. the position of the pebbles.
It is easy to prove that the SNAKE problem is NP-hard on planar graphs of max degree 3 even if no dots are used and also on SOLID grid graphs if we can use an arbitrary number of dots. Things get complicated on solid grid graphs without dots (it is related to another open problem).
I would like to know if the problem has been studied under another name.
and, in particular, if there is a proof that it is in NP ...
Edit: the problem turned out to be PSPACE-complete even on planar graphs and the result seems very interesting, so it remains to find out if it is a new problem and if there are known results about it.
A simple example (pebbles are shown in green, the snake's head is P1).