Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming

FxuD-Q4: Theoretical insights regarding performance

FxuD-A4: Our insight is that LLMs are good at understanding the syntax and semantics of planning problems as optimization problems but are not good at solving optimization problems directly. Specifically,

Next-token prediction is fundamentally different from deterministic algorithms for optimization. There’s a growing belief that next token prediction cannot truly model human thought and cannot support human-like capabilities of understanding a problem, imagining, curating, and backtracking plans before executing [1-3]. Specifically, the claim that next token predictions are “ill-suited for planning tasks” is supported by works [4-7], which tested the planning capabilities of LLMs on various planning tasks. These works empirically show that in addition to identifying patterns in language and predicting the next word in a sequence, LLMs still can not truly understand a problem and thus do not have the capability to perform intense calculations to optimize for any objectives. Thus, this is a major reason why baselines are not capable of solving the complex planning problems in our paper. However, since LLMFP teaches LLMs to build the optimization problem step by step and calls the external solver to solve for a plan, this bypasses the need to devise a plan by LLMs themselves.

LLMs cannot understand and solve an optimization problem. To support this claim, we conduct an experiment on the Coffee task that, instead of using natural language task descriptions as inputs, we directly map this Coffee task to an optimization problem and use the formal mathematical definition (refer to page 16 for the detailed formal definnition) of this problem as the inputs to LLMs. Thus, LLMs do not need to understand the problem and find the underlying constraints, as a formal definition is given and could be directly solved.

We tested Direct with the most powerful LLM OpenAI o1-preview model on all queries of Coffee, which only achieves an optimal rate of 34.2%. Compared to its 25.9% optimal rate with natural language task description, this is not a significant improvement, given all goals and constraints are clearly formally specified in the new setting. This is consistent with the conclusion that LLMs still cannot solve optimization problems by themselves, even given a formal representation. LLMFP enables LLMs to formalize planning problems as optimization problems. Since SMT solvers can guarantee to return correct answers given correct input, the high optimal and success rate of LLMFP indicates that LLMFP allows LLM to parse the correct syntax and semantics information of a planning problem from its natural language description to a formal mathematical description. Such translation is also non-trivial when no task-specific examples are provided. As shown in our newly added baseline approach Code_SMT as shown in Table 1 and 2, when we directly ask LLMs to translate and encode the natural language task description in an SMT format, the optimal rate is low, with an average of 2.7% and 62.4% for multi-constraint tasks, and 1.0% and 0.0% for multi-step tasks across two LLMs GPT-4o and Claude 3.5 Sonnet.

We thank the reviewer for the valuable comments and suggestions! We provide some clarifications, discussions, and experiments regarding the weakness and questions proposed by the reviewer, and experiments suggested by other reviewers (Please see the Revision Summary). We also updated a revised draft and colored the modifications/additional discussions with blue.

FxuD-Q1: Complexity in FORMULATOR

FxuD-A1: Thanks for the suggestion. We have rewritten the FORMULATOR section. In particular,

• We rewrote the first two paragraphs with a clearer way of introducing the JSON representation and field.
• We cut down the paragraph Single-Step Multi-Constraint Problem to make it less dense for the readers.

Please refer to our updated draft. All the changes are highlighted in blue.

FxuD-Q2: Unclear presentation in ‘Multi-Step Planning Problem’ section

FxuD-A2: Thanks for the suggestion. We have modified the ‘Multi-Step Planning Problem’ section. In particular,

• We rewrote the start of the paragraph with a clearer explanation of what different stages mean, and disambiguated them from the fields.
• We replaced Figure 2 with two clear, to-the-point examples of the JSON representation. Figure 2 can now better assist the explanation.

Please refer to our updated draft. All the changes are highlighted in blue.

FxuD-Q3: The statement ‘Our approach does not require task-specific examples or task-specific efforts’ is not supported

FxuD-A3: We would like to clarify that the only task-specific information is the user description of the planning problem and the user’s question (i.e., lines 188-196). This is the minimum information needed to define and understand the planning problem.

Other than that, all the prompts for different modules are task-agnostic, i.e. the same prompt works for all planning problems. To emphasize this, we added sentences like ‘which is task-agnostic’ or ‘which is invariant across tasks’. It is worth emphasizing that although our prompts include in-context examples, those examples are from a fixed task that is unrelated to the target task. In our implementation, we used examples from travel salesman, object selection, and logistics problems, which do not belong to any planning task we evaluate. Please refer to the detailed prompts listed in A.10. Those are the prompts that are fixed for all the different planning tasks.

