Adversarial decision and optimization-based models

Résumé

INTRODUCCIÓN La toma de decisiones nos rodea. Todo el mundo lleva a cabo elecciones a diario, desde el mismo momento en que nos despertamos por la mañana: levantarse al instante o permanecer un rato en la cama; qué comida desayunar, coger el autobús o ir a pie al trabajo, etc. Por supuesto, las consecuencias de las decisiones que acabamos de mencionar no son demasiado importantes, más allá de ganar algunos kilos si tomamos un desayuno poco saludable, o llegar tarde al trabajo si el autobús que elegimos tomar se retrasa. Los factores que tenemos en cuenta para estas decisiones son bastante simples, dado que las consecuencias de cada elección están bien definidas. Sin embargo, en el mundo de los negocios, los directivos toman decisiones que tienen importantes consecuencias en el futuro de su propia empresa (en términos de beneficios, posicionamiento en el mercado o políticas de empresa) que a su vez influyen en la organización de la compañía y repercuten en los empleados. El número de factores que un director general debe tener en cuenta es grande y desgraciadamente, con frecuencia son difíciles de medir o incluso de darse cuenta de su existencia. La toma de decisiones es, por tanto, una actividad inherentemente humana. En la actualidad existe un interés creciente en incorporar capacidades propias de los humanos a los sistemas informáticos. Los Smart systems pueden definirse como sistemas autónomos o colaborativos que aúnan sensores, actuadores, informática y comunicaciones para ayudar a los usuarios o a otros sistemas a realizar una tarea. Por su propia naturaleza estos sistemas combinan funcionalidades. No sólo unen múltiples tecnologías sino que están fuertemente orientados a las aplicaciones concretas, en sectores como transporte, energía, salud, seguridad, manufacturación, etc. Están compuestos de sensores para adquisición de señal, elementos transmisores de la información a una unidad central que toma decisiones inteligentes basándose en la información disponible, y actuadores que llevan a cabo las acciones adecuadas según la decisión. La importancia de los Smart systems queda demostrada por su inclusión en los objetivos del programa Horizonte 2020 de la Unión Europea, en la convocatoria ICT-2 (Integración de Smart Systems. Una de sus principales características es precisamente la toma de decisiones, que utiliza la información suministrada por los sensores para intentar tomar la mejor decisión, tal como haría una persona. La pregunta es, ¿cómo se determina la mejor decisión? En el caso (ideal) de que un decisor (a) sea capaz de tener en cuenta perfectamente todas las consecuencias que puedan derivarse de una decisión (decisor perfectamente informado) y pueda cuantificarlas, (b) esté al tanto de todas las posibles alternativas para escoger, y (c) sea capaz de realizar todos los cálculos necesarios de una manera perfectamente racional, entonces la elección óptima será la acción cuya consecuencia sea la preferida del decisor por encima de todas las demás consecuencias asociadas a las demás acciones. Aún podrían discutirse algunos detalles de esta definición, como la manera de definir las preferencias, de cuantificarlas o si todos estos elementos serían percibidos y cuantificados de la misma forma por otros decisores que se encontrasen ante la misma situación. Además, la mayoría de las situaciones que requieren de un proceso riguroso de toma de decisiones presentan incertidumbre en muchos aspectos: una acción puede tener asociadas diferentes consecuencias que pueden darse o no con cierta probabilidad. La naturaleza probabilística de este proceso dio lugar a la disciplina conocida como Análisis de Decisión, que estudia desde una perspectiva formal cómo la gente debería tomar las decisiones. Los problemas estudiados por el Análisis de Decisión consideran que sólo hay un decisor involucrado en la decisión. Sin embargo, tomar una decisión cuando sabemos que existe alguien que observa y reacciona a nuestra elección constituye una situación bastante diferente al caso en el que no existe ningún adversario. Por ejemplo, podríamos preferir ocasionalmente una alternativa sub-óptima orientada a causar confusión en el adversario, de manera que sea más difícil para él predecir nuestras propias decisiones en el futuro. Esto llevaría a un mayor beneficio para nosotros a largo plazo. Consideremos el siguiente ejemplo. Un hombre de negocios va caminando a su trabajo todas las mañanas. Se trata de un hombre adinerado que posee una gran compañía con importantes beneficios anuales, así que es un potencial objetivo para un grupo terrorista que necesite financiación. Todos los días se marcha a las 8 de la mañana y sigue el mismo camino hasta su trabajo, no demasiado lejos. Sabe que en este caso, caminar es más rápido que ir en coche, y que su ruta es la más corta, por lo que puede afirmarse que su elección es la mejor para él. Sin embargo, si el hombre supiera que está siendo vigilado por alguien que intenta aprender sus costumbres, entonces debería cambiar deliberadamente su comportamiento para hacerlo más impredecible. Por ejemplo, podría tomar caminos alternativos ocasionalmente, o ir en coche o en autobús de vez en cuando, sin ningún patrón definido, a pesar de que todas estas elecciones son aparentemente peores dado que se gasta más tiempo en ellas. A pesar de todo, el resultado es que será más difícil secuestrarle en un día cualquiera, lo cual es sin duda la consecuencia que nuestro hombre de negocios prefiere. De este ejemplo se deduce que la manera en la que tomamos decisiones es diferente cuando sabemos que existe un adversario cuyas acciones afectan a nuestros beneficios. En su forma más general, este tema es conocido como decisión en presencia de adversarios y constituye el centro de la presente tesis. El razonamiento en presencia de adversarios trata en gran medida sobre la comprensión de la mente y las acciones de nuestro oponente. Es de interés para una gran variedad de problemas donde los actores son conscientes de la existencia del otro, y saben que están compitiendo contra otro cuyos objetivos son generalmente contrarios. El objetivo de este tipo de análisis es encontrar estrategias óptimas que tengan en cuenta no sólo nuestras propias preferencias sino también las creencias y preferencias de los oponentes según nosotros las percibimos. Esta situación se da en muchos campos de la vida real, especialmente (aunque no únicamente) en la lucha antiterrorista y en la prevención del crimen. Ciertamente, la amenaza del terrorismo ha incrementado la inversión y el interés en el desarrollo de técnicas y herramientas computacionales para el razonamiento en presencia de adversarios, sobre todo para seguridad nacional. Pueden encontrarse también aplicaciones menos dramáticas en los juegos de ordenador donde el usuario juega el papel de adversario frente a los personajes manejados por el ordenador, provistos de capacidades inteligentes de razonamiento con el fin de mejorar la calidad, la dificultad y la capacidad adaptación del juego, las cuales unidas proporcionan una mejor experiencia para el jugador. Otra utilidad similar a la anterior es el desarrollo de sistemas inteligentes de entrenamiento de personas. Este tipo de tecnologías persiguen la predicción de las estrategias del oponente, la anticipación a sus planes, y el reconocimiento de engaños. Los ámbitos de aplicación incluyen también los negocios, transacciones, conflictos entre gobiernos, finanzas, deportes de equipo (por ejemplo RoboCup), juegos como el póker, etc. En términos simples, un adversario es una entidad cuyos objetivos son opuestos a los nuestros, y que es capaz de influenciar las ganancias que obtenemos de nuestras decisiones eligiendo y ejecutando sus propias acciones. Este tipo de interacción competitiva entre dos actores ocurre en gran cantidad de situaciones y puede analizarse con un abanico variado de técnicas. Muchas están íntimamente ligadas a la Inteligencia Artificial (modelado basado en agentes, heurísticas, planificación, exploración de árboles, aprendizaje automático) pero también a la Ingeniería del Conocimiento (cómo representar y manejar el conocimiento sobre el adversario y el entorno) y la Investigación Operativa, con énfasis en la Teoría de Juegos. Varios problemas pueden formalizarse como juegos competitivos y resolverse utilizando la Teoría de Juegos o técnicas relacionadas. Revisaremos algunos de ellos, como los juegos de búsqueda, los juegos de seguridad y los problemas de patrullaje en el capítulo de Background. Objetivos y estructura de la tesis Teniendo en cuenta todo esto, el {\bf{objetivo general}} de esta tesis es el análisis y diseño de modelos de decisión y optimización en presencia de adversarios que sean capaces de modelar situaciones como las descritas anteriormente. Vamos a llevar a cabo estudios teóricos y a proponer aplicaciones prácticas relacionadas con los juegos de imitación, los juegos de seguridad y los modelos de patrullaje. Los objetivos específicos son los siguientes: 1. Recopilar las referencias relevantes en el campo de los modelos de decisión con adversarios y sus aplicaciones. 2. Desarrollar nuevos modelos y extensiones. 3. Proponer nuevas estrategias para estos modelos que tengan en cuenta la componente temporal. 4. Evaluar las estrategias desde un punto de vista teórico y empírico. 5. Proponer ejemplos de aplicación. Hemos abordado la decisión en presencia de adversarios desde dos puntos de vista diferentes. En primer lugar, nos hemos centrado en un modelo abstracto de imitación publicado en [65]. La situación consiste en un agente S que entra en repetidas ocasiones en una decisión de conflicto con un agente T, que es capaz de observar el comportamiento de S, aprender de él y utilizar lo aprendido para tomar decisiones que pueden cambiar (posiblemente disminuir) la ganancia de S con el fin de incrementar la suya propia. El trabajo citado estudia el balance entre el grado de confusión introducido mediante decisiones sub-óptimas y los beneficios que se pueden obtener de ellas a largo plazo. Los autores concluyen que las estrategias aleatorizadas son útiles para esto. Revisamos el modelo en el capítulo 2 junto con otros conceptos necesarios para entender el resto de la tesis y algunos problemas relacionados. Hemos publicado tres artículos que tratan sobre este modelo o extensiones al mismo, en conexión con los objetivos 2, 3 y 4. En consecuencia, hay tres capítulos dedicados al modelo de imitación. El capítulo 3, que contiene el material publicado en [90], explica cómo obtener una expresión teórica de la ganancia del agente S cuando utiliza estrategias simples de decisión que habían sido propuestas en [65]. La expresión es validada mediante simulaciones computacionales, como indican los objetivos 3 y 4. Los capítulos 4 y 5 también se centran en la obtención de una expresión matemática del pago en dos extensiones diferentes del modelo de imitación, en consonancia con los objetivos 2 a 4. El material de estos capítulos está publicado en [93] y [92], respectivamente. Más concretamente, el capítulo 4 se centra en una versión simplificada del modelo y estudia el caso en el que el agente S utiliza una distribución de probabilidad optimizada sobre sus acciones. Después, se demuestra que cambiar en ciertos instantes la distribución de probabilidad empleada, tras una serie de encuentros con el adversario, puede ser beneficioso. Por su parte, el capítulo 5 extiende el modelo original introduciendo dependencia estadística entre la decisión tomada por S en el momento actual y el conjunto de pagos que podrán obtenerse como resultado de las decisiones del siguiente instante. De modo similar, se calculan expresiones matemáticas del pago de estrategias de decisión optimizadas para esta nueva situación. En segundo lugar, hemos desarrollado dos trabajos con aplicaciones concretas de la decisión en presencia de adversarios. El primero de ellos [94], correspondiente al capítulo 6, explica cómo mejorar la información obtenida a partir de la observación de un agente del cual se sabe que se encuentra en una situación frente a un adversario. Dicha situación es el patrullaje de un área para protegerla frente a intrusiones. Presentamos para ello un procedimiento matemático y un paquete software que lo implementa, siguiendo los objetivos 4 y 5. El segundo de ellos, aún no publicado (capítulo 7), describe un nuevo modelo de patrullaje para un vehículo aéreo no tripulado que vuela sobre un área industrial para protegerla de intrusos terrestres. A diferencia del primero, este modelo está concebido específicamente para un agente que va volando sobre el terreno sin limitaciones de movimiento. Propondremos una solución basada en teoría de juegos bajo el marco general de los juegos de seguridad. Por tanto, aquí hacemos referencia a los objetivos 2 a 5. Parte de este trabajo se completó durante la estancia breve de investigación realizada por el autor en el Teamcore Research Group on Agents and Multi-agent Systems, Computer Science Department, University of Southern California, Los Ángeles (EEUU). Finalmente, el capítulo 8 está dedicado a conclusiones generales, así como a algunas posibles líneas futuras que pueden investigarse en relación con los diferentes modelos descritos a lo largo de la tesis. CONCLUSIONES Esta tesis se ha centrado en el estudio y desarrollo de modelos de decisión en presencia de adversarios y su aplicación a problemas prácticos, tal como marcaban los objetivos mencionados más arriba. Con respecto al objetivo 1, se ha alcanzado siguiendo los dos puntos de vista mencionados en la introducción: a) Por un lado, hemos continuado investigando sobre el modelo de imitación [65], para el cual hemos desarrollado dos extensiones. En la primera de ellas, hemos mostrado la importancia de contar con un modelo apropiado del adversario, así como el impacto negativo que tiene sobre el pago de un agente hacer suposiciones erróneas acerca del adversario. Esta extensión considera explícitamente la componente temporal de una estrategia con el fin de cambiar la aleatorización que guía el movimiento de uno de los agentes. Mientras que esto incrementa el pago total cuando el adversario se ajusta a la concepción que tenemos de él, también puede suponer importantes pérdidas cuando esto no ocurre. En la segunda extensión, hemos introducido dependencia estadística entre la decisión actual tomada por uno de los agentes y las circunstancias (modeladas como el conjunto de pagos que se podrán obtener) de la siguiente decisión que ese agente tenga que tomar. Hemos mostrado que el mismo concepto de estrategias aleatorizadas que varían en el tiempo también resulta ventajoso en este nuevo escenario. b) Por otro lado, hemos desarrollado un modelo con adversarios para una situación real en el contexto de los juegos de seguridad: un dron que protege un área frente a intrusos. La propuesta toma en consideración de manera realista las limitaciones físicas de los agentes, tales como la duración de la batería del dron y su velocidad, la existencia de grafos separados de movimiento para el dron y para los intrusos terrestres, el radio de percepción limitado del dron (que depende de la cámara a bordo), etc. Hemos explicado las dificultades del cálculo del equilibrio de Stackelberg en nuestro modelo debido a que el problema de optimización que resulta, pese a ser lineal, es intratable en la práctica debido al alto número de estrategias existentes. Se ha sugerido la utilización de técnicas heurísticas para remediarlo. En lo que respecta al objetivo 3, se han investigado nuevas estrategias que no sólo son aleatorizadas sino que cambian la aleatorización a lo largo del tiempo, lo cual se ha demostrado beneficioso para llevar a engaño al adversario y conseguir un mayor pago. Esto confirma que es posible la manipulación estratégica cuando la única información disponible para el adversario consiste en observaciones sobre las acciones pasadas. Por lo tanto, cuando un agente se sabe observado, es ventajoso para él modificar la manera en que toma las decisiones para causar engaño y obtener un mayor pago a largo plazo, tal y como se ha logrado con las estrategias que varían en el tiempo. En todas las publicaciones hemos analizado el rendimiento de las estrategias tanto desde un punto de vista teórico como empírico, con el fin de validar las expresiones analíticas que se habían deducido, tal y como nos habíamos marcado en el objetivo 4. Esto ha demostrado también que no es necesario llevar a cabo simulaciones para comparar dos estrategias aleatorizadas si podemos obtener correctamente el pago esperado que se obtendrá con dicha estrategia aplicando conceptos de la teoría de la probabilidad. Comparar el pago esperado es una manera mucho más fiable de determinar qué estrategia funciona mejor. Finalmente, en relación al objetivo 5, hemos propuesto dos aplicaciones: por un lado, el modelo de patrullaje para un dron mencionado anteriormente, y por otro, una nueva técnica matemática para mejorar la información obtenida mediante las observaciones de un agente que está patrullando un área siguiendo una estrategia aleatorizada Markoviana. Estas observaciones constituyen la percepción que el intruso tiene acerca del defensor cuando el primero observa al segundo con el objetivo de aprender su aleatorización, tal como se suele asumir en los juegos de seguridad. Hemos mostrado que utilizando conceptos de Lógica Difusa y Números Difusos, el intruso puede tener una mejor aproximación de las verdaderas probabilidades que guían el movimiento del agente que patrulla, ya que un número difuso es más informativo porque incorpora la incertidumbre que rodea a una cantidad. Hemos implementado un paquete software de código abierto con el método propuesto y lo hemos incorporado a un repositorio público para que esté a disposición de la comunidad investigadora. TRABAJOS FUTUROS Tanto el juego de imitación como los modelos de patrullaje aún precisan de mayor investigación. En el modelo de imitación, no se han investigado algunas técnicas que podrían dar buenos resultados, tales como el uso de mecanismos de aprendizaje más sofisticados para el agente T (por ejemplo, aprendizaje por refuerzo) que le facilitarían aprender la estrategia de S. Además, el juego de imitación podría abordarse como un problema de clasificación para el que se pueden aplicar algoritmos de aprendizaje automático para determinar cuál de entre las posibles alternativas va a ser elegida a continuación por el agente $S$. Por último, deben aún examinarse aplicaciones reales de este modelo, especialmente orientadas al ámbito de los juegos de ordenador. Una mejor predicción de las acciones del usuario llevará a adversarios más inteligentes que mejorarán la experiencia del juego por parte del usuario. Con respecto al modelo de patrullaje para el drone, aún quedan varias cuestiones abiertas. La dificultad matemática del problema de optimización que debe resolverse para calcular el equilibrio de Stackelberg abre la puerta a la aplicación de técnicas de optimización aproximada, como algoritmos bioinspirados u otras metaheurísticas, que aún no han sido aplicadas a juegos de seguridad. La magnitud de los espacios de acciones de ambos jugadores requieren que se considere solamente un subconjunto de estrategias porque el problema completo no puede resolverse debido a las limitaciones físicas sobre la memoria RAM disponible. Este problema se da con frecuencia en los juegos de seguridad cuando se intentan escalar para escenarios reales. Aún deben realizarse experimentos para comprobar qué metaheurísticas en concreto resuelven mejor este tipo de problemas y cómo adaptarlas al dominio de los juegos de seguridad. Dado el creciente número de problemas que están siendo abordados como juegos de seguridad en la actualidad, si el uso de metaheurísticas se demuestra efectivo para el problema del dron, puede llevar a su adopción en otros modelos que presentan problemas similares de escalabilidad. Por último, no se ha modelado la incertidumbre sobre las limitaciones físicas de los agentes, como la velocidad real del dron y la velocidad que asumimos para los posibles intrusos, o la duración exacta de la batería. Ninguno de estos parámetros puede ser conocido con exactitud, por lo que parece natural modelarlos como números difusos, y recurrir a enfoques existentes de programación lineal difusa para calcular el equilibrio de Stackelberg. Esto no se ha hecho hasta ahora en juegos de seguridad. PUBLICACIONES P. Villacorta y D. Pelta (2010). Evolutionary design and statistical assessment of strategies in an adversarial domain. Proc. of the IEEE Conf. on Evolutionary Computation, pp. 2250 - 2256. P.J. Villacorta y D.A. Pelta (2012). Theoretical Analysis of Expected Payoff in an Adversarial Domain. Information Sciences 186(1):93-104. P. Villacorta y D. Pelta (2011). Expected payoff analysis of dynamic mixed strategies in an adversarial domain. Proc. of the IEEE Symposium on Intelligent Agents. IEEE Symposium Series on Computational Intelligence, 116 - 122. P.J. Villacorta, D.A. Pelta y M.T. Lamata (2013). Forgetting as a way to avoid deception in a repeated imitation game. Autonomous Agents and Multi-Agent Systems 27(3): 329-354. P.J. Villacorta, L. Quesada y D. Pelta (2012). Automatic Design of Deterministic Sequences of Decisions for a Repeated Imitation Game with Action-State Dependency. Proc. of the IEEE Conf. on Computational Intelligence y Games, 1 - 8. P.J. Villacorta y D.A. Pelta (2015). A repeated imitation model with dependence between stages: decision strategies y rewards. Int. Journal of Applied Mathematics and Computer Science 25 (3): 617 - 630. P.J. Villacorta y J.L. Verdegay (2015). FuzzyStatProb: an R Package for the Estimation of Fuzzy Stationary Probabilities from a Sequence of Observations of an Unknown Markov Chain. Journal of Statistical Software. En prensa.