Algoritmos eficientes para juegos de stackelberg con defensores descentralizados

Abstract

Uno de los desafíos importantes que enfrenta un grupo de defensores corresponde a su coordinación con el objetivo de poder brindar una mayor protección al sistema que defienden. En este trabajo, se estudia el desarrollo de algoritmos eficientes y garantías de optimalidad para un modelo de juego de seguridad de Stackelberg que resuelve la coordinación de múltiples recursos defensivos descentralizados. Este modelo asume la presencia de incertidumbre en las acciones efectuadas por cada recurso defensor y la ausencia de comunicación entre ellos. En específico, el modelo de juego de seguridad de este trabajo consiste en resolver un número pequeño de problemas de programación lineal, que se pueden resolver mediante un esquema de generación de columnas. El subproblema de dicha generación de columnas corresponde a la resolución de un problema de decisión markoviana descentralizado. Estos problemas de decisión markoviana descentralizados son de difícil solución; sin embargo, es posible resolver estos subproblemas mediante heurísticas, dando como resultado un enfoque capaz de obtener soluciones subóptimas para el modelo de juego de seguridad. Se presentan diversas heurísticas para la resolución de dicho subproblema, y se realiza un estudio para evaluar su uso dentro del esquema de generación de columnas. Este estudio consiste en la simulación de instancias de prueba aleatorias para evaluar el desempeño, tanto en el valor del resultado obtenido como en el tiempo de resolución de cada heurística. Se presenta una cota para el valor óptimo de un problema de decisión markoviana descentralizado que se obtiene al resolver un problema de optimización entero relacionado. Nuestros estudios computacionales muestran que esta cota es menor a un 10% del valor óptimo. Se presentan además, variantes del enfoque de generación de columnas, buscando reducir los tiempos de solución sin sacrificar calidad de la respuesta. Estos enfoques también están basados en generación de columnas y otorgan una solución subóptima al problema planteado. Con el objetivo de evaluar el comportamiento de los enfoques presentados, se recurre a la simulación de instancias aleatorias y una instancia inspirada en parte de la red de metro de Santiago. Además, con el objetivo de poder evaluar las soluciones subóptimas otorgadas por dichos enfoques, se desarrolla un método que permite obtener garantías para la solución del problema de generación de columnas. En específico, el algoritmo desarrollado permite resolver el problema de patrullar descentralizadamente una red conformada por 16 estaciones de metro, durante 12 períodos de tiempo y utilizando 6 recursos. Esta solución se obtiene, en promedio, en un tiempo de 400 [s] y con una garantía del 20%.