⚡ electrical engineering

Safe Large-Scale Robust Nonlinear MPC in Milliseconds via Reachability-Constrained System Level Synthesis on the GPU

Dit paper introduceert GPU-SLS, een op GPU gebaseerd framework dat via reachability-gedreven systeemlevel-synthese veilige en robuuste niet-lineaire modelpredictieve regeling voor complexe, onzekere robotsystemen in real-time mogelijk maakt door berekeningstijden drastisch te reduceren en 100% empirische veiligheid te garanderen.

Oorspronkelijke auteurs: Jeffrey Fang, Glen Chou

Gepubliceerd 2026-04-10

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Jeffrey Fang, Glen Chou

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer slimme, maar soms onvoorspelbare robot bestuurt. Deze robot moet door een drukke stad lopen, waar overal obstakels zijn (zoals mensen, auto's of meubels) en waar de grond soms schuurt of er plotseling een windvlaag komt.

De uitdaging is tweeledig:

De route plannen: Hoe komt de robot van A naar B zonder te struikelen?
Veiligheid garanderen: Wat gebeurt er als de robot toch een beetje uit zijn evenwicht komt door een windvlaag? Zet hij dan nog steeds veilig zijn voet neer, of valt hij om?

Dit artikel introduceert een nieuwe technologie genaamd GPU-SLS. Het is als een superkrachtige navigatiecomputer die in milliseconden een veilig plan maakt, zelfs voor robots met heel veel gewrichten (zoals een hond of een mens).

Hier is hoe het werkt, vertaald naar alledaagse beelden:

1. Het probleem: De "Rekenmachine" is te traag

Stel je voor dat je een robot hebt met 75 gewrichten (zoals een mens). Om te beslissen wat de volgende stap is, moet de computer miljarden berekeningen doen om te kijken: "Als ik hierheen ga, en er komt een windvlaag, val ik dan?"

De oude methoden waren als een enkele rekenmeester die alles één voor één uitrekent. Voor een simpele robot ging dat nog, maar voor een complexe robot duurde het te lang. Tegen de tijd dat de robot een beslissing had genomen, was hij al tegen een muur gelopen.

2. De oplossing: Een heel leger rekenmeesters (De GPU)

De auteurs gebruiken een GPU (de grafische kaart die je ook in gaming-computers hebt). In plaats van één rekenmeester, heb je nu een heel leger van duizenden rekenmeesters die tegelijkertijd werken.

De Analogie: Stel je voor dat je een lange rij mensen moet tellen.
- De oude manier (CPU): Eén persoon telt 1, 2, 3... tot 100. Dit duurt lang.
- De nieuwe manier (GPU-SLS): Je deelt de rij op in 100 stukjes. 100 mensen tellen tegelijk hun stukje. Dan combineren ze snel de resultaten. Het is als een snelweg in plaats van een smalle landweg.

3. De slimme truc: "Bereikbare Vakjes" (Reachability)

Dit is het meest creatieve deel. De robot weet niet precies waar hij over 1 seconde is, omdat de wind onvoorspelbaar is.

Oude methode: De robot plande één perfecte lijn. Als de wind die lijn verstoorde, was de robot in de problemen.
Nieuwe methode (GPU-SLS): De robot plant niet één lijn, maar een onzichtbare, flexibele buis (een "tube") om die lijn heen.
- Zie het als een slang die de robot volgt. Zolang de robot binnen die slang blijft, is hij veilig, zelfs als de wind hem een beetje duwt.
- De computer berekent in een flits hoe groot die slang moet zijn om veilig te blijven. Als de slang te groot wordt (te veel risico), vraagt de computer de robot om een andere route te kiezen.

4. Hoe ze het zo snel maken: Het "Pakketje" (ADMM & Scans)

Om dit allemaal in 20 milliseconden (sneller dan een knipoog) te doen, gebruiken ze twee slimme trucs:

Truc 1: Het "Caching" (Het opslaan van antwoorden).
Stel je voor dat je een puzzel oplost. Vaak zijn de randstukjes in elke poging hetzelfde. In plaats van die randstukjes elke keer opnieuw te zoeken, onthoudt de computer ze. De volgende keer dat hij ze nodig heeft, pakt hij ze gewoon uit de kast. Dit bespaart enorm veel tijd.
Truc 2: De "Parallelle Scan" (Het samenvoegen van informatie).
In plaats van informatie van het begin tot het einde van de route lineair te verwerken, laat de computer duizenden stukjes informatie tegelijk "naar elkaar toe bewegen" en samenvoegen. Het is alsof je in plaats van een lange rij mensen die elkaar een bericht doorgeven, een groep mensen hebt die allemaal tegelijk een bericht naar het centrum sturen.

5. Het resultaat: Robots die echt kunnen rennen

De auteurs hebben dit getest op:

Een vierpotige robot (zoals een hond) die over obstakels loopt.
Een mensachtige robot (humanoid) die door een hindernisbaan moet.

Wat gebeurde er?

De robot kon 50 keer per seconde een nieuwe, veilige route plannen.
De robot viel nooit om, zelfs niet als er hard werd geduwd.
De oude methoden waren tot 237 keer langzamer.

Samenvatting in één zin

GPU-SLS is als het geven van een supercomputer aan een robot, zodat deze niet alleen een route plent, maar ook direct ziet waar de "veiligheidsbuis" zit, en dat alles doet terwijl hij al rent, in plaats van stil te staan om na te denken.

Dit maakt het mogelijk om in de toekomst veiligere robots te hebben die in onze huizen, fabrieken en straten kunnen werken zonder ons te verwonden of zelf om te vallen.

Titel: GPU-SLS: Veilige, schaalbare robuuste niet-lineaire MPC in milliseconden via bereikbaarheids-gedwongen Systeem Niveau Synthese op de GPU

Auteurs: Jeffrey Fang en Glen Chou (Georgia Institute of Technology)

1. Probleemstelling

Veilige real-time controle is essentieel voor langdurige robotoperaties, vooral bij complexe, onzame systemen zoals looprobots (quadrupeds en humanoids). Bestaande methoden kampen met twee fundamentele beperkingen:

Schaalbaarheid: Niet-lineaire Model Predictive Control (NMPC) en bereikbaarheidsanalyse (reachability analysis) worden computationeel onhaalbaar voor systemen met een hoge dimensie (bijv. >60 staten) en lange planningshorizons. Traditionele CPU-gebaseerde solvers zijn te traag voor real-time toepassing.
Veiligheid onder onzekerheid: Data-gedreven benaderingen schalen wel, maar bieden vaak geen formele veiligheidsgaranties. Bestaande robuuste methoden (zoals buis-MPC) zijn vaak te conservatief of vereisen de oplossing van niet-convexe problemen, wat de rekentijd explodeert.

Het doel is een methode te ontwikkelen die niet-lineaire NMPC, robuuste tracking-regelaars en gesloten-lus bereikbaarheidsanalyse (reachability) gelijktijdig en in real-time kan oplossen voor systemen met honderdduizenden beslissingsvariabelen, terwijl 100% veiligheid onder verstoringen wordt gegarandeerd.

2. Methodologie: GPU-SLS

De auteurs stellen GPU-SLS voor, een framework dat de kracht van GPU-parallelisme combineert met geavanceerde optimalisatietechnieken. De kern van de methode bestaat uit drie samenhangende onderdelen:

A. GPU-geaccelereerde ADMM voor NMPC

Om de nominale trajecten te optimaliseren, wordt een Sequential Quadratic Programming (SQP) cyclus gebruikt. Binnen elke SQP-iteratie moet een gestructureerd Lineair Tijd-Variabel (LTV) Kwantitatief Programma (QP) worden opgelost.

ADMM Framework: In plaats van traditionele Riccati-recursies (die sequentieel zijn), gebruiken de auteurs de Alternating Direction Method of Multipliers (ADMM).
Parallel Associative Scans (PAS): De oplossing van het QP wordt geparaalleliseerd via "reverse parallel associative scans". Dit vervangt de sequentiële tijd-afhankelijkheid door een logaritmische diepte ( $O(\log N)$ ), waardoor de rekentijd onafhankelijk wordt van de horizonlengte $N$ in termen van sequentiële stappen.
Caching: Om de convergentie van ADMM te versnellen, worden matrixfactorisaties die invariant zijn voor de iteratie (zolang de penalty-parameter $\rho$ constant blijft) in het cache-geheugen bewaard. Dit reduceert de complexiteit van de iteraties aanzienlijk.

B. System Level Synthesis (SLS) voor Robuuste Controle

Om veiligheid onder verstoringen te garanderen, wordt NMPC gekoppeld aan SLS.

Storing-Feedback: In plaats van een vaste feedback, optimaliseert SLS een controller die reageert op verstoringen ( $u_k = v_k + \sum \Phi u_{k,j} w_j$ ).
Bereikbaarheidsanalyse: De methode berekent de "forward reachable sets" (gesloten-lus bereikbaarheidssets) van het systeem. Deze sets worden gebruikt om de constraints in de nominale trajectplanning te "strakker" te maken (constraint tightening).
GPU-Parallelisme: Net als bij de QP-oplossing, worden de recursies voor het berekenen van de SLS-matrices ( $\Phi$ ) parallel uitgevoerd via associative scans. Dit maakt het mogelijk om bereikbaarheidssets voor hoge dimensies in real-time te berekenen.

C. Real-Time Iteration (RTI)

Voor echte real-time prestaties wordt een RTI-scheme toegepast. Per controlestap wordt slechts één SQP-iteratie uitgevoerd in plaats van te convergeren naar een exacte oplossing. De linearisatie en de controller-update worden warm-start met de waarden van de vorige stap. Dit zorgt ervoor dat het systeem snel reageert op nieuwe toestanden, terwijl de fouten in de linearisatie in volgende stappen worden gecorrigeerd.

3. Belangrijkste Bijdragen

GPU-ADMM QP Solver: Een nieuwe solver voor inequality-constrained LQR-problemen die gebruikmaakt van factorisatie-caching en parallelle associatieve scans, wat leidt tot een complexiteit van $O(\log N \log^2 n_x + \log^2 n_u)$ .
Real-time NMPC met SLS: Een geïntegreerde methode die niet-lineaire trajectoptimalisatie en robuuste controller-synthese combineert, met een iteratiekosten van $O(\log N \log^2 n_x + \log^2 n_u)$ .
Unificatie van Bereikbaarheid en Controle: Een methode die in real-time bereikbaarheidssets berekent om constraints te verstrakken, waardoor robuuste veiligheid wordt gegarandeerd zonder de schaalbaarheid te verliezen.
Schaalbaarheid: De methode is getest op problemen met tot $2 \times 10^5$ beslissingsvariabelen en $8 \times 10^4$ constraints, wat een orde van grootte groter is dan wat met bestaande methoden mogelijk is.

4. Resultaten

De auteurs hebben hun methode gevalideerd op zowel simulatie als hardware (Unitree Go2 quadruped en H1 humanoid).

Snelheidswinst:
- NMPC: De tijd voor het oplossen van nominale trajecten is 97,7% sneller dan state-of-the-art CPU-solvers (zoals OSQP en HPIPM) en 71,8% sneller dan bestaande GPU-solvers.
- SLS: De berekening van robuuste controllers en bereikbaarheidssets is 237x sneller dan de bestaande FastSLS-methode.
- Hardware: Op een Unitree Go2 quadruped (61 staten) wordt een gemiddelde oplostijd van 20 ms bereikt, wat real-time controle bij 50 Hz mogelijk maakt.
Veiligheid:
- In tegenstelling tot data-gedreven methoden (zoals DeepReach) die faalden in 6 van de 31 rollouts, behaalde GPU-SLS 100% empirische veiligheid in alle geteste scenario's, inclusief onder adversariële en willekeurige verstoringen.
- De robot slaagde erin om obstakels te vermijden en binnen de berekende "robuste buizen" (tubes) te blijven.
Schaalbaarheid:
- De methode slaagde erin om een 10-link pendulum met een horizon van 3000 stappen (meer dan $1,35 \times 10^5$ variabelen) binnen 73 ms op te lossen.
- De schaalbaarheid is logaritmisch ten opzichte van de horizonlengte, in tegenstelling tot de lineaire of kubische schaalbaarheid van traditionele methoden.

5. Betekenis en Impact

Dit paper markeert een doorbraak in de controletheorie voor robotica door de computationele barrière voor veilig, robuust en niet-lineair MPC voor hoge-dimensie systemen weg te nemen.

Praktische Toepassing: Het maakt het mogelijk om complexe, veilige bewegingsplanningen uit te voeren op fysieke robots (zoals looprobots) in real-time, zelfs in onvoorspelbare omgevingen.
Theoretische Vooruitgang: Het bewijst dat het combineren van SLS, ADMM en GPU-parallelisme (via associative scans) leidt tot een schaalbare oplossing die zowel de theoretische garanties van bereikbaarheidsanalyse als de snelheid van GPU-computing biedt.
Toekomst: De open-source implementatie (GitHub) en de bewezen prestaties op hardware openen de deur voor de volgende generatie autonome systemen die veilig kunnen opereren in dynamische, menselijke omgevingen.

Kortom, GPU-SLS transformeert robuuste NMPC van een computationeel onhaalbaar probleem voor grote systemen naar een real-time oplossing die 100% veiligheid garandeert.