Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

Technische Samenvatting: Maximaliseren van Reach-Avoid Waarschijnlijkheden voor Lineaire Stochastische Systemen via Controlearchitecturen

Probleemformulering
Dit artikel behandelt de uitdaging om de reach-avoid waarschijnlijkheid voor lineaire stochastische systemen over een eindige tijdhorizon te maximaliseren. Het systeem wordt gedefinieerd door dynamica die zowel deterministisch evoluerende toestanden ($x_d$) als probabilistisch evoluerende toestanden ($x_s$) bevat, onderhevig aan additieve i.i.d.-ruis. Het controle-doel is het vinden van een beleid dat de waarschijnlijkheid maximaliseert dat het systeem een doelset $T$ bereikt terwijl het een veilige set $S$ binnen blijft voor een duur $[0, T]$, terwijl tegelijkertijd deterministische restricties $G$ (zoals invoerlimieten en toestandsgrenzen) op elk moment worden nageleefd.

Bestaande methoden kampen met een afweging: op statistische grenzen gebaseerde benaderingen (bijv. stochastische tubes, scenario MPC) bieden schaalbaarheid maar leveren vaak conservatieve prestaties, terwijl directe optimalisatiemethoden (bijv. Markov Beslissingsprocessen) nauwe garanties bieden maar computationeel onhandelbaar zijn voor hoogdimensionele of continue toestandsruimten.

Methodologie
De auteurs stellen een gelaagde controlearchitectuur voor die de schaalbaarheid van Model Predictive Control (MPC) combineert met de optimaliteit van Dynamic Programming (DP). De kerninnovatie ligt in het behandelen van het gesloten-lus systeem (plant + MPC) als een Markov Beslissingsproces (MDP) waarbij de "acties" referentie-signalen zijn die naar de MPC worden gestuurd, in plaats van directe controle-inputs.

1. Gelaagde Architectuur:

   • Onderste laag (MPC): Een Model Predictive Controller volgt referentie-signalen die door de bovenste laag worden gegenereerd. De MPC is ontworpen om agnostisch te zijn aan het stochastische reach-avoid doel; het enige doel is om te garanderen dat het systeem de deterministische restricties $G$ en invoerlimieten $U$ naleeft. Om de kloof tussen discrete-tijd MPC-optimalisatie en continue-tijd restrictie-naleving te overbruggen, leiden de auteurs technieken voor restrictie-verstrakking af (Lemma III.1) die rekening houden met systeemdynamica en ruis over het bemonsteringsinterval.
   • Bovenste laag (DP Referentie Generator): Een DP-gebaseerd beleid opereert op vaste intervallen ($\Delta t$). Het selecteert referentie-sequenties (commando's) voor de MPC om de waarschijnlijkheid te maximaliseren dat het doel wordt bereikt terwijl onveilige regio's worden vermeden. De toestandsruimte van dit MDP is de systeemtoestand $x_k$, en de actieruimte bestaat uit een eindige set referentie-trajecten.

2. Omgaan met Continue Toestandsruimten en Abstractie:
   Omdat de toestandsruimte continu is, maken de auteurs gebruik van een eindige rooster-abstractie om de DP computationeel hanteerbaar te maken. Om te waarborgen dat theoretische garanties behouden blijven ondanks deze discretisatie, introduceren zij een robuustificatie-framework:

   • Robuuste MPC (RMPC): De MPC wordt aangepast om invoer-sequenties te generen die invariant zijn voor de specifieke begintoestand binnen een roostercel (partitie). Dit wordt bereikt door de MPC-voorspelling te initialiseren vanaf het middelpunt van de cel in plaats van vanaf de gemeten toestand, waardoor dezelfde controle-sequentie wordt toegepast op alle toestanden binnen een partitie.
   • Robuuste Value Iteration: De veilige en doel-sets worden verstrakkt met een straal $r$ (afgeleid van de maximale afwijking van trajecten binnen een tijdstap) om rekening te houden met abstractiefouten. Het DP-algoritme wordt aangepast om een ondergrens te berekenen op de reach-avoid waarschijnlijkheid door rekening te houden met de worst-case transities binnen de nabijheid van elke roostercel.

Belangrijkste Bijdragen

• Controlearchitectuur: Het artikel introduceert een nieuwe architectuur die de dimensionaliteit van de DP-planningruimte reduceert van de volledige toestandsdimensie $n$ naar de dimensie van het probabilistisch evoluerende component $n_s$. Dit wordt bereikt door gebruik te maken van de deterministische evolutie van $x_d$ en de tracking-capaciteiten van de MPC.
• Theoretische Garanties: De auteurs bieden formele certificaten voor de aanpak. Zij bewijzen dat de gerobusteerde architectuur continue-tijd restrictie-naleving garandeert en dat de waarde berekend door de robuuste DP-algoritme dient als een strikte ondergrens op de werkelijke reach-avoid waarschijnlijkheid die door het systeem wordt bereikt (Theorem IV.4).
• Schaalbaarheid en Flexibiliteit: De methode wordt gedemonstreerd als schaalbaar naar hogere-dimensionele systemen (specifiek een 12D quadcopter model) en flexibel genoeg om complexe, gehinderde omgevingen aan te kunnen.

Resultaten
De aanpak werd gevalideerd op een verstoord 12D quadcopter model dat navigeert door diverse gehinderde omgevingen (bijv. labyrinten, zigzag-paden en obstakelvelden).

• Prestaties: In een labyrint-scenario bereikte de architectuur een succespercentage van 40%, wat de conservatieve baselines aanzienlijk overtreft.
• Vergelijking: Over meerdere scenario's heen voldeed de empirische reach-avoid waarschijnlijkheid ($V_0(x_0)$) consequent aan of oversteeg deze de ondergrens berekend door de robuuste value iteration ($\tilde{V}_0(x_0)$), wat de theoretische garanties valideert. Bijvoorbeeld, in een "zigzag"-omgeving was het empirische succespercentage 44% vergeleken met een theoretische ondergrens van 0,3%.
• Afwegingen: Het artikel demonstreert ook het vermogen van de architectuur om geconstraineerde optimale controleproblemen op te lossen. Door een Lagrange-multiplier aan te passen, kan het systeem een afweging maken tussen padkosten (het traject dicht bij een centrum houden) en de reach-avoid waarschijnlijkheid, waardoor een Pareto-front van oplossingen wordt gegenereerd.

Betekenis en Claims
Het artikel claimt dat dit werk de kloof overbrugt tussen de theoretische optimaliteit van MDP-gebaseerde methoden en de praktische schaalbaarheid van MPC. Door de veiligheidshandhaving (behandeld door de robuuste MPC) te ontkoppelen van de probabilistische optimalisatie (behandeld door de DP referentie generator), bereiken de auteurs een controlestrategie die zowel computationeel haalbaar is voor hogere-dimensionele systemen als in staat is om formele reach-avoid certificaten te bieden zonder terug te vallen op overmatig conservatieve statistische grenzen. De auteurs benadrukken dat hun methode formele certificaten biedt voor stochastische systemen, een kenmerk dat vaak ontbreekt bij schaalbare heuristische benaderingen, terwijl het de computationele onhandelbaarheid van volledige-toestand MDP-oplossingen vermijdt.