GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

El artículo presenta GenePlan, un marco novedoso que utiliza algoritmos evolutivos asistidos por modelos de lenguaje grandes para generar planificadores generalizados en Python que minimizan la longitud de los planes en tareas de planificación PDDL, logrando un rendimiento comparable al de los planificadores más avanzados y superando significativamente a otros enfoques basados en LLM.

Lo esencial

¡Claro que sí! Imagina que tienes un juego de lógica muy complicado (como un rompecabezas gigante o un videojuego de estrategia) donde debes mover objetos, subir escaleras o entregar paquetes para ganar. En el mundo de la inteligencia artificial, esto se llama "planificación".

El problema es que, aunque las Inteligencias Artificiales modernas (como los modelos de lenguaje grandes o LLMs) son muy buenas escribiendo poemas o resumiendo noticias, a menudo se pierden cuando tienen que crear un plan paso a paso para ganar estos juegos. Suelen cometer errores o dar soluciones que son demasiado largas y torpes.

Aquí es donde entra GenePlan.

¿Qué es GenePlan? (La analogía del "Entrenador de Atletas")

Imagina que tienes un entrenador muy sabio (el LLM) y un grupo de atletas principiantes (los planes de código).

1. El Objetivo: Quieres que tus atletas aprendan a correr el circuito perfecto (el plan más corto y eficiente) para ganar la carrera en cualquier escenario posible, no solo en uno.
2. El Proceso de Evolución:
   • Generación 1: El entrenador pide a los atletas que corran el circuito. Algunos tropiezan, otros van lento. El entrenador anota sus tiempos.
   • La Selección: El entrenador mira a los que corrieron mejor y les dice: "¡Vosotros dos, sed los padres de la siguiente generación!".
   • La Mezcla (Cruce): El entrenador toma las mejores partes de la estrategia del corredor A (por ejemplo, "gira a la izquierda rápido") y las combina con las del corredor B (por ejemplo, "salta el obstáculo con fuerza") para crear un nuevo atleta híbrido.
   • La Mutación: A veces, el entrenador le da un pequeño "empujón" aleatorio al nuevo atleta: "¡Prueba a correr de espaldas!" o "¡Salta dos veces!". A veces esto es un error, pero a veces descubre un atajo genial.
   • Repetición: Este proceso se repite muchas veces. Los atletas lentos o torpes se quedan fuera, y los nuevos, hijos de los mejores, heredan y mejoran las estrategias.

GenePlan hace exactamente esto, pero en lugar de atletas, usa códigos de programación en Python (instrucciones para la computadora).

¿Cómo funciona en la vida real?

1. El Entrenador (LLM): Es la IA que escribe el código. No le das una solución lista, le dices: "Aquí tienes cómo lo hicieron los mejores de la ronda anterior, intenta mejorarlos".
2. El Campo de Entrenamiento (Dominios PDDL): Son los diferentes juegos o problemas (como mover cajas, subir montañas o entregar periódicos). GenePlan entrena a sus "atletas" en muchos de estos juegos a la vez.
3. El Cronómetro (Evaluación): Cada vez que un nuevo código (un nuevo atleta) intenta resolver los problemas, el sistema mide cuántos pasos dio. ¡Menos pasos es mejor! Si el código falla o se atasca, recibe una puntuación terrible y es descartado.

¿Por qué es tan especial?

• No es solo "adivinar": A diferencia de otras IAs que intentan adivinar la respuesta una sola vez (como cuando le pides a un amigo que te dé una solución y ya), GenePlan aprende y mejora iterativamente. Es como si un equipo de ingenieros revisara un diseño, lo mejorara, lo volviera a probar y lo volviera a mejorar una y otra vez hasta que sea perfecto.
• Es rápido y barato: Una vez que GenePlan ha "entrenado" a su mejor atleta (el código final), ese código puede resolver nuevos problemas en menos de medio segundo y cuesta muy poco dinero generar ese código (apenas unos dólares por dominio).
• Es comprensible: El resultado final no es una "caja negra" misteriosa. Es un código de Python que un humano puede leer y entender: "Ah, mira, primero mueve al personaje aquí, luego coge el objeto, y luego déjalo allá".

