Leveraging Environment Interaction for Automated PDDL Translation and Planning with Large Language Models

We thank the reviewer for their positive comments. Due to character limit constraints, below we summarize and answer the main questions raised by the reviewer.

Q1: Assumption 2 may be unrealistic. What if the domain description lacks a constraint?

We put the first steps towards using the environment as a source of refinement on top of natural language for domain PDDL generation. We have removed the biggest assumption/blocker, which is human feedback. While our framework, at its current state, may not provide high accuracy in the absence of natural language description, or partial natural language description, we are excited to see future extensions of our work that rely more on environment interaction and less (or not at all) on natural language descriptions. Particularly, partial information in NL can be addressed in future work through better prompting for LLM to propose and fill in missing information. This can be further enhanced by multiple guesses in an overall search tree-like reasoning setup that is on top of the "search tree" in our method. Our work lays the groundwork for achieving this goal.

Q2: There is a dependency on the environment to do the refinement, and that also may limit the impact of the proposed solution as the environment may not always be available for all domains.

We understand the concern that the "PDDL" environment might not always be available, thus limiting the impact. Our framework is not limited to PDDL environments, although the current implementation is. The only scenario where our framework is not applicable is when environment feedback is significantly delayed or slow. In such cases, relying on fully automated agent planning and action execution may not be advisable.

Q3: Novelty: two other works generate PDDL domain and problem without human intervention.

We thank the reviewer for bringing our attention to these very recent related works, and will add citations to our paper. However, these two papers do not really change the fact that our work is the first work to generate both domain and problem PDDLs end-to-end without human intervention. To elaborate, (1) the work of Oswald et al. despite generating domain PDDL from natural language and proposing heuristics for PDDL action domain comparison, differs in two significant ways: first, they assume the predicates are given, which is a too relaxing assumption, second, their work does not directly translate problem and uses the ground-truth problem PDDL instance for comparing the compatibility of two domains. (2) the work of Stein et al. is focused on translating PDDL to natural language, which is the opposite of what we seek to achieve: translating natural language to PDDL.

Q4: What does 66% solve rate what does it mean? What does 7 out of 10 domains solved mean?

66% solve rate means that out of 100 tasks (10 problems for each of the 10 environments), 66 of them were solved by finding a correct plan. Note that a task will be solved iff both problem and domain are translated successfully. We observe that despite the translation of the domain being completely successful, sometimes the LLM makes minor mistakes in translating one or more of the 10 problems of the same domain. As such, we consider a domain to be solved if more than 50% of its tasks are solved correctly.

Q5: Clarify the need for ground truth PDDL. What if the PDDL environment is not known or given?

We thank the reviewer for noting the potential of our framework for general planning problems that do not have a PDDL environment. As we have noted the potential applicability in section 4.1, we leave the extension to future work. Automatically generating pddl problem and domains without human intervention is a challenging enough problem that we will have to address these other questions in future work. We use the ground-truth PDDLs only to retrieve the list of possible actions, and their applicability, compatible with our Assumption 1. Hence, our framework, by design, is agnostic to the underlying environment. Therefore, as long as the action interface is expressible in PDDL, and Assumptions 1and 2 are met, our method is applicable to the underlying environment.

Q6: How do you know when to stop refinement?

Following prior works on code generation [2, 3], we set a maximum of $c_{max}=4$ conversation turns in our experiments. That said, if the exploration walk metric is 1.0 and the task in hand is solved, we stop early and do not continue the refinement.

Q7: In algorithm 1, how many times a LLM model should be called? What is the cost associated with that as well beyond the token size?

For the P&D method with variables $n_p$ problem samples, $n_d$ domain samples, and $c_{max}$ conversation turns, the language model is called $n_p n_d c_{max}$ times, which in our experiments is $5 \times 10 \times 4 = 200$ times. Computing the EW metric for each domain-problem pair takes less than two minutes on a 64-core Server CPU.

Q9: Regarding planning error, what about unsolvable instances?

We consider any unsolvable instance as a part of a planning error. In general, a planning error means that there exists no plan that achieves the desired goal from the initial state, whether it is domain-problem incompatibility or unsolvability.

Q10: Do you generate multiple problem instances and refine the domain multiple times?

