STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

El artículo presenta STRUCTUREDAGENT, un marco de planificación jerárquica que utiliza árboles AND/OR dinámicos y un módulo de memoria estructurada para superar las limitaciones de los agentes web actuales en tareas de navegación a largo plazo, mejorando significativamente su rendimiento y capacidad de depuración.

Lo esencial

¡Claro que sí! Imagina que quieres que un robot (o una Inteligencia Artificial) vaya a internet a hacer una tarea complicada, como "Encontrar 3 recetas de brownies veganos con más de 4 estrellas y que cuesten menos de $10".

Los agentes de IA actuales suelen ser como niños muy entusiastas pero sin mapa: ven algo que parece bueno, lo hacen, y si se equivocan, se rinden o se pierden. A veces, la página web es tan larga que el robot olvida lo que vio hace cinco pasos.

Este paper presenta a STRUCTUREDAGENT, un nuevo tipo de agente que es como un arquitecto experto con un plano de construcción. Aquí te explico cómo funciona usando analogías sencillas:

1. El Problema: El "Viajero Sin Mapa"

Imagina que intentas llegar a una ciudad desconocida.

• Los agentes viejos: Son como alguien que camina mirando solo el suelo a sus pies. Si se tropieza, se queda ahí. Si ven una calle que parece bien, la toman sin pensar en el destino final. Si la página web es gigante (como un libro de 200 páginas), se les olvida lo que leyeron al principio.
• El resultado: Se cansan, se frustran y terminan la tarea antes de tiempo o con respuestas incorrectas.

2. La Solución: El "Arquitecto con Plano AND/OR"

STRUCTUREDAGENT no camina a ciegas. Tiene un plano de construcción (un árbol de decisiones) que va dibujando mientras avanza.

Imagina que el plano tiene dos tipos de habitaciones:

• Habitaciones "Y" (AND): Son como una lista de compras obligatoria. Para que la misión sea un éxito, TODAS las cosas deben pasar.
  • Ejemplo: Para hacer un brownie, Necesitas (Y) harina, Y chocolate, Y huevos. Si te falta uno, no hay brownie. El agente se asegura de completar cada paso de la lista.
• Habitaciones "O" (OR): Son como tener varias rutas para llegar a la misma meta.
  • Ejemplo: Para encontrar el chocolate, puedes O ir al supermercado, O ir a la tienda de barrio, O pedirlo por internet. Si el supermercado está cerrado (falla), el agente no se rinde; simplemente toma la ruta "O" (la tienda de barrio) y sigue.

La magia: El agente no solo sigue el plano, lo dibuja en tiempo real. Si una ruta falla, borra esa parte del plano y dibuja una nueva al instante.

3. La "Carpeta de Notas Inteligente" (Memoria Estructurada)

Los agentes normales suelen tener una "memoria de pez" o toman notas desordenadas en un papel arrugado. Si encuentran un producto bueno pero luego ven otro, a veces olvidan el primero.

STRUCTUREDAGENT tiene una Carpeta de Notas Inteligente (un módulo de memoria estructurada).

• Imagina una hoja de cálculo (Excel) que se actualiza sola.
• Cada vez que el agente ve un producto, lo anota en la hoja con sus características: "Brownie A: 4 estrellas, $8. Brownie B: 5 estrellas, $12".
• Si el agente se equivoca y el Brownie A no cumple una regla, la carpeta lo marca automáticamente y le dice: "Oye, no uses este, mira el siguiente".
• Esto evita que el agente vuelva a visitar páginas que ya sabe que no le sirven.

4. El "Supervisor Humano" (Interpretabilidad)

A veces, el agente puede tener una idea equivocada sobre cómo empezar.

• En los sistemas viejos, si el agente se equivoca, nadie sabe por qué hasta que falla todo.
• Con STRUCTUREDAGENT, como tiene un plano visual (el árbol), un humano puede mirar el plano y decir: "Espera, no empieces buscando en Google, empieza yendo a la tienda". El agente puede corregir el plano en ese momento exacto. Es como tener un copiloto que puede ver el mapa y corregir la ruta antes de que el coche se estrelle.

Resumen en una frase

STRUCTUREDAGENT es como un detective que no solo busca pistas, sino que lleva un cuaderno de investigación organizado donde anota cada pista, dibuja un mapa de rutas alternativas (si una calle está cerrada, toma otra) y nunca olvida lo que ya descubrió, lo que le permite resolver misterios muy largos y complejos en internet sin perderse.

¿Por qué es importante?
Porque ahora podemos confiar en que la IA puede hacer tareas largas y difíciles (como comprar cosas específicas, investigar datos complejos o llenar formularios largos) sin cometer errores tontos por olvidarse de lo que hizo hace un minuto.

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo "STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks" en español:

1. El Problema

Los agentes impulsados por Modelos de Lenguaje Grande (LLM) han avanzado significativamente, pero aún enfrentan dificultades críticas al realizar tareas web de largo horizonte (complejas, con múltiples pasos y dependencias temporales). Las limitaciones principales identificadas son:

• Memoria limitada en contexto: Los agentes no pueden rastrear eficazmente el historial de soluciones alternativas a través de múltiples páginas web, especialmente cuando el contenido de una página supera los 20k tokens.
• Debilidad en la planificación: Incapacidad para construir y ejecutar planes complejos a lo largo de horizontes temporales extendidos.
• Falta de mecanismos de recuperación de errores: Dificultad para recuperarse de fallos y explorar soluciones alternativas.
• Comportamiento codicioso (Greedy): Tendencia a terminar tareas prematuramente sin satisfacer todas las restricciones del usuario, a menudo debido a la falta de retroalimentación de errores (back-propagation).

