Inteligencia Artificial (página 2)

Paradigmas de Inteligencia Artificial o Heurísticas Generales

• Prueba y Error
• Dividir y conquistar

Sistemas de Producción

• Situaciones: Foto del problema en un momento dado
• Movidas: Cambios entre Situaciones
• Sistemas de Control

1. Punto de Partida (BDGi)
2. Conjunto de Reglas (Movidas)
3. Condición de Terminación
4. Estrategia de Control

Base de Datos Global (BDG): Son los datos que representan una situación

Estrategia de Control: El caso a estudiar es Backtraking

Reglas: Reglas de Producción

Son definidas mediante: IF condición THEN acción

Donde la condición es una expresión booleana de la BDG sindo verdadera cuando la movida es permitida y la acción es una actualización de la BDG que actualiza los resultados en la BDG.

Relación:

Situación Þ Datos Þ BDG

Movidas Þ Código Þ Reglas de Producción

Estrategias de Control

Las estrategias de control son métodos para encontrar caminos, que se traducen como métodos de búsqueda por prueba y error en forma de heurísticas básicas.

Los métodos que habiendo solución la encuetran se denominan admisibles.

Los métodos que encuentran la mejor solución se denominan optimales.

1. En estos casos una vez realizada la movida no se puede volver atrás, ya que no guardan una copia de la base inicial, por ejemplo el método de Hill Climbing.

2. Métodos irrevocables
3. Métodos Tentativos

En estos procedimientos se guarda una copia de la Base inicial, permitiendo el paso atrás, por ejemplo Backtraking y la Búsqueda en Grafo (Informado o Desinformado)

Desarrollo de los Métodos

• Hill Climbing

Siendo f la función de evaluación en el nodo ni

¦ : Estado ® R

El valor máximo de la función evaluación se encuentra en el nodo final

¦ (nf) = Máximo

Procedimiento

1. 1. Se toma la BDGi. Si cumple con la condición de terminación, se detiene, sino aplico todas las reglas que sean aplicables y obtengo nuevas bases
   2. Se evalúa la función de evaluación de cada base y tomo la regla y la base con la cual obtengo el mayor valor

      Condiciones de la función de evaluación

      • Que no tenga máximos ni mínimos locales
      • Que no tenga mesetas
      • Que no presente puntos de ensilladura
   3. Vuelvo a aplicar el punto 1 para la nueva base
   • Backtraking

   Procedimiento

   1. Se toma la BDGi.Si cumple con la condición de terminación se detiene sino se aplica la primera regla de las reglas y se obtiene una nueva base

      No se puede profundizar cuando:

      1. No quedan reglas apicables
      2. Se repiten bases en la rama jerárquica
      3. Se supera un nivel de profundidad
   2. Se toma la primera base y se repite, cuando no se puede profundizar más, vuelve a la base anterior y elige la regla siguiente.
   1. Desinformado o de Fuerza Bruta o Búsqueda a Ciegas
2. Búsqueda en Grafo

1.1. Deep First (Primero en Profundidad)

1. Si BDGi cumple con la condición de terminación termina sino aplica todas las reglas y guarda en memoria la lista de bases abiertas
2. Se elige una de las bases más profundas, por convención, la de la izquirda y repito
3. Se continúa hasta que no se pueda profundizar más y se continúa con la más profunda

1.2. Wide First (Primero en Ancho)

Es un método admisible

1. Si la BDGi verifica la condición de terminación termina sino aplico todas las reglas aplicables y la BDGi se destruye
2. Se forma una nueva lista de bases y se elige la menos profunda

1. Informado o Focalizafo

El Método A*

A* es un método admisible y optimal

Se le asignan a las movidas un Costo Ci siendo Ci > x >0 siendo x costos possitivos no infinitésimos.

El costo de la movida esta asociado al costo de las reglas y estas al costo del arco.

La solución de menor cantidad demovidas se plantea como la suma de los costos de las movidas con valor unitario.

La búsqueda focalizada implica una función heurística ¦ (nodo) que devuelve como resultado el costo estimado del mejor camino que pasa por el nodo y va desde el nodo inicial al nodo final.

Siendo ¦ (nodo) = g(nodo) + h(nodo)

La función g(nodo) que devuelve el costo estimado del mejor camino que va desde el nodo inicial al nodo sumando el costo de las reglas.

La función h(nodo) es el costo estimado del mejor camino que va desde el nodo hasta el nodo final. Es la función hurística propiamente dicha, ya que ayuda dada al sistema.

Para todo nodo:

g(nodo) ³ g*(nodo)

h(nodo) £ h*(nodo)

Siendo g* el costo real del camino del nodo inicial al nodo y h* el costo real de la ruta del nodo al nodo final

Admisibilidad del Algoritmo A*

