Abstract
This paper investigates the impact of different state encoding strategies on the performance of Graph Neural Network (GNN) based heuristics for classical planning. While theoretical expressiveness is often prioritized in neural symbolic AI, this study highlights a critical trade-off between representation complexity and computational efficiency. Results demonstrate that the compact Object Encoding (Gaifman graph) consistently outperforms more complex alternatives, achieving performance levels comparable to state-of-the-art classical planners like LAMA while maintaining significantly higher evaluation speeds.
Introduction
In classical planning, agents seek a sequence of actions to reach a goal state from an initial configuration. The efficiency of this search relies heavily on heuristics—estimates of the distance to the goal. Recent advancements have leveraged GNNs to learn these heuristics directly from problem states. However, a fundamental challenge remains: how to effectively encode a logical state (e.g., "Truck A is at Location B") into a graph structure suitable for GNN processing.
Existing research often focuses on the theoretical expressiveness of encodings—their ability to distinguish between non-isomorphic states. However, highly expressive encodings frequently result in massive graphs that are computationally prohibitive for real-time search. This paper addresses this gap by systematically evaluating the practical utility of various encoding strategies within a search-based planning framework.
Methodology
The researchers integrated several encoding strategies into a GNN-based pipeline using A* search. The pipeline transforms a logical state into a graph, which is then processed by a GNN to produce a heuristic value for search guidance.
Four primary encoding strategies were analyzed:
- Object Encoding (Gaifman Graph): The most compact representation, where vertices represent objects and edges connect objects appearing together in a relation.
- Atom Encoding: Vertices represent ground atoms, with edges connecting atoms that share common objects.
- Object-Atom Encoding: A bipartite graph representing both objects and atoms.
- Relation Encoding (Rel): A specialized architecture operating directly on ground atoms without explicit graph conversion.
The models were trained using a Ranking Loss ($L^*$), which prioritizes correct state ranking along optimal paths over exact cost prediction. Evaluation was conducted on benchmarks from the IPC 2023 Learning Track, covering domains like logistics, puzzles, and infrastructure.
Key Results and Insights
The study revealed that "small is beautiful" in the context of search heuristics. The Object Encoding emerged as the superior strategy due to its minimal graph size, allowing for rapid state evaluation.
Key findings include:
- Efficiency vs. Expressiveness: While complex encodings like Atom Encoding are theoretically more expressive, they often fail to complete training on large problems within a 72-hour limit. In contrast, Object Encoding allows the GNN to evaluate states 1–2 orders of magnitude faster than grounded neural planners.
- Search Performance: Object Encoding achieved a total coverage of 46.4%, nearing the 51.4% coverage of the highly optimized LAMA planner. In domains such as
miconicandtransport, it significantly reduced the number of expanded states required to find a solution. - Model Simplicity: Post-hoc analysis indicated that shallow GNNs (e.g., 1 layer) often outperformed deeper architectures in offline search settings, further emphasizing the value of simplicity.
Conclusion
This research demonstrates that for GNN-based planning, the choice of state encoding is a pivotal factor in balancing heuristic quality and computational overhead. The Object Encoding provides a highly effective baseline that challenges the necessity of more complex, expressive representations. Future work will explore these encodings in online policy settings and investigate improved handling of global facts (nullary predicates) within graph structures.
Reference: Horčík, R., Šír, G., Šimek, V., & Pevný, T. (2025). State Encodings for GNN-Based Lifted Planners. Proceedings of the 39th AAAI Conference on Artificial Intelligence.
Summary updated