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

We thank the reviewer for their valuable feedback, which has greatly improved our paper. Below, we summarize the main concerns and detail the revisions and clarifications made to address them.

Q1: Missing comparison and discussion of efficiency

We have included a study of the efficiency of our method including 2 new plots in a new section in the appendix "Efficiency considerations" in the revised paper:

Figure A (Average execution times (in seconds) per model using Gemini 1.5 flash) shows the average computational time for the different models across the 13 tasks using Gemini-1.5-flash as LLM. As expected, approaches involving hierarchical decomposition require (approximately three times) more time than those without. However, as LLMs become faster, the overhead introduced by the HVR framework becomes increasingly negligible, while substantially improving plan correctness. For example, running the same tasks with Gemini-2.0-flash reduced the average execution time for HVR from 3285.32 seconds to 681.51 seconds—a 5x improvement.

In contrast to this improvement, relying solely on an LLM as a planner demands a substantially larger context window, which quickly becomes impractical as task or environment complexity increases. HVR addresses this limitation through retrieval-augmented generation (RAG), enabling it to dynamically access only the relevant information from the knowledge graph. This design ensures stable processing times and scalability, even as the environment grows, whereas LLM-only approaches face escalating computational demands and eventual context window exhaustion.

Figure B (Plan Correctness vs. Execution Time in seconds with Gemini 1.5 flash) shows the trade-off between plan correctness and execution time across the different methods. While HVR takes longer to compute plans, it consistently achieves the highest correctness. In contrast, simpler methods like LLM or R achieve faster execution but produce significantly less reliable plans, demonstrating the benefit of HVR’s more structured approach.

We thank the reviewer for their valuable feedback, which has greatly improved our paper. Below, we summarize the main concerns and detail the revisions and clarifications made to address them.

Q1: Missing comparison with the state-of-the-art

We did not include direct comparisons with existing methods, as none address complex, long-horizon kitchen tasks compatible with our setup. However, following reviewers’ suggestions, we considered additional works and included additional results/discussion in the Appendix of the revised paper, summarized below:

• SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Models This work is closely related to ours, as it uses the same simulator and addresses complex tasks (but in a multi-agent setting). We considered only 15 tasks, excluding those not related to the kitchen domain, of which only 12 were feasible in our setup due to a key design difference: unlike SMART-LLM, which assumes full knowledge of all object locations (including hidden ones), our system—aligned with RECOVER —only considers visible objects (hidden objects are treated as failures). HVR with Gemini-2.0-flash successfully planned and executed all 12 tasks.
• ProgPrompt: Generating Situated Robot Task Plans using Large Language Models In this work there are 10 available tasks, 7 of which are kitchen related. We adapted the original implementation with the VirtualHome simulator to the AI2Thor simulator. Using Gemini-2.0-flash, HVR was able to plan and execute correctly all of the tasks. However, it's worth noting that these tasks are relatively simple compared to those in our benchmark. Additionally, ProgPrompt was evaluated using GPT-3, and their performance would likely improve with a more capable LLM.
• LLM+P: Empowering Large Language Models with Optimal Planning Proficiency These methods are built on different simulators and/or involve tasks that are not compatible with our setup (e.g., organizing blocks on a table). As a result, a direct comparison would require a substantial and non-trivial reimplementation, which falls outside the scope of this work.
• PDDL-based planning systems We could not compare with PDDL-based planning systems on our tasks as we found no existing works using planners expressive enough. As described in Section 3.3, our system uses conjunctive, disjunctive, and conditional PDDL statements. We therefore implemented a custom validator in Python, adapted specifically to the AI2Thor environment.
• ISR-LLM: Iterative Self-Refined Large Language Model for Long-Horizon Sequential Task Planning Here, given specifications of simple abstract tasks in a simulated kitchen environment, the authors generate both a PDDL domain and a goal state. While this can work for a simple environment with few available actions, we argue it is generally not possible to generate PDDL domain specifications from high-level natural language task specifications such as those we use in our work. Thus, we did not run experimental comparisons with this method.
• Translating Natural Language to Planning Goals with Large-Language Models This work uses the ALFRED simulator, similar to AI2Thor. However, the implementation is too limited for our use case and does not support key functionalities like creating individual slices after slicing an object, or modeling interactions such as opening appliances—essential for our tasks— making it unsuitable for a meaningful comparison.

Q2: Evaluation of Error Detection/Recovery and System Robustness

