Graph Neural Networks; Graph Attention Network; Subgoal Prediction; Heuristic search

Tato práce aplikuje grafové neuronové sítě na predikci podcílů ve hře s názvem Ricochet Robots, NP-úplné logické hře. Herní stavy jsou reprezentovány jako orientované grafy, kde uzly odpovídají políčkům mřížky a hrany reprezentují pohyby robotů. Rekurentní architektura Graph Attention Network je trénována k napodobení hierarchické vyhledávací heuristiky, která identifikuje slibné pozice (podcíle), kterých by cílový robot měl dosáhnout. Vyhodnoceny jsou dva klasifikační úkoly: identifikace políček, ze kterých je cíl nezávisle dosažitelný, a predikce optimálních podcílů. Model dosahuje téměř dokonalého výkonu u jednoduššího úkolu dosažitelnosti a prokazuje významné učení u komplexnějšího úkolu predikce optimálních podcílů. Výsledky potvrzují, že grafové neuronové sítě dokážou zachytit prostorové uvažování potřebné pro identifikaci podcílů ve výpočetně náročných problémových doménách, čímž vytvářejí základ pro autonomní objevování podcílů v komplexních stavových prostorech.

This work applies Graph Neural Networks to predict subgoals in a game called Ricochet Robots, an NP-complete puzzle game. Game states are represented as directed graphs where nodes correspond to grid tiles and edges represent robot movements. A recurrent Graph Attention Network architecture is trained to imitate a hierarchical search heuristic that identifies promising intermediate positions (subgoals) the target robot should reach. Two classification tasks are evaluated: identifying tiles from which the goal is independently reachable, and predicting optimal subgoals. The model achieves near-perfect performance on the simpler reachability task and demonstrates substantial learning on the more complex optimal subgoal prediction task. Results validate that graph neural networks can capture the spatial reasoning required for subgoal identification in computationally challenging puzzle domains, establishing groundwork for autonomous subgoal discovery in complex state spaces.