IVAN DE JESUS VENTURA FLORES

INGENIERIA EN SISTEMAS COMPUTACIONALES

7 TETRAMESTRE

INTELIGENCIA ARTIFICIAL I

UNIDAD III

EN ESTA UNIDAD III VEREMOS LO QUE ES LA REPRESENTACION DEL CONOCIMIENTO Y LA RECUPERACION DE LA INFORMACION, EL CUAL VEREMOS LOS TIPOS DE CONOCIMIENTOS, LAS ESTRUCTURAS PARA ALMACENAR EL CONOCIMIENTO Y LOS METODOS.

TIPOS DE CONOCIMIENTOEl conocimiento es la capacidad de actuar, procesar e interpretar información para generar más conocimiento o dar solución a un determinado problema. El conocimiento puede ser interpretado y entendido por seres humanos e incluso por máquinas a través de agentes inteligentes, esto se logra mediante bases de conocimiento o conjuntos de entrenamiento e inferencia lógica.Lo científicos e investigadores definen de dos maneras el conocimiento: como una representación mental de la realidad y como la información que se puede transmitir de un ente a otro por vías no genéticas. Según estas definiciones y los métodos que se utilicen para construir o generar conocimiento, el conocimiento se divide en:Conocimiento Científico: Este es un pensamiento dinámico el cual utiliza métodos científicos, investigaciones, experimentación, para aproximarse a la realidad o dar solución a un determinado problema. Este utiliza modelos, métodos, procedimientos e información abstracta con el fin de determinar y explicar

porqué suceden las cosas. Todos los resultados que se adquiera del conocimiento científico es fundamentado en la realidad y en las investigaciones.Conocimiento Artístico: Es aquel que se utiliza para comunicar emociones, pensamientos, sentimientos, además de descubrir la belleza y sencillez de las cosas. El conocimiento artístico no se puede comunicar o transmitir, este es propio del individuo que lo posee y solo puede ser desarrollado por él.Conocimiento Revelado: Este conocimiento tiene dos formas: el conocimiento revelado por Dios, y el conocimiento revelado por nuestra conciencia. Este viene dado por una representación de fe, en el que cualquier individuo que desea conocer algo, lo conoce de forma oculta o misteriosa. Es más aplicado a la teología o identidades religiosas.Conocimiento Empírico: Es el conocimiento que se da por casualidad de la vida, es decir, al azar, permitiendo a los seres humanos conducirse en su vida y las diferentes actividades que desarrollan, les permite salir de la rutina. Este conocimiento es propio de las personas sin formación, pero que tienen conocimieto del mundo exterior, lo que les permite actuar y determinar acciones, hechos y respuestas casi por instinto, de aquí que su

fuente principal de conocimiento son los sentidos.El conocimiento se puede generar de varias maneras y aplicar de distintas formas. A partir de esta clasificación se han geneado otros tipos de conocimiento como: el demostrativo, intuitivo, sensible, dinámico, inteligible, y otros, La mayoría de estos están representados en la clasificación presentada. Sea cual sea el conocimiento, el fin es el mismo, y es desarrollar las capacidades de los seres humanos para aportar a la sociedad.

Base de conocimiento

Una Base de Conocimiento (o knowledgebase en inglés; KB, kb or Δ) es un tipo especial de base de datos para la gestión del conocimiento. Provee los medios para la recolección, organización y recuperación computarizada de conocimiento.

TiposLas bases de conocimiento se han clasificado en dos grandes tipos:

Bases de conocimiento leíbles por máquinas, diseñadas para almacenar conocimiento en una forma legible por el computador, usualmente con el fin de obtener razonamiento deductivo automático aplicado a ellas. Contienen una serie de datos, usualmente en la forma de reglas que describen el conocimiento de manera lógicamente consistente. Operadores lógicos como Y (conjunción), O (disyunción), condición lógica y negación son utilizada para aumentarla desde el conocimiento atómico. En consecuencia la deducción clásica puede ser utilizada para razonar sobre el conocimiento en la base de conocimiento. Este tipo de bases de conocimiento son utilizadas por la Web semántica

Bases de conocimiento leíbles por Humanos están diseñadas para permitir a las personas acceder al conocimiento que ellas contienen, principalmente para propósitos de aprendizaje. Estas son comúnmente usadas para obtener y manejar conocimiento explicito de las organizaciones, incluyen artículos, white papers, manuales de usuario y otros. El principal beneficio que proveen las bases de conocimiento es proporcionar medios de descubrir soluciones a problemas ya

resueltos, los cuales podrían ser aplicados como base a otros problemas dentro o fuera del mismo área de conocimiento.

El más importante aspecto de una base de conocimiento es la calidad de la información que esta contiene. Las Mejores Bases de Conocimiento tienen artículos cuidadosamente redactados que se mantiene al día, un excelente sistema de recuperación de información (Motor de Búsqueda), y un delicado formato de contenido y estructura de clasificación. Una Base de Conocimiento puede usar una ontología para especificar su estructura(tipos de entidades y relaciones) y su esquema de clasificación. Una ontología, junto con un grupo de instancias de sus clases constituyen una Base de Conocimiento.Determinando qué tipo de información es capturada, y dónde se encuentra la información en una base de conocimiento es algo que es determinado por los procesos que respaldan al sistema. Una estructura robusta de procesos es la columna vertebral de cualquier Base de Conocimiento. Algunas Bases de Conocimiento tienen un componente de inteligencia artificial. Este tipo de Bases de Conocimiento pueden sugerir soluciones a problemas esporádicos en la retroalimentación por el usuario, y son capaces de aprender de la experiencia

(sistemas expertos). Representación de Conocimiento, Razonamiento automatizado y argumentación son las áreas activas de la investigación de la inteligencia artificial. Ejemplos de instalacionesLa Escuela de Medicina de Tufts University ha creado una infraestructura de software llamada the Tufts University Sciences Knowledgebase, TUSK. Sirve como base de conocimiento de información curricular para las escuelas de ciencias de la salud en Tufts (médica, dental, veterinaria, salud pública, nutrición, ciencias biomédicas). Esta infraestructura es compartida con tres escuelas de medicina en los Estados Unidos, tres en África y próximamente una en la India. La infraestructura permite a las instituciones crear un base de conocimiento al servicio de las necesidades locales

Minsky, M. 1977. Marco de la teoría. En PN Johnson-Laird y PCWason, pensando: Reasings en Ciencia Cognitiva, Cambridge: Cambridge University Press, pp 355-376. Abstracto Como dice el autor: "He aquí la esencia de la teoría de los marcos: Cuando uno se encuentra

con una situación nueva (o hace un cambio sustancial en la propia visión de un problema), se selecciona de la memoria de una estructura llamada un marco. Se trata de un marco acordado de ser adaptadas a la realidad cambiando detalles como sea necesario. "Un marco es la estructura de datos para representar la situación estereotipados (por ejemplo, estar en el cierto tipo de sala de estar). Cualquier marco está conectado con algún tipo de información (por ejemplo acerca de cómo usar el marco, lo que va a ser la próxima, etc,). El marco puede ser imaginado como una red de nodos y relaciones. Niveles más altos de este marco fijo y representar a la siempre son verdad acerca de la situación supone (personalmente creo que se dice no siempre, pero con la mayor probabilidad de comparar cualquier otro conocimiento sobre la situación de supuesto) y los niveles más bajos tienen muchas terminales - "slots", que debe estar llena de casos específicos o de datos. Cada terminal puede especificar las condiciones de sus asignaciones deben cumplir. Como dice el autor: "(...) las colecciones de cuadros relacionados están vinculados a los sistemas de chasis. Los efectos de las acciones importantes se reflejan en las transformaciones entre los marcos de un sistema. Estos se utilizan para hacer ciertos tipos de cálculos económicos,

para representar los cambios de énfasis y atención, y "de efectividad de la imaginaria. Por ejemplo para el análisis de la escena visual, la misma escena vista desde diferentes perspectivas está representado por cuadros diferentes que sin embargo están conectados con las relaciones de lo anterior, las transformaciones relevantes (en caso de no clases visuales de los marcos de un sistema de diferencias entre los marcos pueden representar a particulares acciones, la relación causa-efecto o los cambios en el punto de vista conceptual). Autor subrayar que el punto crucial que hace posible la coordinación de la información obtenida de diferentes puntos de vista es que los diferentes marcos de la acción del sistema los mismos terminales. Punto fuerte de la teoría de Minsky es que toma en cuenta las expectativas diferentes y las presunciones diferentes. Un marco de terminales están normalmente ya está lleno de tareas por defecto. Por lo tanto un marco de m ay contener muchos detalles cuya suposición no está especialmente justificada por la situación. Estos tienen muchos problemas en la representación de la información general, casos más probables, las técnicas para pasar por la lógica y hacer generalizaciones útiles. Estas asignaciones por omisión no están fuertemente

