inteligencia artificial

AGENTES INTELIGENTESEl enfoque que se adoptar en el curso correspondeal de Actuar Racionalmente.Este enfoque se basa en la idea del agente racional.

Este enfoque provee una visin ms general de la IA, debido a que incluye inferencia correcta manejo de incertidumbre consideraciones de limitacin de recursos habilidades cognitivas

Agentes y Bsqueda de Soluciones

El comportamiento racional consiste en hacer lo correcto.

Hacer lo correcto significa:

tomar las acciones que en la mayora de los casos se tenga xito

tomar las acciones que maximice el retorno esperado


El objetivo general de la IA es construir agentes inteligentes

Es decir construir agentes que tengan un comportamiento o una actuacin racional

Un agente es todo aquello que puede ser visto como percibiendo su ambiente a travs de sensores y actuando sobre ese ambiente mediante efectores.


ambientepercepcionesaccionessensoresefectores


Como se dijo antes un agente racional es aquel que hace lo correcto. Pero,

Qu significa hacer lo correcto?

Como un primer enfoque, afirmaremos que lo correcto es aquello que permite al agente obtener el mejor desempeo.

Cmo y cuando evaluar ese buen desempeo?

La medicin del desempeo se aplica al como


Ejemplo. Considere el caso de un agente al que se le encomienda limpiar con una aspiradora un piso sucio.

Medidas de desempeo posibles:

cantidad de mugre eliminada en un turno de ocho horas correlacionar la cantidad de electricidad consumida y la cantidad de ruido limpiar silenciosamente y eficientemente el piso


Ahora, el cuando se va evaluar el desempeo tambin es importante.Si se mide cuanta mugre elimin un agente durante la primera hora del da, aquellos agentes que empiezan a trabajar rpidamente (no obstante que posteriormente realicen poco o ningn trabajo) resultaran premiados, tanto que aquellos que laboran todo el turno de manera consistente resultaran castigados.

Lo importante es medir el desempeo en el largo plazo, sea ste un turno de ocho horas o una vida.


Trataremos ahora, de precisar lo de la racionalidad

Ejemplo: Supongamos que va caminando por una avenida y que ve al otro lado de la calle un antiguo amigo. No hay trnsito en las cercanas y tiene tiempo, as que racionalmente actuando, empieza a cruzar la calle. Al mismo tiempo pasa un avin al cual se le desprende una puerta, y antes de llegar donde su amigo queda completamente aplastado.


Al respecto podemos hacernos la siguiente pregunta: Se considera irracional el haber cruzado la calle?De lo anterior se puede deducir que la racionalidad tiene que ver con un xito esperado, tomando como base lo que se ha percibido.

No se puede culpar a un agente por no haber tomado en cuenta algo que no poda percibir, o por no emprender una accin ( esquivar la puerta) de la que es incapaz.


El carcter de racionalidad de lo que se hace un momento dado depende de cuatro factores: de la medida con que se evala el grado de xito

de todo lo que hasta ese momento haya percibido el agente. (a esta historia perceptual completa se le denomina secuencia de percepciones)

del conocimiento que posea el agente

de las acciones que el agente puede emprender


Lo anterior nos permite definir lo que es un agente racional ideal :

en todos los casos de posibles percepciones, un agente racional deber emprender todas aquellas acciones que favorezcan obtener el mximo de su medida de rendimiento, basndose en las evidencias aportadas por la secuencia de percepciones y en todo el conocimiento incorporado al agente.


El cometido de la IA, como se dijo antes, es el diseo de un programa de agente: una funcin que permita implantar un mapeo del agente para pasar de las percepciones a las acciones. Se da por sentado que el programa se ejecutar en algn dispositivo de computo al que se le denominar arquitectura. La relacin entre agentes, arquitectura y programas se puede resumir de la siguiente manera:Agente = arquitectura + programa


Agentes basados en metas

Por ejemplo, al llegar a un cruce, un taxi puede optar por dar la vuelta a la derecha, a la izquierda o seguir de frente. La decisin adecuada depender a donde desee llegar el taxi.


Agentes basados en utilidad

Las metas no son suficientes para generar una conducta de alta calidad. Considerando el ejemplo del taxi, seran muchas las acciones que permitiran llegar a su destino (diferentes rutas), pero de todas ellas algunas sern ms rpidas, seguras y confiables o ms baratas que las dems. Las metas permiten establecer una gran diferencia entre estados que proporcionen una mayor utilidad y estados que no proporcionen utilidad.


Problemas bien Definidos y Soluciones

Un problema es un conjunto de informacin que el agente utiliza para decidir lo que va a hacer. Empezaremos primero por especificar que informacin se necesita para definir un problema de un solo estado.


