Maximizing Reach-Avoid Probabilities for Linear Stochastic Systems via Control Architectures

Resumo Técnico: Maximização de Probabilidades de Alcance-Evasão para Sistemas Estocásticos Lineares via Arquiteturas de Controle

Formulação do Problema
O artigo aborda o desafio de maximizar a probabilidade de alcance-evasão para sistemas estocásticos lineares em um horizonte de tempo finito. O sistema é definido por dinâmicas que contêm tanto estados que evoluem deterministicamente ($x_d$) quanto estados que evoluem probabilisticamente ($x_s$), sujeitos a ruído i.i.d. aditivo. O objetivo de controle é encontrar uma política que maximize a probabilidade de o sistema alcançar um conjunto alvo $T$ enquanto permanece dentro de um conjunto seguro $S$ durante um período $[0, T]$, tudo isso satisfazendo restrições determinísticas $G$ (como limites de entrada e limites de estado) em todos os momentos.

Métodos existentes enfrentam um compromisso: abordagens baseadas em limites estatísticos (ex: tubos estocásticos, MPC de cenário) oferecem escalabilidade, mas frequentemente resultam em um desempenho conservador, enquanto métodos de otimização direta (ex: Processos de Decisão de Markov - MDP) fornecem garantias rigorosas, mas são computacionalmente intratáveis para espaços de estados de alta dimensão ou contínuos.

Metodologia
Os autores propõem uma arquitetura de controle em camadas que combina a escalabilidade do Controle Preditivo Baseado em Modelo (MPC) com a otimalidade da Programação Dinâmica (DP). A inovação central reside em tratar o sistema de malha fechada (planta + MPC) como um Processo de Decisão de Markov (MDP) onde as "ações" são sinais de referência enviados ao MPC, em vez de entradas de controle diretas.

1. Arquitetura em Camadas:

   • Camada Inferior (MPC): Um Controlador Preditivo Baseado em Modelo (MPC) rastreia sinais de referência gerados pela camada superior. O MPC é projetado para ser agnóstico ao objetivo de alcance-evasão estocástico; seu único propósito é garantir que o sistema satisfaça as restrições determinísticas $G$ e os limites de entrada $U$. Para preencher a lacuna entre a otimização do MPC em tempo discreto e a satisfação de restrições em tempo contínuo, os autores derivam técnicas de estreitamento de restrições (Lema III.1) que levam em conta a dinâmica do sistema e o ruído ao longo do intervalo de amostragem.
   • Camada Superior (Gerador de Referência DP): Uma política baseada em DP opera em intervalos de tempo fixos ($\Delta t$). Ela seleciona sequências de referência (comandos) para o MPC para maximizar a probabilidade de alcançar o alvo enquanto evita regiões inseguras. O espaço de estados deste MDP é o estado do sistema $x_k$, e o espaço de ações consiste em um conjunto finito de trajetórias de referência.

2. Tratamento de Espaços de Estados Contínuos e Abstração:
   Como o espaço de estados é contínuo, os autores empregam uma abstração de grade finita para tornar a DP computacionalmente tratável. Para garantir que as garantias teóricas sejam preservadas apesar dessa discretização, eles introduzem um framework de robustecimento:

   • MPC Robusto (RMPC): O MPC é modificado para gerar sequências de entrada que são invariantes ao estado inicial específico dentro de uma célula de grade (partição). Isso é alcançado inicializando a predição do MPC a partir do centro da grade, em vez do estado medido, garantindo que a mesma sequência de controle seja aplicada a todos os estados dentro de uma partição.
   • Iteração de Valor Robusta: Os conjuntos seguros e de alvo são estreitados por um raio $r$ (derivado do desvio máximo das trajetórias dentro de um passo de tempo) para contabilizar erros de abstração. O algoritmo DP é modido para calcular um limite inferior na probabilidade de alcance-evasão, considerando transições de pior caso dentro da vizinhança de cada célula de grade.

Principais Contribuições

• Arquitetura de Controle: O artigo introduz uma nova arquitetura que reduz a dimensionalidade do espaço de planejamento da DP da dimensão total do estado $n$ para a dimensão do componente que evolui probabilisticamente $n_s$. Isso é alcançado aproveitando a evolução determinística de $x_d$ e as capacidades de rastreamento do MPC.
• Garantias Teóricas: Os autores fornecem certificados formais para a abordagem. Eles provam que a arquitetura robustecida garante a satisfação de restrições em tempo contínuo e que o valor computado pelo algoritmo de DP robusto serve como um limite inferior estrito na probabilidade de alcance-evasão real alcançada pelo sistema (Teorema IV.4).
• Escalabilidade e Flexibilidade: O método é demonstrado como escalável para sistemas de maior dimensão (especificamente um modelo de quadricóptero 12D) e flexível o suficiente para lidar com ambientes complexos e obstruídos.

Resultos
A abordagem foi validada em um modelo de quadricóptero 12D perturbado navegando em vários ambientes obstruídos (ex: labirintos, caminhos em zigue-zague e campos de obstáculos).

• Desempenho: Em um cenário de labirinto, a arquitetura alcançou uma taxa de sucesso de 40%, superando significativamente as linhas de base conservadoras.
• Comparação: Em múltiplos cenários, a probabilidade de alcance-evasão empírica ($V_0(x_0)$) consistentemente atingiu ou excedeu o limite inferior computado pela iteração de valor robusta ($\tilde{V}_0(x_0)$), validando as garantias teóricas. Por exemplo, em um ambiente "zigue-zague", a taxa de sucesso empírica foi de 44% comparada a um limite inferior teórico de 0,3%.
• Compromissos (Trade-offs): O artigo também demonstra a capacidade da arquitetura de resolver problemas de controle ótimo restritos. Ao ajustar um multiplicador de Lagrange, o sistema pode trocar o custo do caminho (manter a trajetória próxima a um centro) pela probabilidade de alcance-evasão, gerando uma fronteira de Pareto de soluções.

Significância e Alegações
O artigo afirma que este trabalho preenche a lacuna entre a otimalidade teórica dos métodos baseados em MDP e a escalabilidade prática do MPC. Ao desacoplar a aplicação de segurança (tratada pelo MPC robusto) da otimização probabilística (tratada pelo gerador de referência DP), os autores alcançam uma estratégia de controle que é tanto computacionalmente viável para sistemas de maior dimensão quanto capaz de fornecer certificados formais de alcance-evasão sem recorrer a limites estatísticos excessivamente conservadores. Os autores enfatizam que seu método fornece certificados formais para sistemas estocásticos, uma característica frequentemente ausente em abordagens heurísticas escaláveis, enquanto evita a intratabilidade computacional das soluções de MDP de estado completo.