relacionados con el marco de sujetos (sus terminales), que puede entenderse como "variables" que se describe más bien la situación particular de que la "corriente principal" del marco. Por encima de la presunción principal de la teoría de los marcos se verifican más adelante en el artículo en casos particulares. La forma en cómo se adquiere el conocimiento, representados y organizados para el cálculo futuro de acuerdo a la ciencia cognitiva está fuertemente asociada con los conceptos presentados en el documento de Minsky. Comentario: Los fenómenos de las ciencias cognitivas y su popularidad se va hasta que avanzó la frontera, donde el debate científico no se inicia sobre el ser humano. Por el debate científico no me refiero a la discusión en el que la distancia entre la presunción empírica verificada y la conclusión filosófica está muy lejos. Las ciencias cognitivas han hecho la diferencia más corta en muchos campos, oh nuestro conocimiento sobre los seres humanos, sobre nosotros mismos (sobre la cognición). Especialmente en el terreno de los dos principales pilares de las ciencias cognitivas, la IA y la psicología, muchos autores han publicado sus artículos revolucionarios en pedazos más y más grande de conocimiento

estricto, computables o computable casi determinista (en forma probabilística) y la causalidad sobre las capacidades de la mente han han presentado. Además, muchas de estas hipótesis se verifican desde el punto de vista empírico (psicología) y muchos otros desde el punto de vista biológico (neurociencias). Grandes manchas de ese conocimiento ha aparecido después de 1956 famosos. Uno de estos artículos importantes fue la que presentó en 1977 por Marvin Minsky "el Papa de la gripe aviar". El autor describe la teoría de los marcos, lo que explica el mecanismo de adquisición de conocimientos y su representación en forma que permita su transformación potencial computable dar los mismos efectos que en la mente inteligente. Las redes semánticas

La idea detrás de una red semántica es que el conocimiento muchas veces es mejor entendida como un conjunto de conceptos que están relacionados entre sí.

El significado de un concepto se define por su relación con otros conceptos.

Una red semántica consiste en un conjunto de nodos que están conectados por arcos etiquetados. Los nodos representan

conceptos y los arcos representan las relaciones entre conceptos.

Común de relaciones semánticas No hay un conjunto estándar de las relaciones de las redes semánticas, pero las siguientes relaciones son muy comunes: Ejemplo: X es una instancia de Y si X es un ejemplo específico del concepto general Y. Ejemplo: Elvis es un ejemplo de los Derechos Humanos ISA: X ISA Y si X es un subconjunto del concepto más general Y. Ejemplo: gorrión ISA aves HasPart: X hasPart Y si el concepto Y es una parte de la X. concepto (o puede ser cualquier otra propiedad) Ejemplo: gorrión hasPart cola Herencia

La herencia es un concepto clave en las redes semánticas y se pueden representar de forma natural por los siguientes enlaces ISA.

En general, si X concepto tiene la propiedad P, entonces todos los conceptos que son un

subconjunto de X también debe tener la propiedad P.

Pero las excepciones son omnipresentes en el mundo real!

En la práctica, las propiedades heredadas suelen ser tratados como valores por defecto. Si un nodo tiene un enlace directo que contradice una propiedad heredada, el valor por defecto se reemplaza.

Herencia múltiple La herencia múltiple permite que un objeto

que herede las propiedades de múltiples conceptos.

La herencia múltiple a veces puede permitir que un objeto que herede las propiedades en conflicto.

Los conflictos son potencialmente inevitables, por lo que las estrategias de resolución de conflictos son necesarios.

En representación de los predicados

puntuación (Mavs, los Bulls, 120-101) Juego Ejemplo: Game17 hometeam: Mavs Del equipo visitante: Toros Puntuación: 120-121 En representación de las relaciones Karl John la altura de la altura Height1 mayor que altura2

Marcos Un fotograma representa una entidad como

un conjunto de slots (atributos) y los valores asociados.

Cada ranura puede tener limitaciones que describen los valores jurídicos que la ranura se pueden tomar.

Un cuadro puede representar una entidad específica, o un concepto general.

Los marcos están implícitamente asociadas entre sí porque el valor de una ranura puede ser otro marco.

Demonios Una de las principales ventajas de los

marcos es la posibilidad de incluir los demonios para calcular los valores de la ranura. Un demonio es una función que calcula el valor de una ranura en la demanda.

Características de las Representaciones del marco

Los marcos pueden apoyar los valores más natural que las redes semánticas (por ejemplo, el valor de 25)

Los marcos pueden ser fácilmente implementados usando técnicas orientadas a objetos de programación.

Demonios permiten funciones arbitrarias para ser embebido en una representación.

Pero se paga un precio en términos de eficiencia, la generalidad, y la modularidad!

La herencia puede ser fácilmente controlada.

Temas comparativos en la Representación del Conocimiento

La semántica detrás de un modelo de representación del conocimiento depende de la forma en que se utiliza (implementado). Notación es irrelevante!

Si una declaración escrita en la lógica o como una red semántica no es importante - lo que importa es si el conocimiento se utiliza de la misma manera.

La mayoría de los modelos de representación del conocimiento se puede hacer para ser funcionalmente equivalentes. Es un ejercicio útil para tratar de convertir el conocimiento en una forma a otra forma.

Desde una perspectiva práctica, la consideración más importante por lo general es si el modelo KR permite el conocimiento para ser codificados y manipulados de una manera natural.

La expresividad de redes semánticas Algunos tipos de propiedades que no se

expresan fácilmente utilizando una red semántica. Por ejemplo: la negación, disyunción, y el conocimiento general y no taxonómica.

Hay formas especializadas de hacer frente a estas relaciones, por ejemplo, particiones de redes semánticas y el apego de

procedimiento. Sin embargo, estos enfoques son feas y no se usa comúnmente.

La negación puede ser manejado por haber predicados complementarios (por ejemplo, A y no A) y el uso de procedimientos especiales para verificarlas. También es muy feo, pero fácil de hacer.

Si la falta de expresividad es aceptable, redes semánticas tienen varias ventajas: la herencia es natural y modular, y redes semánticas pueden ser muy eficientes.

Herencia Como mencionamos anteriormente, las

redes semánticas y los marcos se utilizan a menudo porque la herencia se representa de forma tan natural.

Pero los sistemas basados en reglas también se puede utilizar para hacer

herencia! ¿Cómo? Las redes semánticas (y cuadros) tienen una

ventaja de aplicación por la herencia, porque los algoritmos de propósito especial se puede utilizar para seguir los enlaces ISA.

Resumen comparativo

Las reglas son apropiados para algunos tipos de conocimiento, pero no fácilmente mapa a los demás.

Redes semánticas pueden representar a la herencia y las excepciones, pero no son muy adecuados para la representación de la negación, disyunción, preferencias, condicionales y las relaciones de causa / efecto.

Marcos permiten funciones arbitrarias (demonios) y la herencia escrita. La implementación es un poco más engorroso.

Y justo cuando pensaba que era seguro salir ... cont. Networks. (Implementación) . Definición de información.La información es todo aquello que puede ser manejado por un sistema, ya sea como entrada, como proceso, o bien como resultado. De esta forma, podemos clasificar a los sistemas informáticos como sistemas de flujo de información (si la información de entrada y salida es la misma) y sistemas de tratamiento de la información, en los que la información que entra y la que sale es distinta, ya que ha sufrido alguna manipulación.La información, para que sea útil a nuestro ordenador debe estar representada por símbolos. Tales símbolos por si solos no

constituyen la información, sino que la representan.La información se puede clasificar como:

Datos numéricos, generalmente números del 1 al 9

Datos alfabéticos, compuestos solo por letras

Datos alfanuméricos, combinación de los dos anteriores

Sistemas de NumeraciónLos sistemas de numeración son las distintas formas de representar la información numérica. Se nombran haciendo referencia a la base, que representa el número de dígitos diferentes para representar todos los números.El sistema habitual de numeración para las personas es el Decimal, cuya base es diez y corresponde a los distintos dedos de la mano, mientras que el método habitualmente por los sistemas electrónicos digitales es el Binario que utiliza únicamente dos cifras para representar la información, el 0 y el 1.Otros sistemas como el Octal (base 8) y el Hexadecimal (base 16) son utilizados en las computadoras.

 Sistema BinarioLos circuitos digitales internos que componen las computadoras utilizan el sistema de numeración Binario para la interpretación de la información, por tal motivo será el que desarrollaremos en mayor detalle a continuación.Como mencionamos anteriormente este sistema utiliza dos cifras (el 0 y el 1) en dónde cada una de ellas se denomina bit (contracción de binary digit).Para medir la cantidad de información representada en binario se utilizan múltiplos que a diferencia de otras magnitudes físicas utilizan el factor multiplicador 1024 en lugar de 1000, debido a que es el múltiplo de 2 más cercano a este último (210=1024).

Múltiplo R e p r e s e n t aNibble Conjunto de 4

bits1001

Byte Conjunto de 8 bits

10101010

Kilobyte (Kb) Conjunto de 1024 bytes

1024 * 8 bits

Megabyte (Mb) Conjunto de 10242 * 8 bits

1024 KbGigabyte (Gb) Conjunto de

1024 Mb10243 * 8 bits

Terayte (Tb) Conjunto de 1024 Gb

10244 * 8 bits

El byte es la unidad básica de medida de la información representada mediante este sistema. Operaciones con Números BinariosAntes de ver las operaciones básicas de suma, resta, producto y cociente necesitamos conocer como se representa un número decimal en binario y viceversa.Ejemplo: Decimal a Binario.