Estado Inicial: es el estado en cual el agente sabe que all se encuentra

Operadores: es el conjunto de acciones que el agente puede emprender. El trmino operador denota la descripcin de una accin en funcin de la cual se alcanzar un estado al emprender una accin en un estado particular. ( Otra forma de definirlo es mediante una funcin subsecuente S. Teniendo un estado particular x, S(x) responde con un conjunto de estados obtenibles a partir de x, mediante una sola accin.


Espacio de Estados: Los dos trminos anteriores definen el espacio de estados del problema: el conjunto de todos los estados que pueden alcanzarse a partir del estado inicial mediante cualquier secuencia de acciones.

Ruta: Una ruta del espacio de estados es simplemente cualquier secuencia de acciones que permiten pasar de un estado a otro.


Prueba de Meta: La prueba de meta es lo que el agente aplica a la descripcin de un solo estado para decidir si se trata de un estado meta. Hay ocasiones en las que existe un conjunto explcito de posibles estados meta, y la prueba solo sirve para cerciorarse si hemos alcanzado alguno de ellos. A veces la meta se especifica mediante una propiedad abstracta, en lugar de un conjunto de estados enumerados en forma explcita. Por ejemplo, en el ajedrez la meta es alcanzar un estado denominado jaque mate, en que el rey del contrincante se capturar en la siguiente jugada, haga lo que haga ste.


Por ltimo, hay casos en los que una solucin es preferible a otra, no obstante que con ambas pueda lograrse la meta. Por ejemplo son preferibles, las rutas que involucran menos acciones o acciones menos costosas.

Costo de Ruta: La funcin de costo de ruta es una funcin mediante la que se asigna un costo a una ruta determinada. En todos los casos que consideremos, este costo es la suma de los costos de cada una de las acciones individuales que se emprendan a lo largo de la ruta. Esta funcin se denotar por g.


Ejemplo 1Una serie de luces, dispuestas en una hilera, pueden estar encendidas o apagadas. En la siguiente figura, estado inicial, se representa una fila de cinco luces, las dos primeras (empezando por la izquierda) estn apagadas y las restantes encendidas.

A A E E E

Se desea conseguir que estn encendidas de manera alternada, con la primera, empezando de la izquierda encendida


Solucin Ej. 1Podemos conceptualizar el espacio de estados como elconjunto EE={(x1, x2, x3, x4, x5) / xi = A E }

Estado Inicial : (A, A, E, E, E)Estado Final : (E, A, E, A, E)Operadores : O1 Encender la primera ampolleta apagada cuya siguiente est encendida O2 Apagar todas las ampolletas que se encuentren encendidas entre dos encendidasCosto de Ruta: cero, problema basado en metaPrueba de Meta: Comparar si el estado actual corresponde al estado final


Ejemplo 2Dada una jarra de 5 litros llena de agua y una jarra de 2 litros vaca, cmo se puede obtener exactamente 1 litro de agua en la jarra de 2 litros?. El agua puede ser desechada o pasada de una jarra a la otra; sin embargo, no se cuenta con ms que los 5 litros de agua iniciales. Cuando se transfiere agua entre jarras, puede ocurrir que una jarra se llene o que la otra se vace.

Se pide plantear formalmente este problema y plantearlas condiciones que hacen posible aplicar los operadores que se definan


Solucin Ej2J1 : denotar el jarro de 5 litrosJ2 : denotar el jarro de 2 litros

EE = { (x, y) / 0 x 5} , 0 y 2}Estado Inicial : (5, 0)Estado Final : (- , 1) , - = cualquier valor

Operadores:

O1 : pasar agua del J1 al J2 Si x > 0 y < 2 (x - min(2 - y, x), y + min(2 -y, x) )


Continuacin sol. Ej2O2: pasar agua del J2 al J1 Si y > 0 x < 5 ( x + min(5 -x, y), y - min (5 -x, y))O3: vaciar el J1 Si x > 0 (0, y)O4 : vaciar el J2 Si y > 0 (x, 0)

Costo de Ruta: cero, problema basado en metaPrueba de Meta: Si y=1, se llega a la meta


Ejemplo 3

Problema del vendedor viajero: consiste en visitar, partiendo de un nodo, digamos A, todos los nodos de la red una sola vez, al menor costo,y volviendo al nodo desde el cual parti, ed A.

Los nodos de la red pueden representar ciudades y los arcos estn etiquetados con el costo de pasar de una ciudad a otra. Este costo puede ser la distancia entre los nodos, o efectivamente el costo (unidades monetarias) en que se incurre al pasar de un nodo a otro.

Se pide plantear formalmente este problema


