Transcript
Universidad Universidad del Cono Sur de las Américas
Alumno
: Claudio Frutos
Profesor
: Carlos Almeida
INTELIGENCIA ARTIFICIAL 1 DEFINE BREVEMENTE LOS SIGUIENTES ÍTEMS: Inteligencia Artificial: es una rama de la computación que se dedica a desarrollo de agentes racionales A) no vivos. desarrollar sistemas que piensen y actúen racionalmente. Agente: un agente es una entidad que percibe su ambiente a través de sensores y actúa sobre su B) entorno a través de actuadores. Prueba de turing: se diseño para proporcionar una definición operacional y satisfactoria de inteligencia. C) Una prueba basada en la incapacidad de diferenciar entre entidades inteligentes indiscutibles y seres humanos. El computador supera la prueba si un evaluador humano no es capaz de distinguir si las respuestas, a una serie de preguntas planteadas, son de una persona. D)
Racionalidad: un agente siempre realiza lo correcto a partir de los datos que percibe del entorno.
Autonomía: un agente es complementamente autónomo si es capaz de actuar basándose en su E) experiencia, cuando el agente percibe su entorno. Agente reactivo: un agente actúa como resultado de cambios de su entorno, un agente percibe su F) entorno y esos cambios dirigen su comportamiento. Agente basado en utilidad: utiliza un modelo del mundo real junto con una función de utilidad que G) calcula sus preferencias entre los estados del mundo. Después selecciona la acción que la lleve a alcanzar mayor utilidad esperada. Espacio de estados: implícitamente el espacio inicial y la función sucesor definen el espacio de estados H) del problema (conjunto de todos los estados alcanzables desde el estado inicial). El espacio de estado forma un grafo el cual los nodos son estados y los arcos entre nodos son acciones. Árbol de búsqueda: el objetivo es atravesar el árbol partiendo de un estado inicial hasta un estado I) objetivo ,explicito generado por el estado inicial y la función sucesor, definiendo así el espacio de estado, en general se tiene un grafo de búsqueda mas que un árbol, cuando el mismo estado puede alcanzarse desde varios caminos. Objetivo: encontrar un camino que conecte al nodo inicial a un nodo objetivo. es el estado que se J) quiere alcanzar partiendo desde un nodo inicial. Acción: una descripción de las posibles acciones disponible por el agente. Utilizando una función K) sucesor. L)
Función sucesor: cada sucesor es un estado que puede alcanzarse aplicando la acción.
Factor de ramificación: Cantidad de ramas que tiene un nodo en particular, también es el número de M) sucesores que posee un nodo.
Identifique la descripción REAS que define el entorno de trabajo para cada uno de los siguientes agentes: AGENTE
RENDIMIENTO
ENTORNO
ACTUADORES
SENSORES
Robot que juega fútbol
Autonomía, resistencia, goles, velocidad, aceleración, posesión del balón
Campo de fútbol, pelota, arcos
Correr, patear, mover brazos y piernas
Cámaras, acelerómetro, metros, sensores de impacto, GPS
Agente comprar libros por Internet
Comparar precios, cantidad de libros, velocidad de transacción, tiempo de entrega, velocidad de búsqueda, cantidad de libros comprados correctamente
Web, computadores, servidores, estudiantes, profesores, librería o carrito virtual
Buscar, clasificar, recorrer páginas, cargar carrito, pago, verificar datos de compra, imprimir factura, entrega al destinatario.
Teclado, Mouse, Pantalla Táctil, Datos del libro.
Explorador autónomo de Marte
Autonomía, Velocidad, Temperatura, Resistencia, Cantidad de muestras recolectadas, distancia, tiempo
Superficie, rocas, gravedad, atmósfera, clima
Moverse, frenar, escalar, excavar, analizar piedras, enviar informaciones, comunicarse por radio
Cámaras, GPS, Sensor de clima, Temp., Humedad, Sensor de Impacto, Velocímetro, Energía, Espectrómetro, Equipo de radio
Computadora, Datos numéricos, Ecuaciones, Formulas Matemáticas, Teoremas
Calcular, Consultar BD, Utilizar Datos, Utilizar métodos de búsqueda, Mostrar resultado.
Teclado, Mouse, Pantalla Táctil, Datos Ingresados, Formulas, Cuestiones y Teoremas Ingresadas.
Asistente Velocidad de Matemático procesamiento, Exactitud de resultados, Cantidad de teoremas demostrados, Cantidad de problemas resueltos simultáneamente.
Considere un espacio de estados donde el estado comienzo es el numero 1 y la función sucesor para el estado n devuelve 2 estados, los números 2 n y 2n +1. a) Dibuje el trozo del espacio de estados para los estados del 1 al 15..
b) Supongamos que el estado objetivo es el 11. Enumere el orden en el que serán visitados los nodos por la búsqueda primero en anchura, búsqueda primero en profundidad con límite tres, y la búsqueda de profundidad iterativa. Primero en anchura: 1,2,3,4,5,6,7,8,9,10,11. Primero en profundidad: 1,2,4,8,9,5,10,11. Profundidad Iterativa: nivel 0: 1 nivel 1: 1,2,3 nivel 2: 1,2,4,3,6,7 nivel 3: 1,2,4,8,9,10,11
c) ¿Será apropiada la búsqueda bidireccional para este problema? Si es así, describa con detalle cómo trabajaría. Si, por que se encuentran en un estado intermedio, en este caso el 2.
d) ¿Qué es el factor de ramificación en cada dirección de la búsqueda bidireccional? El factor ramificación es 2 del nodo inicio y 1 partiendo del nodo objetivo Nodo inicio: 2 Nodo objetivo: 1
e) ¿La respuesta (c) sugiere una nueva formulación del problema que permitiría resolver el problema de salir del estado 1 para conseguir un estado objetivo dado, con casi ninguna búsqueda? Sí sugiere una nueva formulizacion del problema por el camino recorrido desde el nodo inicio al nodo objetivo por concluir un camino mas corto.
Trace cómo opera la búsqueda A* aplicada al problema de alcanzar Bucarest desde Lugoj utilizando la heurística distancia en línea recta. Es decir, muestre la secuencia de nodos que considerará el algoritmo y los valores f, g, y h para cada nodo. f(n) = g(n) + h(n) HEURISTICA ARAD BUCAREST CRAIOVA DOBRETA GIURGIO LUGOJ MEHADIA PITESTI RIMNICU SIBIU TIMISOARA URCIZENCI
lugoj 70
111
mehadia f(n)=70+241= 311 75
timisoara f(n)=111+329=440 70
dobreta f(n)=145+242=387
118 arad f(n)=229+366=595
lugoj f(n)=140+244=384
75 120 craiova mehadia f(n)=220+241=461 f(n)=265+160=245
111 70 timisoara f(n)=251+329=580
140 120 138 rimnicu dobreta f(n)=411+193=604 f(n)=385+242=627 138 cariova
75
pitesti f(n)=403+110=503 97
111 mehadia f(n)=210+241=451 70 dobreta f(n)=285+242=527
101 rimnicu
BUCAREST
111 lugoj f(n)=222+244=466
70 timisoara f(n)=333+329=662
lugoj f(n)=280+244=524
mehadia f(n)=292+241=533
h (n) 366 0 160 242 77 244 241 100 193 253 329 80
f(n)=541+160=701
f(n)=500+193=693
f(n)=504+0=504
Considere el espacio de búsqueda de siguiente, donde S es el nodo de inicio, y G1, G2 y G3 satisfacen la prueba del nodo objetivo. Los arcos están etiquetados con el costo de atravesar entre los nodos, y los valores de la función h se muestran al lado del gráfico. Para cada una de las siguientes estrategias de búsqueda, indique cual objetivo es alcanzado (cualquiera de ellos) y liste en orden, todos los estados considerados.
a) Primero en anchura S, A, B, C, D, E, G3
b) Primero en profundidad S, A, C, D, G1
c) Profundidad iterativa LIMITE 0 LIMITE 1 LIMITE 2
S S, A, B S, A, C, B, E, G3
d) Costo uniforme f(n) = g(n)
Costo f(n)
Nodo
Camino
0
S
S
1
A
S->A
2
C
S->A->C
3
B
S->A->B
7
E
S->A->B->E
10
D
S->A->B->E->D
13
G2
S->A->B->E->D->G2
Costo f(n)
Nodo
Camino
100
S
S
10
A
S->A
1
C
S->A->C
3
D
S->A->D
0
G1
S->A->D->G1
Costo f(n)
Nodo
Camino
100
S
S
11
A
S->A
3
C
S->A->C
19
D
S->A->D
19
G2
S->A->D->G2
Costo f(n)
Nodo
Camino
100
S
S
10
A
S->A
1
C
S->A->C
3
D
S->A->D
0
G1
S->A->D->G1
e) Primero el mejor (usando f = h)
f) Primero el mejor (usando f = g + h)
g) Búsqueda en haz (con anchura del haz = 2 y f = h)
h) Escalar montaña (usando solamente la función h)
Costo f(n)
Nodo
Camino
100
S
S
10
A
S->A
1
S->A->C
C
El problema de los misioneros y caníbales en general se forma como sigue. Tres misioneros y tres caníbales están en un lado de un río, con un barco que puede sostener a una o dos personas. Encuentre un modo de conseguir que todos estén en el otro lado, sin dejar alguna vez a un grupo de misioneros en un lugar excedido en número por los caníbales. Este problema es famoso en IA porque fue el tema del primer trabajo que aproximó una formulación de problema de un punto de vista analítico (Amarel, 1968). a) Formule el problema de forma precisa, haciendo sólo las distinciones necesarias para asegurar una solución válida. Dibujar un diagrama del espacio de estados completo. Orilla 0 mmm ccc nodo inicial (3c, 3m, 1)
Orilla 1 \___/
mmm ccc nodo objetivo (0c, 0m, 0)
Simbología: c=caníbal, m=misionero, 0=no hay bote, 1=bote Estado inicial: (3c,3m,1/0c,0m,0) /representa el otro lado del rio Estado final: (0c,0m,0/3c,3m,1)
b) Implemente y resuelva el problema de manera óptima utilizando un algoritmo apropiado de búsqueda. ¿Es una buena idea comprobar los estados repetidos? No es una buena idea comprobar los espacios repetidos por que se extenderá el problema. En la búsqueda preferente por profundidad siempre se expande uno de los nodos que se encuentre en los más profundo de árbol, por lo tanto los nodos sucesores estarán a profundidades cada vez mayores.
Simbología: c=caníbal, m=misionero, 0=no hay bote, 1=bote Estado inicial: (3c,3m,1/0c,0m,0) /representa el otro lado del rio Estado final: (0c,0m,0/3c,3m,1) BÚSQUEDA EN PROFUNDIDAD (3c,3m,1/0c,0m,0) 1 (1c,3m,0/2c,0m,1) 9 (2c,3m,1/1c,0m,0)
5 (2c,2m,0/1c,1m,1)
1 (0c,3m,0/3c,0m,1) 9
5 (2c,3m,0/1c,1m,1) 6 (2c,3m,1,1c,0m,0)
(1c,3m,1/2c,0m0) 2 (1c,1m,0/2c,2m,1) 8 (2c,2m,1/1c,1m,0)
7 (1c,3m,1/2c,0m,0)
2 (2c,0m,0/1c,3m,1)
3 (1c,1m,0/2c,2m,1)
6 (3c,0m,1/0c,3m,0) 1 (1c,0m,0/2c,3m,1)
4 (2c,0m,0/1c,3m,1)
9 (2c,0m,1/1c,3m,0)
10 (1c,1m,1/2c,2m,0)
1 (0c,0m,0/3c,3m,1)
3
(0c,0m,0/3c,3m,1)
c) ¿Por qué cree que la gente utiliza mucho tiempo para resolver este puzle, dado que el espacio de estados es tan simple?. Nos cuesta resolver el puzle a la primera porque no somos capaces de pensar diferente si no que pensamos de una forma más ambigua.
