Elamur Research⌕
☰
home / papers / 2023 / Dynamic Planning with a LLM

Dynamic Planning with a LLM

Paper · 2023 · Gautier Dagan, Frank Keller and Alex Lascarides

Summary

Agents built only on LLMs have difficulty with long, multi-step plans in embodied settings where the world is only partly observed. Repeated model calls are expensive, the context keeps growing, and hallucinated steps can derail a plan. Classical symbolic planners find optimal plans quickly, but they need a complete and correct problem description in advance. The authors propose LLM Dynamic Planner (LLM-DP), a closed-loop neuro-symbolic agent that divides the work. An LLM turns the natural-language task into a PDDL goal and guesses plausible values for unknown facts, such as where an object is likely to be. A symbolic PDDL planner then searches for plans in each sampled world state. An Action Selector chooses what to do next, and each observation updates the tracked world state and beliefs. New discoveries trigger replanning. With a hand-written PDDL domain file, LLM-DP solves 96% of the Alfworld test set. A ReAct baseline rerun on the same LLM solves roughly 54%, takes longer episodes and uses many more tokens. The work suggests that pairing LLMs with dedicated planning tools makes embodied agents cheaper and more reliable.

Key points

  • Setup: Alfworld is a text-only household environment with seven task types, in which object locations are initially hidden. LLM-DP uses gpt-3.5-turbo-0613 at temperature 0, with three fixed in-context examples for goal generation. It samples n = 3 plausible world states per planning step.
  • Accuracy: LLM-DP reaches 0.96 overall, as does LLM-DP-random, which samples beliefs randomly instead of with the LLM. The authors' ReAct rerun on gpt-3.5-turbo scores 0.54 in the table (53% in the text); the original ReAct with text-davinci-002 reported 0.64. The LLM produces an executable PDDL goal in 97% of cases.
  • Cost: LLM-DP processed about 633k LLM tokens, LLM-DP-random about 67k, and the ReAct reproduction about 9.16M.
  • Efficiency: Successful episodes average 13.16 actions for LLM-DP, 15.02 for random belief sampling and 18.69 for ReAct.
  • Assumptions and resources: The approach requires a known PDDL domain (actions, pre- and postconditions, predicates). It also assumes perfect observations, that only the agent changes the environment, and that valid actions always succeed. The code is released at github.com/itl-ed/llm-dp.

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

 Institutions

🎓University of EdinburghEdinburgh · United Kingdom359 works · 77,352 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

Cite

Cite as Gautier Dagan, Frank Keller and Alex Lascarides. 2023. Dynamic Planning with a LLM. arXiv:2308.06391.

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

@misc{dagan2023dynamic,
  title = {{Dynamic Planning with a LLM}},
  author = {Gautier Dagan, Frank Keller and Alex Lascarides},
  year = {2023},
  doi = {10.48550/arxiv.2308.06391},
  eprint = {2308.06391},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2308.06391}
}

References

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

  1. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,… — Language Models are Few-Shot Learners
  2. Yanda Chen, Ruiqi Zhong, Sheng Zha, George Karypis, and He He. 2022. Meta-learning via language model in-context tuning. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 719–730, Dublin, Ireland. Association for Computational L… find
  3. Shibo Hao, Yilan Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. ArXiv, abs/2305.14992. find
  4. Jörg Hoffmann and Bernhard Nebel. 2001. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253–302. find
  5. Or Honovich, Uri Shaham, Samuel R. Bowman, and Omer Levy. 2022. Instruction induction: From few examples to natural language task descriptions. ArXiv, abs/2205.10782. find
  6. Chenxu Hu, Jie Fu, Chenzhuang Du, Simian Luo, Junbo Jake Zhao, and Hang Zhao. 2023. Chatdb: Augmenting llms with databases as their symbolic memory. ArXiv, abs/2306.03901. — [arXiv:2306.03901](https://arxiv.org/abs/2306.03901) find
  7. Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Yejin Bang, Wenliang Dai, Andrea Madotto, and Pascale Fung. 2022. Survey of hallucination in natural language generation. ACM Computing Surveys, 55:1 – 38.
  8. Nir Lipovetzky, Miquel Ramirez, Christian Muise, and Hector Geffner. 2014. Width and inference based planners: Siw, bfs (f), and probe. Proceedings of the 8th International Planning Competition (IPC-2014), page 43. find
  9. B. Liu, Yuqian Jiang, Xiaohan Zhang, Qian Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. 2023. Llm+p: Empowering large language models with optimal planning proficiency. ArXiv, abs/2304.11477.
  10. The 1998 ai planning systems competition. AI Magazine, 21(2):35–55. find
  11. Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022. Rethinking the role of demonstrations: What makes in-context learning work? In Conference on Empirical Methods in Natural Language Processing.
  12. OpenAI. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774. Computation and Language (cs.CL); Artificial Intelligence (cs.AI).
  13. Yongchao Chen, Jacob Arkin, Yang Zhang, Nicholas A. Roy, and Chuchu Fan. 2023. Autotamp: Autoregressive task and motion planning with llms as translators and checkers. ArXiv, abs/2306.06531. — [arXiv:2306.06531](https://arxiv.org/abs/2306.06531) find
  14. Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. 2023. Gorilla: Large language model connected with massive apis. arXiv preprint arXiv:2305.15334.
  15. Richard E. Fikes and Nils J. Nilsson. 1971. Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3):189– 208. find
  16. Baolin Peng, Michel Galley, Pengcheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Lidén, Zhou Yu, Weizhu Chen, and Jianfeng Gao. 2023. Check your facts and try again: Improving large language models with external knowledge and automated feedback. ArXiv, abs/2302.12813.
  17. Caelan Reed Garrett, Tomas Lozano-Perez, and Leslie Pack Kaelbling. 2018. Pddlstream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning. In International Conference on Automated Planning and Scheduling. find
  18. Miquel Ramirez, Nir Lipovetzky, and Christian Muise. 2015. Lightweight Automated Planning ToolKiT. http://lapkt.org/. Accessed: 2020. ↗
  19. Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. ArXiv, abs/2302.04761.
  20. Noah Shinn, Beck Labash, and Ashwin Gopinath. 2023. Reflexion: An autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303.11366.
  21. Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew J. Hausknecht. 2020. Alfworld: Aligning text and embodied environments for interactive learning. CoRR, abs/2010.03768.
  22. Significant-Gravitas. 2023. An experimental open-source attempt to make gpt-4 fully autonomous. https://github.com/significant-gravitas/ auto-gpt. Accessed: 2023-06-09. ↗
  23. Tom Silver, Varun Hariprasad, Reece S Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez, and Leslie Pack Kaelbling. 2022. Pddl planning with pretrained large language models. In NeurIPS 2022 Foundation Models for Decision Making Workshop. find
  24. Håkan LS Younes and Michael L Littman. 2004. Ppddl1. 0: An extension to pddl for expressing planning domains with probabilistic effects. Techn. Rep. CMU-CS-04-162, 2:99. find
  25. LLM-DP (n=3) LLM-DP (n=3) - fallback LLM-DP (n=5) LLM-DP (n=5) - fallback SR EL 0.96 0.92 0.96 0.94 13.16 12.80 12.54 12.24 find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/dagan-2023-dynamic-planning-llm/