Elamur Research
☰
home / papers / 2023 / LLM+P: Empowering Large Language Models with Optimal Planning Proficiency

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

Written for the Research library (claude-opus-5-5) from the paper text. Original — arxiv.org/pdf/2304.11477

Summary

Large language models are good at producing fluent text, but they often fail at long-horizon planning. In a blocksworld example, for instance, GPT-4 proposes an invalid move sequence. LLM+P addresses this by letting the LLM do translation and handing the search to a classical planner. In LLM+P, the LLM rewrites a natural-language task as a PDDL problem file. It does this through in-context learning from a single small example pair of a natural-language problem and its PDDL. A human expert supplies a fixed domain PDDL file that encodes the actions with their preconditions and effects. A classical planner then searches for a correct or optimal plan, and the LLM turns that plan back into natural language or robot actions. The LLM is never finetuned. The authors also built a set of benchmark problems drawn from robot planning scenarios. On these, LLM+P found optimal solutions for most tasks, while GPT-4 working alone usually failed to produce even a feasible plan. The approach matters because it pairs the flexibility of language models with the guarantees of symbolic solvers, and the same pattern could carry over to other problem types that have a sound and complete solver.

Key points

  • The pipeline has three steps: the LLM writes the problem PDDL (objects, initial state, goals), a classical planner solves it using the given domain PDDL, and the LLM translates the resulting plan back.
  • Without an example in the prompt, GPT-4's PDDL looked syntactically valid but contained an invented predicate (empty) and left out an initial fact. With one demonstration, the file it produced was solvable directly, and the planner returned a 12-action plan.
  • The method relies on three assumptions: the robot knows when to invoke LLM+P, a domain PDDL is provided, and one simple natural-language/PDDL example pair is available.
  • The authors also demonstrated LLM+P on a home robot carrying out a complex manipulation task given in natural language. Code and results are available at github.com/Cranial-XIX/llm-pddl.
  • Known limitations: the LLM does not decide by itself whether a prompt should go through the pipeline, and domain files must be written by hand.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Other

Cited by

124 papers of our library cite it (of the 140673 whose bibliographies we read); 7 of them have a page here, 117 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2304.11477 · arXiv 2304.11477

@misc{liu2023llm,
  title = {{LLM+P: Empowering Large Language Models with Optimal Planning Proficiency}},
  author = {Liu, Bo and Jiang, Yuqian and Zhang, Xiaohan and Liu, Qiang and Zhang, Shiqi and Biswas, Joydeep and Stone, Peter},
  year = {2023},
  doi = {10.48550/arxiv.2304.11477},
  eprint = {2304.11477},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2304.11477}
}

References

