Differential dynamic programming

Também chamado: DDP
Categoria: Planning & manipulation › Trajectory optimisation
Tags: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods

Um método de otimização de trajetória que melhora uma sequência de controles por meio de passadas repetidas para trás e para frente, usando modelos quadráticos locais do custo a percorrer (cost-to-go) ao longo da trajetória atual.

Definição

Programação dinâmica diferencial (DDP) (differential dynamic programming) é um algoritmo de otimização de trajetória: dados um modelo dinâmico, um custo sobre estados e controles e um estado inicial, ele encontra uma sequência de controles que minimiza localmente o custo total. Foi introduzida por David Mayne em 1966 e desenvolvida no livro homônimo de Jacobson e Mayne de 1970. A DDP é um método de tiro (shooting): as variáveis de decisão são os controles e, em sua forma clássica, os estados são sempre obtidos simulando a dinâmica para frente, de modo que cada iterado é uma trajetória dinamicamente viável.

Cada iteração tem duas passadas. A passada para trás começa no último passo de tempo e avança em direção ao início, aplicando localmente o princípio de otimalidade de Bellman: ela constrói uma aproximação quadrática do custo a percorrer (cost-to-go) em torno da trajetória atual a partir das derivadas primeiras e segundas da dinâmica e do custo, e resolve em cada passo uma atualização afim do controle, formada por um termo de pré-alimentação k e uma matriz de ganhos de realimentação K. Em seguida, a passada para frente simula o sistema com os controles atualizados u = ū + αk + K(x − x̄), onde α é um tamanho de passo de busca linear. Como a expansão inclui termos de segunda ordem da dinâmica, a DDP converge quadraticamente perto de um mínimo local, como o método de Newton, enquanto o trabalho por iteração cresce apenas linearmente com o comprimento do horizonte.

As derivadas segundas da dinâmica são caras de calcular, por isso a variante mais usada, o regulador linear quadrático iterativo (iLQR), as descarta e mantém um modelo de primeira ordem da dinâmica, uma aproximação de Gauss-Newton. Os solvers práticos regularizam a passada para trás para mantê-la bem condicionada e estendem o método a limites de controle (control-limited DDP), restrições gerais (métodos de Lagrangiano aumentado como o ALTRO), estimativas iniciais inviáveis (feasibility-driven DDP no Crocoddyl) e, como no Parameterized DDP, parâmetros invariantes no tempo otimizados junto com os controles. A DDP encontra apenas ótimos locais, então os resultados dependem da estimativa inicial. Um subproduto útil é o conjunto de ganhos de realimentação, que pode estabilizar o robô em torno da trajetória otimizada.

Por que importa

DDP e iLQR estão entre os solvers mais usados para otimização de trajetória de robôs e controle preditivo baseado em modelo não linear. Eles exploram a estrutura temporal do problema, escalam linearmente com o comprimento do horizonte e retornam uma política de realimentação local junto com a trajetória, e é por isso que robôs com pernas, humanoides e drones os executam em tempo real a bordo.

Principais aplicações

Controle preditivo baseado em modelo não linear para robôs com pernas e humanoides
Otimização de trajetória para drones e veículos ágeis
Planejamento de movimento em nível de torque para braços robóticos
Levantamento (swing-up) e equilíbrio de sistemas subatuados
Otimização conjunta de trajetórias e de parâmetros do modelo ou do projeto

Na prática

Uma equipe que constrói um controle preditivo baseado em modelo de corpo inteiro para um quadrúpede formula o problema no Crocoddyl. A sequência de contatos vem de um cronograma de marcha fixo, de modo que cada fase tem contatos conhecidos, e o custo combina o rastreamento da base, o posicionamento dos pés, o esforço de controle e penalidades que mantêm as forças de contato dentro dos cones de atrito. A cada ciclo de controle, o solver recebe partida a quente com a solução anterior deslocada de um passo e executa apenas uma ou poucas iterações. O primeiro controle e seu ganho de realimentação são enviados ao controlador de junta de baixo nível, que usa o ganho para corrigir as mudanças de estado entre as atualizações do solver. A maior parte do esforço de ajuste vai para os pesos do custo, a regularização e o comprimento do horizonte, que equilibra a antecipação e o tempo de solução.

Equívocos comuns

A DDP encontra a trajetória globalmente ótima — é um método local; o resultado depende da estimativa inicial e pode ser um mínimo local ruim
iLQR e DDP são o mesmo algoritmo — o iLQR omite os termos de segunda ordem da dinâmica, o que dá iterações muito mais baratas ao custo de uma convergência mais lenta perto da solução
A DDP não consegue lidar com restrições — o algoritmo básico é irrestrito, mas as variantes com limites de controle e de Lagrangiano aumentado são amplamente usadas
A DDP é programação dinâmica sobre todo o espaço de estados — ela aplica a recursão de Bellman apenas ao longo de uma trajetória, o que evita a maldição da dimensionalidade, mas dá apenas resultados locais

Quem deve saber

Engenheiros de controle que constroem controladores preditivos baseados em modelo para robôs com pernas e drones
Pesquisadores de otimização de trajetória
Desenvolvedores de humanoides e de controle de corpo inteiro
Estudantes de robótica que estudam controle ótimo

Tecnologias relacionadas

iLQR
Crocoddyl
ALTRO
Recursão de Riccati (Riccati Recursion)
Métodos de tiro (Shooting Methods)

Termos relacionados

Projetos relacionados

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