Technische Samenvatting: Het Leren van Bilevel Policies op Symbolische Wereldmodellen voor Planning op Lange Termijn

Probleemstelling

Het artikel adresseert de uitdaging om embodied AI-agenten te bouwen die betrouwbaar planningproblemen op lange termijn kunnen oplossen in continue toestands- en actieruimtes met variërende aantallen objecten. Hoewel imitatielearning uit demonstraties bewezen effectief is voor laag-niveau (LL) motorische controle en manipulatie, heeft het moeite om efficiënte plannen op lange termijn te genereren. Omgekeerd zijn hoog-niveau (HL) symbolische planners effectief voor redenering op lange termijn, maar falen ze vaak in generalisatie naar omgevingen met variërende sensormodaliteiten, gedeeltelijke waarneembaarheid en complexe laag-niveau dynamiek.

De auteurs formuleren het probleem als het leren van een doel-geconditioneerde policy $\pi(all | s_{ll}, g_{hl})$ die laag-niveau acties ($a_{ll}$) kiest om hoog-niveau doelen ($g_{hl}$) te bereiken. De leermiddelen bestaan uit:

1. LL Demonstraties: Trajecten van toestanden en acties gekoppeld aan HL-doelen.
2. Abstractie-taal ($D$): Een domeintheorie die predicaten en actieschema's definieert.
3. Labelfunctie ($L$): Een mapping van LL-observaties naar HL-symbolische toestanden.

Het doel is het leren van een policy die op zero-shot wijze generaliseert naar ongezane toestanden en doelen, met de verwerking van willekeurige aantallen objecten en open-world condities.

Methodologie

De auteurs stellen BISON voor, een systeem dat bilevel policies $(\pi_{hl}, \pi_{ll})$ leert door neurale imitatielearning te combineren met symbolische abstractie en inductieve generalisatie.

1. Bilevel Policy Architectuur

Het systeem decomposeert het probleem in twee distincte policies:

• Hoog-niveau (HL) Policy ($\pi_{hl}$): Een symbolische policy die werkt op abstracte toestanden ($s_{hl}$) en doelen ($g_{hl}$) om HL-acties ($a_{hl}$) voor te stellen.
• Laag-niveau (LL) Policy ($\pi_{ll}$): Een neurale policy (Graph Neural Network) die de huidige LL-toestand ($s_{ll}$), de voorgestelde HL-actie ($a_{hl}$) en het doel ($g_{hl}$) als input neemt om continue LL-acties ($a_{ll}$) te outputten.

De policies zijn zodanig samengesteld dat $\pi(all | s_{ll}, g_{hl}) = \sum_{a_{hl}} \pi_{ll}(all | s_{ll}, a_{hl}, g_{hl}) \cdot \pi_{hl}(a_{hl} | L(s_{ll}), g_{hl})$.

2. Het Leren van de Hoog-niveau Policy ($\pi_{hl}$)

De HL-policy wordt geleerd uit LL-demonstraties via een drie-staps proces (geïllustreerd in Figuur 2):

1. Constructie van HL-traces: De labelfunctie $L$ wordt toegepast op LL-demonstraties om abstracte HL-traces (reeksen van HL-toestanden en acties) te extraheren.
2. Doelregressie: De auteurs passen doelregressie toe (een pre-image herschrijftechniek) op deze traces. Dit berekent de minimale condities waaronder een actie een doel bereikt. Door doelen achterwaarts te regresseren door actietraces, extrahert het systeem grondconditie-actie-regels.
3. Inductieve Generalisatie: De grondregels worden gelift naar eerste-orde logica door specifieke objecten te vervangen door variabelen. Dit resulteert in een compacte set Conditie $\mapsto$ Actie-regels met prioriteitswaarden gebaseerd op doelproximiteit. Deze regels zijn interpreteerbaar en kunnen generaliseren naar willekeurige aantallen objecten.

De resulterende HL-policy is een set regels van eerste orde. Executie houdt in dat de toepasbare regel met de laagste prioriteitswaarde (hoogste prioriteit) wordt gevonden die voldoet aan de huidige staat en niet-bereikte doelcondities.

3. Het Leren van de Laag-niveau Policy ($\pi_{ll}$)

De LL-policy wordt geïmplementeerd als een Graph Neural Network (GNN) met minder dan 33.000 parameters.

• Inputcodering: De GNN codeert de LL-toestand (agenttoestand en objecttoestanden), het HL-actieschema en de HL-doelfactoren.
• Architectuur: Het maakt gebruik van berichtenuitwisseling tussen objectknooppunten, actieknooppunten en een globaal knooppunt om informatie te aggregeren.
• Training: De GNN wordt getraind via imitatielearning (behavior cloning) op de dataset van tuples $\langle s_{ll}, a_{hl}, g_{hl}, a_{ll} \rangle$ afgeleid van de demonstraties, waarbij de Mean Squared Error (MSE) tussen voorspelde en ground-truth acties wordt geminimaliseerd.

