Resumo Técnico: FALCON para Problemas de Equilíbrio de Nash Generalizado Parcialmente Desacoplados Não Convexos

Formulação do Problema

O artigo aborda o desafio de resolver problemas de controle ótimo multiagente em aeroespacial e robótica, modelando-os especificamente como jogos diferenciais não convexos. Os autores focam em uma subclasse específica de Problemas de Equilíbrio de Nash Generalizado (GNEPs) denominada Problemas de Equilíbrio de Nash Generalizado Parcialmente Desacoplados (PDGNEPs).

Nesta formulação, $N$ agentes buscam minimizar funções de custo individuais $J_i$ sujeitas a:

1. Dinâmicas Separáveis: Cada agente $i$ evolui de acordo com suas próprias dinâmicas $\dot{x}_i(t) = f(x_i(t), u_i(t))$, independentemente dos controles ou estados dos outros agentes.
2. Restrições Acopladas: Os agentes são acoplados através de restrições de igualdade e desigualdade compartilhadas $C(X, \Upsilon) \leq 0$, que podem depender das trajetórias de todos os agentes.
3. Objetivo: Encontrar um Equilíbrio de Nash em Malha Aberta (Open-Loop), definido como um conjunto de estratégias onde nenhum agente pode unilateralmente melhorar seu custo ao se desviar, dadas as estratégias dos outros.

Métodos existentes enfrentam limitações: Jogos de LQ Iterativos (iLQGames) carecem de tratamento nativo de restrições; Jogos de Lagrangiana Aumentada (ALGAMES) mostram desempenho melhorado, mas lutam contra não convexidades acentuadas; e o Programação Quadrática Sequencial para Jogos Diferenciais (DG-SQP) oferece garantias de convergência, mas frequentemente sofre com altos custos computacionais e instabilidade numérica em cenários altamente não convexos.

Metodologia: O Algoritmo FALCON

Os autores propõem o FALCON (Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria), um algoritmo que combina Programação Convexa Sequencial (SCP) com uma estrutura de Lagrangiana Aumentada. A metodologia central procede da seguinte forma:

1. Implementação de Restrições em Tempo Contínuo

Para abordar a questão das violações de restrição entre amostras, comum em solvers de SCP discretizados, os autores reformulam as restrições usando uma abordagem de penalidade exterior.

• Uma medida de tempo contínuo da violação de restrição, $\Lambda_i(t)$, é definida usando uma função de penalidade cúbica $q(z) = [z]_+^3$ (escolhida pela suavidade $C^2$).
• Uma variável de estado aumentada $y_i(t)$ acumula essa violação ao longo do tempo.
• As restrições são impostas não apenas nos nós de discretização, mas ao longo de todo o horizonte contínuo, limitando a acumulação de $y_i$ entre os nós, garantindo a satisfação pontual da restrição dentro de um limite teórico $\delta(\varepsilon)$.

2. Reformulação de Epígrafo e Lagrangiana Aumentada

Para lidar com objetivos e restrições não convexos:

• Forma de Epígrafo: A função de custo não convexa $J_i$ é deslocada para as restrições via uma variável de epígrafo $\tau_i$, minimizando $\tau_i$ sujeito a $J_i \leq \tau_i$. Isso permite linearizar o objetivo enquanto mantém a não convexidade nas restrições.
• Lagrangiana Aumentada: Uma função lagrangiana aumentada $L_i$ é construída, incorporando multiplicadores de Lagrange ($\lambda, \mu$) e pesos de penalidade ($\omega$) para as dinâmicas e restrições de acoplamento.

3. Convexificação Sequencial (SCvx*)

O jogo não convexo é aproximado iterativamente pela resolução de uma sequência de subproblemas convexos:

• Linearização: As dinâmicas e restrições são linearizadas em torno de uma trajetória de referência $\bar{z}$.
• Relaxação: Variáveis de controle virtual ($\xi$) e buffer virtual ($\zeta$) são introduzidas para mitigar a inviabilidade artificial causada pela linearização.
• Região de Confiança: Uma restrição de região de confiança $\|z - \bar{z}\|_\infty \leq r$ garante que a aproximação permaneça válida.
• Reformulação de Jogo de Potencial: O subproblema convexo resultante é estruturado como um Equilíbrio de Nash Generalizado Variacional (v-GNE). Ao construir uma função de potencial fortemente convexa $\Phi_k$ (soma dos objetivos penalizados individuais), o subproblema é resolvido eficientemente como um Programa de Cônicas de Segundo Ordem (SOCP).