Ejemplo 4Supongamos que tenemos un tablero rectangular divididoen cuadrados, cuyo tamao es 3 cuadrados de largo por 4cuadrados de ancho. Inicialmente, todos los cuadrados estn pintados de blanco.El objetivo es pintar todos los cuadrados de rojo. Para ello, disponemos de un robot que es capaz de pintar cuadrados individuales de rojo, con las siguientes restricciones: El robot se mueve por el tablero de cuadrado en cuadrado, con movimientos simples iguales a los del caballo de ajedrez. El robot nunca se puede situar sobre un cuadrado pintado de rojo Una vez que ha realizado el movimiento, el robot se coloca sobre el cuadrado correspondiente (que ha de estar pintado de blanco) y lo pinta de color rojo. Inicialmente, el robot se encuentra sobre el cuadrado de la esquina superior izquierda, que ya est pintado de rojo. Plantear formalmente, este problema


Solucin: Podemos definir el espacio de estados de este problema mediante una estructura con dos campos. Un campo para almacenar el estado del tablero, y otro para almacenar la posicin del robot. A su vez, el tablero el tablero se representar mediante una matriz de 3x4, en la que cada elemento se corresponde con un cuadrado y pueden tener el valor NIL (cuadrado pintado de blanco) o T (cuadrado pintado de rojo). La posicin del robot la representamos mediante un par ordenado (i, j), que corresponder a la posicin del robot en la matriz de 3x4


Estado inicial: ( a11 = T aij = NIL ij 11 , (1, 1) )

Estado final : ( aij = T i,j , (?, ? ) )

Operadores: Como los movimientos del robot deben ser como los del caballo de ajedrez , y estos movimientos vienen determinados por un movimiento vertical y otro horizontal, o viceversa. De estos movimientos uno ha de ser de dos cuadrados y el otro de uno. Adems, los movimientos verticales pueden ser hacia arriba o hacia abajo y los horizontales a izquierda o a derecha.


De esta manera los movimientos podemos representarlosmediante una estructura con dos campos, vertical y horizontal. El campo vertical almacena el nmero de casillas movidas en vertical, en negativo si es hacia abajo y en positivo si es hacia arriba. El campo horizontal almacena el nmero de casillas movidas en horizontal, negativo si es hacia la izquierda y positivo a la derecha.


Ejemplo 5

Misioneros y canbales: Tres misioneros y tres canbales estn en una de las mrgenes de un ro, junto a una lancha en la que caben una o dos personas. Hay que encontrar la manera de pasarlos a todos al otro lado del ro, pero teniendo cuidado que en ningn momento quede un grupo de misioneros junto con un grupo de canbales, siendo la cantidad e misioneros menor a la de los canbales.



Despus de definir y formular un problema comienza la etapa de bsqueda de soluciones, esto se logra mediante una bsqueda realizada a travs de un espacio de estados.En el caso de los misioneros y canbales es clara la prueba de meta, vale decir el estado al cual queremos llegar.En muchos problemas no se sabe hacia dnde ir. Slo se busca una solucin final no conocida que sea deseable a la luz de alguna funcin de desempeo (o criterio de efectividad).Existen dos tipos de bsqueda: Sin informacin (el agente no cuenta con informacin) y heurstica ( o el agente posee ms informacin)


En la industria los problema pueden ser difciles o fciles de entender, con frecuencia presentan una o ms de las siguientes caractersticas: combinatorios, no lineales, imprecisos, estocsticos, complejos, de gran escala, etc. En particular, algunos problemas que se pueden resolver mediante la idea de agentes son:

Transportedeterminacin de rutasconfiabilidad


Produccindiseo de productos y procesosplanificacin y mejoramiento de procesosprogramacin y control

FinancieroSeleccin de carteras de proyectosrentabilidad vs riesgo

Marketingidentificacin de necesidades del clienteatencin al cliente


Bsqueda de SolucionesLas estrategias de bsqueda son mtodos que a partir de un estado inicial (S0) y la aplicacin sucesiva de los operadores (acciones) encuentran un camino hasta un estado solucin (meta) (S*), cuando tal solucin existe. Para ello, proceden a generar un camino en el grafo de estados, conectando S0 con S*


Versin Informal del Algoritmo de Bsqueda GeneralFuncin BG( problema, estrategia) retorna sol o falla{Inicializar el rbol de bsqueda empleando el estado inicial del problemaCiclo {si no hay candidatos para la expansin, retorne falla

escoger un nodo hoja para hacer la expansin, de acuerdo con la estrategia

si el nodo contiene un estado meta, retorne la solucin, de lo contrario expanda el nodo, y agrege los nodos resultantes al rbol de bsqueda }}


