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

Dit paper introduceert STRUCTUREDAGENT, een hiërarchisch planningsframework dat dynamische AND/OR-bomen en een gestructureerd geheugenmodule combineert om de prestaties van webagenten op complexe, lange-termijn taken te verbeteren door beperkingen in geheugen en planning te overwinnen.

De kern

Stel je voor dat je een reisplanner bent die een complexe vakantie moet regelen voor iemand. De opdracht is niet zomaar "ga naar Parijs", maar: "Vind een hotel onder de €100, met een zwembad, dicht bij het centrum, en boek ook een restaurantje voor dinsdagavond dat veganistisch is en goedkoop."

Vroeger waren de digitale "reisklanten" (de AI-agenten) een beetje als een impulsieve toerist. Ze zagen een mooi hotel, klikten erop, en dachten: "Ja, dit is het!" Zelfs als ze vergeten waren om te checken of het zwembad er echt was, of als het restaurant al volgeboekt was. Ze liepen vaak vast, raakten de weg kwijt in de enorme hoeveelheid informatie op het internet, en gaven te snel op.

Deze paper introduceert STRUCTUREDAGENT, een nieuwe, slimme manier om die digitale agenten te laten werken. Het is alsof we die impulsieve toerist vervangen door een ervaren projectmanager met een superkrachtige notitieblok.

Hier is hoe het werkt, in simpele termen:

1. De Boom van Keuzes (De AND/OR Boom)

Stel je voor dat je taak een grote boom is.

• De stam is je einddoel (bijv. "Vind een veganistisch brownie-recept").
• De takken zijn de stappen die je moet zetten.

De slimme kant van STRUCTUREDAGENT is dat deze boom twee soorten takken heeft:

• De "EN"-takken (AND): Dit zijn stappen die allemaal nodig zijn. Je moet én zoeken én klikken én noteren. Als één van deze mislukt, is de hele tak kapot.
• De "OF"-takken (OR): Dit zijn alternatieve routes. Misschien werkt zoekopdracht A niet? Dan probeer je route B. Als route B wel werkt, is het doel bereikt en hoef je route C niet eens te proberen.

De analogie: Een oude agent liep blindelings door de eerste deur die hij zag. STRUCTUREDAGENT kijkt eerst naar de hele kaart, bedenkt: "Oké, als deze deur op slot zit, probeer ik die andere," en houdt de kaart bij. Als hij vastloopt, veegt hij de verkeerde weg niet weg, maar plakt er een label "Hier niet" op en probeert hij een andere route.

2. Het Super-Notitieblok (Gestructureerd Geheugen)

Een ander groot probleem voor AI is dat ze snel vergeten wat ze al hebben gezien. Ze lezen een pagina, klikken ergens, en vergeten dat ze net een goedkoop product zagen dat ze eerder hadden afgewezen.

STRUCTUREDAGENT heeft een gestructureerd geheugen. Stel je dit voor als een slimme spreadsheet in plaats van een losse stapel briefjes.

• Als de agent op zoek is naar drie verschillende laptops, schrijft hij niet zomaar "Laptop A" op.
• Hij maakt een rijtje aan: Laptop A | Prijs: €500 | RAM: 8GB | Status: Te duur.
• Als hij later een nieuwe laptop ziet, vult hij die in de tabel in en vergelijkt hij direct: "Oh, deze is goedkoper en heeft meer RAM. Ik zet Laptop A in de prullenbak en deze nieuwe in de 'beste keuze' kolom."

Dit zorgt ervoor dat de agent nooit twee keer dezelfde fout maakt en altijd de beste opties onthoudt, zelfs als de taak heel lang duurt.

3. De "Stop en Denk"-Methode

Wanneer de agent ergens vastloopt (bijvoorbeeld: hij kan het juiste knopje niet vinden), geeft hij niet direct op.

• Oude agent: "Ik kan het niet vinden. Ik ben klaar."
• STRUCTUREDAGENT: "Oké, deze route faalt. Ik ga terug naar de boom, knip deze tak af (prunen), en probeer een andere strategie. Misschien moet ik eerst een andere pagina bezoeken?"

Het is alsof je een puzzel oplost. Als een stukje niet past, leg je het niet terug in de doos en geef je op; je kijkt of je het stukje ergens anders kunt gebruiken of of je een ander stukje moet zoeken.

