Technische Samenvatting: Sampling-gebaseerde Regeling via Entropie-geregulariseerde Optimale Transport

Probleemstelling

Sampling-gebaseerde Model Predictive Control (MPC)-methoden, zoals Model Predictive Path Integral (MPPI) en de Cross-Entropy Methode (CEM), worden veel gebruikt voor real-time regeling van niet-lineaire robotische systemen, met name waar gradiënten niet beschikbaar zijn of dynamica discontinu is. Deze methoden vertrouwen echter op informatie-theoretische doelstellingen (zoals KL-divergentie) die onverschillig zijn voor de geometrische structuur van de regelruimte.

Deze geometrische onverschilligheid leidt tot twee primaire faalmodi:

1. Modus-averaging: MPPI aggregeert samples via een gewogen gemiddelde. In complexe, multimodale kostenlandschappen (bijvoorbeeld bij het navigeren rond een obstakel) resulteert dit in besturingscommando's die verschillende lokale minima vermengen, wat de robot vaak direct in obstakels stuurt in plaats van een geldig pad eromheen te kiezen.
2. Modus-zoeken: CEM vermijdt averaging door "elite" samples te selecteren, maar dit leidt tot een agressieve toewijzing aan een enkele modus, wat exploratie beperkt en er mogelijk toe leidt dat het algoritme levensvatbare oplossingen mist ten gunste van een lokaal optimum.