dysu-Q7: Success rates of tested methods? Do they all achieve 100%?

dysu-A7: We thank the reviewer for the suggestion to include success rates as another metric for evaluation. We include the success rates of all methods in the tables below and also in Appendix A.3.

Note that although the optimization goal is described in the task description for multi-constraint problems, we exclude the optimization goal when calculating the success rate and only evaluate whether the plan fulfills the task setup and the query. This would largely decrease the difficulty of multi-constraint problems for baseline methods. For example, even assigning all tasks to one robot is considered a success for the task allocation task. Thus, the success rates of all baselines for multi-constraint problems are significantly higher than the optimal rates. However, the success rates of LLMFP almost remain the same as optimal rates since the SMT solver guarantees to output the optimal result with the correct encoding. Even when compared in such an unfair way, the performance of LLMFP still outperforms other baselines, with an average of 86.4%, 18.1% higher than the best baseline.

While for the multi-step problems, considering all initial conditions, predicate and action definitions, and goals are the same, developing a reasonable and correct plan is not significantly easier than developing an optimal plan with the least number of steps. Thus, the success rates of baselines are improved, but not significantly, compared to the optimal rates.

Table 8: Success rate (%) comparison of LLMFP with baselines on 5 multi-constraint problems.

Table 9: Success rate (%) comparison of LLMFP with baselines on 4 multi-step problems.

[1] Li, Beibin, et al. "Large language models for supply chain optimization." arXiv preprint arXiv:2307.03875 (2023).

[2] Gupta, Naresh, and Dana S. Nau. "On the complexity of blocks-world planning." Artificial intelligence 56.2-3 (1992): 223-254.

dysu-Q3: Time and cost comparison of baselines and LLMFP

dysu-A3: In Appendix A.4 we included the time and cost analysis for LLMFP. As the reviewer suggested, we add time and cost comparisons for all methods.

The following tables show the wall time comparison of all methods for GPT-4o on 9 tasks (also in Appendix A.4). From the results, we observe that the time taken for LLMFP, although longer than most of the baselines, is within a reasonable range. Especially for multi-constraint problems, it is shorter than Direct with o1-preview because of the inherent difficulty for LLMs to solve these combinatorial optimization problems.

Table 2: Average wall time (s) per query comparison for 5 multi-constraint problems with GPT-4o.

Table 3: Average wall time (s) per query comparison for 4 multi-step problems with GPT-4o.

The table below shows the average cost comparison of all methods on the coffee task. We observe that although LLMFP is more costly than most of the baselines, it is cheaper than Direct with o1-preview with better performance. In addition, the average cost per query for all 9 tasks is around 0.1 dollars, indicating LLMFP is not very costly.

Table 4: Average cost ($) per query comparison of LLMFP on the Coffee task.

We thank the reviewer for the constructive comments and helpful feedback! We are pleased to see that the reviewer appreciates the idea, approach, and presentation of LLMFP. You brought up some great questions and suggestions which have helped improve our work. We have added more experiments and discussions to address the concerns of the reviewer. We also updated a revised draft and colored the modifications/additional results and discussions with blue.

To summarize:

• We added experiments on Sokoban tasks for 15 queries
  • LLMFP achieves optimal rates of 80%, outperforming all baselines
• We added a baseline Code_SMT that is forced to use SMT for code generation for all tasks and LLMs
  • LLMFP outperforms Code_SMT, which achieves an average of 2.7% and 62.4% for multi-constraint tasks, and 1.0% and 0.0% for multi-step tasks across two LLMs GPT-4o and Claude 3.5 Sonnet
• We provide results with success rate as the metric across all 9 tasks and for both LLMs
  • LLMFP still outperforms the baselines
• We added experiments that explicitly instruct baselines to output optimal solutions for multi-step problems
  • LLMFP still outperforms the baselines
• We added wall time comparison and cost comparison
  • LLMFP runtime and cost are reasonable, comparable to using o1-preview
• We added complexity analysis and failure cases analysis
  • All multi-constraint tasks, Blocksworld, and Mystery Blocksworld are proved to be NP-Hard

