🤖 machine learning

A Reward-Petri-Net Interpretation of Temporal Behavior Trees

Dit artikel stelt voor om Temporale Gedragsbomen te interpreteren als Reward-Petri-Netwerken om automatisch gestructureerde beloningsfuncties voor reinforcement learning te genereren, waardoor het efficiënt leren van complexe, langdurige robotica-taken met hiërarchische en temporele beperkingen mogelijk wordt waarbij standaardmethoden falen.

Oorspronkelijke auteurs: Till Schmeil, Günther Waxenegger-Wilfing, Sebastian Schirmer

Gepubliceerd 2026-06-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Till Schmeil, Günther Waxenegger-Wilfing, Sebastian Schirmer

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren hoe hij een rommelig huis moet schoonmaken. In de wereld van Kunstmatige Intelligentie wordt dit Reinforcement Learning (RL) genoemd. De robot leert door dingen te proberen, fouten te maken en "beloningen" (zoals een digitale high-five) te krijgen wanneer hij iets goed doet.

Het probleem, zoals de auteurs aangeven, is dat het schoonmaken van een heel huis een lange, ingewikkelde taak is. Als je de robot pas een high-five geeft wanneer het hele huis schoon is, kan hij dagenlang ronddwalen zonder ooit een beloning te krijgen. Hij raakt de weg kwijt, geeft het op en leert nooit. Dit is het "sparse reward" probleem (het probleem van schaarse beloningen).

Dit paper stelt een slimme nieuwe manier voor om de robot feedback te geven, gebruikmakend van een systeem genaamd Temporal Behavior Trees (TBTs) vertaald naar Reward Petri Nets (RPNs). Hier is hoe het werkt, onderverdeeld in eenvoudige concepten:

1. Het Blauwdruk: Temporal Behavior Trees (TBTs)

Beschouw een Behavior Tree als een flowchart of een recept voor de robot.

Standaard Recept: "Ga naar de keuken, open dan de koelkast, pak dan de melk."
Het Probleem: Standaard recepten gaan niet goed om met tijd. Wat als de robot "uiteindelijk" de melk moet vinden, of de melk "moet blijven vasthouden" totdat hij de tafel bereikt?
De Oplossing (TBT): De auteurs hebben het recept geüpgraded. Ze hebben "tijdsregels" (met behulp van iets dat Linear Temporal Logic wordt genoemd) direct in de stappen toegevoegd.
- Voorbeeld: In plaats van alleen "Open de deur", is de regel "Open uiteindelijk de deur, en houd hem daarna open."
- Dit stelt de robot in staat om complexe sequenties te begrijpen, zoals "Doe A, dan B, maar als je bij B faalt, probeer dan C, en zorg dat je D doet terwijl je E doet."

2. De Vertaler: Van Boom naar Netwerk (Petri Nets)

Een flowchart is geweldig voor mensen, maar computers hebben een andere taal nodig om direct beloningen te kunnen berekenen. De auteurs hebben een vertaler gemaakt die de TBT "recepten" omzet in een Petri Net.

De Analogie: Stel je een token voor (zoals een knikker) die door een netwerk van buizen en schakelaars beweegt.
Hoe het werkt:
- De Places in het netwerk zijn de stappen in je recept (bijv. "Vind Sleutel", "Open Deur").
- De Transitions zijn de acties die de knikker van de ene stap naar de volgende verplaatsen.
- Tokens vertegenwoordigen vooruitgang. Wanneer de robot succesvol "Sleutel vindt", beweegt een knikker naar de "Open Deur"-station.
- Guards: Dit zijn als beveiligers bij de buizen. Ze controlen of de robot daadwerkelijk het juiste doet voordat ze de knikker doorlaten. Als de robot een stap faalt, kan de knikker vast komen te zitten of gereset worden.

3. Het Geheime Sausje: Reward Petri Nets (RPNs)

Dit is de kerninnovatie. De auteurs hebben beloningen toegevoegd aan het knikkernetwerk.

