UNIFICACION

Por ejemplo en Lógica Proposicional la contradicción es evidente porque Estudia (Belén) ^¬ Estudia (Belén).

Pero en Cálculo de Predicados es diferente porque si tengo:
Estudia(x) ^ ¬Estudia (y). No hay contradicción [Belén/ x, Alberto/y]  Estudia (Belén) ^¬ Estudia (Belén).  

P(a) y P(x) no son comparables, para que lo sean, se debe encontrar una substitución para x que haga ambas fórmulas idénticas. Este proceso de encontrar una sustitución para hacer fórmulas idénticas  se conoce como unificación. Lo que se puede sustituir en una fbf para permitir el paramiento de dos fórmulas son las variables por términos.

Variable (Símbolos de constantes, Símbolos de variables, expresiones funcionales) 

 

Sustitución

• La sustitución de variables por términos generales se remite a variables libres. En las ocurrencias ligadas sólo podemos hacer un cambio de variables por variables y no sucede nada
• La sustitución se debe hacer para todas las ocurrencias libres o para ninguna
• Hay que cuidar que una variable libre no se convierta en ligada por la sustitución.

RESOLUCION

Resolución en Lógica Proposicional

Sea ф la conclusión,  Σ el conjunto de los argumentos:

1. Convertir todas las proposiciones en Σ a su forma de cláusulas 2. Negar ф y convertir el resultado en cláusula. Agregar la o las cláusulas resultantes al conjunto de cláusulas obtenidas en 1
3. Hasta encontrar una contradicción o no se pueda seguir avanzando:

• Seleccionar dos cláusulas que tienen como literales una L y la otra ¬L
• Resolverlas juntas. El resolvente será la disyunción de todos los literales que contienen los padres excepto L y ¬L
• Si el resolvente es la cláusula vacía, es que se ha encontrado una contradicción. Si no lo es agregarla al conjunto de cláusulas disponibles.

Resolución en Lógica de Predicados

1. Convertir todas las expresiones de Σ a Cláusulas 2. Negar ф y convertir el resultado en cláusula  y agregarlo al conjunto obtenido en 1
3. Repetir hasta encontrar una contradicción o no se pueda seguir:

a) Seleccionar cláusulas padres
b) Si existe un par de literales L1 y L2, uno en cada cláusula padre, tal que L1 y ¬L2 sean unificables, entonces obtener el resolvente mediante:

• La disyunción de los literales de ambas cláusulas padres excepto L1 y L2
• Usar la sustitución que unifica L1 y ¬L2 para crear el resolvente
• Si existe más de un par de literales complementarios, sólo se elimina uno

c) Si el resolvente es la cláusula vacía, se ha encontrado contradicción, sino agregarla al conjunto de cláusulas.

SISTEMAS DE PRODUCCION

REPRESENTACIÓN DE PROBLEMAS COMO SISTEMA DE PRODUCCIÓN

La representación mediante formalismos lógicos es declarativa pero puede representar procedimientos. Se describen cuales son los pasos para resolver un problema como una cadena de deducciones. La representación se basa en dos elementos:

v hechos: proposiciones o predicados;

v reglas: formulas condicionales donde el consecuente está formado por un único átomo.

Analogía con búsqueda por reducción a sub-problemas:

v hechos = problemas primitivos.

v reglas  = operadores de reducción.

Un problema queda definido por:

v  Base de hechos: predicados que describen el problema concreto.

v  Base de conocimiento (o de reglas): reglas que describen los mecanismos de razonamiento que permiten resolver problemas.

v  Motor de inferencia: interprete que ejecuta las reglas y obtiene la cadena de razonamiento que soluciona el problema.

La solución de un problema depende del proceso seguido por el intérprete. Terminología de los hechos:

v  Los hechos constituyen los datos del problema en forma de:

–        Base de hechos (BH)

–        Memoria de trabajo

–        Memoria a corto plazo

–        Aserciones

Ejemplos:

–        x es un gato

–        x es un animal doméstico

Terminología de las reglas:

•      Si                                                      entonces

–        condiciones                                    - acciones

–        antecedentes                                  - consecuentes

–        premisas                                          - conclusiones

Las reglas modelan el conocimiento general del dominio y constituyen:

–        Base de conocimiento (BC)

–        Memoria a largo plazo

–        Implicaciones

Ejemplo: Si x es un gato entonces x es un animal doméstico

OTRAS  FUENTES: SISTEMAS DE PRODUCCION

MECANISMOS DE INFERENCIA

Selecciona, decide, interpreta y aplica el conocimiento de la base de conocimientos sobre la base de hechos con el fin de obtener la solución buscada. Un mecanismo de inferencia debe ser independiente del conocimiento y de los hechos. Está caracterizado por:

• El lenguaje en que ha sido escrito.
• La velocidad de trabajo: Inferencias/segundo.
• Las estrategias de búsqueda de soluciones:

No Ordenada: aleatoria, heurística.

Ordenada: Encadenamiento hacia adelante (guiado por los datos, deductivo), encadenamiento hacia atrás (guiado por los objetivos, inductivo).

• La forma en que elige el conocimiento.
• La posibilidad de incorporar metaconocimiento.
• El tipo de lógica que emplea en el razonamiento:

Booleana, trivalente, multivalente, difusa.

Monotónica o no monotónica.

Atemporal o temporal.

