Differential dynamic programming

Detto anche: DDP
Categoria: Planning & manipulation › Trajectory optimisation
Tag: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods

Un metodo di ottimizzazione delle traiettorie che migliora una sequenza di controlli con passate ripetute all'indietro e in avanti, usando modelli quadratici locali del costo residuo (cost-to-go) lungo la traiettoria corrente.

Definizione

Programmazione dinamica differenziale (DDP) (differential dynamic programming) è un algoritmo di ottimizzazione delle traiettorie: dati un modello dinamico, un costo su stati e controlli e uno stato iniziale, trova una sequenza di controlli che minimizza localmente il costo totale. È stata introdotta da David Mayne nel 1966 e sviluppata ulteriormente nell'omonimo libro di Jacobson e Mayne del 1970. La DDP è un metodo di shooting: le variabili decisionali sono i controlli e, nella forma classica, gli stati si ottengono sempre simulando la dinamica in avanti, quindi ogni iterata è una traiettoria dinamicamente ammissibile.

Ogni iterazione ha due passate. La passata all'indietro parte dall'ultimo passo temporale e procede verso l'inizio, applicando localmente il principio di ottimalità di Bellman: costruisce un'approssimazione quadratica del costo residuo (cost-to-go) attorno alla traiettoria corrente a partire dalle derivate prime e seconde della dinamica e del costo, e risolve a ogni passo un aggiornamento affine del controllo, composto da un termine in avanti (feedforward) k e da una matrice di guadagni di retroazione K. La passata in avanti simula poi il sistema con i controlli aggiornati u = ū + αk + K(x − x̄), dove α è un passo di line search. Poiché lo sviluppo include termini del secondo ordine della dinamica, la DDP converge quadraticamente vicino a un minimo locale, come il metodo di Newton, mentre il lavoro per iterazione cresce solo linearmente con la lunghezza dell'orizzonte.

Le derivate seconde della dinamica sono costose da calcolare, quindi la variante più usata, il regolatore lineare quadratico iterativo (iLQR), le elimina e mantiene un modello del primo ordine della dinamica, un'approssimazione di Gauss-Newton. I solver pratici regolarizzano la passata all'indietro per mantenerla ben condizionata ed estendono il metodo ai limiti sui controlli (control-limited DDP), a vincoli generali (metodi a Lagrangiana aumentata come ALTRO), a stime iniziali non ammissibili (feasibility-driven DDP in Crocoddyl) e, come in Parameterized DDP, a parametri invarianti nel tempo ottimizzati insieme ai controlli. La DDP trova solo ottimi locali, quindi i risultati dipendono dalla stima iniziale. Un sottoprodotto utile è l'insieme dei guadagni di retroazione, che può stabilizzare il robot attorno alla traiettoria ottimizzata.

Perché è importante

DDP e iLQR sono tra i solver più usati per l'ottimizzazione delle traiettorie dei robot e per il controllo predittivo basato su modello non lineare. Sfruttano la struttura temporale del problema, scalano linearmente con la lunghezza dell'orizzonte e restituiscono una policy di retroazione locale insieme alla traiettoria, ed è per questo che robot con gambe, umanoidi e droni li eseguono in tempo reale a bordo.

Applicazioni principali

Controllo predittivo basato su modello non lineare per robot con gambe e umanoidi
Ottimizzazione delle traiettorie per droni e veicoli agili
Pianificazione del movimento a livello di coppia per manipolatori
Swing-up ed equilibrio di sistemi sottoattuati
Ottimizzazione congiunta di traiettorie e di parametri del modello o del progetto

In pratica

Un team che sviluppa un controllo predittivo basato su modello del corpo intero per un quadrupede formula il problema in Crocoddyl. La sequenza dei contatti deriva da un calendario di andatura fisso, quindi ogni fase ha contatti noti, e il costo combina l'inseguimento della base, il posizionamento dei piedi, lo sforzo di controllo e penalità che mantengono le forze di contatto dentro i coni di attrito. A ogni ciclo di controllo il solver viene avviato a caldo con la soluzione precedente spostata di un passo ed esegue solo una o poche iterazioni. Il primo controllo e il suo guadagno di retroazione vengono inviati al controllore dei giunti di basso livello, che usa il guadagno per correggere le variazioni di stato tra un aggiornamento del solver e l'altro. La maggior parte del lavoro di taratura riguarda i pesi del costo, la regolarizzazione e la lunghezza dell'orizzonte, che bilancia la capacità di previsione e il tempo di risoluzione.

Idee sbagliate comuni

La DDP trova la traiettoria globalmente ottima — è un metodo locale; il risultato dipende dalla stima iniziale e può essere un minimo locale scadente
iLQR e DDP sono lo stesso algoritmo — iLQR omette i termini del secondo ordine della dinamica, il che dà iterazioni molto più economiche al prezzo di una convergenza più lenta vicino alla soluzione
La DDP non può gestire vincoli — l'algoritmo di base non ha vincoli, ma le varianti con limiti sui controlli e a Lagrangiana aumentata sono molto usate
La DDP è programmazione dinamica su tutto lo spazio degli stati — applica la ricorsione di Bellman solo lungo una traiettoria, il che evita la maledizione della dimensionalità ma dà solo risultati locali

Chi dovrebbe saperlo

Ingegneri del controllo che sviluppano controllori predittivi basati su modello per robot con gambe e droni
Ricercatori di ottimizzazione delle traiettorie
Sviluppatori di umanoidi e di controllo del corpo intero
Studenti di robotica che studiano il controllo ottimo

Tecnologie correlate

iLQR
Crocoddyl
ALTRO
Ricorsione di Riccati (Riccati Recursion)
Metodi di shooting (Shooting Methods)

Termini correlati

Progetti correlati

PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
python_simple_mppi: MPPI control derived and implemented in numpy, with four worked examples
mjbatch: Runs thousands of MuJoCo simulations in parallel on the CPU
Quadruped-PyMPC: Python MPC framework for quadruped locomotion with gradient and sampling control
STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness