pipette
ESEspañol

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

Andr\'{e} G. Pereira, Augusto B. Corr\^ea, Felipe Meneguzzi, Jendrik Seipp

PreprintClaims a big step

In the authors' words

Frontier large language models (LLMs) can generate heuristic functions that guide search to achieve state-of-the-art performance in satisficing planning, where any plan is acceptable. However, these heuristics are not guaranteed to be admissible and can lead to suboptimal plans. We introduce LeanPlan, the first planning system that finds optimal plans with LLM-generated heuristics whose admissibility is machine-checked. Given a domain description and training tasks, an agentic loop uses planner feedback to iteratively improve a reusable domain-specific heuristic, its admissibility proof and the required domain assumptions. LeanPlan implements the heuristic, its proof and an efficient planner with machine-checked grounding and search in Lean 4. We evaluate LeanPlan on ten domains from the International Planning Competition and three new domains, using test tasks with up to 57 times as many objects as the training tasks. With GPT-5.6 Sol in the agentic loop, we successfully generate heuristics and admissibility proofs for all these domains. With the resulting heuristics, LeanPlan usually expands fewer states than the state-of-the-art Scorpion planner and solves more tasks overall.

Main resultThe abstract does not state a limitation.

In plain words AI summary

Large language models can create heuristic functions that guide search for planning tasks, but these heuristics may not be admissible and can produce suboptimal plans. LeanPlan is the first system that finds optimal plans using LLM-generated heuristics with machine-checked admissibility proofs. The system uses an agentic loop with planner feedback to iteratively improve a reusable domain-specific heuristic, its proof, and required domain assumptions. LeanPlan implements the heuristic, proof, and planner with machine-checked grounding and search in Lean 4. Evaluated on thirteen domains with test tasks up to 57 times larger than training tasks, LeanPlan with GPT-5.6 Sol successfully generated heuristics and proofs for all domains. With these heuristics, LeanPlan usually expands fewer states than the state-of-the-art Scorpion planner and solves more tasks overall.

Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.