Bestaande oplossingen vertrouwen vaak op post-hoc heuristieken (zoals afkoelschema's, covariantie-adaptatie) die de variationale doelstelling niet fundamenteel veranderen. Het artikel betoogt dat een fundamentele verschuiving vereist is om ruimtelijke informatie op te nemen in het optimalisatieproces.

Methodologie: OT-MPC en Sinkhorn Coördinaatafdaal

De auteurs stellen OT-MPC (Optimal Transport MPC) voor, een sampling-gebaseerd algoritme afgeleid van een Entropie-geregulariseerde Optimale Transport (EOT) formulering. In plaats van informatie-theoretische divergentie te minimaliseren, minimaliseert OT-MPC de kosten van het transporteren van waarschijnlijkheidsmassa tussen kandidaat-besturingssequenties en lage-kosten voorstellen, waarbij geometrische nabijheid expliciet wordt opgenomen.

Kernalgoritme: Sinkhorn Coördinaatafdaal (SCD)

De optimalisatie-engine is Sinkhorn Coördinaatafdaal (SCD), een gradiënt-vrij algoritme dat een set van $N$ deeltjes (kandidaat-besturingssequenties) ontwikkelt naar een doeldistributie met behulp van $M$ voorstellen.

1. Formulering: Het probleem wordt geformuleerd als het vinden van een optimale koppeling $\Gamma$ tussen deeltjes $z$ en voorstellen $y$ die een transportkost $c(z, y)$ minimaliseert, geregulariseerd door entropie $H(\Gamma)$.
2. Alternerende Optimalisatie:
   • Koppelingsupdate: Gegeven vaste deeltjes wordt de optimale koppeling $\Gamma$ efficiënt berekend met het Sinkhorn-algoritme. Deze stap houdt rekening met zowel de kosten van de voorstellen als de geometrische afstand tussen deeltjes en voorstellen.
   • Deeltjesupdate: Gegeven de koppeling worden de deeltjes bijgewerkt. Voor kwadratische kosten heeft deze update een gesloten-vorm oplossing: elk deeltje beweegt naar het gewogen barycentrum van zijn gekoppelde voorstellen.
   • Relaxatie: Een stapgrootte-parameter $\eta$ wordt gebruikt om updates te stabiliseren, met name wanneer voorstellen bij elke iteratie opnieuw worden bemonsterd.
3. Voorstel-distributie: Om exploratie en exploitatie in evenwicht te brengen, worden voorstellen bemonsterd uit een mengdistributie: een fractie $\rho$ wordt getrokken uit een globale distributie (bijvoorbeeld uniform of een brede Gaussische verdeling), terwijl de rest lokale verstoringen zijn van bestaande deeltjes.

Belangrijke Theoretische Eigenschappen

• Biconvexiteit: De doelstellingsfunctie is biconvex in de deeltjes en de koppeling, wat unieke oplossingen voor de deelvragen garandeert.
• Monotone Afdaal: Het algoritme garandeert een niet-stijgende reeks van doelstellingswaarden.
• Convergentie: De iteraten convergeren naar een stationair punt.
• Generalisatie: SCD generaliseert MPPI; in de limiet waar het aantal deeltjes $N=1$ of de regularisatie $\epsilon \to \infty$, herstelt SCD de standaard MPPI gewogen gemiddelde.

Belangrijke Bijdragen

1. Algoritmische Innovatie: Het voorstellen van SCD en zijn instantiatie als OT-MPC. In tegenstelling tot bestaande sampling-methoden, update SCD deeltjes op basis van zowel kosten als geometrische nabijheid, wat lokale verfijning mogelijk maakt terwijl diversiteit over modi behouden blijft.
2. Theoretische Garanties: Vestiging van theoretische eigenschappen voor SCD, waaronder monotone afdaal, convergentiegaranties en gesloten-vorm updates voor kwadratische kosten (en andere specifieke kostenfuncties zoals cirkelafstand en Log-Euclidische metrieken).
3. Empirische Validatie: Aantonen dat OT-MPC hogere succespercentages bereikt dan MPPI, CEM en Stein Variational MPC (SV-MPC) over diverse robotica-taken, met name die met multimodale kostenlandschappen.

Experimentele Resultaten

De auteurs hebben OT-MPC geëvalueerd op navigatie-, manipulatie- en locomotie-taken, waarbij ze het vergeleken met MPPI, CEM en SV-MPC.

• Auto Obstakelvermijding (Kinematische Fiets): In dichte obstakelvelden ("Hard" instelling) behaalde OT-MPC een 93,5% succespercentage vergeleken met 88,5% voor MPPI. Het prestatieverschil nam toe in complexe omgevingen waar MPPI leed onder modus-averaging.
• 2D Push-T (Contact-rijke Manipulatie): OT-MPC behaalde een 76% succespercentage, wat significant beter was dan MPPI (4%) en CEM (46%). SV-MPC faalde volledig (0%) vanwege het ontbreken van differentieerbare gradiënten in hybride contactdynamica.
• Quadrotor Obstakelvermijding (12-DOF): In medium en hard dichte obstakelinstellingen behaalde OT-MPC respectievelijk 100% en 92% succespercentages, vergeleken met 60% en 19% voor MPPI. MPPI faalde vaak om haalbare paden te vinden en bleef steken in lokale minima.
• Coöperatieve Lastdracht (Twee Quadrotors): In een taak die precisiecoördinatie vereiste door een smalle muuropening, behaalde OT-MPC 75% succes in de "Hard" instelling versus 10% voor MPPI. De smalle bottleneck verergerde de modus-averaging-problemen van MPPI, waardoor coördinatie werd verstoord.
• Franka Push-T (3D Manipulatie): OT-MPC behaalde 66% succes, vergelijkbaar met een zwaar afgestelde MPPI (64%), maar vereiste aanzienlijk minder inspanning voor het afstellen van hyperparameters.
• Vierpotige Locomotie (Unitree Go2): OT-MPC toonde superieure efficiëntie, waarbij minder gemiddelde stappen nodig waren om doelen te bereiken bij het beklimmen van hellingen en het duwen van dozen vergeleken met MPPI.

Berekeningskosten: Hoewel de Sinkhorn-stap rekenkosten toevoegt ($O(NM)$ versus $O(M)$ voor MPPI), rapporteren de auteurs dat OT-MPC vaak vergelijkbare of snellere wandkloktijden bereikt. Dit komt omdat de transportkoppeling meer informatie per sample extrahert, waardoor het algoritme minder voorstellen (rollouts) kan gebruiken om convergentie te bereiken.

Betekenis en Claims

Het artikel beweert dat OT-MPC de fundamentele beperkingen van informatie-theoretische sampling-methoden aanpakt door de KL-divergentie te vervangen door een Optimale Transport-doelstelling. Deze verschuiving stelt de regelaar in staat om:

• Modi te Behouden: Het "modus-averaging" te vermijden dat leidt tot botsingen in multimodale omgevingen.
• Coördinatie van Updates: Ensemblediversiteit te behouden terwijl kandidaten worden verfijnd naar veelbelovende lokale gebieden.
• Werken zonder Gradiënten: Compatibel te blijven met black-box simulatoren en niet-gladde dynamica, vergelijkbaar met MPPI.

De auteurs positioneren OT-MPC niet merely als een heuristische verbetering, maar als een fundamentele verandering in hoe sampling-gebaseerde regeling informatie aggregeert, waarbij gebruik wordt gemaakt van de geometrische structuur van de regelruimte om robuuste prestaties te bereiken in complexe, contact-rijke en hoogdimensionale robotische taken. Ze erkennen beperkingen, zoals de afhankelijkheid van voorsteldekking voor exploratie en de noodzaak van zorgvuldige afstelling van de entropie-regularisatieparameter $\epsilon$, maar stellen dat de methode een principieel alternatief biedt voor bestaande state-of-the-art sampling-regelaars.