We thank the reviewer for the suggestion. The metrics EPV, MPV, and AABV (highlighted as blue metrics in the ‘Verification’ part of in Table 2) are specifically designed to evaluate the role of symbolic verification and correction. These metrics are defined as follows: (4) Expanded Plan Verification (EPV) indicates the extent to which the expanded plan (full sequence of atomic ac- tions) has been successfully verified. It is calculated as the ratio of verified steps to the total number of steps in the generated plan. (5) Macro Plan Verification (MPV) measures the extent to which the macro plan has been verified. It is calculated as the ratio of verified macro plan steps to the total number of macro steps. (6) Atomic Action Block Verification (AABV) evaluates the extent to which the macro plan has been verified at the level of atomic action blocks. It is determined by dividing the number of verified atomic action blocks by the total number of macro actions.

To summarize, these metrics reflect how effectively the symbolic validator detects and helps recover from errors at different levels of the plan (expanded, macro, and atomic action blocks). Their strong correlation with Plan Correctness (PC) demonstrates that symbolic validation not only identifies errors but also leads to measurable improvements in plan quality. This provides insight into the system’s robustness and adaptability in recovering from planning errors.

We thank the reviewer for their valuable feedback, which has greatly improved our paper. Below, we summarize the main concerns and detail the revisions made to address them.

Q1: Why is it necessary to use an LLM for planning in this setting?

While prior works such as [1] and [2] show how natural language (NL) instructions can be translated into PDDL goals, they are limited to simple tasks and lack the flexibility needed for more complex scenarios. Moreover, symbolic planners tend to be brittle—minor changes in the environment or execution failures can break the entire plan. In contrast, HVR leverages the flexibility of LLMs throughout the whole planning process, addressing several key limitations of symbolic–only methods:

• Partial plan execution: for particularly complex tasks, LLM-based models are able to produce at least some correct initial steps or an initial sub-task, while symbolic planners can only generate full plans and thus likely failing entirely on these type of tasks
• LLMs enable dynamic adaptation during task execution, incorporating feedback from the environment to replan on the fly. Symbolic planners would need new mid-task NL instructions.
• Thanks to LLMs, and even more thanks to the employment of retrieval-augmented generation (RAG), our approach achieves significantly faster planning, avoiding the exponential search space growth typical of classical planners.

Lastly, although HVR currently relies on a fixed world model, it can be extended to operate without one—just as we generate macro-actions and their pre/post-conditions dynamically.

Q2: Missing comparison with the state-of-the-art

We did not include direct comparisons with existing methods, as none address complex, long-horizon kitchen tasks compatible with our setup. However, following reviewers’ suggestions, we considered additional works and included new results/discussions in the appendix of the revised paper. See the full response to Review-Ac9Q, summarized here:

• SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Models This work is closely related to ours, as it uses the same simulator and addresses complex tasks (but in a multi-agent setting). HVR with Gemini-2.0-flash successfully planned and executed all 12 tasks.
• ProgPrompt: Generating Situated Robot Task Plans using Large Language Models We adapted the original implementation with the VirtualHome simulator to the AI2Thor simulator. HVR with Gemini-2.0-flash was able to plan and execute correctly all kitchen-related tasks.
• LLM+P: Empowering Large Language Models with Optimal Planning Proficiency These methods are built on different simulators and/or involve tasks that are not compatible with our setup.
• PDDL-based planning systems We could not compare with PDDL-based planning systems on our tasks as we found no existing works using planners expressive enough.
• Translating Natural Language to Planning Goals with Large-Language Models This work uses the ALFRED simulator, similar to AI2Thor. However, the implementation is too limited for our use case and does not support key functionalities making it unsuitable for a meaningful comparison.

Q3: Missing discussion about HVR limitations

We have included a discussion of our work’s limitations and future work in a new section in the appendix in the revised paper:

The HVR framework integrates hierarchical planning, knowledge graph retrieval, and symbolic validation to enhance LLM-based task planning, but it also presents several limitations that point to promising directions for future work. One key limitation is its reliance on a fixed ontology and action space, which constrains generalization to new environments or tasks. While updating to the ontology currently requires expert domain knowledge, the predefined action space could be extended to include novel actions automatically using LLM-based techniques—similar to how HVR currently generates macro actions along with their corresponding pre- and post-conditions. Prompt sensitivity is another concern common to LLM-based systems, although recent models show improved robustness to variations in prompt phrasing. Additionally, HVR's current use of natural language to mediate interactions between the LLM and the knowledge graph may not be the most efficient; leveraging sub-symbolic or embedded representations could improve this integration. Another limitation is the current restriction to a linear structure for the generated plans. Supporting partial-order plans would not only allow for more flexible planning but also make it possible to execute different branches in parallel, which is especially valuable in multi-agent settings. Finally, in our method, error correction is done independently for each part of the plan and does not address interdependencies between errors at different planning levels. A more connected correction strategy that reasons across macro and atomic actions could help improve overall correctness.