4. Theoretische Garanties

Het artikel vestigt de Nondeterministische Downward Refinement Property (NDRP), waarmee wordt gegarandeerd dat elke oplossing voor het HL-probleem kan worden verfijnd tot een oplossing voor het LL-probleem. Bovendien bewijst Stelling 1 dat onder condities van C-grensdoelonafhankelijkheid (waarbij doelcomponenten onafhankelijk in elke volgorde kunnen worden bereikt met een begrenste policygrootte), de geleerde HL-policy generaliseert naar problemen met willekeurig veel objecten en horizonnen.

Belangrijkste Bijdragen

1. BISON Systeem: Een aanpak om bilevel policies $(\pi_{hl}, \pi_{ll})$ te leren uit LL-demonstraties gekoppeld aan HL-doelen, met gebruikmaking van een domeintheorie en labelfunctie.
2. Symbolische HL-learning: De toepassing van doelregressie en inductieve generalisatie om compacte, expressieve HL-policies te leren. Deze policies worden weergegeven als eerste-orde conditie-actie-regels, wat werking mogelijk maakt in open-world en gedeeltelijk waarneembare omgevingen en generalisatie naar willekeurige objectaantallen.
3. Efficiënte LL-learning: De realisatie van LL-policies via een compact GNN (onder 33k parameters) geconditioneerd op HL-acties.
4. Empirische Validatie: Uitgebreide experimenten (21.600 episodes) op uitgebreide MetaWorld-benchmarks die superieure efficiëntie, generalisatie en planningcapaciteiten op lange termijn aantonen in vergelijking met Vision-Language-Action (VLA)-modellen, end-to-end methoden en symbolische planningsbaselines.

Experimentele Resultaten

De auteurs evalueerden BISON tegen 8 baselines (waaronder SmolVLA, PureNN, PddlNN en diverse herplanningsstrategieën) over 8 omgevingen met variërende onzekerheid (exogeen, endogeen, toestandsonzekerheid).

• Generalisatie: BISON generaliseerde succesvol naar omgevingen met meer objecten (tot 10) en langere horizonnen dan gezien tijdens training (3 objecten), en presteerde beter dan end-to-end GNN-baselines waarvan de prestaties significant degradeerden boven 6 objecten.
• Robuustheid: BISON behaalde de hoogste gemiddelde slagingspercentages in de meeste omgevingen, met name in complexe scenario's waar herplanningsbaselines worstelden of faalden.
• Efficiëntie: BISON toonde superieure tijd- en geheugenefficiëntie tijdens zowel training als inferentie in vergelijking met end-to-end en herplanningsmethoden.
• Schaalbaarheid: Bij het negeren van LL-executie losten BISON's symbolische HL-policies planningproblemen op met 10.000 objecten in minder dan een minuut, wat significant beter presteerde dan de state-of-the-art PDDL-planner LAMA, die moeite had met enkele honderden objecten.
• VLA-prestaties: Voorgereputeerde VLA-modellen (SmolVLA) slaagden er niet in om enige taak in de benchmarks op te lossen, wat de moeilijkheid benadrukt om ze direct toe te passen op manipulatie op lange termijn met meerdere objecten zonder specifieke architecturale aanpassingen.

Betekenis en Claims

Het artikel claimt dat BISON een nieuwe oplossing biedt voor de langdurige uitdaging van planning op lange termijn door effectief de kloof te overbruggen tussen neurale imitatielearning en symbolisch redeneren.

• Zoekvrije Planning: In tegenstelling tot traditionele bilevel planningsystemen die zoeken naar HL-plannen over symbolische abstracties voordat ze deze verfijnen, generaliseert BISON inductief HL-policies direct uit demonstraties, waardoor zoektochten tijdens executie overbodig worden.
• Open-world Capaciteit: De codering van policies als eerste-orde, conditie-actie-regels faciliteert planning in open-world omgevingen en verwerkt gedeeltelijke waarneembaarheid, waarmee beperkingen van puur symbolische planners worden aangepakt.
• Efficiëntie en Schaalbaarheid: De aanpak produceert compacte policies die computationeel efficiënt zijn en schalen naar enorme aantallen objecten, een capaciteit die vaak ontbreekt in zowel pure neurale als pure symbolische benaderingen.

De auteurs erkennen beperkingen, met name dat de aanpak de afhankelijkheid erft van de kwaliteit van de HL-abstractie (of deze nu is geleerd of gegeven) en geen optimaliteit garandeert voor de LL-policies. Zij stellen echter dat de methode een robuust kader biedt voor embodied agents om complexe taken op lange termijn op te lossen met variërende objectaantallen.