Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification

Large Language Models (LLMs) have shown promise as robotic planners but often struggle with long-horizon and complex tasks, especially in specialized environments requiring external knowledge. While hierarchical planning and Retrieval-Augmented Generation (RAG) address some of these challenges, they remain insufficient on their own and a deeper integration is required for achieving more reliable systems. To this end, we propose a neuro-symbolic approach that enhances LLMs-based planners with Knowledge Graph-based RAG for hierarchical plan generation. This method decomposes complex tasks into manageable subtasks, further expanded into executable atomic action sequences. To ensure formal correctness and proper decomposition, we integrate a Symbolic Validator, which also functions as a failure detector by aligning expected and observed world states. Our evaluation against baseline methods demonstrates the consistent significant advantages of integrating hierarchical planning, symbolic verification, and RAG across tasks of varying complexity and different LLMs. Additionally, our experimental setup and novel metrics not only validate our approach for complex planning but also serve as a tool for assessing LLMs' reasoning and compositional capabilities. Code available at https://github.com/corneliocristina/HVR.

Robots are getting better at understanding everyday language, but they still struggle to plan and execute complicated tasks, especially when those tasks involve many steps, objects, or require outside knowledge. To address this, we developed a new method that helps robots think and plan more like humans do.Our system breaks down complicated problems into smaller, manageable parts using a knowledge graph using the aid of a knowledge graph, a tool that organizes facts describing the environment. The robot uses this structure to generate a plan composed by high-level instructions and then expands each of them into specific actions it can perform. To make sure these plans are not just plausible but also correct, we added a "Symbolic Validator." This component double-checks the robot’s plan to ensure that it makes sense and can be executed in the real world, based on what’s actually happening in the environment, and it flags any failures if something goes wrong.We tested our method on a range of tasks and showed it works better than existing techniques. This approach not only helps robots plan more reliably but also gives researchers a new way to understand how well AI systems reason and adapt.