Data-Driven Reachability Analysis for Piecewise Affine Systems

1. O Problema

O artigo aborda o desafio crítico da verificação de segurança em sistemas híbridos, especificamente Sistemas Afins por Partes (PWA - Piecewise Affine Systems).

• Contexto: Sistemas híbridos combinam dinâmicas contínuas com comutação de modos discretos (ex.: veículos autônomos, redes de energia). A análise de alcançabilidade determina se os estados do sistema podem entrar em regiões inseguras dadas condições iniciais e incertezas.
• Desafio Principal: Métodos tradicionais de análise de alcançabilidade dependem de modelos matemáticos exatos, que muitas vezes não estão disponíveis na prática. Além disso, métodos baseados em dados existentes falham nas transições de fronteira (onde a dinâmica muda abruptamente), produzindo aproximações inadequadas ou imprecisas das regiões alcançáveis.
• Objetivo: Desenvolver uma abordagem puramente baseada em dados para calcular conjuntos de alcançabilidade (over-approximations) para sistemas PWA, utilizando apenas dados de entrada-estado ou entrada-saída ruidosos, garantindo segurança mesmo sem conhecimento prévio do modelo.

2. Metodologia

A abordagem proposta utiliza Zonotopos Híbridos (Hybrid Zonotopes) para representar conjuntos de estados e modelos, permitindo lidar com a estrutura de múltiplos modos e fronteiras.

• Representação: O método emprega zonotopos híbridos, que combinam geradores contínuos e discretos, capazes de capturar a topologia complexa de sistemas PWA através das fronteiras das regiões.
• Análise de Alcançabilidade (Dados de Entrada-Estado):
  • Para dados com ruído de processo, o método divide os dados em subconjuntos correspondentes a cada modo de operação.
  • Utiliza um teorema estendido (baseado em trabalhos anteriores de Alanwar et al.) para calcular um familia de modelos matriciais (representada por zonotopos matriciais) que garantem conter o modelo real do sistema.
  • O algoritmo propaga o conjunto de estados através do tempo, realizando interseções com as regiões de definição de cada modo e aplicando a dinâmica de cada submodelo, garantindo que as transições entre modos sejam tratadas corretamente.
• Estimação de Estado Online (Dados de Entrada-Saída):
  • Estende o framework para lidar com medições ruidosas (ruído de processo e de medição).
  • Propõe e compara três técnicas de atualização de medição para refinar o conjunto de estados estimado:
    1. Mapeamento Reverso (Reverse-Mapping - RM): Usa decomposição SVD para construir explicitamente o zonotopo de estado compatível com a medição.
    2. Interseção Implícita (Implicit Intersection - IN): Otimiza pesos para minimizar o volume do conjunto resultante sem calcular explicitamente o zonotopo de medição.
    3. Interseção Generalizada (Generalized Intersection - GI): Formula as equações de medição como restrições adicionais na representação do zonotopo híbrido.

3. Contribuições Chave

O artigo apresenta quatro contribuições principais:

1. Método Baseado em Dados: Uma nova técnica utilizando zonotopos híbridos para calcular conjuntos de alcançabilidade de sistemas PWA diretamente a partir de medições ruidosas, sem necessidade de um modelo matemático prévio.
2. Gestão de Transições de Modo: Um algoritmo que lida explicitamente com múltiplos modos de operação e partições do espaço de estados, mantendo garantias de segurança durante as transições entre regiões.
3. Framework de Estimação de Estado: Uma estrutura abrangente para estimação de estado baseada em conjuntos para sistemas MIMO (Multiple-Input Multiple-Output) PWA com ruído de medição.
4. Equivalência Matemática: Prova formal de que as três técnicas de processamento de ruído (RM, IN e GI) são matematicamente equivalentes sob condições definidas (matrizes de medição de posto completo, ruído limitado por zonotopos), produzindo o mesmo conjunto de estados viáveis, embora com diferentes eficiências computacionais.

4. Resultados

Os resultados foram validados através de exemplos numéricos e benchmarks:

• Validação de Sobre-Aproximação: Em um sistema PWA de benchmark, os conjuntos alcançáveis derivados dos dados (baseados em zonotopos híbridos) contiveram consistentemente os conjuntos derivados do modelo analítico, validando a capacidade de sobre-approximação do método.
• Equivalência das Técnicas: Simulações demonstraram que os métodos RM, IN e GI produzem limites de estimação idênticos, confirmando a prova teórica de equivalência.
• Eficiência Computacional:
  • A análise de tempo de execução revelou um crescimento exponencial no tempo de computação conforme o horizonte temporal aumenta (desafio inerente a métodos de conjuntos).
  • Entre as três técnicas de estimação, o método Mapeamento Reverso (RM) mostrou-se o mais eficiente computacionalmente (tempo médio de 0,029s), seguido pela Interseção Generalizada (GI) e pela Interseção Implícita (IN).
• Robustez: Os métodos conseguiram conter a trajetória do estado real em todo o horizonte de simulação, mesmo na presença de ruído significativo.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

• Preenchimento de Lacuna Teórica: Resolve o problema específico de transições de fronteira em sistemas híbridos que métodos baseados em dados anteriores não conseguiam tratar adequadamente.
• Aplicabilidade Prática: Oferece uma ferramenta de verificação de segurança para sistemas críticos (como veículos autônomos e robótica) onde a modelagem matemática exata é difícil ou impossível de obter, mas dados de operação estão disponíveis.
• Garantias de Segurança: Ao fornecer sobre-approximações rigorosas, o método permite descartar falsos positivos e negativos em verificações de segurança, algo crucial para a certificação de sistemas autônomos.
• Direção Futura: Abre caminho para a análise de alcançabilidade em outros tipos de sistemas híbridos (como sistemas dinâmicos lógicos mistos) e para a investigação da acoplamento entre parâmetros de submodelos e fronteiras do sistema.

Em resumo, o artigo estabelece um novo paradigma para a verificação de segurança de sistemas híbridos complexos, combinando a flexibilidade da análise baseada em dados com a rigorosidade matemática dos zonotopos híbridos.