Research map / Graph learning / GNN architectures
State Encodings for GNN-Based Lifted Planners
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Compares existing GNN state encodings (object, atom, object-atom, and the Rel message-passing encoding) for lifted classical planning heuristics trained with a ranking loss, finding the Gaifman-graph object encoding best on IPC 2023 learning domains.
Problem
Which state encoding for GNN-based heuristics in lifted classical planning is most effective in practice, balancing expressiveness, evaluation time, and informativeness, since prior work only assessed expressiveness.
Approach
A systematic comparison of all existing lifted state encodings (object/Gaifman graph, atom, object-atom, and relational message passing) under a common A* offline setting with a ranking loss; the smallest Gaifman-graph object encoding, not previously used in planning, gives the best trade-off of fast evaluation and informative heuristics.
Key results
- Object (Gaifman) encoding with multi-hot graph Gr achieves the highest total coverage of 46.4% vs 36.3-37.5% for other lifted encodings in the 30-second offline A* setting.
- Object encoding is the smallest and fastest to evaluate; its overall coverage nearly matches LAMA (51.4%) while being complementary across domains.
- Object encoding generally expands fewer or similar numbers of states compared with other encodings, with atom encoding informative on ferry.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use object encoding with graph Gg rather than the other tested state encodings | GNN-based lifted planner · IPC 2023 learning track test, total | coverage (%): 46.4 vs 34.9 | Helped |
| Use object encoding with graph Gg rather than LAMA | GNN-based lifted planner · IPC 2023 learning track test, total | coverage (%): 46.4 vs 51.4 | Hurt |
| Replace object encoding graph Gg with multigraph Gm (ablation) | Object encoding · IPC 2023 learning track test, total | coverage (%): 46.4 -> 37.5 | Hurt |
| Replace object encoding graph Gg with edge-typed graph G (ablation) | Object encoding · IPC 2023 learning track test, total | coverage (%): 46.4 -> 36.3 | Hurt |
| Replace atom encoding graph Gg with multigraph Gm (ablation) | Atom encoding · IPC 2023 learning track test, total | coverage (%): 29.4 -> 18.6 | Hurt |
| Replace atom encoding graph Gg with edge-typed graph G (ablation) | Atom encoding · IPC 2023 learning track test, total | coverage (%): 29.4 -> 22.1 | Hurt |
| Use bipartite multigraph BipMGr instead of BipGr (ablation) | Object-atom encoding · IPC 2023 learning track test, total | coverage (%): 26.2 -> 29.3 | Helped |
| Use bipartite edge-typed graph BipEGr instead of BipGr (ablation) | Object-atom encoding · IPC 2023 learning track test, total | coverage (%): 26.2 -> 32.8 | Helped |
| Use atom encoding rather than object encoding | GNN-based lifted planner · IPC 2023 learning track test, total | coverage (%): 46.4 vs 29.4 | Hurt |
| Use object-atom encoding rather than object encoding | GNN-based lifted planner · IPC 2023 learning track test, total | coverage (%): 46.4 vs 32.8 | Hurt |
| Use the object encoding rather than Rel | GNN-based lifted planner · IPC 2023 learning track test, total | coverage (%): 46.4 vs 34.9 | Helped |
| Use the object encoding rather than ASNet | GNN-based planner · IPC 2023 learning track test, total | coverage (%): 46.4 vs 18.8 | Helped |
Surprising findings
- Smaller models (hidden dimension 4, a single message-passing layer) often gave the best coverage, indicating smaller models work better in the offline setting.
- Object-atom encodings and atom encodings can be computationally expensive; the atom encoding has the fewest indistinguishable state pairs but is much slower to evaluate.
Limitations
- Evaluation limited to IPC 2023 learning track domains and an offline A* setting; online/greedy policy setting not studied.
- Coverage nearly but not fully matches LAMA; results averaged over only three seeds.
- Heuristic is not admissible, so A* is used despite being trained as a non-admissible heuristic.
Experimental setup
Datasets: IPC 2023 learning track
Benchmarks: IPC 2023 learning track
Metrics: coverage expanded states evaluation time plan length indistinguishable state pairs
Baselines: LAMA ASNet STRIPS-HGN LMCut (Fast Downward)
Builds on: Gaifman graph encoding (Horčík and Šír 2024) ranking loss L* (Chrestien et al. 2023) Rel message-passing architecture (Ståhlberg et al. 2022) object-atom encoding (Chen et al. 2024)
Closest papers by meaning
- Learning Domain-Independent Heuristics for Grounded and Lifted Planning (AAAI 2024 · similarity 0.90)
- Learning More Expressive General Policies for Classical Planning Domains (AAAI 2025 · similarity 0.89)
- Graph Neural Network Based Action Ranking for Planning (NeurIPS 2025 · similarity 0.89)
- Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning (NeurIPS 2026 · similarity 0.87)
- Graph Learning for Numeric Planning (NeurIPS 2024 · similarity 0.86)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.