Technische Samenvatting: Steekproef-efficiënte en Gladdere Cross-Entropy Methode

Probleemstelling

Model Predictive Control (MPC) is een standaardbenadering voor niet-lineaire optimale regeling, maar het oplossen van het onderliggende optimalisatieprobleem blijft uitdagend, met name voor systemen met niet-differentieerbare dynamica of niet-convexe kostenfuncties. In dergelijke scenario's worden gradient-vrije methoden zoals de Cross-Entropy Methode (CEM) de voorkeur gegeven. Echter, standaard CEM-gebaseerde MPC (CEM-MPC) vertrouwt op willekeurige steekproeven om de regelruimte te verkennen. Deze afhankelijkheid presenteert twee primaire beperkingen:

1. Inefficiëntie: Willekeurige steekproeven leiden vaak tot inefficiënte verkenning, wat een groot aantal steekproeven vereist om bevredigende resultaten te bereiken, wat rekenkundig duur is.
2. Niet-gladheid: Zelfs met verbeteringen zoals temporele correlaties (bijvoorbeeld in de Improved CEM of iCEM), kunnen willekeurige steekproeven niet-gladde regeltrajecten produceren. Dit onvoorspelbare gedrag is in de praktijk ongewenst omdat het actuatoren kan beschadigen en tot instabiel systeemgedrag kan leiden.

Methodologie

De auteurs stellen de deterministische steekproef Cross-Entropy Methode (dsCEM) voor, een raamwerk dat de stap van willekeurige steekproeven in CEM-MPC vervangt door deterministische steekproeven afgeleid van Gecumuleerde Lokale Verdelingen (LCDs).

Kernmechanisme

In plaats van willekeurige steekproeven uit een voorstelverdeling te trekken, gebruikt dsCEM vooraf berekende optimale steekproefsets gebaseerd op LCDs. Deze steekproeven zijn ontworpen om de oplossingsruimte met lage discrepantie te dekken, waardoor de clustering en gaten die inherent zijn aan willekeurige steekproeven worden vermeden.

• Offline Generatie: Optimale deterministische steekproeven $\{\tilde{\xi}^{(i)}\}$ worden offline gegenereerd voor een isotrope standaard Gaussische verdeling door een gemodificeerde Cramér–von Mises (CvM) afstand tussen de doel-Gaussische verdeling en een Dirac-mengselbenadering te minimaliseren.
• Online Transformatie: Tijdens runtime worden deze vooraf berekende steekproeven getransformeerd om te matchen met de huidige voorstelverdeling $N(\hat{\xi}_j, C_j)$ van de CEM-optimizer met behulp van de affiene transformatie:
  $$\xi^{(i)} = \hat{\xi}_j + L_j \tilde{\xi}^{(i)}$$
  waarbij $L_j$ de matrixwortel is van de covariantiematrix $C_j$.

Variabiliteits- en Adaptatieschema's

Om voortijdige convergentie te voorkomen en adequate verkenning te garanderen, introduceren de auteurs modulaire schema's voor het genereren van gevarieerde steekproefsets over iteraties en tijdstappen:

• Variabiliteitschema's (V1–V3):
  • V1 (Willekeurige Rotatie): Roteert steekproeven met een willekeurige matrix in elke iteratie, waardoor stochasticiteit wordt geïntroduceerd.
  • V2 (Deterministische Gezamenlijke Dichtheid): Berekent steekproeven vooraf in een hoogdimensionale ruimte die alle iteraties omvat, en partitioneert deze om unieke deterministische sets voor elke stap te leveren.
  • V3 (Gecombineerd): Roteren een hoogdimensionale set één keer per MPC-tijdstap, en gebruikt vervolgens de resulterende steekproeven deterministisch voor alle interne CEM-iteraties.
