LENGUAJE DE PROGRAMACIÓN PROLOG

Fecha de la clase: 15 de Enero

INTRODUCCIÓN

El objetivo de esta clase es investigar sobre PROLOG para utilizarlo en ejercicios de Inteligencia Artificial. La resolución de ejercicios en este programa consiste en crear un archivo como la base de conocimiento que contendrá información suficiente para que se tomen correctas decisiones y se arrojen respuestas correctas y otro el cual es el que llevará las reglas, que validaran las solicitudes para dar las respuestas.

MARCO TEÓRICO

PROLOG

PROLOG es un lenguaje de programación muy útil para resolver problemas que implican objetos y relaciones entre objetos. Está basado en los siguientes mecanismos básicos:      

  o   Unificación

  o   Estructuras de datos basadas en árboles

  o   Backtracking automático

La sintaxis del lenguaje consiste en lo siguiente:

    o   Declarar hechos sobre objetos y sus relaciones

    o   Hacer preguntas sobre objetos y sus relaciones

    o   Definir reglas sobre objetos y sus relaciones. (Escrig,T).

HECHOS

ü  Átomos en Lógica de Predicados.

ü  No se permiten disyunciones.

ü  Los nombres de los predicados empiezan con minúscula.

ü El hecho debe terminar con un punto.

PREGUNTAS

En tiempo de ejecución, aparece el prompt ?- y el intérprete de PROLOG espera que el usuario introduzca un objetivo en forma de predicado, con o sin variables.

Al igual que en CLIPS, tendremos ficheros con la descripción de la base de conocimiento (hechos y reglas).

baseconoc.pl (o .pro)

esHombre(juan).

esHombre(pedro).

Para cargar un fichero, escribiremos:

?- [baseconoc].

/* Esto añade a la MT de Prolog los hechos del fichero baseconoc.pl */

?- esHombre(juan).

yes

?- esHombre(pedro).

yes

?- esHombre(juanCarlos).

no

?- esMamifero(leon).

 No

 . (Cubero, J).

REGLAS

Existe en PROLOG la posibilidad de definir la relación “abuelo(X,Y)” o la relación “tio(X,Y)” como reglas, además de poderlo hacer como hechos o como conjunción de objetivos.

abuelo(X,Y):- progenitor(X,Z), progenitor(Z,Y).

tio(X,Y):- progenitor(Z,Y), progenitor(V,Z), progenitor(V,X).

A la primera parte de la regla se le llama cabeza o conclusión, el símbolo ":-" es el condicional (SI), y a la parte de la regla que está después de “:-“ es el cuerpo o parte condicional. El cuerpo puede ser una conjunción de objetivos separados por comas. Para demostrar que la cabeza de la regla es cierta, se tendrá que demostrar que es cierto el cuerpo de la regla.

Por lo visto hasta ahora, las cláusulas PROLOG son de tres tipos: hechos, reglas y preguntas. Las cláusulas PROLOG consisten en una cabeza y un cuerpo. Los hechos son cláusulas que tienen cabeza pero no tienen cuerpo. Las preguntas sólo tienen cuerpo. Las reglas tienen siempre cabeza y cuerpo. Los hechos son siempre ciertos. Las reglas declaran cosas que son ciertas dependiendo de una condición. El programa PROLOG (o base de datos PROLOG) está formado por hechos y reglas y para PROLOG no hay ninguna distinción entre ambas. Las preguntas se le hacen al programa para determinar qué cosas son ciertas. (Escrig,T).

CONCLUSIÓN

Este lenguaje prolog está orientado a la IA , usando para esto la programación lógica. Prolog tiene la facilidad para programar y contiene una sintaxis sencilla gracias a esto los programadores pueden escribir rápidamente un código y no contener muchos errores, además es de fácil entendimiento y puede ser utilizado por inexpertos.

BIBLIOGRAFÍA

Cubero, J. 2009. Tutorial de Prolog. En Línea. Formato PDF. Disponible en http://elvex.ugr.es/decsai/intelligent/workbook/ai/PROLOG.pdf

Escrig,T. 2005. El lenguaje de Programación PROLOG. En línea. Formato PDF. Disponible en http://mural.uv.es/mijuanlo/PracticasPROLOG.pdf

JUEGOS

Fecha de la clase: 8 de Enero

INTRODUCCIÓN

En esta clase se realizaron unos trabajos de investigación en clase en los que se expusieron cada uno de los trabajos en uno de estos vimos sobre los juegos y las decisiones óptimas para estos donde tenemos que estos multiagentes pueden ser cooperativos o competitivos.

MARCO TEÓRICO

JUEGOS

La Teoría de Juegos estudia de manera formal y abstracta las decisiones óptimas que deben tomar diversos adversarios en conflicto, pudiendo definirse como el estudio de modelos matemáticos que describen el conflicto y la cooperación entre entes inteligentes que toman decisiones. Tales decisiones se consideran estratégicas, es decir, que los entes que participan en el juego actúan teniendo en cuanta las acciones que tomarían los demás.

