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

Il paper presenta STRUCTUREDAGENT, un framework di pianificazione gerarchica che utilizza alberi AND/OR dinamici e un modulo di memoria strutturata per migliorare le prestazioni degli agenti LLM su compiti web a lungo orizzonte, superando le limitazioni degli approcci esistenti in termini di memoria, pianificazione e comportamento greedy.

L'essenziale

🌐 STRUCTUREDAGENT: Il "Capo Cantiere" Intelligente per il Web

Immagina di dover organizzare un viaggio complesso per un gruppo di amici. Devi trovare voli, hotel, ristoranti e attività, rispettando budget, gusti personali e orari. Se provassi a farlo tutto a mente, senza scrivere nulla, probabilmente ti perderesti, dimenticheresti un volo o prenoteresti un hotel che non ha la piscina che volevi.

I LLM (i modelli di intelligenza artificiale come me) sono molto bravi a parlare, ma quando devono navigare su internet per compiti lunghi e complessi, spesso agiscono come qualcuno che cerca di organizzare quel viaggio senza prendere appunti e senza un piano. Si perdono, dimenticano cosa hanno fatto prima e si arrendono troppo presto.

STRUCTUREDAGENT è la soluzione a questo problema. È come trasformare l'agente da un "turista sperduto" in un "Capo Cantiere" esperto.

Ecco come funziona, diviso in due grandi idee:

1. La Mappa del Tesoro (L'Albero AND/OR) 🗺️

Invece di camminare a caso, STRUCTUREDAGENT costruisce una mappa mentale a forma di albero (chiamata albero AND/OR) mentre naviga.

• Il Nodo "E" (AND): Immagina di dover preparare una cena. Per farla, devi avere gli ingredienti E le pentole E il fuoco. Se manca anche solo uno di questi, la cena non si fa. L'agente sa che deve completare tutti questi passaggi obbligatori.
• Il Nodo "O" (OR): Ora immagina di dover scegliere il vino. Puoi prendere un Rosso O un Bianco. Se il Rosso è finito, l'agente non si blocca e non va in crash; passa semplicemente al Bianco. L'albero permette di avere piani di riserva pronti all'uso.

L'analogia del "Gioco delle Scale":
Pensa a un vecchio gioco dove devi salire una scala. Se ti fermi su un gradino sbagliato, un agente normale potrebbe cadere e dire "Non ce la faccio". STRUCTUREDAGENT, invece, ha una scala mobile intelligente: se un gradino crolla (un errore), può immediatamente saltare su un altro ramo della scala (un piano alternativo) senza dover ricominciare da capo.

2. Il Quaderno degli Appunti Strutturato (Structured Memory) 📓

Il secondo grande problema degli agenti web è la "memoria a breve termine". Se un agente legge 20 pagine web, dopo un po' dimentica cosa c'era nella pagina 1.

STRUCTUREDAGENT ha un quaderno speciale. Non scrive tutto a caso come un diario disordinato.

• Se stai cercando 3 laptop sotto i 500€, il quaderno crea una tabella.
• Riga 1: Laptop A (Prezzo: 450€, RAM: 8GB, Stato: Promettente).
• Riga 2: Laptop B (Prezzo: 600€, RAM: 16GB, Stato: Scartato - troppo caro).

Questo permette all'agente di non perdere mai di vista i suoi obiettivi. Se trova un'offerta migliore, aggiorna la riga. Se un prodotto non è più disponibile, lo cancella. È come avere un assistente personale che tiene traccia di tutte le opzioni mentre tu guardi il panorama.

🛠️ Come agisce nella vita reale?

Immagina di chiedere all'agente: "Trova una ricetta di brownie vegani con rating 4 stelle o più su AllRecipes".

1. Pianificazione: L'agente non clicca subito. Disegna l'albero:
   • Obiettivo: Trova ricetta.
   • Sotto-obiettivo 1 (E): Cerca "brownie vegani".
   • Sotto-obiettivo 2 (E): Controlla il rating.
   • Sotto-obiettivo 3 (O): Se la prima ricetta non va bene, prova la seconda o la terza.
2. Esecuzione: Clicca, legge, e scrive nel suo Quaderno Strutturato: "Brownie A: Rating 3.5 (Scartato)".
3. Recupero dall'errore: Se clicca sul link sbagliato e la pagina è rotta, invece di arrendersi, l'albero gli dice: "Ok, questo ramo è rotto. Torna indietro e prova il ramo 'Sotto-obiettivo 2' con un'altra strategia".
4. Intervento Umano (Opzionale): Se l'agente si blocca, un umano può guardare la mappa, vedere dove ha sbagliato il ragionamento e correggere il percorso, proprio come un capitano che corregge la rotta a un pilota automatico.

🏆 Perché è meglio degli altri?

Gli studi mostrano che STRUCTUREDAGENT vince perché:

• Non è "avido": Non si accontenta della prima cosa che trova se non è perfetta. Esplora le alternative.
• Non dimentica: Il quaderno strutturato gli permette di gestire compiti lunghissimi (come fare la spesa online con 10 regole diverse) senza impazzire.
• È spiegabile: Se fallisce, possiamo guardare l'albero e vedere esattamente dove ha sbagliato il ragionamento, invece di avere una scatola nera che dice solo "non so farlo".

In sintesi 🌟

STRUCTUREDAGENT è come dare a un'intelligenza artificiale:

1. Una mappa strategica che prevede piani A, B e C.
2. Un quaderno organizzato per non dimenticare nulla.
3. La capacità di riconoscere gli errori e ripartire senza perdere tempo.

È il passaggio dal "cliccare a caso sperando di indovinare" al "pianificare, eseguire e correggere come un professionista".

Sommario tecnico

1. Il Problema

Gli agenti basati su Large Language Models (LLM) hanno mostrato progressi significativi nel prendere decisioni sequenziali, ma faticano ancora di fronte a compiti web a lungo orizzonte (long-horizon tasks). Le principali limitazioni degli agenti web esistenti includono:

• Memoria contestuale limitata: Difficoltà nel tracciare la storia delle azioni e le soluzioni alternative attraverso molteplici pagine web, specialmente quando le pagine sono dense (spesso >20k token).
• Debolezza nella pianificazione: Incapacità di costruire ed eseguire piani complessi su finestre temporali estese.
• Mancanza di gestione degli errori: Assenza di meccanismi robusti per recuperare dai fallimenti ed esplorare soluzioni alternative.
• Comportamenti "greedy": Tendenza a terminare prematuramente i compiti senza soddisfare tutti i vincoli dell'utente, spesso a causa di una mancanza di esplorazione sistematica.

2. Metodologia: STRUCTUREDAGENT

Gli autori propongono STRUCTUREDAGENT, un framework di pianificazione gerarchica che interseca pianificazione ed esecuzione. Il sistema si basa su due componenti principali:

A. Pianificatore Gerarchico Online con Alberi AND/OR

Il cuore del sistema è un albero di pianificazione AND/OR costruito e mantenuto dinamicamente durante l'esecuzione del compito.

• Struttura dell'Albero:
  • Nodi AND: Rappresentano sotto-obiettivi congiuntivi (tutti i figli devono avere successo).
  • Nodi OR: Rappresentano strategie alternative (basta che un figlio abbia successo).
  • Nodi ACTION: Foglie che corrispondono a operazioni atomiche del browser (click, type, scroll, note).
• Algoritmo di Ricerca: Utilizza una Ricerca in Profondità (DFS) modificata e greedy. A differenza della DFS classica, questa versione supporta:
  • Stati di esecuzione: I nodi possono transire tra stati ENTERING (in ingresso), EXITING (in uscita) e FAILED (fallito).
  • Revisione e Potatura (Pruning): Se un nodo fallisce, il sistema può tentare di ripararlo (aggiungendo o modificando figli) o potare il ramo. I fallimenti si propagano verso l'alto, invalidando i fratelli successivi nei nodi AND ordinati.
  • Separazione dei compiti: Il framework gestisce la struttura dell'albero e la logica di navigazione, mentre l'LLM viene invocato solo per operazioni locali ben definite (espansione nodi, riparazione, verifica completamento).

B. Modulo di Memoria Strutturata

Per i compiti di ricerca di informazioni, viene introdotto un modulo di memoria che traccia le entità candidate e i vincoli soddisfatti.

• Funziona come una tabella dinamica dove ogni riga rappresenta un'entità candidata e le colonne catturano attributi e vincoli.
• Durante l'esplorazione, l'agente aggiunge, aggiorna o elimina voci basandosi sulle nuove osservazioni.
• Durante la decisione (espansione dei nodi), vengono recuperati i top-K candidati che soddisfano il maggior numero di vincoli, riducendo l'esplorazione ridondante.

3. Contributi Chiave

1. Framework di Pianificazione Gerarchica: Introduzione di un sistema che utilizza alberi AND/OR ordinati per abilitare il ragionamento composizionale, la revisione dinamica dei piani e la propagazione degli errori, producendo piani interpretabili che facilitano il debugging e l'intervento umano.
2. Memoria Strutturata: Sviluppo di un modulo specifico per tracciare entità candidate e vincoli, migliorando significativamente la soddisfazione dei vincoli nei compiti di ricerca complessi.
3. Interpretabilità e Intervento Umano: La struttura ad albero permette a un operatore umano di ispezionare la decomposizione dei sottoproblemi e correggere errori (es. decomposizioni errate) in qualsiasi livello dell'albero prima che l'esecuzione proceda.

4. Risultati Sperimentali

Il framework è stato valutato su tre benchmark principali: WebVoyager, WebArena e un benchmark personalizzato per lo shopping su Amazon (Amazon Easy/Hard).

• Prestazioni Generali: STRUCTUREDAGENT ha superato gli agenti basati su LLM standard (come AgentOccam, BasicClaudeAction, SteP) nella maggior parte dei compiti a lungo orizzonte.
  • Su Amazon Easy, ha raggiunto una percentuale di successo media del 83.3%, superando AgentOccam del 14%.
  • Su Amazon Hard (compiti complessi con molti vincoli), ha ottenuto il miglior punteggio nella valutazione umana (35.6% vs 28.4% di AgentOccam) e ha mostrato un miglioramento del 5% con l'aggiunta del modulo di memoria strutturata.
  • Su WebArena, ha ottenuto il punteggio complessivo più alto (52.6%), con particolare forza nei compiti di Shopping e Reddit.
• Efficienza e Traiettorie: Sebbene STRUCTUREDAGENT compia un numero leggermente maggiore di azioni rispetto agli agenti greedy su compiti difficili (riflettendo un'esplorazione più sistematica), evita la terminazione prematura. Su compiti più semplici, le prestazioni sono comparabili.
• Generalizzazione: I benefici del framework si sono dimostrati validi anche quando si utilizzano modelli LLM diversi (es. Kimi-k2) come backbone, non solo Claude.

5. Significato e Impatto

Il lavoro di STRUCTUREDAGENT è significativo perché affronta il problema fondamentale della robustezza e dell'interpretabilità negli agenti web autonomi.

• Superamento del "Greedy Behavior": Dimostra che separare la gestione della struttura di ricerca (albero) dalla generazione delle azioni (LLM) permette di evitare errori comuni come la terminazione prematura.
• Recupero dagli Errori: La capacità di propagare i fallimenti e riparare dinamicamente i piani rende gli agenti molto più resilienti in ambienti web stocastici e parzialmente osservabili.
• Human-in-the-Loop: La natura interpretabile dell'albero AND/OR offre un canale chiaro per l'intervento umano, permettendo di correggere errori di ragionamento che gli LLM autonomi non riuscirebbero a rilevare da soli.

In sintesi, STRUCTUREDAGENT rappresenta un passo avanti verso agenti web capaci di gestire compiti complessi e multi-step con un livello di affidabilità e trasparenza paragonabile al problem-solving umano.