El contraejemplo de Witsenhausen , que se muestra en la figura siguiente, es un problema de juguete engañosamente simple en el control estocástico descentralizado . Fue formulado por Hans Witsenhausen en 1968. [1] Es un contraejemplo de una conjetura natural que uno puede generalizar un resultado clave de control centralizado lineal-cuadrático-gaussianosistemas, que en un sistema con dinámica lineal, perturbación gaussiana y costo cuadrático, las leyes de control afines (lineales) son óptimas, a los sistemas descentralizados. Witsenhausen construyó un sistema gaussiano cuadrático lineal de dos etapas donde los tomadores de decisiones toman dos decisiones con información descentralizada y mostró que para este sistema, existen leyes de control no lineales que superan todas las leyes lineales. El problema de encontrar la ley de control óptima sigue sin resolverse. [2]
Declaración del contraejemplo
El enunciado del contraejemplo es simple: dos controladores intentan controlar el sistema intentando acercar el estado a cero en exactamente dos pasos de tiempo. El primer controlador observa el estado inicial Hay un costo en la entrada. del primer controlador, y un costo en el estado después de la entrada del segundo controlador. La entrada del segundo controlador es gratuito, pero se basa en observaciones ruidosas del Estado después de la entrada del primer controlador. El segundo controlador no puede comunicarse con el primer controlador y, por lo tanto, tampoco puede observar el estado original. o la entrada del primer controlador. Por lo tanto, la dinámica del sistema es
con la ecuación de observación del segundo controlador
El objetivo es minimizar una función de costo esperado ,
donde la expectativa se toma sobre la aleatoriedad en el estado inicial y el ruido de la observación , que se distribuyen de forma independiente . El ruido de la observaciónse supone que se distribuye de manera gaussiana , mientras que la distribución del valor del estado inicial difiere según la versión particular del problema.
El problema es encontrar funciones de control
que dan al menos un valor tan bueno de la función objetivo como cualquier otro par de funciones de control. Witsenhausen demostró que las funciones óptimas y no puede ser lineal.
Resultados específicos de Witsenhausen
Witsenhausen obtuvo los siguientes resultados:
- Existe un óptimo (Teorema 1).
- La ley de control óptimo del primer responsable del tratamiento es tal que (Lema 9).
- La solución exacta se da para el caso en el que ambos controladores están obligados a ser lineales (Lema 11).
- Si tiene una distribución gaussiana y si al menos uno de los controladores está restringido a ser lineal, entonces es óptimo que ambos controladores sean lineales (Lema 13).
- Las leyes de control no lineales exactas se dan para el caso en el que tiene una distribución simétrica de dos puntos (Lema 15).
- Si tiene una distribución gaussiana, para algunos valores del parámetro de preferencia Se da una solución no lineal no óptima para las leyes de control que da un valor más bajo para la función de costo esperado que el mejor par lineal de leyes de control (Teorema 2).
La importancia del problema
El contraejemplo se encuentra en la intersección de la teoría del control y la teoría de la información . Debido a su dureza, el problema de encontrar la ley de control óptima también ha recibido atención por parte de la comunidad informática teórica . La importancia del problema se reflejó en la 47ª Conferencia del IEEE sobre Decisión y Control (CDC) 2008, Cancún, México, [2] donde se dedicó una sesión completa a comprender el contraejemplo 40 años después de su formulación inicial.
El problema es de importancia conceptual en el control descentralizado porque muestra que es importante que los controladores se comuniquen [3] implícitamente entre sí para minimizar el costo. Esto sugiere que las acciones de control en el control descentralizado pueden tener un doble rol: las de control y comunicación.
La dureza del problema
La dureza del problema se atribuye al hecho de que la información del segundo controlador depende de las decisiones del primer controlador. [4] Las variaciones consideradas por Tamer Basar [5] muestran que la dureza también se debe a la estructura del índice de rendimiento y al acoplamiento de diferentes variables de decisión. También se ha demostrado que los problemas del espíritu del contraejemplo de Witsenhausen se vuelven más simples si el retardo de transmisión a lo largo de un canal externo que conecta los controladores es menor que el retardo de propagación en el problema. Sin embargo, este resultado requiere que los canales sean perfectos e instantáneos, [6] y por lo tanto tiene una aplicabilidad limitada. En situaciones prácticas, el canal es siempre imperfecto y, por lo tanto, no se puede suponer que los problemas de control descentralizado sean simples en presencia de canales externos.
Una justificación del fracaso de los intentos que discretizan el problema provino de la literatura informática: Christos Papadimitriou y John Tsitsiklis demostraron que la versión discreta del contraejemplo es NP-completo . [7]
Intentos de obtener una solución
Se han realizado varios intentos numéricos para resolver el contraejemplo. Centrarse en una elección particular de parámetros de problemas, los investigadores han obtenido estrategias mediante la discretización y el uso de redes neuronales . [8] Investigaciones posteriores (en particular, el trabajo de Yu-Chi Ho , [9] y el trabajo de Li, Marden y Shamma [10] ) han obtenido costos ligeramente mejorados para la elección del mismo parámetro. Los resultados numéricos más conocidos para una variedad de parámetros, incluido el mencionado anteriormente, se obtienen mediante un algoritmo de búsqueda local propuesto por S.-H. Tseng y A. Tang en 2017. [11] Las primeras estrategias probables aproximadamente óptimas aparecieron en 2010 (Grover, Park, Sahai) [12] donde la teoría de la información se utiliza para comprender la comunicación en el contraejemplo. La solución óptima del contraejemplo sigue siendo un problema abierto.
Referencias
- ^ Witsenhausen, Hans. "Un contraejemplo de control óptimo estocástico". SIAM J. Control , Volumen 6, Número 1, págs. 131–147 (febrero de 1968)
- ^ a b Ho, Yu-Chi, "Revisión del problema de Witsenhausen". Actas de la 47ª Conferencia del IEEE sobre Decisión y Control (CDC) , págs. 1611–1613, 2008.
- ^ Mitterrand y Sahai. "Información y control: Witsenhausen revisitado". Aprendizaje, control y sistemas híbridos , 1999, Springer.
- ^ Ho, Yu-Chi. "Teoría de la decisión en equipo y estructuras de información". Actas del IEEE , vol. 68, No 6, junio de 1980.
- ^ Basar, Tamer. "Variaciones sobre el tema del contraejemplo de Witsenhausen". 47ª Conferencia IEEE sobre Decisión y Control Cancún , México, 9 al 11 de diciembre de 2008.
- ↑ Rotkowitz, M .; Cogill, R .; Lall, S .; , "Una condición simple para la convexidad de un control óptimo sobre redes con retrasos", Decisión y control , 2005 y 2005 European Control Conference. CDC-ECC '05. 44th IEEE Conference on , págs. 6686–6691, 12–15 de diciembre de 2005.
- ^ Christos Papadimitriou y John Tsitsiklis . "Problemas intratables en la teoría del control". 24a Conferencia IEEE sobre Decisión y Control , 1985
- ^ Baglietto, Parisini y Zoppoli. "Soluciones numéricas al contraejemplo de Witsenhausen mediante la aproximación de redes". Transacciones IEEE sobre control automático . 2001.
- ^ Lee, Lau y Ho. "El contraejemplo de Witsenhausen: un enfoque de búsqueda jerárquica para problemas de optimización no convexos". Transacciones IEEE sobre control automático , 2001
- ^ Li, Marden y Shamma. "Aprender enfoques del contraejemplo de Witsenhausen desde una perspectiva de juegos potenciales". Conferencia IEEE sobre Decisión y Control , 2009.
- ^ Tseng y Tang. "Un algoritmo de búsqueda local para el contraejemplo de Witsenhausen". Conferencia IEEE sobre Decisión y Control , 2017.
- ^ Grover, Sahai y Park. "El contraejemplo de Witsenhausen de dimensión finita". IEEE WiOpt 2010, taller de ConCom , Seúl, Corea.