Elamur Research⌕
☰
home / papers / 2023 / SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge

SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge

Paper · 2023 · Rishi Hazra, Pedro Zuidberg Dos Martires and Luc De Raedt

Summary

LLM-generated plans often fail in two ways. They include steps whose preconditions are not met in the actual environment, and they run longer than needed because the model picks each next step without considering the final goal. Classical planners avoid both problems by using PDDL domain files and heuristic search, but such files are hard to write for open, real-world settings. SayCanPay combines the two by treating LLM planning as heuristic search. At each step, an LLM (Say) proposes candidate actions. A feasibility model (Can) checks whether each candidate is executable, playing the role of precondition evaluation. A payoff model (Pay) estimates how much the action moves the agent toward the goal, acting as a heuristic estimator. Can and Pay are trained on expert trajectories from the target domain. Their joint score guides decoding, including a beam search over whole actions (Beam-Action), and complete plans are built offline. On Ravens-Hanoi, Ravens-Blocks, BabyAI and VirtualHome, the approach yields more successful and shorter plans than other LLM planners. This points to a practical route toward grounded, cost-aware planning with language models.

Key points

  • Three decoding strategies are compared: Greedy-Token, Greedy-Action and Beam-Action. Performance consistently ranks Greedy-Token < Greedy-Action < Beam-Action. Over Greedy-Action, Beam-Action SayCanPay raises success by about 1–40%, cost-effectiveness by 0–73% and generalization by 0–89%.
  • Say models include Vicuna and Flan-T5. An oracle "Perfect Say" raises Greedy-Action success considerably. For example, SayCanPay on Ravens-Hanoi goes from 50 to 92, an overall gain of 16–84% across environments.
  • SayCanPay scoring produces plans whose length is close to the oracle plan length (relative length ≈ 1).
  • Approximate planning times are ~9s for Greedy-Token, ~17s for Greedy-Action and ~35s for Beam-Action. Because Can and Pay are small LMs, they add negligible overhead.
  • The authors name two limitations: the need for expert trajectories to train the domain models, and the weak transfer of these models to out-of-distribution data.

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

🎓KU LeuvenLeuven · Belgium52 works · 8,121 citations🎓Örebro UniversityÖrebro · Sweden2 works · 60 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

Cite

Cite as Rishi Hazra, Pedro Zuidberg Dos Martires and Luc De Raedt. 2023. SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge. arXiv:2308.12682.

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

@misc{hazra2023saycanpay,
  title = {{SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge}},
  author = {Rishi Hazra, Pedro Zuidberg {Dos Martires} and Luc {De Raedt}},
  year = {2023},
  doi = {10.48550/arxiv.2308.12682},
  eprint = {2308.12682},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2308.12682}
}

