**Ejercicios del Curso [SVRAI](./svrai.md.html)** Version 1.0 En esta página se irán colgando las propuestas de ejercicios de los diversos capítulos que conforman el curso. Ha de tenerse en cuenta que para cada capítulo también se admitirán como entregas ejercicios relacionados propuestos por el propio alumno. Tema 2: **Agentes Basados en Utilidades** ================================================================= 1. Implementar de forma genérica los algoritmos **Value-Iteration** y **Q-Learning** para trabajar sobre MDPs definidos a partir de redes aleatorias. Genera experimentos que te permitan determinar cuánto tarda en converger a medida que aumenta el número de estados (ten cuidado de asegurarte de que el grafo de estados sea conexo), incluyendo un pequeño análisis de la importancia de los posibles parámetros de cada algoritmo. 2. Disponemos de un mundo en el que hay unos agentes que han de encontrar el camino más rápido para llegar a unas bases de seguridad (marcadas en verde) evitando las zonas peligrosas del mapa (marcadas en rojo). Aplicar un algoritmo **Value-Iteration**/**Q-Learning** para diseñar la política óptima que lleva a cada agente a su zona de seguridad más próxima evitando el peligro (si no añadimos mecanismos de rutas adicionales, ten cuidado de hacer que las dimensiones del mundo no sean muy grandes). 3. Marvin es un robot que habita en una cuadrícula de $3\times 3$ y sólo puede moverse hacia el Norte, Sur, Este y Oeste. Las ruedas de Marvin giran a veces, de modo que en cada acción hay una probabilidad de $0,2$ de que Marvin permanezca inmóvil. Marvin recibe una recompensa de 1 cada vez que visita la casilla central: 1. Dibuja un MDP que describa el problema de Marvin. 2. ¿Cuál es la política óptima? 4. Tenemos una mesa con tres bloques encima marcados con las letras A, B y C. Supongamos que el estado del mundo está completamente definido por la posición de los bloques entre sí, donde un bloque sólo puede estar en la mesa o encima de otro bloque. Como máximo, solo se pueden montar pilas de tamaño 2. Además, se dan los siguientes operadores: * *mover-a-la-mesa*$(b)$: Requiere que $b$ no tenga ningún otro bloque encima. El resultado es que el bloque $b$ está ahora en la mesa. * *mover-sobre-bloque*$(b_1, b_2)$: Requiere que $b_1$ y $b_2$ no tengan ningún otro bloque encima. El resultado es que el bloque $b_1$ queda encima del bloque $b_2$. Dibuja un MDP para este dominio asumiendo que los operadores no tienen incertidumbre ni ruido. 5. Implementar un programa de NetLogo donde los patches se establecen al azar a un color entre: $negro$, $rojo$ y $verde$. Hay un agente en este mundo que sólo puede moverse hacia el Norte, Sur, Este y Oeste por un patch a la vez. Cada vez que cae en un patch recibe una recompensa determinada por el color del parche: $negro=0$, $rojo=-1$, y $verde=1$.
El movimiento del agente es ruidoso, por lo que cuando decide moverse hacia el Norte termina en el patch Norte deseado con una probabilidad de $0.5$, en el patch Noreste de su ubicación actual (un patch diagonalmente adyacente) con una probabilidad de $0.25$, y en el patch Noroeste de su ubicación actual con una probabilidad de $0.25$.
Aplica el algoritmo **Value-Iteration**/**Q-Learning** para este dominio y encuentra la política óptima. 6. Aplicar **Q-learning** a problemas variados. Debe tenerse en cuenta que deben ser problemas que se puedan definir con un conjunto discreto de estados (preferiblemente, finitos y no muy grandes). 7. Idear algún método para, en problemas concretos, **aproximar la tabla Q por medio de una función** de forma que permita interpolar los valores de la tabla y extenderla de forma automática a estados no visitados. Tema 3: **CSP Distribuido (DisCSP)** ================================================================= Puedes encontrar una buena colección de problemas CSP en el [siguiente enlace](https://www.csplib.org). 1. Adapta y completa de forma adecuada **ABT** para poder resolver otros CSPs. 2. Adapta de forma adecuada, y aplica, **AWCS** para poder resolver otros CSPs. 3. Implementa **Distributed Breakout** y aplícalo a diversos CSPs. 4. Aunque este ejercicio depende mucho de NetLogo, ¿serías capaz de crear una librería general de resolución de CSPs de forma que fuese relativamente fácil de usar para un usuario? 5. Analiza cómo puede afectar la relación de prioridad entre agentes para los algoritmos que usan relaciones de prioridad estáticas. Por ejemplo, usa ABT para un resolver una instancia concreta y lanza la resolución del CSP para distintas prioridades. 5. Para un problema concreto de CSP, compara cómo se comportan los diversos algoritmos respecto a la cantidad de mensajes que procesa cada agente/variable. Puede ser interesante ver cómo se comportan diferenciando los distintos tipos de mensajes que procesa, no solo la cantidad global. Haz el mismo estudio sobre el mismo problema, pero cambiando el orden de prioridad asignado a las variables. 6. Todos los algoritmos vistos asumen que la red de restricciones es estática, pero muchos problemas de la vida real son dinámicos y las restricciones pueden modificarse cuando el sistema evoluciona (normalmente, de un paso al siguiente no cambia radicalmente, sino solo un poco). Implementa alguno de los algoritmos anteriores para el problema de coloreado y ejecuta algunos tests para ver cómo se comporta cuando el grafo cambia. Por ejemplo: comenzando con un grafo generado al azar y una coloración inicial, se ejecuta el algoritmo y posteriormente se cambia el grafo añadiendo o eliminando un nodo al azar y se vuelve a ejecutar el algoritmo. ¿Tarda el algoritmo lo mismo en el primer paso que en todos los demás? ¿Qué tipos de cambios en el grafo suponen la mayor diferencia en tiempo de ejecución? Tema 4: **COP Distribuido (DisCOP)** ================================================================= 1. Implementa el algoritmo de construcción distribuida de árboles DFS. 2. Implementa y aplica los diversos algoritmos de DiscOP vistos en el tema. 3. Implementa el algoritmo ADOPT. 4. Genera ejemplos de aplicación con los que se puedan probar los algoritmos anteriores. Tema 5: **Juegos no Cooperativos** ================================================================= 1. **Construcción de un puente**: El ayuntamiento de una ciudad está llevando a cabo una campaña de recaudación de fondos para construir un puente por medio de donaciones anónimas. La ciudad tiene $10.000$ habitantes, y cada uno de ellos tiene que decidir si contribuye o no. Cada persona que decide contribuir dona $10$ dólares. La construcción del puente cuesta $50.000$ dólares. Por lo que basta que la mitad de los habitantes contribuyan para que el puente se construya. Si hay un excedente, se lo queda el ayuntamiento, pero si no se llega al mínimo, el puente no se construye y el dinero donado lo conserva el ayuntamiento para un posible uso futuro. Cada persona asigna una utilidad de $20$ a la construcción del puente. Demostrar que este juego tiene un único equilibrio de Nash. 2. Demostrar que el juego de **emparejar monedas** no tiene ningún equilibrio de Nash, pero que $s=(1/2,1/2)$ es el único equilibro de Nash mixto que tiene (Ayuda: usa las **Propiedades Equilibrios de Nash Mixtos**). 3. Calcula los equilibrios de Nash mixtos del Juego de la Batalla de los Sexos (Ayuda: usa las **Propiedades Equilibrios de Nash Mixtos**). 4. Dos jugadores deciden jugar al siguiente juego. Empiezan a conducir el uno hacia el otro y la colisión es inevitable a menos que uno (o ambos) de los conductores decida cambiar su curso de conducción (se acobarde). Para cada jugador, el mejor resultado es que siga conduciendo en línea recta mientras el otro jugador se acobarda. El siguiente mejor resultado es que ambos se acobarden. La tercera mejor opción es que el propio jugador se acobarde mientras el otro conduce recto, y finalmente el peor resultado es que ambos sigan conduciendo recto hasta que se produzca la colisión. Escribe un Juego en Forma Normal que represente esta situación y encuentra sus equilibrios puros de Nash. 5. Considera el juego para dos jugadores definido por la siguiente matriz de pagos y decide si las siguientes afirmaciones son verdaderas o falsas: * A domina estrictamente a B. * Z domina estrictamente a W. * C domina débilmente a D. * X domina débilmente a W. * C es la mejor respuesta a X. * Z es la mejor respuesta a A. ||$W$|$X$|$Y$|$Z$| |:---:|:---:|:---:|:---:|:---:| |$A$|$(15,42)$|$(13,23)$|$(9,43)$|$(0,23)$| |$B$|$(2,19)$|$(2,14)$|$(2,23)$|$(1,0)$| |$C$|$(20,2)$|$(20,21)$|$(19,4)$|$(3,1)$| |$D$|$(70,45)$|$(3,11)$|$(0,45)$|$(1,2)$| 6. Demuestra que ($1/3L+ 2/3M, 1/2T + 1/2B)$ es un equilibrio de Nash mixto del siguiente juego. ¿Tiene este juego algún equilibrio de Nash puro? ||$L$|$M|$R$| |:---:|:---:|:---:|:---:| |$T$|$(6,22)$|$(3,26)$|$(47,22)$| |$C$|$(4,4)$|$(4,2)$|$(99,42)$| |$B$|$(3,22)$|$(4.5,18)$|$(19,19)$| 7. Dos estudiantes tienen que realizar una tarea conjunta para un curso. La nota final depende de la cantidad de esfuerzo realizado por los estudiantes. Cada uno de los estudiantes quiere completar la tarea, pero al mismo tiempo no quiere trabajar mucho más que el otro. Esto se capta mediante la siguiente función de utilidad: $a_1,\ a_2\in \mathbb{R}$ denotan la cantidad de esfuerzo ejercido por cada uno de los estudiantes: $u_i(a_i,a_j) = a_i(c+a_j-a_i)$, $ con $i = 1,2$ y $j = 3-i$, donde $c$ es una constante dada. Esta función captura el hecho de que si $a_i$ supera a $a_j$ en al menos $c$, entonces la utilidad del jugador $i$ se vuelve negativa. Encuentra los equilibrios puros de Nash de este juego.