Detailed response:

dysu-Q1: The complexity of planning problems

dysu-A1: We thank the reviewer for bringing up the discussion about the complexity of our planning problems. We include a more detailed complexity discussion and put it in Appendix A.1. In short, many of the tasks we experimented on are NP-hard problems. In particular -

• For 5 multi-constraint problems, they are all NP-hard problems. Specifically,

  • We use the benchmark from [1] for the first 3 problems (Coffee, Workforce, and Facility), in which these 3 problems are built as Mixed-integer linear programming (MILP) problems. Please refer to Appendix A.1 for the formal optimization problem definition example. As MILP is known to be NP-hard, the first 3 problems are NP-hard.
  • For the Task Allocation problem, since it is equivalent to a multi-agent traveling salesman problem(agent=robots, tasks=cities), it reduces from the classic traveling salesman problem (TSP) and thus is also NP-hard.
  • For the Warehouse problem, as TSP is a special case when one station can be used to finish one specific task, and there are no extra stations, the Warehouse problem is at least as complex as TSP and, thus, is also NP-hard.

• For multi-step problems, Blocksworld has proved to be an NP-hard problem [2], and the same is true for Mystery Blocksworld, as it is the same problem with obfuscated names. Although there is no existing proof to be NP-hard problems, Movie has 13 predicates and 9 possible actions, and Gripper has 4 types of objects (rooms, objects, robots, grippers), 4 predicates, and 3 possible actions. These show that they are not simple straightforward tasks.

dysu-Q2: More complex multi-step problem - Sokoban

dysu-A2: As the reviewer suggested, we tested LLMFP on the Sokoban environment. Due to the time limitations, we created a pilot evaluation set containing 15 queries describing the game setup and goals with different map sizes and number of boxes. We have five queries with 5x5 maps and 1 box, five queries with 6x6 maps and 1 box, and five queries with 5x5 maps and 2 boxes. The evaluation results are presented in the following table.

Table 1: Optimal rate (%) comparison of LLMFP with baselines on Sokoban problem

As can be observed, LLMFP achieves a success rate of 80%, outperforming the baselines. The new results, along with other problems, showcase the potential of LLMFP to solve complex problems. We will keep working on expanding our query set and will add the full results to our paper.

We added this result in Appendix A.1 LLMFP Performance on Sokoban of the revised paper, as well as the discussion of failure mode. Please refer to the revision page 16 for detailed discussions.

We thank the reviewer for comments and suggestions! We provide some clarifications and discussions regarding the weakness and questions proposed by the reviewer, and experiments suggested by other reviewers (Please see the Revision Summary). We also updated a revised draft and colored the modifications/additional discussions with blue.

8M6X-Q1: Baselines of LLMFP

8M6X-A1: The baselines for comparisons in our paper are fair comparisons in that they have the same inputs and are all zero-shot methods with no task-specific examples. To the best of our knowledge, LLMFP is the first general-purpose planning framework that requires no task specific examples or external critics. We were not able to locate other frameworks/architectures that provide such a fair comparison to LLMFP at the time of submitting the paper.

Regarding the three papers -

• We have added the three papers mentioned by the reviewer to the Related Works section as they are relevant LLMs for Planning papers.
• However, these papers are not comparable to our framework LLMFP. This is because we focus on the setting where we do not have task-specific examples, external humans/verifiers/critics, whereas [1-3] require either domain-specific examples or feedback from real humans. Specifically, [1] requires task-specific in-context examples, [2] requires a Memory that is filled with 25 solved problems, and [3] is interactive and user-guided, which needs a real human person capable of validating the code.
• We noticed that [1] recently submitted another version to ArXiv after the ICLR submission deadline, which added a new experiment that investigated a zero-shot version of their method, MAP, on one multi-step task, Mystery Blocksworld, and showed that MAP could solve 8.2% of the problems. Meanwhile, LLMFP could achieve 77.7% and 98.0% optimal rates for GPT-4o and Claude 3.5 Sonnet. The comparison of the performance results further proves the effectiveness of our paper, which significantly outperformed the zero-shot MAP.

8M6X-Q2: Are LLMs hallucinate or overuse APIs?

8M6X-A2: We do observe some hallucinations and misuse of the APIs. For example,

