CoChat
Sign Up
PreprintCited by 104AI-based Problem Solving and PlanningNatural Language Processing TechniquesTopic Modeling

LLM+P: Empowering Large Language Models with Optimal Planning Proficiency

Open access
Liu, Bo, Jiang, Yuqian, Zhang, Xiaohan, Liu, Qiang, Zhang, Shiqi, Biswas, Joydeep, Stone, Peter·2023·arXiv
DOI 10.48550/arxiv.2304.11477arXiv 2304.11477
Open this paper in CoChat — free accountOpen PDF

Abstract

Large language models (LLMs) have demonstrated remarkable zero-shot generalization abilities: state-of-the-art chatbots can provide plausible answers to many common questions that arise in daily life. However, so far, LLMs cannot reliably solve long-horizon planning problems. By contrast, classical planners, once a problem is given in a formatted way, can use efficient search algorithms to quickly identify correct, or even optimal, plans. In an effort to get the best of both worlds, this paper introduces LLM+P, the first framework that incorporates the strengths of classical planners into LLMs. LLM+P takes in a natural language description of a planning problem, then returns a correct (or optimal) plan for solving that problem in natural language. LLM+P does so by first converting the language description into a file written in the planning domain definition language (PDDL), then leveraging classical planners to quickly find a solution, and then translating the found solution back into natural language. Along with LLM+P, we define a diverse set of different benchmark problems taken from common planning scenarios. Via a comprehensive set of experiments on these benchmark problems, we find that LLM+P is able to provide optimal solutions for most problems, while LLMs fail to provide even feasible plans for most problems.\footnote{The code and results are publicly available at https://github.com/Cranial-XIX/llm-pddl.git.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2304.11477

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Common task success metrics for LLM-based agents include success rate, reward/score, coverage, and accuracy.

    “Common metrics include success rate [12,22,57,59], reward/score [22,59,122], coverage [16], and accuracy [18,40,102].”

    From A survey on large language model based autonomous agents (2024) · cites this paper as [57]

    The Experiment Setup and Results and Analysis sections report success rate as an evaluation metric for LLM-based planning methods. The provided copy does not establish reward/score, coverage, or accuracy as metrics used by this paper, so it supports only the success-rate portion of the attributed sentence. Page numbers were not available in the indexed passages. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Several recent studies confirm that LLMs are not actually able to generate executable plans when used in autonomous modes.

    “several recent studies confirm that LLMs are not actually able to generate executable plans when they are used in autonomous modes (Valmeekam et al., 2023c;Liu et al., 2023;Silver et al., 2022).”

    From LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks (2024) · cites this paper as Liu et al., 2023

    The Findings (LLM-AS-P; page not provided) say that when the LLM plans directly, most of its plans are not feasible. This supports the concern about using LLMs as autonomous planners, but not the categorical claim that they cannot generate executable plans at all. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Existing work uses plan validators to check if generated code can be solved with a traditional planner.

    “existing work uses “plan validators” to check if the generated code can be solved with a traditional planner”

    From Planetarium: A Rigorous Benchmark for Translating Text to Structured Planning Languages (2025) · cites this paper as Liu et al., 2023

    The Method section says LLM+P feeds LLM-generated PDDL into a classical planner to generate a plan, and the Experiment Setup says it feeds generated PDDL into FAST-DOWNWARD. Those passages support the planner component, but they do not describe using “plan validators” to check whether generated code can be solved. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • LLM+P transforms task descriptions into PDDL, uses an external planner to deal with the PDDL, and transforms results back into natural language by LLMs.

    “In specific, LLM+P [57] first transforms the task descriptions into formal Planning Domain Definition Languages (PDDL), and then it uses an external planner to deal with the PDDL.Finally, the generated results are transformed back into natural language by LLMs.”

    From A survey on large language model based autonomous agents (2024) · cites this paper as [57]

  • Common efficiency metrics for LLM-based agents include length of planning, cost associated with development, speed of inference, and number of clarification dialogues.

    “Commonly considered metrics encompass the length of planning [57], the cost associated with development [18], the speed of inference [16,38], and number of clarification dialogues [122].”

    From A survey on large language model based autonomous agents (2024) · cites this paper as [57]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 60

  1. J. Weizenbaum, "Eliza-a computer program for the study of natural language communication between man and machine," Communica- tions of the ACM, vol. 9, no. 1, pp. 36-45, 1966.
  2. K. Mahowald, A. A. Ivanova, I. A. Blank, N. Kanwisher, J. B. Tenenbaum, and E. Fedorenko, "Dissociating language and thought in large language models: a cognitive perspective," arXiv preprint arXiv:2301.06627, 2023. · arXiv
  3. C. Lee, K. Cho, and W. Kang, "Mixout: Effective regularization to finetune large-scale pretrained language models," arXiv preprint arXiv:1909.11299, 2019. · arXiv
  4. J. Wei, M. Bosma, V. Y. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and Q. V. Le, "Finetuned language models are zero-shot learners," arXiv preprint arXiv:2109.01652, 2021. · arXiv
  5. P. Haslum, N. Lipovetzky, D. Magazzeni, and C. Muise, "An introduc- tion to the planning domain definition language," Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 13, no. 2, pp. 1-187, 2019.
  6. K. Valmeekam, A. Olmo, S. Sreedharan, and S. Kambhampati, "Large language models still can't plan (a benchmark for llms on planning and reasoning about change)," arXiv preprint arXiv:2206.10498, 2022. · arXiv
  7. T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al., "Language models are few-shot learners," Advances in neural information pro- cessing systems, vol. 33, pp. 1877-1901, 2020.
  8. M. Helmert, "The fast downward planning system," Journal of Artifi- cial Intelligence Research, vol. 26, pp. 191-246, 2006.
  9. T. Bylander, "The computational complexity of propositional STRIPS planning," Artificial Intelligence, vol. 69, no. 1-2, pp. 165-204, 1994.
  10. R. E. Fikes and N. J. Nilsson, "Strips: A new approach to the appli- cation of theorem proving to problem solving," Artificial intelligence, vol. 2, no. 3-4, pp. 189-208, 1971.
  11. J. Carbonell, O. Etzioni, Y. Gil, R. Joseph, C. Knoblock, S. Minton, and M. Veloso, "Prodigy: An integrated architecture for planning and learning," ACM SIGART Bulletin, vol. 2, no. 4, pp. 51-55, 1991.
  12. D. S. Nau, T.-C. Au, O. Ilghami, U. Kuter, J. W. Murdock, D. Wu, and F. Yaman, "Shop2: An htn planning system," Journal of artificial intelligence research, 2003.
  13. Y.-q. Jiang, S.-q. Zhang, P. Khandelwal, and P. Stone, "Task planning in robotics: an empirical comparison of pddl-and asp-based sys- tems," Frontiers of Information Technology & Electronic Engineering, vol. 20, pp. 363-373, 2019.
  14. G. Brewka, T. Eiter, and M. Truszczyński, "Answer set programming at a glance," Communications of the ACM, vol. 54, no. 12, pp. 92-103, 2011.
  15. V. Lifschitz, "Answer set programming and plan generation," Artificial Intelligence, vol. 138, no. 1-2, pp. 39-54, 2002.
  16. M. Fox and D. Long, "Pddl2. 1: An extension to pddl for expressing temporal planning domains," Journal of artificial intelligence research, vol. 20, pp. 61-124, 2003.
  17. S. Zhang, F. Yang, P. Khandelwal, and P. Stone, "Mobile robot planning using action language bc with an abstraction hierarchy," in International Conference on Logic Programming and Nonmonotonic Reasoning. Springer, 2015, pp. 502-516.
  18. Y. Ding, X. Zhang, X. Zhan, and S. Zhang, "Task-motion planning for safe and efficient urban driving," in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.
  19. Y. Jiang, H. Yedidsion, S. Zhang, G. Sharon, and P. Stone, "Multi-robot planning with conflicts and synergies," Autonomous Robots, vol. 43, no. 8, pp. 2011-2032, 2019.
  20. F. Lagriffoul, N. T. Dantam, C. Garrett, A. Akbari, S. Srivastava, and L. E. Kavraki, "Platform-independent benchmarks for task and motion planning," IEEE Robotics and Automation Letters, vol. 3, no. 4, pp. 3765-3772, 2018.
  21. L. P. Kaelbling and T. Lozano-Pérez, "Integrated task and motion planning in belief space," The International Journal of Robotics Research, vol. 32, no. 9-10, pp. 1194-1227, 2013.
  22. J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, "Bert: Pre-training of deep bidirectional transformers for language understanding," arXiv preprint arXiv:1810.04805, 2018. · arXiv
  23. M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Ka- plan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, et al., "Evaluating large language models trained on code," arXiv preprint arXiv:2107.03374, 2021. · arXiv
  24. S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. De- wan, M. Diab, X. Li, X. V. Lin, et al., "Opt: Open pre-trained trans- former language models," arXiv preprint arXiv:2205.01068, 2022. · arXiv
  25. H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al., "Llama: Open and efficient foundation language models," arXiv preprint arXiv:2302.13971, 2023. · arXiv
  26. H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, et al., "Llama 2: Open foundation and fine-tuned chat models," arXiv preprint arXiv:2307.09288, 2023. · arXiv
  27. A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al., "Palm: Scaling language modeling with pathways," arXiv preprint arXiv:2204.02311, 2022. · arXiv
  28. M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, K. Gopalakrishnan, K. Hausman, A. Herzog, et al., "Do as i can, not as i say: Grounding language in robotic affordances," arXiv preprint arXiv:2204.01691, 2022. · arXiv
  29. Y. Ding, X. Zhang, C. Paxton, and S. Zhang, "Task and motion planning with large language models for object rearrangement," 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2023.
  30. D. Driess, F. Xia, M. S. Sajjadi, C. Lynch, A. Chowdhery, B. Ichter, A. Wahid, J. Tompson, Q. Vuong, T. Yu, et al., "Palm-e: An embodied multimodal language model," arXiv preprint arXiv:2303.03378, 2023. · arXiv
  31. W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch, Y. Chebotar, et al., "Inner monologue: Embodied reasoning through planning with language models," arXiv preprint arXiv:2207.05608, 2022. · arXiv
  32. W. Huang, P. Abbeel, D. Pathak, and I. Mordatch, "Language models as zero-shot planners: Extracting actionable knowledge for embodied agents," in International Conference on Machine Learning. PMLR, 2022, pp. 9118-9147.
  33. Y. Kant, A. Ramachandran, S. Yenamandra, I. Gilitschenski, D. Batra, A. Szot, and H. Agrawal, "Housekeep: Tidying virtual households using commonsense reasoning," in Computer Vision-ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXXIX. Springer, 2022, pp. 355-373.
  34. I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg, "Progprompt: Generating situ- ated robot task plans using large language models," arXiv preprint arXiv:2209.11302, 2022. · arXiv
  35. K. Lin, C. Agia, T. Migimatsu, M. Pavone, and J. Bohg, "Text2motion: From natural language instructions to feasible plans," arXiv preprint arXiv:2303.12153, 2023. · arXiv
  36. Y. Yang, J.-R. Gaglione, C. Neary, and U. Topcu, "Automaton-based representations of task knowledge from generative language models," arXiv preprint arXiv:2212.01944, 2023. · arXiv
  37. Y. Ding, X. Zhang, S. Amiri, N. Cao, H. Yang, A. Kaminski, C. Esselink, and S. Zhang, "Integrating action knowledge and llms for task planning and situation handling in open worlds," arXiv preprint arXiv:2305.17590, 2023. · arXiv
  38. A. Z. Ren, A. Dixit, A. Bodrova, S. Singh, S. Tu, N. Brown, P. Xu, L. Takayama, F. Xia, J. Varley, et al., "Robots that ask for help: Uncertainty alignment for large language model planners," arXiv preprint arXiv:2307.01928, 2023. · arXiv
  39. Y. Chen, J. Arkin, Y. Zhang, N. Roy, and C. Fan, "Autotamp: Autoregressive task and motion planning with llms as translators and checkers," arXiv preprint arXiv:2306.06531, 2023. · arXiv
  40. K. Valmeekam, S. Sreedharan, M. Marquez, A. Olmo, and S. Kamb- hampati, "On the planning abilities of large language models (a critical investigation with a proposed benchmark)," arXiv preprint arXiv:2302.06706, 2023. · arXiv
  41. T. Silver, V. Hariprasad, R. S. Shuttleworth, N. Kumar, T. Lozano- Pérez, and L. P. Kaelbling, "PDDL planning with pretrained large language models," in NeurIPS 2022 Foundation Models for Decision Making Workshop, 2022. [Online]. Available: https: //openreview.net/forum?id=1QMMUB4zfl
  42. V. Pallagani, B. Muppasani, K. Murugesan, F. Rossi, L. Horesh, B. Srivastava, F. Fabiano, and A. Loreggia, "Plansformer: Generating symbolic plans using transformers," arXiv preprint arXiv:2212.08681, 2022. · arXiv
  43. D. Arora and S. Kambhampati, "Learning and leveraging verifiers to improve planning capabilities of pre-trained language models," arXiv preprint arXiv:2305.17077, 2023. · arXiv
  44. L. Guan, K. Valmeekam, S. Sreedharan, and S. Kambhampati, "Leveraging pre-trained large language models to construct and uti- lize world models for model-based task planning," arXiv preprint arXiv:2305.14909, 2023. · arXiv
  45. T. Silver, S. Dan, K. Srinivas, J. B. Tenenbaum, L. P. Kaelbling, and M. Katz, "Generalized planning in pddl domains with pretrained large language models," arXiv preprint arXiv:2305.11014, 2023. · arXiv
  46. V. Pallagani, B. Muppasani, K. Murugesan, F. Rossi, B. Srivastava, L. Horesh, F. Fabiano, and A. Loreggia, "Understanding the capabili- ties of large language models for automated planning," arXiv preprint arXiv:2305.16151, 2023. · arXiv
  47. K. Valmeekam, M. Marquez, S. Sreedharan, and S. Kambhampati, "On the planning abilities of large language models-a critical investi- gation," arXiv preprint arXiv:2305.15771, 2023. · arXiv
  48. Y. Xie, C. Yu, T. Zhu, J. Bai, Z. Gong, and H. Soh, "Translating natural language to planning goals with large-language models," arXiv preprint arXiv:2302.05128, 2023. · arXiv
  49. R. Hazra, P. Z. D. Martires, and L. De Raedt, "Saycanpay: Heuristic planning with large language models using learnable domain knowl- edge," arXiv preprint arXiv:2308.12682, 2023. · arXiv
  50. K. Rana, J. Haviland, S. Garg, J. Abou-Chakra, I. Reid, and N. Suen- derhauf, "Sayplan: Grounding large language models using 3d scene graphs for scalable task planning," arXiv preprint arXiv:2307.06135, 2023. · arXiv
  51. Z. Zhou, J. Song, K. Yao, Z. Shu, and L. Ma, "Isr-llm: Iterative self-refined large language model for long-horizon sequential task planning," arXiv preprint arXiv:2308.13724, 2023. · arXiv
  52. Z. Wang, S. Cai, A. Liu, X. Ma, and Y. Liang, "Describe, explain, plan and select: Interactive planning with large language models en- ables open-world multi-task agents," arXiv preprint arXiv:2302.01560, 2023. · arXiv
  53. R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, et al., "Webgpt: Browser- assisted question-answering with human feedback," arXiv preprint arXiv:2112.09332, 2021. · arXiv
  54. A. Lazaridou, E. Gribovskaya, W. Stokowiec, and N. Grigorev, "Internet-augmented language models through few-shot prompting for open-domain question answering," arXiv preprint arXiv:2203.05115, 2022. · arXiv
  55. W. Shi, S. Min, M. Yasunaga, M. Seo, R. James, M. Lewis, L. Zettle- moyer, and W.-t. Yih, "Replug: Retrieval-augmented black-box lan- guage models," arXiv preprint arXiv:2301.12652, 2023. · arXiv
  56. W. Chen, X. Ma, X. Wang, and W. W. Cohen, "Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks," arXiv preprint arXiv:2211.12588, 2022. · arXiv
  57. L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig, "Pal: Program-aided language models," arXiv preprint arXiv:2211.10435, 2022. · arXiv
  58. T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, L. Zettle- moyer, N. Cancedda, and T. Scialom, "Toolformer: Language models can teach themselves to use tools," arXiv preprint arXiv:2302.04761, 2023. · arXiv
  59. Q. Lyu, S. Havaldar, A. Stein, L. Zhang, D. Rao, E. Wong, M. Apid- ianaki, and C. Callison-Burch, "Faithful chain-of-thought reasoning," arXiv preprint arXiv:2301.13379, 2023. · arXiv
  60. S. Yao, D. Yu, J. Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and K. Narasimhan, "Tree of thoughts: Deliberate problem solving with large language models," arXiv preprint arXiv:2305.10601, 2023. · arXiv

Cited by

Sorted by citations

Authors
Liu, B., Jiang, Y., Zhang, X., Liu, Q., Zhang, S., Biswas, J., & Stone, P.
Affiliations
  • The University of Texas at Austin (US)
  • Binghamton University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2304.11477
arXiv
2304.11477
OpenAlex
W4366999541
Cited by
104
References
0
Citations by year
2026: 4 · 2025: 18 · 2024: 64 · 2023: 18
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
Keywords
large language models, automated planning, long-horizon planning, optimal planning, PDDL, planning benchmarks

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review