Research map / Large language models / Retrieval and knowledge
Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification
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 HVR, a neuro-symbolic LLM planner combining hierarchical macro/atomic action planning, knowledge-graph RAG over an AI2-THOR ontology, and PDDL symbolic validation with LLM back-prompting correction, evaluated on 12 kitchen tasks with Phi-3 and Gemini-1.5-flash.
Problem
LLM robotic planners struggle with long-horizon, complex tasks requiring domain knowledge and produce formally incorrect plans in specialized environments such as kitchens.
Approach
Combine hierarchical macro-action decomposition, KG-based RAG over a dynamic ontology-backed knowledge graph, and PDDL symbolic validation (VAL-style and runtime state alignment) with LLM back-prompting correction, plus six new metrics for plan correctness, minimality, and verification.
Key results
- With Gemini, HVR reaches 94.19% average Plan Correctness (100% on moderate tasks, 88.39% on high), versus 85.27% for HV and 49.01% for HR.
- With Phi-3, HVR achieves 59.66% Plan Correctness versus 18.62% for HV and 54.32% for HR, showing RAG is key for the small model.
- Simulator execution of correctly planned tasks succeeded on average for about 95% of planned actions; HVR plans averaged roughly 100-200% longer than ground truth.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add hierarchical planning, KG-RAG, and symbolic verification together (ablation) | LLM planner · AI2Thor kitchen, 12 tasks; Phi-3-mini-4k-instruct | Plan Correctness (PC): 11.79 -> 59.66 | Helped |
| add hierarchical planning, KG-RAG, and symbolic verification together (ablation) | LLM planner · AI2Thor kitchen, 12 tasks; Gemini-1.5-flash | Plan Correctness (PC): 17.72 -> 94.19 | Helped |
| add KG-RAG (ablation) | hierarchical planning with symbolic verification (HV), Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Plan Correctness (PC): 18.62 -> 59.66 | Helped |
| add KG-RAG (ablation) | hierarchical planning with symbolic verification (HV), Gemini-1.5-flash · AI2Thor kitchen, 12 tasks | Plan Correctness (PC): 85.27 -> 94.19 | Helped |
| add symbolic verification (ablation) | hierarchical planning with KG-RAG (HR), Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Plan Correctness (PC): 54.32 -> 59.66 | Helped |
| add symbolic verification (ablation) | hierarchical planning with KG-RAG (HR), Gemini-1.5-flash · AI2Thor kitchen, 12 tasks | Plan Correctness (PC): 49.01 -> 94.19 | Helped |
| add hierarchical planning and symbolic verification (ablation) | RAG-only planner, Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Plan Correctness (PC): 17.73 -> 59.66 | Helped |
| apply symbolic plan correction (ablation) | HVR, Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Macro Plan Verification (MPV): 47.03 -> 74.20 | Helped |
| apply symbolic plan correction (ablation) | HV, Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Macro Plan Verification (MPV): 63.51 -> 87.86 | Helped |
| apply symbolic plan correction (ablation) | HVR, Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Atomic Action Block Verification (AABV): 27.41 -> 37.14 | Helped |
| apply symbolic plan correction (ablation) | HVR, Gemini-1.5-flash · AI2Thor kitchen, 12 tasks | Atomic Action Block Verification (AABV): 16.33 -> 79.83 | Helped |
| use hierarchical planning (ablation) | LLM planner, Phi-3-mini-4k-instruct · AI2Thor kitchen, 12 tasks | Length Discrepancy (LD), average | Mixed |
Surprising findings
- Symbolic verification alone (VR, without hierarchy) can produce negative length discrepancies, meaning plans shorter than ground truth, which hierarchical decomposition avoids.
- Verification and correction increase plan length, trading efficiency for accuracy.
Limitations
- Ground truth plans are manually defined and limited to 12 tasks in one kitchen environment.
- Plans generated are longer and contain superfluous steps, and the approach is weaker on open-ended goals.
- Simulator AI2-Thor execution failures limit end-to-end success even for correct plans.
Experimental setup
Datasets: OntoThor ontology AI2-Thor kitchen environment
Benchmarks: 12 AI2-Thor kitchen tasks (T1-T12, T5bis)
Metrics: Plan Correctness Execution Success Length Discrepancy Expanded Plan Verification Macro Plan Verification Atomic Action Block Verification
Baselines: HV HR VR R LLM (direct planner)
Builds on: LLM-Modulo OntoThor RECOVER VAL PDDL
Closest papers by meaning
- Planning in the Dark: LLM-Symbolic Planning Pipeline Without Experts (AAAI 2025 · similarity 0.90)
- Long-Horizon Planning for Multi-Agent Robots in Partially Observable Environments (NeurIPS 2024 · similarity 0.90)
- SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.90)
- Graph-enhanced Large Language Models in Asynchronous Plan Reasoning (ICML 2024 · similarity 0.89)
- Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks (ICML 2025 · similarity 0.89)
- Embodied Task Planning via Graph-Informed Action Generation with Large Language Models (ICML 2026 · similarity 0.89)
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.