Technische Samenvatting: Het Leren van Opgeheven Actiemodellen uit Sporen met Minimale Informatie

Probleemstelling

Recent werk heeft aangetoond dat opgeheven STRIPS-modellen efficiënt kunnen worden geleerd uitsluitend uit actiesporen (SIFT-algoritme), en dat STRIPS+-modellen (die impliciete actieargumenten toestaan) kunnen worden geleerd uit volledig waarneembare staat-actie-sporen (SYNTH-algoritme). Deze benaderingen lopen echter tegen praktische beperkingen aan:

1. SIFT vereist volledige STRIPS-actiesporen waarbij argumenten expliciet zijn, wat vaak onnodige parameters omvat die niet nodig zijn voor actiekeuze (bijvoorbeeld, bij schuifpuzzels moet de huidige positie van een tegel expliciet worden doorgegeven, zelfs als de actie "naar links bewegen" is).
2. SYNTH gaat uit van volledige waarneembaarheid van alle staatpredicaten, wat onrealistisch is voor agenten die opereren in gedeeltelijk waarneembare omgevingen.

Dit artikel behandelt het probleem van het leren van STRIPS+-actie-domeinen uit sporen waarbij zowel actieargumenten als staatsinformatie gedeeltelijk waarneembaar zijn. Specifiek onderzoeken de auteurs de voorwaarden waaronder een equivalent domein kan worden geleerd wanneer sporen minimale informatie dragen: sommige actieargumenten worden weggelaten, en staatpredicaten zijn ofwel volledig onwaarneembaar, volledig waarneembaar, of slechts lokaal waarneembaar (waarneembaar alleen voor objecten die relevant zijn voor de huidige staat).

Methodologie

De voorgestelde oplossing, SYNTH+, is een unificerend algoritme dat de mogelijkheden van SIFT en SYNTH uitbreidt en combineert. Het werkt op uitgebreide sporen (sequenties van acties en gedeeltelijke staatobservaties) en vertrouwt op twee kernmechanismen:

1. Mutex-kenmerken (Uitbreiding van SIFT)

Om ontbrekende actieargumenten te hanteren zonder staatwaarneembaarheid, introduceren de auteurs mutex-kenmerken.