El resultado final

En sus pruebas, GenePlan logró ser tan bueno como los mejores planificadores automáticos del mundo (que tardan 30 minutos en pensar la solución), pero GenePlan generó un código que resuelve el problema en milisegundos y que funciona en muchos escenarios diferentes a la vez.

En resumen: GenePlan es como un taller de ingeniería evolutiva donde una IA inteligente toma ideas imperfectas, las mezcla, las mejora y las pule hasta crear un "super-planificador" que resuelve problemas complejos de forma rápida, barata y elegante.

Resumen técnico

Resumen Técnico: GenePlan

1. El Problema

El artículo aborda dos desafíos principales en la planificación automática asistida por Inteligencia Artificial:

1. Limitaciones de los LLMs en la planificación: Aunque los Modelos de Lenguaje Grande (LLMs) han tenido éxito en tareas como la generación de código o la respuesta a preguntas, su rendimiento en tareas de toma de decisiones secuenciales (planificación) ha sido deficiente. Los enfoques directos (como el prompting de cadena de pensamiento o CoT) a menudo generan planes que no son óptimos o que fallan en resolver instancias complejas.
2. Planificación Generalizada vs. Calidad de la Solución: La planificación generalizada busca generar un "planificador" (una estrategia o función) que funcione para múltiples instancias de un mismo dominio, en lugar de resolver un solo problema. Sin embargo, los métodos existentes basados en LLMs suelen centrarse en encontrar soluciones satisfactorias (que funcionen), ignorando la calidad de la solución (longitud del plan, coste óptimo). En aplicaciones prácticas, la eficiencia del plan es crucial.

2. Metodología: GenePlan

Los autores proponen GenePlan (GENeralized Evolutionary Planner), un marco novedoso que trata la planificación generalizada como un problema de optimización asistido por algoritmos evolutivos y LLMs.

Concepto Central

En lugar de pedirle al LLM que genere un plan directamente, GenePlan evoluciona un planificador generalizado escrito en Python. Este planificador es una función (get_plan) que toma una instancia del problema (estado inicial, objetivo, objetos) y devuelve una secuencia de acciones (plan) válida y de alta calidad.

Arquitectura del Algoritmo Evolutivo

El proceso sigue un ciclo evolutivo inspirado en algoritmos genéticos, donde el espacio de búsqueda son fragmentos de código Python válido:

1. Población Inicial: Se inicia con un conjunto de planificadores candidatos (generados mediante prompting CoT o semilla proporcionada).
2. Evaluación de Aptitud (Fitness):
   • Cada planificador candidato se ejecuta sobre un conjunto de tareas de entrenamiento (instancias PDDL).
   • Se valida la salida usando un validador de planes PDDL.
   • La función de aptitud ($\hat{f}$) es el longitud promedio de los planes generados. Si un planificador falla en resolver una instancia, recibe una puntuación de error muy alta.
   • Objetivo: Minimizar la longitud del plan (número de acciones).
3. Selección: Se seleccionan "padres" (planificadores de alto rendimiento) para la siguiente generación. Los autores utilizan una función de temperatura decreciente (hiperbólica) para ajustar la probabilidad de selección, fomentando la exploración al inicio y la explotación al final.
4. Recombinación y Mutación (Asistida por LLM):
   • Los planificadores seleccionados se pasan al LLM en un prompt estructurado (ver Figura 2 del artículo).
   • El prompt incluye el dominio PDDL, ejemplos de código de los padres y sus resultados (éxito/error), e instrucciones explícitas para realizar cruce (combinar componentes lógicos) y mutación (mejorar heurísticas, eliminar redundancias).
   • El LLM genera nuevo código Python.
5. Validación de Código (AST): El código generado se analiza mediante un parser de Árbol de Sintaxis Abstracta (AST) para asegurar que solo use nodos, paquetes y funciones permitidos (actuando como una barrera de seguridad).
6. Reemplazo: Se aplica una estrategia de reemplazo elitista ($\mu + \lambda$). Se mantiene la población de mejor rendimiento y se eliminan los peores planificadores en cada generación.

