Problème de reconfiguration «serpent»

En écrivant un petit post sur la complexité des jeux vidéo Nibbler et Snake ; J'ai trouvé que les deux peuvent être modélisés comme des problèmes de reconfiguration sur les graphes planaires; et il semble peu probable que de tels problèmes n'aient pas été bien étudiés dans le domaine de la planification du mouvement (imaginez par exemple une chaîne de chariots ou de robots liés). Les jeux sont bien connus, mais voici une courte description du modèle de reconfiguration associé:

PROBLÈME DE SERPENT

Entrée : étant donné un graphe planaire , l galets p 1 , . . . , P l sont placés sur des nœuds u 1 , . . . , u l qui forment un chemin simple. Les cailloux représentent le serpent , et le premier p 1 est sa tête. La tête peut être déplacée de sa position actuelle vers un nœud libre adjacent, et le corps la suit. Certains nœuds sont marqués d'un point; lorsque la tête atteint un nœud avec un point, le corps augmente de$G = (V,E)$$l$$p_1,...,p_l$$u_1,...,u_l$$p_1$ cailloux dans les e mouvements suivants de la tête. Le point sur le nœud est supprimé après la traversée du serpent.$e$$e$

Problème : Nous demandons si le serpent peut être déplacé le long du graphique et atteindre une configuration cible où la configuration cible est la description complète de la position du serpent, c'est-à-dire la position des cailloux.$T$

Il est facile de prouver que le problème SNAKE est NP-difficile sur les graphes planaires de degré maximum 3 même si aucun point n'est utilisé et également sur les graphes de grille SOLIDE si nous pouvons utiliser un nombre arbitraire de points. Les choses se compliquent sur les graphiques à grille solide sans points (c'est lié à un autre problème ouvert).

Je voudrais savoir si le problème a été étudié sous un autre nom.
et, en particulier, s'il y a une preuve qu'il est en NP ...

Edit: le problème s'est avéré être PSPACE complet même sur les graphes planaires et le résultat semble très intéressant, il reste donc à savoir s'il s'agit d'un nouveau problème et s'il existe des résultats connus à ce sujet.

Un exemple simple (les cailloux sont représentés en vert, la tête du serpent est P1).

Déplacer un serpent d'une position à une autre est PSPACE complet. Snake est trivialement dans PSPACE. Nous donnons une réduction de dureté PSPACE à partir de la logique de contrainte non déterministe de Hearn.

Logique de contrainte non déterministe

$1$$2$$\geq 2$$\geq 2$$3$$1$$3$$2$ . Le premier type de sommet est appelé Et et le dernier est appelé Ou (voir figure).

Serpent

Dans notre construction, la tête du serpent chassera sa queue à une petite distance et sera obligée de répéter le même cycle avec des modifications mineures. Nous incorporons chaque bord du graphe de contraintes comme sur la figure (bords montrés en rouge), où nous indiquons la position du serpent par des lignes épaisses. Un bord a deux côtés (sommets) et le serpent prend la route centrale au sommet auquel le bord est dirigé.

Pour inverser un bord, le serpent efface d'abord la route centrale puis prend la route centrale une fois que sa tête atteint le sommet opposé.

$2$

Enfin, les lignes noires de tous les gadgets de bord sont connectées pour former un seul cycle, de sorte que la tête du serpent poursuit sa queue. Si entre deux gadgets de bord, nous rendons le chemin noir suffisamment long, le serpent doit toujours parcourir les chemins noirs dans le même ordre cyclique.

Pour montrer que les chemins noirs peuvent toujours être construits de manière plane, considérons un sous-arbre couvrant (bords épais dans la figure ci-dessous) du graphe de contraintes. Ensuite, nous pouvons faire suivre les bords noirs de cet arbre comme illustré ci-dessous, ce qui donne un graphique planaire.

La position cible du serpent peut être dérivée par la même transformation. Par conséquent, reconfigurer un serpent est PSPACE complet, même sur des graphes planaires.