Para obtener de un número decimal su representación en el sistema binario, debemos dividir el primero por 2 siendo el resto de cada una de las divisiones leído de derecha a izquierda los que compondrán el número binario.Ejemplo: Binario a Decimal.

Para transformar un número representado como binario en decimal multiplicamos cada cifra del binario por 2 elevado a una potencia que ira disminuyendo hasta llegar a cero. Para determinar la primer potencia contamos las cifras del binario (5 en este caso) y disminuimos dicho número en 1 unidad (4 en el ejemplo).Suma de Números BinariosEs similar a la suma decimal excepto que se manejan sólo dos dígitos (0 y 1).Las sumas básicas son:

0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 (número 2 en binario)

Ejemplo: 100110101 + 11010101 =

Se comienza a sumar desde la izquierda, en el ejemplo, 1 + 1 = 10, entonces escribimos 0 y "llevamos" 1. Se suma este 1 a la siguiente columna: 1 + 0 + 0 = 1, y seguimos hasta terminar todas la columnas (exactamente como en decimal).Resta de Números BinariosEs semejante a la decimal excepto que se utilizan dos dígitos y teniendo en cuenta que se realizan las restas parciales entre dos dígitos de idénticas posiciones, uno del minuendo y otro del sustraendo, si el segundo excede al primero, se sustrae una unidad del dígito de más a la izquierda en el minuendo (si existe y vale 1), convirtiéndose este último en 0 y equivaliendo la unidad extraída a 1 * 2 en el minuendo de resta parcial que estamos realizando. Si es 0 el dígito siguiente a la izquierda, se busca en los sucesivos teniendo en cuenta que su valor se multiplica por 2 a cada desplazamiento a la derecha.

Las restas básicas son:0 - 0 = 00 - 1 = No se puede realizar.1 - 0 = 11 - 1 = 0Ejemplo: 11001 – 1010 =

Producto de Números BinariosEl producto de números binarios es semejante al decimal, ya que el 0 multiplicado por cualquier otro da 0, y el 1 es el elemento neutro del producto.Los productos básicos son:0 * 0 = 00 * 1 = 01 * 0 = 01 * 1 = 1

Ejemplo: 10110 * 1001 =

Cociente de Números BinariosLa división se realiza en forma semejante al decimal, con la salvedad que las multiplicaciones y restas internas del proceso de la división se realizan en binario.Ejemplo: 100010 / 110 =

Representación de Números EnterosAritmética de computadoresLos computadores no almacenan los números con precisión infinita sino de forma aproximada empleando un número fijo de bits o bytes

(grupos de ocho bits). Prácticamente todos las computadoras permiten al programador elegir entre varias representaciones o 'tipos de datos'. Los diferentes tipos de datos pueden diferir en el número de bits empleados, pero también (lo que es más importante) en cómo el número representado es almacenado: en formato fijo (también denominado 'entero') o en punto flotante (denominado 'real').Aritmética de punto fijoUn entero se puede representar empleando todos los bits de una palabra de computadora, con la salvedad de que se debe reservar un bit para el signo. Por ejemplo, en una máquina con longitud de palabra de 32 bits, los enteros están comprendidos entre -(231 - 1) y 231 - 1 = 2147483647. Un número representado en formato entero es 'exacto'. Las operaciones aritméticas entre números enteros son también 'exactas' siempre y cuando:

1.2.La solución no esté fuera del rango del

número entero más grande o más pequeño que se puede representar (generalmente con signo). En estos casos se dice que se comete un error de desbordamiento por exceso o por defecto (en inglés: Overflow y Underflow) y es necesario recurrir a técnicas

de escalado para llevar a cabo las operaciones.

3.La división se interpreta que da lugar a un número entero, despreciando cualquier resto.

Por estos motivos, la aritmética de punto fijo se emplea muy raramente en cálculos no triviales. Notación Científica NormalizadaEn el sistema decimal, cualquier número real puede expresarse mediante la denominada Notación científica normalizada. Para expresar un número en notación científica normalizada multiplicamos o dividimos por 10 tantas veces como sea necesario para que todos los dígitos aparezcan a la derecha del punto decimal y de modo que el primer dígito después del punto no sea cero. Por ejemplo:Para ver la fórmula seleccione la opción "Descargar" del menú superiorEn general, un número real x distinto de cero, se representa en notación científica normalizada en la forma: Para ver la fórmula seleccione la opción "Descargar" del menú superior

Exactamente del mismo modo podemos utilizar la notación científica en el sistema binario. En este caso, tenemos que: Para ver la fórmula seleccione la opción "Descargar" del menú superior

Donde m es un entero. El número q se denomina mantisa y el entero m exponente. En un ordenador binario tanto q como m estarán representados como números en base 2. Puesto que la mantisa q está normalizada, en la representación binaria empleada se cumplirá que: Para ver la fórmula seleccione la opción "Descargar" del menú superior

Representación de los números en punto flotanteEn un ordenador típico los números en punto flotante se representan de la manera descrita en el apartado anterior, pero con ciertas restricciones sobre el número de dígitos de q y m impuestas por la longitud de palabra disponible (es decir, el número de bits que se van a emplear para almacenar un número). Para

ilustrar este punto, consideraremos un ordenador hipotético que denominaremos MARC-32 y que dispone de una longitud de palabra de 32 bits (muy similar a la de muchos ordenadores actuales). Para representar un número en punto flotante en el MARC-32, los bits se acomodan del siguiente modo: Signo del número real x:

1 bit

Signo del exponente m:

1 bit

Exponente (entero |m|):

7 bits

Mantisa (número real |q|):

23 bits

 En la mayoría de los cálculos en punto flotante las mantisas se normalizan, es decir, se toman de forma que el bit más significativo (el primer bit) sea siempre '1'. Por lo tanto, la mantisa q cumple siempre la ecuación (3).Dado que la mantisa siempre se representa normalizada, el primer bit en q es siempre 1, por lo que no es necesario almacenarlo proporcionando un bit significativo adicional. Esta forma de almacenar un número en punto flotante se conoce con el nombre de técnica del 'bit fantasma'.

Se dice que un número real expresado como aparece en la ecuación (2) y que satisface la ecuación (3) tiene la forma de punto flotante normalizado. Si además puede representarse exactamente con |m| ocupando 7 bits y |q| ocupando 24 bits, entonces es un número de máquina en el MARC-32.La restricción de que |m| no requiera más de 7 bits significa que: Para ver la fórmula seleccione la opción "Descargar" del menú superiorPor ejemplo: 0.5 representado en punto flotante en el MARC-32 (longitud de palabra de 32 bits) se almacena en la memoria del siguiente modo: Para ver la fórmula seleccione la opción "Descargar" del menú superiorSolución: El número 26.32 en binario se escribe del siguiente modo: Para ver la fórmula seleccione la opción "Descargar" del menú superiorSi expresamos el error como la diferencia entre el valor y el número realmente almacenado en el ordenador, obtenemos:

 Para ver la fórmula seleccione la opción "Descargar" del menú superiorAntes de entrar con detalle en la aritmética de los números en punto flotante, es interesante notar una propiedad de estos números de especial importancia en los cálculos numéricos y que hace referencia a su densidad en la línea real. Supongamos que p, el número de bits de la mantisa, sea 24. Para ver la fórmula seleccione la opción "Descargar" del menú superior

Razonamiento = Motor de inferenciaB Dos maneras de razonar:u Hacia adelante (forward chaining)u Hacia atr´as (backward chaining)

B RAZONAMIENTO HACIA DELANTE:

u A partir de los hechos, buscar las conclusionesu Desde los datos hacia los objetivos

B RAZONAMIENTO HACIA ATR´AS:

u Dadas las conclusiones que se buscan, buscar los

hechos que las derivanu Desde los objetivos hacia los datosIIC 2006–07 CcIa Representaci´on del conocimiento mediante reglas 4.14Razonamiento hacia atr´asB Meta-int´erpretesB Programa Prolog:se_deduce(P) :-_ hecho P.se_deduce(P) :-_ # si C entonces P,se_deduce(C).se_deduce(P1 y P2) :-se_deduce(P1),se_deduce(P2).se_deduce(P1 o _) :-se_deduce(P1).se_deduce(_ o P2) :-se_deduce(P2).B Ejemplo:?- se_deduce(fuga_en_cocina).Yes?- se_deduce(fuga_en_bagno).NoIIC 2006–07 CcIa Representaci´on del conocimiento mediante reglas 4.15Razonamiento hacia adelanteB Programa Prolog::- dynamic hecho_deducido/1.adelante :-nuevo_hecho_deducido(P),

!,write(’Deducido: ’), write(P), nl,assert(hecho_deducido(P)),adelante;write(’No hay m´as hechos’).nuevo_hecho_deducido(P) :-_ # si Condicion entonces P,not(hecho_deducido(P)),hecho_compuesto(Condicion).hecho_compuesto(C) :-hecho_deducido(C).hecho_compuesto(C) :-_ hecho C.hecho_compuesto(C1 y C2) :-hecho_compuesto(C1),hecho_compuesto(C2).hecho_compuesto(C1 o C2) :-hecho_compuesto(C1);hecho_compuesto(C2).IIC 2006–07 CcIa Representaci´on del conocimiento mediante reglas 4.16Razonamiento hacia adelanteB Ejemplo:?- adelante.Deducido: problema_en_cocinaDeducido: no_agua_exteriorDeducido: fuga_en_cocinaNo hay m´as hechosYes