For each generated problem, we run a fresh instance of domain refinement. As a part of problem translation, some predicates will be generated, as such, the generated domain should also conform the the defined predicates, and should be generated from scratch.

[1] Guan et al., Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning, NeurIPS 2023.

[2] Madaan et al., “SELF-REFINE: Iterative Refinement with Self-Feedback”

[3] Chen et al., Teaching Large Language Models to Self-Debug, ICLR 2024

Can you please point to where you discuss computational complexity and soundness and completeness of your approach?

I would say that the notion of human intervention can be interpreted in multiple ways: no human, human before the LLM call, human in the loop (after LLM call), etc. I would be good to distinguish your work in one of these. The related work has as you point out the assumption of predicates, but that does not mean humans are in the loop while LLM is being called, right?

I am still not convinced regarding the generality of the work given the current assumptions (need for the environment, etc).

We thank the reviewer for the feedback. However, we respectfully disagree with the criticisms around our core contributions and problem setup, as we believe there are misunderstandings about our work.

The reviewer seems to believe that we only use the scalar feedback provided by the EW score and that the latter is insufficient. However, the scalar EW metric is only used to pick the best response from the LLM, and the textual feedback (as explained in Figure 2 and Appendix B.3) consists of the incorrect set of actions and a textual description of the last state. Please see the attached rebuttal pdf in the overall response for the exact form of feedback.

The second group of criticism appears to try to redefine the problem that we set out to solve and concludes that our solution misaligns as a result. However, our goal is toward fully automatic planning in very complex problems from natural language description. To this end, all challenges surrounding automatic PDDL generation need to be resolved, including but not limited to the predicate identification problem raised by the reviewer, and we have made substantial progress in the overall problem, as evidenced by the benchmark results.

We provide additional responses to each point raised by the reviewer below:

W1 about core contributions: EW does not provide a sufficient objective, the objective in Equation (1) should be the one to optimize to produce a valid domain.

We agree that the final objective is Eq (1); however, this equation is not easy to optimize. We should note that it is common practice in machine learning to optimize a proxy objective instead when the primary objective is not easy to optimize. For instance, optimizing the cross-entropy loss as a proxy for accuracy or optimizing the L1 loss function as a proxy for sparsity. We believe the EW score serves a similar purpose as a proxy for Equation (1), which is hard to optimize.

W2 about core contributions: The exact feedback is not explained enough

We will add an example of feedback for the Termes environment to our paper. Please see the attached rebuttal page for the example.

W3 about core contributions: The scalar provides little feedback.

Please see the comment at the beginning of this response.

Weakness about problem setup: This setup is fundamentally different from what the problem of "generating PDDL" should be. The difficulty is to identify important predicates. Once the predicates are ready, the precondition & effect terms and initial & goal states should be relatively simple to be translated with GPT-4 with some prompt engineering.

Our goal is toward fully automatic planning in very complex problems from natural language description. To this end, all challenges surrounding automatic PDDL generation need to be resolved, and we have made substantial progress in the overall direction, as evidenced by the benchmark results. We appreciate the reviewer's acknowledgment of the challenge in identifying important predicates, which we did target in this work. However, we would like to emphasize that determining the correct preconditions and effects is also more complex than it might seem. Our observations indicate that GPT-4 sometimes misses preconditions or effects. For instance, as shown in the attached rebuttal PDF, the LLM corrected an action's precondition only after receiving feedback from the environment about the action's illegality. We also note that the level of description in our setting is similar to that of prior works (e.g., [1]). Overall, we are excited to see future extensions of our work that rely more on environment interaction and less (or not at all) on natural language descriptions. Our work lays the groundwork for achieving this goal.

Responses to questions

Q: What is $c_max$ in Algorithm 1? If it is the refinement iterations, how many iterations are used in the paper?

It is the maximum number of refinement iterations (or conversation turns). Following prior works on code generation [2, 3], we set a maximum of $c_{max}=4$ in our experiments.

Q: In experiments, the method runs 4 times and the best result is used for evaluation. I'm curious what the statistics of the 4 runs look like. Does a "magical seed" lead to good results while the others fail?

We did not “optimize for the random seed” if the question hints at it. Furthermore, in a realistic setting, it is perfectly reasonable to try a few times and use the EW score to decide the final solution, as that only relies on environment feedback. Furthermore, the Best@4 metric is similar to the Pass@K metric, which is commonly used in code generation literature (e.g., [3, 4]).

