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

Le papier présente STRUCTUREDAGENT, un cadre de planification hiérarchique intégrant des arbres AND/OR dynamiques et une mémoire structurée pour surmonter les limites des agents web actuels dans l'exécution de tâches complexes à long horizon.

L'essentiel

Imaginez que vous essayez de trouver un cadeau parfait sur Internet pour quelqu'un de très exigeant. Vous devez respecter une liste de règles précises : le prix, la couleur, la marque, et le délai de livraison.

Les "agents" (des robots intelligents) actuels qui naviguent sur le web sont un peu comme des touristes pressés et un peu étourdis. Ils regardent la page actuelle, prennent une décision rapide, et s'ils se trompent de chemin, ils paniquent, recommencent tout depuis le début, ou abandonnent parce qu'ils ont oublié ce qu'ils cherchaient exactement. C'est ce qu'on appelle un comportement "gourmand" : ils veulent la solution immédiate, même si elle est imparfaite.

STRUCTUREDAGENT, c'est comme si on donnait à ce robot un chef d'orchestre et un cahier de notes très organisé.

Voici comment cela fonctionne, avec des images simples :

1. L'Arbre de Décision (Le Plan de Construction)

Au lieu d'avancer au hasard, STRUCTUREDAGENT construit une carte au trésor en forme d'arbre (appelée arbre AND/OR).

• Les nœuds "ET" (AND) : Imaginez que vous devez construire une maison. Pour que la maison soit finie, vous devez à la fois poser les fondations ET construire les murs ET mettre le toit. Tous ces éléments sont obligatoires. Dans l'arbre, ce sont des branches qui doivent toutes réussir.
• Les nœuds "OU" (OR) : Maintenant, imaginez que vous devez traverser une rivière. Vous pouvez soit nager, soit prendre un pont, soit utiliser un bateau. Vous n'avez besoin que d'une seule de ces options pour réussir. C'est une branche où le robot peut choisir le meilleur chemin.

L'astuce géniale : Si le robot essaie de traverser la rivière à la nage et échoue (il a froid !), il ne panique pas. Il regarde sa carte, voit qu'il a d'autres options (le pont), et essaie celle-là. Il ne jette pas tout le plan à la poubelle ; il change juste de branche.

2. La Mémoire Structurée (Le Tableau de Bord)

Les robots classiques ont une mémoire courte. Ils oublient ce qu'ils ont vu il y a 5 minutes.
STRUCTUREDAGENT utilise une mémoire structurée, comme un tableau Excel intelligent ou un tableau de chasse.

• Imaginez que vous cherchez 3 types de chaussures différentes. Au lieu de noter des phrases en vrac sur un bout de papier, le robot remplit un tableau :
  • Colonne 1 : Nom de la chaussure.
  • Colonne 2 : Prix (satisfait ? Oui/Non).
  • Colonne 3 : Couleur (satisfait ? Oui/Non).
• À chaque fois qu'il trouve une nouvelle chaussure, il met à jour ce tableau. Si une chaussure ne respecte pas les règles, il la barre d'un trait rouge. S'il en trouve une parfaite, il la met en vert. Cela lui permet de ne jamais perdre de vue ses objectifs, même après 30 clics sur le web.

3. La Réparation Dynamique (Le Mécanicien)

Parfois, le plan initial est mauvais. Peut-être que le robot a mal compris la demande.
Dans les systèmes actuels, le robot reste bloqué. Dans STRUCTUREDAGENT, le système agit comme un mécanicien de course.

Si une roue (une étape du plan) se dévisse :

1. Le système détecte le problème.
2. Il arrête de forcer sur cette roue.
3. Il demande à l'intelligence artificielle : "Comment on répare ça ?"
4. Soit il ajoute une nouvelle étape (ex: "aller sur un autre site"), soit il coupe la branche défectueuse de l'arbre pour ne pas perdre de temps.

En Résumé

Alors que les autres agents sont comme des enfants qui courent dans un labyrinthe en criant "Je suis perdu !", STRUCTUREDAGENT est comme un architecte expérimenté avec une boussole.

• Il planifie avant d'agir (l'arbre).
• Il note tout ce qu'il trouve (la mémoire structurée).
• Il s'adapte quand ça ne marche pas (la réparation).

Le résultat ? Il est beaucoup plus capable de résoudre des tâches complexes et longues (comme faire des courses en ligne avec des critères stricts) sans se perdre, sans oublier les règles, et sans abandonner au premier obstacle. C'est un pas de géant pour rendre les robots web aussi intelligents et fiables que des assistants humains.

Résumé technique

1. Problématique

Les agents basés sur les grands modèles de langage (LLM) ont fait des progrès significatifs dans la prise de décision séquentielle. Cependant, ils peinent toujours à accomplir des tâches web complexes et à long terme (long-horizon). Les principales limitations identifiées sont :

• Mémoire contextuelle limitée : Les agents actuels ont du mal à suivre l'historique et les chemins de solutions alternatifs sur de multiples pages web, surtout lorsque le contenu d'une page dépasse 20 000 tokens.
• Faiblesse de la planification : Incapacité à construire et exécuter des plans complexes sur de longues périodes.
• Manque de robustesse : Absence de mécanismes efficaces pour gérer les erreurs, se remettre des échecs ou explorer des solutions de rechange.
• Comportement gourmand (Greedy) : Les agents tendent à terminer prématurément une tâche sans satisfaire toutes les contraintes de l'utilisateur, souvent en raison d'une prise de décision myope.

2. Méthodologie : STRUCTUREDAGENT

