From Kinematics to Dynamics: Learning to Refine Hybrid Plans for Physically Feasible Execution

Probleemstelling

In veel robotische taken moeten agenten een reeks ruimtelijke regio's doorkruisen om een missie te voltooien. Deze problemen zijn inherent gemengd-discreet-continu: ze vereisen een hoog-niveau volgorde van acties (discreet) en een fysiek haalbare continue traject (continu). Bestaande hybride tijdsplanners (zoals Scotty) proberen dit aan te pakken door beweging te modelleren met lineaire (eerste-orde) dynamica, waarbij de snelheid direct wordt gecontroleerd ($\dot{x}(t) = v(t)$).

Dit leidt tot twee kritieke problemen:

1. Fysieke onhaalbaarheid: Eerste-orde modellen negeren tweede-orde beperkingen zoals maximale versnelling, vertraging en luchtweerstand (drag). Hierdoor zijn de gegenereerde plannen vaak fysiek onuitvoerbaar voor echte robots, wat leidt tot actuator-saturatie en grote volgsfouten.
2. Beperkte correctie: Bestaande planners kunnen binnen hun eerste-orde modellen geen plannen herzien om tweede-orde haalbaarheid af te dwingen. Zelfs als de hoog-niveau actievolgorde vaststaat, is het vinden van een dynamisch haalbaar traject een complex bi-niveau optimalisatieprobleem.

Het paper adresseert de kloof tussen het eerste-orde plan en de werkelijke fysieke dynamica door een neuro-symbolisch verfijningsframework te introduceren.

Methodologie

De auteurs formuleren het probleem als een Continuous-State and Action Markov Decision Process (CSA-MDP) dat gebruikmaakt van Reinforcement Learning (RL) om plannen te verfijnen. Het proces bestaat uit vier fasen:

1. Plan-naar-Graph Representatie:

   • Een eerste-orde haalbaar hybride plan (gegenereerd door een standaard planner zoals Scotty) wordt omgezet in een graaf $G=(V, E)$.
   • Nodes vertegenwoordigen gebeurtenissen (start/einde van acties) met attributen zoals positie, tijdstip en regio-toewijzing.
   • Edges vertegenwoordigen overgangen tussen gebeurtenissen en coderen continue constraints (snelheidsgrenzen, tijdsduur).
   • Een Graph Neural Network (GNN) verwerkt deze graaf om latentere embeddings te genereren die ruimtelijke, temporele en dynamische relaties vastleggen.

2. Validatie via Minimum-Time Validation (MTV):

   • Om de fysieke haalbaarheid te controleren, wordt gebruikgemaakt van MTV. Dit is een analytische methode die de minimale reistijd berekent tussen twee punten onder niet-lineaire tweede-orde dynamica (inclusief versnellingsbeperkingen en kwadratische luchtweerstand).
   • De dynamica worden gemodelleerd als: $\dot{x}_1 = x_2$ en $\dot{x}_2 = u - \frac{1}{2}k x_2^2$.
   • Als de door de planner toegewezen duur korter is dan de MTV-berekende minimale tijd ($t_{min}$), is het segment fysiek onhaalbaar.

3. Verfijningscyclus met RL (PPO):

   • Agent: Een RL-agent (gebaseerd op Proximal Policy Optimization - PPO) observeert de graaf en geeft continue actieparameters af.
   • Actie: De agent past snelheidsgrenzen voor elke traject-segment aan door een schalingsfactor (tussen 0 en 1) toe te passen. Dit is een conservatieve benadering (verkleinen van grenzen) om binnen het haalbare domein te blijven.
   • Optimalisatie: Na elke aanpassing wordt een SOCP (Second Order Cone Program) solver gebruikt om het traject te herschrijven binnen de nieuwe snelheidsgrenzen.
   • Beloning (Reward):
     • Als de SOCP-oplossing niet haalbaar is: negatieve beloning (-1).
     • Als de oplossing eerste-orde haalbaar is maar tweede-orde schendingen heeft: een beloning gebaseerd op de "haalbaarheidskloof" (hoeveel de huidige duur afwijkt van $t_{min}$).
     • Als de oplossing volledig tweede-orde haalbaar is: een positieve beloning gebaseerd op de verhouding van de oorspronkelijke tot de nieuwe makespan (totale uitvoertijd).

4. Architectuur:

   • Het model gebruikt een gedeelde encoder-actor-critic architectuur. De actor en critic gebruiken de GNN-embeddings om respectievelijk een Gaussisch beleid (voor snelheidsaanpassingen) en een waarde-schatting te genereren.

Belangrijkste Bijdragen

1. Formulering als CSA-MDP: Het verfijnen van plannen wordt voor het eerst geformuleerd als een MDP over een graafgebaseerde representatie, wat gestructureerd redeneren over temporele, ruimtelijke en dynamische relaties mogelijk maakt.
2. Geautomatiseerd Refinement Framework: Dit is het eerste framework dat eerste-orde haalbare plannen transformeert naar fysiek geldige trajecten door analytische tweede-orde haalbaarheidsanalyse (MTV) te integreren met Reinforcement Learning.
3. Empirisch Bewijs: De auteurs tonen aan dat plannen van standaard hybride planners onder tweede-orde dynamica fysiek onhaalbaar zijn (0% succes), en dat hun verfijningsmethode dit probleem in 100% van de gevallen oplost.

Resultaten

De methode werd getest op vier hybride planningsdomeinen (AUV-2D, NORM-AUV-2D, OnAir Refuel, Sailing):

• Haalbaarheid: Alle initiële plannen waren onhaalbaar onder tweede-orde dynamica. Na verfijning bereikte het systeem 100% haalbaarheid in alle domeinen.
• Makespan (Totale Tijd): Omdat eerste-orde modellen de benodigde tijd onderschatten, neemt de totale uitvoertijd toe na verfijning. De gemiddelde toename (makespan ratio) varieerde van 1.14 tot 1.23 (dus 14% tot 23% langer), wat een strikte bovengrens biedt voor de optimale oplossing.
• Vergelijking met Baselines: De RL-methode presteerde aanzienlijk beter dan een conservatieve baseline met constante snelheidscontractie (bijv. 10% of 0.5% vermindering per stap). De RL-agent bereikte haalbaarheid met een lagere makespan en vereiste veel minder iteraties dan de baselines. De baseline met fijne contractie (0.5%) leverde slechts marginale winst op maar vereiste bijna 1800% meer verfijningsstappen.
• Convergentie: De training liet een duidelijke stijgende trend in de cumulatieve beloning zien, waarbij de agent snel de fysiek haalbare regio bereikte en vervolgens de makespan optimaliseerde.

Betekenis en Toekomstperspectief

Dit werk is significant omdat het de kloof overbrugt tussen symbolische planning (hoog-niveau logica) en fysieke uitvoering (realistische dynamica). Het biedt een praktische oplossing voor robotica waar complexe tijdsplanningen vaak falen door te simpele bewegingsmodellen.

Beperkingen en Toekomstig Werk:

• Het huidige model gaat uit van verstoringvrije, ontkoppelde dynamica (X en Y assen worden onafhankelijk behandeld).
• Er worden geen tijdsvensters (time windows) meegenomen in de verfijning.
• Toekomstig werk richt zich op het uitbreiden van het framework naar gekoppelde assen, variabiliteit in activiteitsduur en het hanteren van tijdsvenster-beperkingen in realistische omgevingen.

Kortom, het paper introduceert een robuust, leerbaar mechanisme dat garanties biedt voor fysieke uitvoerbaarheid zonder de symbolische structuur van het oorspronkelijke plan te hoeven wijzigen.