We thank the reviewer for their valuable feedback, which has greatly improved our paper. Below, we summarize the main concerns and detail the revisions and clarifications made to address them.

Q1: Missing details and experiments regarding the reusable library of macro actions

The macro actions are stored in the ontology following the same approach used in Cornelio & Diab 2024. While we have not yet conducted experiments leveraging the macro action library to accelerate the planning process, we plan to explore this in the future. We added additional details in a new section in the appendix, summarized below:

OntoThor contains the class Action representing agent-environment interactions. We refine this by introducing two subclasses: Atomic Action (AA), as the original Action class, and Macro Action (MA) representing higher-level operations like boil-water. During execution, AA and MA instances are stored in the agent’s Knowledge Graph. Each MA instance is linked to its NL description including pre- and post-conditions, via the hasDescription predicate. These conditions can also be modeled as triples, extending the scene-graph representation in OntoThor. Each MA instance is also linked to its sequence of AAs via the hasAtomicAction predicate. After task execution, the set of MAs, along with their associated conditions, are stored in the Knowledge Graph and, if validated by the environment (see section 2.4), also added to the ontology.

Q2: Missing References

Thank you for the suggested references. We’ve added the missing citations and included SMART-LLM—previously unknown to us—in the revised manuscript, along with an experimental comparison (see Q3).

Q3: Missing comparison with State-of-the-art systems

We did not include direct comparisons with existing methods, as none address complex, long-horizon kitchen tasks compatible with our setup. However, following reviewers’ suggestions, we considered additional works and included additional results/discussion in the Appendix of the revised paper, summarized below:

• SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Models This work is closely related to ours, as it uses the same simulator and addresses complex tasks (but in a multi-agent setting). We considered only 15 tasks, excluding those not related to the kitchen domain, of which only 12 were feasible in our setup due to a key design difference: unlike SMART-LLM, which assumes full knowledge of all object locations (including hidden ones), our system—aligned with RECOVER —only considers visible objects (hidden objects are treated as failures). HVR with Gemini-2.0-flash successfully planned and executed all 12 tasks.
• ProgPrompt: Generating Situated Robot Task Plans using Large Language Models In this work there are 10 available tasks, 7 of which are kitchen related. We adapted the original implementation with the VirtualHome simulator to the AI2Thor simulator. Using Gemini-2.0-flash, HVR was able to plan and execute correctly all of the tasks. However, it's worth noting that these tasks are relatively simple compared to those in our benchmark. Additionally, ProgPrompt was evaluated using GPT-3, and their performance would likely improve with a more capable LLM.
• LLM+P: Empowering Large Language Models with Optimal Planning Proficiency These methods are built on different simulators and/or involve tasks that are not compatible with our setup (e.g., organizing blocks on a table). As a result, a direct comparison would require a substantial and non-trivial reimplementation, which falls outside the scope of this work.
• PDDL-based planning systems We could not compare with PDDL-based planning systems on our tasks as we found no existing works using planners expressive enough. As described in Section 3.3, our system uses conjunctive, disjunctive, and conditional PDDL statements. We therefore implemented a custom validator in Python, adapted specifically to the AI2Thor environment.
• ISR-LLM: Iterative Self-Refined Large Language Model for Long-Horizon Sequential Task Planning Here, given specifications of simple abstract tasks in a simulated kitchen environment, the authors generate both a PDDL domain and a goal state. While this can work for a simple environment with few available actions, we argue it is generally not possible to generate PDDL domain specifications from high-level natural language task specifications such as those we use in our work. Thus, we did not run experimental comparisons with this method.
• Translating Natural Language to Planning Goals with Large-Language Models This work uses the ALFRED simulator, similar to AI2Thor. However, the implementation is too limited for our use case and does not support key functionalities like creating individual slices after slicing an object, or modeling interactions such as opening appliances—essential for our tasks— making it unsuitable for a meaningful comparison.