• Concept: Een mutex-kenmerk $f = \langle k, A, D \rangle$ vertegenwoordigt een predicat van ariteit $k$ waarbij het $k$-de argument impliciet wordt bepaald door de eerste $k-1$ argumenten.
• Mechanisme: In tegenstelling tot standaardkenmerken, waarbij toevoeg- en verwijderpatronen dezelfde ariteit hebben, staan mutex-kenmerken toe dat verwijderpatronen een ariteit van $k-1$ hebben. Dit vat de beperking samen dat een actie (bijvoorbeeld drop()) een predicat (bijvoorbeeld holding(o)) verwijdert op basis van het object dat momenteel wordt vastgehouden, zonder dat dit object expliciet in het actiespoor wordt genoemd.
• Consistentie: Een mutex-kenmerk is consistent als, over het spoorgraf heen, elke grondatom $f(o)$ één waarheidswaarde ontvangt, en voor twee ware atomen $f(o)$ en $f(o')$ in dezelfde staat, als de laatste argumenten verschillen ($o_k \neq o'_k$), dan moet ten minste één voorafgaand argument ook verschillen ($o_i \neq o'_i$ voor sommige $i < k$).

2. Query-synthese en Integratie (Uitbreiding van SYNTH)

SYNTH+ integreert de "uitvinding" van predicaten (via SIFT) met de inferentie van impliciete argumenten (via SYNTH) in een iteratieve lus:

1. Invoer: Een gelabeld graf van uitgebreide sporen en een set volledig waarneembare predicaten $P_\omega$.
2. Iteratie:
   • SIFT+-stap: Gebruikt actiepatronen over expliciete en momenteel bekende impliciete argumenten om nieuwe mutex-kenmerken en gewone kenmerken uit te vinden. Deze kenmerken vertegenwoordigen nieuwe predicaten en hun effecten.
   • SYNTH-stap: Gebruikt de nieuw uitgevonden predicaten (en eventueel waarneembare predicaten) om queries te definiëren (subqueries $Q_i$) die impliciete variabelen ($z_i$) binden aan unieke objecten in de staat.
   • Update: Het graf wordt bijgewerkt met de nieuwe impliciete argumenten en hun definiërende queries.
3. Beëindiging: Het proces gaat door totdat een vast punt is bereikt of een maximale dieptegrens ($d_{max}$) wordt overschreden.

3. Lokaal Waarneembaarheid

Het kader wordt uitgebreid tot LOCAL SYNTH+, wat lokaal waarneembaarheid behandelt. In deze setting is een predicat alleen waarneembaar voor "lokale" objecten (die als argumenten in de huidige actie voorkomen). Het algoritme wijzigt de consistentietestprocedure (TEST*) om aan te nemen dat niet-lokale atomen onwaar zijn bij het testen van precondities, zodat onwaargenomen delen van de staat het leren van impliciete argumenten niet ongeldig maken.

Belangrijkste Bijdragen

1. SYNTH+-algoritme: Een algemeen algoritme voor het leren van STRIPS+-domeinen uit sporen met gedeeltelijke waarneembaarheid van zowel acties als staten. Het verenigt de predicatuitvinding van SIFT met de impliciete argumentresolutie van SYNTH.
2. Mutex-kenmerken: Een nieuw formalisme dat het leren van predicaten mogelijk maakt waarbij het laatste argument functioneel afhankelijk is van de anderen, waardoor het herwinnen van weggelaten actieargumenten mogelijk wordt zonder volledige staatobservatie.
3. Volledigheidsresultaten: Theoretische voorwaarden worden vastgesteld voor wanneer de algoritmen volledig zijn:
   • SIFT+ (Geen staatwaarneembaarheid): Vereist dat het verborgen STRIPS+-domein goed geformeerd, sterk samenhangend en acyclisch is in zijn afhankelijkheidsgraf (waarbij knopen predicaten en impliciete variabelen zijn).
   • SYNTH+ (Gedeeltelijke staatwaarneembaarheid): Vereist dat de afhankelijkheidsgraf beperkt tot niet-waarneembare predicaten acyclisch is.
   • LOCAL SYNTH+: Bewezen volledig onder lokale waarneembaarheid voor sleutelpredicaten (predicaten in precondities die alleen impliciete argumenten bevatten) als ze volledig waarneembaar zijn, en andere predicaten lokaal waarneembaar zijn.
4. Generalisatie: Het werk toont aan dat SIFT en SYNTH speciale gevallen zijn van SYNTH+ (waarrespectievelijk $P_\omega = \emptyset$ en $P_\omega = P$).

Experimentele Resultaten

De auteurs evalueerden SIFT+ en SYNTH+ op een reeks standaard planningsdomeinen (bijvoorbeeld Blokken, Levering, Raster, Sokoban, Logistiek) met behulp van uitgebreide sporen gegenereerd uit verborgen STRIPS+-modellen.

• SIFT+-prestaties: Leerde met succes correcte domeinen (100% verificatiepercentage) uitsluitend uit actiesporen in alle geteste domeinen, waarbij gemiddeld 55% van de actieargumenten die uit de sporen waren weggelaten, werd hersteld.
• SYNTH+-prestaties: Leerde correcte domeinen met aanzienlijk minder waarneembare predicaten dan SYNTH.
  • In Levering leerde SYNTH+ het domein door alleen de positie van de agent (at(x)) en statische adjacentie waar te nemen, terwijl SYNTH alle fluïdumpredicaten vereiste.
  • In Sokoban en Logistiek* leerde SYNTH+ domeinen met alleen statische predicaten waargenomen, een scenario waarin noch SYNTH noch SIFT+ succesvol konden zijn.
• Efficiëntie: De algoritmen draaiden efficiënt (seconden tot minuten) op standaard hardware, schaalbaar tot domeinen met duizenden sporstappen.

Betekenis en Beweringen

Het artikel beweert dat SYNTH+ een praktische, opgeheven alternatief biedt voor modelgebaseerde versterkingslering door het leren van dynamische modellen uit "natuurlijke" sporen mogelijk te maken. Deze sporen vereisen minimale informatie:

• Ze hoeven niet elk argument te vermelden dat vereist is door een formele STRIPS-codering (bijvoorbeeld de huidige positie van een blok dat wordt ontstapeld).
• Ze vereisen geen volledige staatwaarneembaarheid; gedeeltelijke of lokale waarneembaarheid van specifieke predicaten is voldoende.

De auteurs benadrukken dat hun aanpak de kloof overbrugt tussen theoretisch modelleerwerk (dat vaak volledige waarneembaarheid veronderstelt) en praktische toepassing (waar agenten beperkte perceptie hebben). Door de exacte voorwaarden (acycliteit van afhankelijkheidsgrafen) te karakteriseren waaronder leren mogelijk is, vestigt het werk een rigoureuze scope voor het leren van opgeheven actiemodellen in gedeeltelijk waarneembare settings. De resultaten suggereren dat complexe domeinen kunnen worden gereconstrueerd uit sporen die alleen de informatie bevatten die nodig is om acties te selecteren, in plaats van de volledige staatbeschrijving.