Para garantizar que el algoritmo A* encuentre siempre el camino de mínimo coste, tanto el grafo como la función h* deben satisfacer ciertas condiciones:

2. Cada nodo del grafo tiene un número finito de sucesores
3. El coste de cada arco del grafo es mayor que una cierta cantidad positiva x
4. La función h(nodo) debe satisfacer la siguiente condición: en todos los nodos del grafo de búsqueda se tiene que cumplir que h(nodo) £ h*(nodo), es decir, la función h(nodo) nunca sobreestimará el valor real, que viene dado por la función h*(nodo)

Complejidad Computacional en el Tiempo y en el Espacio

Siendo

Tiempo = ¦ 1(s)

Espacio = ¦ 2(s)

Estudios Asintóticos

T = lim s® ¥ ¦ 1(s)

M = lim s® ¥ ¦ 2(s)

L = Es el nivel que lleva encontrar la solución

Teorema de la Aceleración (Speed Up)

Dado un T decodificando la entrada se puede conseguir T/K, depreciando los términos por el teorema de menor orden y por Speed Up, los factores que multiplican los de mayor orden

Complejidades de los distintos métodos

Hill Climbing :

El tiempo es proporcional a la lista y estas proporcionales a las reglas aplicables. El factor de ramificación (Brenching Factor) es b * L, b (cantidad de bases abiertas o reglas aplicadas) y L el nivel.

T = ¶ (b*L), s = b*L que crece linealmente

M = ¶ (b), s = b que se mantiene constante, no utilizando más memoria con la profundidad alcanzada

Backtraking

s = 1+ b + b2 + … + bL Þ bs = b + b2 + … + bL+1 Þ (b-1)s = bL+1 –1 Þ s = bL+1 –1 / (b-1) = bL

T = ¶ (bL) que es de carácter exponencial , no factible

M = ¶ (L) es de crecimiento lineal

Profundidad Primero

T = ¶ (bL) es exponencial por lo tanto, no factible

M = ¶ (bL) es exponencial

Ancho Primero

T = ¶ (bL) es exponencial, no factible

M = ¶ (bL) es exponencial, no factible

i

s = S b i => s = bL+1 –1 / (b-1) = bL

0

Método A*

T depende de h(nodo) ¶ (b*L) £ T £ ¶ (bL)

M depende de h(nodo) ¶ (b) £ M £ ¶ (bL)

Resumen :

Cuadro Comparativo

Ejemplos:

Los Misioneros

A la orilla de un río encontrabasé un grupo de tres misioneros y otro de tres caníbales los cuales querían cruzar a la otra orilla del río, para ello diponían de una balsa la cual podía llevar solo a dos personas. Si el número de caníbales no puede sobrepasar el número de misioneros sino estos serían deborados ¿ Cómo hicieron los misioneros y los caníbales para cruzar?.

Sistema de Producción

1. Base de Datos Global:

Una variable M [0,1,2,3] que indique la cantidad de misioneros a la derecha

Una variable C [0,1,2,3] entera que indique la cantidad de caníbales a la derecha

Una variable B [0,1] que indique si el bote se encuentra a la derecha

2. Conjunto de Reglas (Movidas):

pasa Misionero : IF M>0 AND B=0 AND M>C THEN M=M-1; B=1

vuelve Misionero : IF M>0 AND B=1 AND M<C THEN M=M-1; B=0

pasa Canibal y Misionero: IF M>0 AND B=0 AND C>0 THEN M=M-1; C=C-1;B=1

pasa Canibal : IF M>0 AND B=1 AND M>C THEN M=M-1; B=0

vuelve Canibal : IF M>0 AND B=1 AND C>0 THEN M=M-1; C=C-1;B=0

3.

1. BDGi : M=3,C=3,B=0
2. Condición de Terminación: M=0 AND C=0
3. Estrategia de Control:

Hill Climbing

Backtraking

DeepFirst

Wide First

A*

El Ascensor

Un ascensor sube con dos ó tres personas y baja con sólo una persona.

Hay siete personas en planta baja y seis deben subir mientras que sólo una debe quedar de guardia .

Sistema de Producción

1. Base de Datos Global:

Una variable P [0,1,2,3,4,5,6,7] que indique la cantidad de gente en Planta Baja.

Una variable A [0,1] que indique si el asensor se encuentra en Planta Baja.

2. Conjunto de Reglas (Movidas):

Suben 2: IF P>=2 AND A=0 THEN P=P-2 ; A=1

Suben 3: IF P>=3 AND A=0 THEN P=P-3 ; A=1

Baja1: IF P<=6 AND A=1 THEN P=P+1; A=0

3.

1. BDGi: P=7,A=0
2. Condición Terminación: P=1
3. Estrategia de Control:

Hill Climbing

Backtraking

DeepFirst

Wide First

A*

Gabriel Pineda