Line-Search Filter Differential Dynamic Programming for Optimal Control with Nonlinear Equality Constraints

Technische Samenvatting: FilterDDP voor Optimale Controle met Nietlineaire Gelijkheidsvoorwaarden

Probleemformulering
Het artikel behandelt discrete-time optimale controleproblemen (OCP's) met nietlineaire gelijkheidsvoorwaarden. Deze problemen zijn alomtegenwoordig in de robotica voor taken zoals bewegingsplanning, inverse dynamica en contact-impliciete trajectoptimalisatie (bijv. voortbeweging van gevleugelde robots, manipulatie). De specifieke OCP-formulering minimaliseert een cumulatieve kostenfunctie onder de voorwaarden van initiële toestandscondities, systeemdynamica en nietlineaire gelijkheidsvoorwaarden $c(x_t, u_t) = 0$. Hoewel Differential Dynamic Programming (DDP) efficiënt is voor onbeperkte problemen, is het uitbreiden ervan om nietlineaire gelijkheidsvoorwaarden robuust aan te pakken een onderbelicht gebied gebleken. Bestaande benaderingen vertrouwen vaak op augmented Lagrangian (AL)-methoden of merit-functies, die kunnen lijden onder beperkte formele convergentiegaranties of numerieke instabiliteit.

Methodologie: FilterDDP
De auteurs stellen FilterDDP voor, een line-search filteralgoritme dat het DDP-framework integreert met een stap-filtermechanisme, vergelijkbaar met de aanpak die wordt gebruikt in de algemene nietlineaire programmeersolver IPOPT. Het algoritme wisselt af tussen een backward pass en een forward pass:

1. Backward Pass: Het algoritme berekent eerste en geperturbeerde tweede afgeleiden van een suboptimale waarde-functie. Het past een geperturbeeerde Newton-stap toe op de stationariteitsvoorwaarden van de Lagrangian. Een belangrijke innovatie is de introductie van perturbatietermen ($\delta_w I$ en $-\delta_c I$) in de KKT-matrix om ervoor te zorgen dat de matrix een specifieke inertie heeft (positieve, negatieve, nul eigenwaarden), wat niet-singulariteit en stabiliteit garandeert.
2. Forward Pass: Een trial-traject wordt gegenereerd met behulp van een backtracking line search. De stapgrootte $\gamma$ wordt aangepast op basis van een filtercriterium.
3. Filtercriteria: In tegen tegenstelling tot traditionele merit-functie benaderingen, gebruikt FilterDDP een filter gebaseerd op twee grootheden:
   • Constraint Violation ($\theta$): De som van de $L_1$-normen van de schendingen van de voorwaarden.
   • Lagrangian ($L$): De waarde van de Lagrangian-functie, in plaats van de ruwe kostenfunctie.
     Een trial-punt wordt geaccepteerd als het een voldoende afname oplevert in ofwel de schending van de voorwaarden of de Lagrangian, mits het niet in een "taboe"-regio valt die door het filter is gedefinieerd.

Belangrijke Ontwerpkeuzes en Theoretische Bijdragen
Het artikel identificeert en rechtvaardigt rigoureus twee cruciale ontwerpkeuzes die de numerieke prestaties verbeteren:

1. Lagrangian versus Kosten in Stapacceptatie: De auteurs vervangen de kostenfunctie door de Lagrangian in het criterium voor stapacceptatie. Ze bewijzen dat de voldoende afname-conditie op de Lagrangian analoog is aan de Armijo-conditie in onbeperkte optimalisatie. Deze keuze wordt ondersteund door een formeel bewijs dat aantoont dat de directionele afgeleide van de Lagrangian overeenkomt met de zoekrichting die door het algoritme wordt gebruikt.
2. Geperturbeerde Hessians en Duale Variabelen: In de backward pass gebruikt het algoritme geperturbeerde Hessians en werkt het de gradiënt van de waarde-functie bij met een geschatte duale variabele van de dynamica-voorwaarden in plaats van de ruwe gradiënt van de waarde-functie.
   • Lokale Kwadratische Convergentie: De auteurs leveren een formeel bewijs van lokale kwadratische convergentie voor FilterDDP binnen een buurt van een oplossing. Dit generaliseert bestaande bewijzen voor onbeperkte DDP (scalaire toestanden/controles) naar de beperkte, vector-waardige setting. Het bewijs berust op het aantonen dat het optimale punt een vast punt is van het algoritme en dat de iteraties kwadratisch convergeren wanneer ze voldoende dicht bij de oplossing zijn.
3. Primal-Dual Uitbreiding: Het artikel presenteert een uitbreiding om ongelijkheidsvoorwaarden te behandelen met een primal-dual interior point framework. Dit houdt in dat er duale variabelen worden geïntroduceerd voor ongelijkheidsvoorwaarden en dat een sequentie van barrière-subproblemen met geperturbeerde complementariteitsvoorwaarden wordt opgelost.

Experimentele Resultaten
FilterDDP werd gevalideerd op drie uitdagende contact-impliciete trajectoptimalisatieproblemen voortvloeiend uit de robotica:

1. Cart-pole swing-up met Coulomb-wrijving.
2. Acrobot swing-up met harde gewrichtslimieten.
3. Non-prehensile pushing (manipulatie) met obstakelvermijding.

Het algoritme werd vergeleken met:

• IPOPT: Een state-of-the-art algemene nietlineaire programmeersolver.
• IPOPT (B): Een L-BFGS variant van IPOPT.
• ProxDDP: Een bestaand AL-gebaseerd DDP-algoritme.

Bevindingen:

• Robuustheid: FilterDDP demonstreerde aanzienlijk hogere robuustheid vergeleken met eerste-orde methoden (ProxDDP en IPOPT (B)). Met name faalden ProxDDP en IPOPT (B) om de acrobot-taak volledig op te lossen, waarbij ze onhaalbare of gedegenereerde oplossingen opleverden.
• Efficiëntie: FilterDDP bereikte convergentie in minder iteraties en met aanzienlijk lagere wandkloktijd vergeleken met IPOPT. Over de drie taken heen was de gemiddelde wandkloktijd van FilterDDP ongeveer 10–27% van de tijd van IPOPT en 1–5% van de tijd van IPOPT (B).
• Convergentie: Empirische resultaten bevestigden lokale kwadratische convergentie, wat de theoretische analyse valideert.
• Ablatie-studie: Het verwijderen van de voorgestelde ontwerpkeuzes (het gebruik van kosten in plaats van de Lagrangian, of ongeperturbueerde Hessians) resulteerde in een hoger aantal iteraties en hogere faalpercentages, wat de noodzaak van deze modificaties bevestigt.

Betekenis en Claims
Het artikel claimt dat FilterDDP een robuust en efficiënt alternatief biedt voor bestaande methoden voor het oplossen van gelijkheidsvoorwaardelijke OCP's in de robotica. Door af te stappen van augmented Lagrangian-benaderingen en een line-search filter framework te adopteren met specifieke theoretische modificaties (Lagrangian-gebaseerde acceptatie en geperturbeerde Hessians), bereiken de auteurs sterkere convergentie-eigenschappen en betere numerieke prestaties. Het werk overbrugt de kloof tussen de efficiëntie van DDP en de robuustheid die vereist is voor complexe, beperkte robotica-taken, door een solver te bieden die sneller is dan algemene solvers zoals IPOPT terwijl hij vergelijkbare of superieure robuustheid behoudt. De auteurs merken op dat toekomstig werk zich zal richten op het toepassen van FilterDDP op hoog-dimensionale voortbeweging van gevleugelde robots en het formeel vaststellen van globale convergentie.