Automatische High-Fives: In plaats van dat de programmeur moet raden waar beloningen gegeven moeten worden, deelt het systeem automatisch "punten" uit telkens wanneer een knikker door een buis beweegt.
Slimme Verdeling: Het systeem kan beslissen hoeveel van een beloning het geeft.
- Scenario: Als de taak is "Vind de sleutel, open dan de deur, en haal dan de schat", kan het systeem een kleine beloning geven voor het vinden van de sleutel, een grotere voor het openen van de deur, en de grootste voor de schat.
- Dit begeleidt de robot stap voor stap, zodat hij zich nooit verloren voelt, zelfs niet in een enorme, complexe doolhof.

4. De "Backtracking" Functie

Een van de coolste functies die beschreven wordt, is backtracking.

Stel je voor dat de robot probeert een deur te openen, maar deze zit op slot. In een standaard systeem zou hij misschien eeuwig tegen de deur aan blijven slaan.
In dit systeem, als de robot een stap faalt (de "guard" zegt "Nee!"), wordt de knikker gereset. Het systeem zegt in feite: "Oké, dat pad is mislukt. Laten we die specifieke stap resetten en een andere aanpak proberen." Dit voorkomt dat de robot vast komt te zitten in een lus van falen.

5. De Resultaten: Werkt het?

De auteurs hebben dit getest in een digitale wereld genaamd MiniGrid (een doolhofspel gebaseerd op een raster).

De Uitdaging: Ze gebruikten steeds moeilijkere doolhoven waarbij de robot sleutels moest vinden, obstakels moest verplaatsen en deuren in een specifieke volgorde moest openen.
De Uitkomst:
- Vanilla RL (De Oude Manier): De robot faalde. Hij kon de lange sequentie van stappen niet begrijpen omdat hij niet genoeg feedback kreeg.
- TBT + RPN (De Nieuwe Manier): De robot leerde succesvol. Hij begreep de complexe taken veel sneller en met minder pogingen.
- Flexibiliteit: Door te variëren in hoe de beloningen werden verdeeld (bijv. meer punten geven voor latere stappen), konden ze de manier waarop de robot leerde controleren, wat het efficiënter maakte.

Samenvatting

Beschouw dit paper als het uitvinden van een GPS met turn-by-turn instructies en een voortgangsbalk voor robots.

Oude Manier: "Rijd naar de stad." (De robot rijdt in cirkels, in de war).
Nieuwe Manier (TBT + RPN): "Sla linksaf, rijd dan 2 mijl, en sla dan rechtsaf. Je krijgt een punt voor elke juiste afslag, en als je een afslag mist, zetten we je terug naar de laatste correcte kruising."

De auteurs laten zien dat door complexe, tijdsgebonden regels te vertalen naar een netwerk van bewegende tokens, zij automatisch de perfecte "scorekaart" kunnen genereren om robots te leren hoe ze moeilijke, langdurige puzzels moeten oplossen.

Technische Samenvatting: Een Reward-Petri-Net Interpretatie van Temporale Behavior Trees

Probleemstelling

Reinforcement Learning (RL) staat voor aanzienlijke uitdagingen in omgevingen met een lange horizon die gekenmerkt worden door ijle beloningen (sparse rewards). In dergelijke settings worstelen agenten met effectieve krediettoewijzing (credit assignment) en exploratie omdat het beloningssignaal vertraagd en incidenteel is. Hoewel specificatietalen (bijv. Linear Temporal Logic of Automata) zijn gebruikt om automatisch beloningsfuncties af te leiden, missen deze vaak de controle van de gebruiker over de relatieve belangrijkheid van sub-taken. Omgekeerd is handmatige beloningsvorming (reward shaping) moeilijk voor complexe taken met hiërarchische structuren en temporele beperkingen. Het kernprobleem dat wordt aangepakt, is hoe men dichte, informatieve beloningsfuncties kan genereren uit formele taakspecificaties die de intuïtie van de gebruiker met betrekking tot taakhiërarchie en de kritikaliteit van sub-taken behouden, met name voor taken die sequenties, fallbacks en temporele beperkingen omvatten.

Methodologie

De auteurs stellen een raamwerk voor dat Temporale Behavior Trees (TBTs) interpreteert als Reward Petri Nets (RPNs) om RL-agenten te begeleiden.