As for the statistics, it depends on the environment. For example, on Termes, all four seeds succeed in recovering the correct domain. On Grippers, three seeds succeed. On harder environments, such as hiking, two seeds succeed in recovering the correct domain PDDL, and Floortile only one seed succeeds.

Q: The language descriptions are generated by a GPT-4 from ground-truth PDDL files. I will expect there might be missing items or hullicination. I wonder, do you manually check and fix the generated outputs?

We did manually check for hallucination, and observed that the hallucination cases for back-translation are very rare, though not zero, and fixed the cases that we detected. We will publicly release the data along with the camera-ready version of our paper.

Note that this manual checking for hallucination is only for creating the natural language description dataset for the problem setup. For automatic PDDL generation, there is no human in the loop.

[1] Liu et al., LLM+P: “Empowering Large Language Models with Optimal Planning Proficiency”, 2023

[2] Madaan et al., “SELF-REFINE: Iterative Refinement with Self-Feedback”

[3] Chen et al., Teaching Large Language Models to Self-Debug, ICLR 2024

[4] Chen et al., Evaluating Large Language Models Trained on Code, 2021

We thank the reviewer for their positive comments. Below, we address the main questions raised by the reviewer:

W1: The domain model sampling/generation is done in a relatively simple way. The feedback message could be more informative than just indicating the inexecutable step or action in a plan.

Respectfully, our perspective here differs. The simplicity of our feedback messages is a deliberate choice to showcase the general applicability of our framework. As we improved the solve rate from 29% to 66% with a simple variant of our framework, it shows the impact of the core idea of the framework and a path forward for future innovation. More detailed feedback messages can be useful for future direction among other possibilities enabled by our approach.

W2: Regarding the structure of the related work section, the distinction between "intrinsic reasoning" and "external reasoning" seems unclear to me, especially given that "with the assistance of basic external tools [14]" is mentioned under the "intrinsic reasoning" subsection. Also, even for the task of PDDL generation, certain degree of "intrinsic reasoning" is needed. Rather than saying "intrinsic reasoning", I guess the authors likely meant "direct plan generation."

We appreciate the reviewer's feedback on the structure of the related work section. To clarify, we will replace the term "intrinsic reasoning" with "direct reasoning." This should better capture the distinction we intended to make between different types of reasoning approaches in our study.

W3: Are LLMs used as knowledge sources or translators?

The LLMs are mainly used as translators, however, some elementary general knowledge and reasoning are required for the LLM to be able to come up with correct predicates and preconditions/effects.

W4: While the EM score may be effective for selecting candidate domain models and guiding their generation, its suitability as an evaluation metric is questionable. We know there exists a "ground-truth" PDDL and our goal is to fully recover its functionality. This is a binary 0/1 problem. This is not like a generated model with 0.8 avg solve rate is more usable than a model with 0.2 avg solve rate.

While achieving exact functionality with ground-truth PDDL is ideal, this is often unattainable in hard domain PDDLs, resulting in incompatible output plans (and consequently functionally inequivalent PDDL domains). Therefore, a proxy metric is essential for meaningful comparison. Such proxy metrics are crucial in comparing different models and understanding trends that would have been unpredictable through the primary metric [5]. In Section 4.2, we demonstrate that the EW metric is a suitable proxy for our setting.

W5: It's important to mention that the avg solve rate can only serve as an approximate measure of the equivalency between two domain models. A 100% avg. solve rate doesn't guarantee model equivalency (but this seems to be an easier-to-compute measure)

We will add a sentence to clarify complete task solve rate does not mean exact domain equivalency. However, we should note that it is common practice to test a generated PDDL code using task solve rate (e.g., [1], [2]). More generally, the majority of code generation literature (e.g., Codex [2], AlphaCode [3]) tests the generated Python, or C++ code using unit test cases and decides the final accuracy based on performance on test cases.

W6: Assumption 2 is stated in a loose way. An NL description of a domain can be given at different degrees of detail (which correspond to different levels of difficulty in domain PDDL generation).

This assumption is a part of the input to our framework., The amount of details provided only changes the accuracy, and not the framework itself. Our natural language descriptions maintain a degree of detail comparable to previous works (e.g., [1]). Studying the trade-off between the amount of detail in natural language and accuracy is an interesting area for future work.