68 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. J. Weizenbaum, “Eliza—a computer program for the study of natural language communication between man and machine,” Communications of the ACM, vol. 9, no. 1, pp. 36–45, 1966. find
  2. OpenAI, “Gpt-4 technical report,” 2023. find our card
  3. S. Vemprala, R. Bonatti, A. Bucker, and A. Kapoor, “Chatgpt for robotics: Design principles and model abilities,” Microsoft, Tech. Rep. MSR-TR-2023-8, February 2023. [Online]. Available: https://www.microsoft.com/en-us/research/publication/ chatgpt-for-robotics-design-principles-and-model-abilities/ ↗
  4. 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. find
  5. C. Lee, K. Cho, and W. Kang, “Mixout: Effective regularization to finetune large-scale pretrained language models,” arXiv preprint arXiv:1909.11299, 2019. — [arXiv:1909.11299](https://arxiv.org/abs/1909.11299) find
  6. 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. find
  7. D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld, and D. Wilkins, “Pddl-the planning domain definition language,” 1998. find
  8. P. Haslum, N. Lipovetzky, D. Magazzeni, and C. Muise, “An introduction to the planning domain definition language,” Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 13, no. 2, pp. 1–187, 2019. find
  9. 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. find our card
  10. 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 processing systems, vol. 33, pp. 1877–1901, 2020. find
  11. M. Helmert, “The fast downward planning system,” Journal of Artificial Intelligence Research, vol. 26, pp. 191–246, 2006. find
  12. T. Bylander, “The computational complexity of propositional STRIPS planning,” Artificial Intelligence, vol. 69, no. 1-2, pp. 165–204, 1994. find
  13. J. McCarthy, “Situations, actions, and causal laws,” Stanford University Technical Report, Tech. Rep., 1963. find
  14. R. E. Fikes and N. J. Nilsson, “Strips: A new approach to the application of theorem proving to problem solving,” Artificial intelligence, vol. 2, no. 3-4, pp. 189–208, 1971. find
  15. N. J. Nilsson et al., “Shakey the robot,” 1984. find
  16. 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. find
  17. 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. find
  18. Y.-q. Jiang, S.-q. Zhang, P. Khandelwal, and P. Stone, “Task planning in robotics: an empirical comparison of pddl-and asp-based systems,” Frontiers of Information Technology & Electronic Engineering, vol. 20, pp. 363–373, 2019. find
  19. 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. find
  20. V. Lifschitz, “Answer set programming and plan generation,” Artificial Intelligence, vol. 138, no. 1-2, pp. 39–54, 2002. find
  21. 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. find
  22. 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. find
  23. 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. find
  24. 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. find
  25. 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. find
  26. 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. find
  27. 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. find
  28. M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, et al., “Evaluating large language models trained on code,” arXiv preprint arXiv:2107.03374, 2021. find our card
  29. S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, et al., “Opt: Open pre-trained transformer language models,” arXiv preprint arXiv:2205.01068, 2022. find
  30. OpenAI, “Chatgpt,” Accessed: 2023-02-08, 2023, cit. on pp. 1, 16. [Online]. Available: https://openai.com/blog/chatgpt/ ↗
  31. 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. find
  32. 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. find
  33. 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. find
  34. 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. find our card
  35. 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. find
  36. 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. find
  37. 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. find
  38. 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. find our card
  39. 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, p… find
  40. I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg, “Progprompt: Generating situated robot task plans using large language models,” arXiv preprint arXiv:2209.11302, 2022. find our card
  41. 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:2303.12153](https://arxiv.org/abs/2303.12153) find
  42. 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:2212.01944](https://arxiv.org/abs/2212.01944) find
  43. 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:2305.17590](https://arxiv.org/abs/2305.17590) find
  44. 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. find
  45. 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:2306.06531](https://arxiv.org/abs/2306.06531) find
  46. K. Valmeekam, S. Sreedharan, M. Marquez, A. Olmo, and S. Kambhampati, “On the planning abilities of large language models (a critical investigation with a proposed benchmark),” arXiv preprint arXiv:2302.06706, 2023. find
  47. 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 find
  48. 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:2212.08681](https://arxiv.org/abs/2212.08681) find
  49. D. Arora and S. Kambhampati, “Learning and leveraging verifiers to improve planning capabilities of pre-trained language models,” arXiv preprint arXiv:2305.17077, 2023. find
  50. L. Guan, K. Valmeekam, S. Sreedharan, and S. Kambhampati, “Leveraging pre-trained large language models to construct and utilize world models for model-based task planning,” arXiv preprint arXiv:2305.14909, 2023. find
  51. 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. find
  52. V. Pallagani, B. Muppasani, K. Murugesan, F. Rossi, B. Srivastava, L. Horesh, F. Fabiano, and A. Loreggia, “Understanding the capabilities of large language models for automated planning,” arXiv preprint arXiv:2305.16151, 2023. — [arXiv:2305.16151](https://arxiv.org/abs/2305.16151) find
  53. K. Valmeekam, M. Marquez, S. Sreedharan, and S. Kambhampati, “On the planning abilities of large language models–a critical investigation,” arXiv preprint arXiv:2305.15771, 2023. find
  54. 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:2302.05128](https://arxiv.org/abs/2302.05128) find
  55. R. Hazra, P. Z. D. Martires, and L. De Raedt, “Saycanpay: Heuristic planning with large language models using learnable domain knowledge,” arXiv preprint arXiv:2308.12682, 2023. find
  56. K. Rana, J. Haviland, S. Garg, J. Abou-Chakra, I. Reid, and N. Suenderhauf, “Sayplan: Grounding large language models using 3d scene graphs for scalable task planning,” arXiv preprint arXiv:2307.06135, 2023. — [arXiv:2307.06135](https://arxiv.org/abs/2307.06135) find
  57. 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:2308.13724](https://arxiv.org/abs/2308.13724) find
  58. Z. Wang, S. Cai, A. Liu, X. Ma, and Y. Liang, “Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents,” arXiv preprint arXiv:2302.01560, 2023. find our card
  59. 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. find our card
  60. 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. find our card
  61. A. Madaan, N. Tandon, P. Clark, and Y. Yang, “Memory-assisted prompt editing to improve gpt-3 after deployment,” 2023. find
  62. W. Shi, S. Min, M. Yasunaga, M. Seo, R. James, M. Lewis, L. Zettlemoyer, and W.-t. Yih, “Replug: Retrieval-augmented black-box language models,” arXiv preprint arXiv:2301.12652, 2023. find our card
  63. 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. find our card
  64. 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. find
  65. T. Schick, J. Dwivedi-Yu, R. Dessı̀, R. Raileanu, M. Lomeli, L. Zettlemoyer, N. Cancedda, and T. Scialom, “Toolformer: Language models can teach themselves to use tools,” arXiv preprint arXiv:2302.04761, 2023. find our card
  66. Q. Lyu, S. Havaldar, A. Stein, L. Zhang, D. Rao, E. Wong, M. Apidianaki, and C. Callison-Burch, “Faithful chain-of-thought reasoning,” arXiv preprint arXiv:2301.13379, 2023. find our card
  67. J. Seipp, Á. Torralba, and J. Hoffmann, “PDDL generators,” https: //doi.org/10.5281/zenodo.6382173, 2022. — [doi:10.5281/zenodo.6382173](https://doi.org/10.5281/zenodo.6382173) find
  68. 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. find