Solución Examen Presencial Móstoles Mayo Sistemas Inteligentes 28 Mayo 2021 PDF

Preview

Summary

28 de mayo de 20 21APELLIDOS: NOMBRE:Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examenEjercicio 1: [20 puntos]El grafo que se muestra a continuación ...

Description

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen Ejercicio 1:

[20 puntos]

El grafo que se muestra a continuación describe un problema de búsqueda. Suponga que A es el estado inicial, y que el único estado meta es E. Los arcos están etiquetados con el coste real de cada operador (e.d., con el coste c(X,Y) de ir de un nodo X a su sucesor directo Y).

Asimismo, considere la siguiente función heurística h* Nodo h*

A 9

B 6

C 3

D 2

E 0

a) Desarrolle el árbol de búsqueda que genera el algoritmo A* con esta función heurística, asumiendo que no se filtran nodos repetidos. Indique el orden en el que se expanden los nodos, así como los valores de g, h*, y f * de cada nodo del árbol. En caso de que el algoritmo A* pueda elegir arbitrariamente entre algunos nodos hoja, asuma el mejor caso (e.d., se pide el árbol de búsqueda de menor tamaño posible desarrollado por el algoritmo A*) b) Demuestre si la función heurística h* es optimista, o si no lo es. c) Demuestre si la función heurística h* es consistente, o si no lo es.

Pág. 1 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen

Solucion a)

b) h* es • h* (A)= 9 • h* (B)= 6 • h* (C)= 3 • h* (D)= 2 • h* (E)= 0

optimista ≤ ≤ ≤ ≤ ≤

10 = h(A) 6 = h(B) 5 = h(C) 3 = h(D) 0 = h(E)

c) h* NO es consistente • Contraejemplo: h*(B) – h*(C) = 6 – 3 = 3 > c(B,C) = 1

Pág. 2 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen Ejercicio 2: [ 20 puntos] Contemple el siguiente árbol de un juego bipersonal de suma nula, en cuyas hojas se indica el valor correspondiente de la función de evaluación. Es el turno del jugador Max. Realice este ejercicio en este mismo enunciado.

a) Suponga que respecto a los valores de evaluación de los nodos H, I y J, sólo se sabe que 6 < z < y < x < +∞. Asumiendo que siempre se expanden los sucesores de un nodo de izquierda a derecha, aplique el algoritmo Minimax con poda a -b e indique en la tabla de abajo cómo van cambiando los valores de a y b de los demás nodos interiores durante la ejecución del algoritmo (si fuera necesario, ponga x, y o z en vez de números concretos). Indique qué nodo(s) se poda(n) así como la mejor jugada para Max.

a

b

A B C D G H Nodo(s) podado(s): Mejor jugada:

Pág. 3 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen b) Suponga ahora que no se dan las restricciones sobre los valores de x, y o z del apartado anterior. ¿Cuál es la restricción más débil sobre las variables x, y y/o z (e.d. la que menos restringe sus posibles valores) para que se pode un nodo más? ¿Cuál sería este nodo? ¿Cuál sería la mejor jugada en este caso? Condición más débil: Nuevo nodo podado Mejor jugada: Solución: a)

a

b

A

-∞ / 5 / z

+∞

B

-∞

+∞ / 7 / 5

C

5

+∞ / 5

D

5

+∞ / y / z

G

5

+∞

H

PODADO

PODADO

Nodo(s) podado(s):

H

Mejor jugada:

D

Condición más débil:

y≤5

Nuevo nodo podado

J

Mejor jugada:

B

b)

Pág. 4 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen Ejercicio 3: [15 puntos] Dados los siguientes nombres de conceptos: Reptil, Pez, Animal, Cocodrilo, Agua y Tierra, y el nombre de rol viveEn, representar el siguiente conocimiento en lógica de descripciones ALC (10 puntos) y en lógica de primer orden (5 puntos). 1) Los reptiles y los peces son animales 2) Los reptiles no son peces 3) Los cocodrilos son reptiles que viven en agua y en tierra (en los dos sitios) 4) Los peces son animales que sólo viven en agua 5) Calamardo es un animal que vive en agua Solución: 1) Los reptiles y los peces son animales Reptil v Animal Pez v Animal (otra equivalente: Reptil t Pez v Animal) "x(Reptil(x) ® Animal(x)) "x(Pez(x) ® Animal(x)) (otra equivalente: "x(Reptil(x) Ú Pez(x) ® Animal(x)) 2) Los reptiles no son peces Reptil v ¬Pez (otra: Reptil u Pez ´ ^ ) "x(Reptil(x) ® ¬Pez(x)) 3) Los cocodrilos son reptiles que viven en agua y en tierra (en los dos sitios) Cocodrilo v Reptil u $viveEn.Agua u $viveEn.Tierra "x(Cocodrilo(x) ® Reptil(x) Ù $y(viveEn(x,y) Ù Agua(y)) Ù $z(viveEn(x,z) Ù Tierra(z)) )

4) Los peces son animales que sólo viven en agua Pez v Animal u "viveEn.Agua "x(Pez(x) ® Animal(x)!Ù "y(viveEn(x,y) ® Agua(y)))

5) Calamardo es un animal que vive en agua {Animal(Calamardo), $viveEn.Agua(Calamardo)} Animal(Calamardo) Ù $y(viveEn(Calamardo,y) Ù Agua(y))

Pág. 5 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen Ejercicio 4:

[15 puntos]