1. Temporale Behavior Trees (TBTs)

TBTs breiden conventionele Behavior Trees (BTs) uit door Linear Temporal Logic (LTL) formules in bladknopen (leaf nodes) te integreren.

Structuur: TBTs maken gebruik van standaard BT-operatoren: Sequence (sequentiële uitvoering), Fallback (probeer alternatieven totdat één succesvol is) en Parallel (voer meerdere takken uit, waarbij een specifiek aantal moet slagen).
Bladknopen: In plaats van eenvoudige acties bevatten bladen LTL-formules (bijv. $\Diamond a$ , wat betekent "uiteindelijk $a$ ").
Semantiek: De boom definieert een spoor-tevredenheidsconditie (trace satisfaction condition). Een spoor voldoet aan de TBT als de executiegeschiedenis voldoet aan de logische beperkingen gedefinieerd door de operatoren en de formules in de bladen.

2. Constructie van Reward Petri Nets (RPNs)

Het artikel formaliseert een vertaling van TBT-specificaties naar RPNs. Een RPN is een Petri Net uitgebreid met guards, acties en beloningen.

Mapping:
- Places ( $P$ ): Vertegenwoordigen TBT-knopen (zowel controleflow-knopen als bladknopen).
- Transitions ( $T$ ): Vertegenwoordigen de bevrediging of schending van een knoop.
- Tokens: Houden de voortgang van de agent naar het voldoen aan de TBT bij.
- Guards ( $G$ ): Booleanse expressies gebaseerd op de output van automata afgeleid van LTL-formules. Transities vuren alleen als de guard waar is (bijv. als de LTL-formule van een bladknoop is voldaan).
- Actions ($Act$): Beheren de levenscyclus van de onderliggende automata (start/stop) om backtracking te afhandelen. Als een bladknoop faalt (false teruggeeft), wordt de automaton gereset, wat de agent in staat stelt opnieuw te proberen, wat cruciaal is voor niet-monotone eigenschappen.
Determinisme: De constructie waarborgt deterministisch gedrag door gebruik te maken van controle-places (bijv. cT) om de tokenstroom in Fallback- en Parallel-nodes te beheren, wat oneindige lussen of ambigue staten voorkomt.

3. Beloningstoewijzing en -distributie

Het RPN-raamwerk maakt automatische beloningstoewijzing mogelijk op basis van de TBT-structuur.

Distributiefuncties: De auteurs definiëren recursieve functies ( $f_{nLeaf}, f_{nFback}, f_{nParM}, f_{nSeq}$ $f_{n L e a f}, f_{n F ba c k}, f_{n P a r M}, f_{n S e q}$ ) om een totale beloning $r$ $r$ over de boom te verdelen.
- Bladknopen: Wijs positieve beloningen toe voor tevredenheid ( $R(t_\phi) = r$ ) en kleine straffen voor falen ( $R(t_{\neg\phi}) = -\alpha r$ ).
- Controleknopen:
  - Fallback: Stuurt de volledige beloning door naar subtrees; de agent wordt beloond voor het voldoen aan elke tak.
  - Sequence: Verdeelt beloningen zodanig dat latere sub-taken hoger of lager gewogen kunnen worden afhankelijk van het schema (bijv. een strikt toenemende beloning om taakvoltooiing te prioriteren).
  - Parallel: Verdeelt beloningen op basis van het aantal voltooide takken.
Inbedding in MDP: De RPN wordt ingebed in de Markov Decision Process (MDP). Bij elke stap wordt de RPN-status (marking) bijgewerkt op basis van de observaties van de agent en de verdicts van de LTL-automata. De totale beloning die wordt uitgegeven is de som van de beloningen van alle vurende transities.

Belangrijkste Bijdragen

