On the Roles of LLMs in Planning: Embedding LLMs into Planning Graphs

Summary

This work creates a hybrid LLM and classic planning algorithm, by integrating a LLM into the GraphPlan algorithm. The GraphPlan is an algorithm that solves a relaxed planning problem (forward expansion), and then traverses the created graph to find a valid plan (backtracking). Both steps are expensive. In the hybrid approach, a LLM is prompted in the forward expansion to limit the exploration of states deemed irrelevant. In the backtracking phase, the LLM is used to sort actions to explore first. Experiments with corrupted domain files show that LLMs can better handle corruption than the GraphPlan algorithm.

Strengths

- A very interesting novel idea of a hybrid planning approach with a fundamental classic planning algorithm. - The paper provides an introduction to an interesting research area of classical planning (e.g., Figure 4).

Weaknesses

- Multiple missing experiments and discussions severely undermine the results of the paper. - It is not clearly motivated why experiments with corrupted pddl domain files are interesting. This was introduced quite suddenly in the *results section* (lines 261-262) without enough details and without providing motivation. - The paper is missing important discussion and experiments about the trade-off between the hybrid approach and the classic GP algorithm. Experiments with valid pddl domain files are not included, which could have alleviate it. - The effect of hyperparameters on the results, such as the number of iterations (N) in Algorithm 1, is not discussed. - The failure of LLMs4PLAN-GPT3.5 compared to the phenomenal success of LLMs4Plan-GPT4 is somewhat unexpected and undermines the results of the paper. - Multiple details are missing regarding the experimental setups. (see questions below) - The paper's writing needs to be improved. (see suggestions below)

Questions

**Suggestions** - Most importantly, I would like to see experiments with valid pddl files. While the GP algorithm would receive 100% success rate, I expected to see a graph of success rate (y-axis) compared to the number of nodes explored (x-axis). Such a graph would describe **a trade-off** between statistically using a LLM and using an exhaustive algorithm, such as GraphPlan. - It is possible that this is included in Table 3, but I don't understand if it includes the corrupted domain files. A graph which includes success rate would be clearer. - Clearly describe and motivate the pddl data corruption in the experimental setup. - Writing - While I happen to be well-versed with the GRAPHPLAN algorithm, I am not sure that enough introduction has been provided, as it is only briefly mentioned in lines 44 and 67. - “3 Our LLMs4Plan approach” does not properly introduce the algorithm before discussing it. Notations, such as N, are not defined. Terms, such as planning graphs and mutual constraints, are used but not explained until reading 3.1 and 3.2. Concepts, such as pruning, should be formally introduced before discussing “pruning possibility” (line 109). - subsection 3.2: - this subsection is not part of your algorithm, but part of graphplan. related to my previous notes, I think this should not be in section 3, but properly explained earlier. - add citations to support the mutual exclusion constraints names (i.e., inconsistent effects, interference, competing needs). - subsection 4.3. writing could be improved. I was initially confused about the location of the ablation results table. **Questions** - Data corruption of pddl domain files: Please provide details about the corruption, such as % files corrupted. It seems that this is a very high percentage, if this is the main reason that the GP method gets low resulsts (lines 261-262). - Please provide details about the hyperparameters influence on the results, such as the number of iterations N and the number of layers K. - In Table 2, where we compare “number of nodes required for searching”. Which iteration do we measure? Do we ignore the fact that there could have been multiple iterations before the successful one? - line 189 - “Ten problems are randomly selected for each domain” - from which corpus? - Statistics about the pddl problem files are missing. How long are the plans from initial state to goal?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors did not discuss limitations of their work.

Summary

The paper investigates how large language models (LLMs) can be integrated into established planning frameworks, specifically graph-based planning. The authors propose a novel framework called LLMs4Plan, which incorporates LLMs at two critical stages of the planning process: action selection during graph expansion and candidate action set generation during backtracking. The framework is tested across various planning domains, demonstrating improved efficiency and effectiveness in planning tasks.

Strengths

1. The paper's approach of embedding LLMs into graph-based planning is innovative and contributes to the field of automated planning. 2. The technical implementation of LLMs4Plan is well-detailed, with descriptions of how LLMs are utilized in action selection and candidate set generation. 3. The effectiveness of the proposed framework is empirically validated across ten planning domains, showcasing its practical applicability.

Weaknesses

1. The proposed integration of LLMs into planning frameworks in LLMs4Plan may be complex and difficult to scale. 2. Comparisons with more recent LLM integrated planning baselines is limited.

Questions

1. How does the proposed LLMs4Plan compare with the more recent related work [12] (LLM+P) cited in the paper? And what makes LLMs4Plan a better approach? 2. What potential applications do the authors envision for the LLMs4Plan framework in real-world planning scenarios?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

yes

Summary

There have been debates about the fundamental planning abilities of LLMs in planning tasks. To achieve more reliable performance, several recent works have embedded an LLM into a search framework (e.g., MCTS, BFS) and viewed LLMs as heuristics. Along this line, this work take a closer look at the roles LLMs can play in Planning Graph. It considers two tasks for LLMs: pruning actions and sorting actions (as heuristics).

Strengths

- The paper is well-written, with precise language and formalism. - The experiment is conducted on over 10 domains, making it quite comprehensive.

Weaknesses

