9 TIA Resolucion.pdf

Tema 9 Técnicas de Inteligencia Artificial Resolución de problemas mediante búsqueda  Índice Esquema 3...

Tema 9 Técnicas de Inteligencia Artificial Resolución de problemas mediante búsqueda  Índice Esquema 3 Ideas clave 4 9.1. ¿Cómo estudiar este tema? 4 9.2. Introducción. «El mundo de los bloques» 4 9.3. Dirección de la búsqueda 10 9.4. Búsqueda exhaustiva o a ciegas 14 9.5. Búsqueda heurística 21 9.6. Búsqueda en juegos 32 © Universidad Internacional de La Rioja (UNIR) 9.7. Costes 34 9.8. Aplicaciones prácticas y ejemplos de implementación 35 9.9. Referencias bibliográficas 41 A fondo 43 Test 46  Esquema © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 3 Tema 9. Esquema  Ideas clave 9.1. ¿Cómo estudiar este tema? Para estudiar este tema deberás leer las Ideas clave que se presentan a continuación. Puedes completar el estudio visualizando la lección magistral y revisando los recursos adicionales que se facilitan. Al finalizar el estudio de este tema el alumno será capaz de:  Describir diferentes métodos de búsqueda de soluciones.  Seleccionar y aplicar métodos de búsqueda adecuados a diferentes problemas. 9.2. Introducción. «El mundo de los bloques» Existen dos tipos de agentes: inteligentes y no inteligentes. Empezando por los segundos, un agente (por ejemplo, un robot) se puede programar para actuar de tal manera que alcance unos objetivos fijos, sin que sea capaz de adaptarse a otros objetivos de forma dinámica, lo que implica que no es inteligente. Por otro lado, se puede programar un robot que decida sobre sus acciones en función de su estado, sus capacidades y sus objetivos, siendo en este caso inteligente. Entonces, ¿cómo se puede programar un robot para que tome decisiones? Una solución es que busque, entre todos los estados posibles que representa el mundo, aquel estado que le © Universidad Internacional de La Rioja (UNIR) permita alcanzar un estado objetivo a partir del estado actual (Poole & Mackworth, 2010; Slaney & Thiébaux, 2001). Existen problemas de IA que pueden ser resueltos mediante búsqueda. En ellos se define un espacio de estados y unos operadores que permiten la transición entre Técnicas de Inteligencia Artificial 4 Tema 9. Ideas clave  estados, partiendo de un estado inicial y dirigiéndose a un estado objetivo. Entonces, el problema a resolver es encontrar el camino que lleve del estado inicial al estado objetivo a través del espacio de estados disponible. En cada estado se pueden aplicar una serie de operaciones para llegar a otro estado distinto, que puede ser el final o no. En la resolución de problemas mediante búsqueda se ha de aplicar una estrategia de control que permita encontrar un camino desde el estado inicial al objetivo, lo que implica examinar posibles secuencias de acciones y los estados que provocan, seleccionando aquella secuencia que sea la mejor según un determinado criterio. En la Figura 1 se representa un problema sencillo de búsqueda mediante un grafo. Ei es el estado inicial y E0 es el estado objetivo. Mediante la aplicación de operadores de estado se cambiará de estados (transición representada por flechas en la Figura 1) y el orden en que se apliquen esos operadores vendrá determinado por el algoritmo de búsqueda. Ei Ej Ek E0 Figura 1. Búsqueda de estados. © Universidad Internacional de La Rioja (UNIR) Para resolver un problema mediante búsqueda deben definirse en primer lugar los componentes que lo forman: Técnicas de Inteligencia Artificial 5 Tema 9. Ideas clave   Descriptores de estado: estructura simbólica capaz de representar cada estado.  Descriptores de operación: herramientas computaciones capaces de transformar la representación del estado para poder inspeccionar sistemáticamente el espacio de estados candidatos.  Descriptores de algoritmo de búsqueda: orden en que se aplican los operadores a los diferentes estados para llegar al estado objetivo. El algoritmo de búsqueda ha de ser un método efectivo de organizar las transformaciones entre estados para así obtener el objeto deseado tan pronto como sea posible. Este tipo de búsqueda se aplica, entre otros ámbitos, en la búsqueda en juegos. Por ejemplo, en el juego de ajedrez cada contrincante realiza una búsqueda entre todas las jugadas que puede realizar en cada instante para realizar la jugada que le sea lo más favorable posible respecto al estado en el que se encuentra. En este caso las reglas del juego marcan las posibles operaciones de transición entre estados. La investigación en robótica es uno de los ámbitos en los que se han utilizado técnicas de búsqueda de estados para la resolución de problemas. Programar un robot consiste en integrar varias funciones, entre las que se incluye la percepción del entorno que le rodea a través de sensores, formulación de planes de actuación y la realización de esos planes mediante actuadores. Un controlador recibirá los estímulos, procesará datos, tomará decisiones y enviará los comandos correspondientes a los actuadores que los convertirán en acciones. A continuación, se muestra un ejemplo referido específicamente a la generación de planes de actuación que se utiliza típicamente para ilustrar la resolución de este tipo © Universidad Internacional de La Rioja (UNIR) de problemas mediante búsqueda. El problema se denomina «Mundo de bloques» y en él se plantea un robot que tiene un repertorio finito de acciones que puede ejecutar para alcanzar un objetivo. El robot dispone de un brazo móvil capaz de cambiar de sitio a unos cuantos bloques situados sobre una mesa. El entorno del Técnicas de Inteligencia Artificial 6 Tema 9. Ideas clave  robot estará formado por la descripción de los distintos estados por los que atraviesa el mundo de bloques tras las actuaciones del robot sobre él. El planteamiento sigue el modelo propuesto para el planificador automático utilizado en robótica STRIPS (Stanford Research Institute Problem Solver), utilizando un formalismo bastante intuitivo basado en lógica para representar estados y operadores (Fikes & Nilsson, 1971). Partiendo de la situación inicial mostrada en la Figura 2: C A B Esta situación de partida se puede describir mediante el conjunto de fórmulas lógicas: SOBRE(C, A) SOBRE_LA_MESA(A) LIBRE(C) MANO_LIBRE SOBRE_LA_MESA(B) LIBRE(B) Para elaborar el plan de actuaciones, se ha de conocer el objetivo al que se desea llegar. En este caso es que todos los bloques estén uno sobre otro tal y como se © Universidad Internacional de La Rioja (UNIR) muestra en la Figura 3. Técnicas de Inteligencia Artificial 7 Tema 9. Ideas clave  A B C Por tanto, el objetivo es obtener una descripción del estado del entorno del robot dado por la conjunción de las fórmulas: MANO_LIBRE SOBRE(B,C) SOBRE(A,B) SOBRE_LA_MESA(C) Para ello se han de aplicar operadores STRIPS que representan una acción mediante tres componentes:  Precondiciones (P): prerrequisitos que han de ser ciertos en la descripción del entorno para la realización de la acción.  Borrar (B): fórmulas que se han de borrar de la descripción del entorno una vez aplicada la acción ya que dejan de ser ciertas.  Añadir (A): fórmulas que se han de añadir a la descripción del entorno una vez aplicada la acción. El modelo se completa con las reglas que simulan las acciones posibles del robot y que este tiene programadas, tales como: © Universidad Internacional de La Rioja (UNIR) COGER(X) P: LIBRE(X), MANO_LIBRE B: LIBRE(X), MANO_LIBRE A: COGIENDO(X) Técnicas de Inteligencia Artificial 8 Tema 9. Ideas clave  POSAR(X) P: COGIENDO(X) B: COGIENDO(X) A: SOBRE_LA_MESA(X), LIBRE(X), MANO_LIBRE APILAR(X,Y) P: COGIENDO(X), LIBRE(Y) B: COGIENDO(X), LIBRE(Y) A: MANO_LIBRE, SOBRE(X,Y), LIBRE(X) DESAPILAR(X,Y) P: MANO_LIBRE, LIBRE(X), SOBRE(X,Y) B: MANO_LIBRE, LIBRE(X), SOBRE(X,Y) A: COGIENDO(X), LIBRE(Y) COGER(X) corresponde a la acción de coger el bloque X de la mesa con el brazo, POSAR(X) se refiere a posar el bloque X sobre la mesa, APILAR(X,Y) es situar el bloque X sobre el bloque Y, y DESAPILAR(X,Y) se refiere a coger el bloque X que está situado sobre el bloque Y. Estas acciones constan de tres partes. La primera P son las precondiciones que se han de dar para la aplicación de la acción, la segunda B y la tercera A son las fórmulas que se han de borrar y añadir, respectivamente, a la descripción del entorno si esa acción se ejecuta (es, por tanto, parte de la consecuencia de la acción). La planificación de las acciones del robot se puede entonces obtener mediante la aplicación de algún procedimiento de búsqueda entre las descripciones posibles que resultan de ejecutar distintas acciones que transformen el entorno desde la situación de partida hasta el estado final u objetivo. La solución es el siguiente plan de acciones: © Universidad Internacional de La Rioja (UNIR) DESAPILAR(C,A) POSAR(C) COGER(B) APILAR(B,C) COGER(A) APILAR(A,B) Técnicas de Inteligencia Artificial 9 Tema 9. Ideas clave  Las siguientes secciones abordan diferentes procedimientos de búsqueda que permiten resolver este tipo de problemas de búsqueda de estados. 9.3. Dirección de la búsqueda El objetivo del proceso de búsqueda se resume en encontrar un camino a través del conjunto de estados entre el estado o estados iniciales y el estado o los estados finales u objetivos. Esta búsqueda puede hacerse en dos direcciones:  Hacia adelante (del inicio al fin).  Hacia atrás (del fin al inicio). Existen modelos de búsqueda que permiten que estos procedimientos sean simétricos. En este caso cualquiera de estas estrategias de búsqueda tiene validez. Búsqueda hacia adelante Se trata de una búsqueda guiada por los datos, aplicando información disponible para obtener nueva información. Por ejemplo, si: el objetivo es conocer C: A A → B © Universidad Internacional de La Rioja (UNIR) B → C Conocido A y sabiendo que si se cumple A se cumple B, se busca cambiar del estado al estado para conocer B. Una vez conocido B se llega al estado porque si se cumple B se cumple C y se alcanza así el objetivo de conocer C. Técnicas de Inteligencia Artificial 10 Tema 9. Ideas clave  Búsqueda hacia atrás Se parte del objetivo hasta llegar al estado inicial. Por ejemplo: A A → B B → C Sabiendo cuál es el objetivo, conocer C, hace falta encontrar B, saber si B es cierto ya que, de acuerdo con , si B es cierto, entonces C es cierto. C ↓ B ↓ A Hay por tanto que encontrar A puesto que se sabe que si A es cierto (), B es cierto () y, por tanto, C es cierto (). ¿Qué método de búsqueda se debe aplicar? Existen algunos criterios para seleccionar el mecanismo de búsqueda. A continuación, se describen tres de ellos:  Número de estados iniciales y finales: normalmente es más conveniente ir del conjunto con menor número de elementos al de mayor número de elementos. Por ejemplo, en el ejemplo bien conocido del llamado «problema de la lechera»: © Universidad Internacional de La Rioja (UNIR) «Se dispone de dos medidores de líquidos; uno de 5 litros y el otro de 7. Inicialmente ambos están vacíos y, en cualquier momento pueden ser llenados o vaciados usando un depósito de leche con suficiente capacidad. La leche también puede ser traspasada de uno a otro medidor hasta que el primero se vacíe o hasta que el segundo se llene. El problema consiste en Técnicas de Inteligencia Artificial 11 Tema 9. Ideas clave  encontrar la secuencia de acciones que se deben seguir para que en el mayor de los medidores se disponga exactamente de 4 litros». Se conoce el estado inicial, con ambas jarras vacías, y el conjunto de estados finales: todos los estados posibles que contengan 4 litros en el mayor de los medidores: 6 estados. Parece, por tanto, más sencillo buscar desde el estado inicial alguno de los 6 posibles estados finales. Si se realiza la búsqueda hacia atrás no se sabría desde qué estado final es más fácil encontrar una solución; incluso en algunos casos desde algún estado final no es accesible el estado inicial. En este ejemplo, por tanto, se debería iniciar una búsqueda en paralelo desde todos los nodos finales si quisiéramos adoptar una estrategia de búsqueda hacia atrás.  Factor de ramificación (branching factor): el criterio es caminar en el sentido en que el factor de ramificación sea más pequeño, esto es, el número medio de estados accesibles directamente desde cada nodo en la dirección de búsqueda sea menor. Un posible ejemplo podría ser la resolución del problema de ir desde casa a un lugar desconocido. Dado que un propietario conoce los alrededores de su casa, si busca un camino hacia atrás (de lo desconocido hacia su casa) resultará más fácil que lo contrario, ya que es de suponer que encontrará cruces en los cuales sabrá por dónde volver con más facilidad a su casa que si hiciera el recorrido inverso, pretendiendo en los cruces tratar de llegar al lugar desconocido.  La necesidad de justificar los pasos que se siguen en el razonamiento. Si existe esta necesidad, es importante proceder en la dirección que más se aproxime al modo de pensar del futuro usuario del sistema. Este es el caso típico de los sistemas expertos de diagnóstico y propuesta de soluciones que siguen un método © Universidad Internacional de La Rioja (UNIR) de razonamiento hacia atrás. Por ejemplo, un ingeniero ante un programa de detección de fallos y diagnóstico siempre querrá justificar los pasos seguidos en el razonamiento, razonando hacia Técnicas de Inteligencia Artificial 12 Tema 9. Ideas clave  atrás hasta determinar las causas de los fallos. Razonando hacia atrás el sistema podrá responder a preguntas del tipo «¿Por qué debo hacer esta comprobación?» respondiendo «porque eso ayudaría a determinar si el problema es debido a un fallo eléctrico o un fallo de software». El problema que existe con este tipo de criterios tan generales es que no siempre son aplicables. Por ejemplo, en el primer caso, no siempre se sabe cuál es el número de estados finales. Por otra parte, el factor de ramificación es normalmente difícil de aproximar. Por último, también debe tenerse en cuenta que existe una tercera posibilidad y es usar los dos tipos de razonamiento, hacia adelante o hacia atrás, de forma combinada. Otro factor que permite clasificar los algoritmos de búsqueda es la aplicación de la información disponible sobre el problema para su resolución. Así, los algoritmos de búsqueda se pueden dividir en dos grandes grupos, atendiendo al papel que juega el conocimiento en la estrategia de control de un sistema de búsqueda:  Búsqueda exhaustiva o a ciegas: no se tiene en cuenta la posible localización del objetivo. Estos algoritmos no utilizan ninguna información del problema e ignoran hacia dónde se dirigen hasta que encuentran el objetivo.  Búsqueda heurística: se tiene una estimación de lo que falta para llegar al estado objetivo. Los algoritmos utilizan información del problema para localizar el © Universidad Internacional de La Rioja (UNIR) objetivo. Las siguientes secciones explican estos dos grandes grupos de algoritmos de búsqueda. Técnicas de Inteligencia Artificial 13 Tema 9. Ideas clave  9.4. Búsqueda exhaustiva o a ciegas Búsqueda a ciegas Consiste en generar todos los estados posibles hasta encontrar la solución. Para generar todos los estados se aplica una regla de forma sistemática, sin tener en cuenta ninguna información del problema, ni del objetivo que se busca. Existen varios tipos de algoritmos de búsqueda a ciegas, tal y como se describe en las siguientes subsecciones. Búsqueda en amplitud En la búsqueda de estados se va generando un grafo como puede ser una malla o un árbol de estados como los mostrados en la Figura 1 o en la Figura 4. Si la búsqueda es en amplitud, a partir de un nodo se generan todos los hijos y, para cada hijo, todos los nietos, y así sucesivamente. Por tanto, cada nivel del árbol de estados se desarrolla completamente antes de desarrollar el siguiente nivel. Según los nodos de un nivel se generan, si no se ha llegado a la solución, se va al siguiente nivel para generar los nodos siguientes. Así, hasta encontrar el objetivo. Esta estrategia asigna mayor prioridad a los nodos con menor profundidad, generando los nodos por niveles tal y como se muestra en la Figura 4, en la que los números indican el orden en que se van generando los nodos: © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 14 Tema 9. Ideas clave  1 2 3 4 5 6 7 8 9 10 11 Figura 4. Ejemplo de búsqueda en amplitud. Así, se hace un recorrido uniforme del grafo que le da un carácter «lento pero seguro». En este algoritmo siempre se expande primero el nodo menos recientemente creado, siguiendo una estrategia FIFO (First-In, First-Out). Cuando los costes de ir de un nodo a otro son uniformes, se garantiza que se encontrará la solución con el camino más corto, esto es, la secuencia con menor número de estados hasta el estado objetivo. Sin embargo, si el coste no es uniforme, no se podrá garantizar que el camino sea el más corto. El problema es la gran cantidad de memoria necesaria y la lentitud en encontrar la solución si esta se encuentra a gran profundidad. Aunque algorítmicamente se puede considerar una búsqueda perfecta (siempre encuentra solución óptima), no lo es desde el punto de vista de la IA, ya que es inflexible frente a cualquier tipo de conocimiento que se tenga sobre el problema. Búsqueda en profundidad © Universidad Internacional de La Rioja (UNIR) Esta estrategia da prioridad a los nodos más profundos en el grafo de búsqueda de tal forma que estos se expanden o desarrollan, para generar posibles soluciones, antes que otros nodos menos profundos, tal y como se muestra en la Figura 5. Técnicas de Inteligencia Artificial 15 Tema 9. Ideas clave  Tras cada expansión o desarrollo de un nodo, de los hijos que acaban de ser generados se selecciona uno para ser de nuevo desarrollado. Esta exploración hacia abajo se desarrolla hasta que, por alguna razón, el proceso queda bloqueado. En tal caso, el proceso continúa desde el nodo más profundo que haya sido dejado atrás sin explorar. Dicho de otro modo, desde el último punto en el que se tomó una decisión dejando alguna alternativa sin explorar. De esta forma, se toma un camino y se sigue hasta que se encuentra la solución o un callejón sin salida, en cuyo caso se vuelve hacia atrás. 1 2 8 3 5 9 4 6 7 10 Figura 5. Ejemplo de búsqueda en profundidad. En este algoritmo siempre se expande el nodo más recientemente creado, siguiendo la estrategia LIFO (Last-In, First-Out). El problema de este algoritmo es que no garantiza que se encuentre la solución por el camino más corto. Además, podría suceder que una solución se encuentre a poca © Universidad Internacional de La Rioja (UNIR) profundidad, pero no se encuentre pronto porque previamente se han explorado caminos muy profundos. Sin embargo, tiene la ventaja de que si la tasa de generación de hijos es muy alta, se mitiga el hecho de poder quedarse sin memoria, tal y como es más probable que pase en la búsqueda en amplitud. Técnicas de Inteligencia Artificial 16 Tema 9. Ideas clave  Esta estrategia funciona bien cuando abundan las soluciones en el grafo y todas ellas son igualmente deseables (no conduce más que de casualidad a una solución óptima). También puede resultar adecuada cuando existen medios que nos pueden indicar pronto el que se ha elegido una dirección equivocada con lo cual podremos bloquear la búsqueda en este camino. Los dos algoritmos (búsqueda en amplitud y en profundidad) funcionan bien en grafos y en árboles; aunque con árboles en búsqueda en profundidad se puede entrar en un camino infinito. Además, estos dos algoritmos son algoritmos de fuerza bruta, se va de una rama a otra sin tener en cuenta ninguna información sobre el problema. Búsqueda en profundidad acotada En vez de coger un camino hasta el final, se aplica búsqueda en profundidad hasta un nivel y, si con esa profundidad no se consigue el objetivo, se realiza búsqueda en profundidad a partir de un nivel superior. Así, se evita centrarse sólo en una parte del árbol. Se define una profundidad límite más allá de la cual no se buscará. Esto evita que el proceso no pare en grafos infinitos (o en los que haya una rama infinita). Búsqueda en profundidad iterativa Se busca con profundidad acotada, partiendo de una cota inicial e incrementándola en uno hasta que se llegue a la solución. © Universidad Internacional de La Rioja (UNIR) Con esta forma de búsqueda, se intenta combinar las ventajas de búsqueda en anchura y búsqueda en profundidad. Siempre se va a encontrar el camino más corto y no se necesita tener todos los nodos en memoria. Técnicas de Inteligencia Artificial 17 Tema 9. Ideas clave  Los algoritmos de búsqueda a ciegas no se pueden aplicar siempre, pero en el caso de que se puedan aplicar dan muy buenos resultados. A continuación, se expone un ejemplo para ilustrar el funcionamiento de los algoritmos de búsqueda a ciegas. Dado el árbol que se muestra en la Figura 6, se representa en las Figuras 7, 8 y 9 los órdenes en que se expanden los nodos en función del tipo de búsqueda. Nótese que para la búsqueda en profundidad iterativa la cota inicial de profundidad tiene un valor de 0, por lo cual se expande únicamente el nodo raíz. En el siguiente paso, la profundidad tiene un valor de 1, con lo que se extiende el nodo raíz y sus hijos. Figura 6. Árbol de ejemplo. 1 2 3 4 5 6 7 8 9 10 © Universidad Internacional de La Rioja (UNIR) 11 12 13 14 Figura 7. Orden en que se expanden los nodos si se aplica búsqueda en anchura. Técnicas de Inteligencia Artificial 18 Tema 9. Ideas clave  1 2 7 10 3 6 8 9 11 14 4 5 12 13 Figura 8. Orden en que se expanden los nodos si se aplica búsqueda en profundidad. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 19 Tema 9. Ideas clave  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Figura 9. Orden en que se expanden los nodos si se aplica búsqueda en profundidad iterativa. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 20 Tema 9. Ideas clave  9.5. Búsqueda heurística Métodos de búsqueda a ciegas Son métodos exhaustivos para encontrar caminos a un estado objetivo. En principio proporcionan una solución al problema de encontrar el camino, pero a menudo no es viable su uso porque la búsqueda expandirá demasiados nodos antes de encontrar un camino. Para muchas tareas es posible declarar principios o reglas que ayudan a reducir la búsqueda. Cualquier técnica usada para acelerar la búsqueda depende de la información disponible sobre el problema representado por el grafo. En los métodos de búsqueda heurística se aplica información del problema para encontrar la solución. A esta información disponible se le denomina información heurística, mientras que los procedimientos de búsqueda usados son denominados métodos de búsqueda heurística. Estos algoritmos tienen en cuenta que un estado generado puede no ser solución, pero podría estar más cerca de ella. En ese caso la búsqueda se seguiría desde este nodo en adelante. Para aplicar este método de búsqueda se emplea una función denominada heurístico, que mide la proximidad de los nodos al objetivo. Heurístico (regla heurística o método heurístico) Es una regla de estrategia y simplificación, que limita drásticamente la búsqueda de soluciones en grandes espacios de problemas. © Universidad Internacional de La Rioja (UNIR) Se enumeran a continuación algunos aspectos en los que la información heurística puede ser aplicada para expandir un árbol de manera eficiente: Técnicas de Inteligencia Artificial 21 Tema 9. Ideas clave   Decidir qué nodo debe ser expandido o desarrollado en todas sus posibilidades en lugar de tener un criterio puramente igualitario de la potencia de los nodos candidatos.  Decidir qué sucesor o sucesores deben ser considerados en primer lugar en lugar de considerar todos los posibles sucesores a la vez.  Decidir qué nodos deben ser descartados o podados del espacio de búsqueda. El objetivo de la búsqueda heurística es, por tanto, reducir el número de nodos examinados y la efectividad depende del heurístico seleccionado. Sin embargo, se da el hecho de que no es fácil seleccionar el heurístico. A continuación, se muestra un ejemplo basado en el conocido problema del «Puzle 8» en el que se proponen dos posibles heurísticos. La solución de este rompecabezas consiste en, a partir de una configuración inicial dada, reordenar ocho elementos numerados móviles situados en un tablero de 3 × 3 para conseguir una configuración final dada (ver Figura 10). Figura 10. Problema «Puzle 8». © Universidad Internacional de La Rioja (UNIR) Los heurísticos propuestos son: Técnicas de Inteligencia Artificial 22 Tema 9. Ideas clave   h1: número de fichas mal colocadas, mientras mayor sea este valor, peor.  h2: distancia Manhattan: la suma de las distancias de las fichas mal colocadas. La distancia se mide como el número de movimientos necesarios para situar la ficha en la posición final deseada. La Figura 11 muestra los valores de estos heurísticos para diversas configuraciones según la ficha que se mueva desde la posición inicial mostrada en la Figura 10. Figura 11. Valores de heurísticos para diversas configuraciones del puzle 8. © Universidad Internacional de La Rioja (UNIR) Se ve en este ejemplo sencillo cómo el heurístico que se selecciona determina la rapidez en conseguir el objetivo. El movimiento adecuado es el segundo y, por tanto, el heurístico 2 en este ejemplo parece más adecuado. Técnicas de Inteligencia Artificial 23 Tema 9. Ideas clave  Este caso es muy sencillo, pero, en general, no es fácil definir el heurístico adecuado. Más aún, los heurísticos no garantizan la obtención de soluciones óptimas; de hecho, no garantizan ningún tipo de solución: se estima si un nodo está más cerca que otro para llegar a la solución, aunque como es una estimación podría dar lugar a una equivocación. En conclusión, todo lo que se puede decir de un heurístico útil es que ofrece soluciones que son suficientemente buenas la mayoría de las veces. Escalada simple o hill climbing La interpretación intuitiva más sencilla y de la que toma el nombre el método de búsqueda «escalada simple» consiste en considerar el proceso como la escalada a una montaña: el objetivo es alcanzar la cima y el estado de búsqueda es el punto donde se encuentra el escalador. La regla de la que se dispone es seguir escalando hasta que se llegue a un punto a partir del cual no se pueda ascender más. Mediante este método en el momento que se encuentra un estado más favorable que el actual, se avanza al nuevo estado encontrado. Para simplificar la explicación se puede considerar montañas de dos dimensiones con lo que la escalada consiste en la búsqueda de un máximo de una función real de variable real: f. El escalador hipotético, si se encuentra en un punto x0, si los saltos que puede dar son de amplitud δ, podría dirigirse a x0 + δ o quedarse donde está. Dependiendo de la altura f(x0 + δ) que se obtenga al avanzar y la altura actual del © Universidad Internacional de La Rioja (UNIR) escalador f(x0) se decidirá avanzar a la nueva posición si la situación tras el avance es mejor que la situación sin avanzar, porque la altura se incremente. Si la altura no se incrementa al avanzar, se da como solución la posición x0 (ver Figura 12). Técnicas de Inteligencia Artificial 24 Tema 9. Ideas clave  f(x) f(x0+δ) f(x0) x0 x0+δ x Figura 12. Escalada simple: búsqueda del máximo de una función. Este método, presenta problemas de máximos locales y/o mesetas como intuitivamente se puede concluir observando las funciones representadas en la Figura 13. Figura 13. Máximo local (función de la izquierda) y meseta (función de la derecha). Este método resulta interesante para maximizar o minimizar funciones y es el © Universidad Internacional de La Rioja (UNIR) algoritmo que se utiliza para, por ejemplo, sintonizar una emisora de radio. Se van haciendo movimientos del sintonizador de frecuencias en una dirección siempre que la calidad de la señal recibida mejore. Al llegar a un punto donde no mejora en ninguna de las dos direcciones se detiene la búsqueda en el dial. Técnicas de Inteligencia Artificial 25 Tema 9. Ideas clave  Escalada por máxima pendiente En el método de escalada simple, el algoritmo en el momento que encuentra un estado E’ más favorable que el actual E, se avanza al estado E’. Sin embargo, el método de escalada por máxima pendiente consiste en «explorar los alrededores» antes de seguir avanzando por la montaña. Cuando se está en un punto, se da un paso en todas las direcciones y se va por el mejor camino. Se consideran todos los posibles movimientos a partir del estado actual y se elige como nuevo estado el mejor de ellos. En este caso el escalador hipotético para avanzar desde un punto x0, si los saltos que puede dar son de amplitud δ, podría dirigirse o bien a x0 - δ o bien a x0 + δ. Dependiendo de la altura que tengan estas posibilidades, f(x0 - δ) y f(x0 + δ) respectivamente, y la del propio escalador, f(x0), se decidirá saltar a la mejor opción. Si la situación actual no es mejorable, la posición x0 se dará como solución. En el caso del ejemplo mostrado en la Figura 14, la decisión será saltar a x0 + δ. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 26 Tema 9. Ideas clave  Por tanto, mediante este método se exploran todos los posibles siguientes estados y se finaliza cuando se llega a un nodo en el que todos los siguientes estados son peores que el actual. Cuando se salta a la mejor opción, se asume que ese siguiente estado está más cerca del final. Este algoritmo obtiene una mejor ruta que el método de escalada simple, pero es más lento, porque hay que evaluar todos los siguientes estados posibles y el número de operadores aplicables a un estado puede ser muy grande. Por tanto, puede suponer altos requerimientos de computación y de memoria. Aun así, en general estos algoritmos de escalada suelen ser muy rápidos, aunque, como principal inconveniente, presentan problemas de máximos locales y mesetas. Búsqueda «mejor el primero» o best-first Este algoritmo intenta combinar las ventajas de la búsqueda en amplitud y en profundidad. En cada paso del algoritmo se va a seguir un camino y se va a cambiar de ruta cuando haya una ruta más prometedora. El funcionamiento es el siguiente: se expande el nodo padre generando nodos hijos. El nodo padre se incluye en la lista de nodos cerrados o ya expandidos, mientras que los nodos hijos se incluyen en la lista de nodos abiertos o no expandidos. Analizando todos los nodos abiertos se comprueba si alguno de los nodos es el objetivo y, si ninguno lo es, se escoge como siguiente nodo a expandir el que parezca más prometedor, de acuerdo al valor de una función de evaluación que se esté aplicando. Típicamente esta función se basará en un heurístico que estime la cercanía del nodo al objetivo. © Universidad Internacional de La Rioja (UNIR) Se muestra, a continuación, un ejemplo para ilustrar los diferentes pasos del algoritmo y cómo progresan los nodos cerrados y abiertos. Las listas que se muestran en el ejemplo están ordenadas por orden de prioridad, tomando por tanto el primer elemento en la lista como el nodo a expandir. El número asociado a cada nodo indica Técnicas de Inteligencia Artificial 27 Tema 9. Ideas clave  el valor de la función de evaluación. Un nodo es más prometedor, cuanto más pequeño sea el valor de esta función. El objetivo es P. La Figura 15 muestra el grafo del ejemplo y los diferentes pasos del algoritmo son los siguientes: ABTOS = [A5] CDOS = [ ] Evaluación A5 ABTOS = [B4, C4, D6] CDOS = [A5] Evaluación B4 ABTOS = [C4, E5, F5, D6] CDOS = [B4, A5] Evaluación C4 ABTOS = [H3, G4, E5, F5, D6] CDOS = [C4, B4, A5] Evaluación H3 ABTOS = [O2, P3, G4, E5, F5, D6] CDOS = [H3, C4, B4, A5] Evaluación O2 ABTOS = [P3, G4, E5, F5, D6] CDOS = [O2, H3, C4, B4, A5] Evaluación P3 A-5 B-4 C-4 D-6 E-5 F-5 G-4 H-3 I J © Universidad Internacional de La Rioja (UNIR) K L M N O-2 P-3 Q R S T Figura 15. Grafo del ejemplo de búsqueda «primero el mejor». Técnicas de Inteligencia Artificial 28 Tema 9. Ideas clave  El problema que presenta este algoritmo es que hay que mantener todos los nodos abiertos (o no expandidos) en la memoria de trabajo. Además, el heurístico puede fallar, como es el caso de la evaluación del nodo O en el ejemplo anterior que no se acerca precisamente al objetivo, aunque el algoritmo es lo suficientemente bueno como para recuperarse del fallo. Por otra parte, este algoritmo tiene la ventaja de valer tanto para árboles como para grafos. Algoritmo A* El algoritmo A* se puede considerar una particularización del algoritmo de búsqueda «mejor el primero» en que la función de evaluación f(n) se define como sigue: Para cada nodo n, f(n) = h(n) + g(n) siendo:  h(n): heurístico, coste estimado del camino más corto del nodo actual al nodo objetivo (h(n)=0 si n es un nodo objetivo). n → nO  g(n): coste real del camino conocido más corto desde el nodo origen al nodo n a evaluar. ni → n Por lo tanto, la función de evaluación f(n) es el coste del camino más corto desde el © Universidad Internacional de La Rioja (UNIR) nodo inicial al nodo objetivo condicionado a pasar por el nodo n.Cabe comentar que la definición de h(n) es una tarea complicada y determinará el rendimiento adecuado de la aplicación de este algoritmo. Técnicas de Inteligencia Artificial 29 Tema 9. Ideas clave  El algoritmo seleccionará como nodo a expandir el que tenga un menor valor de f(n). Este algoritmo tiene en cuenta por tanto la medida de la profundidad, utilizando una estimación del coste del camino total. Si se define h(n) = 0, se está realizando una búsqueda en anchura, que siempre da lugar al camino más corto, pero cuyo coste computacional es muy elevado. Este algoritmo impone una restricción para alcanzar el objetivo por el camino de menor coste: la función h nunca ha de sobreestimar el coste para alcanzar el objetivo. Una función h de este tipo es una heurística admisible. A continuación, se utiliza de nuevo el problema del «Puzle 8» para ilustrar lo que no se considera una heurística admisible. En la Figura 16, la configuración F es la final deseada, la configuración I es la inicial y la configuración A representa un posible movimiento de una ficha desde la configuración I. © Universidad Internacional de La Rioja (UNIR) Figura 16. Ejemplo de problema del «Puzle 8». Para analizar si la configuración A está más cerca del objetivo F, se consideran los heurísticos siguientes: Técnicas de Inteligencia Artificial 30 Tema 9. Ideas clave  h1(n) = número de fichas mal colocadas. h2(n) = distancia Manhattan. h3(n) = h2(n) + 3·S(n). S(n) es la cuenta de secuencia obtenida recorriendo sucesivamente las casillas no centrales y anotando dos puntos en la cuenta por cada ficha no seguida por su ficha sucesora y 0 puntos para las otras; si hay una ficha en el centro se anota 1. Por ejemplo, este cálculo, para la posición inicial sería: h3(posición inicial) = 3 + 3 (2 + 2 + 1) = 18 En la Tabla 1 se muestran los valores de estos heurísticos para las configuraciones I y A: Tabla 1. Valores de los heurísticos propuestos. Los dos primeros heurísticos son admisibles, mientras que h3(n) no es admisible, dado que es mayor al número de movimientos que hay que realizar para llegar a la solución F. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 31 Tema 9. Ideas clave  9.6. Búsqueda en juegos Búsqueda en juegos Consiste en determinar el conjunto de jugadas que permiten ganar al oponente. Las búsquedas más sencillas son las relativas a problemas de búsqueda de estrategias ganadoras en juegos de dos jugadores con movimientos alternados y en los que no interviene el azar. Concretamente, son juegos de los llamados de información completa y suma nula:  La información completa se refiere al hecho de que cada jugador conoce las jugadas que se hicieron y todas las que se pueden hacer en cada momento y por cada jugador.  La suma nula se refiere a juegos en los que las situaciones finales son o de victoria para uno de los jugadores (y, por tanto, derrota para el otro) o empate; se excluyen, por tanto, juegos en los que puedan perder o ganar a la vez los dos jugadores. Juegos típicos de este tipo son el ajedrez, las damas, el tres-en-raya, etc. Las partidas posibles que se pueden realizar en estos juegos se pueden describir mediante árboles o grafos en los cuales las hojas corresponden a situaciones de victoria para alguno de los jugadores, de derrota o tablas. Los nodos intermedios representan situaciones donde debe mover uno u otro jugador. © Universidad Internacional de La Rioja (UNIR) Se pueden diferenciar dos tipos de juegos:  Juegos donde es posible desarrollar todo el espacio de estados. Técnicas de Inteligencia Artificial 32 Tema 9. Ideas clave   Juegos donde no es posible desarrollar todo el espacio de estado, porque es muy grande. En este caso se aplican heurísticos para estimar si una jugada es buena o no. Como ejemplo de la búsqueda en juegos se explica el algoritmo sencillo Minimax. Se consideran dos jugadores: MIN y MAX y el objetivo es que gane MAX. MAX intentará maximizar su ventaja y minimizar la de MIN. Cada nivel del árbol va a estar formado por nodos MAX o MIN, según a quien le toque jugar. Se supone que MIN tiene la misma información e inteligencia que MAX. Además, MIN intentará hacer lo peor para MAX. El algoritmo Minimax elegirá el mejor movimiento para MAX suponiendo que el contrincante elegirá lo peor para MAX. Una vez determinado el grafo de todas las posibles jugadas, el proceso a seguir es el siguiente: 1. Asignar a los nodos finales un valor: 1 → victoria MAX 0 → victoria MIN 2. Propagar las etiquetas o valores de esta función hacia arriba. Si se tiene un nodo MAX se toma el máximo de los hijos y, si se tiene un nodo MIN, se toma el mínimo de los hijos. 3. El camino de victoria se obtiene uniendo el trazado que va por los «1» (ver figura 17). © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 33 Tema 9. Ideas clave  1 MAX 0 1 MIN 0 1 1 MAX 0 0 1 1 MIN Figura 17. Ejemplo de árbol resultado de ejecutar el algoritmo Minimax. El procedimiento MINIMAX toma las decisiones óptimas en cada jugada y, si es posible, ganará la partida o, si no, la empatará. 9.7. Costes Los procedimientos de búsqueda inteligente en problemas de una cierta magnitud, como suelen ser los problemas de inteligencia artificial, deben disponer de estrategias de control adecuadas. Esto implica que se debe guiar la búsqueda basándose en conocimientos específicos del tema a tratar, tal y como se hace en la búsqueda heurística. El problema radica en saber cómo se maneja y representa el conocimiento para que este sea útil. En la búsqueda exhaustiva (con información nula) es necesario expandir todos los nodos, lo que conlleva un elevado coste debido a la expansión del árbol. Por otra parte, a medida que se tiene más información (mejor es el heurístico), se expanden © Universidad Internacional de La Rioja (UNIR) solo los nodos necesarios con lo que disminuye el coste debido a la expansión del árbol. Sin embargo, el coste debido a la estrategia de control aumenta a medida que se emplea un heurístico mejor; ya que calcular el heurístico conlleva mucho gasto computacional. Técnicas de Inteligencia Artificial 34 Tema 9. Ideas clave  Por lo tanto, el problema del coste se puede resumir en la suma de los costes: Debidos a la estrategia de control. Debidos a la expansión de los nodos del árbol. Estas consideraciones sobre los costos de la estrategia de control y de la expansión del árbol en un proceso de búsqueda pueden resumirse a través del gráfico de la Figura 18. Coste total de la búsqueda Coste del proceso de búsqueda Debido a la estrategia de control Debido a la expansión del árbol (reglas) Información empleada en la búsqueda Figura 18. Coste del proceso de búsqueda en función de la información. Analizando el gráfico anterior, el problema está en encontrar el punto de corte de las gráficas correspondientes al consumo causado por la estrategia de control y al coste debido a la expansión del árbol, ya que marca el mínimo del costo total utilizado en el proceso de resolución del problema. 9.8. Aplicaciones prácticas y ejemplos de implementación © Universidad Internacional de La Rioja (UNIR) Aplicaciones prácticas en la literatura Cualquier usuario digital está acostumbrado al uso de aplicaciones como Google Maps o Bing Maps a la hora de encontrar el camino más corto cuando realizan un Técnicas de Inteligencia Artificial 35 Tema 9. Ideas clave  viaje entre dos puntos, teniendo en consideración las restricciones impuestas por el callejero y el trazado de las vías de comunicación. Los algoritmos más empleados para la planificación de rutas son aquellos basados en el algoritmo de Bellman-Ford, el algoritmo de Floux-Warshall y el algoritmo de Dijkstra, como un ejemplo de algoritmo codicioso (greedy) o algoritmo Shortest Path First o SPF. Estos algoritmos codiciosos buscan la ruta más corta o, más correctamente, que tienen menor coste para el usuario en términos de combustible, distancia o tarifas. Con el fin de optimizar el coste global, se crearon algoritmos como el A* que incluía un heurístico para combinar el coste de cada paso y el coste global. Profundizando más en la parte de la algoritmia, actualmente hay muchos algoritmos para encontrar el camino más corto en la literatura. El algoritmo de Dijkstra es el más utilizado para encontrar el camino más corto entre dos vértices (Bozyiğit, Alankuş, y Nasiboğlu, 2017). El algoritmo encuentra las trayectorias más cortas desde el vértice de la fuente hasta todos los demás vértices (problema de la trayectoria más corta de una sola fuente) en poco tiempo, suponiendo que los pesos de todos los bordes no son negativos. Aunque, el Algoritmo de Dijkstra es eficiente en términos de tiempo de recorrido para determinar el camino más corto de manera óptima, el camino propuesto está lejos de ser la ruta ideal para la mayoría de los usuarios; porque el Algoritmo de Dijkstra no tiene en cuenta el número de transferencias o las distancias a pie. Estas dos deficiencias son desventajas importantes para los usuarios finales. En este sentido, a última década ha sido testigo de un asombroso progreso en el rendimiento de los algoritmos de trayecto más corto en las redes de transporte. Para el encaminamiento en redes de carreteras, en particular, los algoritmos modernos pueden ser hasta siete órdenes de magnitud más rápidos que las soluciones estándar (Bast et al. 2016). Los enfoques exitosos aprovechan las diferentes propiedades de © Universidad Internacional de La Rioja (UNIR) las redes de carreteras que las hacen más fáciles de manejar que los gráficos generales, como la dirección de los objetivos, una estructura jerárquica fuerte y la existencia de pequeños separadores. Técnicas de Inteligencia Artificial 36 Tema 9. Ideas clave  Aunque algunas de las primeras técnicas de aceleración se basaban en gran medida en la geometría (después de todo, las redes de carreteras están incrustadas en la superficie de la Tierra), ningún algoritmo actual de última generación utiliza explícitamente las coordenadas de los vértices. Mientras que todavía se ve el desarrollo ocasional (y la publicación) de algoritmos basados en geometría, estos están consistentemente dominados por técnicas establecidas. En particular, el algoritmo reciente de Jerarquías Arteriales (Zhu et al., 2017) se compara con el algoritmo CH (Contraction Hierarchies, que tiene consultas ligeramente más lentas), pero no con otras técnicas previamente publicadas (como CHASE, HL y TNR) que lo dominarían fácilmente. Otra lección importante de los desarrollos recientes es que una ingeniería cuidadosa es esencial para liberar toda la potencia computacional de las arquitecturas informáticas modernas. Algoritmos como CRP, CSA, HL, PHAST y RAPTOR, por ejemplo, logran gran parte de su buen rendimiento explotando cuidadosamente la localidad de referencia y el paralelismo (a nivel de instrucciones, núcleos e incluso GPUs). Este tipo de algoritmos se han utilizado en sistemas que sirven a millones de usuarios cada día, incluyendo proyectos relacionados con el enrutamiento para empresas como Apple, Esri, Google, MapBox, Microsoft, Nokia, PTV, TeleNav, TomTom y Yandex. Aunque las empresas tienden a ser reservadas sobre los algoritmos que utilizan, en algunos casos esto es de conocimiento público. TomTom utiliza una variante de los indicadores de arco con accesos directos para realizar consultas dependientes del tiempo (Zhu et al. 2017). Bing Maps de Microsoft utiliza CRP para el enrutamiento en redes de carreteras (Zhu et al. 2017). OSRM, un popular motor de planificación de rutas que utiliza datos de OpenStreetMap, utiliza CH para las consultas (Luxen y Vetter, 2011). El algoritmo Transfer Patterns (Bast et al., 2010) se utiliza para la planificación de viajes de transporte público en Google Maps desde © Universidad Internacional de La Rioja (UNIR) 2010 (Abraham et al., 2012). Actualmente, OpenTripPlanner está utilizando RAPTOR (Abraham et al., 2013). En este tipo de algoritmos se basa el empleado por Google Maps (que utiliza una evolución mucho más eficiente en términos de rendimiento). Este tipo de búsquedas Técnicas de Inteligencia Artificial 37 Tema 9. Ideas clave  de rutas es utilizado también por aplicativos para la contratación de servicios VTC como Uber o Cabify. Además, servicios como Google incorporan información parcial