Inteligencia artificial

EXTRACTO SACADO DEL WORD QUE PASASTEIS EL OTRO DIA

_________________________

Inteligencia Artificial

Resolución de problemas en Inteligencia Artificial mediante sistemas de producción y búsqueda en espacios de estados.

Un problema en inteligencia artificial consiste en :
● Una descripción de la situación de la que se parte.
● Una descripción de la situación a la que se quiere llegar.
● Una descripción de los medios de que disponemos para alcanzar nuestro objetivo.

Ejemplo:

Se parte de un tablero 3x3 donde aparecen distribuidos los dígitos 1,2,....,8 quedando por tanto una casilla en blanco. Inicialmente están desordenados en una posición determinada.
Se quiere llegar a una situación en la que estén los dígitos ordenados del 1 al 9 de forma consecutiva.
Los medios de que disponemos son los siguientes: si una casilla del tablero está al lado de la casilla vacía se puede desplazar sobre ella.

Un sistema de producción consiste en:
● Información sobre el problema ¿Como es el “tablero”? de que situación parto y a que situación quiero llegar etc etc.
● Un conjunto de reglas (operadores). Cada regla consta de:
○ Precondición: descripción parcial del estado del mundo que debe ser verdad para que sea ejecutable el operador. Si un operador no es ejecutable, se deberá elegir otro que sí lo sea, si lo hay, o descartar ese camino del árbol.
○ Instrucciones para generar el nuevo estado resultante de aplicar el operador.
● Una estrategia de control, que especifica un aplicador de reglas: es decir, si tengo varios operadores aplicables, ¿cuál elijo? ¿en qué orden voy generando/explorando el árbol que define todo lo que puede ocurrir?.

¿Que significa encontrar una solución?

