Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints

Titel: Exacte en Benaderende Convexe Herformulering van Lineaire Stochastische Optimale Controle met Kansbeperkingen

Auteurs: Tanmay Dokania en Yashwanth Kumar Nakka (Georgia Institute of Technology)

---

1. Probleemstelling

Het paper adresseert het probleem van stochastische bewegingsplanning voor discrete-tijd lineaire systemen. Het doel is om een traject te genereren dat een start- naar een doelpunt leidt, terwijl onzekerheid (ruis) in sensoren, dynamica of obstakels wordt meegenomen.

De kernuitdagingen zijn:

• Kansbeperkingen (Chance Constraints): In plaats van deterministische grenzen, moeten probabilistische garanties worden gegeven (bijv. "de kans dat het voertuig buiten de veilige zone komt, is kleiner dan $\epsilon$").
• Niet-convexiteit: Traditionele formuleringen van stochastische optimale controle met kansbeperkingen leiden vaak tot niet-convexe problemen, die moeilijk op te lossen zijn in real-time.
• Conservatisme: Bestaande methoden (zoals lineaire benaderingen of decoupling van gemiddelde en covariantie) zijn vaak te conservatief. Dit betekent dat ze veilige trajecten als onveilig afwijzen, wat leidt tot suboptimale prestaties of zelfs onoplosbare problemen bij hogere ruisniveaus.

Het paper richt zich specifiek op lineaire kansbeperkingen (op toestanden en besturingen over meerdere tijdstappen) en kwadratische kansbeperkingen (ellipsoïdale beperkingen).

---

2. Methodologie

De auteurs stellen een nieuwe opgeheven (lifted) representatiemethode voor die de momentinformatie (gemiddelde en covariantie) expliciet encodeert in de besluitvariabelen.

A. Stochastische Basis en Lifted Representatie

In plaats van alleen het gemiddelde en de covariantie te optimaliseren, wordt de toestand $x_k$ en besturing $u_k$ uitgedrukt als een lineaire combinatie van een stochastische basis van onafhankelijke Gaussische variabelen $e(k)$:

• $x_k = \mu_k + \Psi_k e(k)$
• $u_k = \nu_k + V_k e(k)$

Hierbij zijn:

• $\mu_k, \nu_k$: De deterministische gemiddelden.
• $\Psi_k, V_k$: Matrixen die de covariantie en de reactie op ruis bepalen (gevectoriseerd als $\psi_k, v_k$).
• $e(k)$: Een vector van onafhankelijke standaard-Gaussische variabelen.

Deze aanpak behoudt de causaliteit (besturing op tijdstap $k$ hangt alleen af van ruis tot $k$) en zorgt ervoor dat de verdeling op elk tijdstap gezamenlijk Gaussisch blijft.

B. Convexe Herformulering

De kern van de methode is het omzetten van het oorspronkelijke stochastische probleem naar een deterministisch convex optimalisatieprobleem:

1. Lineaire Kansbeperkingen (Exact):
   Voor lineaire beperkingen van de vorm $P(a^T x \leq b) \geq 1-\epsilon$, wordt bewezen dat deze onder een Gaussische verdeling exact kunnen worden herschreven als Second-Order Cone Constraints (SOCP). Dit is een exacte herformulering zonder conservatisme.

   • Formule: $y_0 + \Phi^{-1}_N(1-\epsilon)\|y\|_2 \leq b$.