1. My biggest concern with this work is that it restricts the use of LLMs to specific roles within a classical planning algorithm. There are many other roles LLMs can play in planning. For instance, see the recent LLM-modulo framework below. Instead of just filtering and ranking actions, LLMs have also been used to evaluate state values or rank plans (i.e., action sequences rather than individual actions). - Kambhampati, Subbarao, et al. "Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks." ICML 2024 2. The evaluation based on the number of nodes explored is partial. We should not ignore the time cost (e.g., latency of calling LLMs) + financial cost of using commercial LLMs. It could be very likely that, although LLM+Graph Planning expands fewer nodes, it may take a longer wall-clock time to give the final outputs. I understand that the evaluation could be tricky and it remains an open question for a while. However, the authors should at least make an attempt to address this. 3. In the abstract, this statement is inaccurate: “works have been proposed to investigate the planning effectiveness of LLMs, without considering any utilization of off-the-shelf planning techniques in LLMs.” There have been quite some paper embedding LLMs in off-the-shelf planning algos - Zhao, Zirui, Wee Sun Lee, and David Hsu. "Large language models as commonsense knowledge for large-scale task planning." NeurIPS 2023. - Yao, Shunyu, et al. "Tree of thoughts: Deliberate problem solving with large language models." NeurIPS 2023. 4. While the corrupted domain model experiment looks interesting, it is unclear what messages it tries to convey. Specifically, why would one run the algo on top of a corrupted domain model when there exists approaches that can leverage LLMs to help complete the domain model before starting the search? - Guan, Lin, et al. "Leveraging pre-trained large language models to construct and utilize world models for model-based task planning." NeurIPS 2023 - Wong, Lionel, et al. "Learning adaptive planning representations with natural language guidance." ICLR 2024. 5. The step of LLM-based action pruning can make the search incomplete, since an LLM may keep ignoring the required action(s) -- in other word, there is no guarantee that the LLM can produce a goal-reaching plan. I notice the authors mention this at a later section (which should be moved to earlier part) that including pruning probabilities could address the problem. I don’t fully agree with this. Can the authors give more detail on how pruning probabilities could guarantee completeness? 6. In the prompt (fig. 3), only the proposition set at the current state is provided. Did the authors consider including the running history of actions (i.e., the partial plan)? Would this affect the overall performance? 7. Line 109: typo in “Algorithm ??” 8. Several works (mentioned earlier) already show that LLMs can be useful heuristics. Can the authors elaborate on the new insights this work provides? ----- Overall, this study provides a thorough evaluation of LLMs within the Planning Graph algorithm. I appreciate the comprehensiveness of the experiments. However, I also have concerns over the scope of this study (i.e., restricting itself to a limited set of roles). I need to discuss with other reviewers and the authors before finalizing my recommendation.

Questions

See the Weakness section.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

See the Weakness section.

Summary

The paper aims to investigate integrating large language models (LLMs) into classical planning frameworks to enhance the planning effectiveness. The authors proposed a novel method named LLMs4Plan which integrates LLMs into action selection and mutual constraints solving within the graph-based planning framework. Evaluated across ten classic planning problems, this approach demonstrates improved success rates and reduced computational complexity compared to traditional methods. The study concludes that while LLMs alone are insufficient for planning, their integration into classical frameworks significantly boosts performance,.

Strengths

1. This paper investigates an intriguing topic: the performance of LLMs in classical planning problems. While the impressive performance of LLMs in natural language processing and coding tasks is well-investigated, their efficacy in planning tasks remains largely unexplored. Understanding whether LLMs can replace classical planning algorithms is a significant and meaningful research question. 2. The paper conducts extensive experiments on ten classical planning problems, which enhances the credibility of its findings and conclusions. This comprehensive evaluation demonstrates the robustness of the proposed approach. 3. The paper reveals that LLMs still cannot surpass classical planning algorithms, thereby highlighting a valuable direction for future research. This insight encourages further investigation into how LLMs can be effectively integrated with traditional planning methods.

Weaknesses

1. Although the authors point out that LLMs cannot outperform classical planning algorithms on their own and need to be integrated with classical methods to perform well, the paper lacks detailed insights on this integration. For example, specific strategies for integrating LLMs with the classic planning algorithms and the roles where LLMs excel within planning problems are not thoroughly discussed. The designed "expandGraph" and "sortActions" may not be the best practice manner. Future research directions to enhance the planning capabilities of LLMs should be more explicitly outlined. 2. The experiments are conducted in simulated planning domains, and the paper does not provide real-world applications or case studies to validate the practical utility of the approach. Including experimental results from more realistic scenarios would strengthen the paper. 3. While the method is effective for graph-based planning, its applicability to other planning frameworks or domains is not thoroughly investigated. A broader analysis could reveal the versatility of the proposed approach. 4. Typos: Algorithm ?? in Line 109.

Questions

What do you foresee as the future of planning algorithm development? Will it be a hybrid approach combining LLMs with classical planning methods, or an end-to-end solution relying solely on LLMs?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See the Weaknesses part

Including running history of actions in prompt

[Including running history of actions in prompt] Response #2.6: The history of actions makes the prompt very long, making LLMs suffered from outputing the result. We thus did not consider including history of actions, even though it is possible for improving the overall performance.

Response to rebuttal

Thank you to the authors for the new results. These align more closely with the expected experimental setup based on the introduction's motivation. The newly reported results are very impressive. Assuming these results and the additional details will be included in the paper, I am inclined to raise my score. However, my new score still considers the need for several modifications to improve the paper's clarity and the limitation of having only five non-corrupted problem files per domain. > when the iteration i (<N) becomes large enough, the pruning possibility \kapa_i is very small, making Algorithm 1 close to the classic GP algorithm I would consider adding another figure that depicts this trade-off between GP and your approach. x-axis is the number of iterations and y-axis is success rate. This will shed light on the number of iterations that were actually necessary.