Estructura de Datos para ArbolesPara manejar la bsqueda en rboles, daremos a los nodosuna estructura de datos con cinco componentes, stas son:

el estado en el espacio de estados al que corresponda el nodo el nodo del rbol de bsqueda que gener este nodo (nodo padre) el operador que se aplic para generar el nodo cuntos nodos de la ruta hay desde la raz hasta dicho nodo (la profundidad del nodo) el costo de ruta, de la ruta que va desde el estado inicial (raz) al nodo


Introduciremos una funcin, que llamaremos expandir,que se encargar de calcular cada una de las componentes de los nodos que ste genera.

Al grupo de nodos que estn en espera de ser expandidos se les conoce como margen o frontera.

Suponemos que el grupo de nodos se implanta como si se tratara de una lnea de espera. Las operaciones sobre esta lnea de espera son las siguientes


Operaciones sobre la lnea de Espera Crear una lista de espera. CLE(elementos) crea una lneade espera conforme a los elementos dados. Funcin est vaca. FEV(lnea de espera) retorna verdadero si no hay elementos en la lista Quitar frente. QF(lnea de espera) elimina el elemento que encabeza la lnea y lo devuelve Poner en lnea de espera. FPL(elementos, lnea de espera) pone un conjunto de elementos en la lista

Cada variedad de la lnea de espera producir distintas variedades de algoritmos de bsqueda


Con las operaciones anteriores el algoritmo de Bsqueda General (BG) se puede escribir como:

Funcin BG(problema, lnea de espera) retorna solucin o falla

nodos CLE(hacer_nodo(estado_inicialproblema))

ciclo si nodos esta vaco, retorne falla

nodo QF (nodos)

Si prueba_meta problema se aplica a Estado(nodo) y si tiene xito, retornar con nodo

nodos lista de espera(nodos, expandir(nodo,operadoresproblema))

fin


Las estrategias de bsqueda se evaluarn en funcin de los cuatro criterios siguientesCompletidad: La estrategia garantiza encontrar una solucin, si es que sta existe?

Complejidad temporal: Cunto tiempo se necesitar para encontrar una solucin?

Complejidad espacial: cunta memoria se necesita para efectuar la bsqueda?

Optimidad: con esta estrategia se encontrar una solucin de la mas alta calidad, en el caso que existan varias soluciones?


Los mtodos de bsqueda pueden clasificarse en dos grandes grupos Bsqueda sin contar con informacin Bsqueda respaldada de informacin o bsqueda heurstica

a) Bsqueda sin contar con informacin

No existe informacin acerca de la cantidad de pasos necesarios para pasar del estado en un momento dado a la meta: lo nico que permiten hacer es diferenciar entre un estado meta de otro que no lo es. A esta bsqueda tambin se le llama bsqueda ciega


Mtodos de Bsqueda No Informada

Bsqueda preferente por amplitud o anchuraBsqueda preferente por profundidadBsqueda de costo uniforme

Bsqueda preferente por amplitud (BPA)

En el algoritmo de bsqueda general la lnea de espera es una cola

BPA(problema) { BG(problema, cola) }


Bsqueda preferente en profundidad (BPP)

En esta bsqueda la lnea de espera es una pila.

BPP(problema) { BG(problema, pila) }Bsqueda de costo Uniforme(BCU)Mediante la bsqueda preferente en amplitud se encuentra el estado meta ms prximo a la superficie, sin embargo sta no es siempre la solucin de mnimo costo de la general de costo de ruta.


En el caso de la bsqueda de costo uniforme se modificala estrategia preferente por amplitud en el sentido de expandir primero el nodo de menor costo en el margen o frontera, medido por el costo de ruta g(n).

BCU(problema) { BG(problema, lnea de espera) } donde la lnea de espera est ordenada por el

min {g(n) / n F }

donde F es la frontera


Ejemplo 1Una serie de luces, dispuestas en una hilera, pueden estar encendidas o apagadas. En la siguiente figura, estado inicial, se representa una fila de cinco luces, las dos primeras (empezando por la izquierda) estn apagadas y las restantes encendidas.

A A E E E

Se desea conseguir que estn encendidas de manera alternada, con la primera, empezando de la izquierda encendida


Solucin Ej. 1Podemos conceptualizar el espacio de estados como elconjunto EE={(x1, x2, x3, x4, x5) / xi = A E }

Estado Inicial : (A, A, E, E, E)Estado Final : (E, A, E, A, E)Operadores : O1 Encender la primera ampolleta apagada cuya siguiente est encendida O2 Apagar todas las ampolletas que se encuentren encendidas entre dos encendidasCosto de Ruta: cero, problema basado en metaPrueba de Meta: Comparar si el estado actual corresponde al estado final


