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

Resumen Técnico: Asignación de Sensores Probablemente Eficiente para Sistemas de Alta Dimensión Desconocidos con Sensado Limitado

Enunciado del Problema
Este artículo aborda el desafío de aprender asignaciones eficientes de sensores para sistemas dinámicos lineales de alta dimensión desconocidos ($x_{t+1} = Ax_t + Bu_t + w_t$) donde la dimensión del estado $r$ es grande. El objetivo es identificar un conjunto mínimo de sensores (coordenadas del estado) que asegure que el sistema sea observable, utilizando únicamente un número limitado de sensores durante la fase de recolección de datos.

Los enfoques existentes enfrentan dos limitaciones principales en este escenario:

1. Dependencia del Modelo: Los métodos clásicos de asignación de sensores requieren un conocimiento exacto de las matrices del sistema ($A, B$), las cuales no están disponibles en sistemas desconocidos.
2. Requisitos de Datos: Los métodos estándar de identificación de sistemas (SYSID) típicamente requieren observaciones de estado completo (prohibitivamente costosas) o asumen la existencia de una asignación inicial de sensores que ya garantice la observabilidad (dependencia circular).

Metodología
Los autores proponen un marco de dos etapas para superar estas limitaciones, operando bajo la suposición de que el sistema es controlable y estable (Suposiciones 1 y 2).

• Etapa 1: Identificación de Sistemas con Selección Dinámica de Mediciones
  Los autores introducen un nuevo algoritmo de SYSID (Algoritmo 1) que no requiere mediciones de estado completo ni una asignación observable preexistente.

  • Recolección de Datos: En lugar de medir todos los estados simultáneamente, el algoritmo recopila $K$ trayectorias. En cada trayectoria $k$, un pequeño número de sensores ($\bar{n}$) mide un subconjunto específico, potencialmente diferente, de coordenadas del estado.
  • Estrategia de Medición: Las matrices de medición $C_k$ se diseñan cíclicamente para asegurar que cada coordenada del estado sea observada en al menos $s$ trayectorias ($s_{min} \ge 1$).
  • Estimación: El algoritmo aprovecha una expansión recursiva de la dinámica del estado para expresar el estado como una combinación lineal de entradas pasadas (parámetros de Markov). Al realizar regresión de mínimos cuadrados en estos pares entrada-salida a través de todas las trayectorias, el algoritmo estima la matriz de parámetros de Markov $G = [B, AB, \dots, A^dB]$.
  • Recuperación: Las matrices del sistema $\hat{A}$ y $\hat{B}$ se recuperan posteriormente de los parámetros de Markov estimados utilizando un enfoque de pseudo-inversa, siempre que el rango de estimación $d \ge r$.

• Etapa 2: Asignación de Sensores Basada en Datos
  Utilizando las matrices del sistema estimadas de la Etapa 1, los autores adaptan un algoritmo de asignación de sensores voraz (Algoritmo 2) para seleccionar el conjunto final de sensores.

  • Subrutina de Estimación de Rango: Un componente crítico es una subrutina de estimación de rango (Algoritmo 3) que estima el rango de la matriz de observabilidad $\mathcal{O}(\hat{C})$ utilizando la estimación ruidosa $\hat{A}$. Esta subrutina emplea un umbral cuidadosamente derivado basado en los límites de error de estimación para distinguir entre valores singulares no nulos y nulos.
  • Selección Voraz: El algoritmo agrega iterativamente sensores a la coordenada del estado que maximiza el aumento estimado del rango de la matriz de observabilidad hasta alcanzar el rango completo ($r$).

• Extensión a Coordenadas Inaccesibles
  El marco se extiende a escenarios donde ciertas coordenadas del estado son físicamente inaccesibles para la colocación de sensores. El algoritmo restringe el espacio de búsqueda a coordenadas accesibles y utiliza una matriz de Hankel estimada construida a partir de las filas accesibles de los parámetros de Markov para realizar la estimación de rango (Algoritmo 4).

Contribuciones Clave y Resultados Teóricos

1. Límites de Error No Asintóticos para SYSID: El artículo proporciona garantías de muestras finitas para el algoritmo de SYSID propuesto. El Teorema 1 establece que el error en la estimación de los parámetros de Markov decae como $\tilde{O}(\sqrt{md/(s_{min}T)})$, donde $m$ es la dimensión de entrada, $d$ es el rango de estimación, $T$ es la longitud de la trayectoria y $s_{min}$ es el número mínimo de veces que se observa cualquier estado. Crucialmente, esto se mantiene incluso con un solo sensor ($\bar{n}=1$) siempre que se recopilen suficientes trayectorias.
2. Garantías de Asignación de Sensores: El Teorema 2 y el Teorema 3 demuestran que el marco de dos etapas propuesto produce una asignación de sensores que garantiza la observabilidad. El número de sensores utilizados, $\hat{n}$, está acotado por $(1 + \log(r))n^*$, donde $n^*$ es el número mínimo óptimo de sensores requerido. Esta razón de aproximación coincide con los resultados mejor conocidos para sistemas conocidos, a pesar de operar sobre modelos aprendidos y aproximados.
3. Robustez ante Inaccesibilidad: El marco maneja exitosamente sistemas con coordenadas del estado inaccesibles, siempre que las coordenadas accesibles sean suficientes para garantizar la observabilidad (Suposición 3).

Validación Experimental
Los autores validan su enfoque mediante experimentos numéricos en dos modelos:

• Sistema Cíclico en Bloques: Un sistema donde la observabilidad requiere un sensor por bloque. El algoritmo aprendió exitosamente los parámetros del sistema e identificó una asignación óptima de 5 sensores.
• Dinámica Térmica (HVAC): Un sistema de 20 zonas con 5 coordenadas inaccesibles. El algoritmo aprendió la dinámica utilizando únicamente mediciones accesibles e identificó una asignación óptima de 10 sensores (dos por bloque) para garantizar la observabilidad.

Significado
El artículo afirma cerrar la brecha entre la asignación teórica de sensores (que asume modelos conocidos) y el control práctico basado en datos (que a menudo carece de observabilidad completa). Al desacoplar el proceso de identificación de sistemas del requisito de observabilidad de estado completo, el método propuesto permite aprender configuraciones de sensores eficientes para sistemas de alta dimensión donde los sensores son escasos, costosos o restringidos a ubicaciones específicas. Las garantías no asintóticas proporcionan una base teórica para la fiabilidad de estas asignaciones basadas en datos en aplicaciones críticas para la seguridad, como redes eléctricas, pronóstico del tiempo y neurociencia.