?- listing(hecho_deducido).hecho_deducido(problema_en_cocina).hecho_deducido(no_agua_exterior).hecho_deducido(fuga_en_cocina).Yes?- listing(hecho).f1 hecho recibidor_mojado.f2 hecho bagno_seco.f3 hecho ventana_cerrada.YesIIC 2006–07 CcIa Representaci´on del conocimiento mediante reglas 4.17Hacia adelante vs hacia atr´asB Deducci´on = b´usqueda en espacios de estados:Datos --> .... --> ObjetivosEvidencias --> .... --> Hip´otesisObservaciones --> .... --> JustificacionesS´ıntomas --> ... --> Diagn´osticoB La direcci´on de la b´usqueda determina el tipode razonamiento:u Hacia adelante: de los hechos hacia las conclusionesu Hacia atr´as: de los objetivos hacia los hechosB Problemas adecuados para razonar hacia adelante:u Monitorizaci

B´usqueda en Espacios de Estados2.1 Concepto de Espacio de estados.Espacio de Estados: Formalimo para representar problemas.ideas clave:Abstraer problemas reduci´endolos a un conjunto de estados y operadores.Resolver problema revisando posibles alternativas (¿todas?).• analog´ıa con forma de actuar humanosEstado:• Representaci´on completa de la situaci´on del mundo/problema enun momento dado• Contiene toda la info. relevante (y nada m´as)Operador:• Se suponen deterministas_ se sabe de antemano c´omo ser´a el estado del mundo/problemadespues de aplicarlos• Se suponen discretos_ no es relvante lo que “pasa” mientras se ejecutan– c FJRP 2004 ccia ia – 12.1.1 Caracterizaci´on de un ProblemaPROBLEMA = Terna de 3 componentes (I,O,M)1. Estado/s inicial (I):Descripci´on de la situaci´on de partida

2. Conjunto de operadores pertinentes (O):Descripci´on de los medios de los que disponemos para lograr elfin deseadoAcciones que se pueden emprender, dado un estado, para alcanzarotro distino.Tienen 2 componentes:• precondiciones: condici´on que debe cumplir un estado para quepueda aplicarse el operador sobre ´el.• postcondiciones: descripci´on de las caracter´ısticas del nuevoestado al que se transita.Pueden ser interpretados como reglas”: (patr´on + acci´on)3. Conjunto de estados meta (M):Estados del problema que satisfacen los requisitos para ser consideradoscomo soluciones.Pueden expresarse en forma de lista de estados ´o como una funci´on booleana (prueba de meta) que bas´andose en las propiedadesde un estado indica si es meta o no.(I) y (O) determinan el espacio de estados del problema.• Conjunto de todos los posibles estados admisibles del problema.B´USQUEDA DE SOLUCIONES

soluci´on: Secuencia ordenada de operadores (S 2 O_) que posibilitatransito desde estados iniciales (I) a finales (O).Conseguir un ”plan de acci´on”que permita pasar de (I) a (M)Objetivo: Encontrar la ”mejor”soluci´on (o una aceptable)– c FJRP 2004 ccia ia – 2ESTRATEGIAS DE B´USQUEDATambi´en estrategias de control o ”mecanismo de inferencia”Secuencia de pasos a seguir para encontrar el conjunto de operadoresdeseado.• Estrategia es independiente del conocimiento.• Estrategia debe de ser:_ sistem´atica y f´acilmente reproducible_ producir movimientos v´alidos en el espacio de estados_ producir nuevos estados (para poder avanzar)• Necesidad de estructuras adicionales._ indicar cu´ando es aplicable un operador_ indicar cu´ando se ha utilizado un operador_ indicar cu´ando un operador produce un estado final_ indicar cu´ando un operador produce un estado no nuevo_ indicar si la soluci´on es aceptableEJEMPLO: Representaci´on de problemasProblema de las 2 jarras– c FJRP 2004 ccia ia – 3

2.1.2 Caracter´ısticas Generales Procesos de B´usqueda1. Direcci´on del proceso de b´usqueda: (2 opciones)a) I −! M: de estados iniciales a finalesdatos −! objetivosproceso dirigido por los datos (progresivo)razonamiento hacia adelanteb) I − M: de estados finales a inicialeship´otesis de trabajo −! datosproceso dirigido por los objetivos (evocativo)razonamiento hacia atr´asnota: necesidad definici´on operadores inversos (si es posible)Tambi´en es posible realizare b´usquedas bidireccionales.Criterios de Selecci´on:Tama˜no relativo de conjuntos I y M.• avazar de menos a m´as estadosFactor de ramificaci´on• def.: Promedio de estados que podemos alcanzar directamentedesde un estado previo.• avanzar en la direcci´on con menor factor ramificaci´onJustificaci´on del razonamiento/soluci´on• Si se exige justificaci´on del resultado ! usar misma direcci´onque usar´ıa experto humano• Criterio m´as importante en sistemas pr´acticos.

– c FJRP 2004 ccia ia – 42. Topolog´ıa del Proceso de B´usquedaDependiendo de la estructura que definan los operadores elespacio de estados puede ser:• Un ´arbol:_ m´as sencillo de manejar_ mayor consumo memoria (estados duplicados, etc)• Un grafo (con o sin ciclos):_ ahorro de memoria_ generaci´on m´as compleja (comprobar existencia de estados)Se ir´an construyendo a medida que el proceso de b´usqueda avanzaEjemplos: Problema 2 jarras3. Representaci´on del ProblemaTres aspectos a decidir (de cara a la implementaci´on)• Representaci´on de los hechos, objetos y entidades que relevantesen el dominio considerado! Representaci´on de Estados• Representaci´on de las relaciones entre hechos, objetos y entidadesrelevantes! Representaci´on de Operadores• Representaci´on de las secuencias de estados surgidas durantela b´usqueda! Representaci´on de Estrategias

8>>< >>:Modulo Represent. del Conocimientorepresentaci´on estadosrepresentaci´on operadores9>>=>>;+8>><>>:Modulo de Control del Sistemarepresentaci´on estrategias9>>=>>;– c FJRP 2004 ccia ia – 54. Criterios de Selecci´on de Operadores Relevantesa) Proceso de emparejamiento: decidir que operadores son aplicablessobre un estado dado.Determinar operadores cuyas precondiciones sean compatiblescon caracter´ısticas del estado consideradoProblema de correspondencia de patrones complejo• pueden incluirse variablesPrincipal causa de la ”lentitud”de los sistemas de I.A.b) Resoluci´on de conflictos de operadores.def.: Conjunto Conflicto: Conjunto de operadores aplicablesresultantes del proceso de emparejamiento.

Resoluci´on de conflictos: elecci´on del operador/es a aplicar! depende de/determina la estrategia de b´usquedaPosibilidades:• aplicar todos los operadores disponibles• aplicar s´olo los operadores a´un no utilizados• aplicar s´olo operadores que emparejen con estados incorporadosrecientemente• aplicar el operador m´as espec´ıfico (retrasar uso de los +generales)• aplicar un operador aleatorio– c FJRP 2004 ccia ia – 65. Optimizaci´on de B´usqueda con Funciones Heur´ısticasUso de funciones (num´ericas) que indican lo buena o mala quela elecci´on de un nuevo operador.Finalidad: ”dirigir”el proceso de b´usquedaSe basan en conocimiento heur´ıstico, espec´ıfico del problema,derivado de la experiencia, dif´ıcil de formalizar y explicar.Estrategias ciegas:• No usan info heur´ıstica• Aplicables en cualquier dominio• En general, menos eficientes (explosi´on combinatoria)• Ejemplos:

_ generar y comprobar_ b´usqueda en anchura_ b´usqueda en profundidad (prof. acotada y prof. iterativa)Estrategias heur´ısticas ´o informadas:• Usan informaci´on heur´ıstica espec´ıfica del dominio.• Dise˜nados para problemas concretos• Limitan explosi´on combinatoria• No aseguran soluciones ´optimas (si ”aceptables”)• Elemplos:_ ascenso a colinas_ mejor nodo_ A_ y variantes– c FJRP 2004 ccia ia – 76. Criterios de Evaluaci´oncompletitud : ¿Se garantiza o no que se va a encontrar unasoluci´on?optimalidad : En caso de que existan varias soluciones, ¿seencuentra la mejor (´optima) o no?complejidad :• espacial : memoria necesaria para efectuar la b´usqueda• temporal : tiempo necesario para efectuar la b´usqueda• Estimaciones en el peor de los casos• Especificadas en funci´on de alg´un parametro del problema,

