Phase 14 - Lesson 11

Planificación con HTN y Búsqueda Evolutiva

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

La planificación simbólica maneja los casos en los que el plan es demostrablemente correcto. La búsqueda evolutiva de código maneja los casos en los que la función de aptitud (fitness) es verificable por máquina. ChatHTN (2025) y AlphaEvolve (2025) muestran lo que cada uno desbloquea cuando se combina con un LLM.

Tipo: Build Lenguajes: Python (stdlib) Prerrequisitos: Phase 14 · 02 (ReWOO and Plan-and-Execute) Tiempo: ~75 minutos

Objetivos de Aprendizaje

• Explicar Hierarchical Task Networks: tareas, métodos, operadores, precondiciones, efectos.
• Describir el loop híbrido de ChatHTN: búsqueda simbólica con descomposición de fallback del LLM.
• Explicar el loop evolutivo de AlphaEvolve y por qué solo funciona con un evaluador programático.
• Implementar un planificador HTN de juguete más una búsqueda evolutiva de juguete en la stdlib.

El Problema

ReWOO (Lesson 02), Plan-and-Execute y ReAct cubren la mayor parte de la planificación de agentes. Dos casos que no cubren bien:

1. Planes con corrección demostrable. Programación (scheduling), rutas de vuelo, flujos de trabajo de cumplimiento; el plan debe ser seguro por construcción. Un plan de LLM fluido que a veces alucina un paso es inaceptable.
2. Optimizaciones con una función de aptitud verificable por máquina. Multiplicación de matrices, heurísticas de programación, pasadas de compilador; el objetivo no es "un plan correcto" sino "el mejor plan".

La planificación HTN y AlphaEvolve resuelven los dos problemas diferentes. Ambos usan LLMs como amplificadores, no como reemplazos.

El Concepto

Hierarchical Task Networks

Un HTN consiste en:

• Tareas — compuestas (a ser descompuestas) y primitivas (directamente ejecutables).
• Métodos — formas de descomponer una tarea compuesta en subtareas, con precondiciones.
• Operadores — acciones primitivas con precondiciones y efectos.
• Estado — un conjunto de hechos.

Planificación: dada una tarea objetivo y un estado inicial, encontrar una descomposición en operadores primitivos cuyas precondiciones se cumplan en secuencia.

HTN es anterior a los LLMs y sigue siendo la referencia para planes demostrablemente correctos.

ChatHTN (Gopalakrishnan et al., 2025)

ChatHTN (arXiv:2505.11814) intercala HTN simbólico con consultas a LLM:

1. Intentar descomponer la tarea compuesta actual con los métodos existentes.
2. Si no se aplica ningún método, preguntar al LLM: "¿cómo descompondrías task en el estado s?"
3. Traducir la respuesta del LLM en subtareas candidatas.
4. Validar contra el esquema del operador; rechazar descomposiciones inválidas.
5. Ejecutar recursivamente.

La afirmación central del artículo: cada plan producido es demostrablemente seguro porque las sugerencias del LLM solo ingresan como descomposiciones candidatas, nunca como ediciones directas del plan. La capa simbólica se encarga de la corrección; el LLM expande la biblioteca de métodos.

El aprendizaje de métodos en línea (seguimiento en OpenReview gwYEDY9j2x, 2025) añade un aprendiz que generaliza las descomposiciones producidas por el LLM mediante regresión, reduciendo la frecuencia de consultas al LLM hasta en un 75%.

AlphaEvolve (Novikov et al., 2025)

AlphaEvolve (arXiv:2506.13131, DeepMind, junio de 2025) es una propuesta diferente: búsqueda evolutiva de código orquestada por un ensemble de Gemini 2.0 Flash/Pro.

Loop:

1. Comenzar con un programa semilla + un evaluador programático (que devuelve una puntuación de aptitud).
2. Un ensemble de LLMs propone mutaciones.
3. Ejecutar las mutaciones a través del evaluador.
4. Mantener la mejor; mutar de nuevo.

Logros publicados:

• Primera mejora sobre Strassen para la multiplicación de matrices complejas de 4x4 en 56 años (48 multiplicaciones escalares).
• 0.7% de cómputo de Google recuperado a través de una heurística de programación de Borg.
• Aceleración del 32% de FlashAttention en una carga de trabajo de frontera.

La restricción estricta: la función de aptitud debe ser verificable por máquina. La búsqueda evolutiva sobre respuestas en prosa no converge.

Cuándo usar cuál

Dónde falla este patrón

• HTN sin operadores. Sin esquemas de precondición/efeito, la afirmación de seguridad se derrumba. La "sugerencia de descomposición del LLM" de ChatHTN requiere el esquema para rechazar movimientos inválidos.
• AlphaEvolve sin un evaluador real. "Preguntar al LLM si el código es mejor" no es una función de aptitud. El evaluador debe ser determinístico y rápido.
• Sobreingeniería. La mayoría de las tareas de agentes no necesitan ninguno de los dos. Recurre a ReAct o ReWOO primero.

Constrúyelo

El archivo code/main.py implementa dos ejemplos de juguete:

• Un planificador HTN en la stdlib con operadores, métodos, precondiciones, efectos y un LLMFallback que se activa cuando ningún método coincide con una tarea compuesta. El "LLM" es un descomponedor programado para que el planificador se ejecute sin conexión (offline).
• Una búsqueda evolutiva en la stdlib sobre programas aritméticos: desarrolla expresiones cuya salida minimiza |f(x) - target| sobre un conjunto de prueba. El evaluador es determinista.

Ejecútalo:

python3 code/main.py

La traza muestra al planificador HTN descomponiendo una tarea compuesta (con un fallback del LLM en mitad del plan) y el loop evolutivo convergiendo en una expresión objetivo.

Úsalo

• Planificadores HTN — pyhop, SHOP3 o construye el tuyo propio para la aplicación de políticas específicas del dominio.
• ChatHTN — código de investigación; el patrón (simbólico + fallback de LLM) se traslada limpiamente a cualquier planificador HTN.
• AlphaEvolve — artículo de DeepMind; el patrón (ensemble + evaluador) es reproducible. Están surgiendo OpenEvolve y bifurcaciones (forks) similares de código abierto.
• Frameworks de agentes — ninguno incluye HTN o AlphaEvolve nativos todavía. Constrúyelo como un subagente o un trabajador en segundo plano (background worker).

Ship It

El archivo outputs/skill-hybrid-planner.md genera un andamio (scaffold) de planificador híbrido (HTN o evolutivo) con el rol del LLM explícitamente delimitado.

Ejercicios

1. Extiende el planificador HTN con backtracking: cuando una poscondición del operador falle en tiempo de ejecución, revierte los cambios (roll back) e intenta el siguiente método.
2. Añade una caché de método-LLM a ChatHTN: cuando el LLM descomponga la tarea T en el patrón de estado P, almacena el resultado. Vuelve a comprobar la biblioteca de métodos primero en la siguiente llamada.
3. Cambia el evaluador de búsqueda evolutiva por una suite de pruebas real. Evoluciona una función de ordenación que pase 20 casos de prueba; reporta las generaciones hasta la convergencia.
4. Lee las notas de diseño del evaluador de AlphaEvolve. Diseña un evaluador para un dominio de tu interés (optimización de consultas SQL, minimización de suites de pruebas, YAML de despliegue).
5. Combina: usa HTN para descomponer una tarea compuesta en subtareas, luego usa la búsqueda evolutiva en el operador primitivo de cada subtarea. ¿Dónde destaca y dónde resulta en sobreingeniería?

Términos Clave

Lectura Adicional

• Gopalakrishnan et al., ChatHTN (arXiv:2505.11814) — planificador híbrido simbólico + LLM
• Novikov et al., AlphaEvolve (arXiv:2506.13131) — búsqueda evolutiva de código con mutaciones de LLM
• Anthropic, Building Effective Agents — cuándo recurrir a un planificador en lugar de a un loop simple