La teoría de juegos es capaz de ofrecer cuestiones de interés para estudiantes de todas las ramas de las Ciencias Sociales y la Biología, así como técnicas para tomar decisiones prácticas. (Fernández, F)

Los juegos son interesantes porque son demasiado difíciles de resolver. El ajedrez, por ejemplo, tiene un factor de ramificación promedio de 35 y los juegos van a menudo a 50 movimientos por cada jugador:

Grafo de búsqueda: aproximadamente 10^40 nodos distintos árbol de búsqueda: 35^100 o 10^154. Los juegos, como el mundo real, requieren la capacidad de tomar alguna decisión (la jugada) cuando es infactible calcular la decisión óptima. (Ceccaroni, L).

DESICIONES ÓPTIMAS EN JUEGOS

Un juego puede definirse formalmente como una clase de problemas de búsqueda con los componentes siguientes:

– El estado inicial

– Una función sucesor, que devuelve una lista de pares (movimiento, estado)

 – Un test terminal, que determina cuándo termina el juego (por estructura o propiedades o función utilidad)

 – Una función utilidad. (Ceccaroni, L).

ALGORITMO MINIMAX:

El algoritmo calcula la decisión minimax del estado actual. Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor, directamente implementando las ecuaciones de la definición. La recursión avanza hacia las hojas del retroceder árbol, y entonces los valores minimax retrocedió por el árbol cuando la recursión se va deshaciendo. Por ejemplo, en la Figura, el algoritmo primero va hacia abajo a los tres nodos izquierdos, y utiliza la función Utilidad para descubrir que sus valores son 3, 12 y 8 respectivamente. Entonces toma el mínimo de estos valores, 3, y lo devuelve como el valor del nodo B. Un proceso similar devuelve hacia arriba el valor de 2 para C y 2 para D. Finalmente, tomamos el máximo de 3, 2 y 2 para conseguir el valor de 3 para el nodo de raíz.

El algoritmo minimax realiza una exploración primero en profundidad completa del árbol de juegos. Si la profundidad máxima del árbol es m, y hay b movimientos legales en cada punto, entonces la complejidad en tiempo del algoritmo minimax es O(b^m). La complejidad en espacio es O(bm) para un algoritmo que genere todos los sucesores a la vez, o O(m) para un algoritmo que genere los sucesores uno por uno.

Para juegos reales, desde luego, los costos de tiempo son totalmente poco prácticos, pero este algoritmo sirve como base para el análisis matemático de juegos y para algoritmos más prácticos. (Russell, S y Norvig, P).

CONCLUSIÓN

En anteriores temáticas tratamos sobre agentes que usaban estrategias en la que solo un agente realizaba la búsqueda a la solución, pero en los juegos tenemos dos agentes luchando por tratar de buscar un mismo objetivo.

BIBLIOGRAFÍA

Ceccaroni, L. 2007. Inteligencia Artificial Busqueda entre Adversarios. En Línea. Formato PDF. Disponible en http://www.cs.upc.edu/~luigi/II/IA-2007-fall/2d-busqueda-entre-adversarios-(es).pdf

Fernández, F. 2005. Teoría de Juegos. En Línea. Formato PDF. Disponible en http://imarrero.webs.ull.es/sctm05/modulo1lp/5/ffernandez.pdf

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

BUSQUEDA LOCAL EN ESPACIOS CONTINUOS

Fecha de la clase: 27 de Noviembre

INTRODUCCIÓN

En la clase de búsqueda local en espacios continuos el objetivo es comprender como el agente inteligente realiza la búsqueda en espacios continuos y lo que son las búsquedas online se basa en lo que está pasando en ese estado para tomar de nuevo otra acción clases impartidas en las respectivas exposiciones.

MARCO TEÓRICO

BUSQUEDA LOCAL EN ESPACIOS CONTINUOS

Aun ninguno de los algoritmos descritos puede manejar espacios de estados continuos, la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados! la técnicas de búsqueda local para encontrar soluciones optimas en espacios continuos.

Un modo de evitar problemas continuos es simplemente discretizar la vecindad de cada estado. Podemos aplicar entonces cualquiera de los algoritmos de búsqueda local descritos anteriormente. Uno puede aplicar también la ascensión de colinas estocástica y el temple simulado directamente, sin discretizar el espacio. Estos algoritmos eligen a los sucesores aleatoriamente, que pueden hacerse por la generación de vectores aleatorios de longitud.

Los métodos locales de búsqueda sufren de máximos locales, crestas, y mesetas tanto en espacios de estados continuos como en espacios discretos. Se pueden utilizar el reinicio aleatorio y el temple simulado y son a menudo provechosos. Los espacios continuos dimensionalmente altos son, sin embargo, lugares grandes en los que es fácil perderse.

