Classical Planning with LLM-Generated Heuristics: Challenging the State
  of the Art with Python Code
In recent years, large language models (LLMs) have shown remarkable
capabilities in various artificial intelligence problems. However, they fail to
plan reliably, even when prompted with a detailed definition of the planning
task. Attempts to improve their planning capabilities, such as chain-of-thought
prompting, fine-tuning, and explicit "reasoning" still yield incorrect plans
and usually fail to generalize to larger tasks. In this paper, we show how to
use LLMs to generate correct plans, even for out-of-distribution tasks of
increasing size. For a given planning domain, we ask an LLM to generate several
domain-dependent heuristic functions in the form of Python code, evaluate them
on a set of training tasks within a greedy best-first search, and choose the
strongest one. The resulting LLM-generated heuristics solve many more unseen
test tasks than state-of-the-art domain-independent heuristics for classical
planning. They are even competitive with the strongest learning algorithm for
domain-dependent planning. These findings are especially remarkable given that
our proof-of-concept implementation is based on an unoptimized Python planner
and the baselines all build upon highly optimized C++ code. In some domains,
the LLM-generated heuristics expand fewer states than the baselines, revealing
that they are not only efficiently computable, but sometimes even more
informative than the state-of-the-art heuristics. Overall, our results show
that sampling a set of planning heuristic function programs can significantly
improve the planning capabilities of LLMs.
67eaa0f83ace6eb46745a9fe
Augusto B. Corrêa
claimed_verified
2025-03-31T15:15:12.565Z
674f43d6df6fa102409f6d1a
https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/KT_-dmXWshUKvbhtn-LSs.png
Augusto B. Corrêa
user
abcorrea
67eaa0f83ace6eb46745a9ff
André G. Pereira
claimed_verified
2025-03-31T15:15:13.942Z
662fb9c891587703a677856e
/avatars/9cb7f035a513279532fc205ce9c5902c.svg
Andre Grahl Pereira
user
andregrahl
67eaa0f83ace6eb46745aa00
Jendrik Seipp
claimed_verified
2025-04-01T07:47:39.862Z
66f3dfd4b8703dde248f6d26
/avatars/c199c91d422500cc7c7556569291644d.svg
Jendrik Seipp
user
jendrikseipp
Classical Planning with LLM-Generated Heuristics: Challenging the State
  of the Art with Python Code
In recent years, large language models (LLMs) have shown remarkable
capabilities in various artificial intelligence problems. However, they fail to
plan reliably, even when prompted with a detailed definition of the planning
task. Attempts to improve their planning capabilities, such as chain-of-thought
prompting, fine-tuning, and explicit "reasoning" still yield incorrect plans
and usually fail to generalize to larger tasks. In this paper, we show how to
use LLMs to generate correct plans, even for out-of-distribution tasks of
increasing size. For a given planning domain, we ask an LLM to generate several
domain-dependent heuristic functions in the form of Python code, evaluate them
on a set of training tasks within a greedy best-first search, and choose the
strongest one. The resulting LLM-generated heuristics solve many more unseen
test tasks than state-of-the-art domain-independent heuristics for classical
planning. They are even competitive with the strongest learning algorithm for
domain-dependent planning. These findings are especially remarkable given that
our proof-of-concept implementation is based on an unoptimized Python planner
and the baselines all build upon highly optimized C++ code. In some domains,
the LLM-generated heuristics expand fewer states than the baselines, revealing
that they are not only efficiently computable, but sometimes even more
informative than the state-of-the-art heuristics. Overall, our results show
that sampling a set of planning heuristic function programs can significantly
improve the planning capabilities of LLMs.
LLMs can generate effective heuristics for classical planning tasks, outperforming domain-independent heuristics and competing with specialized learning algorithms.
large language models LLMs chain-of-thought prompting fine-tuning heuristic functions greedy best-first search unseen test tasks domain-independent heuristics efficient computable domain-dependent planning