notaci´on O().– c FJRP 2004 ccia ia – 82.2 B´usqueda No Informada2.2.1 Generar y Comprobar1. Generar caminos al azar, partiendo del estado inicial hasta agotarlos2. Comprobar si son soluci´onPoco ´util en la pr´acticaAplicable si• espacio de estados en muy peque˜no• hay muchos estados objetivo! es posible encontrar alguno al azar2.2.2 B´usqueda en Anchura(a) FUNCIONAMIENTORecorrer ´arbol/grafo de b´usqueda en anchura• expandir estado ra´ız• expandir todos sus sucesores• expandir todos los sucesores de los sucesores .....Realiza un ordenamiento de los estados a estudiar en base a suprofundidad• todos los nodos de profundidad d se estudir´an antes que cualquiernodo a profundidad d + 1– c FJRP 2004 ccia ia – 9(b) ALGORITMOabiertos: Lista ordenada de nodos generados a´un no expandidos (nose han generado sus sucesores)

! almacena nodos ”frontera”, en espera de ser expandidosa˜nadir estado inicial a abiertosresuelto := falsewhile (abiertos no vacio and no resuelto) doactual := primer nodo de abiertosif actual es estado final thenresuelto := trueelse/* expandir actual */for all (operador aplicable a actual) dogenerar nuevo estado aplicando operadora˜nadir nuevo estado al final de abiertosend forend ifend whileabiertos: Funciona como una cola (fifo)! mayor profundidad al final de la lista– c FJRP 2004 ccia ia – 10MEJORA: En espacios de estados con estructura de grafo evitarexaminar un estado en m´ultiples ocasionesLista cerrados: Almacena estados ya examinadosExpandir s´olo estados que no parezcan en abiertos (ya generados)ni en cerrados (ya examinados)Tipos de estados8>><>>:

No generados: no aparecen en abiertos ni en cerradosGenerados no Examinados: en abiertosExaminados no Expandidos: el estado actualExaminados: en cerradosa˜nadir estado inicial a abiertosinicializar cerrados a vacioresuelto := falsewhile (abiertos no vacio and no resuelto) doactual := primer nodo de abiertosif actual es estado final thenresuelto := trueelsea˜nadir actual a cerrados/* expandir actual */for all (operador aplicable a actual) dogenerar nuevo estado aplicando operadorif (nuevo estado no en abiertos ni en cerrados) thena˜nadir nuevo estado al final de abiertosend ifend forend ifend whileIncrementa el coste computacionalgesti´on de las listascomprobaci´on pertenencia (inspeccionar abiertos y cerrados)– c FJRP 2004 ccia ia – 11(c) CARACTER´ISTICAS B´USQUEDA EN ANCHURA

Es completa: Garantiza que se encuentra la soluci´on• si ´esta existe• si el espacio de b´usqueda es finito (sin ciclos)Es ´optima: Siempre encuentra la soluci´on m´as corta• Se asegura que la soluci´on encontrada es la de menor profundidad• nota: Si los operadores tienen asociado un coste, la soluci´onmenos profunda puede no ser la menos costosa.Complejidad• Dos factores_ b, factor de ramificaci´on: no promedio de estados generadosdesde un estado dado_ p, profundidad estado objetivo: no m´ınimo de operadores necesariospara alcanzar la soluci´on encontrada• Complejidad espacial: O(bp)• Complejidad temporal: O(bp)• En el peor de los casos examina todos los nodos posible• Complejidad exponencial: se saca 1 de abiertos y se a˜naden bde mediaMuy ineficaz (explosi´on combinatoria), sobre todo en requisitos deespacio.– c FJRP 2004 ccia ia – 122.2.3 B´usqueda en Profundidad

(a) FUNCIONAMIENTOExpandir un camino hasta llegar al finalSi no es soluci´on y no tiene expansi´on posible, volver a un nodo noexpandido del nivel anteriorMenor exigencia de memoria• basta con almacenar los nodos de la ruta que se est´a expandiendo(b) ALGORITMOa˜nadir estado inicial a abiertosinicializar cerrados a vacioresuelto := falsewhile (abiertos no vacio and no resuelto) doactual := primer nodo de abiertosif actual es estado final thenresuelto := trueelsea˜nadir actual a cerrados/* expandir actual */for all (operador aplicable a actual) dogenerar nuevo estado aplicando operadorif (nuevo estado no en abiertos ni en cerrados) thena˜nadir nuevo estado al principio de abiertosend ifend forend ifend whileabiertos: Funciona como una pila (lifo)! nodos con mayor profundidad al principio

nota: este algoritmo almacena, adem´as del camino explorado, el inicio de los caminossin explorar– c FJRP 2004 ccia ia – 13(c) CARACTER´ISTICAS B´USQUEDA EN PROFUNDIDADNo es completa: Puede no acabar nunca si encuentra una rama sinfin en el espacio de estados• En ciertos casos nunca se volver´ıa atr´as_ si hay ciclos ) bucle infinito_ si espacio de estados es infinito• Muy dependiente del orden de aplicaci´on de los operadoresNo es ´optima: Encuentra una soluci´on (la primera que aparezca)que no tiene por qu´e ser la mejor (la m´as cercana)Complejidad• Complejidad espacial: O(b × m)_ b, factor de ramificaci´on_ m, profundidad m´axima de cualquier soluci´on• Complejidad temporal: O(bm)_ si no hay soluci´on (o es el ´ultimo estado) examinar´a todos losestados (como en anchura)• En general, suele ser m´as r´apida que b´usqueda en anchura_ es ¸cuesti´on de suerte”

_ puede funcionar bien si hay muchos estados finales• ventajas:_ Menores requisitos de memoria_ Mayor rapidez (en promedio)• inconvenientes:_ Posibilidad de que se estanque_ No asegura soluci´on ´optima– c FJRP 2004 ccia ia – 14(d) VARIANTESProfundidad Acotada• Fijar un l´ımite m´aximo de profundidad (cota c)_ cuando un camino alcanza la profundidad c sin ser soluci´on,desecharlo• Es completo_ Asegura encontrar soluci´on si c es mayor que la profundidadde la soluci´on• No asegura soluci´on ´optima• Complejidad: espacial (O(b × c)), temporal (O(bc))• problema: elecci´on cota c_ Peque˜na:_ahorra tiempo y espaciopuede impedir encontrar soluci´on_ Grande:_desperdicio tiempo y espacio

aumenta posibilidades de encontrar soluci´on_ En general, no hay suficiente info. para elegir cota adecuada• Ejemplo– c FJRP 2004 ccia ia – 15Profundidad Iterativa• Secuencia de b´usquedas por profundidad acotada, incrementandoel valor de la cota hasta encontrar soluci´on• ventajas:_ Evita problema elecci´on de la cota_ Es completa y ´optima_ Siempre da una soluci´on (si la hay)_ Encuentra la mejor (a menor profundidad)! Agota todos los nodos bajo la cota c antesde incrementarla_ Funcionamiento intermedio (anchura-profundidad)_ Uso de memoria reducido (como busqueda profundidad)• inconvenientes:_ Repetici´on de c´alculos_ No excesivamente importante (afecta principalmente a estadosen niveles superiores)_ Mayoria de nodos situados en niveles inferiores– c FJRP 2004 ccia ia – 162.3 B´usqueda Heur´ıstica2.3.1 Generalidades

B´usqueda ciega: ineficaz en la pr´actica (explosi´on combinatoria)B´usqueda heur´ıstica:objetivo: guiar el proceso de b´usqueda• ”Podar”el espacio de estadosUsar info. sobre la cercan´ıa de un estado dado a uno de los estadosobjetivo! explorar primero caminos m´as prometedorescaracter´ısticas :• No garantiza que se vaya a encontrar la soluci´on• Si la encuentra, no asegura que sea ´optima (m´ınimo coste)• En ocasiones, encuentra soluci´on buena en tiempo aceptable_ pierden completitud y/o optimalidad_ aumentan eficienciaFUNCIONES DE EVALUACI´ON HEUR´ISTICASAglutinan el conocimiento del dominio sobre el que se apoyar´a ladecisi´onAsocian a cada estado, e, un n´umero, h(e), que indica lo prometedor,o no, que es ese nodo e de cara a alcanzar un estado objetivo´optimo.Dos interpretaciones:• Estiman la ¸calidad”del estado e) buscar nodos con mayor valor heur´ıstico• Estiman la ”prosimidad.a un estado final

) buscar nodos con menor valor heur´ıstico– c FJRP 2004 ccia ia – 17Ejemplos:• 8-puzzle: no casillas bien colocadas (2o tipo)• cubos: |cantidad en 8 l. - cantidad en 4 l.| (2o tipo)• ajedrez: no piezas de ventaja (1er tipo)Clasificaci´on:• Heur´ısticas generales: adecuadas para multiples dominios! vecino m´as pr´oximo (”medir distancias”)• Heur´ısticas de prop´osito especial: usan conocimiento exclusivo deun dominioheur´ısticas bien fundadas1. Si estiman la ¸calidad”:h(e) est´a bien fundada si los estados finales tienen elvalor m´aximo posible. (estado inicial suele tener valor 0)2. Si estiman la ”distancia”:h(e) est´a bien fundada si los estados finales tienen el valor 0– c FJRP 2004 ccia ia – 182.3.2 M´etodos de escalada o ascenso a colinas(a) FUNCIONAMIENTOFamilia de m´etodos de mejora iterativa.idea: Elegir, en cada paso, uno de los descendientes del estado actualque mejore el valor heur´ıstico de su padremejor = m´as alto ) ascenso a colinas

