Research map / Graph learning / GNN architectures
Learning Domain-Independent Heuristics for Grounded and Lifted Planning
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 three graph representations (grounded SLG and FLG, and lifted LLG) for GNN-learned domain-independent and domain-dependent planning heuristics, with expressiveness analysis and the GOOSE GBFS planner.
Problem
Learning domain-independent heuristics for classical planning with GNNs is limited by STRIPS-HGN's delete-list omission, non-permutation-invariant aggregation, arity bounds, and the cost of grounding large hypergraphs.
Approach
Introduce three graphs (grounded SLG and FLG, and the first lifted LLG with index positional encodings for arguments) that let MPNNs learn heuristics without grounding, with theory on what MPNNs can and cannot represent (h_add, h_max, h+, h*).
Key results
- Domain-independent GOOSE with SLG outperforms or ties domain-dependent STRIPS-HGN across all domains except VisitAll.
- Domain-dependent GOOSE with LLG gives best coverage on Blocksworld and Spanner and ties hFF on Gripper; GOOSE with SLG performs best on VisitAll and VisitSome.
- Theory: MPNNs on grounded graphs can learn h_add and h_max, cannot learn h+ or h* on any of the three graphs, and LLG cannot learn h_add or h_max.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use domain-dependent GOOSE with LLG instead of other planners | GOOSE · Blocksworld | coverage | Helped |
| Use domain-dependent GOOSE with LLG instead of other planners | GOOSE · Spanner | coverage | Helped |
| Use domain-dependent GOOSE with SLG instead of other planners | GOOSE · VisitAll and VisitSome | coverage | Helped |
| Use domain-dependent GOOSE with LLG instead of Fast Downward eager GBFS with hFF | GOOSE · Gripper | coverage | No clear effect |
| Use domain-dependent GOOSE with LLG instead of hFF | GOOSE · Ferry, n-puzzle, and Sokoban | coverage | Hurt |
| Use domain-dependent GOOSE instead of blind search | GOOSE · Sokoban | coverage | Hurt |
| Use domain-dependent GOOSE instead of hFF | GOOSE · Problems solved by both planners | plan quality | Helped |
| Use domain-independent GOOSE instead of blind search | GOOSE · All domains except Sokoban | coverage | Helped |
| Use domain-independent GOOSE with SLG instead of hFF | GOOSE · VisitAll and VisitSome | coverage | Helped |
| Use domain-independent GOOSE with SLG instead of hFF | GOOSE · VisitAll, VisitSome, and more than half of shared Blocksworld instances | plan quality | Helped |
| Use domain-independent GOOSE with SLG instead of domain-dependent STRIPS-HGN | GOOSE · All domains except VisitAll | coverage | Helped |
| Use domain-independent GOOSE instead of its domain-dependent variant with the same graph | GOOSE · Planning domains | plan quality | Hurt |
Surprising findings
- All GOOSE configurations perform worse than blind search on Sokoban due to high heuristic evaluation cost.
- The lifted LLG graph cannot represent h_add or h_max, despite being the only graph that scales without grounding.
Limitations
- Search uses only eager GBFS from Fast Downward, not stronger satisficing search algorithms.
- Lifted graph evaluation does not fully utilise the GPU at typical batch sizes, raising per-state cost.
- Theory shows MPNNs cannot learn h+ or h* in general, so learned heuristics are approximate and can overfit on expressive grounded graphs.
Experimental setup
Datasets: IPC 1998-2018 benchmarks optimal plans generated by Scorpion
Benchmarks: blocksworld ferry gripper n-puzzle sokoban spanner visitall visitsome
Metrics: coverage expanded nodes plan cost heuristic value vs h* evaluation time
Baselines: blind search FF heuristic (hFF) with eager GBFS STRIPS-HGN Powerlifted
Builds on: STRIPS-HGN RGCN Fast Downward Powerlifted
Closest papers by meaning
- State Encodings for GNN-Based Lifted Planners (AAAI 2025 · similarity 0.90)
- Graph Neural Network Based Action Ranking for Planning (NeurIPS 2025 · similarity 0.87)
- Graph Learning for Numeric Planning (NeurIPS 2024 · similarity 0.87)
- Learning More Expressive General Policies for Classical Planning Domains (AAAI 2025 · similarity 0.87)
- SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge (AAAI 2024 · similarity 0.86)
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 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.