Problema de las luces (Bsqueda Preferente por Amplitud) (AAEEE)

(AEEEE) (AAEAE)

(EEEEE) (AEAAE) (AEEAE)

(EAAAE) (EEAAE) (EEEAE)

(EAAEE) (EEAEE) (EEEEE) (EAEAE)

Solucin: O2 - 01 - 01 - 02O1O2O1O2O1O2O1O1Cola(AAEEE)(AEEEE)(AAEAE) (EEEEE) (AEAAE) (AEEAE) (EAAAE) (EEAAE) (EEEAE) (EAAEE)(EEAEE)(EEEEE)(EAEAE)O1O10102


Ejemplo 2Dada una jarra de 5 litros llena de agua y una jarra de 2litros vaca, cmo se puede obtener exactamente 1 litro de agua en la jarra de 2 litros?. El agua puede ser desechada o pasada de una jarra a la otra; sin embargo, no se cuenta con ms que los 5 litros de agua iniciales. Cuando se transfiere agua entre jarras, puede ocurrir que una jarra se llene o que la otra se vace.

Se pide plantear formalmente este problema y plantearlas condiciones que hacen posible aplicar los operadores que se definan


Solucin Ej2J1 : denotar el jarro de 5 litrosJ2 : denotar el jarro de 2 litros

EE = { (x, y) / x {0,1, 2, 3, 4, 5} , y {0, 1, 2} }Estado Inicial : (5, 0)Estado Final : (- , 1) , - = cualquier valor

Operadores:

O1 : pasar agua del J1 al J2 Si x > 0 y < 2 (x - min(2 - y, x), y + min(2 -y, x) )


Continuacin sol. Ej2O2: pasar agua del J2 al J1 Si y > 0 x < 5 ( x + min(5 -x, y), y - min (5 -x, y))O3: vaciar el J1 Si x > 0 (0, y)O4 : vaciar el J2 Si y > 0 (x, 0)

Costo de Ruta: cero, problema basado en metaPrueba de Meta: Si y=1, se llega a la meta


Problema de las Jarras (Bsqueda Preferente por Profundidad) (5, 0)

(3, 2) (0, 0)

(0, 2) (3, 0)

(1, 2) (0, 0)

(0, 2 ) (1, 0)

(0, 1)

Solucin: O1 - 04 - O1 - O4 - O1

Pila(1, 0) (0, 2)(0, 0) NO(1, 2) (3, 0)(0, 2)(0, 0) NO(3, 2) (5, 0)

O1O3O3O4O1O3O3O4O1


Ejemplo Costo Uniforme: Considere en la siguiente red, el problema de ir de S a G, al menor costoSCBAG15155510


SBACg=1g=5g=15SBACg=1g=5g=15SBACg=1g=5g=15Gg=11GGg=11g=10


En este ejemplo se expande el estado inicial, lo que produce rutas con direccin a A, B y C. Como la ruta que lleva a A es la mas barata, se procede a expandirla y as generar la ruta SAG, que de hecho es una solucin, si bien no es la ptima. El algoritmo no acepta, por el momento a esta ruta como solucin, debido que en el margen o frontera, hay nodos que tienen un costo de ruta menor que 11, por lo tanto hay que expandir B (que tiene el menor costo de ruta en el margen), se genera de esta manera la ruta SBG con un costo de 10. En este caso, se llega a la solucin, pues no hay otro nodo en el margen que tenga un menor costo de ruta.


Ejemplo 3

Problema del vendedor viajero: consiste en visitar, partiendo de un nodo, digamos A, todos los nodos de la red una sola vez, y volviendo al nodo desde el cual parti, ed A, al menor costo.

Los nodos de la red pueden representar ciudades y los arcos estn etiquetados con el costo de pasar de una ciudad a otra. Este costo puede ser la distancia entre los nodos, o efectivamente el costo (unidades monetarias) en que se incurre al pasar de un nodo a otro.



Considere la siguiente red y resuelva el problema del vendedor viajero, que parte de A, mediante costo uniformeACDBE2562101520258


A

AB AC AD AE

ABC ABD ABE ACB ACD ACE ADB ADC ADE

ABCE ABCD ABDC ABDE ABEC ABED ACBD ACBE ACEB ACED ADBC ADBE

ABCED ABDEC ABECD ABEDC ACBDE ACEBD ACEDB

ABCEDA ABDECA ACEBDA ACEDBA

Solucin 1 A-B-D-E-C-A COSTO DE RUTA = 18Solucin 2 A-C-E-D-B-A COSTO DE RUTA = 18

211025877721315301810282715915 122081121201817293520131628182318


