Representación del Conocimiento y Resolución de Problemas

1. Representación del Conocimiento

Parte estática: conocimiento del dominio donde se desarrolla el problema (operaciones o acciones del problema, predicados para consultar el estado del problema…).

Parte dinámica: datos del problema concreto a resolver (información sobre un estado particular del problema).

Un esquema de representación es una simplificación del problema real porque:

  • No es posible, ni posiblemente necesario, representar todos los detalles del problema real.
  • La resolución de un problema real requiere grandes volúmenes de información y habitualmente se trabaja con representaciones parciales.
  • Resulta complejo modelar la realidad y establecer con precisión todos los cambios que se producen en el mundo.

Tipos de Conocimiento

Descripción Declarativa

Conjunto de cláusulas que describen propiedades: CÓMO es algo (por ejemplo, lista de ingredientes necesarios para hacer un pastel).

  • El conocimiento se representa de forma independiente a su uso posterior.
  • Tipos de conocimiento declarativo: relacional, heredable, inferible.

Descripción Procedural o Procedimental

Conjunto de procedimientos que describen CÓMO hacer algo (por ejemplo, receta para hacer un pastel).

  • El conocimiento representado implica la inclusión de información sobre cómo usarlo.

Programación Lógica

Un programa lógico es un conjunto de cláusulas de Horn de dos tipos diferentes:

  • Hechos: on(blockA,blockB), on(blockB,blockD), road(cityA,cityB), gives(john,book,mary).
  • Reglas:
    • above(X,Y):- on(X,Z), above(Z,Y)
    • can_swin(Y):- type(X,animal), is-a(Y,X), lives_in(Y,water)

Objetivo (queries/preguntas sobre hechos): llamada a un programa lógico.

  • ?-above(blockA,blockD)
  • ?-above(blockA,X)
  • ?-road(cityA,X)

2. Representación Basada en Estados

La resolución de un problema consiste en encontrar una secuencia de estados que lleva a una solución.

Definición del Problema

  1. Representar el conjunto de posibles estados del problema.
  2. Especificar el estado inicial.
  3. Especificar el estado final o una función objetivo.
  4. Definir las reglas de transición u operadores del problema que permiten ‘pasar’ de un estado del problema a otro (acciones del problema).

Acción: transición que cuando se aplica en un estado s devuelve un nuevo estado como resultado de ejecutar la acción en s.

Espacio de estados: Conjunto de todos los estados alcanzables desde el estado inicial mediante la aplicación de una secuencia de acciones.

Objetivo: Encontrar la secuencia de operadores o acciones (solución), la cual aplicada al estado inicial alcanza el estado final u objetivo del problema. Esto se realiza mediante un proceso de búsqueda en un espacio de estados.

Entorno: observable (el agente conoce el estado actual), discreto (número finito de acciones), conocido (el agente conoce los estados que se alcanzan por la aplicación de una acción), determinista (existe un único resultado asociado a cada acción).

Formulación del Problema

Estado inicial: estado inicial del problema.

Acciones: acciones disponibles para el agente y que se pueden ejecutar en el problema.

Modelo de transición: Result(s,a) devuelve el estado resultante de aplicar la acción a en el estado s.

  1. El estado inicial, junto con las acciones y el modelo de transición definen implícitamente el espacio de estados.
  2. El espacio de estados forma un grafo dirigido.
  3. Los nodos representan los estados del problema, las aristas las acciones del problema.
  4. Un camino del espacio de estados es una secuencia de estados conectados a través de una secuencia de acciones.

Prueba objetivo: determina si un estado es un estado objetivo.

  • Definición explícita de un estado en particular como el estado objetivo, o
  • Definición explícita de un conjunto de estados finales, o
  • Definición de una función objetivo (test) que aplicada sobre un estado devuelve si éste es un estado objetivo.

Coste del camino: función que asigna un coste numérico a cada camino.

Estado:

  • Conjunto de hechos que representa una situación concreta del mundo (problema).
  • Un hecho es una tupla de elementos (constantes); un elemento puede representar:
    • Un objeto (o parte de un objeto) del problema.
    • Una relación entre objetos del problema, una propiedad/atributo de un objeto, el valor de un atributo de un objeto, etc.

Acción: (consta de dos partes)

  1. Precondiciones: representan las condiciones que se deben satisfacer en el estado para que la acción sea aplicable.
    • Las precondiciones pueden ser de dos tipos:
      • Un elemento que representa los estados potenciales sobre los que la acción se puede aplicar.
      • Opcionalmente, un query/consulta sobre las variables del estado.
  2. Efectos: representan el nuevo estado que resulta de la ejecución de la acción. Los efectos se expresan mediante un elemento que denota el estado resultante.

3. Componentes de un Sistema Basado en Reglas (SBR)

También llamados Sistemas de Producción, son sistemas que utilizan reglas como la base de la representación del conocimiento.

Objetivo: resolver problemas (como el de las jarras de agua) modelados como un SBR:

  1. Definir los estados del problema, incluyendo el estado inicial y final.
  2. Definir las acciones (reglas).
  3. Aplicar una estrategia de búsqueda para encontrar la solución.

Se componen de tres elementos:

  • Base de Reglas (BR): contiene reglas que representan cómo cambia el mundo (acciones del problema).
  • Base de Hechos (BH): contiene hechos que representan el estado del mundo (situaciones).
  • Motor de Inferencia: mecanismo de control de un SBR.

Base de Hechos

  • También llamada memoria de trabajo o base de datos.
  • Contiene hechos sobre el mundo (estados del problema), que pueden observarse directamente o deducirse a través de las reglas.
  • Contiene conocimiento temporal, conocimiento sobre uno o varios estados de la resolución del problema.
  • Se puede modificar mediante reglas (añadir hechos, eliminar hechos).

Base de Reglas

  • También llamada Base de Conocimiento.
  • Contiene reglas, cada regla representa un paso de la resolución del problema. Una regla es un conjunto de condiciones (precondiciones) junto con las operaciones a realizar si las condiciones se satisfacen (efectos).
  • Las reglas son conocimiento duradero (persistente) sobre el dominio.
  • Las reglas se utilizan para representar las acciones del problema (ej. jarras de agua).
  • Típicamente, una vez se han definido las reglas para un problema, éstas no se modifican, solo el experto del dominio puede modificarlas.

Motor de Inferencia

  • Procesa la información de la BH y BR.
  • Es el mecanismo de razonamiento, independiente del dominio, para SBR.
  • Selecciona una regla de la BR y la aplica.
  • Un motor de inferencia se caracteriza por:
    • El tipo de encadenamiento.
    • El proceso de unificación (pattern-matching).
    • El mecanismo de control para seleccionar y ejecutar reglas.
  • Dos tipos de motor de inferencia:
    • Encadenamiento hacia delante o razonamiento dirigido por los datos (las reglas unifican el antecedente e infieren el consecuente).
    • Encadenamiento hacia atrás o razonamiento dirigido por el objetivo (las reglas unifican el consecuente y prueban el antecedente).