La siguiente figura muestra el conjunto borroso que representa el valor pocos de la variable número de partidos oficiales jugados por un futbolista en una temporada. Pocos 1

0 0

10

20

30

40

50

60

Una temporada el jugador Koke juega 44 partidos y Marcelo 18 partidos. Obtener el grado de verdad de las siguientes expresiones: a) Koke jugó muchos partidos, pero Marcelo jugó pocos b) Koke no jugó muchos partidos o Marcelo jugó muy pocos En caso de que sea necesario utilizar las siguientes funciones: • T-norma = x*y • T-conorma = x + y – x*y • Implicación = J(x,y) = 1 – x + x*y Solución: a) Koke jugó muchos partidos, pero Marcelo jugó pocos µMuchos(44) = µPocos(60 – 44) = µPocos(16) = 0.4 µPocos(18) = 0.2 µMuchos Ù Pocos(44,18) = T(µMuchos(44), µPocos(18)) = T(0.4,0.2) = 0.4*0.2 = 0.08 b) Koke no jugó muchos partidos o Marcelo jugó muy pocos µ¬Muchos(44) = 1 – µMuchos(44) = 1 – 0.4 = 0.6 µMuy Pocos(18) = µPocos(18)2 = 0.22 = 0.04 µ¬Muchos Ú Muy Pocos(44, 18) = S(µ¬Muchos(44), µMuy Pocos(18)) = S(0.6, 0.04) = = 0.6 + 0.04 – 0.6*0.04 = 0.616

Pág. 6 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen Ejercicio 5: [15 puntos] Considere el siguiente juego. Un agente se encuentra en un laberinto de habitaciones en el cual debe encontrar un tesoro y, una vez encontrado este tesoro, debe abandonar el laberinto, todo ello lo más rápido posible. Un posible esquema de este juego se presenta en la figura. En este caso, T representa el tesoro, A el agente y la flecha 0 indica la salida del laberinto. Tanto el tesoro como la salida siempre están en las mismas habitaciones. Los números sirven 3 para identificar cada habitación. En cada habitación, el agente 6 puede moverse a una habitación adyacente (no puede cruzar las paredes marcadas con líneas gordas, ni puede ir en diagonal). Si se encuentra en la habitación del tesoro puede recoger el tesoro. El tesoro no se puede “soltar” ni se puede coger si el agente ya lo tiene.

1

2

T 4

5

7

8

A

El agente no conoce los detalles del entorno, aunque si sabe que hay un tesoro y una salida y sabe que en cada habitación podrá moverse a las habitaciones adyacentes (si no hay muro). El agente quiere utilizar el algoritmo Q-learning para aprender las mejores acciones en este juego. Describe cómo se puede modelar este juego como problema de decisión de Markov. NOTA: No es necesario definir el modelo completo, sino simplemente describir cómo serían los estados, las acciones, el modelo de transición y el modelo de recompensas. Solución: Estados: Cada estado está determinado por el número de habitación y si o no el agente tiene el tesoro: (x,y), con x∈ {1,..,9} e y∈ {sí,no}. Acciones y modelo de transición: Hay 4 acciones de movimiento izquierda, derecha, arriba y abajo que el agente puede realizar desde cualquier estado (x,y), si en la habitación x existe el movimiento correspondiente. Al aplicar una de estas acciones en el estado (x,y), se llega a un estado (z,y) donde z es la habitación adyacente. Hay una acción de “recoger tesoro”. Sea x la habitación en la que se encuentra el tesoro, entonces en el estado (x,no) el agente puede realizar esta acción y transitaría al estado (x,si). Modelo de recompensas: La acción recoger el tesoro en la habitación 2 debe tener una recompensa positiva, por ejemplo, de 10. R((2,no), coger tesoro)=10.

Pág. 7 / 8

Examen Inteligencia Artificial (Móstoles) 28 de mayo de 2021

APELLIDOS:

NOMBRE:

Duración: 1 hora 40 mins No se permiten móviles, libros, apuntes, ni calculadora Entregue los ejercicios en hojas separadas, incluidos en blanco No se levante del asiento salvo para entregar el examen La acción que lleva a salir del laberinto si el agente tiene el tesoro debe tener una recompensa positiva, por ejemplo de 10. R((1,sí), izquierda)=10 Todas las demás acciones tienen recompensa negativa, por ejemplo, de -1.

Ejercicio 6:

[15 puntos]

El siguiente grafo presenta un entorno de un proceso de decisión de Markov con los estados S0 a S4 y en las que un agente puede realizar las acciones t, a y c (como se indica en el modelo de transición). La acción t es una acción que puede tener dos posibles resultados, cada uno con probabilidad 0,5, tal como se indica en el grafo. 0,5

0,5 a/2 S0

S1

t/-1

0,5

S2

t/-1

0,5

c/6 S3

S4

a/1 a/0 a) Aplica el algoritmo de iteración de valores para obtener los valores de la función Q* en este problema. Asume que el factor de descuento Gama es igual a 1. b) Dado los resultados del apartado A, especifica la política óptima. Solución: Q*(S1,a) 0 2 2 2 2

Q*(S1,t) 0 0 0,5 1,5 1,5

Q*(S2,a) 0 1 1 1 1

Q*(S2,t) 0 0 3 3 3

Q*(S3,a) 0 0 0 0 0

Q*(S3,c) 0 6 6 6 6

Respecto a la política óptima, serían: π∗(S1)=a;!π∗(s2)=t;!π∗(s3)=c

Pág. 8 / 8...