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

Sintesi Tecnica: FilterDDP per il Controllo Ottimo con Vincoli di Uguaglianza Non Lineari

Formulazione del Problema
Il documento affronta problemi di controllo ottimo in tempo discreto (OCP) che coinvolgono vincoli di uguaglianza non lineari. Questi problemi sono prevalenti nella robotica per compiti quali la pianificazione del movimento, la dinamica inversa e l'ottimizzazione della traiettoria implicita nel contatto (ad esempio, locomozione bipede, manipolazione). La specifica formulazione dell'OCP minimizza una funzione di costo cumulativa soggetta a condizioni iniziali dello stato, dinamica di sistema e vincoli di uguaglianza non lineari $c(x_t, u_t) = 0$. Sebbene il Differential Dynamic Programming (DDP) sia efficiente per problemi non vincolati, estendere il DDP per gestire in modo robusto i vincoli di uguaglianza non lineari è stata un'area poco esplorata. Gli approcci esistenti si affidano spesso a metodi di Augmented Lagrangian (AL) o funzioni di merito, che possono soffrire di una limitata garanzia formale di convergenza o instabilità numerica.

Metodologia: FilterDDP
Gli autori propongono FilterDDP, un algoritmo di filtro a ricerca di linea che integra il framework DDP con un meccanismo di filtro del passo, simile all'approccio utilizzato nel risolutore generale per programmazione non lineare IPOPT. L'algoritmo alterna un passaggio backward a un passaggio forward:

1. Passaggio Backward (Indietro): L'algoritmo calcola le derivate del primo ordine e le derivate perturbate del secondo ordine di una funzione di valore sub-ottimale. Applica un passo di Newton perturbato alle condizioni di stazionarietà del Lagrangiano. Un'innovazione chiave è l'introduzione di termini di perturbazione ($\delta_w I$ e $-\delta_c I$) nella matrice KKT per garantire che la matrice abbia un'inerzia specifica (autovalori positivi, negativi, zero), garantendo non singolarità e stabilità.
2. Passaggio Forward (Avanti): Una traiettoria di prova viene generata utilizzando una ricerca di linea con backtracking. La dimensione del passo $\gamma$ viene regolata in base a un criterio di filtro.
3. Criteri di Filtro: A differenza dei tradizionali approcci basati su funzioni di merito, FilterDDP utilizza un filtro basato su due quantità:
   • Violazione del Vincolo ($\theta$): La somma delle norme $L_1$ delle violazioni dei vincoli.
   • Lagrangiano ($L$): Il valore della funzione Lagrangiana, anziché la funzione di costo grezza.
     Un punto di prova viene accettato se produce una diminuzione sufficiente della violazione del vincolo o del Lagrangiano, a condizione che non cada in una regione "tabù" definita dal filtro.

Scelte Progettuali Chiave e Contributi Teorici
Il documento identifica e giustifica rigorosamente due scelte progettuali critiche che migliorano le prestazioni numeriche:

1. Lagrangiano vs. Costo nell'Accettazione del Passo: Gli autori sostituiscono la funzione di costo con il Lagrangiano nel criterio di accettazione del passo. Dimostrano che la condizione di diminuzione sufficiente sul Lagrangiano è analoga alla condizione di Armijo nell'ottimizzazione non vincolata. Questa scelta è supportata da una prova formale che mostra come la derivata direzionale del Lagrangiano corrisponda alla direzione di ricerca utilizzata dall'algoritmo.
2. Essiani Perturbati e Variabili Duali: Nel passaggio backward, l'algoritmo utilizza essiani perturbati e aggiorna la derivata della funzione di valore utilizzando una variabile duale stimata dei vincoli di dinamica, anziché la derivata grezza della funzione di valore.
   • Convergenza Quadratica Locale: Gli autori forniscono una prova formale di convergenza quadratica locale per FilterDDP all'interno di un vicinato di una soluzione. Questo generalizza le prove esistenti per il DDP non vincolato (stati/controlli scalari) al contesto vettoriale vincolato. La prova si basa sulla dimostrazione che il punto ottimale è un punto fisso dell'algoritmo e che le iterazioni convergono quadraticamente quando sono sufficientemente vicine alla soluzione.
3. Estensione Primal-Dual: Il documento presenta un'estensione per gestire i vincoli di disuguaglianza utilizzando un framework interior point primal-dual. Ciò comporta l'introduzione di variabili duali per i vincoli di disuguaglianza e la risoluzione di una sequenza di sottoproblemi di barriera con condizioni di complementarità perturbate.

Risultati Sperimentali
FilterDDP è stato validato su tre difficili problemi di ottimizzazione della traiettoria implicita nel contatto derivanti dalla robotica:

1. Swing-up di un cart-pole con attrito di Coulomb.
2. Swing-up di un acrobot con limiti articolari rigidi.
3. Spinta non prehensile (manipolazione) con evitamento di ostacoli.

L'algoritmo è stato confrontato con:

• IPOPT: Un risolutore all'avanguardia per la programmazione non lineare generale.
• IPOPT (B): Una variante L-BFGS di IPOPT.
• ProxDDP: Un esistente algoritmo DDP basato su AL.

Risultati:

• Robustezza: FilterDDP ha dimostrato una robustezza significativamente maggiore rispetto ai metodi del primo ordine (ProxDDP e IPOPT (B)). In particolare, ProxDDP e IPOPT (B) non sono riusciti a risolvere completamente il compito dell'acrobot, producendo soluzioni inammissibili o degenerate.
• Efficienza: FilterDDP ha raggiunto la convergenza in meno iterazioni e in un tempo di esecuzione (wall-clock time) significativamente inferiore rispetto a IPOPT. Nei tre compiti, il tempo medio di esecuzione di FilterDDP era circa il 10–27% del tempo di IPOPT e l'1–5% del tempo di IPOPT (B).
• Convergenza: I risultati empirici hanno confermato la convergenza quadratica locale, validando l'analisi teorica.
• Studio di Ablazione: La rimozione delle proposte scelte di progettazione (utilizzando il costo invece del Lagrangiano, o essiani non perturbati) ha comportato un aumento del numero di iterazioni e tassi di fallimento più elevati, confermando la necessità di tali modifiche.

Significatività e Rivendicazioni
Il documento sostiene che FilterDDP offre un'alternativa robusta ed efficiente ai metodi esistenti per la risoluzione di OCP con vincoli di uguaglianza nella robotica. Allontanandosi dagli approcci di Augmented Lagrangian e adottando un framework di filtro a ricerca di linea con specifiche modifiche teoriche (accettazione basata sul Lagrangiano ed essiani perturbati), gli autori ottengono proprietà di convergenza più forti e prestazioni numeriche migliori. Il lavoro colma il divario tra l'efficienza del DDP e la robustezza richiesta dai complessi compiti robotici vincolati, fornendo un risolutore che è più veloce dei risolutori general-purpose come IPOPT pur mantenendo una robustezza comparabile o superiore. Gli autori osservano che il lavoro futuro si concentrerà sull'applicazione di FilterDDP alla locomozione di robot bipedi ad alta dimensionalità e sull'instaurare formalmente la convergenza globale.