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

Resumo Técnico: FilterDDP para Controle Ótimo com Restrições de Igualdade Não Lineares

Formulação do Problema
O artigo aborda problemas de controle ótimo em tempo discreto (OCPs) que envolvem restrições de igualdade não lineares. Esses problemas são prevalentes na robótica para tarefas como planejamento de movimento, dinâmica inversa e otimização de trajetória implícita de contato (ex: locomoção de pernas, manipulação). A formulação específica do OCP minimiza uma função de custo cumulativa sujeita a condições iniciais de estado, dinâmica do sistema e restrições de igualdade não lineares $c(x_t, u_t) = 0$. Embora o Diferencial Dynamic Programming (DDP) seja eficiente para problemas sem restrições, estender o DDP para lidar com restrições de igualdade não lineares de forma robusta tem sido uma área pouco explorada. Abordagens existentes frequentemente dependem de métodos de Lagrangiana Aumentada (AL) ou funções de mérito, que podem sofrer de garantias de convergência formal limitadas ou instabilidade numérica.

Metodologia: FilterDDP
Os autores propõem o FilterDDP, um algoritmo de filtro de busca de linha que integra o framework DDP com um mecanismo de filtro de passo, semelhante à abordagem utilizada no solver de programação não linear geral IPOPT. O algoritmo alterna entre uma passagem para trás (backward pass) e uma passagem para frente (forward pass):

1. Passagem para Trás (Backward Pass): O algoritmo computa as primeiras derivadas e as derivadas de segunda ordem perturbadas de uma função de valor subótima. Ele aplica um passo de Newton perturbado às condições de estacionariedade do Lagrangiano. Uma inovação fundamental é a introdução de termos de perturbação ($\delta_w I$ e $-\delta_c I$) na matriz KKT para garantir que a matriz possua uma inércia específica (autovalores positivos, negativos, zero), garantindo não singularidade e estabilidade.
2. Passagem para Frente (Forward Pass): Uma trajetória de teste é gerada usando uma busca de linha de retrocesso (backtracking line search). O tamanho do passo $\gamma$ é ajustado com base em um critério de filtro.
3. Critérios de Filtro: Ao contrário das abordagens tradicionais de função de mérito, o FilterDDP utiliza um filtro baseado em duas quantidades:
   • Violação de Restrição ($\theta$): A soma das normas $L_1$ das violações das restrições.
   • Lagrangiana ($L$): O valor da função Lagrangiana, em vez da função de custo bruta.
     Um ponto de teste é aceito se ele resultar em uma diminuição suficiente na violação da restrição ou na Lagrangiana, desde que não caia em uma região "tabu" definida pelo filtro.

Escolhas de Design Chave e Contribuições Teóricas
O artigo identifica e justifica rigorosamente duas escolhas críticas de design que aumentam o desempenho numérico:

1. Lagrangiana vs. Custo na Aceitação de Passo: Os autores substituem a função de custo pela Lagrangiana no critério de aceitação de passo. Eles provam que a condição de diminuição suficiente na Lagrangiana é análoga à condição de Armijo em otimização sem restrições. Essa escolha é sustentada por uma prova formal mostrando que a derivada direcional da Lagrangiana corresponde à direção de busca usada no algoritmo.
2. Hessianas Perturbadas e Variáveis Duais: Na passagem para trás, o algoritmo utiliza Hessianas perturbadas e atualiza o gradiente da função de valor usando uma variável dual estimada das restrições da dinâmica, em vez do gradiente bruto da função de valor.
   • Convergência Quadrática Local: Os autores fornecem uma prova formal de convergência quadrática local para o FilterDDP dentro de uma vizinhança de uma solução. Isso generaliza provas existentes para DDP sem restrições (estados/controles escalares) para o cenário vetorial com restrições. A prova baseia-se em mostrar que o ponto ótimo é um ponto fixo do algoritmo e que as iterações convergem quadraticamente quando suficientemente próximas da solução.
3. Extensão Primal-Dual: O artigo apresenta uma extensão para lidar com restrições de desigualdade usando um framework de ponto interior primal-dual. Isso envolve a introdução de variáveis duais para restrições de desigualdade e a resolução de uma sequência de subproblemas de barreira com condições de complementaridade perturbadas.

Resultados Experimentais
O FilterDDP foi validado em três problemas desafiadores de otimização de trajetória implícita de contato oriundos da robótica:

1. Balanço de Cart-pole (Cart-pole swing-up) com fricção de Coulomb.
2. Balanço de Acrobot (Acrobot swing-up) com limites rígidos de junta.
3. Empurramento não-preensil (Non-prehensile pushing) (manipulação) com desvio de obstáculos.

O algoritmo foi comparado contra:

• IPOPT: Um solver de programação não linear geral de última geração.
• IPOPT (B): Uma variante L-BFGS do IPOPT.
• ProxDDP: Um algoritmo DDP existente baseado em AL.

Descobertas:

• Robustez: O FilterDDP demonstrou robustez significativamente maior em comparação com métodos de primeira ordem (ProxDDP e IPOPT (B)). Notavelmente, o ProxDDP e o IPOPT (B) falharam em resolver a tarefa do acrobot, gerando soluções inviáveis ou degeneradas.
• Eficiência: O FilterDDP alcançou convergência em menos iterações e tempo de execução (wall-clock time) significativamente menor em comparação ao IPOPT. Nas três tarefas, o tempo médio de execução do FilterDDP foi aproximadamente 10–27% do tempo do IPOPT e 1–5% do tempo do IPOPT (B).
• Convergência: Resultados empíricos confirmaram a convergência quadrática local, validando a análise teórica.
• Estudo de Ablação: Remover as propostas escolhas de design (usar custo em vez de Lagrangiana, ou Hessianas não perturbadas) resultou em um aumento no número de iterações e maiores taxas de falha, confirmando a necessidade dessas modificações.

Significância e Alegações
O artigo afirma que o FilterDDP oferece uma alternativa robusta e eficiente para resolver OCPs com restrições de igualdade na robótica. Ao se afastar de abordagens de Lagrangiana aumentada e adotar um framework de filtro de busca de linha com modificações teóricas específicas (aceitação baseada em Lagrangiana e Hessianas perturbadas), os autores alcançam propriedades de convergência mais fortes e melhor desempenho numérico. O trabalho preenche a lacuna entre a eficiência do DDP e a robustez necessária para tarefas robóticas complexas e com restrições, fornecendo um solver que é mais rápido que solvers de propósito geral como o IPOPT, mantendo uma robustez comparável ou superior. Os autores observam que o trabalho futuro focará na aplicação do FilterDDP à locomoção de robôs de pernas de alta dimensão e no estabelecimento formal da convergência global.