Lógica de orden 0, orden 0+, orden 1.

• El método que utiliza para la evaluación del conocimiento incompleto o incierto:

Determinístico.

Probabilístico.

Aproximado.

Difuso.

RESOLUCION DE CONFLICTOS

Las técnicas de solución de problemas en IA, en general, incorporan un proceso de búsqueda. Todo proceso de búsqueda puede ser visualizado como el recorrido por un árbol en el que cada nodo representa un estado y cada rama representa las relaciones entre los estados cuyos nodos conecta.

En general, las reglas contienen en forma implícita el árbol, y se genera en forma explícita sólo aquellas partes que se decide explorar. Las principales diferencias que pueden aparecer en las diferentes técnicas de búsqueda, son:

• La dirección en la cual se conduce la búsqueda (hacia adelante o hacia atrás).
• La estrategia de control, o forma de seleccionar las reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.
• La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).

Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son:

• Cada vez que se genere un nodo se debe chequear para ver si ha sido generado antes.

• Se deben introducir procedimientos especiales para que la búsqueda no quede atrapada en algún lazo.

BUSQUEDAS

Búsqueda en anchura

Como su nombre indica, el recorrido realizado se lleva a cabo visitando todos los nodos de un nivel, de izquierda a derecha, pasando posteriormente al nivel siguiente, hasta que se encuentre el nodo objetivo, momento en el que se detiene el algoritmo. Lo vemos en el dibujo con el mismo ejemplo de antes, numerando los nodos con el orden que les corresponde según el recorrido en anchura.

En efecto, los nodos que con este algoritmo se visitan hasta encontrar el objetivo (8) son: 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8

Su complejidad tanto espacial como temporal es exponencial, y está en O (n^p), siendo n el número medio de sucesores, y p el nivel donde se alcanza la solución; por ello, esta estrategia es sólo aplicable a problemas no demasiado amplios.

Este procedimiento es completo, ya que encontrará siempre una solución si es que la hay, pero en general no es óptimo. Para implementarlo se ha hecho uso de una cola FIFO.

halla_objetivo_anchura (A: espacio_de_busquedas)

  { /* dev objetivo*/

     Cola lista_nodos;

     Boolean acabar = false;

     lista_nodos.encolar (A.nodo_raiz);

     while ((!lista_nodos.esVacia()) AND (!acabar)) do

     {

        nodo_actual = lista_nodos.primero(); 

        lista_nodos.quitaPrimero();

        if (esObjetivo (nodo_actual) ) then

           {

                acabar = true;

           }

        else

           {

                  nodo_actual.expandir(); //se añaden los hijos del nodo actual

                   lista_nodos.encolarMuchos (nodos_expandidos_de_nodo_actual);

           }

     }

     return nodo_actual;

  }

BUSQUEDAS DE PROFUNDIDAD

Supongamos que nuestro robot no tiene ninguna capacidad especial para poder moverse por la habitación de una manera eficiente (desconoce cualquier información útil para poder llegar al libro de la forma más corta): entonces deberá seguir un algoritmo de búsqueda no informada (“un método ciego”) para llegar hasta él. En general, este tipo de algoritmos recorre el espacio de estados de una forma concreta hasta dar con el objetivo (en este caso, el libro). Nuestro primer método se denomina búsqueda en profundidad.

Supongamos el árbol del dibujo representando un espacio de estados cualquiera. Vemos que, teniendo este árbol delante con sus nodos numerados, tenemos distintas formas de recorrerlo. ¿Cómo lo hacemos en profundidad? Siendo el 1 el nodo inicial y 7 el nodo objetivo que se debe alcanzar, hacemos lo siguiente: buscaremos en todas las ramas que cuelgan, de izquierda a derecha, y exploramos cada rama hasta llegar a una hoja. Para cada hijo buscamos a su vez en profundidad, parando cuando se encuentre el objetivo. En este ejemplo, la secuencia a seguir está indicada por el número de los nodos: 1-> 2-> 3-> 4-> 5-> 6-> 7.

Si el camino tiene longitud k y factor de ramificación r, la complejidad espacial del algoritmo está en O (kr). Su complejidad temporal depende tanto del factor de ramificación como de la profundidad de la solución. Siendo n el número medio de hijos expandidos, y si la solución se alcanza en el nivel p, la complejidad temporal está en O (n^p); es, por tanto, un coste exponencial.

Este algoritmo de búsqueda, además, no es completo, ya que si existe solución y se mete por una rama infinita puede que no termine nunca. Tampoco es óptimo, ya que puede encontrar la solución pero haciendo un recorrido mayor del necesario en general. Se ha usado una estructura pila LIFO para implementarlo.

halla_objetivo_profundidad (A: espacio_de_busquedas)

  { /* dev objetivo*/

     Pila lista_nodos;

     Boolean acabar = false;

     lista_nodos.apilar (A.nodo_raiz);

     while ((!lista_nodos.esVacia()) AND (!acabar)) do

     {

        nodo_actual = lista_nodos.cima(); 

        lista_nodos.desapila();

        if (esObjetivo (nodo_actual) ) then

           {

                acabar = true;

           }

        else

           {

                  nodo_actual.expandir(); //se añaden los hijos del nodo actual

                   lista_nodos.apilarMuchos (nodos_expandidos_de_nodo_actual);

           }

     }

     return nodo_actual;

 }