Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing

Resumo Técnico: Alocação de Sensores Provavelmente Eficiente para Sistemas de Alta Dimensionalidade Desconhecidos com Sensoriamento Limitado

Declaração do Problema
Este artigo aborda o desafio de aprender alocações eficientes de sensores para sistemas dinâmicos lineares de alta dimensionalidade desconhecidos ($x_{t+1} = Ax_t + Bu_t + w_t$), onde a dimensão do estado $r$ é grande. O objetivo é identificar um conjunto mínimo de sensores (coordenadas de estado) que garanta que o sistema seja observável, utilizando apenas um número limitado de sensores durante a fase de coleta de dados.

As abordagens existentes enfrentam duas limitações principais neste cenário:

1. Dependência de Modelo: Os métodos clássicos de alocação de sensores exigem conhecimento exato das matrizes do sistema ($A, B$), que estão indisponíveis em sistemas desconhecidos.
2. Requisitos de Dados: Os métodos padrão de identificação de sistemas (SYSID) tipicamente exigem observações de estado completo (proibitivamente caras) ou assumem a existência de uma alocação inicial de sensores que já garanta a observabilidade (dependência circular).

Metodologia
Os autores propõem um framework de duas etapas para superar essas limitações, operando sob a suposição de que o sistema é controlável e estável (Suposições 1 e 2).

• Etapa 1: Identificação de Sistemas com Seleção Dinâmica de Medição
  Os autores introduzem um novo algoritmo de SYSID (Algoritmo 1) que não exige medições de estado completo ou uma alocação observável pré-existente.

  • Coleta de Dados: Em vez de medir todos os estados simultaneamente, o algoritmo coleta $K$ trajetórias. Em cada trajetória $k$, um pequeno número de sensores ($\bar{n}$) mede um subconjunto específico, potencialmente diferente, de coordenadas de estado.
  • Estratégia de Medição: As matrizes de medição $C_k$ são projetadas ciclicamente para garantir que cada coordenada de estado seja observada em pelo menos $s$ trajetórias ($s_{min} \ge 1$).
  • Estimação: O algoritmo aproveita uma expansão recursiva da dinâmica do estado para expressar o estado como uma combinação linear de entradas passadas (parâmetros de Markov). Ao realizar regressão de mínimos quadrados nesses pares entrada-saída através de todas as trajetórias, o algoritmo estima a matriz de parâmetros de Markov $G = [B, AB, \dots, A^dB]$.
  • Recuperação: As matrizes do sistema $\hat{A}$ e $\hat{B}$ são subsequentemente recuperadas a partir dos parâmetros de Markov estimados usando uma abordagem de pseudo-inversa, desde que a classificação de estimação $d \ge r$.

• Etapa 2: Alocação de Sensores Baseada em Dados
  Utilizando as matrizes do sistema estimadas na Etapa 1, os autores adaptam um algoritmo de alocação de sensores ganancioso (Algoritmo 2) para selecionar o conjunto final de sensores.

  • Sub-rotina de Estimação de Classificação: Um componente crítico é uma sub-rotina de estimação de classificação (Algoritmo 3) que estima a classificação da matriz de observabilidade $\mathcal{O}(\hat{C})$ usando a estimativa ruidosa $\hat{A}$. Esta sub-rotina emprega um limiar cuidadosamente derivado com base nos limites de erro de estimação para distinguir entre valores singulares não nulos e nulos.
  • Seleção Gananciosa: O algoritmo adiciona iterativamente sensores à coordenada de estado que maximiza o aumento estimado da classificação da matriz de observabilidade até que a classificação completa ($r$) seja alcançada.

• Extensão para Coordenadas Inacessíveis
  O framework é estendido para cenários onde certas coordenadas de estado são fisicamente inacessíveis para colocação de sensores. O algoritmo restringe o espaço de busca às coordenadas acessíveis e utiliza uma matriz de Hankel estimada, construída a partir das linhas acessíveis dos parâmetros de Markov, para realizar a estimação de classificação (Algoritmo 4).

Principais Contribuições e Resultados Teóricos

1. Limites de Erro Não Assintóticos para SYSID: O artigo fornece garantias de amostra finita para o algoritmo de SYSID proposto. O Teorema 1 estabelece que o erro na estimação dos parâmetros de Markov decai como $\tilde{O}(\sqrt{md/(s_{min}T)})$, onde $m$ é a dimensão da entrada, $d$ é a classificação de estimação, $T$ é o comprimento da trajetória e $s_{min}$ é o número mínimo de vezes que qualquer estado é observado. Crucialmente, isso vale mesmo com um único sensor ($\bar{n}=1$), desde que sejam coletadas trajetórias suficientes.
2. Garantias de Alocação de Sensores: O Teorema 2 e o Teorema 3 provam que o framework de duas etapas proposto produz uma alocação de sensores que garante a observabilidade. O número de sensores utilizados, $\hat{n}$, é limitado por $(1 + \log(r))n^*$, onde $n^*$ é o número mínimo ótimo de sensores necessários. Esta razão de aproximação iguala os resultados mais conhecidos para sistemas conhecidos, apesar de operar sobre modelos aprendidos e aproximados.
3. Robustez à Inacessibilidade: O framework lida com sucesso com sistemas que possuem coordenadas de estado inacessíveis, desde que as coordenadas acessíveis sejam suficientes para garantir a observabilidade (Suposição 3).

Validação Experimental
Os autores validam sua abordagem por meio de experimentos numéricos em dois modelos:

• Sistema Cíclico em Blocos: Um sistema onde a observabilidade requer um sensor por bloco. O algoritmo aprendeu com sucesso os parâmetros do sistema e identificou uma alocação ótima de 5 sensores.
• Dinâmica Térmica (HVAC): Um sistema de 20 zonas com 5 coordenadas inacessíveis. O algoritmo aprendeu a dinâmica usando apenas medições acessíveis e identificou uma alocação ótima de 10 sensores (dois por bloco) para garantir a observabilidade.

Significado
O artigo afirma preencher a lacuna entre a alocação teórica de sensores (que assume modelos conhecidos) e o controle prático baseado em dados (que frequentemente carece de observabilidade completa). Ao desacoplar o processo de identificação de sistemas da exigência de observabilidade de estado completo, o método proposto permite o aprendizado de configurações de sensores eficientes para sistemas de alta dimensionalidade onde os sensores são escassos, caros ou restritos a locais específicos. As garantias não assintóticas fornecem uma base teórica para a confiabilidade dessas alocações baseadas em dados em aplicações críticas para a segurança, como redes elétricas, previsão do tempo e neurociência.