• We provide a Max(variable_list) function to LLMs for the task allocation task. Although the input is a list of variables, LLMs sometimes input multiple variables separately and use it like Max(variable_1, variable_2,...). This phenomenon would result in runtime errors and can be corrected during later iterations.
• As we discussed in Appendix A.4.5, LLMFP Failure Case Analysis, the major failure case for Warehouse is: Code Generator overwrites the provided API get_distance and provides 1 as the output. Thus, the distance between each station is mistakenly set to be 1. Although we do not provide a fix for this issue in our paper, it is easy to locate and correct this type of issue by adding a checker to check for repeated initialization of functions.

Despite these hallucinations and misuse of APIs, they are sporadic and LLMFP still significantly outperforms all baselines.

qLBs-Q5: Why does Encoding to PDDL requires more human efforts than LLMFP

qLBs-A5: We would like to clarify that we do not mean encoding to PDDL inherently requires more human effort than encoding to SMT. Instead, existing methods using LLM+PDDL need human efforts [1-5]. Specifically, [1,3,4] needs task-specific in-context examples, [2] needs human corrections from experts, and [1,5] needs an existing PDDL domain file. We listed a comprehensive set of papers in the related work session and discussed their major differences from LLMFP.

qLBs-Q6: How do you encode the length of the plan?

qLBs-A6:

• For multi-constraint problems such as Coffee, Workforce, Facility, Task_allocation, and Warehouse, since they are inherently combinatorial optimization problems, it is encoded as a single-step problem.
• For multi-step problems such as Blocksworld, Mystery Blocksworld, Movie, and Gripper, we do not give LLMFP a fixed horizon. Instead, we use interactive deepening. The solver starts from timestep=1 to check satisfaction. If the solver finds a satisfiable solution for a given timestep, it is guaranteed to be the optimal solution; if the solver finds no solution given a timestep, it adds one more step and repeats the process. This process is repeated until reaching a predefined limit set by us.

The requirement predefined limit is a shortcoming of the SMT solver. In the future, we would love to extend our work to explore methods that could help mitigate the runtime issue for large-scale problems. Some possible directions are: 1) introducing methods to estimate the lower and upper bounds of step numbers needed, 2) developing heuristics to prioritize some possible options first, and 3) developing methods that put attention on a part of the map and ignore the unnecessary positions in the map. In addition, one advantage of the LLMFP is that it can work with different solvers. Thus, we will also explore other solver options for long-horizon tasks.

[1] Liu, Bo, et al. "Llm+ p: Empowering large language models with optimal planning proficiency." arXiv preprint arXiv:2304.11477 (2023).

[2] Guan, Lin, et al. "Leveraging pre-trained large language models to construct and utilize world models for model-based task planning." Advances in Neural Information Processing Systems 36 (2023): 79081-79094.

[3] ISR-LLM: Iterative Self-Refined Large Language Model for Long-Horizon Sequential Task Planning.

[4] Xie, Yaqi, et al. "Translating natural language to planning goals with large-language models." arXiv preprint arXiv:2302.05128 (2023).

[5] Silver, Tom, et al. "Generalized planning in pddl domains with pretrained large language models." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 18. 2024.

[6] Gundawar, Atharva, et al. "Robust Planning with LLM-Modulo Framework: Case Study in Travel Planning." arXiv preprint arXiv:2405.20625 (2024).

qLBs-Q4: LLMs have been used to translate natural language to planning problems. Similarly, the mapping from planning to SMT is well known in the planning literature. So, is the novelty limited to combining the two ideas together?

qLBs-A4: We argue that LLMFP is more than translating natural language to planning problems. Specifically,

• Simply translating from natural language to planning problems and using SMT solvers does not work. We added a new baseline approach Code_SMT, where we directly ask LLMs to translate and encode the natural language task description as a planning problem in SMT format and use SMT solvers to solve the problem. Code_SMT achieves an average of 2.7% and 62.4% for multi-constraint tasks, and 1.0% and 0.0% for multi-step tasks across two LLMs GPT-4o and Claude 3.5 Sonnet.
• Existing works using LLMs as translators need task-specific examples. As we mentioned in the paper, [1,4,6] leverages LLMs as translators to convert problems into fixed formats(like PDDL or JSON) and input them to external planners. They accomplish this by giving LLMs example input-output pairs under the same contexts and leveraging LLMs as pure translators.
• LLMFP is a framework that enables LLM agents to understand and formalize planning problems from natural language descriptions. When given a planning problem in natural language description, a planning researcher or engineer will formalize the natural language description as a formal optimization problem, and then use appropriate solvers to solve it. LLMFP framework enables LLM agents to act as expert planning engineers. Without any task-specific examples, LLMFP starts from understanding and analyzing the problem to generate valid goals, decision variables, and (explicit & implicit) constraints. Then, it summarizes all needed variables and necessary related information, again with no task-specific reference. This process is non-trivial and is the key to enabling LLMs to solve problems across various inherently different tasks in a zero-shot setting.