mejor = m´as bajo ) descenso de gradienteDos variantes:1. Escalada simple:Generar hijos 1 a 1, calculando su valor heur´ısticoEl primer hijo que sea mejor que estado actual pasa a sernuevo estado estado actual2. Escalada por m´axima pendiente:Generar todos los hijos y calcular su valor heur´ısticoTomar al mejor hijo• Si es mejor o igual que estado actual ) pasa a ser nuevoestado actual• Si no, detener algoritmoEjemplos:Espacio de estados Escalada Simple M´axima Pendiente– c FJRP 2004 ccia ia – 19ventajas• Muy poco consumo de espacio• Complejidad espacial: O(1) (basta guardar 1 estado)inconvenientes• Complejidad temporal: exponencial en peor caso (revisa todos)• No son ´optimos ni completos_ pueden no encontrar soluci´on aunque exista (ver problemas)_ no garantizan el camino m´as corto

problemas: Puntos en los que el algoritmo se estancaM´aximos locales: todos los hijos de un estado son peores que ´el yno es un estado objetivo• def.: Un m´aximo local es un estado mejor que cualquier otroestado vecino, pro peor que otros m´as lejanos• El algoritmo para sin dar soluci´onMesetas: todos los hijos tienen mismo valor heur´ıstico que padre• def.: Una meseta es una regi´on del espacio de estados dondetodos los estados tienen el mismo valor heur´ıstico• El algoritmo para sin dar soluci´on• Si sigue, la heur´ıstica no informa ) b´usqueda ciega– c FJRP 2004 ccia ia – 20Crestas: mezcla de los anteriores, se llega a un conjunto m´aximoslocales contiguos• def.: Regi´on del espacio de estados que tiene algunos estadoscon mejor valor heur´ıstico que los colindantes, pero a los queno se puede llegar por transiciones simples (usando un ´unicooperador)soluciones :Reiniciar toda o parte de la buqueda

Dar un paso m´as!generar sucesores de sucesores y ”ver que pasa”M´ax. locales: Volver a un nodo anterior y provar direcci´on distintaMesetas: Hacer un ”salto”grande, para ”salir”de la meseta– c FJRP 2004 ccia ia – 212.3.3 M´etodo del mejor nodo (primero el mejor)(a) FUNCIONAMIENTOidea: Considerar todos los estados frontera, no s´olo los sucesores delestado actualMantener lista abiertos (nodos no expandidos) ordenada por losvalores de la heur´ıstica de los estadoIntenta combinar anchura y profundidad, guiado por la heur´ıstica• Seguir un camino, pasando a otro cuando deje de ser prometedorDiferencia con escalada: los descendientes del estado actualcompiten con todos los dem´as nodos no expandidos(b) ALGORITMOa˜nadir estado inicial a abiertosinicializar cerrados a vacioresuelto := falsewhile (abiertos no vacio and no resuelto) doactual := primer nodo de abiertosif actual es estado final thenresuelto := true

elsea˜nadir actual a cerrados/* expandir actual */for all (operador aplicable a actual) dogenerar nuevo estado aplicando operadorcalcular su heur´ıstica h(nuevo estado)if (nuevo estado no en abiertos o cerrados)or (est´a con peor heur´ıtica) thena˜nadir nuevo estado en abiertosordenar abiertos por valor heur´ısticoend ifend forend ifend while– c FJRP 2004 ccia ia – 22Ejemplo:(c) CARACTER´ISTICAS B´USQUEDA MEJOR NODOComplejidad• Temporal: O(bm)• Espacial: O(bm)• m= profundidad de la soluci´on m´as lejana• En el peor de los casos hay que recorrer todos los estadosEs completo: si hay soluci´on la encuentra, siempre que la heur´ısticafuncione bienNo es ´optimo: puede no dar la soluci´on m´as cercana (ejemploanterior)

• En esencia, sigue siendo un procedimento de b´usqueda en profundidad• Da la primera soluci´on que encuentra– c FJRP 2004 ccia ia – 232.3.4 Algoritmo A_(a) FUNCIONAMIENTOFamilia de algoritmos (Hart, Nilsson, Raphael (1968))objetivo: Mejorar m´etodo del mejor nodo para asegurar completitudy optimalidad.Incorpora la longitud del camino desde la ra´ız hasta el estado actual enla funci´on de evaluaci´on h.considerar no s´olo lo bueno que es un estadotener en cuenta c´omo es el camino usado para alcanzarloFunci´on de evaluaci´on A_f(e) = g(e) + h(e)g(e): costo del mejor camino desde estado inicial al estado eh(e): estimaci´on (heur´ıstica) del coste desde e hasta un estado final´optimof(e): costo estimado de la mejor soluci´on que pasa por el estado eh_(e)g_(e) = g(e)f_(e) = g_(e) + h_(e)9= ;costes reales

conocidos cuando terminael algoritmo– c FJRP 2004 ccia ia – 24(b) ALGORITMOVersi´on Ampliada8<:para manejar grafoscon traza de los caminos (enlace al padre)abiertos ordenada por el valor de f(e)a˜nadir estado inicial a abiertosinicializar cerrados a vacioresuelto := falsewhile (abiertos no vacio and no resuelto) doactual := primer nodo de abiertos /*mejor valor f(e)*/if actual es estado final thenresuelto := trueelsea˜nadir actual a cerradosfor all (operador aplicable a actual) dogenerar sucesor aplicando operador (1)if (sucesor en abiertos con peor g(e)) thencambiar padre del nodo en abiertosestablecer sus nuevas g(e) y f(e)end ifif (sucesor en cerrados con peor g(e)) thencambiar padre del nodo en cerradosestablecer sus nuevas g(e) y f(e)propagar nueva g(e) a susdescendientes en abiertos y cerrados

end ifif (sucesor no en abiertos ni en cerrados) theninsertar sucesor en abiertosend ifreordenar abiertos si es necesarioend forend ifend while– c FJRP 2004 ccia ia – 25(1) Generar sucesor():sucesor.estado := aplicar operadorsucesor.padre := actualsucesor.g := actual.g + coste(operador[actual ! sucesor])sucesor.f := sucesor.g + h(sucesor.estado)nota:Si_h(e) = 0g(e) = profundidad(e)_) B´usqueda en anchuraSi_h(e) = 0g(e) = 0)_) B´usqueda aleatoria– c FJRP 2004 ccia ia – 26CARACTER´ISTICAS B´USQUEDA A*Es ´optimo y completo si:

todo nodo tiene un no finito de sucesorescoste de cada arco/operador > 0la funci´on h(e) es una heur´ıstica admisibleHeur´ıstica Admisible:Diremos que h(e) es una heur´ıstica admisible si nunca sobreestimael coste real desde e hasta un estado meta ´optimo.Es decir, h(e) _ h_(e) 8econclusi´on: Si h(e) es admisible ) f(e) tampoco sobreestima elcoste real de la mejor soluci´on que pase por el estado e.f(e) _ f _ (e)Complejidad_espacial: O(bp)temporal: O(bp)b = factor ramificaci´on, p = profundidad soluci´onEn el peor de los casos (h(e) = 0) sigue siendo necesario recorrertodo el ´arbolEn caso promedio:• El consumo de memoria sigue siendo alto_ almacenamiento de todos los estados visitados y los pendientesde visitar• Tiempo promedio aceptable (mejora b´usqueda en profundidad)– c FJRP 2004 ccia ia – 27

(d) VARIANTESRTA*: Real Time A_• Aplicaci´on en tareas de tiempo real_ no pueden esperar a encontrar soluci´on ´optima• Obliga a tomar una decisi´on cada periodo de tiempo k × t• Periodo de tiempo determina profundidad alcanzada en b´usqueda_ busca hasta donde le da tiempo_ indica la operaci´on sobre el estado actual que inicia el caminoque lleva al mejor estado encontradoA*PI: A_ con profundizaci´on iterativa• B´usqueda por profundizaci´on iterativa controlada por la funci´onde evaluaci´on A__ f(e) = g(e) + h(e)_ nota: en principio, no comprueba estados repetidos• objetivo: reducir necesidades de memoria• L´ımite de coste k, no de profundidad• Expandir s´olo estados e con coste dentro de la cota (f(e) _ k)• El resultado de cada iteraci´on se usa para establecer cota de lasiguienteA*SRM: A_ acotado por memoria• Trabajo con memoria limitada• idea: limitar la cantidad de memoria disponible

_ Usa toda la meoria de la que se dispone_ Mientras hay memoria funcionamiento normal, evitando estadosrepetidos_ Si al generar un sucesor falta memoria, libera el espacio de losestados menos prometedores_ Sigue manteniendo traza de la ”bondad”de esos estadosdesechados– c FJRP 2004 ccia ia – 282.3.4 Heur´ısticas(1) CONSTRUCCI´ON DE HEUR´ISTICASDependen del problemaInfluyen en el rendimientoT´ecnicas generales1. Relajaci´on de operadores• Reducir algunas restricciones sobre los operadores del problemaoriginal• Operadores simplificados facilitan c´alculo de coste en problemarelajado”• Usar coste de la soluci´on del problema relajado¸como heur´ısticadel problema original• Suele generar heur´ısticas admisible• Ejemplo: 8-puzzle_ h1: no de placas en lugar correcto_ no de pasos si se permite mover el hueco a cualquier lugar

