Source: http://www.slideshare.net/jlopez300/agentes-inteligentes-inteligencia-artificial
Timestamp: 2016-08-30 18:33:03+00:00

Document:
Jann Le Xocolat
at Centro de Sistemas Computacionales
INTELIGENCIA ARTIFICIAL:INTRODUCCIÓN Y TAREAS DE BÚSQUEDA VERSIÓN 20100619 © Roberto J. de la Fuente López 2.
Inteligencia artificial: introducción y tareas de búsqueda 2 3.
Presentación 3PRESENTACIÓN El presente documento surge de los apuntes tomados de diversas fuentes durante mipaso por la Ingeniería Técnica en Informática de Sistemas de la Universidad Nacional deEducación a Distancia. Tiene pocos ejemplos y ningún ejercicio propuesto: solo es un tratado teórico. Esteinconveniente se puede solventar ampliamente si se consulta [Fernández et al 1998], pues setrata de un libro de problemas enfocado, entre otros temas, a las tareas de búsqueda. Por último, aunque el documento está enfocado hacia la asignatura de la UNEDantes mencionada, el lector no tendrá problemas en su comprensión si tiene conocimientosprevios de programación, complejidad algorítmica y grafos (de este último se incluye unapéndice).AVISO DE DERECHOS DE AUTOR El autor se reserva todos los derechos. No obstante, el lector lo puede imprimircuantas veces necesite y también lo puede transmitir por cualquier medio. Cualquier otrouso precisa del permiso previo y por escrito del autor. Roberto J. de la Fuente López 4.
Inteligencia artificial: introducción y tareas de búsqueda 4 5.
INDICECAPÍTULO 1.- FUNDAMENTOS DE INTELIGENCIA ARTIFICIAL ................................... 9 1.1.- JERARQUÍA DE NIVELES ........................................................................................ 9 1.2.- JERARQUIA DE NIVELES EN COMPUTACIÓN ............................................... 12 1.2.1. Los agentes .............................................................................................................. 14 1.2.2. Nivel de conocimiento de Newell............................................................................ 15 1.2.3 Dominios de descripción .......................................................................................... 18 1.2.4. SBC, Un agente ¿inteligente? .................................................................................. 20 1.3.- HIPÓTESIS FUERTE DE INTELIGENCIA ARTIFICIAL .................................. 21 1.4.- MODELADO DEL CONOCIMIENTO .................................................................... 21 1.4.1. Metodología KADS-I .............................................................................................. 23 1.5.- ALTERNATIVAS: IA SIMBÓLICA E IA CONEXIONISTA ............................... 24 1.6.- UNA TAREA GENÉRICA: CLASIFICACION ...................................................... 25 1.6.1. Clasificación heurística ............................................................................................ 26 1.6.2. Clasificación conexionista ....................................................................................... 27 CAPÍTULO 2.- MÉTODOS DE RESOLUCIÓN: LA BÚSQUEDA....................................... 29 2.1. TÉCNICAS DE REPRESENTACIÓN DEL CONOCIMIENTO ........................... 29 2.2.- PROBLEMAS EN LOS QUE SE APLICAN TÉCNICAS DE IA ......................... 30 2.3.- PLANTEAMIENTO DEL PROBLEMA .................................................................. 32 2.4.- ENTIDADES EN LAS TAREAS DE BÚSQUEDA ................................................ 33 2.4.1. ¿Qué incluimos en un estado? ................................................................................. 33 2.4.2. ¿Cómo se define un operador? ................................................................................ 34 2.5.- REPRESENTACIÓN DE LAS TAREAS DE BÚSQUEDA ................................... 35 2.6.- CLASIFICACIONES DE LAS TAREAS DE BÚSQUEDA ................................... 38 2.7. CLASIFICACIÓN Y APLICABILIDAD DE LOS OPERADORES ...................... 40 2.8. ESQUEMAS DE REPRESENTACIÓN ..................................................................... 40 2.8.1. Esquema de producción ........................................................................................... 41 2.8.2. Esquema de reducción ............................................................................................. 43 2.9.- MÉTODOS DE RESOLUCIÓN ................................................................................ 46 2.9.1. Generar – probar ...................................................................................................... 46 2.9.2. Medios – fines.......................................................................................................... 47 2.9.3. STRIPPS .................................................................................................................. 48 6.
Inteligencia artificial: introducción y tareas de búsqueda 6 2.9.4. Reducción del problema...........................................................................................48 2.10.- FORMALIZACIÓN DEL PROBLEMA.................................................................48 2.10.1. Lenguaje de descripción de estados .......................................................................49 2.10.2. Lenguaje de operadores .........................................................................................49 2.10.3 Equiparación de descripciones ................................................................................50 2.11.- SOLUCIONADOR ....................................................................................................51 3. BÚSQUEDA SIN INFORMACIÓN DEL DOMINIO .........................................................53 3.1.- INTRODUCCIÓN .......................................................................................................53 3.2.- BÚSQUEDA EN AMPLITUD ....................................................................................54 3.2.1. Algoritmo para búsqueda en amplitud. Nivel de conocimiento...............................56 3.2.2. Análisis del algoritmo. Nivel de conocimiento........................................................57 3.2.3. Algoritmo para búsqueda en amplitud. Nivel simbólico .........................................58 3.2.4. Análisis del algoritmo. Nivel simbólico ..................................................................59 3.2.5. Conclusiones ............................................................................................................59 3.3.- BUSQUEDA EN PROFUNDIDAD ............................................................................60 3.3.1. Algoritmo para búsqueda en profundidad. Nivel de conocimiento .........................62 3.3.2. Análisis del algoritmo. Nivel de conocimiento........................................................63 3.3.3. Algoritmo para búsqueda en profundidad. Nivel simbólico ....................................63 3.3.4. Análisis del algoritmo. Nivel simbólico ..................................................................64 3.3.5. Conclusiones ............................................................................................................65 3.4.- BUSQUEDA CON RETROCESO CRONOLÓGICO .............................................65 3.4.1. Algoritmo para búsqueda con retroceso cronológico. Nivel de conocimiento ........65 3.4.2. Análisis del algoritmo ..............................................................................................66 3.4.3. Conclusiones ............................................................................................................67 3.5.- BUSQUEDA EN PROFUNDIDAD PROGRESIVA ................................................67 3.5.1. Algoritmo para búsqueda en profundidad progresiva ..............................................68 3.5.2. Análisis del algoritmo ..............................................................................................69 3.5.3. Conclusiones ............................................................................................................69 3.6.- BUSQUEDA BIDIRECCIONAL ...............................................................................70 3.6.1. Algoritmo para la búsqueda bidireccional ...............................................................71 3.6.2. Análisis del algoritmo ..............................................................................................72 3.6.3. Otras variaciones para este algoritmo ......................................................................72 3.6.4. Conclusiones ............................................................................................................73 3.7. ALGORITMO GENERAL DE BÚSQUEDA EN GRAFOS ....................................73 3.7.1. Algoritmo general de búsqueda en grafos de Nilsson..............................................75 3.7.2. Análisis del algoritmo ..............................................................................................76 7.
Índice 7 3.7.3. Conclusiones ............................................................................................................ 77 3.8. REFERENCIAS ............................................................................................................ 77 CAPÍTULO 4.- TAREAS DE BÚSQUEDA HEURÍSTICA .................................................... 79 4.1.- INTRODUCCIÓN ....................................................................................................... 79 4.1.1. Algoritmo general de búsqueda en grafos ............................................................... 81 4.1.2. Problema del 8 puzzle .............................................................................................. 81 4.1.3. Mapa de carreteras ................................................................................................... 82 4.1.4. Optimizar el tiempo de una ruta .............................................................................. 82 4.2. PLANTEAMIENTO DEL PROBLEMA ................................................................... 83 4.3. MÉTODO DEL GRADIENTE O BÚSQUEDA EN ESCALADA ........................... 83 4.3.1. Algoritmo para el método del gradiente o búsqueda en escalada ............................ 84 4.3.2. Análisis del algoritmo .............................................................................................. 85 4.3.3. Conclusiones ............................................................................................................ 86 4.4. BUSQUEDA PRIMERO EL MEJOR (PM) .............................................................. 86 4.4.1. Algoritmo de búsqueda primero el mejor (PM) ...................................................... 87 4.4.2. Análisis del algoritmo .............................................................................................. 88 4.4.3. Conclusiones ............................................................................................................ 90 4.5. BÚSQUEDA EN HAZ .................................................................................................. 90 4.5.1. Algoritmo de búsqueda en haz ................................................................................ 91 4.5.2. Análisis del algoritmo .............................................................................................. 92 4.5.3. Conclusiones ............................................................................................................ 93 4.6. BÚSQUEDA A* ............................................................................................................ 93 4.6.1. Algoritmo A* ........................................................................................................... 96 4.6.2. Análisis del algoritmo ............................................................................................ 101 4.6.3. Conclusiones .......................................................................................................... 101 4.6.4. Estrategias derivadas inmediatas ........................................................................... 101 4.6.5. A* con funciones de error...................................................................................... 102 4.7. A* EN PROFUNDIDAD ITERATIVA (A* -P ) ...................................................... 103 4.7.1. Algoritmo A*-P ..................................................................................................... 103 4.7.2. Análisis del algoritmo ............................................................................................ 104 4.8. BÚSQUEDA AO* ....................................................................................................... 105 4.8.1. Algoritmo AO* ...................................................................................................... 107 4.8.2. Análisis del algoritmo ............................................................................................ 109 4.9. BÚSQUEDA CON ADVERSARIOS ........................................................................ 110 4.9.1. Procedimiento MINIMAX..................................................................................... 111 4.9.2. Algoritmo del método MINIMAX. Etiquetado MAX-MIN.................................. 116 8.
Inteligencia artificial: introducción y tareas de búsqueda 8 4.9.3. Algoritmo del método MINIMAX. Etiquetado MMvalor .....................................119 4.9.4. Análisis del algoritmo ............................................................................................120 4.9.4. Conclusiones ..........................................................................................................121 4.9.5. Poda α-β .................................................................................................................121 4.9.6. Algoritmo de poda α-β. Etiquetado MAX-MIN ....................................................124 4.9.7. Algoritmo de poda α-β. Etiquetado MMvalor .......................................................127 4.9.8. Análisis del algoritmo ............................................................................................128 4.9.9 Conclusiones ...........................................................................................................129 APENDICE A.- TEORÍA DE GRAFOS ...............................................................................131 A.1.- DEFINICIONES .......................................................................................................131 A.1.1. Grafos no dirigidos ............................................................................................135 A.1.2. Grafos dirigidos .................................................................................................136 A.1.3. Árboles con raíz .................................................................................................138 A.2. ÁRBOLES Y GDA,S DE UNA RAÍZ ......................................................................138 A.3.MATRIZ DE ADYACENCIA ......................................................................................141 BIBLIOGRAFÍA................................................................................................................143 9.
CAPÍTULO 1.- FUNDAMENTOS DE INTELIGENCIA ARTIFICIAL1.1.- JERARQUÍA DE NIVELES Dado un sistema, sea de la naturaleza que sea, podemos verlo desde dosperspectivas: • Análisis.- Escudriñamos (estudiamos) el sistema para comprender como funciona y así fijar sus especificaciones funcionales, qué hace el sistema, de una manera formal. Este punto de vista es propio de cualquier ciencia como la Física o la Biología. • Síntesis.- Obtención del sistema a partir de unas especificaciones funcionales (creamos el sistema). Este punto de vista es propio de la las ingenierías. Vamos a utilizar como ejemplo un sistema electrónico: Nos lo pueden mostrar descritocon esquemas en papel. Con los conocimientos de electrónica que tenemos, analizamos elcircuito en varios pasos, (por ejemplo, primero por partes y luego de forma global)deduciendo qué es lo que hace y cómo lo hace (por ejemplo, extrayendo las ecuaciones quelo describen). Por el contrario, podemos tener que diseñar un circuito para resolver unproblema concreto; para ello tenemos que sintetizar el problema (extraer sus característicasrelevantes, que pueden ser las ecuaciones que lo definen) para posteriormente, y después deuna serie de pasos, implementarlo con alguna tecnología. Un sistema, por regla general, es muy complejo por lo que se hace necesariosegmentarlo en unidades funcionales más pequeñas. Esta segmentación la realizaremosmediante una jerarquía de niveles. Cada uno de estos (los pasos a los que hacíamosreferencia en el ejemplo anterior) se caracteriza por: • Fenomenología propia del nivel. • Entidades (componentes) y relaciones entre ellos (interconexiones). 10.
Inteligencia artificial: introducción y tareas de búsqueda 10 • Organización y estructura propias (sintaxis propia, “lenguaje”1 que se habla a este nivel). • Restricciones de capacidad. No hay que confundir la jerarquía de niveles con la abstracción: en esta última lo quehacemos es segmentar un sistema en unidades funcionales más pequeñas, de manera que eldiseño se puede hacer por bloques, para posteriormente desarrollar cada uno de estos. Sinembargo estos bloques funcionales pueden estar al mismo nivel jerárquico. Mediante laabstracción podríamos no encontrar un enlace (relación entre dos niveles) de la descripciónde un sistema a un nivel con la descripción en un nivel superior (esta puede no existir). Un nivel está parcialmente encapsulado: cada uno se define y funciona de maneraindependiente. Para ello podemos describir un nivel con: • Espacio de entradas.- Es un espacio multidimensional de características relevantes. Este espacio ha de ser medible. • Reglas de transformación.- Descripción precisa de transformaciones sobre el espacio de entradas. • Espacio de salidas.- También es un espacio multidimensional, que es el resultado de la aplicación en el tiempo, de las reglas de transformación sobre el espacio de entradas. Este espacio también ha de ser medible. La fenomenología del nivel se puede describir mediante la partición de este en medio ysistema. Definimos el medio como el conjunto de características del espacio de entrada másel conjunto de resultados (espacio de salidas) y que son entendibles por el sistema (el querealiza las transformaciones en este nivel). El sistema “entiende y habla” el lenguaje en elque están escritos los espacios de entrada y salida. Aunque los niveles son independientes, están relacionados los unos con los otros pormedio de dos enlaces:1 Aquí se utiliza el término “lenguaje” en un sentido general 11.
Capítulo 1.- Fundamentos de inteligencia artificial 11 • Reducción.- Cada nivel se enlaza con el inferior por medio de una serie de especificaciones precisas de traducción: o El medio del nivel se utiliza para describir el sistema del nivel inferior. o En este proceso se pierde información, pues el resultado es más simple. o El resultado de un proceso de reducción no es único, pues puede dar lugar a varios niveles inferiores, todos ellos equivalentes entre sí. o El proceso de reducción es el que se produce durante la síntesis de un sistema. • Emergencia.- Cada nivel se enlaza con el superior por medio de unas especificaciones: o Se inyecta el conocimiento perdido durante el proceso de reducción. Se añaden al sistema unas estructuras adicionales, emergiendo así entidades del nivel superior (el medio del nivel superior) y el sistema que las procesa. o El proceso de emergencia es el que se produce durante el análisis de un sistema. Esta encapsulación parcial conlleva que la acción del sistema en un nivel sea invarianteante cambios en los niveles inferiores a los que han sido reducidos. Desde el punto de vistadel sistema son totalmente independientes. En la descripción realizada para la fenomenología no hemos hecho mención a la posiblesemántica de los espacios de representación (entradas-salidas). Esto es porque el procesoque realiza el sistema es causal, determinado por las leyes de transformación. El significadode las entidades se las da el experto humano que está analizando/sintetizando el sistema. Porejemplo, un sumador aritmético digital hace que si la entrada tiene una cadena 010 y unacadena 001 a su entrada, a su salida tendrá una cadena 0011. Es el experto el que identificaque se está realizando la operación 2+1=3. 12.
Inteligencia artificial: introducción y tareas de búsqueda 12 Hemos dicho que, dado un nivel n, en la reducción al nivel n-1 perdemos información yque en el proceso de emergencia al nivel n+1 tenemos que inyectar conocimiento para subirde nivel: para esto necesitamos conocer la semántica en este nivel. Por lo tanto, los espaciosde entrada y salida estarán compuestos por pares (Xi, Si) y (Yj, Si) respectivamente, dondeXi e Yj serán características del medio y Si y Sj sus correspondientes significados en estenivel. Al conjunto de estos pares lo vamos a llamar tablas de semántica en este nivel. Hayque hacer hincapié en que la semántica solo tiene sentido para el experto que estámodelando el sistema (esta distinción se verá cuando definamos los dominios dedescripción). Una característica importante de cada nivel es la robustez frente a alteracionessintácticas y semánticas. Los niveles más bajos, al ser más formales, son menos robustos(cualquier cambio en las entradas provoca un cambio en las salidas) que los superiores, quepermiten ambigüedades y siguen siendo válidos. Volvamos a nuestro ejemplo de sistema electrónico y describámoslo en el nivelinferior: la fenomenología será la Física (corrientes de electrones y huecos), sus entidadesserán los dispositivos pasivos (resistencias, condensadores…) y/o activos (diodos,transistores….) interconectadas entre sí, la sintaxis (el lenguaje utilizado) serán lasmatemáticas (cálculo integral, diferencial…), y las restricciones estarán impuestas por latecnología de implementación. ¿Hay algo raro en esta descripción? A simple vista parecería que no, pero adolece deun problema muy extendido en I.A.: Se están mezclando conceptos del nivel de la física decomponentes con el nivel de símbolos de dispositivos. En este caso deberíamos definir lasentidades como física de materiales. La mezcla de descripciones de un nivel en otro es unafuente frecuente de errores.1.2.- JERARQUIA DE NIVELES EN COMPUTACIÓN El primero en identificar niveles en computación fue Chomsky en su estudio de lajerarquía de lenguajes, en especial en la distinción que hizo, para los lenguajes naturales,entre la competencia lingüística y la ejecución del lenguaje. 13.
Capítulo 1.- Fundamentos de inteligencia artificial 13 • Competencia lingüística.- Conocimiento de las reglas gramaticales para la formación de frases. • Ejecución del lenguaje.- Dado que un lenguaje natural no es formal, la manera en que se aplican las reglas gramaticales es ambigua; para su buena ejecución hay que tener en cuenta también la semántica y el contexto de la frase. Por ejemplo, si nos dicen: Hoy paseamos con Chispas. ¿paseamos con destellos? (si por fuese escrito, desecharíamos esta opción, pues empieza por mayúscula) ¿Chispas es el perro? ¿Chispas es el mote de una persona? ¿hay chispas en el ambiente? La teoría de niveles en los modelos de computación fue introducida de formaindependiente por David Marr y por Allen Newell. El primero buscaba una teoríacomputacional en percepción visual2 y el segundo se percató de la dificultad de pasardirectamente de la descripción del problema en lenguaje natural a la implementación delprograma. Los dos determinaron la segmentación de la descripción de un modelocomputacional en tres niveles. En la tabla se visualiza la equivalencia entre niveles de uno yotro. En la teoría computacional de Marr, se dice que hay que tener una clara compresiónde qué hay que calcular planteándolo en lenguaje natural, analizando los posibles esquemasde solución en términos del conocimiento del dominio (del experto). En el nivel deconocimiento de Newell, que engloba a la teoría computacional de Marr, se indica que enmuchas ocasiones no se dispone de una teoría de cálculo, sino especificaciones ambiguasquizás válidas en lenguaje natural, pero difíciles o imposibles de plantear a nivel simbólico2 Ver la definición de agente más adelante 14.
Inteligencia artificial: introducción y tareas de búsqueda 14(una teoría de cálculo es un procedimiento tangible, por tanto más específico que elconocimiento como tal). En el nivel de representación y algoritmo de Marr, se dice que hay que definir unlenguaje que describa el medio (espacios de representación) y el sistema (los algoritmos)que los enlazan para su implementación simbólica. Este nivel se solapa con los deconocimiento y simbólico de Newell. Para este, el nivel simbólico es el formado por lasestructuras de datos en lenguaje de alto nivel, gobernados por las gramáticas formales; es larepresentación del programa. Los algoritmos y la representación del medio pertenecen alnivel del conocimiento. El nivel de implementación de Marr es equivalente al nivel físico de Newell, descritoen términos de procesadores físicos (circuitos lógicos combinacionales, secuenciales y detransferencia de registros) gobernados por el álgebra de Boole.1.2.1. Los agentes Antes de continuar vamos a definir que es un agente. Un agente es un “ente” capazde “percibir” estímulos y “actuar” en consecuencia. En computación, este “ente” puede serun sistema electrónico (el medio son señales), un sistema lógico (el medio son los lenguajesde programación) o un experto humano (el medio es el conocimiento en estado puro). Comovemos, los tres agentes propuestos se diferencian por el nivel al que actúan. Los dosprimeros actúan respectivamente en el nivel físico y simbólico; sus conjuntos de entradas,su forma de actuar y su conjunto de salidas, son totalmente distintas estando, además,perfecta y claramente definidas. Estos dos agentes son causales por definición. Por otro lado, tenemos al experto humano, al que denominaremos agenteinteligente. No obstante, vamos a definir este en términos abstractos diciendo que va a teneruna serie de sensores que perciben estímulos del entorno, va a tener un conocimiento previodel entorno en el que se mueve, el cual está estructurado en algún tipo de representaciónsimbólica desconocida para nosotros (pueden ser hechos, creencias, intenciones…).También tiene unos objetivos o metas que cumplir. Con arreglo a este conocimiento, a losestímulos exteriores que percibe del entorno y a sus objetivos, actúa en consecuencia, 15.
Capítulo 1.- Fundamentos de inteligencia artificial 15afectando al entorno utilizando sus actuadores3. Después de cumplir estos objetivos elagente inteligente aprende del resultado obtenido, añadiendo este nuevo hecho (el objetivo)a su estructura de conocimiento. Así, el agente inteligente es capaz de predecir, con arregloa su conocimiento, el comportamiento que va a tener si se encuentra en un entorno similar auno que ya haya aprendido, es decir, son entornos distintos pero de semántica equivalente. La predicción se ha producido como consecuencia de un razonamiento, que puedeser de tipo: • Deductivo.- Se parte de un conjunto de premisas o hipótesis, y todas ellas se cumplen, se saca una conclusión. Se va de lo general a lo específico • Inductivo.- Dado un caso particular, podemos generalizarlo para un caso general. En este razonamiento siempre va a tener una validez con un grado de incertidumbre. Se va de lo específico a lo general • Abductivo.- Dado una conclusión se trata de deducir las premisas o hipótesis que han dado lugar a ella. El agente inteligente puede utilizar uno solo de estos métodos de razonamiento, queen I.A. normalmente llamaremos de inferencia, o una mezcla de ellos. Un ejemplo: Un niño que estando en su casa mete el dedo en un enchufe por primeravez en su vida. Aunque muchas veces sus padres le advirtieran sobre el peligro que ellosupone, finalmente la curiosidad puede con él y lo hace. Aunque se queda en un susto, le daun buen calambrazo: acaba de aprender, por deducción, que meter el dedo en el enchufe esmuy desagradable. Cuando este niño va a jugar a casa de un amigo e identifica un enchufe,predice, inductivamente, que si mete el dedo en un agujero de ese enchufe se produce unefecto desagradable. El entorno es distinto aunque la semántica de la situación es la misma:es otra casa y otro enchufe (más grande, de otro color, con luz de neón…).1.2.2. Nivel de conocimiento de Newell ¿ En base a qué actúa un agente inteligente? En base a lo que Newell llamó el principiode racionalidad (también llamado de causalidad semántica), cuya traducción es:3 También llamados efectores. 16.
Inteligencia artificial: introducción y tareas de búsqueda 16 “Si un agente tiene el conocimiento de que una de sus acciones conducirá a una de sus metas, entonces el agente seleccionará esa acción” 4 Según este principio, se toman las decisiones más óptimas de forma instantánea yautomática, en base a TODA la información del entorno disponible en ese momento. Estosignifica que el agente puede tomar decisiones erróneas si el conocimiento que tiene delentorno es insuficiente. ¿Cómo describimos el conocimiento? Según la teoría de niveles antes descrita, hemos dedescribir el medio de este nivel con unos espacios de representación, que por definición sonfinitos, es decir, tiene una sintaxis formal. El conocimiento del mundo no se puede modelarcompletamente con estructuras finitas, luego tenemos un problema, ya que esto nos estádiciendo que solo podremos modelar parcelas del conocimiento. Otro problema, derivadodel anterior, es que, si no podemos describir el conocimiento con estructuras finitas, ¿cómopodemos describir, entonces, las percepciones del agente? Esto es consecuencia de que los problemas se expresan en lenguaje natural, el cual no esestricto en cuanto a estructuras, y normalmente incompleto en cuanto a lo que describen; secomplementan con la semántica que sólo el agente inteligente es capaz de interpretar. Unejemplo muy parecido al anterior sobre ejecución del lenguaje para Chomsky: “Hoy voy acomer con UNIX”; la frase está bien formada sintácticamente, pero semánticamente ¿quiéncome con UNIX?, ¿es un sistema operativo? ¿O es una persona con el mote UNIX? Elcontexto solo lo identifica el agente inteligente en su entorno. Estas dos cuestiones que nos hemos planteado (encontrar una sintaxis que describa elconocimiento y un medio racional para identificar el contexto) son las que trata desolucionar la I.A. y que, además, son las que llevan a Newell a definir el nivel deconocimiento: No existe un mecanismo claro para reducir el conocimiento de manera que sepueda representar mediante estructuras finitas (sintaxis formal) y tampoco hay unmecanismo claro de cómo computar el comportamiento no analítico del experto, que estambién conocimiento (razonamiento en base a la semántica). El nivel de conocimiento deNewell es equivalente a la competencia lingüística definida por Chomsky en su jerarquía de4 Traducción de la definición en [Newell 1980]. 17.
Capítulo 1.- Fundamentos de inteligencia artificial 17lenguajes, es decir, describe como se debe pasar de una estructura ambigua a una sintaxisformal. En la definición dada por Newell para sus niveles, estos los describe en base a cincoaspectos: Nivel Nivel físico Nivel simbólico Nivel deAspecto Conocimiento Sistema Sistemas digitales y Agente programador Agente inteligente Arquitectura de Computadores Medio Bits y vectores de bits Símbolos y Conocimiento expresiones Componentes Puertas, registros, Operadores y Metas u objetivos UAL,s ubicaciones en Creencias memoria (primitivas Intenciones del lenguaje) (semántico) Composición Algebra de Boole Asignación y Estructura asociación desconocidaComportamiento Autómatas finitos Autómatas de pila Principio de racionalidadEl nivel de conocimiento se caracteriza por ser: • Abstracto y genérico.- Lo que se intenta es encontrar tareas genéricas que sirvan para manipular la representación del conocimiento, llegando a ser estas tan simples que permitan un proceso de reducción al nivel simbólico. Así mismo se intentan encontrar lenguajes de representación del conocimiento (aplicación de la lógica matemática, reglas, marcos y redes) y unos métodos de inferencia (inducción, abducción, deducción, resolución y herencia) que permitan el aprendizaje. • Es independiente del dominio.- Intenta definir una arquitectura general y a ser posible reutilizable, que modele el conocimiento y que enlace fácilmente con el nivel simbólico. 18.
Inteligencia artificial: introducción y tareas de búsqueda 181.2.3 Dominios de descripción En cada nivel se van a tener dos sistemas de referencia para representar lasmagnitudes y su semántica (recordar que el medio hay que definirlo para que sea medible): • Dominio Propio (DP) o auto contenido.- Describe la fenomenología propia del nivel. Es propio de los niveles físico y simbólico, en los que las descripciones son operacionales y los resultados son causales por definición. No se puede salir de la sintaxis del nivel, dado el carácter formal de este (en el nivel físico gobernado por una función lógica y en el simbólico por una gramática independiente del contexto). • Dominio del observador externo (DO).- Interpretación de la fenomenología desde el punto de vista del experto, luego sólo existe en el nivel de conocimiento. En este dominio se utiliza el lenguaje natural para definir y dar significado a los procesos del DP. El DP solo tiene significado en el DO, luego son las tablas de semántica de los nivelesfísico y simbólico las que relacionan estos dos dominios. Así, para el nivel físico, en el DPson ceros y unos, y en el DO se le asocia un valor, por ejemplo numérico, que es el que tienesentido para el observador externo. Para el nivel simbólico, en el DP son símbolos cuyasintaxis está definida por una gramática independiente del contexto y en el DO se trata deuna secuencia de operaciones que manipulan una estructura de datos, que para el observadorexterno tienen un significado dentro del dominio. Anteriormente se ha dicho que hay que tener cuidado en mezclar aspectos de distintosniveles. Pues también deberemos tener cuidado con mezclar descripciones de los dosdominios dentro del mismo nivel. Si esto se produce, el modelo probablemente será erróneoo cuando menos ambiguo. ¿Y el DP en el nivel de conocimiento? Se considera que la descripción de este dominioen este nivel no existe (aun cuando en la tabla que dibujamos a continuación así parezca), yaque es el mismo observador externo el que modela el conocimiento en lenguaje natural:realiza la descripción detallada de la arquitectura general definida en el nivel deconocimiento de Newell, estructurada en tareas genéricas, lenguajes de representación del 19.
Capítulo 1.- Fundamentos de inteligencia artificial 19conocimiento y métodos de inferencia. Además esta arquitectura general también determinalas tablas de semántica en este nivel. En su teoría del nivel de conocimiento, Newell sólo definió la representación delconocimiento y no una teoría sobre como representarlo. Para esto se están haciendoesfuerzos en un nivel intermedio entre el de conocimiento y el simbólico desarrollándose: • Teoría de agentes cooperativos (descomposición, segmentación y especialización) para la arquitectura global. • Metodología KADS (o KADS-I, ya que ha evolucionado hacia commonKADS, o KADS-II, que se generaliza para la administración y análisis del conocimiento) con su estructura de tareas genéricas predefinidas (metodología utilizada para creación de sistemas basados en el conocimiento, SBC, también llamados sistemas expertos5). Los niveles de computación junto con los dominios de descripción del modelocomputable, hacen que podamos sintetizarlos/analizarlos, tal como lo haríamos en cualquierotra ingeniería. Esto se muestra en el siguiente recuadro. En el proceso de análisis, partimos de la implementación del hardware para obtener loscircuitos lógicos y las funciones que en él se dan. Con el DO del nivel físico (la semántica),junto con el DP del nivel simbólico (el programa), emergen las estructuras de datos que semanipulan con él (DO del nivel simbólico), y con estas y la tabla de semántica del DP delnivel de conocimiento termina por emerger qué hace el modelo. En el DO siempre habrámás conocimiento que el que se pueda deducir del DP. En el proceso de síntesis, partimos del problema, capturamos los procesos noanalíticos del experto humano junto con el conocimiento del dominio, y lo reducimos alnivel simbólico, implementamos el programa, el cual traduciremos a una secuencia defórmulas lógicas que finalmente implementaremos en el hardware.5 Sistemas Expertos, SE, también llamados “sistemas basados en el conocimiento”, SBC, es una aplicacióninformática que implementa un modelo de conocimiento circunscrito a un campo específico del conocimientohumano (por ejemplo, medicina), funcionando como un agente inteligente. 20.
Inteligencia artificial: introducción y tareas de búsqueda 20 DOMINIONIVEL DO DP Tareas genéricas, teorías sobre la representación del conocimiento (Lógica formal, Caracterizado por las metas, marcos, reglas y redes) eNivel de conocimiento creencias e intenciones y inferencia (inducción, gobernado por el principio de deducción, abducción, racionalidad. resolución y herencia), para su reescritura computable y construcción de las tablas de semántica. Caracterizado por un lenguaje Implementación del programaNivel simbólico formal y estructuras de datos. en el lenguaje formal Semántica del DP Diseño de los circuitos lógicos, cuyo comportamiento estáNivel físico gobernado por el álgebra de Implementación del hardware Boole. Semántica del DP1.2.4. SBC, Un agente ¿inteligente? Según un estudio realizado en 1986 por Dietterich basándose en la teoría de niveles,muchos de los sistemas que se llamaban de aprendizaje se quedaban en optimizadores deprestaciones, pero no aprendiendo nada. Llegó a la conclusión de que el comportamiento deun programa de aprendizaje no se puede describir ni predecir al nivel de conocimiento, puesrealizan saltos inductivos no justificados. Recordemos que un agente inteligente es aquel que percibe unos estímulos y actúaen base a ellos y al conocimiento que tiene para conseguir los objetivos (metas, creencias,intenciones). Lo importante del agente inteligente es que ha de ser capaz de reaccionar ensituaciones nuevas para él, tomando sus propias decisiones (realmente no se pueden predecirde manera formal el comportamiento). Como ya se dijo, el resultado de las acciones seinyecta al agente inteligente como conocimiento adicional. 21.
Capítulo 1.- Fundamentos de inteligencia artificial 211.3.- HIPÓTESIS FUERTE DE INTELIGENCIA ARTIFICIAL Como ya se expuso, en los enlaces de reducción entre niveles, se produce una pérdida deconocimiento que se almacena en su tabla de semántica, y en la emergencia hay queinyectar conocimiento para reconstruir el medio. La hipótesis fuerte de la IA es que, a pesarde las pérdidas de semántica en el enlace de reducción del nivel de conocimiento alsimbólico y luego al físico, todavía es posible hacer computable la inteligencia humana.1.4.- MODELADO DEL CONOCIMIENTO Con lo dicho hasta ahora, podemos decir que tenemos dos tipos de conocimientopara modelar: • Procesos no analíticos del experto humano, que definen la forma de razonar y actuar (sus métodos de inferencia); es el conocimiento estratégico y es independiente del dominio. • Conocimiento del dominio, que define el dominio propio en el que vamos a sintetizar el SBC (identificación del vocabulario específico del dominio y del contenido de las estructuras de datos). Para abordar el modelado del conocimiento, el DO se puede estructurar en tres capas: • Una capa interna, que estará compuesta por una estructura de Tareas Genéricas que, interconectadas, forman el conocimiento estratégico (por ejemplo: clasificación, diagnóstico, planificación…). • Una capa intermedia, formada por las herramientas (formalismos de representación del conocimiento: lógica, reglas, marcos, redes o híbridos de los anteriores) y los métodos (Inducción, deducción, abducción, resolución y herencia) que utilizarán las tareas genéricas. Para una misma tarea genérica puede haber varias soluciones con distintas herramientas y métodos. 22.
Inteligencia artificial: introducción y tareas de búsqueda 22 • Una capa externa, que es la descripción global de la solución al problema planteado, donde se incluye la organización de la adquisición del conocimiento y del modelo, la segmentación en tareas genéricas y sus estrategias de control. Un primer paso en el modelado es el análisis del problema de forma estratégica,identificando los objetivos, las funciones necesarias y como se estructuran (jerarquía deobjetos). Este conocimiento estratégico es el conjunto de procesos no analíticos del expertohumano. La forma más típica de este análisis es la entrevista con el experto, aunque debidoa que puede ser incompleta y ambigua, se han desarrollado otros métodos basados en lapsicología que garanticen estas dos características. El ingeniero de conocimiento ha deconocer el domino, pero sin llegar a ser un experto en él. Al principio de los SBC,s, lo quese pretendía era introducir todo el conocimiento del dominio en el sistema para queobtuviese conclusiones (eran estáticos a nivel de conocimiento, además de tener queconvertir en experto al ingeniero, lo que es un tiempo prohibitivo en el desarrollo delsistema). Por eso lo que se pretende es modelar “como” piensa el experto, más que en“qué” piensa. Con los objetivos obtenidos de este análisis, se modela el conocimiento en unasecuencia limitada de bloques funcionales de alto nivel que llamamos tareas genéricas.Estas todavía son demasiado complejas para reducirlas al nivel simbólico, por que sedeterminan también unos métodos de resolución de problemas que desarrolla las anteriores,es decir, los métodos son las subtareas en las que se dividirán las Tareas Genéricas parallegar a su objetivo. Estos métodos serán de naturaleza heurística6. Estas subtareas, a suvez, podrán desglosarse en otras subtareas de manera recursiva hasta que se obtengan unosmétodos elementales ya reductibles directamente al nivel simbólico. Al ser conocimientoestratégico, las tareas y los métodos son independientes del dominio, por lo que se podránreutilizar en otros SBC,s. Las tareas genéricas más importantes son la clasificación y eldiagnóstico. El método estará íntimamente ligado a las herramientas de representación que seutilicen. Estas, que también son genéricas, son las que van a enlazar con el conocimiento6 Etimológicamente, heurística es el estudio del descubrimiento y la invención debido a la reflexión y no alazar. En I.A. la usaremos en el sentido de estrategias que conducen a un descubrimiento razonado de lasolución -dirigen las inferencias con la información disponible, la cual normalmente será incompleta. 23.
Capítulo 1.- Fundamentos de inteligencia artificial 23del dominio. Este último puede hacer que nos decantemos por una u otra herramienta(incluso híbridas), y determinará a su vez los métodos a utilizar. Una vez que tenemos esta estructura de tareas genéricas y métodos, decimos quetenemos un modelo del conocimiento, y lo que tenemos que hacer ahora es codificarlo anivel simbólico.1.4.1. Metodología KADS-I Acrónimo de Knowledge Analysis and Design Support, fue un proyecto inicial en elque se diseñó una metodología para la adquisición de conocimiento con herramientassimilares a las de la teoría de sistemas (ciclo de vida de desarrollo, estructuración enmódulos funcionales….). KADS-I no era lo suficientemente precisa y eficiente; es en elproyecto KADS-II donde se alcanza un grado de formalización comercialmente viable,denominándose actualmente commonKADS. Esta metodología es un estándar de facto en eldesarrollo de sistemas basados en el conocimiento. Además sentó las bases para UML7,utilizado en ingeniería del software y que tiene una sintaxis muy parecida. Veremos las bases de KADS introduciendo KADS-I. Esta metodología se basa en laestructura de tareas genéricas antes descrita, para la que dispone de una biblioteca de estasya predefinida, así como los métodos de inferencia que utilizan. El ciclo temporal dedesarrollo consta de fases alternativas de análisis y síntesis. El análisis comienza con la identificación del problema global, su descomposiciónen bloques funcionales y la descripción de como va a interaccionar con el entorno. Todoellos se documenta. Este análisis derivará en una síntesis global del sistema en variossubsistemas cooperantes (módulo de conocimiento, interfaz y resto de aplicación-base dedatos,…-). Otra parte importante del análisis es la adquisición del conocimiento del experto, talcomo la hemos descrito anteriormente. Para ello esta metodología estructura esteconocimiento en cuatro capas estructuradas jerárquicamente:7 Unified Modeling Language.- Lenguaje de modelado uniforme, orientado a objetos. 24.
Inteligencia artificial: introducción y tareas de búsqueda 24 • Conocimiento del dominio.- Esta es la capa más profunda en la que se adquiere el conocimiento estático: entidades del dominio y sus relaciones y se determinan las herramientas de representación (lógica, reglas, marcos, redes). • Inferencia.- Son los métodos que utilizaremos (inducción, deducción, abducción, resolución y herencia) y que estarán relacionados íntimamente con la o las herramientas de representación elegidas (aunque no con su contenido). • Estructura de tareas genéricas.- Seleccionadas o construidas a partir de los métodos utilizados. • Estrategia de modelado.- En la que se determina la estructura de tareas genéricas y si hay que cambiar alguna. La suma de estas cuatro capas es lo que forma el modelo de conocimiento. Una vezobtenido este, hay que compararlo con la biblioteca de tareas genéricas predefinida paraescoger la que más se parezca, modificando, si es necesario, la estructura obtenida en elanálisis. Así se encontrará la estructura de tareas genéricas más adecuada al problema que seestá resolviendo. Una vez que se ha obtenido la estructura del modelo de conocimiento, seprocede a sus síntesis.1.5.- ALTERNATIVAS: IA SIMBÓLICA E IA CONEXIONISTA Actualmente, y debido a las limitaciones de ambas, estas dos alternativas cooperanen la resolución de un problema (antes estaban enfrentados los que defendían una u otraalternativa), dependiendo de la naturaleza de este. Tenemos: • I.A. Simbólica.- Se caracteriza por pasar del nivel de conocimiento al físico, programando los procesadores, es decir, pasando por el nivel simbólico. • I.A. Conexionista.- Se caracteriza por pasar del nivel de conocimiento al físico directamente, sustituyendo la programación por el aprendizaje de su “red neuronal” (siempre se va a estructurar en una red multicapa de procesadores elementales, donde parte de la computación es intrínseca a la tipología de la misma). El 25.
Capítulo 1.- Fundamentos de inteligencia artificial 25 autoaprendizaje se produce por el ajuste en el valor de un conjunto de parámetros o por asociación de estímulos. Para poder aplicar esta alternativa el problema debe ser segmentable y modular (paralelismo).Comparando las dos alternativas: • En la conexionista, para reducir del nivel de conocimiento directamente al nivel físico, el análisis debe ser más pormenorizado. En la simbólica se facilita enormemente la labor de análisis, ya que tiene, como herramienta, los lenguajes de alto nivel. • La conexionista está limitada a problemas que admitan esta alternativa (segmentable y modular). La simbólica ofrece varias tareas genéricas y métodos de aplicación, mientras que la conexionista va a ser siempre una red multicapa, lo que limita el tipo de problemas a resolver. • En la conexionista, la bajada de dos niveles de manera directa es problemática pues la red multicapa es de procesadores muy elementales, luego la función de aprendizaje no puede ser muy complicada. Por ello se necesita tener la posibilidad de obtener un conjunto de entrenamiento. • La conexionista es adecuado para un medio cambiante y poco conocido.1.6.- UNA TAREA GENÉRICA: CLASIFICACION Sea cual sea la alternativa que se elija para solucionar el problema, vamos a teneruna tarea genérica común: la clasificación (ya se dijo antes que era una de las másimportantes). La tarea de clasificación agrupa configuraciones de salida en clases y lo que hace esasociar configuraciones del espacio de entradas a estas clases de salida. Ambos espaciosprecisan una definición previa en extenso. Según el dominio podríamos tener: • Entradas o Datos. 26.
Inteligencia artificial: introducción y tareas de búsqueda 26 o Vectores de características. o Hipótesis iniciales. • Salidas o Diagnósticos. o Fallos del sistema. o Conceptos asociados. El método que utiliza es distinto según el tipo de clasificación que se realice: • Clasificación jerárquica.- Establecer y refinar (redes semánticas). • Clasificación heurística.- Comparación abstracta. • Clasificación conexionista.- función de aproximación de coste.1.6.1. Clasificación heurística En 1985 Clancey encontró similitudes en todos los sistemas basados en reglas(herramienta para la representación de datos), y las aplicó en MYCIN (diagnóstico médico),denominándolo clasificación heurística. Se divide en tres subtareas: • Abstracción de los datos.- El valor real de una variable pertenecerá implícitamente a una categoría abstracta de datos (clase de datos de entrada). Por ejemplo, las temperaturas corporales superiores a 37ºC son de la categoría “fiebre”). • Equiparación heurística.- Busca una asociación entre la categoría abstracta de entrada con clases abstractas de soluciones (por ejemplo, la fiebre se puede asociar con la clase de patologías que son “infección”). • Refinamiento.- Especialización de las clases obtenidas para llegar a la solución. 27.
Capítulo 1.- Fundamentos de inteligencia artificial 27 Clancey analizó varios métodos de inferencia de varios sistemas expertos y mostró quela clasificación heurística se podía aplicar a todos ellos (mostró que era independiente deldominio).1.6.2. Clasificación conexionista La tarea a solucionar en el enfoque conexionista se puede plantear en términos de unclasificador multicapa, donde cada capa realiza una inferencia. Se descompone en 4subtareas: • Extracción de propiedades.- Se preparan las señales del espacio de entradas donde cada variable será una línea etiquetada con su tabla de semántica (la red maneja números, dejando la semántica siempre en el dominio del observador). Se puede hacer por métodos analíticos (filtros), algorítmicos (mínimos, máximos o histogramas) y simbólicos (condicionales). La salida de cada procesador elemental de la última capa es una línea etiquetada, asociada a una tabla de semántica, y cada una representa una clase de resultados. Las entradas y salidas así obtenidas son estáticas. Otra parte de las entradas y salidas son programables por autoaprendizaje. • Métricas.- Determinar la distancia de las salidas a los valores representativos de las clases. • Selección de máximos.- Una capa decide sobre la clase a la que “creemos” que pertenece la configuración. Esto se puede realizar de varias formas: o Selección del valor máximo: procedimientos competitivos. o Procesos cooperativos. o Interpretación borrosa o probabilística del resultado final. • Aprendizaje por realimentación.-- 28.
Inteligencia artificial: introducción y tareas de búsqueda 28 29.
CAPÍTULO 2.- MÉTODOS DE RESOLUCIÓN: LA BÚSQUEDA2.1. TÉCNICAS DE REPRESENTACIÓN DEL CONOCIMIENTO Dependiendo del problema que se nos plantee, se ha de elegir una forma derepresentar el conocimiento del dominio; así tenemos dos opciones: • Técnicas declarativas.- Se describen los aspectos conocidos del problema. Se especifica la información pero sin decir cómo usarla. Describen el conocimiento del dominio como tal. Se caracterizan por: o Claridad y uso modular.- Permiten añadir nuevos hechos, los cuales se almacenan una sola vez. o Conllevan un tratamiento heurístico. • Técnicas procedimentales.- Describe el proceso a realizar para encontrar la solución. Declaran como se manipulan las entidades. Se caracterizan por: o Son más eficientes que las anteriores. o Conllevan un tratamiento algorítmico. Por ello son más fáciles de mantener. o Se utilizan para guiar las líneas de razonamiento (que la evolución del razonamiento sean coherente). Ningún sistema experto es completamente declarativo o procedimental (salvo que elproblema que soluciona sea muy sencillo), ya que la especificación del conocimiento 30.
Inteligencia artificial: introducción y tareas de búsqueda 30(declarativo) necesita de algoritmos para su tratamiento (procedimental). No obstante, el usode unas u otras técnicas determinan como se representa el conocimiento. Estas dos técnicas son intercambiables, siempre y cuando, para las declarativas, hayaun procedimiento de interpretación algorítmico. Ya se dijo que los métodos estarán ligados a las herramientas de representación. Paraproblemas cuyo conocimiento se representa por técnicas procedimentales, los métodos sonde resolución y se llevan a cabo mediante tareas de búsqueda, que son de naturalezaalgorítmica (procedimental): son subtareas genéricas para la resolución de problemas.Los métodos clásicos de resolución, que no son exclusivos entre sí, sino que, paraproblemas complejos, se pueden utilizar conjuntamente, son: • Generar – Probar • Medios – Fines o STRIPPS • Reducción del problema Estos métodos se describirán después de formalizar los problemas en términos de tareasde búsqueda.2.2.- PROBLEMAS EN LOS QUE SE APLICAN TÉCNICAS DE IA Ante un problema se nos pueden plantear dos situaciones: • Que se tenga el conocimiento sobre lo que hay que hacer. • Que haya que indagar como llegar a una solución. 31.
Capítulo 2.- Métodos de resolución: La búsqueda 31 Desde el punto de vista del nivel simbólico (Dominio Propio), y para los problemaspara los que existe algún algoritmo que los soluciona, sus implementaciones se puedenclasificar según el coste computacional que vaya a tener. Se pueden presentar dos tipos: • Problemas tipo P.- Son aquellos en los que el coste tiene una complejidad polinómica (además, en problemas reales, el exponente no puede ser muy grande). • Problemas tipo NP.- Son aquellos en los que los algoritmos que los solucionan tienen una complejidad exponencial. Esto nos lleva a que, con tamaños muy pequeños del problema se consuman todos los recursos disponibles. Desde el punto de vista del nivel de conocimiento (Dominio del Observador), losproblemas pueden ser: • Problemas P.- Se conoce el algoritmo y es computable. Se implementa mediante las técnicas normales de estructura de datos y algoritmos. • Problemas NP.- Se conoce el algoritmo que lo soluciona, pero es de complejidad intratable. • Problemas con solución parcialmente conocida.- En el campo del conocimiento humano, la incógnita está en como se formaliza el razonamiento para llegar a alguna solución, ya sea conocida totalmente o con un grado de incertidumbre. La I.A. estudia precisamente como pasar del nivel de conocimiento al simbólico yconseguir un algoritmo computable para alguno de estas dos últimas categorías. Esto sehace con herramientas y métodos genéricos, que al ser independientes del dominio son: • Aplicables a muchas clases de problemas. Cada uno de ellos se pueden caracterizar encontrando unas “entidades” y “procedimientos de manipulación” comunes. Entonces, es cuando podemos crear procedimientos de resolución genéricos, independientes del dominio del problema. • Son débiles, pues no utilizan la información relevante del domino para su resolución (pueden ser problemas de una misma clase, pero de dominios totalmente dispares). 32.
Inteligencia artificial: introducción y tareas de búsqueda 32 • Su principal desventaja es que son poco eficientes, debido, precisamente, a su carácter genérico.2.3.- PLANTEAMIENTO DEL PROBLEMA De manera general, para plantear el problema, lo primero que se hace es fijar una meta,y en base a esta formular el problema. Para ello se parte de una descripción en lenguajenatural y a partir de esta se abstraen los elementos y acciones más relevantes (se eliminanlos detalles superfluos). De esta manera definimos el problema en términos representablespor “entidades”, que el sistema reconoce y puede “manipular”. Para que un sistemareconozca estas “entidades”, deberemos poder definirlas de manera formal y estructurada,mediante un lenguaje de representación. El proceso de definición de entidades (abstracción)es muy importante, ya que depende de la habilidad que tenga el diseñador del sistema (espoco sistemático y muy subjetivo). El problema, por regla general, se representará con ungrafo donde aparecerán todas las relaciones entre unas entidades y otras (también hay otrasformas de mostrar estas relaciones). Uno de los procedimientos para “manipular” estas “entidades” es la búsqueda, la cualserá ejecutada por un agente (el sistema, el programa) que es el que tiene unas metas aalcanzar. A este agente se le denomina solucionador. Para buscar las metas se necesita un conjunto de acciones, y estas ser aplicadas en elorden fijado por algún mecanismo de selección que guía la búsqueda. A este mecanismo sele llama estrategia de control o estrategia de búsqueda. La solución obtenida (puede nohaber o ser más de una), si la hay, se expondrá como una secuencia de accionesdeterminada; habrá casos en los que solo se necesita el valor final de la resolución, pero porlo general, en IA, se quieren saber los pasos seguidos para llegar a una solución válida. 33.
Capítulo 2.- Métodos de resolución: La búsqueda 33 La debilidad y eficiencia de los métodos genéricos se puede mejorar, como se verá mástarde, dirigiendo la búsqueda mediante el conocimiento heurístico8 aplicado a la estrategiade control, siendo este de dos tipos: 1.- Dependiente del dominio. Para determinar la proximidad a la meta. 2.- Dependiente de cómo funciona internamente la tarea de búsqueda. El proceso de búsqueda de la solución se representará con un grafo dirigido y acíclico(GDA)9. Los algoritmos de búsqueda se van a ver desde el punto de vista del nivel deconocimiento; la implementación detallada y eficiente de estos (nivel simbólico) se dejapara las disciplinas de programación de estructura de datos y algoritmos.2.4.- ENTIDADES EN LAS TAREAS DE BÚSQUEDA Se ha dicho que, en el proceso de abstracción del problema, hemos de identificarcorrectamente las “entidades”. Para hacerlo hemos de tener en cuenta el enfoque quenecesitamos; en este caso enfocados a la búsqueda, por tanto en un marco procedimental. Cualquier tarea de búsqueda responde al esquema de grafo de exploración (luegoveremos como se representa) de la tabla 1.2.4.1. ¿Qué incluimos en un estado? Este es un punto difícil: hay que definir qué incluimos en un estado y qué no. Siabstraemos demasiado la descripción del problema, puede que las entidades extraídas delmismo sean demasiado generales; el resultado obtenido sería inútil porque este no se puedetrasladar al nivel simbólico. Y viceversa, si se detalla demasiado, el número de operadores8 Ya se dijo que etimológicamente, heurística es el estudio del descubrimiento y la invención debido a lareflexión y no al azar. Aquí la usaremos en el sentido de estrategias que conducen a un descubrimientorazonado de la solución (dirigen el proceso de búsqueda con la información disponible, la cual normalmenteserá incompleta -lo que se hace en estos problemas es simplificarlos, para extraer algún criterio que nos sirvapara dirigir la búsqueda-)9 Ver anexo A: Repaso de grafos 34.
Inteligencia artificial: introducción y tareas de búsqueda 34puede ser muy grande y el coste de llegar a la solución puede hacer no computable labúsqueda de una solución del problema con esos operadores.CON ESTOS ELEMENTOS ENCONTRAR • Conjunto (finito o infinito) de estados.- Son TODAS las configuraciones posibles (todas las situaciones posibles) dentro del dominio del problema. • Estados iniciales.- Uno o varios de los anteriores (un subconjunto finito no vacío del • Una solución, es decir, una secuencia de conjunto de estados). A partir de estos, el acciones desde un estado inicial (datos de solucionador empieza la búsqueda. entrada) del problema hasta un estado final Representan los datos iniciales desde los que (una de sus metas). parte el problema. Si se identifican elementos relevantes del • Estados finales.- Uno o varios de los problema en el dominio de aplicación, estos nos primeros (un subconjunto finito no vacío del pueden ayudar a guiar la búsqueda de la secuencia de conjunto de estados), que son aceptados manera más eficiente (conocimiento heurístico). como meta válida. • Conjunto finito de operadores o reglas.- Describen las acciones que manipulan los estados. Son una función de transformación de un estado que lo convierte en otro u otros f(nk)={(nk+1)}. Tabla 1.- Esquema general de las tareas de búsqueda2.4.2. ¿Cómo se define un operador? Hemos dicho que un operador es una función de transformación de un estado que loconvierte en otro u otros. En este esquema, para cada operador se especificarán: • Condiciones de aplicabilidad.- Cada uno de los operadores va a definir lo que se llama “espacio de aplicabilidad” o “dominio de estados”, que serán, para cada operador, todos los estados a los que se les puede aplicar. Son las condiciones que 35.
Capítulo 2.- Métodos de resolución: La búsqueda 35 debe cumplir cada estado para poder aplicar el operador. Podemos tener varios casos de aplicabilidad: o Casos en los que se pueden aplicar todos los operadores a todos los estados en cada situación (propiedad de conmutatividad). o Según la situación, solo pueden ser aplicables unos cuantos. o Se puede aplicar un mismo operador de diferentes formas (lo que se llama “instanciación” de un operador). • Función de transformación.- Es la que determina que cambios se aplican al estado actual. El resultado de la transformación definirá un conjunto de estados resultantes (rango del operador). En cuanto al número de operadores que se han de definir para cada tipo de estado, hayque llegar a un compromiso entre el número de operadores a aplicar (si se eligen pocos, elproblema puede ser irresoluble y si se eligen muchos el coste puede ser prohibitivo) y elgrado de transformación que estos apliquen (si la transformación es mínima, el costetambién puede ser prohibitivo). Cuanto menor transformación haya, será necesario unmayor número de operadores lo que redunda en un mayor coste.2.5.- REPRESENTACIÓN DE LAS TAREAS DE BÚSQUEDA Hemos dicho que vamos a representar el proceso de la búsqueda mediante GDA. Esto esporque necesitamos la relación de orden parcial de estos (concepto de más profundo omenos profundo) que no se da en grafos dirigidos con ciclos. Se construirán a medida queavancemos hacia una meta. Antes de continuar10, vamos a definir como representamos elesquema general con un GDA: • Nodo (vértice).- Uno de los elementos del conjunto de estados.10 Para recordar más detalles sobre grafos, se puede consultar el apéndice A 36.
Inteligencia artificial: introducción y tareas de búsqueda 36 • Arco (arista).- En la expansión de un estado n, denota cada uno de los operadores aplicados a n. • Expansión de un nodo.- Dado un estado n, consiste en generar todos los posibles nodos sucesores de este, por aplicación de todos los operadores posibles y en todas sus formas de aplicación (todas sus instanciaciones). • Nodo meta.- Es un nodo terminal u hoja que cumple los objetivos del problema (que constituye una meta del problema). • Nodo frontera.- Nodo que está en espera de ser expandido. • Frontera de expansión.- Conjunto de nodos frontera. • Nodo (estado) cerrado.- Nodo que ya se ha expandido completamente. • Nodo (estado) abierto.- Nodo al que todavía le quedan sucesores que obtener. • Coste (computacional) de un arco.- Es un valor numérico positivo. Se define como el tiempo consumido al aplicar un operador dado a un estado (a un nodo). Si no se dice nada, su coste implícito será 1. • Coste (computacional) de un nodo.- Es un valor numérico positivo. Se define como el tiempo consumido en alcanzar ese nodo desde la raíz, por el mejor camino encontrado. • Coste (computacional) real de un nodo.- Es un valor numérico positivo. Se define como el tiempo consumido en alcanzar este nodo desde la raíz. • Coste (computacional) entre dos nodos.- Es un valor numérico positivo. Se define como la suma de los costes de todos los arcos que van desde un nodo hasta otro. Si los nodos son na y nb, entonces el coste se representa como C(na, nb) 37.
Capítulo 2.- Métodos de resolución: La búsqueda 37 • Factor de ramificación.- Número “medio” de sucesores (operadores) de un nodo (aplicables a un estado). Este valor es la media de operadores de todos los estados expandibles, pues cada uno de estos puede tener distinto espacio de aplicabilidad. • Longitud de una trayectoria.- Número de nodos generados a lo largo de un camino, o lo que es lo mismo, número de operadores aplicados a lo largo de ese camino. • Profundidad del grafo.- Longitud (número de niveles del grafo) desde el nodo inicial hasta el nodo meta por el camino más corto, o lo que es lo mismo, número de operadores (número de arcos) aplicados a la solución desde el estado inicial al estado meta. La profundidad del estado inicial (raíz en los árboles) es 0 y la profundidad de cualquier otro nodo será la de su antecesor menos profundo más 1 (podemos tener un GDA en el que, en un nodo dado, puede tener más de un antecesor o padre; entonces su profundidad es la del antecesor menos profundo -el que menos ha costado de calcular- más 1). • Recorrido de un grafo.- Se trata de visitar todos los nodos a partir del nodo raíz. Existen dos tipos de recorrido (se tratan detalladamente en el siguiente capítulo): o En amplitud o anchura.- Se recorre el grafo en niveles: desde la raíz, se visitan todos los nodos sucesores de este. Una vez terminados todos estos sucesores, se recorren los descendientes de estos últimos, y así sucesivamente, hasta encontrar una solución, si existe. o En profundidad.- Se visita la raíz, se expande el nodo y se visita uno de sus sucesores. Se expande este último y se visita uno de sus sucesores. Si se llega a un callejón sin salida11, se retrocede un nivel12 . Si en este nivel no quedan nodos para expandir, se sube otro nivel (así hasta que no queden nodos o se encuentre un nivel con nodos para expandir). Si hay, se expande el nodo de ese nivel para seguir el mismo proceso. De este modo se avanza una vez en cada nivel, hasta encontrar una solución, si esta existe.11 Ver la definición en la búsqueda por tentativas del siguiente punto.12 Este retroceso (backtracking en inglés) se conoce como cronológico, pues se retrocede al nivel inmediatosuperior. Existen otros retrocesos que dependen del estado del problema y no solo del anterior estado. 38.
Inteligencia artificial: introducción y tareas de búsqueda 38 El grafo de exploración será el GDA resultante de la aplicación del método. Estegrafo contendrá todos los subgrafos resultantes del seguimiento de todos los caminosseguidos, incluidos los infructuosos. ¿Por qué no almacenar un grafo con todas las combinaciones de estados yoperadores y trazar un camino? Aunque el número de estados y operadores a aplicar seanfinitos, el número de combinaciones posibles de estos será una cantidad muy grande enproblemas medianos o grandes(normalmente de orden exponencial), por lo que nosquedaríamos sin recursos (memoria insuficiente). Aunque ya se han descrito por separado,vamos a distinguir entre dos tipos de grafos: un grafo implícito que estará formado por todaslas posibles combinaciones de estados y operadores (que es la representación de lasentidades y sus relaciones), y un grafo explícito que será el que se va formando conforme vaavanzando la búsqueda, y que es el que hemos llamado grafo de exploración.2.6.- CLASIFICACIONES DE LAS TAREAS DE BÚSQUEDA Hemos dicho anteriormente que la búsqueda es una secuencia de acciones en unorden, determinado este por la estrategia de control. Según la información utilizada paraavanzar hacia una meta, las tareas de búsqueda se pueden clasificar: • Búsqueda ciega o exhaustiva.- En esta estrategia se generan estados para luego comprobar si estos cumplen con los objetivos para ser meta; si no son meta, se siguen generando otros estados. Al no tener en cuenta el conocimiento del dominio disponible (de ahí el nombre de ciega), no puede dejar ningún nodo de todos los posibles sin examinar (de ahí el nombre de exhaustiva). Es por ello que su complejidad será la del problema, exponencial en la mayor parte de los casos, lo que deriva en que estos procedimientos solo sirvan para problemas pequeños. • Búsqueda heurística o informada.- La estrategia de control utiliza conocimiento del dominio para estimar cual es siguiente mejor estado. Dado que la búsqueda es un proceso dinámico, la estrategia de control utiliza toda la información disponible hasta ese momento. El objetivo de esta dirección informada es que el número de operadores a aplicar a un estado sea bastante menor que en la exhaustiva (menos 39.
Capítulo 2.- Métodos de resolución: La búsqueda 39 caminos inútiles), y por lo tanto mejore apreciablemente la eficiencia promedio del algoritmo (en el caso peor podría ser la misma que la búsqueda ciega). Hay que tener muy claro que las técnicas heurísticas no eliminan estados u operadores, sino que intentan mejorar el coste del camino a una meta. Otra clasificación que se puede hacer es por la forma en la que se avanza en labúsqueda: • Búsqueda de tentativas.- Se avanza en una dirección y si se llega a un punto en el que se supone que no se llega a alguna meta, se abandona este camino para retomar alguno anterior que también prometía. Esta situación se puede dar: o Cuando a un estado no se le pueden aplicar operadores y además no es meta. A esto lo llamamos callejón sin salida, vía muerta o punto sin retorno. o Cuando las técnicas heurísticas estimen que hay un camino mejor que el que se está siguiendo. • Búsqueda irrevocable o sin vuelta atrás.- Una vez que se ha tomado un camino, este no se puede dejar. La búsqueda de tentativas se puede dar tanto en exhaustivas como informadas, mientrasque la irrevocable solo en las informadas. Si no se dice lo contrario, las tareas de búsquedaque se verán lo serán por tentativas. Otra clasificación será según la naturaleza del problema. La búsqueda podrá ser: • Búsqueda dirigida por los datos o encadenada hacia delante.- Consiste en seguir algún procedimiento para encontrar alguna meta. El problema se plantea como una situación inicial a partir de la cual se realiza una secuencia de acciones (aplicación de operadores) para llegar a una situación que cumpla ser una meta. También se la llama búsqueda de arriba - abajo. • Búsqueda dirigida por las metas o encadenada hacia atrás.- Consiste en, dada una solución conocida, encontrar el procedimiento para llegar a esa solución. En estas se parte de una meta, a la que se le aplica algún operador que la transforma en 40.
Inteligencia artificial: introducción y tareas de búsqueda 40 una o más submetas de un menor tamaño o dificultad. Cada submeta se puede transformar en una o más submetas de manera recursiva, hasta que estas sean lo suficientemente triviales para ser solucionadas en el nivel simbólico. También se la llama búsqueda de abajo-arriba. La mayor parte de los problemas de I.A. son planteados en términos de búsquedasdirigidas por las metas.2.7. CLASIFICACIÓN Y APLICABILIDAD DE LOS OPERADORES Vamos a clasificar los operadores por su capacidad de reversibilidad: • Operadores irreversibles.- Tras su ejecución no se puede volver al estado anterior. • Operadores semi-reversibles.- Tras su ejecución se puede volver al estado anterior, pero si se dispone de recursos para ello. Si no los hay, entonces se consideran operadores irreversibles. • Operadores reversibles.- Se puede obtener el estado anterior sin consumir recursos. Estos a su vez pueden ser reversibles con solo una operación o requerir la ejecución de varias operaciones para llegar al estado padre (complica la reversibilidad).2.8. ESQUEMAS DE REPRESENTACIÓN Antes de describir los dos esquemas de representación posibles, vamos a definir unostérminos generales: • Espacio de representación o espacio del problema.- Es el entorno dentro del cual se realiza la búsqueda. Este espacio estará formado por: o El conjunto de todos los estados. o El conjunto de todos los operadores. 41.
Capítulo 2.- Métodos de resolución: La búsqueda 41 El espacio de representación dará una idea de la complejidad del problema (la combinación de ambos puede llegar a ser intratable, computacionalmente hablando). • Instancia de un problema.- Es un conjunto de estados en el que se dice cual es el inicial y uno de las posibles metas (si hay más de una). De manera general, en todas las tareas de búsqueda vamos a tener una base de datos detrabajo en la que almacenaremos el estado inicial y todos los que se vayan obteniendosucesivamente a partir del primero. Se mantendrán dos estructuras de datos que llamaremosABIERTA y CERRADA: • ABIERTA.- Contendrá todos los estados abiertos. Es decir, contiene la frontera de expansión. • CERRADA.- Contendrá todos los estados cerrados, y por tanto no se van a volver a visitar (esta no existirá en alguno de los métodos que veremos). Vamos a tener dos esquemas generales de funcionamiento, distintos según el problema asolucionar: • Esquema de producción.- También llamado de búsqueda en el espacio de estados. • Esquema de reducción.- Responde a la posibilidad de que el problema se pueda descomponer en subproblemas más pequeños. También llamado de búsqueda en el espacio de reducción.2.8.1. Esquema de producción Al espacio del problema se denomina “espacio de estados”, y en este planteamiento, labúsqueda consiste en la aplicación de un único operador a un único estado, y se obtienecomo resultado un único estado. Este estado es un nuevo “paso” en el proceso de búsqueda.Este esquema es propio de las búsquedas guiadas por los datos o encadenado hacia delante.La equiparación es el proceso por el cual se comprueba la aplicabilidad de un operador. 42.
Inteligencia artificial: introducción y tareas de búsqueda 42 La estrategia de control procederá de la siguiente manera: 1.- Selecciona un nodo. 2.- Equiparación: Determinar los espacios de aplicabilidad a los que pertenece (operadores aplicables al nodo seleccionado en el punto anterior). 3.- Conforme a algún criterio, elige uno de los operadores aplicables al nodo seleccionado y lo aplica. 4.- Se determina si el estado generado es una meta. Si no lo es, y tampoco se han consumido todos los recursos, se pueden hacer dos cosas: 4.1.- Intentar aplicar otro operador, o el mismo si tiene varias formas de aplicación, de los que se puedan aplicar al nodo seleccionado (esto se verá que corresponde al recorrido en amplitud). 4.2.- Intentar aplicar el procedimiento al nuevo estado obtenido (corresponderá al recorrido en profundidad). El avance en la búsqueda será sistemático para que el algoritmo sea lo más eficienteposible (es decir, los estados y sus operadores se elegirán de manera ordenada). Laestrategia de control avanzará en la misma hacia la solución teniendo en cuenta toda lainformación obtenida hasta ese momento, es decir, considerando el proceso de formaglobal.El conjunto de estados obtenidos en el proceso de búsqueda descrito, lo representaremoscon el “grafo de exploración o de búsqueda”. Este es un GDA explícito donde cada nodoexpandido estará enlazado con un arco dirigido a su nodo predecesor y contendrá todos lossubgrafos resultantes del seguimiento de todos los caminos seguidos, incluidos losinfructuosos. Implícito en este habrá un árbol, que contendrá la solución si se llegó a esta(cada estado va a recordar cual fue su antecesor, con lo cual, para dar una solución,podemos recorrer la trayectoria desde la meta hasta el estado inicial). 43.
Capítulo 2.- Métodos de resolución: La búsqueda 43 Este esquema se utiliza en problemas en los que un solo agente intenta encontrar unasolución, tales como: • Enrutamiento de paquetes en redes de propósito general. • Desplazamiento de robots. • Búsqueda de la ruta de viaje óptima. • Diseño de circuitos integrados.2.8.2. Esquema de reducción Al espacio del problema se llama “espacio de reducción” y es el propio de lasbúsquedas dirigidas por las metas o encadenadas hacia atrás. Como ya se dijo, se pueden dardos situaciones: • Que al aplicar un operador, se produzca una única submeta, siendo esta más pequeña o simple. En este caso se actúa igual que en el esquema de producción. • Que al aplicar un operador se produzca un conjunto de submetas, siendo cada una de ellas más sencilla que su predecesora y además tratable independientemente (y por tanto simultáneamente). A este proceso de descomposición se le llama reducción de una meta. En consecuencia, en este esquema, vamos a tener dos tipos de operadores: • Los que conocemos hasta ahora, con sus condiciones de aplicabilidad y función de transformación, y que son con los que avanzamos hacia las metas. • Operadores que se encargan propiamente de descomponer la meta en submetas más sencillas. 44.
Inteligencia artificial: introducción y tareas de búsqueda 44 Se dijo que con este planteamiento se llegaría a una situación en la cual todas lassubmetas obtenidas serán lo suficientemente triviales para ser solucionadas en el nivelsimbólico. Para dar la solución al problema se pueden dar dos situaciones: • Que la solución sea la unión de todos esos subproblemas, en cuyo caso estará resuelto cuando lo así están todos los estados terminales del grafo resultante (resueltas todas las submetas). • Que la resolución de los subproblemas triviales, permita la resolución de su subproblema padre y así sucesivamente hasta llegar a la resolución completa del problema (dirigido por las metas). Para poder realizar este cometido los operadores han de ser reversibles. El conjunto de metas y submetas obtenidas en este esquema (proceso de búsqueda y desubdivisión), lo representaremos con “grafos o árboles Y/O”13. En estos, el estado raízcorresponde a la meta global y la conexión entre nodos se produce mediante enlaces. Unenlace va a tener k arcos dirigidos desde un nodo hacia sus sucesores (subproblemas mássencillos) y estos k arcos estarán unidos por una línea curva (ver figura a continuación).Podemos diferenciar dos tipos de enlaces: • Enlace O (OR).- El enlace tiene un arco dirigido hacia un sucesor, tal como lo hacía el esquema de producción. Este enlace ocurre cuando el operador es de transformación. • Enlace Y (AND).- El enlace tiene dos o más arcos dirigidos desde el nodo a sus sucesores. Este enlace ocurre cuando el operador es de subdivisión del problema. Los nodos terminales de este grafo (los que ya no se pueden subdividir más) seránresolubles si se les puede aplicar algún operador de transformación, o irresolubles si no esasí. Un nodo estará resuelto cuando lo estén los nodos de alguno de sus enlaces. Elproblema estará resuelto cuando lo estén todos los nodos terminales de uno de susenlaces, que hace que sus nodos antecesores estén resueltos (incluido en raíz). Para surepresentación, se dibujará:13 Del inglés, “AND/OR graphs”, también conocidos como grafos A/O. 45.
Capítulo 2.- Métodos de resolución: La búsqueda 45 • Los enlaces tal como se han descrito. • Los nodos no resueltos se representan mediante circunferencias. • Los nodos resueltos se representan mediante círculos. • Tenemos dos situaciones distintas para mostrar la solución: o Que el grafo solo tenga enlaces O.- En este caso tenemos el mismo grafo que en el esquema de producción. o Que el grafo tenga enlaces Y.- Se mostrará la solución de cada uno de los subproblemas (nodos terminales) derivados del original (la solución es el conjunto de ellos). En este ejemplo vemos el grafo de exploración final de una búsqueda con esteesquema. Implícito en él tenemos un subgrafo solución, que son los arcos continuos con losnodos resueltos. Uno nodo está resuelto si lo están todos los nodos de uno de sus enlaces.Este proceso se verá en detalle más adelante. Este esquema se utiliza para la resolución de problemas en varios campos: • Para resolver problemas en los que la solución es un conjunto no ordenado de subproblemas resueltos. Un ejemplo es el caso matemático de la integración por partes. 46.
Inteligencia artificial: introducción y tareas de búsqueda 46 • Para resolver problemas en que dos agentes compiten por un mismo objetivo. Estos problemas pertenecen a la teoría matemática de juegos y se verán mas adelante. • Problemas de razonamiento lógico y planificación por etapas. Se pasa a cada etapa cuando se cumplan todas las premisas de la etapa anterior.2.9.- MÉTODOS DE RESOLUCIÓN Ya se ha comentado que todos los métodos de resolución de problemas van a tener ala búsqueda como subtarea genérica.2.9.1. Generar – probar Estos métodos tienen dos módulos: el módulo generador de soluciones posibles y elmódulo verificador, que comprueba la validez de estas posibles soluciones generadas. Una primera aproximación sería generar todas las soluciones posibles, para luegocomprobar cuales son las válidas. Sin embargo esta solo sería apropiada para problemaspequeños, ya que para medianos o grandes, el número de estados a almacenar puede serinmenso (de orden exponencial), por lo que nos quedaríamos si recursos para sualmacenamiento. Por ello lo normal es, en este método, alternar fases de generación y deverificación. Estos métodos utilizan un esquema de producción para las tareas de búsqueda, dondelos operadores son conocidos, por tanto la equiparación es trivial. La función detransformación será inmediata, obteniendo los sucesores del estado actual. Son propios de los problemas en los que se tiene el conocimiento sobre lo que hayque hacer. Un ejemplo es la búsqueda de una contraseña por fuerza bruta (se generan todaslas posibles contraseñas hasta encontrar la que es válida). 47.
Capítulo 2.- Métodos de resolución: La búsqueda 472.9.2. Medios – fines Este método se desarrolló a través del GPS (General Problema Solving)Solucionador General de Problemas, inicialmente descrito por Newell, Simon y Shaw(1960). El objetivo de este método es identificar el medio (los operadores) para transformarla descripción de un estado con el objetivo de llegar a algún fin (alguna meta), o un estadointermedio (descripción derivada de la anterior) más cercano al fin. El procedimiento parahacer esto es reduciendo la diferencia entre la descripción del problema y una meta. Este método también utiliza el esquema de producción, donde la equiparación es denaturaleza heurística (depende del dominio) y la función de transformación es la que reducelas diferencias con la meta. Así pues, necesitamos dos tablas: • Tabla de operadores: Va a tener dos columnas bien diferenciadas : o Precondiciones.- Que establece el espacio de aplicabilidad de cada operador. o Resultados.- Que establece el rango del operador. • Tabla de diferencias: Las diferencias están ordenadas de mayor a menor importancia, en función del análisis del dominio. Para cada diferencia se establecen los operadores que reducen esta diferencia. Así la equiparación heurística es intrínseca a esta tabla. Así el proceso consiste en hacer una búsqueda con retroceso (variante del recorrido enprofundidad que veremos mas adelante) para resolver las diferencias: determinar losoperadores y su espacio de aplicabilidad y después aplicar el operador elegido para obteneruna descripción derivada o una descripción meta. Sin embargo, la equiparación NO consisteen comprobar la pertenencia del estado al espacio de aplicabilidad (almacenar el espaciopuede ser, de nuevo, prohibitivo), sino en verificar si el estado tiene una parte semejante conel operador, para poder aplicarlo. 48.
Inteligencia artificial: introducción y tareas de búsqueda 48 Hay que reseñar que, aunque el método es genérico, es muy dependiente del dominio, yaque es la tabla de diferencias la que determina la aplicación de operadores.2.9.3. STRIPPS Es una variante del método de medios-fines aplicado en robótica en la que se eliminala tabla de diferencias, estando intrínseca en la tabla de operadores, que ahora tiene doscolumnas: • Adiciones.- Elementos introducidos después de aplicar un operador • Eliminaciones.- Condiciones que se dejan de cumplir después de aplicar el operador. Las diferencias ahora son los elementos de la meta y las condiciones de aplicabilidad delos operadores.2.9.4. Reducción del problema En estos métodos se parte de una meta difícil de encontrar, que se convierte en una ovarias submetas más fáciles. Este procedimiento es recursivo hasta que se encuentran unconjunto de submetas lo suficientemente fáciles para resolver trivialmente. Estos métodos utilizan un esquema de reducción y son propios de los problemas enlos que hay que indagar como llegar a la solución. Un ejemplo de estos métodos es laprogramación, en la que se parte de una meta y esta se implementa a base de losrefinamientos sucesivos de sus funciones y procedimientos.2.10.- FORMALIZACIÓN DEL PROBLEMA Como ya se dijo antes, el problema hay que describirlo en términos formales. Se va apartir de la descripción en lenguaje natural y se va a modelar el conocimiento para lastécnicas procedimentales, identificándose las entidades con el esquema general de la tabla 1.Se deben tener en cuenta los siguientes elementos: 49.
Capítulo 2.- Métodos de resolución: La búsqueda 49 • Representar adecuadamente los elementos que participan en el proceso de búsqueda. • Estrategia de búsqueda más eficiente, con la identificación del conocimiento del dominio relevante. • Limitaciones del sistema: tiempo de ejecución y espacio de almacenamiento. • Como se eliminan los nodos y subgrafos inútiles (que no aportan información y ocupan espacio de almacenamiento inútilmente). También se ha dicho que la manera de describir estas entidades, es mediante un lenguajede representación y un procedimiento para llegar a una posible meta, que es el que controlala estrategia de búsqueda. Para poder llevar a cabo este procedimiento, necesitamos definirdos lenguajes formales, uno para cada uno de los elementos del espacio del problema: • Lenguaje de descripción de estados. • Lenguaje de operadores.2.10.1. Lenguaje de descripción de estados Se utiliza una gramática formal que define el lenguaje. Recorriendo todas las reglasde reescritura de la gramática se obtienen todos los estados válidos. Tanto las sentenciasterminales (expresiones válidas) como no terminales (sustituciones posibles) sirven comodescripciones.2.10.2. Lenguaje de operadores Cada operador definido por este lenguaje, que también se hará con una gramáticaformal, va a constar de: • Un espacio de aplicabilidad o dominio de estados. Recommended
Pt 26 may_2010

References: RESOLUCIÓN 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 RESOLUCIÓN 
 resolución