Waarom is dit belangrijk?

Vroeger waren AI-agenten goed voor simpele dingen (zoals "ga naar Google en zoek 'weer'"). Maar voor complexe taken (zoals "koop drie verschillende cadeaus voor drie verschillende mensen met specifieke budgetten en levertijden") waren ze vaak te slordig.

Met STRUCTUREDAGENT kunnen deze digitale helpers:

1. Beter plannen: Ze denken vooruit in stappen.
2. Beter onthouden: Ze vergeten geen eerdere ontdekkingen.
3. Beter herstellen: Als ze een fout maken, weten ze precies waar ze terug moeten om het goed te maken, in plaats van helemaal opnieuw te beginnen.

Kortom: Het is de overstap van een slordige toerist die snel de weg kwijtraakt, naar een slimme reisplanner die een gedetailleerd plan heeft, een goede map bijhoudt, en altijd een alternatief plan B, C en D paraat heeft. Hierdoor kunnen ze nu ook de moeilijkste taken op het internet aan, zoals het vinden van de perfecte producten of het regelen van complexe boodschappen.

Technische samenvatting

Probleemstelling

Recente vooruitgangen in Large Language Models (LLM's) hebben geautomatiseerde agenten mogelijk gemaakt die sequentiële beslissingen kunnen nemen. Echter, bestaande webagenten kampen met ernstige beperkingen bij complexe taken met een lange horizon (long-horizon tasks), zoals het navigeren door websites om informatie te vinden of transacties uit te voeren. De belangrijkste uitdagingen zijn:

1. Beperkt contextueel geheugen: Agenten kunnen vaak niet effectief alternatieve oplossingspaden bijhouden over meerdere webpagina's heen, vooral omdat webpagina's vaak zeer lang zijn (tot wel 20.000 tokens) en de agent vaak alleen de huidige pagina en actiegeschiedenis ziet.
2. Gebrek aan planning: Agenten hebben moeite om complexe plannen te construeren en uit te voeren over een lange tijdsduur.
3. Gebrek aan robuuste foutafhandeling: Er is geen mechanisme om effectief te herstellen van fouten of alternatieve oplossingen te verkennen wanneer een pad faalt.
4. Gierig gedrag (Greedy behavior): Agenten neigen tot voortijdige beëindiging van taken zonder alle gebruikersbeperkingen te hebben voldaan, vaak omdat ze lokaal optimale keuzes maken in plaats van een globaal plan te volgen.

Methodologie: STRUCTUREDAGENT

Om deze uitdagingen aan te pakken, stellen de auteurs STRUCTUREDAGENT voor, een hiërarchisch planningskader dat planning en uitvoering afwisselt. Het systeem bestaat uit twee kerncomponenten:

1. Dynamische AND/OR Boom Planner

In plaats van dat de LLM het volledige plan genereert, bouwt het kader een expliciete AND/OR boom dynamisch op tijdens de taakuitvoering.

• Boomstructuur:
  • AND-nodes: Vertegenwoordigen conjunctieve subdoelen. Alle kinderen moeten slagen voor het ouderdoel te slagen.
  • OR-nodes: Vertegenwoordigen alternatieve strategieën. Het ouderdoel slaagt zodra één kind slaagt.
  • ACTION-nodes: Bladknopen die corresponderen met concrete browseracties (klikken, typen, scrollen, noteren).
• Zoekalgoritme: Het systeem gebruikt een gemodificeerde, gretige Depth-First Search (DFS). In tegenstelling tot traditionele DFS op statische grafen, wordt deze boom dynamisch uitgebreid, herzien en gesnoeid naarmate nieuwe informatie wordt verkregen.
• Toestandsbeheer: Nodes doorlopen drie toestanden: ENTERING (in behandeling), EXITING (afgerond) en FAILED (mislukt). Dit stelt het systeem in staat om structurele wijzigingen (zoals het verwijderen van mislukte takken) naar boven te propageren en knopen meerdere keren te bezoeken voor herstel.
• Rol van de LLM: De LLM fungeert als een lokale controller die alleen wordt aangeroepen voor specifieke operaties zoals het uitbreiden van een knoop (node expansion), het repareren van mislukte knopen, het controleren of een doel is bereikt, en het samenvatten van observaties. Het kader zelf beheert de boomstructuur.

2. Gestructureerd Geheugen (Structured Memory)

Voor informatievragende taken introduceert het systeem een module die kandidaat-entiteiten en de door hen vervulde beperkingen bijhoudt in een dynamische tabel.

• Dit voorkomt dat agenten eerder gevonden items vergeten of pagina's opnieuw bezoeken die al zijn afgewezen.
• De module helpt bij het voldoen aan complexe, meervoudige beperkingen (bijv. "vind 3 laptops onder de $1000 met specifieke specificaties") door een overzicht te houden van welke items aan welke criteria voldoen.

Belangrijkste Bijdragen

1. Hiërarchisch Planningskader: Introductie van een framework dat inferentie-tijd planning mogelijk maakt via geordende AND/OR-bomen. Dit ondersteunt compositief redeneren, dynamische planherziening en foutterugkoppeling (error back-propagation).
2. Interpreteerbaarheid: De gegenereerde plannen zijn transparant en hiërarchisch, wat foutlokalizatie en menselijke interventie mogelijk maakt. Mensen kunnen de boom inspecteren en subdoelen corrigeren voordat de uitvoering doorgaat.
3. Gestructureerd Geheugen: Een nieuwe module voor het bijhouden van kandidaat-oplossingen en beperkingen, wat de prestaties verbetert bij zoekopdrachten met meerdere constraints.
4. Robuustheid: Het systeem is ontworpen om om te gaan met de stochastische en deels waarneembare aard van webomgevingen door systematische foutafhandeling en herplanning.

Resultaten

Het team heeft STRUCTUREDAGENT getest op drie benchmarks: WebVoyager, WebArena en een aangepast Amazon Shopping benchmark (met complexe, lange-horizon taken).

• Prestaties: STRUCTUREDAGENT presteerde significant beter dan bestaande baselines (zoals AgentOccam, BasicClaudeAction en SteP) op lange-horizon taken.
  • Op de Amazon Easy taken behaalde het de hoogste gemiddelde succesratio (83,3%).
  • Op de moeilijke Amazon Hard taken (waar menselijke evaluatie werd gebruikt) overtrof het AgentOccam met een marge van 7% tot 14%.
  • Op WebArena behaalde het de hoogste algehele score (52,6%), met name sterk op Shopping- en Reddit-taken.
• Invloed van het Model: De voordelen van de hiërarchische planning bleven bestaan zelfs bij gebruik van sterkere base-modellen (zoals Claude 3.7).
• Trajectlengte: Hoewel STRUCTUREDAGENT op moeilijke taken soms meer browseracties uitvoert (door grondigere exploratie en herstel), leidt dit tot een hogere succesratio. Op eenvoudigere taken is het aantal acties vergelijkbaar met baselines.
• Gestructureerd Geheugen: De module verbeterde de prestaties op complexe taken met meerdere items, maar had een licht negatief effect op zeer eenvoudige taken waar de extra complexiteit van het geheugen als ruis fungeerde.

Betekenis en Conclusie

STRUCTUREDAGENT markeert een belangrijke stap in de ontwikkeling van autonome webagenten. Door de verantwoordelijkheid voor het globale planningskader te scheiden van de lokale uitvoering door de LLM, lost het systeem fundamentele problemen op rondom geheugenbeperkingen en gierig gedrag.

De belangrijkste implicaties zijn:

• Betrouwbaarheid: Het systeem kan complexere, real-world taken aan die eerder te moeilijk waren voor LLM-agenten.
• Interpreteerbaarheid: De hiërarchische structuur maakt het mogelijk voor menselijke operators om in te grijpen en fouten in de logica van het plan te corrigeren, wat cruciaal is voor veilige implementatie.
• Generalisatie: Het kader werkt effectief over verschillende LLM-families heen en is niet afhankelijk van specifieke fine-tuning, maar leunt op inference-time planning.

Kortom, STRUCTUREDAGENT bewijst dat het combineren van dynamische zoekalgoritmen (AND/OR bomen) met gestructureerd geheugen de prestaties van webagenten aanzienlijk kan verbeteren, vooral bij taken die diepgaande redenering en langdurige volharding vereisen.