W7: Line 211: I think it's better to say "as long as PDDL is expressive enough to capture the dynamic / working mechanisms of the environment" rather than "the env supports PDDL action interface."

Thank you for your constructive feedback. We will change this line as suggested by the reviewer.

W8: It's unclear what the takeaway of Sec. 4.2 should be. Firstly, "plan-not-found" only accounts for a certain fraction of consequences caused by removing a term or predicate. Other consequences, such as producing invalid plans, can also occur. Secondly, it is well known that obtaining a valid domain model is challenging, even for humans. The authors should better explain the connection between Sec. 4.2 and the other parts of the paper.

Section 4.2 aims to convey the message that even the smallest divergence from the actual domain PDDL leads to no plan being found, let alone the plan being valid. This sensitivity is a significant motivation for our shift from traditional plan search approaches to the introduction of the exploration walk mechanism

W9: The authors should give more information on the computational complexity/cost (e.g., time consumption) associated with the calculation of EW score per candidate model.

Computing the EW is relatively negligible compared to the cost of LLM inference. In our experiments, computing the EW score for a single domain-problem pair takes less than two minutes on a 64-core server CPU. We will add this information to our paper.

[1] Liu et al., LLM+P: Empowering Large Language Models with Optimal Planning Proficiency, 2023

[2] Guan et al., Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning, NeurIPS 2023.

[3] Chen et al., Evaluating Large Language Models Trained on Code, 2021

[4] Li et al., Competition-Level Code Generation with AlphaCode, 2022

[5] Schaeffer et al., Are Emergent Abilities of Large Language Models a Mirage?, Neurips 2023

We thank the reviewer for their positive comments. Below, we respond to the weaknesses and questions raised by the reviewer.

W1: Section 4.2 - demonstration of the brittleness of PDDL generation can be made more realistic such as additionally including hallucinated object identifiers or actions or symbols, which are highly probable with LLM-based code format generators.

We already have a qualitative demonstration of the brittleness of PDDL generation in Appendix A.2, where we show a real (common) example where the LLM makes a subtle error in predicate design, and as such, the whole domain produces invalid plans. This is in addition to the quantitive metrics shown in Section 4.2. We will update the writing to highlight this result more.

W2: The PDDL generation with LLMs approach is not as novel and the exploration walk/environment feedback approach may not be as useful in generating completely new domains from descriptions or making custom modifications to existing domain files. The method does not really differ for rectifying problem files.

PDDL generation is not novel, and we do not claim it to be our contribution. We should emphasize that the main contribution of our work is to provide a framework to eliminate the need for human feedback to generate PDDL domains and problems and put the first steps towards such automation. We are certainly excited to see extensions of our method to “custom domain modification”, or an exploration-walk-like metric for PDDL problem files, but we believe these are out of the current scope and are interesting directions for future research.

W3: There are intrinsic problems with generating domain files from descriptions for domains such as Barman - where the levels of shaker and actions such as clean shot, empty shot do not translate well for LLM-based generation. More analysis and description in this line of argument are necessary.

Indeed predicate design is a crucial part of LLM-based generation, and we already have qualitative analysis for the Grippers environment in Appendix A.2. We observe similar challenges happening in the Barman environment, and kept the Grippers environment example since the environment is simple enough to be illustrative throughout the paper. As per the suggestion of the reviewer, we will add the Barman example to Appendix A.2 for more comprehensiveness.

Q1: This work on generating programs for planning problems [https://arxiv.org/abs/2305.11014] may also need to be cited in related work.

We have already cited and discussed this work in our related work section.

Q2: The authors may benefit from more sophisticated exploration approaches in this paper [https://arxiv.org/abs/2406.07145] that solve a different problem.

We thank the reviewer for pointing out this work. There is a literature on exploration strategies and we will add citations to some papers in that literature including the one mentioned by the reviewer, but the method itself in this suggested reference is for a very different problem. Adaptation to our problem would be highly non-trivial and could warrant a new research effort.

Additionally, we should stress two points: 1) as we have well-established through empirical results on 10 domains, our current simple EW already works. 2) our approach is a general framework, and components in the current implementation can be improved in future work.