Para alcanzar una solución del problema debemos disponer de una descripción de un estado deseado de ese universo de soluciones.
La descripcción puede ser completa o parcial.
La solución consiste en una secuencia de operadores que transforman el estado inicial en el estado objetivo.
● Me puedo encontrar con dos tipos de problemas a resolver.
○ El problema de decisión: decir si sí o no se puede alcanzar el objetivo desde el estado inicial.
○ El problema de explicación: indicar cómo se llega desde el estado inicial al objetivo.
● Me pueden imponer ciertas restricciones sobre las secuencias solución:
○ Encontrar la secuencia más corta.
○ Encontrar la secuencia menos costosa ( en este caso me tendrán que especificar cuál es el coste de aplicar cada operación concreta.
○ Encontrar cualquier secuencia lo más rápido posible.
○ Encontrar todas las secuencias solución

Estrategias de control

● La parte más importante de los sistemas de producción es la estrategia de control (también llamada en algunos contextos motor o mecanismo de inferencia).
● Es la que establece el proceso de búsqueda de la solución, la que establece cómo explorar el árbol de soluciones y por qué camino ir en cada momento.
● Vamos a distinguir entre dos tipos de estrategias de control:
● No informadas: desde un estado concreto, no sabemos cómo de cerca o lejos está el estado objetivo si no exploramos previamente el subárbol del que es raíz.
● Heurísticas: Se dispone de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores.

Esquema algorítmico genérico de búsqueda:

ABIERTOS:=(nodo-inicial)
Resuelto:= FALSO;

mientras que ABIERTOS no es vácia y NO RESUELTO hacer
N:= Quitar primer elemento de ABIERTOS.
E:= estado asociado a N
si E es un estado objetivo
entonces RESUELTO := VERDAD
sino para cada operador O hacer
si O se puede aplicar a E entonces
Crear un nodo correspondiente al estado obtenido por aplicación de O a E y añadir ese nodo a ABIERTOS
si RESUELTO
entonces devuelve el estado objetivo (y si se requiere una explicación, la secuencia de operadores aplicada para llegar hasta él).
sino
informa de que el objetivo no puede ser alcanzado.


Busqueda en anchura.
● Recordemos una pieza clave del algoritmo anterior “ crear un nodo correspondiente al estado obtenido por la aplicación de O a E y añadir ese nodo a ABIERTOS”.
● En la búsqueda en anchura los nuevos nodos son añadidos al final de la lista ABIERTOS.
● Así se consigue que los nodos en ABIERTOS estén ordenados según su profundidad en orden decreciente: los menos profundos al principio.
● La lista de nodos ABIERTOS se comporta como una cola: los primeros entrar son los primeros en salir.,
● Hasta que todos los nodos de un nivel no han sido revisados, no se revisa ninguno del siguiente nivel.
● La búsqueda en anchura es una estrategia exhaustiva.
● La búsqueda en anchura siempre encuentra la secuencia solución más corta.,
● La búsqueda en anchura siempre encuentra solución, incluso en un espacio de estados con ciclos.
● No obstante la búsqueda en anchura puede llegar a ser extremadamente ineficaz ya que es computacionalmente muy costosa, y si hay ciclos explora muchas veces las mismas ramas.

Coste computacional de la búsqueda en anchura.

Sea b el factor de ramificación: media del númer ode nodos generados desde un nodo.
Sea d la profuncidad del estado objetivo: mínimo del número de aplicaciones de reglas necesarias para llegar del estado inicial a un estado inicial a un estado objetivo (asumiendo que existe solución).
Complejidad en espacio: relacionada con la longitud máxima que puede alcanzar la lista de abiertos, que coincide con el número de nodos del nivel inferior a analizar. O(bd)
Complejidad en tiempo:relacionada con el número de nodos generados.O(bD)
Ejemplo: 8-Puzzle . B= 3 . Si partimos de un estado que está a distancia 20 del objetivo, d=20. bd= 3.486.784.401

Búsqueda en profundidad.

Los nuevos nodos son añadidos al comienzo de la lista ABIERTOS, consiguiendo que los nodos en esa lista están ordenados según su profundidad, con los más profundos al principio.
De esta forma se desciende rápidamente por una rama concreta del árbol.
La complejidad en espacio pasa a ser O(db). La complejidad en tiempo en el peor caso continúa siendo O(db) aunque el número de estados examinados puede ser considerablemente menos que la búsqueda en anchura.
La búsqueda en profundidad es mucho más sensible que la búsqueda en anchura en lo que se refiere al orden de aplicación del as reglas. Incluso puede depender de ello el que termine o no.
En los casos en que la búsqueda en profundidad encuentre una solución, nada nos asegura que dicho camino solución sea longitud mínima.
Un modo de conseguir que la búsqueda termine siempre es fijar un límite máximo de profundidad y no explorar aquellos nodos cuya profundidad sea superior.

Estrategias de control heuristicas.
● Los métodos de búsqueda heurística dispinen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en priemr lugar los caminos más prometedores:
● Caracteristicas:
○ No garantizan que se encuentre una solución aunque existan soluciones.
○ Si encuentran una solución, no se asegura que ésta tenga buenas propiedades (que sea de longitud mínima o de coste óptimo=).
○ En algunas ocasiones, encontrarán una solución aceptablemente buena en un tiempo razonable.
Los métodos heurísticos sacrifican la completitud para aumentar la eficiencia.
El algoritmo tiene cierto conocimiento que usará en tiempo de ejecución sobre el problema concreto que debe resolver aprovechando esa información en los procedimientos expandir-nodo y reorganizar-nodos-a-expandir.

Función de evaluación heurística.

● La función de evaluación heurística asocia a cada estado del espacio de estados una cierta cantidad numérica que evalúa de algún modo lo prometedor que es ese estado para acceder a un estado objetivo. Se denota por h(e).
● La función heurística puede tener dos interpretaciones:
○ Puede ser la estimación de la “calidad” de un estado. Los estados de mayor valor heurístico son los preferidos.
○ Puede ser una estimación de lo próximo que se encuentra el estado de un estado objetivo. Los estados de menor valor heurístico son los preferidos.
Las funciones heurísticas más interesantes son aquellas que son bien fundadas:
○ Si la función heurística mide la calidad de un estado será bien fundada si todos los estados objetivo tienen valores mayores que el resto de los estados.
○ Si mide la proximidad a un estado objetivo, lo será si los estados objetivo tienen valor 0.

Estrategia para juegos

● Vamos a ocuparnos solo de juegos de dos jugadores, con información perfecta (es decir en los que no interviene el azar y cada jugador “ve” toda la información del otro) y de suma cero ( sólo se puede GANAR, PERDER O EMPATAR). Ejemplos: damas, ajedrez, tres en raya.
● Un árbol de juego es una representación explícita de todas las jugadas posibles en una partida. Las hojas corresponden a posiciones GANAR, PERDER o EMPATAR (G,P,E). Cada camino desde la raíz hasta una hoja representa una partida completa.
● Se denomina MAX al jugador que abre el juego y MIN al otro. Las posiciones MAX y MIn se distinguen por los niveles del árbol en que aparecen. Si identificamos la raíz con el nivel 0 y empieza jugando MAX, las posiciones de nivel par corresponden a MAx y las de impar a MIN.

Una vez conocido el árbol de juego, podemos propagar hacia arriba las etiquetas G,P,E de las posiciones terminales:
● La etiqueta que tendrá una posicion MAX no terminal, será:
○ G Si algún sucesor tiene etiqueta G.
○ P si todos los sucersores tienen etiqueta P.
○ E en otro caso.
● La etiqueta que tendrá una posición MIN no terminal será:
○ G si todos los sucesores tienen etiqueta G.
○ P si algún sucesor tiene etiqueta P.
○ E en otro caso.
● La etiqueta de una posición nos indica lo mejor que podría jugar MAX en caso de que se enfrentase a un oponente perfecto.
● Resolver un árbol de juego significa asignar, siguiendo el proceso anterior, una etiqueta G,P o E a la posición inicial.
● Un árbol solución para MAX debe ser interpretado como un plan ( una estrategia) de los movimientos que debe realizar MAX, ante cualquier posible movimiento de MIN.
● Conociendo un árbol solución para MAX, podemos programar a un ordenador para que juegue contra un contrincante MIN ( humano o máquina).
● Tener un árbol solución para MAX no es garantía de que éste gane. Ganará seguro, haga lo que haga MIN, si y sólo si al resolver el árbol de juego la etiqueta de la posición inicial es G

Para la mayoria de los juegos, desarrollar todo el árbol de juego es una tarea impracticable:
Damas: 10^40 posiciones no terminales. Si fuésemos capaces de generar 3 billones de posiciones por segundo, necesitamos 10^21 siglos.
Ajedrez: 10 ^ 120 posiciones no terminales. Si i fuésemos capaces de generar 3 billones de posiciones por segundo, necesitamos 10^101 siglos.
Puesto que por restricciones de tiempo y espacio no podemos evaluar la etqieuta exacta de cada posición sucesora, debemos pensar en una aproximación heurística.
Tenemos una función de evaluación estática h que nos indica cuál es el “mérito” de cada una de las posiciones. h asigna valores grandes a las posiciones que son más favorables para MAX.
Una estrategia como ésta no tiene en cuenta la incertidumbre introducida por la existencia del segundo jugador (no sabemos qué movimiento realizará), y depende demasiado de la calidad de la función h.
Lo más lógico es explorar el árbol de juego hasta un nivel fijado ( que se denomina frontera de búsqueda), en las posiciones de ese nivel aplicar la función de evaluación estática, y después propagar hacia arriba esos valores.

Si N es una posición terminal o una posición en la frontera de búsqueda, el valor V(N) es igual al valor de la función h(N). En otro caso…
Si N es una posición MAX, V(N) es igual al máximo de los valores de sus sucesores.
Si N es una posición MIN, V(N) es igual al mínimo de los valores de sus sucesores.
Si hacemos P=-1, E = 0 y G = 1 y no ponemos ningún límite de profundidad, entonces este método es equivalente al método de etiquetado explicado.

Normalmente el método MIniMax se suele implementar junto con la poda alfa-beta que es una mejora para podar bastantes ramas del árbol haciendo más rápida su evaluación.
Ya no entramos en detalles sobre cómo implementarlo...