2. Metodología: STRUCTUREDAGENT

El autores proponen STRUCTUREDAGENT, un marco de planificación jerárquica que intercala la planificación y la ejecución. Su núcleo se basa en dos componentes principales:

A. Planificador Jerárquico con Árboles AND/OR Dinámicos

En lugar de confiar en que el LLM genere todo el plan de una vez, el marco construye y mantiene explícitamente un árbol de planificación dinámico durante la ejecución:

• Estructura del Árbol:
  • Nodos AND: Representan subobjetivos conjuntivos (todos deben tener éxito).
  • Nodos OR: Representan estrategias alternativas (basta con que una tenga éxito).
  • Nodos de Acción (Hojas): Operaciones atómicas del navegador (clic, escribir, desplazarse, volver, anotar).
• Algoritmo de Búsqueda: Utiliza una Búsqueda en Profundidad (DFS) modificada y codiciosa. A diferencia del DFS clásico en grafos estáticos, este algoritmo construye y mantiene el árbol incrementalmente.
• Estados de Ejecución: Los nodos tienen estados dinámicos (ENTERING, EXITING, FAILED) que permiten la propagación de cambios estructurales y fallos hacia arriba en el árbol.
• Operaciones del Árbol: El marco gestiona el árbol directamente y llama al LLM solo para operaciones específicas y bien definidas:
  • Expansión de nodos: Determinar el tipo de nodo y generar hijos.
  • Reparación de nodos: Modificar o podar nodos fallidos.
  • Verificación de completitud: Evaluar si un nodo AND ha cumplido su objetivo.
  • Resumen de observaciones: Condensar el estado del entorno para mantener la memoria.

B. Módulo de Memoria Estructurada

Para tareas de búsqueda de información (como compras o investigación), se introduce un módulo de memoria que rastrea entidades candidatas y las restricciones que satisfacen.

• Funciona como una tabla dinámica donde cada fila es un candidato y las columnas son atributos/restricciones.
• Permite al agente recuperar los Top-K candidatos que satisfacen más restricciones, evitando la exploración redundante y mejorando el cumplimiento de múltiples restricciones simultáneas.

3. Contribuciones Clave

1. Marco de Planificación Jerárquica: Introducen un sistema que permite la planificación en tiempo de inferencia mediante árboles AND/OR ordenados, soportando razonamiento composicional, revisión dinámica de planes y retropropagación de errores.
2. Interpretabilidad y Control Humano: La estructura del árbol genera planes interpretables, lo que facilita la depuración y permite la intervención humana (por ejemplo, un operador puede corregir la descomposición de subobjetivos incorrectos en cualquier nivel del árbol).
3. Módulo de Memoria Estructurada: Desarrollo de un mecanismo específico para rastrear candidatos y restricciones en tareas de información, superando las limitaciones de la toma de notas no estructurada.
4. Separación de Responsabilidades: El marco gestiona la estructura del árbol y la lógica de navegación, mientras que el LLM actúa como un controlador de alto nivel para operaciones locales, mejorando la robustez y reduciendo la carga cognitiva del modelo.

4. Resultados Experimentales

El marco se evaluó en tres benchmarks: WebVoyager, WebArena y un benchmark personalizado de compras en Amazon (Amazon Easy/Hard).

• Rendimiento General: STRUCTUREDAGENT superó consistentemente a las líneas base (AgentOccam, BasicClaudeAction, SteP) en tareas de largo horizonte.
  • En Amazon Easy, logró una tasa de éxito promedio del 83.3%, superando a AgentOccam en un 14%.
  • En Amazon Hard (tareas complejas de múltiples restricciones), obtuvo un 37.8% (evaluación humana), superando a las líneas base en al menos un 7-14%.
  • En WebArena, alcanzó la puntuación general más alta (52.6%), destacando particularmente en las categorías de Shopping y Reddit.
• Robustez del Modelo: Los beneficios de la planificación jerárquica persistieron incluso al usar modelos base más fuertes (Claude 3.7), demostrando que la arquitectura aporta valor más allá de la capacidad bruta del LLM.
• Eficiencia: Aunque en tareas muy difíciles el agente realiza más acciones (debido a una exploración más exhaustiva y recuperación de errores), en tareas de éxito alto mantiene una longitud de trayectoria comparable a las líneas base, evitando el colapso prematuro.

5. Significancia

Este trabajo es significativo porque aborda la brecha entre la capacidad de razonamiento de los LLMs y la necesidad de ejecución robusta en entornos dinámicos y parcialmente observables (la web).

• Cambio de Paradigma: Mueve el enfoque de "generar un plan completo" a "construir y adaptar un plan estructurado", alineándose más con la resolución de problemas humana (búsqueda heurística y análisis medios-fines).
• Resolución de Fallos: La capacidad de propagar errores y podar/reparar ramas del árbol permite a los agentes recuperarse de fallos locales sin abandonar la tarea global.
• Escalabilidad: La separación entre la gestión del árbol (framework) y la inferencia (LLM) hace que el sistema sea más interpretable y menos propenso a alucinaciones en la planificación a largo plazo.

En resumen, STRUCTUREDAGENT demuestra que integrar estructuras de planificación explícitas (árboles AND/OR) y memoria estructurada es esencial para crear agentes web autónomos capaces de manejar tareas complejas, de múltiples pasos y con restricciones estrictas.