3. Contribuciones Clave

• Marco de Optimización Evolutiva para Planificación: Extiende el uso de LLMs como optimizadores (anteriormente usado en heurísticas combinatorias) al dominio de la planificación PDDL generalizada.
• Generación de Planificadores Interpretables: A diferencia de los enfoques de "caja negra" de los LLMs, GenePlan produce código Python legible y modificable que implementa estrategias heurísticas específicas del dominio.
• Superioridad sobre Baselines de LLM: Demuestra que el enfoque evolutivo supera significativamente a las técnicas de prompting directo (CoT) en términos de calidad del plan y tasa de éxito.
• Eficiencia de Coste y Tiempo: Muestra que generar un planificador una sola vez es barato (aprox. $1.82 USD por dominio con GPT-4o) y permite resolver nuevas instancias extremadamente rápido (0.49 segundos por tarea), superando a los solucionadores tradicionales en velocidad de inferencia una vez entrenado.

4. Resultados Experimentales

Los autores evaluaron GenePlan en 8 dominios (6 benchmarks existentes y 2 nuevos creados: Trading y Research).

Métricas Principales

• Puntuación SAT: Se utiliza la métrica estándar de la Competición Internacional de Planificación (IPC). Un valor de 1.0 indica que se encontró el plan óptimo.
• Comparativa: Se comparó contra:
  • Fast Downward (FD): El solucionador clásico de referencia (configuraciones LAMA y óptima).
  • LLMs Baseline: CoT con GPT-4 y GPT-4o.
  • Ablaciones: Variantes de GenePlan sin evaluador, con nombres ablatados, etc.

Hallazgos Clave

1. Rendimiento de Calidad: GenePlan logró una puntuación SAT promedio de 0.91, acercándose muy de cerca a Fast Downward con límite de tiempo de 30 minutos (0.93) y superando significativamente a los baselines de LLM (CoT con GPT-4o obtuvo 0.64).
2. Velocidad de Inferencia: Una vez generado el planificador, resuelve instancias nuevas en 0.49 segundos de media, mucho más rápido que los solucionadores de búsqueda clásicos que requieren minutos por problema.
3. Coste: El coste promedio para generar un planificador fue de $1.82 USD por dominio usando GPT-4o.
4. Análisis de Ablación:
   • La eliminación de nombres específicos del dominio (ablatar nombres de predicados/acciones) destruyó el rendimiento, demostrando que el contexto semántico es vital para el LLM.
   • El uso de resúmenes en lenguaje natural en lugar del PDDL completo funcionó bien en dominios simples pero falló en los complejos.
5. Limitaciones: En dominios sin estrategias simples (como Sokoban o Blocksworld con estados irreversibles), GenePlan intentó construir algoritmos de búsqueda internos que fallaron, mientras que los solucionadores tradicionales (FD) tuvieron éxito. Esto sugiere que GenePlan es ideal para dominios con estrategias heurísticas reutilizables.

5. Significado e Impacto

El trabajo de GenePlan es significativo porque cierra la brecha entre la capacidad de razonamiento de los LLMs y la necesidad de soluciones óptimas en planificación automática.

• Paradigma Híbrido: Propone un modelo donde el LLM actúa como un "ingeniero de algoritmos" que evoluciona y refina heurísticas, en lugar de simplemente generar planes paso a paso.
• Escalabilidad: Ofrece una solución viable para entornos donde se necesitan resolver miles de instancias de planificación similares (ej. logística, gestión de recursos), ya que el coste computacional se paga una sola vez durante la generación del planificador.
• Interpretabilidad: Al generar código Python, los planificadores resultantes pueden ser auditados, depurados y comprendidos por humanos, a diferencia de las políticas neuronales opacas.

En conclusión, GenePlan demuestra que combinar la capacidad de generación de código de los LLMs con la robustez de los algoritmos evolutivos permite crear planificadores generalizados de alta calidad, competitivos con los mejores solucionadores clásicos, pero con una velocidad de ejecución superior y un coste de generación razonable.