4. Loop Algorítmico

O algoritmo itera através de:

1. Linearização Sucessiva: Criando o subproblema convexo.
2. Aceitação de Passo: Avaliando a "qualidade" do passo usando uma razão de potencial conjunta $\rho_k$ (comparando a redução de custo real vs. a redução prevista). Os passos são aceitos se $\rho_k$ exceder um limiar.
3. Atualização de Multiplicadores: Os multiplicadores de Lagrange e os pesos de penalidade são atualizados com base nas violações de restrição e uma tolerância $\delta_k$ definida pelo usuário.
4. Ajuste da Região de Confiança: O raio da região de confiança $r$ é ajustado dinamicamente (contraído ou expandido) com base na razão de aceitação.

Principais Contribuições

1. Desenvolvimento de Algoritmo: Introdução do FALCON, um novo algoritmo que resolve PDGNEPs não convexos combinando convexificação sequencial com técnicas de lagrangiana aumentada.
2. Garantias Teóricas: Prova de convergência global para um equilíbrio de Nash em malha aberta sob suposições moderadas (aceleração limitada, continuidade Lipschitz, suavidade $C^2$). A solução é garantida como dinamicamente viável e aproximadamente viável de acoplamento em um sentido de tempo contínuo.
3. Segurança em Tempo Contínuo: Uma formulação rigorosa para impor restrições continuamente entre os nós de discretização, prevenindo violações de segurança nos intervalos entre amostras.
4. Eficiência: Demonstração de que o subproblema convexificado pode ser resolvido como um jogo de potencial usando solvers SOCP eficientes, evitando os gargalos computacionais dos métodos DG-SQP anteriores.

Resultados Numéricos

Os autores validam o FALCON em três cenários distintos de jogos diferenciais não convexos:

1. F1 Austin Racing (2 Jogadores):

   • Cenário: Dois carros correndo em uma curva fechada da pista de F1 de Austin.
   • Desempenho: O FALCON alcançou uma taxa de convergência de 100% em várias condições iniciais, enquanto o DG-SQP convergiu apenas 72% das vezes.
   • Velocidade: O FALCON foi significativamente mais rápido, com um tempo de computação médio de 0,873 segundos comparado aos 50,021 segundos do DG-SQP. O ALGAMES falhou em convergir neste caso difícil sob os mesmos padrões.

2. Corredores Estreitos (3 Jogadores):

   • Cenário: Três agentes unicycle navegando em um corredor com dois pontos de estrangulamento enquanto mantêm a prevenção de colisões e restrições de alcance de comunicação.
   • Observação: O algoritmo lidou com sucesso com o ambiente não convexo, demonstrando comportamentos cooperativos emergentes (ex: agentes sequenciando sua passagem pelos pontos de estrangulamento) enquanto cumpre estritamente as restrições de tempo contínuo.

3. Espacial Lady-Bandit-Guard (3 Jogadores):

   • Cenário: Um jogo heterogêneo em $R^6$ (dinâmicas de Clohessy-Wiltshire-Hill) envolvendo uma "Lady" (ativo de alto valor), um "Bandit" (atacante) e um "Guard" (defensor).
   • Observação: O FALCON resolveu o complexo jogo de perseguição-evasão-defesa, simulando com sucesso cenários onde o guarda bloqueia o bandit para permitir que a lady escape, lidando com as não convexidades da geometria de engajamento.

Significância e Alegações

O artigo afirma que o FALCON representa um avanço significativo na resolução de jogos diferenciais multiagente ao unir eficiência computacional e garantias de convergência teórica.

• Diferenciação: Ao contrário dos iLQGames, o FALCON lida nativamente com restrições de estado e controle. Ao contrário do DG-SQP, oferece desempenho numérico superior e robustez em configurações altamente não convexas sem sacrificar as garantias de convergência.
• Segurança: A formulação de restrição em tempo contínuo é destacada como uma característica crítica para aplicações aeroespaciais críticas de segurança, onde violações entre amostras são inaceitáveis.
• Escalabilidade: Ao reduzir o loop interno para um jogo de potencial resolvível via SOCP, o método oferece uma abordagem escalável para sistemas multiagente complexos.

Os autores concluem que o FALCON fornece um framework robusto, rápido e teoricamente fundamentado para resolver jogos diferenciais não convexos, tornando-o adequado para operações aeroespaciais complexas, como perseguição-evasão, operações espaciais contestadas e guiagem cooperativa.