References

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

  1. Ahn, M.; Brohan, A.; Brown, N.; Chebotar, Y.; Cortes, O.; David, B.; Finn, C.; Fu, C.; Gopalakrishnan, K.; Hausman, K.; Herzog, A.; Ho, D.; Hsu, J.; Ibarz, J.; Ichter, B.; Irpan, A.; Jang, E.; Ruano, R. J.; Jeffrey, K.; Jesmonth, S.; Joshi, N. J.; Julian, R.; Kalashnikov, D.; Kuang, Y.; Lee, K.-H.;… — Do As I Can, Not As I Say: Grounding Language in Robotic Affordances
  2. Bonet, B.; and Geffner, H. 2001. Planning as heuristic search. Artificial Intelligence, 129(1-2): 5–33. find
  3. Brohan, A.; Brown, N.; Carbajal, J.; Chebotar, Y.; Chen, X.; Choromanski, K.; Ding, T.; Driess, D.; Dubey, A.; Finn, C.; Florence, P.; Fu, C.; Arenas, M. G.; Gopalakrishnan, K.; Han, K.; Hausman, K.; Herzog, A.; Hsu, J.; Ichter, B.; Irpan, A.; Joshi, N.; Julian, R.; Kalashnikov, D.; Kuang, Y.; Leal,… find
  4. Chevalier-Boisvert, M.; Bahdanau, D.; Lahlou, S.; Willems, L.; Saharia, C.; Nguyen, T. H.; and Bengio, Y. 2019. BabyAI: First Steps Towards Grounded Language Learning With a Human In the Loop. In International Conference on Learning Representations, volume 105. find
  5. Chiang, W.-L.; Li, Z.; Lin, Z.; Sheng, Y.; Wu, Z.; Zhang, H.; Zheng, L.; Zhuang, S.; Zhuang, Y.; Gonzalez, J. E.; Stoica, I.; and Xing, E. P. 2023. Vicuna: An Open-Source Chatbot Impressing GPT-4 with 90%* ChatGPT Quality. find
  6. Chung, H. W.; Hou, L.; Longpre, S.; Zoph, B.; Tay, Y.; Fedus, W.; Li, Y.; Wang, X.; Dehghani, M.; Brahma, S.; Webson, A.; Gu, S. S.; Dai, Z.; Suzgun, M.; Chen, X.; Chowdhery, A.; Castro-Ros, A.; Pellat, M.; Robinson, K.; Valter, D.; Narang, S.; Mishra, G.; Yu, A.; Zhao, V.; Huang, Y.; Dai, A.; Yu, H… find
  7. Dettmers, T.; Lewis, M.; Belkada, Y.; and Zettlemoyer, L. 2022. LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale. arXiv:2208.07339. find
  8. Dettmers, T.; Pagnoni, A.; Holtzman, A.; and Zettlemoyer, L. 2023. QLoRA: Efficient Finetuning of Quantized LLMs. arXiv:2305.14314.
  9. Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Lo…
  10. Ding, Y.; Zhang, X.; Amiri, S.; Cao, N.; Yang, H.; Kaminski, A.; Esselink, C.; and Zhang, S. 2023. Integrating action knowledge and LLMs for task planning and situation handling in open worlds. Autonomous Robots, 47(8): 981–997. find
  11. Du, Y.; Liu, Z.; Li, J.; and Zhao, W. X. 2022. A Survey of Vision-Language Pre-Trained Models. arXiv:2202.10936. — [arXiv:2202.10936](https://arxiv.org/abs/2202.10936) find
  12. Frantar, E.; Ashkboos, S.; Hoefler, T.; and Alistarh, D. 2023. GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers. arXiv:2210.17323. find
  13. Golowich, N.; Moitra, A.; and Rohatgi, D. 2022. Planning in Observable POMDPs in Quasipolynomial Time. arXiv:2201.04735. — [arXiv:2201.04735](https://arxiv.org/abs/2201.04735) find
  14. Hao, S.; Gu, Y.; Ma, H.; Hong, J. J.; Wang, Z.; Wang, D. Z.; and Hu, Z. 2023. Reasoning with Language Model is Planning with World Model. arXiv:2305.14992. find
  15. Helmert, M. 2006. The fast downward planning system. Journal of Artificial Intelligence Research, 26: 191–246.
  16. Huang, W.; Abbeel, P.; Pathak, D.; and Mordatch, I. 2022a. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. In International Conference on Machine Learning, 9118–9147.
  17. PMLR. Huang, W.; Xia, F.; Shah, D.; Driess, D.; Zeng, A.; Lu, Y.; Florence, P.; Mordatch, I.; Levine, S.; Hausman, K.; and Ichter, B. 2023. Grounded Decoding: Guiding Text Generation with Grounded Models for Embodied Agents. arXiv:2303.00855. — [arXiv:2303.00855](https://arxiv.org/abs/2303.00855) find
  18. Huang, W.; Xia, F.; Xiao, T.; Chan, H.; Liang, J.; Florence, P.; Zeng, A.; Tompson, J.; Mordatch, I.; Chebotar, Y.; Sermanet, P.; Brown, N.; Jackson, T.; Luu, L.; Levine, S.; Hausman, K.; and Ichter, B. 2022b. Inner Monologue: Embodied Reasoning through Planning with Language Models. arXiv:2207.0560… find
  19. Kaelbling, L. P.; Littman, M. L.; and Cassandra, A. R. 1998. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2): 99–134. find
  20. Kwon, M.; Xie, S. M.; Bullard, K.; and Sadigh, D. 2023. Reward Design with Language Models. In The Eleventh International Conference on Learning Representations.
  21. Lakhotia, K.; Kharitonov, E.; Hsu, W.-N.; Adi, Y.; Polyak, A.; Bolte, B.; Nguyen, T.-A.; Copet, J.; Baevski, A.; Mohamed, A.; and Dupoux, E. 2021. On Generative Spoken Language Modeling from Raw Audio. Transactions of the Association for Computational Linguistics, 9: 1336–1354.
  22. Liang, J.; Huang, W.; Xia, F.; Xu, P.; Hausman, K.; Ichter, B.; Florence, P.; and Zeng, A. 2023. Code as Policies: Language Model Programs for Embodied Control. arXiv:2209.07753. find
  23. Liao, Y.-H.; Puig, X.; Boben, M.; Torralba, A.; and Fidler, S. 2019. Synthesizing Environment-Aware Activities via Activity Sketches. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 6284–6292. find
  24. Lin, K.; Agia, C.; Migimatsu, T.; Pavone, M.; and Bohg, J. 2023. Text2Motion: from natural language instructions to feasible plans. Autonomous Robots, 47(8): 1345–1365. find
  25. Liu, B.; Jiang, Y.; Zhang, X.; Liu, Q.; Zhang, S.; Biswas, J.; and Stone, P. 2023. LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. arXiv:2304.11477.
  26. Pallagani, V.; Muppasani, B.; Murugesan, K.; Rossi, F.; Horesh, L.; Srivastava, B.; Fabiano, F.; and Loreggia, A. 2022. Plansformer: Generating Symbolic Plans using Transformers. arXiv:2212.08681. — [arXiv:2212.08681](https://arxiv.org/abs/2212.08681) find
  27. Puig, X.; Ra, K.; Boben, M.; Li, J.; Wang, T.; Fidler, S.; and Torralba, A. 2018. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 8494– 8502. find
  28. Raffel, C.; Shazeer, N.; Roberts, A.; Lee, K.; Narang, S.; Matena, M.; Zhou, Y.; Li, W.; and Liu, P. J. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1): 5485–5551. Silver, T.; Hariprasad, V.; Shuttleworth, R. S.…
  29. Singh, I.; Blukis, V.; Mousavian, A.; Goyal, A.; Xu, D.; Tremblay, J.; Fox, D.; Thomason, J.; and Garg, A. 2023. ProgPrompt: Generating Situated Robot Task Plans using Large Language Models. In International Conference on Robotics and Automation (ICRA). Touvron, H.; Lavril, T.; Izacard, G.; Martinet…
  30. Valmeekam, K.; Olmo, A.; Sreedharan, S.; and Kambhampati, S. 2022. Large Language Models Still Can’t Plan (A Benchmark for LLMs on Planning and Reasoning about Change). In NeurIPS 2022 Foundation Models for Decision Making Workshop. find
  31. Valmeekam, K.; Sreedharan, S.; Marquez, M.; Olmo, A.; and Kambhampati, S. 2023. On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark). arXiv:2302.06706. van den Oord, A.; Li, Y.; and Vinyals, O. 2019. Representation Learning with Contrastive Predicti…
  32. Wang, Y.; Wang, W.; Joty, S.; and Hoi, S. C. 2021. CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation. In Moens, M.-F.; Huang, X.; Specia, L.; and Yih, S. W.-t., eds., Proceedings of the 2021 Conference on Empirical Methods in Natural Language P… find
  33. Xie, Y.; Yu, C.; Zhu, T.; Bai, J.; Gong, Z.; and Soh, H. 2023. Translating Natural Language to Planning Goals with Large-Language Models. arXiv:2302.05128. — [arXiv:2302.05128](https://arxiv.org/abs/2302.05128) find
  34. Yao, S.; Yu, D.; Zhao, J.; Shafran, I.; Griffiths, T. L.; Cao, Y.; and Narasimhan, K. 2023. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601. find
  35. Zeng, A.; Florence, P.; Tompson, J.; Welker, S.; Chien, J.; Attarian, M.; Armstrong, T.; Krasin, I.; Duong, D.; Sindhwani, V.; and Lee, J. 2021. Transporter Networks: Rearranging the Visual World for Robotic Manipulation. In Proceedings of the 2020 Conference on Robot Learning, volume 155 of Proceed… find
  36. PMLR. Ziegler, D. M.; Stiennon, N.; Wu, J.; Brown, T. B.; Radford, A.; Amodei, D.; Christiano, P.; and Irving, G. 2020. Fine-Tuning Language Models from Human Preferences. arXiv:1909.08593. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hazra-2023-saycanpay-heuristic-planning-large-language/