• Covariantieadaptatie (M1–M2):
  • M1 (Vaste Correlatie, Adaptieve Variantie): Handhaaft een vaste temporele correlatiestructuur (afgeleid van de kleurende ruis power spectral density) terwijl marginale varianties worden bijgewerkt.
  • M2 (Adaptieve Volledige Covariantie): Werk de volledige covariantiematrix online bij om temporele correlaties aan te passen, wat een grotere elite-set vereist.

Deze schema's zijn ontworpen als "drop-in" vervangingen voor de steekproefstap in bestaande CEM-gebaseerde controllers.

Belangrijkste Bijdragen

1. Nieuw Raamwerk: Introductie van dsCEM, dat deterministische steekproeven via LCDs integreert in de CEM-MPC-lus.
2. Modulair Ontwerp: De voorgestelde steekproefschema's zijn orthogonaal ten opzichte van andere CEM-verbeteringen (bijvoorbeeld leer-gebaseerde warm-starts) en kunnen ermee worden gecombineerd.
3. Gladheid en Efficiëntie: De methode richt zich expliciet op het genereren van gladde regeltrajecten zonder expliciete gladheidsstraffen of extra hyperparameters te vereisen, terwijl tegelijkertijd de steekproefefficiëntie wordt verbeterd.

Experimentele Resultaten

De auteurs evalueerden dsCEM tegenover de state-of-the-art iCEM-methode op twee niet-lineaire regeling benchmarks: de Mountain Car taak en de Cart-Pole Swing-Up taak. De evaluatie richtte zich op cumulatieve kosten en gladheid van de regelinput over variërende steekproefgroottes ($N_{CEM}$ van 20 tot 300).

• Prestaties: Over beide taken heen presteerden dsCEM-varianten consistent beter dan iCEM wat betreft cumulatieve kosten, met name in het laag-steekproef regime. Hoewel de prestaties convergeerden voor grotere steekproefgroottes, bereikte dsCEM resultaten vergelijkbaar met een iCEM-basislijn met $10^4$ steekproeven met aanzienlijk minder steekproeven.
• Gladheid: dsCEM produceerde aanzienlijk gladdere regeltrajecten dan iCEM. Opmerkelijk is dat de volledig deterministische variant (dsCEM-Var V2) de hoogste gladheid bereikte, vaak de uitgebreide iCEM-basislijn overtreffend zelfs met een fractie van het steekproefbudget.
• Convergentie: In convergentiegrafieken (vaste steekproefgrootte van 50) toonden dsCEM-varianten snellere convergentie naar lage fasekosten in vergelijking met iCEM.
• Rekenkundige Overhead: De auteurs rapporteren geen meetbare runtime-overhead door de deterministische steekproef- en variatieschema's in vergelijking met willekeurige steekproeven, waarbij parallelisatie in staat is om de uitvoeringstijd verder te verminderen.

Betekenis en Beweringen

Het artikel beweert dat het vervangen van willekeurige steekproeven door deterministische steekproeven gebaseerd op LCDs de fundamentele inefficiënties van CEM-MPC aanpakt. De betekenis van dit werk ligt in:

• Steekproefefficiëntie: Het mogelijk maken van hoogwaardige regeling met minder steekproeven, wat kritiek is voor real-time toepassingen waar rekenkracht beperkt is.
• Intrinsieke Gladheid: Het bereiken van gladde regelinput natuurlijk door de structuur van het steekproefproces, in plaats van via extra straftermen.
• Praktische Implementatie: De vermindering van steekproefvereisten verlaagt de rekenkundige last in alle stadia van het CEM-algoritme (steekproeven, elite-selectie, trajectschieten en kostenbeoordeling). Dit maakt MPC haalbaar voor systemen met complexe modellen en langere voorspellingshorizons op hardware met beperkte parallelisatiemogelijkheden.

De auteurs concluderen dat dsCEM een veelbelovende optie is voor real-time regeling op hardware met beperkte rekenkracht en suggereren dat de orthogonale aard ervan toelaat om in de toekomst te worden gecombineerd met leer-gebaseerde verbeteringen.