Un problema de optimización está restringido si las soluciones debieran satisfacer algunas restricciones sobre los valores de cada variable. La dificultad de los problemas de optimización con restricciones depende de la naturaleza de las restricciones y la función objetivo. La categoría más conocida es la de los problemas de programación lineal en los cuales las restricciones deben ser desigualdades lineales formando una región convexa y la función objetiva es también lineal. Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables. También se han estudiado problemas con tipos diferentes de restricciones y funciones objetivo (programación cuadrática, programación cónica de segundo orden, etcetera). (Russell, S y Norvig, P).

BUSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

Después de cada acción, un agente online recibe una percepción al decirle que estado ha alcanzado; de esta información, puede aumentar su mapa del entorno. El mapa actual se usa para decidir dónde ir después. Esta intercalación de planificación y acción significa que los algoritmos  de búsqueda online son bastantes diferentes de los algoritmos de búsqueda offline.

Un algoritmo online, por otra parte puede expandir sólo el nodo que ocupa físicamente. Para evitar viajar atravez de todo el árbol para expandir el siguiente nodo, parece mejor expandir los nodos en un orden local. La búsqueda primero en profundidad tiene exactamente esta propiedad, porque el siguiente nodo a expandir es hijo del nodo anteriormente expandido.

Objetivo del agente:

·       Alcanzar un estado objetivo

·       Minimizando el coste.

Búsqueda off-line:

– Calcula una solución completa antes de poner un pie en el mundo real.

– Después ejecutan la solución sin recurrir a las percepciones.

Búsqueda on-line: Intercala el calcula y la acción.

– Toma una acción

– Observa el entorno

– Calcula la siguiente acción.

Usos de la búsqueda on-line:

– Problemas de exploración, donde el agente desconoce los estados y acciones.

Problemas  de búsqueda en línea (online)

Un problema de búsqueda online puede resolverse solamente por un agente que ejecute acciones, más que por un proceso puramente computacional. Asumiremos que el agente sabe lo siguiente:

– Acciones (). Que devuelve una lista de acciones permitidas en el estado s;

– Funciones de coste individual c(s, a, s’), hay que tener en cuenta que no pude usarse hasta que el agente sepa que s’ es el resultado; y

– Test-Objetivo(s). (Gómez, F).

CONCLUSIÓN

Para las soluciones de problemas con estos algoritmos de búsqueda es que solo se enfocan en lo que sucede en ese estado y luego al darse cuenta de su entorno toma acciones nuevas ya que para otras búsquedas necesitan tener una vista general de la problemática para así realizar una acción.  

BIBLIOGRAFÍA

 Gómez, F. 2010. Métodos de búsqueda de soluciones (Búsqueda informada y exploración). En Línea. Formato (PDF). Disponible en:http://ants.inf.um.es/~felixgm/pub/others/InteligenciaArtificial.pdf

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España. 

FUNCIONES HEURÍSTICAS

Fecha de clase: 13 de noviembre

INTRODUCCIÓN

Otro tema de los tratados en clase con los compañeros y la docente, es este el de las funciones heurísticas que en si son aquellas que ya disponen de alguna información para llegar a su objetivo lo que hace que este tenga más claro el camino a recorrer.

MARCO TEÓRICO

FUNCIONES HEURÍSTICAS

Los métodos de búsqueda heurística disponen 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.

CARACTERÍSTICAS:

• No garantizan que se encuentre una solución, aunque existan soluciones.
• Si encuentran una solución, no se asegura que ésta tenga las mejor esas propiedades (que sea de longitud mínima o de coste óptimo).
• En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.
• En general, los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.
• La información del problema concreto que estamos intentando resolver se suele expresar por medio de heurísticas.
• El concepto de heurística es difícil de aprehender. Newell, Shaw y Simon en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema".
• Si nos planteamos seguir concretando como aprovechar la información sobre el problema en sistemas de producción, la siguiente idea consiste en concentrar toda la información heurística en una única función que se denomina función de evaluación heurística. Se trata de una función que 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. Habitualmente, se denota esa función por h (e). (Malagón, S)

APRENDIZAJE DE HEURÍSTICAS DESDE LA EXPERIENCIA

Una función heurística h(n), como se supone, estima el costo de una solución que comienza desde el estado en el nodo n. Los métodos de aprendizaje inductivos trabajan mejor cuando se les suministrar características de un estado que sean relevante para su evaluación, más que sólo la descripción del estado.

A partir de esto, se puede utilizar un algoritmo de aprendizaje inductivo para construir una función h(n) que pueda predecir los costos solución para otros estados que surjan durante la búsqueda. Las técnicas para hacer esto, está basado en la  utilización de  redes neuronales, árboles de decisión. Y otros métodos. (Russell, S y Norvig, P.)

CONCLUSIÓN

Para la solución de problemas con esta como es la solución de la función heurística es que depende de la información, ya que dependiendo de esta, se puede  encontrar el estado objetivo de una manera eficiente o más rápida.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Malagón, S. 2010.Busqueda heurística. (En línea).Disponible en http://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_heuristica.pdf