Table 1: Optimal rate (%) comparison of LLMFP with baselines on 5 multi-constraint problems.

Table 2: Optimal rate (%) comparison of LLMFP with baselines on 4 multi-step problems.

We thank the reviewer for the constructive comments and helpful feedback! You brought up some great questions and suggestions, which have helped improve our work. We have added additional experiments to show that the PDDL-based approach cannot solve some planning problems we consider in this paper, and experiments suggested by other reviewers (Please see the Revision Summary). We address the reviewer's concerns below. We also updated a revised draft and colored the modifications/additional results and discussions with blue.

qLBs-Q1: Novelty of the proposed work over the PDDL-based approach

qLBs-A1: Our framework is the first of its kind to perform zero-shot planning from natural language description across various domains. We argue that the existing approaches, including the PDDL-based approach, are not sufficient to solve the problem we consider in this paper. Specifically,

• Existing PDDL-based approaches rely on task-specific efforts. Our LLMFP framework does not need any task-specific examples or human inputs. However, current PDDL-based approaches depend either on task-specific in-context examples[1,3,4], existing PDDL domain files[1,5], or human corrections[2]. These all limit their cross-task generalization capabilities.

• PDDL-based approaches cannot handle general planning problems. Even if the task-specific efforts in the existing PDDL-based approaches can be omitted in the future version of LLMs, the fact that PDDL planners need domain and problem files limits their applicability to non-PDDL problems that we consider in this paper. For example, the multi-constraint problems, such as the Coffee task in our paper, cannot be solved using PDDL-based planners in a zero-shot way. Specifically, the Coffee task’s goal is to develop plans that satisfy retail location demands considering supplier capacities with minimized total cost. The definition of actions, as needed in the PDDL domain file, is not clear and straightforward. We slightly modified the prompts from [1], a work that uses LLMs to generate PDDL domain files, to generate actions and their preconditions and effects for the Coffee task, given only the description of the natural language task (same setting as LLMFP). The method in [1] cannot generate reasonable action definitions. One representative failure mode is:

  • Action 1: Source Beans from Supplier
  • Action: This action enables the company to source a unit of coffee beans from a supplier.
  • Parameters:
    1. ?s - supplier: the supplier from which to source beans
    2. ?f - facility: the facility to which the beans are shipped
  • Preconditions: (and (supplier-has-capacity ?s) (facility-can-receive ?f))
  • Effects: (and (not (supplier-has-capacity ?s)) (facility-has-beans ?f))
    • Failure reason: This action sources only one unit of coffee beans, but the effects mean the supplier would not have any capacity after the action, which does not take the number of coffee beans capacity of suppliers into consideration.

  Other than this, actions are also not defined comprehensively. For example, from the output, we observe that only “Ship Dark Coffee to Retail Location” is defined, but shipping light coffee is not considered.

  These results show the generation of PDDL domain files is not straightforward for non-PDDL problems, which limits PDDL-based approaches’ applicability. Even for PDDL problems, no existing PDDL-based approach can plan PDDL problems in a zero-shot way without PDDL domain files or human corrections. However, LLMFP is able to handle diverse sets of problems, including multi-constraint problems and multi-step problems without task-specific examples, as shown in Table 1 and 2 in the paper.

• LLMFP can use any solvers. Although we use SMT as the solver in this work, LLMFP can be adapted to any planner or solver by updating the requirements and representation format in the prompts. We already included an example in Appendix A.7.3 in the original paper, where prompts can be easily modified to support using MILP. We would love to extend our work to support more solvers or even multiple solvers at the same time. In fact, we believe that each solver has its own specialized types of problems. Our future research plan is to equip LLMs with various solvers and allow LLMs to select preferred solvers or planners automatically.