pipette
ENEnglish

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

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

PreprintDice ser un gran avance

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

En palabras simples Resumen con IA

Los grandes modelos de lenguaje pueden crear funciones heurísticas que guían la búsqueda para tareas de planificación, pero estas heurísticas pueden no ser admisibles y pueden producir planes subóptimos. LeanPlan es el primer sistema que encuentra planes óptimos usando heurísticas generadas por LLM con pruebas de admisibilidad verificadas por máquina. El sistema usa un bucle agentico con retroalimentación del planificador para mejorar iterativamente una heurística reutilizable específica del dominio, su prueba y las suposiciones de dominio requeridas. LeanPlan implementa la heurística, la prueba y el planificador con fundamentación y búsqueda verificadas por máquina en Lean 4. Evaluado en trece dominios con tareas de prueba hasta 57 veces más grandes que las de entrenamiento, LeanPlan con GPT-5.6 Sol generó exitosamente heurísticas y pruebas para todos los dominios. Con estas heurísticas, LeanPlan usualmente expande menos estados que el planificador Scorpion de última generación y resuelve más tareas en total.

Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.