Una de complicaciones importantes del proceso de bsqueda es la posibilidad de perder tiempo al expandir estados que ya se encontraron y expandieron anteriormente, en alguna otra ruta. Hay tres formas de manejar los estados repetidos. Por orden ascendente de eficiencia y exceso de cmputo son:

No regrese al estado del que acaba de llegar. Instruya a la funcin expandir a que se niegue a generar un sucesor cuyo estado sea el mismo que el del nodo padre No cree rutas que contengan ciclos No genere ningn estado que se haya generado alguna vez anteriormente


b) Mtodos de Bsqueda con Informacin

Son aquellas estrategias en las que se utilizaun conocimiento especfico, que gue la bsqueda, en problema determinado

Para guiar la bsqueda se utiliza una funcin de evaluacin, la que retorna un nmero, que representa lo deseable o indeseable de la expansin de un nodo.

Cuando se expande un nodo con un menor valor de la funcin de evaluacin f(n), la bsqueda se llama preferente por lo mejor.


La funcin de evaluacin mencionada, para cada nodo n, considera:

una funcin de costo de ruta g(n)

una funcin h(n), que mide el costo de pasar de cualquier nodo n, al nodo meta, llamada heurstica.

f(n) = g(n) + h(n)

f(n): funcin de evaluacin del costo aproximado de un camino solucin que pasa por el nodo ng(n): costo de generar el nodo nh(n): heurstica que genera el valor aproximado del costo faltante para generar un camino solucin


S0SnS*g(n)h(n)f(n) = g(n) + h(n)


Mtodos respaldados con informacin

Bsqueda Avara El criterio de expansin, o la lnea deespera, se ordena por min f(n) = h(n)

Bsqueda A* La lnea de espera se ordena mediante

min f(n) = g(n) + h(n)


En la siguiente diapositiva se muestra una especie de mapa de Rumania, en cual las ciudades estn conectadas por carreteras cuyas distancias se indican en los arcos. En la transparencia subsiguiente se muestran las distancias en lnea recta de cada ciudad a Bucharest. El problema que se quiere resolver es el de ir de Arad a Bucharest, usando los algoritmos de bsqueda avara y A*.


OradeaZerindAradSibuiFagarasTimisoaraLugojMehadiaDobretaRimmicuCraiovaPitestiBucharestGiorgiuUrziceniEfoireHirsovaVasluiIasiNeamt71751181117570151140120146801387799211101808598861429287


Distancia en lnea recta a Bucharest

Desde a Bucharest Desdea Bucharest

Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti98Efoire161Rimmicu193Fagaras178Sibui253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind374


Mediante Bsqueda Avara (Heurstica distancia en lnea recta a Bucharest)AradSibuiZerindh=366h=253h=374AradSibuiZerindh=366 h=374h=329Timisora Timisoarah=329FagarasOradea Rimmicuh=178h=380h=193


Mediante Bsqueda Avara (Heurstica distancia en lnea recta a Bucharest)AradSibuiZerindh=366 h=374 Timisoarah=329FagarasOradea Rimmicuh=380h=193Bucharesth=0Solucin: Ruta 1: Arad-Sibui-Fagaras-Bucharest Costo = 140+99+211=450Ruta 2: Arad-Sibui-Rimmicu-Pitesi-Bucharest Costo= 140+80+97+101= 418

La Ruta 1 tiene 32 Km ms que la ruta 2, la bsqueda avara no es ptima


Mediante Bsqueda A* (Heurstica distancia en lnea recta a Bucharest) f(n) = g(n) + h(n)AradSibuiZerindf= 0 + 366=366f=140+253=393f= 75 +374=449AradSibuiZerindf=366 f=449f= 118 +329=447Timisora Timisoaraf=447FagarasOradea Rimmicuf=140+99+178f=417f=140+151+380f=671f=140+80+193f=413f=393


Mediante Bsqueda A* (Heurstica distancia en lnea recta a Bucharest) f(n)= g(n) + h(n)AradSibuiZerindf=366 f=449 Timisoaraf=447FagarasOradea Rimmicuf=671f=413f=393f=417PitestiCraiovaBucharestf=317+101+0f=418f=220+97+98f=415f=220+146+160f=526Solucin: Arad-Sibui--Rimmicu-Pitesti-Bucharest (solucin de mnimo costo)Costo: 418


Problema del Puzzle-8El objetivo del puzzle-8 es acomodar una configuracin inicial de 8 piezas en una plantilla de 3x3 localidades, con el objetivo de llegar a una configuracin final deseada. La forma de acomodar las piezas slo puede ser realizada desplazando una pieza hacia una localidad vecina que est vaca.8588Estado Inicial (S0)Estado Final (S*)23147651234678O3O2O42314765283147652314765