_ h2: ”distancia manhatan” (suma distancia vertical y horizontalentre posici´on actual de cada placa y la deseada)_ no de pasos si se permite mover placas en cualquier direcci´on independientementedel hueco– c FJRP 2004 ccia ia – 292. Ponderaci´on de rasgos• Tomar un conjunto de caracter´ısticas del estado que se puedanrepresentar num´ericamente• Combinarlas asign´andoles diferentes pesos• Muy usadas juegos• Posibilidad de aprendizaje de pesos (juego de damas deSamuel)• Ejemplo: ajedrez3. Uso estudio estad´ıstico previo• Partir de una heur´ıstica preliminar h(e) y realizar b´usquedasde entrenamiento• Relacionar los valores de h(e) con los costes reales obtenidosen cada caso_ corregir cada valor de h(e) usando el valor real obtenidocon m´as frecuencia en el ”entrenamiento”4. Combinaci´on de heur´ısticas• Combinar heur´ısticas distintas que funcionen bien s´olo en

ciertas circunstancias_ aprovechar heur´ısticas ”parcialmente”´utiles• Ponder´andolas: h0(e) = w1 × h1(e) + w2 × h2(e) + ... +wn × hn(e)• Agreg´andolas:8<:h0(e) = max{h1(e), h2(e), ...,×hn(e)}h0(e) = min{h1(e), h2(e), ...,×hn(e)}h0(e) = media{h1(e), h2(e), ...,×hn(e)}_ Si todas son admisibles, la agregada tambi´en lo es– c FJRP 2004 ccia ia – 30(2) EVALUACI´ON Y COMPARACI´ON DE HEUR´ISTICASEn general:Si h2(e) _ h1(e) 8e (al rev´es si se maximiza h(e)) se dice queh2(e) domina a h1(e)• con h2(e) se generar´an menos estados! aproxima m´as h_(e) (h_(e) _ h2(e) _ h1(e))• peor no asegura ofrecer una soluci´on mejorCriterios de comparaci´on1. No de estados generados (tama˜no ´arbol/grafo)• depende del problema de b´usqueda concreto• var´ıan con las entradas (estados inicial y finales)2. Factor de ramificaci´on efectivo (ˆb)• M´etrica artificial

_ depende s´olo de la heur´ıstica_ relativamente constante en distintas b´usquedas_ interesa que est´e pr´oximo a 1N: no de nodos expandidosp: profundidad de la soluci´on encontradaˆb: factor de ramificaci´on de un ´arbol uniforme (no de hijosconstante) de profundidad p que contenga N nodosSe cumple:N = 1 +ˆb +ˆb2 + +ˆb3 + ... +ˆbp¿despejar ˆb?– c FJRP 2004 ccia ia – 312.4 B´usqueda en Juegos2.4.1 GeneralidadesINTER´ES DE LOS JUEGOSF´aciles de formalizar• F´acil representaci´on de estados• Acciones restringidas (reglas precisas)• Evaluaci´on de eficacia directaMayor complejidad• Existe oponente_ elemento externo que interact´ua_ introduce incertidumbre• Futuro no predecible• Alto factor de ramificaci´onMODELIZACION: Juegos de 2 jugadores con informaci´on completa

Contrincantes conocen la situaci´on del juego y su oponente• posibles movimientos + movimiento efectuado• resultado del movimiento• no se conoce estrategia del contrincanteNo interviene el azarSe puede determinar en todo momento:8<:victoriaderrotaempateProblemas de suma nula: lo que “gana” un jugador es lo que“pierde” el otroEjemplos: ajedrez, 3 en rayaNO LO SON: juegos con cartas(mus) o dados(backgamon)– c FJRP 2004 ccia ia – 32FORMALIZACI´ON.estado (posici´on) incial : posici´on inicial del tablero + qui´en iniciael juegooperadores (movimientos): definen qu´e jugadas les est´an permitidasa los jugadoresprueba de finalizaci´on: indica el fin del juego (estados/posiciones finales)• victoria, empate, derrota

funci´on de utilidad: asigna valor num´erico a resultado del juego• si no aplicada sobre posiciones finales: funci´on de evaluaci´onT´ECNICA DE REPRESENTACI´ON: ´Arboles alternadosRepresentaci´on expl´ıcita de todas las secuencias de jugadas posibles,para ambos jugadoresnodos: representan posiciones (estados)sucesores: posiciones a las que se puede acceder aplicando losmovimientos permitidosCada nivel representa, alternativamente, las acciones posibles decada jugadorObjetivo: Encontrar un buen primer movimientoEsquema b´asico:1. Generar ´arbol alternado para tablero actual2. Buscar mejor primer movimiento (inicio camino victorioso)3. Ejecutar movimiento4. ”Percibir”que hace el contrincanteEn la pr´actica: Inabordable construir ´arbol completo• 3 en raya: 9! 360000 nodos• damas: _ 1040 nodos• ajedrez: _ 10120 nodos (factor ramific. medio _ 25)• Si es posible_

en juegos pequenosen secuencias finales– c FJRP 2004 ccia ia – 33APROXIMACI´ON PR´ACTICALimitar profundidad de la b´usqueda (fijar horizonte limitado)Aplicar funci´on evaluaci´on (heur´ıstica) sobre nodos hoja resultantes• Convenci´on :_valores altos(positivos) ! posiciones favorablesvalores bajos(negativos) ! posiciones desfavorables– c FJRP 2004 ccia ia – 342.4.2 Procedimiento MINIMAXT´ecnica mixta: combina b´usqueda + evaluaci´onJugador max: maximiza valores de evaluaci´on de sus sucesoresJugador min: minimiza valores de evaluaci´on de sus sucesoresObjetivo: que max sea el ganadormax hace primer movimiento• nodos en niveles pares: turno max• nodos en niveles impares: turno minnota:capa = jugada (1 nivel del ´arbol)profundidad = pares de capas (grupos de 2 movtos. [min+max])• nodos de prof. k = nodos max en capa 2k + nodos min en capa 2k + 1

nodo raiz (max) en capa 0 y prof. 0M´etodo MINIMAXB´usqueda recursiva en profundidad acotada (p = profund. m´axima)• Ra´ız: nodo max• Sucesores nodo max: nodos min• Sucesores nodo min: nodos maxFinal recursividad:8< :gana alg´un jugadoralcanza posici´on de empatese han expandido 2p capasFuncionamiento:• Nodo ra´ız: se corresponde con la posici´on actual del juego• Aplica funci´on evaluaci´on sobre nodos hoja y propaga valoreshasta nodo ra´ız• Devuelve un ”buen”primer movimiento para max_ Selecciona movimiento que genera el sucesor m´as prometedor– c FJRP 2004 ccia ia – 35Suposici´on de partida: Estrategia conservadora• min elegir´a siempre la mejor jugada para ´el (peor para max)_ min es, al menos, tan inteligente como max_ Sabe evaluar tan bien como max!usan misma func. evaluac.Valor minimax: evaluaci´on de la bondad de una posici´on

• en hojas: funci´on de evaluaci´on est´atica• nodos intermedios: calculado a partir de los valores de sus sucesoresFunci´on evaluaci´on hojas:8>>>>><>>>>>:valor positivo: favorable a max(+1 si posici´on ganadora)valor negativo: favorable a min(+1 si posici´on ganadora)empate: devuelve 0PASOS:1. Expandir en profundidad hasta nivel m´aximo (o no expansi´on posible)2. Evaluar nodos hoja (aplicar func. evaluaci´on)3. En cada nivel se propagan evaluaciones hacia atr´asSi es nodo max: tomar m´aximo valor de sus sucesoresSi es nodo min: tomar m´ınimo valor de sus sucesores4. En nodo ra´ız: ejecutar movto. que lleve al sucesor con mejor valor5. Esperar respuesta adversario y volver a (1) con nueva posici´on actualmejor acci´on: Acci´on con evaluaci´on m´as alta, suponiendo queadversario elegir´a en el futuro las mejores opciones para ´el.M´as precisa la evaluaci´on propagada usando minimax que la obtenida

aplicando la funci´on de evaluaci´on est´atica sobre los nodossucesores de la posici´on actual• Tiene en cuenta la secuencia de futuras respuestas del oponenteTodo lo que se sabe de min es que elige la opci´on que m´as leconviene (la de menor valor)• Se supone tan inteligenete como max– c FJRP 2004 ccia ia – 36Punto clave: Definir una buena funci´on de evaluaci´onEjemplo: juego de damas de Samuel• funci´on ponderada de 16 caracter´ısticas• aprendizaje autom´atico de los pesosALGORITMO RECURSIVOMINIMAX(posicion, nivel)/* casos base */if (esGanador(posicion)) thendevolver +1else if (esPerdedor(posicion)) thendevolver −1else if (esEmpate(posicion)) thendevolver 0else if (nivel = limite) thendevolver evaluacion(posicion)else/* caso recursivo */for all sucesor i de posicion dovalores[i] := MINIMAX(sucesor i, nivel+1)if (esNodoMAX(nivel)) then

