Problem z rekonfiguracją „Węża”

Pisząc mały post na temat złożoności gier wideo Nibbler i Snake ; Odkryłem, że oba mogą być modelowane jako problemy z rekonfiguracją na grafach płaskich; i wydaje się mało prawdopodobne, aby takie problemy nie zostały dobrze zbadane w obszarze planowania ruchu (wyobraź sobie na przykład łańcuch połączonych powozów lub robotów). Gry są dobrze znane, jednak jest to krótki opis powiązanego modelu rekonfiguracji:

PROBLEM WĄŻ

Wejście : podany płaska wykres , l kamienie P 1 , . . . , P L są umieszczane w węzłach U 1 , . . . , U L , które tworzą prostą drogą. Kamyczki przedstawiają węża , a pierwszy p 1 to jego głowa. Głowę można przenieść z aktualnej pozycji do sąsiedniego wolnego węzła, a ciało podąża za nią. Niektóre węzły są oznaczone kropką; gdy głowa dotrze do węzła z kropką, ciało wzrośnie o$G = (V,E)$$l$$p_1,...,p_l$$u_1,...,u_l$$p_1$ kamyczki w następujących e ruchów głowy. Kropka w węźle jest usuwana po przejściu węża.$e$$e$

Problem : Pytamy, czy węża można przesunąć wzdłuż wykresu i osiągnąć docelową konfigurację gdzie konfiguracja docelowa jest pełnym opisem pozycji węża, tj. Pozycji otoczaków.$T$

Łatwo jest udowodnić, że problem SNAKE jest trudny do przeprowadzenia na NP na płaskich wykresach o maksymalnym stopniu 3, nawet jeśli nie są używane kropki, a także na wykresach SOLID, jeśli możemy użyć dowolnej liczby kropek. Sprawy komplikują się na jednolitych wykresach siatki bez kropek (jest to związane z innym otwartym problemem).

Chciałbym wiedzieć, czy problem został zbadany pod inną nazwą.
a w szczególności, jeśli istnieje dowód, że jest w NP ...

Edycja: problem okazał się kompletny z PSPACE nawet na płaskich wykresach, a wynik wydaje się bardzo interesujący, więc pozostaje dowiedzieć się, czy jest to nowy problem i czy są znane wyniki na jego temat.

Prosty przykład (kamyki są pokazane na zielono, głowa węża to P1).

Przeniesienie węża z jednej pozycji do innej jest PSPACE zakończone. Snake jest trywialnie w PSPACE. Dajemy redukcję twardości PSPACE z niedeterministycznej logiki ograniczeń Hearn'a.

Niedeterministyczna logika ograniczeń

$1$$2$$\geq 2$$\geq 2$$3$$1$$3$$2$

Wąż

W naszej konstrukcji głowa węża będzie ścigała ogon w niewielkiej odległości i będzie zmuszona powtórzyć ten sam cykl z niewielkimi modyfikacjami. Osadzamy każdą krawędź wykresu ograniczenia jak na rysunku (krawędzie pokazane na czerwono), gdzie wskazujemy pozycję węża grubymi liniami. Krawędź ma dwa boki (wierzchołki), a wąż wybiera środkową trasę w wierzchołku, do którego krawędź jest skierowana.

Aby odwrócić krawędź, wąż najpierw oczyszcza środkową trasę, a następnie wybiera środkową trasę, gdy jego głowa osiągnie przeciwny wierzchołek.

$2$

Wreszcie czarne linie wszystkich gadżetów na krawędzi są połączone, tworząc jeden cykl, więc głowa węża goni ogon. Jeśli między dwoma gadżetami brzegowymi wykonamy czarną ścieżkę wystarczająco długo, wąż musi zawsze przechodzić czarne ścieżki w tej samej kolejności cyklicznej.

Aby pokazać, że czarne ścieżki zawsze można konstruować w sposób płaski, rozważ podrzędne poddrzewo (grube krawędzie na poniższym rysunku) wykresu więzów. Następnie możemy sprawić, by czarne krawędzie podążały za tym drzewem, jak pokazano poniżej, co daje wykres płaski.

Pozycja docelowa węża może być wyznaczona przez tę samą transformację. Dlatego też rekonfiguracja węża jest zakończona PSPACE, nawet na płaskich wykresach.