Modulo 2.pdf

Algoritmos de búsqueda: búsqueda no informada Variantes en los agentes reactivos Buscando la aptitud para resolver problemas El concepto de problema Búsqueda en el espacio de estados Métodos de búsqueda exhaustiva en el espacio de estados Referencias Lección 1 de 6 Variantes en los agentes reactivos Actividades Resolver problemas de búsqueda en el espacio de estados a través de métodos exhaustivos y heurísticos. Reconocer las formas de representar el conocimiento y los métodos de razonamiento. Como se recordará, para orientar el estudio de la inteligencia artiﬁcial (AI), se recurrió a la metáfora de agentes, a los que se interpreta como “entidades racionales que funcionan en forma continua y autónoma, en ambientes en que interactúan con otras entidades” (Russell y Norvig, 2004). Esta construcción abstracta facilita la asignación de cualidades, con la ﬁnalidad de cubrir un espectro de casos que representen entidades asociables a niveles, en una cierta escala de conductas inteligentes. Así es que Russell y Norvig (2004) propuso una escala de cinco niveles de agentes y Nilsson (2001) propuso otra, una de cuatro niveles (las dos escalas fueron descriptas en la lectura 4 de la unidad 1). En ambas clasiﬁcaciones, hay coincidencia en el primer nivel, que corresponde a los llamados agentes reactivos, de estímulo-respuesta (ER) o de reﬂejo simple. Estos agentes no son capaces de ninguna acción espontánea y su conducta queda, exclusivamente, determinada por su entorno. Es decir, sus acciones son una consecuencia directa de los estímulos percibidos en el ambiente donde operan y, a pesar de su simplicidad, debe reconocerse que, a partir de este tipo de comportamiento, se puede concebir una gran variedad de dispositivos. Incluso, en muchas oportunidades, quizás más de las deseables, los seres humanos se comportan como agentes reactivos. Puede citarse como ejemplo el caso del conductor de automóvil que aplica rápidamente su pie sobre el pedal del freno cuando advierte, a cierta distancia, algún obstáculo. Pero es necesario distinguir entre la acción reﬂeja elemental, recién citada, y la acción decidida a partir de la evaluación de otros factores. Entre estos, pueden encontrarse registros históricos de la percepción del medio (mediante sensores) y de conductas anteriores del propio agente, lo que representa información sobre la actividad cumplida y disponible para ser consultada posteriormente. En ese caso, el agente deﬁnirá su respuesta a partir de la realidad de entonces y la de los registros anteriores de desempeños similares. Por ejemplo, puede citarse el caso de una unidad de control de temperatura, donde se regula la válvula de gas no solo a partir de la temperatura actual, sino, también, considerando registros históricos de regulaciones y resultados previos. Conociendo gradientes térmicos que resultan de la evolución de la señal de entrada, se pueden prever respuestas más complejas y obtener conductas más estables. Debe notarse que memorizar una conducta anterior implica adoptar la forma de una máquina de estados, donde el agente responde según el estímulo exterior y el estado en que se encuentra como consecuencia de su historia. Es interesante comprobar que, en este caso, en que, en su conducta, el Agente considera la percepción actual y sus antecedentes, ya no hay coincidencia entre las propuestas de Russell y Norvig (2004) y Nilsson (2001). Para el primero, se trata de un segundo nivel, denominado agentes reactivos basados en modelos y, para el segundo, sigue siendo un agente de estímulo respuesta, es decir, de nivel 1. C O NT I NU A R Lección 2 de 6 Buscando la aptitud para resolver problemas Dando un paso más en esta metáfora, se van a considerar agentes capaces de buscar e identiﬁcar secuencias de acciones que los conduzcan a alcanzar las condiciones deseadas, denominadas metas u objetivos. Para Russell y Norvig (2004), se está ante agentes basados en objetivos (nivel 3) y, para Nilsson (2001), ante agentes planiﬁcadores (nivel 2). Cabe aclarar que, al confrontar ambas clasiﬁcaciones, se está buscando entender mejor las cualidades de los agentes y sus consecuencias, quedando, en un segundo plano, la posible ventaja que ofrezca alguna de ellas. Según lo expuesto, es fácil advertir que, al diseñarse una máquina reactiva, se deben anticipar las reacciones apropiadas para todas las posibles situaciones que enfrentará el agente, lo que es, en muchos casos, impracticable. O visto desde otro ángulo, el desempeño del agente queda muy acotado y condicionado a ciertos escenarios prestablecidos. Y aun, en el caso de que tal diseño fuese posible, el almacenamiento de la información necesaria para posibilitar el desarrollo de tareas relativamente complejas demandaría grandes espacios de memoria y elevados tiempos de consulta. La opción para superar estas limitaciones es procurar un agente que incorpore conductas adaptables al medio, que no requieran un diseño explícito anticipado. También, esto implica reducir el volumen de tablas y reglas que deben ser predeﬁnidas y almacenadas, a cambio de incorporar la capacidad de realizar procesos, los que tendrán la ﬁnalidad de seleccionar y respaldar las acciones que, en cada caso, tome el agente. Y estas expectativas son las que conducen a los ya citados niveles 3 de Russell y Norvig (2004) y 2 de Nilsson (2001). El primero identiﬁca, en este nivel, un agente especíﬁco para resolver problemas, que denomina agentes resuelve problemas (problema solver), mientras que el segundo los denomina genéricamente agentes planiﬁcadores. Ambos agentes disponen de la capacidad analítica necesaria para anticipar los efectos de sus acciones, lo que les permite seleccionar sus conductas entre aquellas que son, aparentemente, más apropiadas para alcanzar sus objetivos. En resumen, no existe, ahora, una relación directa entre entrada y salida, entre estímulo y respuesta. Por el contrario, hay una respuesta que es elaborada a partir de un proceso exploratorio, de búsqueda, cuya determinación constituye la solución de un problema. Por este motivo, queda encuadrado en un marco de actividad planiﬁcada. En la implementación de estos agentes, deben considerarse las variantes que puede presentar el comportamiento del dominio que constituye su medio ambiente. Estas son: 1 dominio estático: sólo afectado por las acciones del propio agente; 2 dominio dinámico: se presentan condiciones externas que muestran una variación en el tiempo y son ajenas al agente; 3 dominio interactivo: hay presencia de otros agentes que comparten el mismo medio y tienen sus propios objetivos; y 4 dominio competitivo: la actividad habitual enfrenta uno o más agentes que se constituyen en rivales en pugna por los mismos objetivos. El tiempo disponible para deﬁnir la respuesta del agente está limitado en los dominios que no son estáticos. Esto es debido a que, mientras se evalúan las alternativas, transcurre el tiempo y cambian las condiciones. Por otra parte, en los dominios interactivos, deben contemplarse las acciones de otros agentes, ya que se constituyen eventuales aliados o rivales que persiguen un objetivo común. Este último caso corresponde a dominios competitivos que requieren la exploración de situaciones idealizadas, en las que alternativamente deben considerarse todas las posibles acciones de los agentes contrincantes. La ﬁgura 1 muestra un esquema que presenta la arquitectura de un agente planiﬁcador. Figura 1: Esquema de un agente planiﬁcador Fuente: elaboración propia. C O NT I NU A R Lección 3 de 6 El concepto de problema Enfrentar un problema signiﬁca que se desea alcanzar cierto objetivo, se conocen las acciones disponibles, pero no se sabe cuáles son las apropiadas para conseguirlo. Normalmente el problema se maniﬁesta ante la existencia de alternativas para alcanzar el objetivo y el desconocimiento de cuáles y en qué orden deben ser invocadas. La decisión que se tome, seguramente, inﬂuirá en la efectividad y en la eﬁciencia de la solución elegida. En resumen, la existencia de un problema queda determinada por los siguientes tres componentes: 1 una situación o diﬁcultad inicial; 2 un objetivo o meta a alcanzar; y 3 un conjunto de acciones posibles, capaces de conducir a soluciones alternativas. El objetivo puede estar representado por algo tangible, como un objetivo físico, o algo eminentemente abstracto, como la demostración de un teorema. Por lo tanto, las acciones conducentes al objetivo serán, en algunos casos, actividades físicas y, en otros, razonamientos o actividades puramente mentales. En la inteligencia artiﬁcial, a los problemas, se los representa como un espacio de estados, que constituyen la base de la mayoría de los métodos de resolución. Tales métodos se distinguen por las siguientes dos características: 1 permiten expresar formalmente un problema y 2 posibilitan la deﬁnición del proceso de resolución de manera sistemática. En esta interpretación, un problema es reconocido como la necesidad de convertir alguna situación inicial dada en otra situación deseada, usando, para ello, un conjunto de operaciones permitidas. Se deﬁne, entonces, formalmente, un problema como una terna: P = (I,O,M) Donde: I: el estado o situación inicial en el dominio del problema; O: conjunto de todos los operadores o acciones disponibles, que puedan ser aplicadas a las instancias del espacio de estados; y M: la meta, el estado, cuya condición caracteriza la situación ﬁnal o estado objetivo. La presentación formal del problema lleva a la deﬁnición de numerosos conceptos, que son enunciados a continuación. Acción: se denomina así al resultado de aplicar cierto operador Ok a una expresión. En caso de poder aplicarse un operador a más de una expresión, queda deﬁnida una clase de acciones. Requisitos y consecuencias: toda acción disponible tiene deﬁnidas las condiciones que deben cumplir los operadores para poder ser aplicados en el estado actual y sus consecuencias, las que darán lugar a un nuevo estado. Sucesor: se dice que el estado K es sucesor del estado J, si es alcanzable a partir de J, mediante la aplicación de alguna secuencia de acciones. En caso de que K pueda ser alcanzado con una única acción, se dice que es sucesor inmediato de J o, también, que J genera a K. Figura 2: Sucesor Fuente: elaboración propia. Espacio de búsqueda o espacio de estados: es el conjunto de todos los estados que pueden ser alcanzados desde el estado, inicial aplicando los operadores disponibles. Solución de un problema: es la secuencia ordenada de operadores que, como resultado de su aplicación al estado inicial I, satisface la condición M. La inexistencia de tal secuencia de operadores prueba que un problema no tiene solución. Por el contrario, si la secuencia de operadores es un conjunto vacío, signiﬁca que el problema ya está resuelto. Objetivo: ante un problema, es factible que se requiera alguna de estas tres opciones: 1. una solución, 2. todas las posibles soluciones, o 3. la solución óptima. Estado ﬁnal: es obtenido a partir de una solución que, como ya se dijo, estará formada por la secuencia ordenada de operadores intervinientes. Estado inicial: debe disponer de la información apropiada que deﬁne el problema. Algunos de sus elementos permanecerán invariantes durante la solución y son reconocidos como hechos. Otros cambiarán conforme progrese la aplicación de los operadores y son reconocidos como condiciones iniciales. Dependiendo de cada caso, la representación de los estados podrá tomar desde formas muy simples (vectores de estados) hasta otras muy complejas. Condición de la solución: el grado de especiﬁcación con que se deﬁne el objetivo de un problema puede ser variable, lo que permite distinguir entre dos tipos de casos: 1. completamente especiﬁcados: por lo general se trata de demostraciones; Y 2. incompletamente especiﬁcados: normalmente se trata de búsquedas. La condición que debe cumplirse en la solución es formulada como una propiedad que debe ser satisfecha en cierto estado y es independiente de la distinción anterior. Tipos de objetivos: es necesario reconocer que, en la solución de un problema, puede presentarse alguno de los tres objetivos diferentes que siguen: 1. hallar la solución del problema, lo que signiﬁca identiﬁcar un estado ﬁnal; 2. hallar la forma de resolver el problema cuyo estado ﬁnal es conocido, es decir, encontrar la secuencia de operadores apropiada; o 3. alguna combinación de los anteriores. C O NT I NU A R Lección 4 de 6 Búsqueda en el espacio de estados Debe tenerse en cuenta que el esfuerzo requerido para resolver un problema es deﬁnitivamente dependiente de la forma en que este es representado. Los espacios de estados pueden ser substancialmente reducidos, empleando representaciones que restrinjan la información representada. Esto a través de la combinación de ciertos operadores, para dar lugar a otros más poderosos o, en ciertos casos, optando por descartarlos. También, un cierto problema puede ser llevado a la forma de otro equivalente para aprovechar una representación más apropiada. Esto signiﬁca que pueden admitirse múltiples representaciones de un mismo problema, todas ellas equivalentes entre sí. Las representaciones equivalentes de un problema original podrían ser reconocidas como modelos, cuya condición es rescatar sus características esenciales. Al trabajarse en la búsqueda de un modelo o representación equivalente de un problema, deben ser tenidas en cuenta las siguientes cinco condiciones: 1 claridad: relación inmediata entre el modelo y el problema real; 2 completitud: preservación de todos los aspectos esenciales del problema real; 3 concisión: omisión de características irrelevantes, redundantes e implícitas; 4 exactitud: formulación precisa y ﬁel representación de la realidad. Clara deﬁnición de sus límites de aplicación; y 5 utilidad: representación conveniente que facilite la resolución del problema. Algunos autores resumen las condiciones de completitud y concisión en estrictez: que implica que todo buen modelo debe ser tan completo como sea necesario y tan simple como sea posible. Una vez representado el problema, las operaciones constituyen transformaciones que son sucesivamente aplicadas y van alterando el estado del modelo, hasta alcanzar el estado ﬁnal, el que debe satisfacer las condiciones establecidas para la solución. La solución fue deﬁnida como una secuencia ordenada de operaciones. Debido a que las acciones no pueden ser aplicadas en cualquier momento, cada acción debe respetar ciertos prerrequisitos establecidos como precondiciones. Esto conduce a la necesidad de deﬁnir reglas que establecen las condiciones que deben ser satisfechas, para que cada una de las acciones sean aplicables. Luego, las transformaciones que provocan la aplicación de estas reglas impactan en el vector del estado y deben ser vistas como sus consecuencias. Para que el proceso de resolución de un problema sea correcto, la formulación del conjunto de reglas que representan todas las acciones disponibles debe reunir, también, ciertas características esenciales: 1 precisión: toda propuesta de acción debe estar especiﬁcada sin ambigüedad y su validez claramente delimitada; 2 consistencia: ningún subconjunto de reglas determinará que una acción es aplicable mientras que, simultáneamente, otro subconjunto determina lo contrario para esa misma acción; 3 completitud: todas las acciones permitidas en el dominio del problema deben estar especiﬁcadas; e 4 independencia: una regla no debe referenciar otras reglas, ya que solo se aplican a la estructura de representación usada. Resumiendo, la descripción formal de un problema implica: representar apropiadamente al problema y deﬁnir su espacio de estados; identiﬁcar un estado que describa la situación inicial; especiﬁcar uno o más estados como objetivos, los que representan soluciones aceptables; y especiﬁcar un conjunto de reglas que describan las acciones disponibles. Tal como la búsqueda de la solución de un problema ha sido planteada, está lo que se denomina un sistema de producción, cuyos componentes son: un conjunto ﬁnito, no vacío, de reglas; el conocimiento sobre el entorno: su espacio de estados; a estrategia de control o criterios de selección de las reglas; y el aplicador de las reglas. La estrategia de control es el elemento determinante para que un agente alcance sus objetivos. Y, en el caso de los agentes planiﬁcadores, a la posibilidad de resolver un problema, debe sumarse la rapidez con que se hace. Esto último es determinante, debido a que la estrategia de selección de las reglas incluye un proceso de exploración o búsqueda del camino apropiado, que demanda tiempo. Ahora una necesaria aclaración: es habitual, en inteligencia artiﬁcial, remitirse a juegos, para demostrar la conveniencia de una técnica, comprobar su eﬁcacia e identiﬁcar sus limitaciones. Los juegos representan escenarios apropiados para conﬁrmar aptitudes y evaluar desempeños, este último es representado por el tiempo y espacio demandado. Ejemplo Se tienen dos jarras, una de ellas de cuatro litros de capacidad y la otra de tres. Ninguna de ellas tiene una marcación que permita reconocer el volumen del contenido y se dispone de un dispositivo que permite llenar las jarras, vaciarlas o trasvasar líquido de una a la otra. Se desea deﬁnir un procedimiento que asegure un volumen de dos litros en la jarra de cuatro litros de capacidad. Representación del problema El problema es representado por un par ordenado (x, y) que considera el contenido de la jarra grande (x) y de la chica chica (y), respectivamente. El espacio de estados queda, entonces, deﬁnido por todos los diferentes vectores (x, y), donde se adoptan variables reales para representar apropiadamente los llenados x e y. Espacio de estados La representación de este espacio de estados es una superﬁcie continua, ya que está constituido por inﬁnitos vectores que corresponden a todas las posibles combinaciones, donde 0 ≤ x ≤ 4 y 0 ≤ y ≤ 3. Entre estas, se encuentran los estados inicial y ﬁnal, como se observa en la ﬁgura 3. Figura 3: Estado de espacios Fuente: elaboración propia. Si por simplicidad se asume que x e y solo toman valores enteros, el espacio de estados se convierte en discreto. En este caso, se distinguen veinte condiciones diferentes, que son representadas en la ﬁgura correspondiente. Para facilitar la interpretación de esta forma de representar un problema, se representa, en ambos modelos, el estado inicial (I) y la meta (M). Se sugiere al lector comprender la posición asignada a ambos estados extremos en el modelo discreto y los casos en que las metas fueran el estado N (2,3) y Q (4,1). Conjunto de reglas disponibles El conjunto de acciones posibles, para operar con las jarras, es especiﬁcado en forma de reglas y representadas en una tabla que detalla el signiﬁcado de cada regla, la condición a cumplir por el vector de estado para poder aplicarse y la consecuencia de cada acción o regla en el vector de estado. Al estar claramente deﬁnidas las condiciones y las consecuencias, la posibilidad de resolver el problema se traslada a la posibilidad de seleccionar una secuencia de acciones apropiadas que permita navegar el espacio de estados desde el objetivo a la meta. La referida tabla es, en este caso, la que contiene la tabla 1. Tabla 1: Conjunto de reglas disponibles N.º Condición Consecuencia Interpretación 1 (x,y) ;x0 (x,0) Vaciar totalmente la jarra chica 5 ( x , y ) ; x+y ≥ 4 ( 4 , y – ( 4 – x)) Completar jarra “x” desde jarra “y” 6 ( x , y ) ; x+y ≥ 3 ( x – ( 3 – y ), 3 ) Completar jarra “y” desde jarra “x” 7 ( x , y ) ; x+y ≤ 4 (x+y,0) Verter toda la jarra “y” en la “x” 8 ( x , y ) ; x+y ≤ 3 (0,x+y) Verter toda la jarra “x” en la “y” Fuente: elaboración propia. Figura 4: Fuente: elaboración propia. Una de las secuencias de reglas que pueden ser aplicadas para alcanzar el objetivo es la presentada en la tabla 2 y la solución del problema queda representada como un camino, en el espacio de estados. La solución del problema de las jarras se muestra en los dos gráﬁcos siguientes (ﬁgura 5), donde en el de la derecha, se representan las secuencia de acciones y la reglas aplicadas, en cada caso separadas entre sí, en el rótulo, por una barra. Tabla 2: Secuencias que pueden ser aplicadas Fuente: elaboración propia. Figura 5: Solución al problema Fuente: elaboración propia. La pregunta surge naturalmente, ¿cómo encontrar, de manera sistemática, una solución en problemas de este tipo? La deﬁnición de procedimientos que tengan esta ﬁnalidad y que sean aptos para resolver problemas complejos es el objeto de los temas que se presentan en el resto de esta unidad. Se denomina algoritmo a un conjunto ﬁnito de reglas, que, al ser aplicadas en una secuencia determinada, conducirán a la solución de un problema en tiempo ﬁnito, es decir, un número ﬁnito de intervalos de tiempo. Sin embargo, debe advertirse que no todos los problemas disponen de un algoritmo que los resuelva y es, en este caso, que la inteligencia artiﬁcial utiliza los denominados métodos débiles, que son aquellos que se apoyan, mayormente, en búsquedas exhaustivas en el espacio de estados. Sin embargo, este espacio de estados es, generalmente, tan extenso que resulta imposible estudiarlo de manera completa, por lo que resulta necesario reducir el espacio de búsqueda, limitando la zona a explorar, lo que tiene dos consecuencias inevitables: la posibilidad de no encontrar la solución, aunque exista; y la necesidad de conformarse con una solución, sin ninguna posibilidad de saber a qué distancia está de ser la mejor. Ambas incertidumbres son consecuencias de la imposibilidad de afrontar la demanda de recursos de la solución del problema en su dominio completo: el espacio requerido y el tiempo de búsqueda asociado. Los procesos de búsqueda establecen un isomorﬁsmo entre la secuencia de operadores que solucione un problema y un camino a través de un grafo dirigido. Así, cada nodo del grafo representa un estado y existirá, como ya fue anticipado, un arco entre los nodos J y K cada vez que exista un operador O que transforme el vector de estado J en el K. También que, en este caso, el nodo K es denominado sucesor inmediato de J y el nodo J es el antecesor de K. Algunas deﬁniciones propias del grafo dirigido son: 1. dos nodos vinculados por 2. se un arco son denominados adyacentes; llama factor de ramiﬁcación al número de sucesores inmediatos que tiene un nodo y cabe acotar que solo son de interés aquellos casos donde esta cantidad es ﬁnita; 3. toda secuencia de nodos K1,..., Km, donde cada nodo genérico Kn+1 es sucesor inmediato de Kn, es denominado camino de tamaño m; 4. se dice que Km es un descendiente de K1, si existe un camino entre ambos nodos; 5. todo camino, 6. un en que cada uno de los nodos, se encuentra una sola vez y se denomina camino elemental; camino cerrado, en el que los nodos inicial y ﬁnal coinciden, es denominado contorno; 7. si se puede establecer siempre un camino entre dos nodos cualquiera de un grafo. se dice que es conexo; 8. todo árbol es, entonces, deﬁnido como un grafo conexo ﬁnito desprovisto de contornos, luego, un árbol es un caso especial de grafo, en el cual, cada nodo tiene un solo antecesor, excepto el inicial o nodo raíz; 9. al nodo raíz de un árbol se le asigna profundidad cero y la profundidad de cualquier otro nodo es la de su antecesor incrementada en uno; 10. a los nodos sin sucesores en un árbol, se los denomina terminales u hojas y a los arcos se los denomina ramas; 11. el costo de un camino es el de las acciones que representa y resulta de la suma de todos los arcos que conectan sus nodos; y 12. se denomina camino óptimo al camino entre dos puntos de mínimo costo. El grafo correspondiente a un espacio de estados puede ser completamente deﬁnido a partir del conjunto de operaciones propias del problema estudiado. El objetivo de un procedimiento de búsqueda es encontrar un camino entre la conﬁguración o estado inicial y la conﬁguración o estado ﬁnal. Este procedimiento puede efectuarse en dos sentidos y esta elección puede tener un fuerte impacto en la eﬁciencia del proceso de resolución de un problema. Estos son: 1. búsqueda hacia delante (forward): consiste en comenzar con la aplicación de las acciones u operadores al estado inicial, para proseguir hasta alcanzar el estado ﬁnal; y 2. búsqueda hacia atrás (backward): en este caso, las acciones u operadores son aplicados al estado objetivo. Esto implica seleccionar las reglas, cuyo consecuente es válido en el estado ﬁnal, y avanzar progresivamente en sentido ascendente hasta alcanzar el estado inicial. C O NT I NU A R Lección 5 de 6 Métodos de búsqueda exhaustiva en el espacio de estados Los métodos de búsqueda exhaustiva, también, son denominados no informados, dos conceptos directamente relacionados. En efecto, la falta de información sobre la conveniencia de alcanzar uno u otro estado conduce a que el proceso de búsqueda solo se apoye en la topología del árbol, es decir, en la disponibilidad de ramas a partir de cada nodo. Luego, la complejidad del proceso será directa consecuencia del factor de ramiﬁcación medio del árbol y de la profundidad a la que se encuentre la solución. Esto implica una búsqueda exhaustiva, que es la necesidad de recorrer ordenadamente todo el árbol, hasta alcanzar el nodo objetivo o meta. Los dos métodos exhaustivos básicos son: primero en anchura y primero en profundidad. Método exhaustivo primero en anchura Se comienza a construir el espacio de estados con la aplicación de todos los operadores disponibles a partir del estado inicial, así se obtienen todos los nodos correspondientes a un primer nivel de profundidad. En forma ordenada, se repite la misma operación con cada uno de los nodos ya desarrollados, para obtener un segundo nivel de profundidad. Y estas operaciones se repiten sucesivamente, nodo tras nodo y nivel tras nivel, hasta alcanzar la profundidad en la que se encuentra el nodo meta, que representa haber alcanzado la solución del problema. Es el más simple de todos los métodos de búsqueda. El ordenamiento de la secuencia con que los nodos son explorados corresponde a operar con una pila FIFO (primero en entrar, primero en salir). Ventajas 1 Se garantiza la solución siempre que ésta exista. 2 Cuando hay numerosas soluciones se las identiﬁca a todas. 3 Se puede conocer la solución de menor costo. 4 No hay posibilidad de quedar atrapado en ciclos cerrados. Inconvenientes Requiere la generación y almacenamiento de todo el árbol, con el esfuerzo y capacidad de almacenamiento que esto implica. Método exhaustivo primero en profundidad Aplicando uno de los operadores disponibles, se genera sólo un sucesor del estado inicial o nodo raíz y se repite el mismo proceso en cada nivel de profundidad. Es así que la búsqueda de la solución prosigue a lo largo de una única rama del árbol, estableciéndose una profundidad límite, para evitar un descenso a profundidad excesivo. Alcanzado este límite, se detiene la generación de sucesores y se regresa atrás, hasta el nodo antecesor que permita la aplicación de una regla alternativa, reiniciándose, así, la exploración de la nueva rama, hasta alcanzar nuevamente la profundidad límite. De esta manera, se recorre el árbol ordenadamente. Debe observarse que la profundidad límite hace descartar la parte inferior del árbol, por lo que debe estar apoyado en alguna evidencia de que la meta está a un menor nivel de profundidad. El ordenamiento de la secuencia con que los nodos son explorados corresponde a operar con una pila LIFO (último en entrar, primero en salir). Ventajas 1 Requiere memoria moderada, ya que sólo almacena la rama que está siendo explorada. 2 Una solución puede encontrarse sin tener que desarrollar todo el árbol. Inconvenientes En caso de haber ciclos cerrados, que son posibles, el proceso de búsqueda puede quedar atrapado en caminos sin salida. No puede asegurarse que la solución encontrada sea la mejor, ya que es posible que en ramas aún no exploradas pueda haber otras soluciones a menor profundidad. Este proceso de búsqueda puede conducir a caminos inﬁnitamente largos, sin éxito, y no determinar un algoritmo. Para tornar efectivo este proceso, es necesario incorporar la noción de profundidad límite. Ejemplos de ambos métodos A continuación, se muestran los esquemas donde se representan los procesos de exploración del espacio de estados, procurando alcanzar el objetivo a través de los dos métodos básicos (ﬁgura 6). Figura 6: Procesos de exploración del espacio de estados Fuente: elaboración propia. Se pone aquí énfasis y se invita al lector a comprobar que, si la descendencia de cada nodo es cargada en una pila que se toma como referencia, según se trate de un acceso FIFO o LIFO, se cae naturalmente en el método en anchura o en el método en profundidad. El método de búsqueda primero en profundidad admite una variante muy interesante, que es denominada de descenso iterativo. Con esta técnica, se procura combinar la demanda lineal de memoria, que es moderada y propia de este método, con la necesidad de procurar asegurar la identiﬁcación del nodo objetivo más próximo al nodo inicial. El procedimiento consiste en realizar sucesivas búsquedas primero en profundidad, aumentando progresivamente la profundidad límite en cada paso, hasta encontrar el nodo objetivo. Con anterioridad se aclaró que, en inteligencia artiﬁcial, era habitual remitirse a juegos para comprobar el funcionamiento de los métodos propuestos. Esto es lo que hacemos a continuación, mostraremos el procedimiento de la solución de un puzzle de nueve piezas, mediante el método exhaustivo de primero en anchura. Cada estado/nodo está identiﬁcado con una letra y cada nivel con un número sobre el margen derecho. El estado de un nodo respecto de un sucesor cambia conforme la “movida” realizada y el contenido de las nueve posiciones están asociado al “vector estado.” El árbol parcial de la solución del puzzle es el que se observa en la ﬁgura 7. Figura 7: Árbol parcial de la solución del puzzle Fuente: elaboración propia. Puede observarse que cada “acción” corresponde al desplazamiento de una pieza, de manera tal de no retroceder a una posición anterior. Los sucesivos movimientos sistemáticos, realizados en forma ordenada y progresiva, van desplegando el espacio de estados del problema. A medida que se progresa, se va tomando noción de su inmensidad, a pesar de que solo se ha avanzado en los primeros niveles. En el caso de que la solución demande una profundidad moderada, estaría bien considerar que ese valor es P = 10. Con respecto al factor de ramiﬁcación R, sin considerar los retrocesos, puede ser de 1, 2 o 3, dependiendo de que el espacio a ocuparse esté en el centro, en el lateral o en un vértice. Podría aceptarse un valor R = 2. Luego, la cantidad de nodos a desarrollar es N = RP = 210 = 1024 estados. Este análisis muy simpliﬁcado tiene la ﬁnalidad de conﬁrmar que los espacios de estados toman rápida e inesperadamente dimensiones insospechadas, a pesar de tratarse de un problema tan simple, lo que ampliamente justiﬁca los esfuerzos para encontrar métodos alternativos más ágiles, incluso, a costo de no encontrar la solución óptima. Se completa la presentación con el método primero en anchura sobre el mismo puzle, en la ﬁgura 8. Figura 8: Método primero en anchura sobre el mismo puzzle Fuente: elaboración propia. Obsérvese que, en este caso, al conocerse los sucesores de un cierto nodo, solo se prosigue con uno de ellos y se continúa avanzando hacia abajo, hasta un cierto punto. En este caso, se reconocen 17 sucesores, para lo cual se alcanza un nivel de profundidad 8. Naturalmente, habría que continuar avanzando en profundidad hasta encontrar la conﬁguración deseada. En la solución anterior en anchura, se reconocieron 21 sucesores en niveles completos, con una profundidad 3 y, también, hay que continuar explorando el espacio de estados, hasta llegar a la meta. En ambos casos, se aprecia que, progresivamente, se van reordenando las piezas y se podrían plantear varios interrogantes: deﬁnida una meta, cuántos movimientos requiere cada método y en qué nivel está la solución. Como puede apreciarse, la fortuna podría hacer ventajoso uno u otro método, en los casos en que la meta esté en los caminos por donde se inician los procesos. La fortuna parecería ser menos necesaria si, por ejemplo, se requiere conocer todas las soluciones posibles para identiﬁcar la mejor. En este caso, el método más conveniente sería en anchura, salvo casos muy especiales. Y, si se requiere encontrar una solución a gran profundidad, el método en profundidad debería ser ventajoso. También, deben considerarse los recursos necesarios. Operar en anchura implica almacenar todo el árbol, lo que demandará un espacio de memoria muy grande, que puede ser insospechado y no estar disponible. Se invita al lector a seguir ambos casos, compararlos y comprobar que operan según modelos FIFO y LIFO. Además, se pueden plantear interrogantes curiosos, por ejemplo, ¿cuántos movimientos son necesarios para llegar, por ambos métodos, a la conﬁguración inicial? Es decir, comenzar a mover piezas hasta poder dejar a las nueve en la posición en que estaban al comenzar. Y tratándose siempre de nueve piezas, ¿cada método demanda siempre una misma cantidad de movimientos para cada caso (anchura y profundidad)? Como pregunta asociada, a las que venimos haciendo, y dirigida al lector, ¿hay algún método especial que haga más breve este proceso? Dejando de lado los procesos exhaustivos generales ya vistos, se pueden implementar procesos especíﬁcos para resolver determinados problemas, entre los que el antes planteado sería uno de estos casos. Estos procesos reducirían el nivel del agente, ya no merecerían el caliﬁcativo de “planiﬁcador” que les asignó Nilsson (2001) al no haber involucrado un proceso general de búsqueda, sino una respuesta a un problema concreto. La solución se alcanzaría de manera sistemática, a través de una secuencia automática. Aquí, cabe aclarar que la frontera entre una conducta razonadora y otra automática puede ser difusa. Volviendo a la pregunta asociada, opinamos que los procesos en el espacio de estados, que después de cierta cantidad de acciones (movimientos) dejen el tablero en la condición inicial, son posibles. No solo eso, el proceso óptimo demandará 64 movimientos, si el espacio vacío está en un lateral y 66 movimientos si está en el centro. Invitamos al lector a que proponga un procedimiento e indique su costo. Otros métodos exhaustivos Además de los tres métodos ya citados (primero en profundidad, primero en anchura y descenso iterativo), que son, indudablemente, los habituales, es decir, lo más utilizados; también, debe considerarse la búsqueda bidireccional. No se trata, en realidad, de un nuevo método, sino de una aplicación ingeniosa del método primero en anchura. La idea es realizar dos búsquedas simultáneas, donde la primera corresponde al proceso tradicional de avanzar desde la raíz hacia el objetivo. En la segunda, se avanza desde el objetivo hacia la raíz, con la ﬁnalidad de que ambos procesos se encuentren en algún punto del espacio de estados, a mitad de camino, entre ambos nodos extremos. Esta aplicación de un mismo método en forma simultánea está reservada a primero en profundidad, a raíz de su barrido progresivo de cada nivel de profundidad. Nunca podría ser aplicado primero en anchura, ya que sería muy remota la posibilidad de que dos caminos, que se inicien en cada extremo, se encuentren. No obstante, aun en anchura, deben tomarse algunas precauciones para asegurar su éxito (Russell y Norvig, 2004). Desafío propuesto a partir de las notas anteriores Se ha dado un primer paso, al tomar contacto con la resolución de problemas de búsqueda, en el espacio de estados a través de métodos exhaustivos. Al mismo tiempo, se tomó contacto con una forma algo más evolucionada dentro de ese tipo de agentes que Russell y Norvig (2004) denomina “basados en objetivos” y Nilsson (2001) denomina “planiﬁcadores”. En la próxima lectura, se avanzará en este tema, al tratarse una forma más evolucionada de estos agentes, que se valdrán de heurísticas. Mientras tanto, se invita al lector a procurar responder a los interrogantes que se presentan a continuación, una vez que haya completado la lectura de estas notas. Luego, el siguiente paso será leer el Capítulo 3 de Russell y Norvig (2004, pp. 78-88) y el Capítulo 3 de García Serrano (2012, pp. 29-55), en los que se tratan los mismos temas con mayor amplitud y desde otros puntos de vista. Por último, se debe volver sobre las preguntas aquí formuladas y las respuestas propuestas, con un espíritu de autocontrol ﬁnal. La intención es estimular una mirada crítica sobre el trabajo realizado, desde una posición de mayores conocimientos sobre los temas tratados. Se reitera que estas preguntas tienen como única ﬁnalidad contribuir a que el estudiante compruebe, por sí mismo, sus conocimientos, ya que no se trata de una instancia de evaluación. Las consignas son las que siguen. 1 A partir de lo visto hasta ahora, perfeccionar el paralelismo entre los agentes de Russell y Norvig (2004) y de Nilsson (2001), considerando los tres primeros niveles del primero y los niveles equivalentes del segundo. Hacerlo desde la visión de la resolución de problemas. 2 Identiﬁcar las ideas centrales referidas a la resolución sistemática de problemas. 3 Identiﬁcar las ideas centrales con respecto a la búsqueda exhaustiva de una solución en el espacio de estados y sus limitaciones principales. C O NT I NU A R Lección 6 de 6 Referencias Benítez Iglésias, R. (2013). Inteligencia artiﬁcial avanzada. España: Editorial UOC (Universitat Oberta Catalunya). García Serrano, A. (2012). Inteligencia artiﬁcial. Fundamentos, práctica y aplicaciones. España: RC Libros- Alfaomega. Kumar Saha, S. (2011). Introducción a la robótica. España: McGraw-Hill. Kvitka, A. (1988). Resolución de Problemas con Inteligencia Artiﬁcial. Editorial EBAI. Masip Rodó, D., Escudero Bakx, G., Benítez Iglésias, R., Kanaan Izquierdo, S. (2015). Inteligencia artiﬁcial avanzada. España: Editorial UOC, S. L. Nilsson, N. (2001). Inteligencia Artiﬁcial, una nueva síntesis. España: Editorial McGraw Hill. Ponce Cruz, P. (2011). Inteligencia Artiﬁcial con aplicaciones a la Ingeniería. Editorial Alfaomega/Marcombo. Reyes, F. (2013). Robótica. Control De Robots Manipuladores. Editorial Alfaomega. Rich, E. y Knight, K. (1991). Inteligencia Artiﬁcial. Editorial McGraw Hill. Russell, S. J. y Norvig, P. (2004). Inteligencia artiﬁcial. Un enfoque moderno. 2° Ed. España: Pearson. Winston, P. (1994). Inteligencia Artiﬁcial. Editorial Addison Wesley. C O NT I NU A R Algoritmos de búsqueda: Búsquedas heurísticas La justi cación de las búsquedas heurísticas Métodos débiles y fuertes de la IA Funciones de evaluación y métodos heurísticos E ciencia de los procesos de búsqueda Referencias Lección 1 de 5 La justiﬁcación de las búsquedas heurísticas Actividades Resolver problemas de búsqueda en el espacio de estados a través de métodos exhaustivos y heurísticos. Como ya fue comprobado, encontrar la solución a ciertos problemas, con los métodos exhaustivos, implica estudiar una explosión combinatoria de posibilidades. La principal razón por la que, con estos métodos, deba acudirse a técnicas tan poco eﬁcaces, es porque no se tienen en cuenta las particularidades del problema a resolver. Esto fue rápidamente advertido por los precursores de la inteligencia artiﬁcial, quienes, desde el comienzo, orientaron las investigaciones hacia la obtención de mayor eﬁciencia en la resolución de problemas. Así, se descubrió la conveniencia de llegar a un compromiso que signiﬁque resignar la solución óptima, a cambio de una buena aproximación que tenga menor demanda de esfuerzo. Para ello, la inteligencia artiﬁcial introdujo los métodos heurísticos. La palabra heurística viene de la palabra griega heuriskein, que signiﬁca descubrir. Esta palabra es, también, el origen de eureka, que deriva de la famosa exclamación de Arquímedes: heureka (lo descubrí), que usó al encontrar un método para determinar la pureza del oro. Como se verá, el modelo heurístico es antinómico del racional-cientíﬁco, pues no responde, necesariamente, a las reglas de un proceso lógico, ni a las del cientíﬁco-racional, ni a una aproximación analítica-reduccionista en todos sus términos. En efecto, estos métodos están destinados a resolver, eﬁcientemente, problemas difíciles, no garantizando la mejor solución, pero sí, un objetivo principal es la reducción considerable del esfuerzo requerido. Más aún, aunque parezca una paradoja, se reconoce que, en muchos casos, lo más importante es llegar a una solución con los recursos disponibles y, en mucho menor medida, alcanzar la solución óptima. Por este motivo, la clave de los procesos heurísticos es ahorrar tiempo de proceso y espacio de almacenamiento, evitando recorrer caminos innecesarios. No consiste en eliminar anticipadamente una parte del espacio de búsqueda, sino en introducir información adicional que guíe el recorrido realizado, lo que implica introducir reglas de control heurístico en el proceso de búsqueda. En síntesis, lo anterior signiﬁca que, usando buenas heurísticas, aunque ocasionalmente una buena ruta sea pasada por alto, se obtendrán soluciones apropiadas, no óptimas, para problemas difíciles, con demandas de recursos compatibles con las posibilidades. La principal diferencia entre este tipo de búsqueda y la que no empleaba información del dominio (búsqueda a ciegas) es que, ahora, a cada nodo, se le asociará un valor que dará idea de lo cerca que se encuentra de un nodo meta. Evidentemente, dicho valor no será más que una estimación de la distancia real a la meta. Distancia como concepto general, es decir, la diferencia entre ambos vectores de estado. La incorporación de este tipo de información, normalmente a través de las llamadas funciones de evaluación heurística, permitirá guiar la búsqueda por caminos que son evaluados como los más prometedores. Las consideraciones que sirven de soporte, a los procesos de búsqueda heurística, son: rara vez se requiere una solución óptima y, normalmente, una buena aproximación representa una solución apropiada; a pesar de que una aproximación heurística no asegura la mejor solución, es cierto que, en la práctica, las encontradas no tienen por qué ser las peores, y la implementación de una técnica heurística, a menudo, trae como consecuencia una mejor comprensión de los problemas. Introducir métodos heurísticos es introducir estrategias de control en las búsquedas, a partir de la utilización de funciones que permitan comparar la conveniencia de un cierto estado en relación con otros. Así, la búsqueda se centra en los nodos que tengan mejores posibilidades de conducir al estado objetivo, reduciéndose, de hecho y de manera importante, el espacio de estados. C O NT I NU A R Lección 2 de 5 Métodos débiles y fuertes de la IA Las entidades de la inteligencia artiﬁcial débil actúan de acuerdo a reglas previstas, sin poder ir más allá de ellas. Se debe reconocer que no gozan de autonomía (cualidad ya deﬁnida), luego, y estrictamente hablando, no pueden ser considerados inteligentes. Estas entidades están destinadas a una simulación de la función cognitiva humana, es decir, dan la apariencia de que piensan, pero no son realmente conscientes en ningún sentido de la palabra. Un buen ejemplo son los personajes de un juego de computadora, que tienen un desempeño compatible a los roles asignados y su contexto, pero que no pueden hacer nada más que eso. La IA débil no representa una genuina inteligencia general, por el contrario, se trata de una construcción diseñada para exhibir inteligencia en la tarea limitada que le fue asignada y, normalmente, respaldada por abundante información sobre el dominio en que se desempeña. Una entidad con estas características es capaz, por ejemplo, de mantener una conversación con personas reales, incluso, de hacer comentarios especiales y bromas, pero operando en una franja de conocimientos angosta y claramente predeﬁnida. En resumen, la hipótesis de la IA débil enuncia que, para una máquina, es posible demostrar inteligencia sin disponer de una mente, estados mentales ni conciencia. En contraste, la IA fuerte procura que cierta entidad pueda llegar a ser dotada de todas las funciones cognitivas que un humano pueda tener. En esencia, que su capacidad y desempeño no sea diferente a los de una mente humana real. A partir de esa premisa, se establece una clara distinción entre genuina inteligencia y alta complejidad. Esta última puede estar involucrada en acciones muy complicadas, mediante elaborados automatismos, aún incomprensibles para una mente humana normal, sin disponer de cualidades atribuidas a la inteligencia. Quien introdujo esta distinción entre IA débil y fuerte fue el ﬁlósofo John Searle en un artículo crítico con la inteligencia artiﬁcial publicado en 1980 (Searle, 1980), que provocó y continúa provocando mucha polémica. La IA fuerte implicaría que un ordenador convenientemente programado no simula una mente, sino que, literalmente, “es una mente” y, por lo tanto, tendría que ser capaz de pensar igual que un ser humano. Searle (1980), en su artículo, intenta demostrar que la IA fuerte es inalcanzable. La IA débil, por otra parte, según Searle (1980), consistiría en construir programas que realicen tareas especíﬁcas. La capacidad de los ordenadores para realizar ciertas tareas, incluso con mejor desempeño que las personas, ya ha sido ampliamente demostrada en numerosos dominios y su aplicación, en el mundo actual, exhibe un rápido crecimiento. C O NT I NU A R Lección 3 de 5 Funciones de evaluación y métodos heurísticos A diferencia de los métodos exhaustivos, la estrategia de los métodos heurísticos es la de realizar búsquedas orientadas en espacios de estados reducidos, es decir, encontrar una solución sin expandir completamente todas las ramas del árbol. Para ello, se opera a través de un único camino, cuyo curso es cambiado cuando aparece alguna otra ruta más prometedora que la que se está siguiendo en ese momento. Esto requiere establecer un criterio que oriente el proceso y da lugar a la necesidad de la llamada función heurística. Funciones heurísticas Estas funciones son una aplicación del espacio de estados sobre un espacio numérico. Para cada estado n se tiene: f(n) = Vn Donde Vn es un valor numérico que caliﬁca un cierto estado n y permite evaluar su conveniencia en el camino de la búsqueda de la solución. Estas suelen ser funciones de evaluación estáticas que determinan factores asociados al grado de proximidad del objetivo. Evidentemente, cuanto mejor indique Vn la cercanía a la meta, menor será la dimensión del grafo del espacio de estados o búsqueda que es requerido. La función heurística, expresada genéricamente como f(n), puede descomponerse en dos partes principales: la primera depende de la distancia del nodo n al estado inicial y la segunda, de su distancia al estado objetivo. Es decir: f(n) = g(n) + h(n) Donde g(n): costo estimado del camino ya recorrido hasta al nodo n; y h(n): distancia estimada que separa el nodo n del estado objetivo. Según estas deﬁniciones, es importante notar que g(n) = 0, cuando n representa el nodo inicial, y h(n) = 0, cuando n representa el nodo objetivo. Es necesario reconocer la existencia de un valor real de la función heurística de cada nodo, deﬁnido f*(n) = g*(n) + h* (n) y que no es conocido. La función f(n) representa la mejor aproximación posible y está claro que g(n) ≤ g*(n) y h(n) ≤ h*(n). Procedimiento general de solución Deﬁnida la función destinada a asociar un valor numérico a cada nodo del espacio de estados, el paso siguiente es establecer el procedimiento sistemático que, a partir de esos valores, permitirá alcanzar la meta. Sus pasos son los que se enumeran seguidamente. 1 Identiﬁcar el estado inicial y el estado objetivo. Crear un grafo de exploración que, inicialmente, consistirá en un único nodo correspondiente al estado inicial. Crear una lista de nodos llamada abierta e inicializarla con dicho nodo. 2 Crear una lista de nodos llamada cerrada que, inicialmente, estará vacía. 3 Hasta que se encuentre un nodo objetivo o una condición de error, se repiten las siguientes acciones: comprobar que la lista abierta no está vacía. En caso contrario, terminar delatando una condición de error; retirar el primer nodo de la lista abierta, llamar a ese nodo m e introducirlo en la lista cerrada; expandir m aplicando las reglas disponibles, identiﬁcar los nodos sucesores y crear, desde todos ellos, punteros a m. El objetivo es poder conocer, en todo momento, la identidad de su antecesor; si algún sucesor de m es el estado meta, se debe abandonar el proceso iterativo y continuar en el paso 4; para cada sucesor n de m, calcular su función heurística f(n); si n es un nuevo nodo que no está registrado en la lista abierta o en la cerrada, asociar, al nodo n, el valor de f(n) e introducirlo en la lista abierta; en caso de que el nuevo nodo ya esté registrado en la lista abierta, debe reemplazar al anterior, si el valor de su función heurística es menor; si el nodo ya estaba registrado en la lista cerrada y el nuevo valor de la función heurística es menor, este debe reemplazar el anterior y corresponde actualizar la deﬁnición y el costo de los caminos, ya que estos pueden haber cambiado; y reordenar la lista abierta, según los valores de f(n), en orden creciente. Continuar el ciclo iterativo en el paso 3b. 4 Devolver, como solución, el camino que se obtiene recorriendo los punteros de los antecesores, desde el nodo objetivo hasta el nodo inicial. Dar por concluido el proceso de búsqueda. Nótese aquí que, si en el algoritmo descripto los nuevos nodos son colocados siempre al ﬁnal en la lista abierta (lista FIFO), su comportamiento será el del método primero en anchura. Por el contrario, si los nuevos nodos son colocados al principio (lista LIFO), el algoritmo se corresponderá con el método primero en profundidad. Esto lleva a reconocer todos estos métodos como casos particulares del procedimiento genérico de búsqueda en grafos, que adquieren su identidad, en cada caso, según la forma en que es operada y ordenada la lista denominada abierta. Si se busca deﬁnir una función heurística para el caso del puzzle de ocho ﬁchas, podría asignarse a g la profundidad, en el árbol de búsqueda, y, a la función h, la representación de la cantidad de ﬁchas mal colocadas. Como alternativa, h podría representar la cantidad de movidas que, en cada caso, son necesarias para alcanzar la meta. Nótese que ambas propuestas son distintas, ya que una ﬁcha mal colocada, muchas veces, implica varias movidas. Habiéndose deﬁnido las funciones heurísticas y el proceso general de solución, los principales métodos se distinguen entre sí por las funciones utilizadas y los criterios adoptados para reducir el espacio de búsqueda. En resumen, cada paso del proceso de búsqueda implica seleccionar el nodo más prometedor que se haya generado hasta ese momento y, para ello, se evalúa una función heurística apropiada. Se trata de un procedimiento de búsqueda, primero, en profundidad, al que se le incorpora la posibilidad de cambiar el camino cada vez que la evaluación de la función heurística lo justiﬁque, haciendo la salvedad de que no se retoman caminos de exploración abandonados anteriormente. Métodos de búsqueda heurística Tal como fue anticipado, habiéndose establecido un proceso general de búsqueda en el espacio de estados, los diferentes métodos se caracterizan en la manera de tratar la función heurística que le asigna una caliﬁcación a cada estado o nodo. Los principales métodos se enlistan seguidamente. Búsqueda primero el mejor – Normalmente, se reserva el nombre de búsqueda primero el mejor para el procedimiento donde la función heurística utilizada consiste, únicamente, en una estimación del menor costo, desde cada nodo a un nodo meta (función h). Método A* – El algoritmo primero el mejor (antes descripto) es, en realidad, una simpliﬁcación de un algoritmo más general introducido por Hart en 1968 y que fue denominado A*. En este caso, se tiene en cuenta el costo del mejor camino parcial, desde la raíz hasta el nodo considerado (función g), además de la función h, que considera el costo desde allí a la meta. Mientras que el algoritmo primero el mejor no garantiza que la solución encontrada sea la óptima, A* sí lo hace. En efecto, se ha demostrado que, si existe una solución, este método la encuentra y, además, es óptima. Búsqueda en haz (beam search): – Es una variación del método primero el mejor. Esta estrategia pretende acelerar el proceso de búsqueda, reduciendo, en cada paso del algoritmo, el número de nodos generados que son expandidos posteriormente. La selección mencionada se puede llevar a cabo de diferentes formas: permitiendo que solo un número ﬁjo, de los nodos más prometedores generados en cada paso, sea expandido más adelante; y estableciendo un valor umbral fo de la función de evaluación heurística, por debajo del cual (o por encima, según el criterio que se esté empleando), ningún nodo generado podrá ser expandido.  Los métodos primero el mejor y A* son los métodos heurísticos más conocidos. Existen otros (muchos métodos menos difundidos o más especializados) que no se tratan en este curso. Métodos de búsqueda con adversarios La teoría de los juegos representa una disciplina matemática, cuyo objeto son los métodos de toma de decisión, en las llamadas situaciones de conﬂicto. Una situación se llama de conﬂicto, si, en ella, chocan los intereses de dos o más agentes que persiguen objetivos opuestos. Cada una de las partes concreta sucesivas acciones, procurando alcanzar sus propios objetivos, en un contexto en el que el éxito de una parte signiﬁca el fracaso de la otra. Si bien ya hubo algunos antecedentes previos, se considera al matemático John Von Neumann y el economista Oscar Morgenstern como los precursores de la Teoría de juegos moderna. Estos representaron, a través de modelos matemáticos, ciertos procesos de negociación en cuestiones comerciales (1939) y, posteriormente, en 1944, los publicaron en un libro bajo el título The Theory of Games and Economic Behaviour. Este trabajo fue presentado como una aplicación matemática orientada a predecir el resultado cierto o más probable de una disputa entre partes. Posteriormente, Claude Shannon (1950) describió, en un artículo, las características que tendría un programa que jugara ajedrez y Alan Turing (s.f.), también, describió tal programa, aunque nunca llegó a implementarlo. Arthur Samuel (1963), por su parte, implementó el primer programa importante de juego. Jugaba a las damas y era capaz de mejorar su comportamiento, aprendiendo de sus errores. Unos años después, Knuth y Moore (1975) introdujeron el concepto de “árbol mínimo”, demostrando que cualquier algoritmo que quiera evaluar, apropiadamente, un juego debe explorar este árbol. Poco más tarde, Ebelin (s.f.) describió procedimientos que permiten estimar el tamaño del árbol de búsqueda en diferentes condiciones. Más recientemente, Nash, Harsanyi y Selten (1994) recibieron el Premio Nobel de Economía por sus contribuciones a la Teoría de juegos. Ejemplo 1 Se presenta el árbol que se obtendría de aplicar todas las acciones posibles al estado inicial de un cierto problema. Resulta obvio el hecho de que este árbol es, anticipadamente, desconocido y la solución debe alcanzarse a través de un procedimiento sistemático, en el que se evalúan, de manera sucesiva, las funciones heurísticas de cada nudo. Para ello, se recorrerá el grafo de la ﬁgura, según el procedimiento primero el mejor. Los nodos están etiquetados con el valor de la función de evaluación heurística que representa la distancia estimada a la meta (h), en cada uno de ellos. El proceso y el camino al nodo objetivo quedan representados por los contenidos de las listas abierta y cerrada a lo largo de cada ciclo de cálculo. Luego, se utiliza el mismo árbol con el ﬁn de recorrerlo nuevamente, según el procedimiento A*. Para ello, se evalúa, en cada nodo, una nueva función heurística, sumando al valor h anterior al costo del camino ya recorrido (g). Al tenerse en cuenta los costos de los caminos recorridos hasta cada nodo, se deberían obtener mejores resultados o, como mínimo, uno diferente. Sin quitar generalidad al ejemplo y por razones de simplicidad, se asigna, al costo de los caminos, un valor igual a la profundidad de cada nodo, tal como se muestra en el segundo grafo, en la ﬁgura 1. Figura 1: Árbol del método primero el mejor y listado de nodos abiertos / cerrados Fuente: elaboración propia. Figura 2: Árbol del método A* y listado de nodos abiertos / cerrados Fuente: elaboración propia. Se sugiere explorar las consecuencias de variantes en los valores heurísticos, de manera de comprobar los posibles diferentes resultados, según los cambios en el orden de la lista abierta. C O NT I NU A R Lección 4 de 5 Eﬁciencia de los procesos de búsqueda La elección de la función heurística es determinante para la eﬁciencia en el desempeño de los algoritmos de búsqueda. En un caso extremo, ignorar la función heurística ( f(n) = 0) conduce a los métodos exhaustivos en los que la solución requiere explorar la totalidad del espacio de estados. El paso siguiente fue solo considerar, en la función heurística, el costo que hay desde cada nodo hasta la meta (h), que ya fue presentado como método primero el mejor. Si bien representa un gran progreso, no es suﬁciente para asegurar una solución óptima. Además, al adoptarse la función apropiada, es esencial considerar el esfuerzo que implica su cálculo. Cuanto más completo sea un modelo, habrá, seguramente, mejores opciones para la función heurística, aunque su cálculo será, también, más laborioso. Por lo tanto, debe llegarse a soluciones de compromiso que contemplen tanto los beneﬁcios de utilizar funciones heurísticas precisas como el costo de su cálculo. Por otra parte, tal como se anticipó en la lectura anterior, podría pensarse que el rendimiento del proceso de búsqueda puede ser mejorado, si se realizan búsquedas simultáneas, partiendo, al mismo tiempo, desde el nodo inicial y el nodo objetivo. Esta es una opción aplicable a la búsqueda primero en anchura, ya que puede asegurarse que ambos procesos se encontrarán en algún punto intermedio entre ambos extremos. Además, resulta previsible que esta búsqueda bidireccional encontrará el camino óptimo. Sin embargo, este recurso no es trasladable a las búsquedas heurísticas, ya que, en ellas, es imposible asegurar que los dos procesos iniciados en ambas direcciones serán capaces de converger a un camino óptimo. Otro aspecto para considerar son las métricas destinadas a evaluar capacidades, esfuerzos y rendimientos en los métodos de búsqueda en el espacio de estados. Son la única forma de establecer comparaciones sobre base sólida. Naturalmente, el punto de partida es reconocer que un método será más eﬁciente en la medida que expanda o analice menos nodos que sean ajenos a la trayectoria óptima que lo conduce a una meta. Un primer indicador sería el factor de dispersión, deﬁnido como la longitud de la trayectoria d dividida por el número total de nodos N que fueron generados durante la búsqueda: P = d / N; 0 ≤ P ≤ 1 Tal como está deﬁnido, P es una medida de lo dirigido o disperso que es un proceso de búsqueda hacia un nodo meta, poniendo de maniﬁesto los casos en que se exploran caminos irrelevantes. Una búsqueda es más eﬁciente en la medida en que P sea más cercano a 1. Sin embargo, P depende no sólo de la eﬁciencia del algoritmo, sino, también, de la diﬁcultad del problema representado por la longitud de la trayectoria. Por esta razón, se ha establecido otro indicador denominado factor de ramiﬁcación efectiva B, que presenta mayor independiente de la longitud de la trayectoria. También, es denominado factor de ramiﬁcación equivalente. Debe considerarse un árbol imaginado, donde cada nodo tiene B sucesores y longitud d. La cantidad total de nodos N se determina a partir de la expresión: N = B + B2 + B3 +... + Bd de donde se deduce: N = B. (Bd – 1 ) / (B – 1) El inconveniente que presenta la expresión es que no es de fácil evaluación, dado que lo que se busca es el valor de B y no el de N. Buscando, ahora, una recomendación sobre este tema, según Nilsson (2001), los factores que caracterizan el potencial de un proceso de búsqueda heurística son los siguientes: 1. la longitud del camino encontrado; 2. el número de nodos expandidos para ese camino; y 3. el esfuerzo computacional requerido para el cálculo de la función heurística. Debe aquí, notarse que la elección de una función heurística adecuada es la que permitirá equilibrar estos factores, de manera de que sea máximo el rendimiento de los procesos de búsqueda. Debido a que la mayor parte de los agentes están sujetos a limitaciones de capacidad de proceso y memoria en sus recursos computacionales, a la vez que exigidos por demandas de breves tiempos de respuesta, es de esencial importancia considerar el rendimiento de los métodos que hacen posible la selección de alternativas. Desafío propuesto a partir de las notas anteriores Se ha completado, aquí, esta presentación introductoria a la resolución de problemas de búsqueda en el espacio de estados. Para ello, se han presentado, en esta lectura, los métodos heurísticos, que se suman a los métodos exhaustivos presentados en la lectura anterior. De esta manera, se ha dado respuesta a la actividad prevista, que es la de resolver problemas de búsqueda en el espacio de estados, a través de métodos exhaustivos y heurísticos. Completado este tema, se invita al lector a procurar responder a los interrogantes que se presentan a continuación, una vez que haya completado la lectura de estas notas. Luego, el siguiente paso será leer el Capítulo 4 de Russell y Norvig (2008, pp. 107-121) y el Capítulo 4 de García Serrano (2012, pp. 65-83), en los que se tratan los mismos temas, con mayor amplitud y desde otros puntos de vista. Por último, se debe volver sobre las preguntas aquí formuladas y las respuestas propuestas con un espíritu de autocontrol ﬁnal. La intención es estimular una mirada crítica al trabajo realizado, desde una posición con mayores conocimientos sobre los temas tratados. Se reitera que estas preguntas tienen como única ﬁnalidad contribuir a que el estudiante compruebe, por sí mismo, sus conocimientos, puesto que no se trata de una instancia de evaluación. Las consignas son las que siguen. 1 Haga un resumen de los motivos que justiﬁcan los métodos heurísticos. 2 Distinga a los métodos débiles y fuertes de la IA. 3 Explore, en la unidad 1, las características de las corrientes de los primeros años de la IA y encuentre una relación con los métodos débiles. Explique. 4 Describa los dos principales métodos heurísticos tratados, identiﬁcando similitudes y diferencias. C O NT I NU A R Lección 5 de 5 Referencias Benítez Iglésias, R. (2013). Inteligencia artiﬁcial avanzada. España: Editorial UOC (Universitat Oberta Catalunya). García Serrano, A. (2012). Inteligencia artiﬁcial. Fundamentos, práctica y aplicaciones. España: RC Libros Alfaomega. Masip Rodó, D., Escudero Bakx, G., Benítez Iglésias, R., Kanaan Izquierdo, S. (2015). Inteligencia artiﬁcial avanzada. España: Editorial UOC, S. L. Nilsson, N. (2001). Inteligencia Artiﬁcial, una nueva síntesis. Editorial McGraw Hill. Ponce Cruz, P. (2011). Inteligencia Artiﬁcial con aplicaciones a la Ingeniería. Editorial Alfaomega/Marcombo. Reyes, F. (2013). Robótica- Control De Robots Manipuladores. Editorial Alfaomega. Rich, E. y Knight, K. (1991). Inteligencia Artiﬁcial. Editorial McGraw Hill. Russell, S. J. y Norvig, P. (2008). Inteligencia artiﬁcial. Un enfoque moderno. 2° Ed. España: Pearson Searle, J. R. (1980). Minds, brains, and programs. Behavioral and Brain Sciences. (3). 417–424. Turing, A. (1950). Computing Machinery and Intelligence. MIND, 59, 236. Von Neumann, J. y Morgenstern, O. (1944). The Theory of Games and Economic Behaviour. Editorial: Princeton University Press Winston, P. (1994). Inteligencia Artiﬁcial. Editorial Addison Wesley. Representación del conocimiento e inferencia (1ª parte) Agentes basados en conocimiento Conocimiento, inferencia y razonamiento Métodos básicos de razonamiento Representación del conocimiento mediante lógica proposicional Representación del conocimiento mediante objetos estructurados Desafío propuesto a partir de las notas anteriores Referencias Lección 1 de 7 Agentes basados en conocimiento Actividades Reconocer las formas de representar el conocimiento y los métodos de razonamiento. Hasta aquí, la discusión se ha centrado en los procedimientos básicos para resolver problemas a través de la búsqueda de secuencias de acciones apropiadas que permitan alcanzar la solución, representada por un objetivo. Se trata de procedimientos eﬁcaces y, a la vez, lo suﬁcientemente generales como para poder ser considerados sin tener que hacer referencia a la forma en que el conocimiento necesario es representado. En la exploración del espacio de estados y la identiﬁcación del camino a seguir, se obvió toda referencia al conocimiento especíﬁco sobre el dominio tratado. A pesar de la observación, estos métodos son eﬁcaces y, como consecuencia, son útiles por sí mismos, pero su potencialidad está limitada por su generalidad. No obstante, constituyen un marco de referencia para métodos más avanzados, que exploren de diferente manera las formas de representar el conocimiento, posibilitando la resolución de problemas más especíﬁcos y complejos. En su evolución, la inteligencia artiﬁcial siguió este camino y llegó a enfrentar la misma realidad: es necesario trabajar en la representación eﬁcaz del conocimiento, para poder, luego, aprovecharlo. Así se plantearon los llamados métodos débiles y los métodos fuertes, en la lectura anterior. Se llega aquí a los agentes basados en utilidad (tipo 4) de Russell y Norvig (2008), dentro de los cuales se encuentran los “Agentes Lógicos” (p. 217) y los “Agentes Razonadores” (tipo 3) de Nilsson (2001), que son aquellos cuyas cualidades se tratarán aquí y los que nos han conducido a la necesidad de trabajar sobre la representación del conocimiento. Como se verá, el componente principal de todo agente basado en conocimiento es su base de conocimiento (en adelante BC). C O NT I NU A R Lección 2 de 7 Conocimiento, inferencia y razonamiento Antes de continuar, es necesario recordar y acordar el signiﬁcado de ciertos conceptos básicos con los que se trabajará en lo sucesivo. Por su relación, parece conveniente considerarlos, a todos ellos, en conjunto, a pesar de que serán tratados progresivamente en el desarrollo de esta lectura y de la próxima. Nada más importante que saber de lo que se está hablando, manifestación obvia, pero, también, fácilmente olvidada. Una forma de anticipar dudas es deﬁnir estrictamente estos conceptos, para que el lector haga luego su propia interpretación. Con este ﬁn se los deﬁnen a continuación. Conocimiento: “Hechos o información adquiridos por una persona a través de la experiencia o la educación. Es la comprensión teórica o práctica de un asunto referido a la realidad” (Wikipedia, 2020, t.ly/mydb). “Capacidad para resolver un determinado conjunto de problemas” (Muñoz y Riverola, 2003). “Información que el individuo posee en su mente, personalizada y subjetiva, relacionada con hechos, procedimientos, conceptos, interpretaciones, ideas, observaciones, juicios y elementos que pueden ser o no útiles, precisos o estructurables” (Alavi y Leidner, 2003). Representación del conocimiento: “Conjunto de convenciones sintácticas y semánticas que hacen posible la descripción de cosas” (Winston, 1994). “Estas convenciones constituyen los llamados lenguajes de representación … que deben tener expresividad, poder heurístico y conveniencia notacional” (Carnota y Teszkiewiwicz, 1989). “Representación de los hechos en un determinado formalismo … que serán las entidades que seremos capaces de manipular” (Rich y Knight, 1991). Un buen sistema de representación del conocimiento en un dominio particular debe exhibir las siguientes propiedades: 1. suﬁciencia de la representación: capacidad para representar todos los tipos de conocimiento necesario en el dominio; 2. suﬁciencia deductiva: capacidad de manipular las estructuras de representación, con la ﬁnalidad de obtener nuevo conocimiento, deducido a partir del inicialmente disponible; 3. eﬁciencia deductiva: capacidad de incorporar información adicional con el ﬁn de que los mecanismos de inferencia puedan seguir las direcciones más prometedoras; y 4. eﬁciencia en la adquisición: capacidad de adquirir nueva información con facilidad. Inferencia: “Proceso por el cual se derivan conclusiones a partir de premisas” (Wikipedia, 2020, t.ly/RWg1). “Inferencia se reﬁere a la acción de deducir, de llegar a alguna conclusión o probabilidad debido a hechos o parámetros que sucedieron previamente” (Nilsson, 2001). “Mecanismo de derivación sintáctica que a partir de un conjunto dado de fórmulas permite derivar nuevas fórmulas, utilizando operaciones que se denominan reglas de inferencia” (Pajares Martinsanz y Santos Peñas, 2006). Razonamiento: “Facultad que permite resolver problemas, extraer conclusiones y aprender de manera consciente de los hechos, estableciendo conexiones causales y lógicas necesarias entre ellos” (Wikipedia, 2020, t.ly/hyKd). “Proceso de inferencia acerca del estado presente del agente por medio de cálculos basados en el conocimiento del dominio y en las restricciones impuestas sobre sus características” (Pajares Martinsanz y Santos Peñas, 2006). Se reﬁere a un conjunto de actividades mentales consistentes en conectar unas ideas con otras de acuerdo a ciertas reglas o también puede referirse al estudio de ese proceso. En sentido amplio, se entiende por razonamiento la facultad humana que permite resolver problemas. (Rich y Knight, 2001). El problema de la representación del conocimiento se maniﬁesta, en su trascripción, bajo una forma simbólica que pueda ser explotada por un sistema de razonamiento. Un modo de representación asocia, así, dos aspectos esencialmente distintos, interrelacionados y habitualmente confundidos que son: 1. la 2. el estructura de datos para representar la información y método asociado de explotación de esta información, es decir, el método de razonamiento. Base de conocimiento (BC): Se denomina BC al reservorio de información del que se dispone, en un dominio especíﬁco, sobre los objetos y sus relaciones. Es la base del razonamiento que permite descubrir dinámicamente nueva información y conocimientos sobre el problema tratado. Esto distingue netamente una base de conocimiento de una base de datos clásica, de la que solo puede extraerse la información que fue explícitamente almacenada. (Pajares Martinsanz y Santos Peñas, 2006). El proceso de representar el conocimiento referido a un dominio particular y convertirlo en una BC, conjuntamente con los procesos que permiten su manipulación y transformación, se denomina ingeniería del conocimiento. Lógica clásica: “Ciencia que expone las leyes, modos y formas del conocimiento cientíﬁco” (Real Academia Española, 2001, t.ly/ESrj). “La disciplina que estudia los principios formales del conocimiento humano” (s.d.). Formas de representar el conocimiento Existen distintas maneras de representar conocimiento y se pueden agrupar a todas ellas en tres clases fundamentales (Carnota y Teszkiewiwicz, 1989): lógica: a través de la representación declarativa del conocimiento; sistemas de producción: donde el conocimiento es representado por reglas; y objetos estructurados: tales como redes semánticas, frames y otras varias alternativas. Con el formalismo lógico, es posible emular sistemas basados en reglas, así como, también, emular representaciones de objetos estructurados. C O NT I NU A R Lección 3 de 7 Métodos básicos de razonamiento Los métodos básicos de razonamiento son: el deductivo, el inductivo, el analógico, el analítico y el sintético. Razonamiento deductivo: parte desde una premisa general hacia lo particular. Por lo tanto, la conclusión se inﬁere y se apoya, necesariamente, en las premisas. Razonamiento inductivo: forma de razonamiento en que la verdad de las premisas apoya la conclusión, pero no la garantiza, lo hace de manera probable. Razonamiento analógico: se obtienen las conclusiones a partir de las premisas con las que se establece una analogía o similitud entre elementos distintos o conjuntos de ellos. Razonamiento analítico: se divide el todo en sus elementos básicos y, como consecuencia, parte de lo general para llegar a lo particular, es decir, se descompone una idea o un objeto en sus componentes. Su correctitud es conﬁrmada a partir del proceso. Razonamiento sintético: proceso de razonamiento que procura reconstruir un todo a partir de sus componentes más simples, identiﬁcados en el análisis. Normalmente, para conﬁrmar su correctitud, se requiere una contrastación empírica. C O NT I NU A R Lección 4 de 7 Representación del conocimiento mediante lógica proposicional Una de las estructuras más básicas e importantes de nuestro pensamiento es la proposición. Los procesos de pensamiento más signiﬁcativos asociados a ella son las operaciones proposicionales y la deducción proposicional. La parte de la lógica que estudia las operaciones proposicionales y la deducción proposicional se denomina lógica o cálculo proposicional. La programación lógica nació a comienzos de la década de 1970, a partir de los resultados obtenidos con los primeros trabajos sobre demostradores automáticos de teoremas e inteligencia artiﬁcial. Con anterioridad, a principios de la década de 1960 y basándose en los trabajos de Herbrand (1930), hubo una gran actividad en torno a la demostración de teoremas que fue desarrollada por Prawitz, Gilmore, Davis, Putnam y otros. Una lógica proposicional, también llamada booleana o de orden “0”, consiste en un sistema formal cuyos elementos más simples representan proposiciones y cuyas constantes o conectivas lógicas representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad. El lenguaje formal de la lógica proposicional se genera a partir de una gramática formal descrita usando la notación BNF (Backus Naur Form). Aquí cabe acotar que esta notación fue propuesta y utilizada por John Backus (s.f.), en la deﬁnición del primer lenguaje superior, y por su compilador, Fortran, en 1956. (Wikipedia, 2020, https://bit.ly/3dFvZT3). Las sentencias atómicas o elementos sintácticos indivisibles se componen de un único símbolo y cada uno de estos símbolos representa una proposición que puede ser verdadera o falsa. Los nombres de los símbolos pueden ser asignados libremente, pero es recomendable que tengan alguna relación con la entidad representada. Por su parte, las sentencias complejas se construyen a partir de sentencias más simples, mediante el uso de conectivas lógicas. Se dispone de cinco conectivas lógicas, que son los siguientes: negación: NO, representada por “¬”; conjunción: AND, representada por “˄”; disyunción: OR, representada por “˅”; implicación: representada por “==>”; y bicondicional: representada por “”. La sintaxis es estricta, en el sentido que cada sentencia que incluya una conectiva lógica debe estar entre paréntesis, para evitar la posibilidad de sentencias ambiguas. Deﬁnida la sintaxis, la semántica deﬁne las reglas que permiten establecer el resultado concreto que es asignado a una sentencia compleja. A modo de resumen, en la tabla 1, se representan las consecuencias de todas las conectivas lógicas aplicadas sobre dos símbolos p y q que adoptan los valores posibles. Tabla 1: Consecuencias de todas las conectivas lógicas p q p˄q p˅q ¬p p => q p q V V V V F V V V F F V F F F F V F V V V F F F F F V V V Fuente: elaboración propia. La lógica proposicional permite formalizar y teorizar sobre la validez de una gran cantidad de argumentos. Sin embargo, también existen argumentos intuitivamente válidos, pero cuya validez no se puede probar de manera formal a través de la lógica proposicional. A partir de lo expuesto, se concluye que el cálculo proposicional no constituye un estudio completo de las formas expresivas e inferenciales que son fundamentales, ni en el lenguaje natural ni en el matemático. Las siguientes cadenas de caracteres son ejemplos de fórmulas bien formadas: (p ˄ q) ((p ==> q) ˄ p) ¬(p ˄ q) C O NT I NU A R (p ==> ¬q) Lección 5 de 7 Representación del conocimiento mediante objetos estructurados Los métodos habituales son las redes semánticas y los frames. Ambos modelos de representación tienen en común que el conocimiento está organizado alrededor de los objetos y eventos del universo de aplicación. Una red semántica es una forma de representación del conocimiento lingüístico, en la que los conceptos y sus interrelaciones se representan mediante un grafo. Para los casos en que no existan ciclos, estas redes pueden ser visualizadas como árboles. Son recursos apropiados para representar mapas conceptuales y mentales, muy utilizados en la inteligencia artiﬁcial. Los elementos básicos que se encuentran en todos los esquemas de redes semánticas son: estructuras de datos en nodos, que representan conceptos, unidas por arcos que representan las relaciones entre estos conceptos; y un conjunto de procedimientos de inferencia que operan sobre las estructuras de datos. Uno de los primeros modelos de red semántica fue desarrollado por Quillian (1969) y fue utilizado para describir el conocimiento semántico. Los frames son descripciones estructuradas de un objeto o de una clase de objetos. Tienen numerosas ventajas en la representación del conocimiento, entre las que se destacan las siguientes: posibilita la descripción detallada de cada concepto y atributo de una red semántica; el acceso a los atributos es de forma rápida y eﬁciente; las propiedades de las relaciones son fáciles de describir; poseen aspectos de la programación orientada a objetos; y ofrecen una representación concisa conocimiento de forma natural. C O NT I NU A R y estructurada del Lección 6 de 7 Desafío propuesto a partir de las notas anteriores Una vez estudiados los métodos de búsqueda en el espacio de estados, tanto exhaustivos como heurísticos (lecturas 1 y 2), se avanza para tratar el conocimiento, la inferencia y el razonamiento, por ser la base de los agentes lógicos de Russell y Norvig (2008) y los agentes razonadores de Nilsson (2001). En esta lectura, se deﬁnen los citados conceptos y se incursiona, muy superﬁcialmente, en la representación del conocimiento mediante lógica proposicional. De la misma forma, a continuación, se hace con la representación del conocimiento mediante reglas. Aquí es necesario reconocer que, por ser la IA muy vasta y dinámica, muchos temas de singular importancia son tratados, inevitablemente, de manera superﬁcial. En estos casos, la ﬁnalidad es que el lector esté advertido de su existencia y, someramente, de sus posibilidades. A los interesados en avanzar más sobre lógica proposicional, en particular, o en ingeniería del conocimiento, en general, se les recomienda el excelente libro de Pajares Martinsanz y Santos Peñas (2006). Completada esta lectura, se invita al lector a intentar responder los interrogantes que se presentan a continuación. Luego, el siguiente paso será leer el Capítulo 7 sobre agentes lógicos de Russell y Norvig (2008, pp. 217270). Como es habitual, el material presentado en la lectura busca facilitar al lector su incursión en el libro principal de la bibliografía básica. Por último, se lo invita a volver sobre las preguntas aquí formuladas y las respuestas propuestas, con un espíritu de autocontrol ﬁnal. La intención es estimular una mirada crítica al trabajo realizado, desde una posición con mayores conocimientos sobre los temas tratados. Se reitera que estas preguntas tienen como única ﬁnalidad contribuir a que el estudiante compruebe, por sí mismo, sus conocimientos, puesto que no se trata de una instancia de evaluación. Las consignas son las que siguen. 1 Elabore sus propias deﬁniciones de conocimiento, inferencia y razonamiento. 2 Elabore sus propias deﬁniciones de las cinco formas de razonamiento y asócielas con ejemplos de la vida cotidiana. 3 Destaque las principales características de la lógica proposicional. C O NT I NU A R Lección 7 de 7 Referencias Benítez Iglésias, R. (2013). Inteligencia artiﬁcial avanzada. España: Editorial UOC (Universitat Oberta Catalunya). Carnota, R. y Teszkiewiwicz, A. (1989). Sistemas Expertos y Representación del Conocimiento. Edición EBAI. Masip Rodo, D.; Escudero Bakx, G. y Benítez Iglesias, R. (2015). Inteligencia artiﬁcial avanzada. España: Editorial UOC, S.L. Nilsson, N. (2001). Inteligencia Artiﬁcial, una nueva síntesis. McGraw Hill. Pajares Martinsanz, G. y Santos Peñas, M. (2006). Inteligencia Artiﬁcial e Ingeniería del Conocimiento. Alfaomega/RaMa. Pajares Martinsanz, G. y Santos Peñas, M. (2006). Inteligencia Artiﬁcial e Ingeniería del Conocimiento. Alfaomega/RaMa. Real Academia Española (2001). https://www.rae.es/drae2001/l%C3%B3gica Lógica. Recuperado de Rich, E. y Knight, K. (1991). Inteligencia Artiﬁcial. Madrid: McGraw Hill. Russell, S. J. y Norvig, P. (2008). Inteligencia artiﬁcial. Un enfoque moderno. 2° Ed. España: Pearson. Wikipedia (2020). Conocimiento. Recuperado de https://es.wikipedia.org/wiki/Conocimiento Wikipedia (2020). Inferencia. Recuperado de https://es.wikipedia.org/wiki/Inferencia#:~:text=La%20inferencia%20es%20e l%20proceso,dice%20que%20%C3%A9stas%20implican%20aquella. Wikipedia (2020). Lógica proposicional. Recuperado de https://es.wikipedia.org/wiki/L%C3%B3gica_proposicional Wikipedia (2020). Razonamiento. Recuperado de https://es.wikipedia.org/wiki/Razonamiento#:~:text=En%20sentido%20ampli o%2C%20se%20entiende,y%20l%C3%B3gicas%20necesarias%20entre%20ell os.&text=En%20otras%20palabras%2C%20un%20argumento,expresi%C3%B3 n%20ling%C3%BC%C3%ADstica%20de%20un%20razonamiento. Winston, P. (1994). Inteligencia Artiﬁcial. Madrid: Addison Wesley. Representación del conocimiento e inferencia (2ª parte) Representación del conocimiento mediante lógica de predicados Representación del conocimiento mediante reglas Desafío propuesto a partir de las notas anteriores Video conceptual Referencias Revisión del módulo Lección 1 de 6 Representación del conocimiento mediante lógica de predicados Actividades: Reconocer las formas de representar el conocimiento y los métodos de razonamiento. Con el ﬁn de dar respuesta a los problemas que se presentaban, conforme se buscaba mayor claridad y eﬁciencia en los lenguajes de programación, se exploraron y desarrollaron nuevas técnicas y paradigmas, entre las que, inicialmente, se destacaron el diseño modular, la programación estructurada y los paradigmas incluidos en la llamada programación declarativa. La programación declarativa es, indudablemente, el campo de trabajo más activo en materia de programación, desde su origen. Dentro del modelo declarativo, es posible reconocer numerosos estilos y paradigmas de programación, como el funcional, la lógica, concurrente y el orientado a objetos. Este marcado interés por la programación declarativa es consecuencia de una convicción ya establecida de que este estilo de programación puede contribuir, esencialmente, a la resolución de muchos problemas críticos en la producción de software, particularmente, en lo que se reﬁere a la productividad y a la ﬁabilidad. Esto se debe, fundamentalmente, a que el modelo declarativo soporta un nivel de abstracción que facilita conceptualmente la tarea de programar. Los dos estilos tradicionales de programación declarativa son la programación lógica y la programación funcional. La idea principal que acompaña a la programación lógica es el uso de la lógica matemática como lenguaje de programación. Fue introducida por Robert Kowalski (1979), a principios de la década de 1970, y fue llevada a la práctica por Alain Colmerauer (s.f.), a través de la implementación de PROLOG, el primer lenguaje de programación lógica. Esta aplicación de la lógica involucra tres elementos esenciales: un lenguaje: cuya gramática especiﬁca la forma en que se deﬁnen expresiones correctas; un conjunto de reglas de inferencia: destinadas a manipular las sentencias del lenguaje; y una semántica: para asociar los elementos del lenguaje con los elementos del dominio al que pertenece la aplicación. Debe comenzarse por reconocer a la programación lógica como un modo de programación no convencional. A diferencia de los lenguajes tradicionales que se encargan de describir la forma de resolver un problema, la programación lógica consiste en describir el problema en sí mismo. Esto signiﬁca independizarse de cómo la computadora va a resolver el problema en cuestión y concentrar el esfuerzo en deﬁnir su estructura lógica. Resulta, aquí, oportuno referirse a la deﬁnición de algoritmo de Robert Kowalski (1979), en la cual, se separaban los componentes lógicos de los componentes de control: algoritmo = lógica + control En la programación lógica, a raíz de quedar el control a cargo de un intérprete, la deﬁnición anterior se reescribe: algoritmo = lógica Debe notarse la importancia de la deﬁnición anterior, al considerarse que son los aspectos lógicos de un problema los que tienen perdurabilidad en el tiempo. Por el contrario, lo referido al control está muy vinculado al estado de la tecnología en el momento en que se resuelve el problema (computador, lenguaje, etcétera) y cambia con el tiempo. Las formas más difundidas que adoptan los lenguajes lógicos son el cálculo preposicional, ya visto en la lectura anterior, y el cálculo de predicados de primer orden. En esta lectura, el tratamiento de la programación lógica concentrará la atención en el cálculo de predicados de primer orden. Cálculo de predicados Un programa tradicional puede interpretarse como una función que, a partir de un estado inicial de una máquina ﬁcticia (que corresponde al lenguaje utilizando), deﬁne los valores que corresponden al estado ﬁnal de esta, luego de la evolución de un algoritmo. Sintaxis de la programación en lógica El lenguaje que se utiliza en la programación en lógica proviene de la lógica de predicados de primer orden. Para ello, se dispone de: un conjunto de elementos simples llamados constantes, que representan objetos; un vocabulario V de variables; un vocabulario F de símbolos funcionales, que representan funciones; un vocabulario P de símbolos predicativos, que representan relaciones; un conjunto de conectivos; y un conjunto de cuantiﬁcadores. Para estos símbolos se adoptan convenciones y debe advertirse que no hay un criterio único establecido. Aquí se utiliza el de Russell y Norvig (2008), que se deﬁne a continuación. 1 Las constantes, símbolos funcionales y símbolos predicativos están representados por cadenas de caracteres que comienzan con una letra mayúscula. 2 Las variables serán representadas con caracteres en minúsculas. 3 Los símbolos predicativos y los símbolos funcionales disponen de argumentos entre paréntesis. Estos argumentos están separados entre sí por comas y su interpretación queda deﬁnida por su ordenamiento, además, es única y debe estar claramente establecida. 4 Cualquier predicado puede negarse, para lo cual, debe estar precedido del símbolo de negación “¬”. 5 Los conectivos permiten deﬁnir relaciones más complejas. Estas son: ^ Conjunción y; v 6 Disyunción o; ==> Implicación si; y Equivalencia si y solo si. Los cuantiﬁcadores usados son: Ṿx Cuantiﬁcador Universal (para todo x); y Ǝx Cuantiﬁcador Existencial (existe un x). A partir de estos elementos del lenguaje, se convienen, ahora, las siguientes deﬁniciones: una constante, variable o función cuyos argumentos son, también, términos; Término: 1 of 4 símbolo predicativo, antepuesto a uno o más términos separados por Predicado: comas y encerrados entre paréntesis; 2 of 4 expresión que puede contener uno o más predicados, junto con conectivos y cuantiﬁcadores; y Fórmula: 3 of 4 es una fórmula en la que está presente un símbolo de “implicación” entre sus conectivos, por lo que Sentencia: pueden distinguirse dos miembros: un antecedente y un consecuente. Se d i t bié l 4 of 4 El conjunto de sentencias que pueden construirse usando las deﬁniciones anteriores constituye un lenguaje de lógica de primer orden. Es deﬁnido como de primer orden, porque no admite cuantiﬁcación sobre los predicados y las funciones. Ejemplos Se presentan algunas cláusulas lógicas y sus interpretaciones: Semántica de la programación en lógica Tal como surge de la deﬁnición sintáctica de los programas en lógica, estos se estructuran a partir de conceptos elementales que se denominaron constantes. Dichas constantes tienen una estructura lexicográﬁca bien deﬁnida: sucesión de caracteres válidos en un vocabulario dado. Pero lo importante es que carecen de todo valor semántico y es por ello que, a los lenguajes con esta concepción, se les llama lenguajes de manipulación simbólica. Esta carencia de valor semántico, también, se aplica a los símbolos funcionales y predicativos. Sin embargo, todo usuario, al escribir un programa, tiene una intencionalidad semántica bien deﬁnida. De igual forma, cuando se plantea una pregunta, esta tiene un valor semántico preciso para el usuario. Consecuencia e inferencia lógica Una fórmula F es consecuencia lógica de un conjunto de fórmulas R, si para todo dominio D, toda interpretación I(D) que satisface R, satisface, también, a F. El concepto de consecuencia lógica es el que permite determinar la forma en que los programas en lógica son evaluados. Debe considerarse una invocación de ejecución de un programa como una fórmula que debe probarse como consecuencia lógica de éste. Es decir que dicha fórmula debe ser satisfecha para "toda" interpretación que satisfaga al programa. Luego, una ejecución corresponde a una prueba de consecuencia lógica. La inferencia lógica es un mecanismo de derivación sintáctica que, a partir de un conjunto dado de fórmulas, permite derivar nuevas fórmulas, utilizando operaciones que se denominan reglas de inferencia. El conjunto inicial de fórmulas son sentencias válidas en un cierto lenguaje y se llaman axiomas. Los axiomas junto con las reglas de inferencia constituyen lo que se denomina un sistema formal. Mediante la inferencia lógica, es posible demostrar fórmulas sin necesidad de considerar interpretación alguna. Una prueba será una derivación en el sistema formal. Regla de resolución o básica de la Inferencia En un sistema formal, un paso de inferencia corresponde a la aplicación de una regla para inferir una nueva fórmula. Por ejemplo: Deducción lógica Sea F una fórmula y R un conjunto de fórmulas de una cierta teoría. Se dice que F es deducible lógicamente a partir de R y se escribe: R |-- F Esto será así, si existe una sucesión de fórmulas F1, F2,... , Fn tal que F = Fn y cada Fi es: 1. un axioma de la teoría, 2. una fórmula de R o 3. deducible de una fórmula precedente de la sucesión. Prueba por contradicción o reducción al absurdo (teorema) Sea F una fórmula y R un conjunto de fórmulas. F es deducible lógicamente a partir de R, si el conjunto formado por R con ¬F es inconsistente. O sea: R ==> F si R ^ ( ¬F ) es inconsistente. Este teorema da lugar a una de las reglas de inferencia más importantes desarrolladas hasta el presente, conocida como Regla de prueba por refutación o Principio de resolución de Robinson. Tal como se enunció en el teorema anterior, si las fórmulas F1, F2,... , Fn son consistentes, la fórmula F es una consecuencia de ellas, cuando el conjunto de las fórmulas F1, F2,... , Fn , ¬F son inconsistentes. Cláusulas de Horn Cualquier cláusula de forma general puede reescribirse de manera que tenga, como máximo, una conclusión. Para ello, basta pasar términos de un miembro al otro. Una vez cumplida esta condición, son denominadas cláusulas de Horn. Estas cláusulas reconocen cuatro casos particulares que se describen a continuación. Programas lógicos Un programa lógico es un conjunto ﬁnito de sentencias o cláusulas, que pueden adoptar alguno de los siguientes tres tipos: Aﬁrmaciones o hechos: también llamadas aﬁrmaciones incondicionales. Sentencias o reglas: también llamadas aﬁrmaciones condicionadas. Cláusula objetivo o goal: representada por una negación. Resolución de problemas El método de resolución de problemas, normalmente usado en programación lógica, es el denominado top down o de arriba a abajo. Consiste en comenzar por plantear la cláusula objetivo, que se enuncia como una sentencia negada (Principio de Robinson). Desde allí, se procede a resolver los predicados que se presentan sucesivamente, a partir de considerar otras reglas o hechos. Así, el problema principal se va dividiendo en subproblemas, cada uno de los cuales, a su vez, invoca otras reglas hasta que, ﬁnalmente, se deriva la cláusula nula. Ejemplo Se muestra un ejemplo muy simple en el que se pone el foco en el proceso de resolución. En el lado izquierdo de la tabla 1, se presentan las reglas disponibles y, a la derecha, su aplicación. Se comienza con el objetivo o negación y se desarrolla, luego, un proceso de inferencia, aplicando sucesivas resoluciones. En ellas, se invocan los procedimientos de la cláusula objetivo de izquierda a derecha. Si el predicado invocado concuerda con la cabeza de alguna sentencia, este se resuelve. Esto implica reemplazar el predicado invocado por sus antecedentes en el programa. Si el predicado no tiene antecedentes, lo que implica un "hecho" o "aﬁrmación", el procedimiento queda resuelto. Tabla 1: Ejemplo Fuente: elaboración propia. Al no concordar el predicado invocado con alguno de los que ﬁguran en el primer miembro de las reglas disponibles, el proceso se detiene con resultado negativo. Es decir, no se alcanzó una cláusula nula y, por lo tanto, el problema no tuvo solución. Por el contrario, cuando se alcanza una cláusula nula, se dice que el proceso de derivación ha tenido éxito y ha dado respuesta al problema planteado. En ambas circunstancias, al proceso se lo considera terminado. Mientras falte satisfacer un objetivo, el proceso no está terminado y algunos programas pueden entrar en un ciclo cerrado inﬁnito o loop. En general, se llamará computación a cada posible derivación que pueda ser generada aplicando una resolución al objetivo inicial. Entonces, una computación es una secuencia de objetivos a satisfacer, cada uno de los cuales fue generado a partir de resolver los que le preceden. El orden en que las cláusulas de un procedimiento son seleccionadas en respuesta a una invocación está dado por la regla de búsqueda utilizada. Normalmente, en programación lógica, los procedimientos son seleccionados según el orden en que aparecen en el programa. En un árbol, se vería, entonces, que cada alternativa de respuesta posible da lugar a una ramiﬁcación adicional. Cuando el intérprete lógico llega a un punto terminal, debe luego, volver hacia atrás hasta llegar el nodo donde se produjo la ramiﬁcación y desde el cual parten caminos todavía inexplorados (método primero en profundidad), algunos de los cuales concluirán con éxito y otros no. Todos estos caminos deben ser necesariamente explorados para obtener todas las soluciones alternativas del problema. Figura 1: Árbol de solución Fuente: elaboración propia. C O NT I NU A R Lección 2 de 6 Representación del conocimiento mediante reglas Los seres humanos tienden, instintivamente, a expresar muchas de las conductas usadas para resolver un problema en términos de un conjunto de reglas de tipo situación – acción. Estos sistemas fueron denominados agentes de reﬂejo simple por Russell y Norvig (2008), debido a que utilizan las citadas reglas para establecer la conexión entre percepciones y acciones. El agente actúa encontrando una regla cuya condición coincida con la situación actual reconocida por la percepción y efectúa la acción que corresponda a tal regla. Esta es una representación muy apropiada para las funciones de selección de acciones y su formalismo es denominado sistema de producción; también, se los denomina, simplemente, sistemas basados en reglas, y se encuentran entre los principales recursos para la implementación de los sistemas expertos. Cada regla toma la forma general Ci Ai, donde Ci representa la condición y Ai la acción, cuando el sistema de producción está formado por un conjunto ﬁnito no vacío de este tipo de reglas. La condición de una regla puede ser cualquier función booleana, deﬁnida sobre el vector de características que se deﬁne a partir de las entradas sensoriales. La selección de acciones se realiza buscando, secuencialmente, en el conjunto de reglas, todas aquellas cuyas condiciones estén conﬁrmadas por el vector de características. Normalmente, la condición de la primera regla deﬁne el objetivo general que persigue el sistema. En caso de no ser esta aplicable, se prosigue explorando las siguientes, las que, en alguna medida, procurarán orientar al agente en alguna dirección concurrente al objetivo general. El resultado de cada regla puede ser: una acción primitiva, un conjunto de acciones simultáneas, el llamado a otro sistema de producción, o una acción nula (indiferencia del agente a cierta condición percibida en el entorno). De acuerdo con lo plant

Document Details

Tags

Related

Full Transcript

Upgrade to continue