2. Kwadratische Kansbeperkingen (Benadering):
   Voor ellipsoïdale beperkingen (bijv. $P((x-\mu)^T Q^{-1} (x-\mu) \leq 1) \geq 1-\epsilon$) worden twee convex benaderingen voorgesteld:

   • LMI-benadering (Lineaire Matrix Ongelijkheid): Gebaseerd op set-inclusie en Schur's complement.
   • Kwadratische benadering: Gebaseerd op een concentratie-ongelijkheid (Lemma 3) die de som van de singuliere waarden (trace) relateert aan de kans.
     De auteurs tonen aan dat deze benaderingen minder conservatief zijn dan bestaande methoden (zoals Markov's ongelijkheid) en dat de keuze tussen LMI en kwadratisch afhangt van de "skewness" van de covariantiematrix.

3. Dynamica en Kosten:
   De lineaire systeemdynamica blijft affien in de nieuwe variabelen. De kwadratische kostenfunctie wordt exact herschreven in termen van de gemiddelden en de vectorisatie van de covariantiematrices, waardoor het totale probleem convex blijft.

---

3. Belangrijkste Bijdragen

• Exacte Herformulering: Voor lineaire kansbeperkingen op toestanden en besturingen over meerdere tijdstappen (multi-step) wordt een exacte SOCP-formulering gepresenteerd. Dit elimineert het conservatisme van lineaire benaderingen.
• Verbeterde Kwaliteit van Benadering: Voor kwadratische beperkingen worden twee nieuwe convex benaderingen ontwikkeld die wiskundig bewezen minder conservatief zijn dan bestaande technieken.
• Decoupling van Beleid en Optimisatie: De methode vereist geen vooraf gedefinieerde feedback-winsten (zoals bij LQR) of iteratieve linearisatie. De optimale feedback-structuur wordt direct geoptimaliseerd binnen het convex raamwerk.
• Universele Toepasbaarheid: De aanpak werkt voor zowel stationaire als tijdsvariërende systemen en kan zowel state- als control-constraints combineren.

---

4. Resultaten en Validatie

De methode is gevalideerd op het genereren van minimum-snap trajecten voor een quadcopter in een 2D-omgeving met stochastische verstoringen.

• Experimentele Opstellingen:

  1. Circle Arena: Een cirkelvormige veilige zone met waypoints.
  2. Funnel Corridor: Een smalle, trapeziumvormige doorgang die de nauwkeurigheid test.
  3. Terminal Kwantitatieve Beperkingen: Testen van de effectiviteit van de LMI- en kwadratische benaderingen voor eindtoestandsbeperkingen.

• Vergelijking: De resultaten zijn vergeleken met state-of-the-art methoden ([7] en [11]), die respectievelijk feedback-winsten en covariantie-schattingen gebruiken.

• Kernbevindingen:

  • Feasibility (Oplosbaarheid): De voorgestelde methode blijft oplosbaar bij ruisniveaus die een orde van grootte hoger zijn dan waar bestaande methoden falen. Bijvoorbeeld, in de "Funnel Corridor" bleef de methode haalbaar tot $\sigma = 0.6$, terwijl de benchmarks al faalden bij $\sigma \approx 0.06$.
  • Optimaliteit: De methode levert aanzienlijk lagere kosten op (tot 35% verbetering in de Circle Arena en 43% in de Funnel Corridor) omdat het de covariantie effectiever kan "vormgeven" (shape the covariance) om obstakels te vermijden zonder onnodig conservatief te zijn.
  • Kwadratische Beperkingen: De LMI-benadering (22) werkt het beste bij isotrope ruis, terwijl de kwadratische benadering (24) superieur is bij sterk anisotrope ruis.

---

5. Betekenis en Conclusie

Dit paper biedt een fundamentele doorbraak in stochastische optimale controle door het bewijs te leveren dat lineaire kansbeperkingen exact en convex kunnen worden geformuleerd.

• Theoretische Impact: Het sluit de theoretische kloof tussen stochastische planning en convex optimalisatie, wat eerder als moeilijk of onmogelijk werd beschouwd zonder conservatieve benaderingen.
• Praktische Impact: Voor toepassingen zoals UAV-vluchten in turbulente wind of ruimtemissies met onzekere dynamica, betekent dit dat systemen veiliger en efficiënter kunnen opereren. Robots kunnen dichter bij obstakels vliegen en snellere trajecten nemen zonder het veiligheidsrisico te vergroten, omdat de "veiligheidsmarge" niet langer op basis van pessimistische schattingen wordt bepaald, maar op de exacte probabilistische verdeling.

Samenvattend biedt deze "lifted" representatie een krachtig raamwerk voor het oplossen van complexe stochastische controleproblemen in real-time, met een ongeëvenaard evenwicht tussen veiligheid en prestatie.