Formele Vertaling: Het artikel biedt een rigoureuze constructiemethode om TBT-specificaties te vertalen naar Reward Petri Nets, waarmee de kloof tussen hoogwaardige temporale logica-specificaties en laagwaardige RL-beloningssignalen wordt overbrugd.
Modulaire Beloningsvorming: Door gebruik te maken van de hiërarchische structuur van TBTs, stelt de methode gebruikers in staat om intuïtief controle uit te oefenen op de distributie van beloningen (bijv. het prioriteren van specifieke sub-taken in een sequentie) zonder handmatig dichte beloningsfuncties te ontwerpen.
Afhandeling van Backtracking: De integratie van automata met RPNs maakt een "backtracking"-mechanisme mogelijk waarbij gefaalde bladknopen worden gereset, waardoor agenten sub-taken opnieuw kunnen proberen terwijl ze nog steeds passende straffen ontvangen, wat essentieel is voor leren in niet-deterministische omgevingen.
Schaalbaarheid: De aanpak toont aan dat TBT-gebaseerde beloningen kunnen schalen naar steeds complexere omgevingen waar standaard RL faalt, door een gestructureerde manier te bieden voor het omgaan met hiërarchische en temporele beperkingen.

Experimentele Resultaten

De auteurs evalueerden de aanpak met behulp van het MiniGrid-framework met het PPO-algoritme in vier steeds moeilijker wordende omgevingen:

Unlock: Sequentiële sleutelverzameling en deurontsluiting.
UnlockPickup: Voegt een doelobjectretrieval toe na het ontgrendelen.
BlockedUnlockPickup: Introduceert obstakels die verplaatst moeten worden voordat er ontgrendeld kan worden.
ObstructedMaze-2Dlh & ObstructedMaze-1Q: Complexe doolhoven met meerdere vergrendelde deuren, obstakels en lange horizonten, die bekend staan als moeilijk voor standaard PPO.

Vergelijkbare Benaderingen:

Vanilla Baseline: Standaard ijle (sparse) beloningen.
TBT-Baseline: TBT in de observatieruimte, eenheid-beloning enkel bij volledige taakvoltooiing.
TBT-Uniform: Eenheid-beloning gelijkmatig verdeeld over alle TBT-knopen.
TBT-MONINC: Eenheid-beloning verdeeld naar bladknopen met strikt strikt toenemende waarden (prioriteren van latere sub-doelen).

Bevindingen:

Leersucces: Vanilla RL slaagde er niet in om te leren in de moeilijkste omgevingen (ObstructedMaze). Alle TBT-gebaseerde benaderingen maakten leren mogelijk.
Sample Efficiëntie: TBT-gebaseerde methoden verbeterden de sample efficiëntie aanzienlijk vergeleken met de vanilla baseline.
Impact van Beloningsdistributie: De TBT-MONINC variant vertoonde een licht voordeel in leersnelheid voor de meest complexe omgevingen, wat suggereert dat het prioriteren van latere sub-doelen helpt de agent effectiever naar taakvoltooiing te leiden dan een uniforme distributie.
Robuustheid: De aanpak bleek robuust tegen variaties in de procedurele generatie van de omgeving.

Betekenis en Claims

Het artikel claimt dat het interpreteren van TBTs als RPNs een flexibele en intuïtieve mechanisme biedt voor beloningsgeneratie in long-horizon RL.

Expressiviteit: TBTs bieden een strikt hogere expressiviteit dan standaard LTL of Signal Temporal Logic (STL) vanwege hun hiërarchische operatoren.
Controle: In tegen tegenstelling tot volledig geautomatiseerde beloningsafleiding uit automata, behoudt deze methode de controle van de gebruiker over de weging van sub-taken via de TBT-structuur en de distributiefuncties voor beloningen.
Modulariteit: De aanpak faciliteert modulaire constructie, waardoor complexe taken gebouwd kunnen worden uit eenvoudigere, herbruikbare TBT-componenten.
Toekomstige Richtingen: De auteurs merken op dat dit raamwerk goed geschikt is voor multi-agent RL (vanwege de inherente concurrency-afhandeling van Petri Nets) en plannen om automatische beloningsvorming via value iteration op RPNs en het gebruik van TBTs als "shields" tijdens het leren te verkennen.

Het werk positioneert TBTs niet alleen als een specificatietool, maar als een directe generator van dichte, gestructureerde beloningssignalen die de bottlenecks van exploratie en krediettoewijzing die inherent zijn aan omgevingen met ijle beloningen overwinnen.