devolver maximo(valores)end ifif (esNodoMIN(nivel)) thendevolver minimo(valores)end ifend forend ifLlamada inicial: MINIMAX(posionActual, 0)– c FJRP 2004 ccia ia – 37Ejemplo: TIC-TAC-TOEmax: ”X”, min: .O”Funcion evaluaci´on:8<:+1 si gana max−1 si gana min(abiertos(max) − abiertos(min)) en otro caso• abiertos(A) = no filas/columnas/diagonales donde A puede ganar! no l´ıneas sin ficha del contrarioabiertos(A) = 8−no filas/colums./diags. ocupadas por contrarioExpansi´on hasta prof. 1 (2 niveles)! no se muestran posiciones sim´etricas– c FJRP 2004 ccia ia – 382.4.3 Poda ALFA-BETAminimax separa generaci´on de nodos y evaluaci´on de posiciones1o genera todo el ´arbol, despues eval´ua y propagamuy ineficiente

Idea: Evitar generar todas las alternativas, “cortando” aquellas quesepamos que no van a mejorar los valores que ya hemos obtenido hastael momento.Generaci´on y evaluaci´on simult´aneasNecesidad de ”arrastrar” informaci´on adicionalPoda _ − _idea: Arrastrar una ventana (2 valores) indicando a que intervalo debede pertener los valores de evaluaci´on para ser consideradosEvita expandir posiciones que no mejorar´an los resultados actualesEn cada nodo n:• valor _: cota inferior (al menos se han conseguido _ puntos)• valor _: cota superior (como mucho se han conseguido _ puntos)Inicialmente:__ = −1_ = +1Cada nodo recibe los mejores valores de _ y _ obtenidos hasta elmomento y los actualiza con los que le devuelvan sus hijos• En determinados casos, podr´a decidir dejar de evaluar sus hijos(poda )– c FJRP 2004 ccia ia – 39

Actualizaci´on de valores _ y _ hacia atr´as• Nodos min: actualizan valor de __ Toman el menor valor de sus sucesores y actualizan _ si lossucesores lo mejoranSi _ − _sucesor < _ ) _ = _ − _sucesor_ Valores _ en nodos min nunca crecen• Nodos max: actualizan valor de __ Toman el mayor valor de sus sucesores y actualizan _ si lossucesores lo mejoranSi _ − _sucesor > _ ) _ = _ − _sucesor_ Valores _ en nodos max nunca decrecenCORTESSe suspende la expansi´on de los sucesores de un nodo en los siguientescasos:1. Corte _ (en nodos min)Si nodo min alcanza un valor _ menor o igual que el valor_ que lleg´o de un nodo max anterior ) No es necesarioseguir estudiando sus sucesores.condici´on: _ _ _padreEjemplo:2. Corte _ (en nodos max)Si nodo max alcanza un valor _ mayor o igual que elvalor _ que lleg´o de un nodo min anterior ) No es necesarioseguir estudiando sus sucesores.

condici´on: _ _ _padreEjemplo:– c FJRP 2004 ccia ia – 40ALPHA BETA(posicion, _, _, nivel)if (esGanador(posicion)) then devolver +1 thenelse if (esPerdedor(posicion)) then devolver −1 thenelse if (esEmpate(posicion)) then devolver 0 thenelse if (nivel = limite) then devolver evaluacion(posicion) thenelse/* caso recursivo */if (esNodoMAX(nivel)) then_actual := _for all sucesor i de posicion doif (_actual _ _) thenPARAR /* poda BETA */elseaux := ALFA BETA(sucesor i, _actual, _, nivel+1)_actual := maximo(_actual, aux)end ifend fordevolver _actualelse if (esNodoMIN(nivel)) then_actual := _for all sucesor i de posicion doif (_actual _ _) thenPARAR /* poda ALFA */elseaux := ALFA BETA(sucesor i, _, _actual, nivel+1)

_actual := minimo(_actual, aux)end ifend fordevolver _actualend ifend ifLlamada inicial: ALFA BETA(posionActual, −1, +1, 0)– c FJRP 2004 ccia ia – 41PROPIEDADESAlgoritmo _ − _ generar´a el mismo movimiento que miimax expandiendomenos nodos• Mismo resultado, obtenido de forma m´as eficienteEfectividad de _−_ depende mucho del orden en que se examinanlos descendientes• Si se examinan primero los peores caminos, nunca habr´a cortes• Interesa ordenar a los sucesoresSituaci´on ideal:• En nodos min: examinar primero sucesores con menor valor• En nodos max: examinar primero sucesores con mayor valorEn la pr´actica no es posible ordenaci´on perfecta! usar una func. evaluaci´on simple para preordenar sucesoresEn el caso ideal (ordenaci´on perfecta)

• minimax explora O(bd) nodos• _ − _ explora O(bd/2) nodosCon b=factor de ramificaci´on y d= prof. b´usqueda m´axima• Es decir, suponiendo ordenaci´on perfecta, _−_ permitir´ıa alcanzarel doble de profundidad que minimax empleando el mismoespacio y tiempo– c FJRP 2004 ccia ia – 422.4.4 Mejoras minimax y alfa beta1. Efecto horizonteProvocado por limitar el estudio hasta profundidad fija• No se ”ve”m´as alla del horizonte• Un sucesor devuelve un valor (muy alto/bajo) que explorandom´as niveles ser´ıa corregido en sentido contrario_ a corto plazo: buen movimiento_ a largo plazo: p´esimo• Ejemplo: Capturar dama en ajedrez_ Parece muy bueno, pero dependiendo del movimiento delcontrincante (que no veremos) puede ser nefasto si el reyqueda descubierto.Soluci´on: B´usqueda en profundidad variable• No parar siempre a la misma profundidad• Intentar llegar a posiciones ”en equilibrio”

a) Seguir profundizando si la hoja ofrece un valor extermob) Profundizar por sucesores hasta que valor est´atico y din´amicono var´ıen mucho2. Uso movimientos de libroConsultar posici´on actual en un cat´alogo construido previamentey recuperar el movimiento guardado.Imposible construir y manejar para juegos completosRazonable en ciertas fases del juego: apertura y final– c FJRP 2004 ccia ia – 433. Profundizaci´on iterativaUsado en juegos con restricciones de tiempo• Ej.: ajedrez, elegir jugada antes de agotar tiempoIdea:a) Estudiar hasta profundiad pb) Seleccionar mejor movimientoc) Si hay tiempo, estudiar k niveles m´as (prof. p + k)d) Al final del tiempo ejecutar el movimiento identificado en lab´usqueda completada m´as profundaConsumo de tempo y espacio ligeramente mayor! se reeval´ua el ´arbol en cada iteraci´onPuede ser ´util para mejorar la poda _ − _

• Usar resultados de la iteraci´on anterior para ordenar sucesoresadecuadamente4. Aumento podas en _ − _a) Uso movimientos asesinosIdentificar tipos de jugadas muy buenasComenzar la evaluaci´on de sucesores empleando esosmovimientosb) Reducci´on ventana inicialComenzar b´usqueda con ventana m´as peque˜na (no [−1,+1])Aumenta podas en los niveles superiores! afectan a un mayor no de nodosProblema: dif´ıcil ajustar ventana inicial! posibilidad “cortar” el buen camino– c FJRP 2004 ccia ia – 442.4.5 Juegos con Elementos de AzarEjemplos: backgamon, juegos de cartas, juegos con dadosIdea: Incluir una capa adicional representando al elemento aleatorioFunciona como un ”jugador”m´asEJEMPLO: Inclusi´on de un dado• El movimiento del jugador depende del resultado de la tirada deldado! ejemplo: parchis• Incluir jugador ”dado ”• Se supone resultados del lanzamiento equiprobables

• Sucesores de dado_ Se corresponden con las opciones del elemento aleatorio_ Se asocia una probabilidad de aparici´on a cada uno– c FJRP 2004 ccia ia – 45• La propagaci´on ascendente de valores tiene en cuenta esas probabilidades• Nodos aleatorios: propagan un valor esperado (no real) de sussucesores• Alternativas:_ Propagar peor valor (opci´on conservadora)_ Propagar mejor valor (opci´on optimista)_ Propagar media ponderada de acuerdo probabilidadesNodo aleatorio padre de nodos maxexpectimax(A) =P6i=1 probi × maximo{sucesoresdadoi}(sucesores son max )Nodo aleatorio padre de nodos minexpectimin(A) =P6i=1 probi × minimo{sucesoresdadoi

CONOCIMIENTO: capacidad de actuar, procesar e interpretar información.CONOCIMIENTO CIENTIFICO: pensamiento dinámico.BASE DE CONOCIMIENTO: recolección, organización y recuperación de conocimiento.RED SEMANTICA: conjunto de nodos que están conectados por arcos etiquetados.INFORMACION: es todo aquello que puede ser manejado por un sistema.MARCO: es la estructura de datos para representar la situación estereotipos.CONOCIMIENTO ARTISTICO: comunica emociones y sentimientos.