Research map / Graph learning / GNN architectures
Learning More Expressive General Policies for Classical Planning Domains
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.
Proposes R-GNN[t], a parameterized relational GNN that approximates 3-GNN expressivity by transforming the input atoms over object pairs, trading expressivity against cost via t.
Problem
General policy learning for classical planning with GNNs is limited to C2 logic; 3-GNNs reach C3 but need quartic message time and cubic space, which is infeasible.
Approach
Keep the plain R-GNN architecture but feed it a transformed atom set A_t(S) over object pairs, adding ternary triangle atoms built from pair compositions up to depth t, so that quadratic-space embeddings approximate 3-GNN expressivity with controllable cost.
Key results
- On C3 domains, R-GNN[1] achieves 75% coverage on Grid vs 45% for plain R-GNN, and 100% on Visitall-xy vs 25% for R-GNN.
- On Logistics, R-GNN[1] reaches 100% coverage (20/20) while plain R-GNN reaches 50%.
- On C2 domains, R-GNN[1] drops to 61% coverage on Gripper, while it matches R-GNN elsewhere.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add t=1 composition atoms to R-GNN (ablation) | R-GNN · Logistics | coverage: 45 % -> 100 % | Helped |
| add t=1 composition atoms to R-GNN (ablation) | R-GNN · Grid | coverage: 60 % -> 75 % | Helped |
| add t=1 composition atoms to R-GNN (ablation) | R-GNN · Visitall-xy | coverage: 75 % -> 100 % | Helped |
| add t=1 composition atoms to R-GNN (ablation) | R-GNN · Rovers | coverage: 70 % -> 70 % | No clear effect |
| increase t from 0 to 1 (ablation) | R-GNN · Gripper | coverage: 100 % -> 61 % | Hurt |
| add t=1 composition atoms to R-GNN (ablation) | R-GNN · Blocks-s, Blocks-m, Miconic, Vacuum | coverage: 100 % -> 100 % | No clear effect |
| add t=1 composition atoms to R-GNN (ablation) | R-GNN · Visitall | coverage: 95 % -> 100 % | Helped |
| use R-GNN[1] instead of plain R-GNN | general policy learning · C3 domains: Grid, Logistics, Rovers, Visitall-xy | coverage | Helped |
| use R-GNN[1] instead of Edge Transformers | general policy learning · C3 domains | coverage | Helped |
| use R-GNN[1] instead of R-GNN₂ | general policy learning · C3 domains | coverage | Mixed |
Surprising findings
- R-GNN[t] with t>1 gave no improvement over t=1 in the experiments.
- R-GNN[0] outperforms the 2-GNN baseline consistently despite both using object pairs.
Limitations
- Gripper coverage declines with t=1 relative to t=0 and plain R-GNN, attributed to high message volume and convergence issues.
- Experiments are limited to a set of planning domains with small training instances.
- Full C3 expressivity may not be needed; the paper leaves the middle ground between C2 and C3 for future work.
Experimental setup
Datasets: Blocks Grid Gripper Logistics Miconic Rovers Vacuum Visitall Navig-xy
Benchmarks: Blocks-s Blocks-m Gripper Miconic Visitall Grid Logistics Rovers Vacuum Visitall-xy
Metrics: coverage plan length
Baselines: R-GNN 2-GNN R-GNN_2 Edge Transformers
Builds on: R-GNN Edge Transformers k-GNN 2-FWL
Closest papers by meaning
- Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning (NeurIPS 2026 · similarity 0.90)
- State Encodings for GNN-Based Lifted Planners (AAAI 2025 · similarity 0.89)
- Graph Neural Network Based Action Ranking for Planning (NeurIPS 2025 · similarity 0.88)
- Learning Domain-Independent Heuristics for Grounded and Lifted Planning (AAAI 2024 · similarity 0.87)
- Efficient Subgraph GNNs by Learning Effective Selection Policies (ICLR 2024 · similarity 0.87)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 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.