Pour surmonter ces défis, les auteurs proposent STRUCTUREDAGENT, un cadre de planification hiérarchique qui intercale la planification et l'exécution. L'approche repose sur deux composants principaux :

A. Planificateur Hiérarchique en Ligne (AND/OR Trees)

Le cœur du système est un arbre de planification AND/OR dynamique que l'agent construit et maintient en temps réel.

• Structure de l'arbre :
  • Nœuds AND : Représentent des sous-objectifs conjonctifs. Tous les enfants doivent réussir pour que le nœud parent réussisse (décomposition séquentielle).
  • Nœuds OR : Représentent des stratégies alternatives. Le nœud parent réussit dès qu'un seul enfant réussit (exploration de chemins alternatifs).
  • Nœuds ACTION : Feuilles de l'arbre correspondant à des opérations atomiques du navigateur (clic, saisie, défilement, note).
• Algorithme de recherche : L'agent utilise une recherche en profondeur d'abord (DFS) modifiée et gourmande. Contrairement au DFS classique, cette version gère des états dynamiques :
  • ENTERING : Le nœud est en cours de traitement ou d'expansion.
  • EXITING : L'exécution est terminée, vérification de la réussite.
  • FAILED : L'exécution a échoué, déclenchant une réparation ou un élagage.
• Gestion des erreurs : Si un nœud échoue, le système peut réparer le nœud (ajouter/supprimer des enfants) ou l'élaguer (pruning). Les échecs se propagent vers le haut de l'arbre, permettant une réévaluation globale du plan.
• Rôle du LLM : Le LLM n'est pas chargé de gérer l'arbre entier. Il est invoqué uniquement pour des opérations locales spécifiques : expansion de nœuds, réparation, vérification de complétion et résumé d'observations. Cela rend le raisonnement plus interprétable et robuste.

B. Module de Mémoire Structurée

Spécifiquement conçu pour les tâches de recherche d'information, ce module remplace la prise de notes non structurée.

• Il extrait les contraintes de la tâche et organise les entités candidates (produits, articles, etc.) dans un tableau dynamique.
• Chaque ligne représente une entité candidate avec des colonnes pour les attributs et les contraintes satisfaites.
• Ce module permet à l'agent de suivre plusieurs candidats simultanément, de vérifier les contraintes tout au long du processus et d'éviter de revisiter des pages rejetées.

3. Contributions Clés

1. Cadre de planification hiérarchique : Introduction d'une approche basée sur des arbres AND/OR ordonnés qui permet un raisonnement compositionnel, une révision dynamique des plans et une rétropropagation des erreurs.
2. Interprétabilité et intervention humaine : La structure de l'arbre rend le processus de décision transparent, facilitant le débogage et permettant une intervention humaine pour corriger des décompositions de sous-objectifs erronées (comme illustré dans l'exemple de la Super Bowl).
3. Module de mémoire structuré : Une solution innovante pour le suivi des contraintes dans les tâches de recherche, améliorant la satisfaction des contraintes sur des tâches complexes.
4. Séparation des responsabilités : Le framework gère la structure de l'arbre, tandis que le LLM ne gère que les opérations locales, réduisant la charge cognitive du modèle et les hallucinations.

4. Résultats Expérimentaux

L'évaluation a été menée sur trois benchmarks : WebVoyager, WebArena et un benchmark de shopping personnalisé (Amazon).

• Performance globale : STRUCTUREDAGENT surpasse systématiquement les agents de base (AgentOccam, BasicClaudeAction, SteP) sur les tâches complexes à long terme.
  • Sur Amazon Easy, il atteint un taux de réussite moyen de 83,3 % (vs 69,2 % pour AgentOccam).
  • Sur Amazon Hard, il obtient 35,6 % (vs 28,4 % pour AgentOccam), avec une amélioration de 5 % supplémentaire grâce au module de mémoire structurée.
  • Sur WebArena, il obtient le meilleur score global (52,6 %), surpassant AgentOccam d'environ 6 %, avec des performances particulièrement fortes sur les catégories "Shopping" et "Reddit".
• Robustesse des modèles : Les bénéfices de la planification hiérarchique persistent même avec des modèles de base plus puissants (Claude 3.7), bien que le module de mémoire structurée soit moins nécessaire avec des modèles plus avancés.
• Efficacité : Bien que l'agent effectue parfois plus d'actions (exploration plus poussée) sur les tâches difficiles, cela se traduit par un taux de réussite nettement supérieur, évitant les terminaisons prématurées.

5. Signification et Impact

Ce travail démontre que l'intégration de mécanismes de planification explicites (arbres AND/OR) et de mémoire structurée est essentielle pour transformer les LLM en agents web robustes capables de gérer l'incertitude et la complexité des environnements réels.

• Passage du "Génie" à l'Ingénierie : L'article montre que la simple augmentation de la puissance du modèle ne suffit pas ; la structure du processus de décision (planification, gestion d'erreurs, mémoire) est critique.
• Interprétabilité : La capacité à visualiser et modifier le plan de l'agent ouvre la voie à des systèmes collaboratifs homme-machine plus sûrs et plus fiables.
• Généralisation : La méthode fonctionne bien sur différents modèles de langage (Claude, Kimi, Gemini), suggérant que l'architecture du framework est le facteur déterminant de la performance plutôt que le modèle de base lui-même.

En conclusion, STRUCTUREDAGENT représente une avancée majeure vers des agents autonomes capables de naviguer, de raisonner et d'agir de manière fiable sur le web pour des tâches complexes et multi-étapes.