Planteamiento formal Puzzle-8Espacio de estados: Cualquier configuracin de los nmeros del 1 al 8 en unamatriz de 3x3

Estado inicial: configuracin inicial de los nmeros

Estado final: configuracin final deseada

Operadores:

O1: mover la celda vaca hacia arribaO2: mover la celda vaca hacia abajoO3: mover la celda vaca hacia la izquierdaO4: mover la celda vaca hacia la derecha

Prueba de meta: Comparar si la configuracin inicial coincide con el estado final

Costo de ruta: 1 al aplicar cada operador


Resolver el problema del puzzle-8, mediante A*, usando la heurstica h(n) como la distancia de los nmeros a sus lugares en el estado final.

Considere como estado inicial y final los indicados mas abajo812 437551234678Estado inicialEstado Final6233


124837654128376512348765123487651234857612348576f=1+7f=8f=1+5f=6f=2+6f=8f=2+4f=6f=3+3f=6O3O2O3O2O3


Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

1234857612345786123485761342578612345786123745861245378612345678f=3+3f=6f=4+2f=6f=4+4f=8f=5+3f=8f=5+3f=8f=5+1f=6f=6+2f=8f=6+0f=6O1O3O1O304O1O2


Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

Hoja1

Hoja2

Hoja3

La solucin del problema anterior consiste en aplicarla secuencia de operadores: O2-O2-O3-O1-O4-O2, el costo de ruta es 6.

Resuelva este mismo problema, pero ahora usando la heurstica h(n)= nmero de piezas (nmeros), fuera de lugar.

Resuelva el siguiente problema, usando bsqueda avara y A*. Compare el resultado dado por A* con el entregado por costo uniforme


AFCEBD41227581463EI : AEF :CEstado HeursticaA9B3C0D8E6F10


El Algoritmo A*

(Best First) BFAGBG + f(n)

f(n) es la funcin de evaluacin

Definimos f*(n) = g*(n) + h*(n)g*(n) = costo mnimo del inicial a nh*(n) = costo mnimo de n a los objetivosA* BF con f(n) = g(n) + h(n)g(n) = costo del inicial a n a travs del rbol de bsqueda desarrollado hasta el momentoh(n) = estimacin positiva de h*(n), es la heursticaLuego f(n) es una estimacin de f*(n)


Propiedades Formales del Algoritmo A*

Definicin: C*=f*(inicial) = h*(inicial)

Propiedades n : h(n) 0, g(n) g*(n) 0C* = f*(n) n est un camino ptimoDefinicin: Un algoritmo es completo si encuentra una solucin, si sta existeDefinicin: Un algoritmo es admisible si encuentra una solucin ptimaDefinicin: A1(h1) domina a A2(h2) si todo nodo expandido por A1 tambin lo es por A2Definicin: A1 domina estrictamente a A2 ssi A1 domina a A2 y A2 no domina a A1


Completitud y Admisibilidad

Proposicin: El algoritmo BF siempre termina y es completo en grafos finitos

Teorema 1: A* es completo en grafos localmente finitos

Definicin: Una funcin h es admisible sii es una estimacin optimista de h*. Es decir n h(n) h*(n),donde h*(n) es el verdadero costo del estado n al nodo meta mas cercano

Proposicin: Para cualquier camino ptimo P del Inicial a un objetivo antes de terminar A*, existe un nodo de P en ABIERTA con f(n) C*

Teorema 2: Si h es admisible entonces A* es admisible


Comparacin Estricta de Algoritmos A*

Definicin: Una heurstica h2 est mejor informada que h1ssi las dos son admisibles y n no final: h2(n) h1(n)

Teorema 3: Si A2* es ms informado que A1*, entonces A2* domina a A1*, es decir todo nodo expandido por A2* tambin lo es por A1*NodosValor h*h2h1


Condiciones de Expansin (dinmicas)

Teorema 4. Si A* es admisible, una condicin necesaria para que un nodo sea expandido por A*es que f(n) C*

(n ABIERTA) ( n se expande) (f(n) C*)

Teorema 5. Si A* es admisible, una condicin suficiente para que un nodo sea expandido por A* es que f(n) C*

(n ABIERTA) (f(n) C*) (n se expande)


Condiciones de Expansin (estticas)

Definicin: Un camino P que parte del nodo inicial es C-acotado sii n P gp(n) + h(n) C, y es estrictamente C-acotado sii n P gp(n) + h(n) C

Teorema 6. Si A* es admisible, una condicin suficiente para que un nodo sea expandido es que exista un camino P del inicial a n que sea estrictamente C*-acotado.

Teorema 7. Si A* es admisible, una condicin necesaria para que un nodo sea expandido es que exista un camino P del inicial a n que sea C*-acotado.


Resolucin de Problemas con A*

Elementos generales Descripcin de los estados Descripcin del estado inicial y de los terminales u objetivos Descripcin de las reglas/operadores que transforman los estados de bsqueda

Elementos especficos de A*Descripcin de los costos de aplicacin de las reglas/operadores (permitirn el clculo de g(n))Funcin heurstica de estimacin del costo de cada nodo al nodo final (clculo de h(n))


EEl problema del vendedor viajero (TSP)

El vendedor viajero debe realizar desde su sede una gira a travs de N ciudades por carretera. El problema es cul es la ruta que debe seguir para visitarlas todas y volver a su punto de salida recorriendo el menor nmero de kilmetros posible?

Estados Secuencias de ciudades que empiezan en A y que representan recorridos parcialesInicial: AFinales: secuencias que contengan todas las ciudades y que empiecen y terminen con AReglas a cada estado agregarle al final el smbolo de una ciudad que no figure en el recorrido parcial actualCosto de aplicacin de las reglas: es la distancia entre la ltima ciudad y la que se agrego al final


Ejemplo

ABCDEF___________________________________A21121511392B 725 32 9C 5 1820D18039E17


Heursticas para el TSP (I)

h1(n)= 0 en todos los casos (costo uniforme)

h2(n)= nmero de arcos que faltan multiplicado por el costo del arco mnimo h2(ABE) = 4*5 = 20

h3(n)= suma de los p arcos mas cortos si faltan p arcos h3(ABE) = 5 + 5+ 7 + 7=24

h4(n)= suma de los arcos mas cortos que parten de las ciudades que quedan por abandonarh4(ABE)= aban E 17 + aban C 5 + aban D 5 + aban F 9 = 36

h5(n)=suma de los arcos ms cortos que salen de las ciudades que quedan por alcanzar{ h5(ABE)= alc A 12 + alc C 5 + alc D 9 + + alc F 9 = 31 }


Heursticas para el TSP (II)

h6(n)= distancia mas corta entre la ltima ciudad de n y la ciudad de partida

h7(n)= nmero de arcos que faltan multiplicado por el costo medio de los arcos

h8(n)= suma de los p arcos ms grandes si faltan p arcos

Se puede probar que: h1(n) h2(n) h3(n) h4(n)h1(n) h2(n) h3(n) h5(n)h1(n) h6(n)


El puzzle - 8

Heursticas:

h1(n)= nmero de elementos fuera de sitio de n respecto al estado final

h2(n)= suma de las distancias (Manhattan) de todos los elementos a la posicin del estado final


El problema Job Shop Scheduling

Dado un conjunto de trabajos J1, J2,...Jn, tales que cada trabajo Ji, 1 i n, est a su vez compuesto por un conjunto de tareas ti1, ...tim, cada una de las cuales necesita utilizar un recurso del conjunto de recursos R1, .....,Rm y tiene una duracin Dij, 1in, 1jm.

Se trata de organizar la ejecucin de todas las tareas en el tiempo de forma que se minimice el tiempo total (makespan), teniendo en cuenta que1.- las tareas de un trabajo deben realizarse secuencialmente2.- dos tareas no se pueden solapar en el tiempo si necesitan el mismo recurso3.- la ejecucin de una tarea en una mquina no puede ser interrumpida4.- los trabajos tienen un tiempo mnimo de inicio, y5.- los trabajos tienen un tiempo mximo de fin


El espacio de Bsqueda para el JSS

Estados: Situaciones en las que unas tareas estn planificadas y otras aun no lo estnInicial: todas sin planificarObjetivos: todas planificadasReglas: lo habitual es que representen la asignacin de un tiempo de inicio a una de las tareas sin planificar, de modo que la asignacin sea compatible con las asignaciones previas. El costo es lo que aumenta el makespan parcial. Ejemplos:en cada estado elegir cualquier tarea de las no planificadas y asignarle cualquier tiempo de inicio posibleelegir solamente entre las tareas cuyas predecesoras en el trabajo ya estn planificadas, y una vez elegida una tarea asignarle el menor tiempo de inicio posibleotra idea mejor: utilizar el algoritmo G&T que restringe la bsqueda al conjunto de planificaciones activas


Monotona y Consistencia

Definicin: Se dice que una funcin heurstica h satisface la condicin de monotona si y slo si para todo par de nodos n1 y n2 se verifica que h(n1) h(n2) + c(n1,n2), donde c(n1,n2) representa el costo preciso para ir desde el nodo n1 al nodo n2

n1objetivon2h(n1)c(n1,n2)h(n2)


inteligencia artificial

Documents

Transcript of inteligencia artificial