**IAIC** Práctica Semana 5 Búsquedas Ciegas e Informadas # Objetivo Esta práctica comparte mucho de la práctica anterior de representación en Espacios de Estados. En este caso estamos más interesados en las características particulares que debemos añadir para la resolución de los problemas por búsqueda y la implementación de heurísticas específicas para $A^*$. En la medida de lo posible, todas las soluciones deben implementarse haciendo uso de la librería proporcionada en el curso. Además, se proponen algunos ejercicios adicionales para ser realizados en papel y donde poner en práctica conceptos de contenido más teórico sobre las búsquedas estudiadas. # Librerías BFS y A* En la práctica anterior vimos cómo formalizar problemas de representación en Espacios de Estados. En este tema introducimos algunos algoritmos (ciegos e informados) para dar soluciones reales a problemas de búsqueda en esos espacios. !!!Tip

**Detalles: Búsquedas BFS**

Lista de ficheros asociados a Búsquedas BFS: + `Uninformed Explorations.nlogo`: Modelo de demostración en el que se muestran diversos recorridos no informados sobre un espacio de estados en forma de árbol. + `BFS.nls`: Fichero Fuente de NetLogo con los algoritmos genéricos asociados al algoritmo BFS. + `LayoutSpace.nls`: Fichero Fuente de NetLogo que contiene la librería para visualizar espacios de estados calculados (para diversas librerías que hacen uso de estructuras similares). + `BFS agents - Template.nlogo`: Modelo de solución BFS del problema del _puzle numérico_. Esta librería es realmente una extensión de la librería BSS explicada en el tema anterior, en consecuencia, tanto los estados (_AI:states_) como las transiciones (_AI:transitions_) siguen un comportamiento similar, pero se añaden las propiedades: Para los estados: + `path` : Contendrá la lista de estados por los que la búsqueda ha pasado para llegar desde el estado inicial hasta el actual. Las transiciones permanecen igual. La función principal de la librería **BFS** es el procedimiento `BFS`, que construye el grafo de estados que se obtiene a partir de un estado inicial dado (siguiendo los constructores en anchura definidos por el usuario) y comprueba si el estado objetivo ha sido alcanzado o no. `BFS` es por tanto un report, que devolverá: + `False` si no ha habido éxito en la búsqueda. + El *estado final* alcanzado, si dicho estado es un estado final válido que resuelve el problema. Ha de tenerse en cuenta que la búsqueda podría dar como resultado un proceso infinito, lo que en NetLogo puede provocar problemas de estabilidad en el motor de ejecución. Los datos de entrada de `BFS` son: + `#initial-state` : Contenido del estado inicial que da comienzo a la búsqueda. + `#final-state` : Contenido del estado final que se busca. En caso de que el estado final venga dado por una condición de parada, pero no por un estado concreto (como en el problema de las _N reinas_), esa condición de parada vendrá dada por un report que se explicará a continuación, y en este caso podemos pasarle cualquier dato como estado final, ya que no lo considerará. + `#debug?` : `True / False` - Indica si se mostrará el contenido en los estados, y las reglas en las transiciones. + `#visible?` : Muestra/Oculta estados y transiciones en el interfaz. Para el correcto funcionamiento de esta librería en el modelo principal se deben definir las siguientes funciones: + `AI:children-states` : Idéntico al caso `BSS`. + `AI:final-state?` : Función booleana de estados. Devuelve si el estado actual debe ser considerado un estado final. Este procedimeinto recibe como entrada un parámetro que, por ejemplo, permita comparar el estado actual con el `#final-state` en caso de que dicho estado final sea un estado concreto. Si no fuera así, el parámetro pasado no tiene utilidad y la verificación de si es final o no solo se basará en propiedades internas del estado actual. + `AI:equal?` : report que decide cuándo dos estados son iguales. Muchas veces podrá ser simplemente el comparador `=`, pero en caso de que el contenido de los estados sea una estructura más compleja (por ejemplo, un conjunto representado por una lista) puede ser necesario definir una igualdad más elaborada (por ejemplo, en el caso anterior, que no dependa del orden). Adicionalmente, debido a que `BFS` devuelve el estado final completo, del que podemos extraer el `path` que ha permitido construirlo, la librería proporciona un _report_ auxiliar, `extract-transitions-from-path`, que al ser ejecutado por un estado devuelve, a partir de la información almacenada en el estado, la sucesión (lista) de transiciones que se han aplicado para llegar desde el estado inicial hasta él. Obsérvese que este procedimiento no necesita ningún dato de entrada, ya que lo ejecuta el propio estado y él puede acceder a toda su información de manera directa. ~~~~ to-report extract-transitions-from-path report (map [[x1 x2] -> AI:transition ([who] of x1) ([who] of x2)] (bl path) (bf path)) end ~~~~

!!!Tip

**Detalles: Búsqueda $A^*$ **

Lista de ficheros asociados a Búquedas $A^*$: + `A-star.nls`: Fichero Fuente de NetLogo con los algoritmos genéricos asociados a la Búsqueda A*. + `LayoutSpace.nls`: Fichero Fuente de NetLogo que contiene la librería para visualizar espacios de estados calculados (para BFS y otras librerías que hacen uso de estructuras similares). + `A-star Problem Solver - Template.nlogo`: Modelo de solución A* para usar como plntilla en la práctica. Esta librería es realmente una extensión de la librería BFS, en consecuencia, tanto los estados (_AI:states_) como las transiciones (_AI:transitions_) siguen un comportamiento similar, pero se añaden las propiedades: Los estados permanecen igual. Para las transiciones: + `rule` : Al igual que en los casos anteriores, las reglas se representan como una lista `["rep" coste ..]`, donde destaca la segunda componente con el coste de aplicar dicha regla. + `cost-link` : Almacena el coste de la transición. Además, el algoritmo A* almacena toda la información de la búsqueda en una familia adicional de agentes denominada AI:searchers, que tienen las siguientes propiedades: + `memory` : Almacena el camino de nodos que ha recorrido A* desde el estado inicial hasta el nodo en el que se encuentra este buscador. + `cost` : Almacena el coste real del camino recorrido desde el estado inicial. + `total-expected-cost` : Almacena el coste total esperado desde el estado inicial hasta el objetivo. + `current-state`: Almacena el estado (_AI:state_) en el que se encuentra este buscador. + `active?` : Establece si este buscador esta activo, es decir, si los estados vecinos al suyo han sido explorados o no. La función principal de la librería **A-star** es el procedimiento `A*`, que construye el grafo de estados que se obtiene a partir del estado inicial (siguiendo la selección heurística definida por el usuario) y comprueba si el estado objetivo ha sido alcanzado o no. El grafo de estados subyacente se va construyendo de forma dinámica a medida que va siendo necesario. `A*` es por tanto un _report_, que devolverá: + `False` si no ha habido éxito en la búsqueda. + La memoria del buscador que ha alcanzado un estado final. Ha de tenerse en cuenta que la búsqueda podría dar como resultado un proceso infinito, lo que en NetLogo puede provocar problemas de estabilidad en el motor de ejecución. Los datos de entrada que espera `A-star` son los mismos que `BFS`: `#initial-state`, `#final-state`, `#debug?`, `#visible?`. Para el correcto funcionamiento de esta librería en el modelo principal se deben definir las siguientes funciones: + `AI:children-states` : Función de estados que devuelve una lista con información sobre los posibles sucesores del estado que lo ejecuta. Cada estado devuelto deber ser un par `[s r]`, donde `s` es el contenido del nuevo estado, y `r` es una regla con la estructura esperada (`["rep" c ...]`). + `AI:final-state?` : Similar al de `BFS`. + `AI:heuristic` : Función de buscadores que devuelve el valor de la heurística que evalúa la distancia entre su localización/estado y el objetivo. + `AI:equal?` : report que decide cuándo dos estados son iguales. Muchas veces podrá ser simplemente el comparador `=`, pero en caso de que el contenido de los estados sea una estructura más compleja (por ejemplo, un conjunto representado por una lista) puede ser necesario definir una igualdad más elaborada (por ejemplo, en el caso anterior, que no dependa del orden).

!!!warn: Descargas 1. [Aquí puedes descargar un ZIP con los ficheros necesarios para realizar esta práctica](P5.zip). 2. Las plantillas añaden algunas características al modelo que facilitan la representación visual del Espacio de Estados generado. 2. Recuerda que es conveniente ir haciendo copias/renombramiento de la Plantilla para cada uno de los ejercicios que vayas a resolver. # Problemas **Problema 1**.- Aplica **BFS** a los problemas vistos en la práctica anterior. **Problema 2**.- Busca heurísticas para resolver los problemas vistos en la práctica anterior por medio de $A^*$. **Problema 3**.- **El problema del 8-puzzle**: es un puzle de deslizamiento que consiste en un conjunto de $8$ piezas en un marco de tamaño $3\times 3$ (por lo que queda un hueco libre). El objetivo del puzle consiste en encontrar la sucesión de movimientos (moviendo piezas al hueco libre) que llevan la distribución inicial a una distribución ordenada prefijada. Se pueden pensar variantes de distinto tamaños, por ejemplo, el $15$-puzzle, que usa un tablero de tamaño $4\times 4$. Plantea un coste para las operaciones válidas y analiza las siguientes heurísticas cuando se hace uso de $A^*$: * $H_1$: número total de fichas descolocadas. * $H_2$: Suma de distancias de Manhattan (entre la posición real de cada pieza y su posición final). * $H_3= H_1+2\cdot H_2$. **Problema 4**.- **$A^*$ para Mallas Cuadradas y Grafos Geométricos**: Comprueba la acción de distintas distancias (heurísticas) para encontrar caminos mínimos en mallas cuadradas y en grafos geométricos (un grafo geométrico $G(n,r)$ consta de $n$ puntos al azar en $\mathbb{R}^2$, y donde se conectan los puntos que tengan una distancia menor a $r$). **Problema 5**.- El algoritmo $A^*$ no especifica qué ocurre cuando hay varios nodos en la frontera que tienen el mismo valor de $f$. Compara las siguientes técnicas de desempate e intenta conjeturar primero cuál crees que funcionará mejor sobre algunos ejemplos. Pruébalo sobre ejemplos en los que haya varios caminos óptimos hasta el objetivo (por ejemplo, en mallas cuadradas con la distancia euclídea o de Manhattan como heurísticas, porque se producen muchos empates): * aleatoriamente con distribución uniforme, * el nodo que lleva en la frontera más tiempo, * el nodo que lleva en la frontera menos tiempo, * el nodo con menor valor de $h$, * el nodo con menor coste. (Las dos últimas necesitan alguna otra técnica de desempate si $h$/coste son iguales). **Problema 6**.- El grafo de la figura siguiente muestra el espacio de estados de un hipotético problema de búsqueda. Los estados se indican con letras, y el coste de cada acción se indica en la arista correspondiente. Obsérvese que las acciones no son reversibles, ya que el grafo es dirigido. La tabla que aparece junto al espacio de estados muestra el valor de una función heurística admisible, considerando $G$ como objetivo (comprueba que esta heurística nunca sobreestima el mínimo coste del camino desde cualquier estado hasta $G$).  Considerando $S$ como estado inicial, resuelve el problema de búsqueda anterior utilizando: * BFS. * DFS. * $A^*$ con la heurística anterior. Al dar el árbol de búsqueda debe indicarse: - el orden de expansión de cada nodo (por ejemplo, numerando los nodos expandidos según el orden de su expansión), - la acción correspondiente a cada arista del árbol, - el estado, - el coste del camino, y - el valor de la heurística de cada nodo. **Problema 7**. ![](../img/astar2.jpg align="right" width=300px)Para cada una de las siguientes estrategias de búsqueda para el Espacio de Estados representado por el grafo adjunto, calcula el orden en el que se expanden los estados y el camino devuelto por la búsqueda. En todos los casos, los empates se resuelven de manera que los estados con un orden alfabético anterior se expanden primero. El estado inicial y el estado objetivo son $S$ y $G$, respectivamente. * BFS. * DFS. * Búsqueda $A^*$ con la heurística $h$. **Problema 8**. En el espacio de estados que se muestra con el grafo siguiente:  Considerando que $A$ es el estado inicial y $G$ es el objetivo. Los costes de cada arista (que pueden ser atravesadas en ambas direcciones) se muestran en el grafo. * Demuestra que la heurística $h_1$ es consistente pero la heurística $h_2$ no lo es. * Para cada uno de los algoritmos de la siguiente tabla, marca cuál (si lo hay) de los caminos señalados podría devolver. Ten en cuenta que para algunas estrategias de búsqueda el camino específico devuelto podría depender del comportamiento de desempate. En tales casos, asegúrate de marcar todos los caminos que podrían ser devueltos bajo algún esquema de desempate. |Algoritmo | A-B-D-G | A-C-D-G | A-B-C-D-F-G| |:--------:|---------|---------|------------| |BFS | | | | |DFS | | | | |$A^*(h_1)$| | | | |$A^*(h_2)$| | | | * Supongamos que estamos completando la nueva función heurística $h_3$ que se muestra a continuación, donde todos los valores son fijos excepto $h_3(B)$. |Nodo | A | B | C | D | E | F | G | |:---:|---|---|---|---|---|---|---| |$h_3$|$10$| ? |$9$|$7$|$1.5$|$4.5$|$0$| Para cada una de las siguientes condiciones, escribe el conjunto de valores posibles para $h_3(B)$: 1. ¿Qué valores de $h_3(B)$ hacen que $h_3$ sea admisible? 2. ¿Qué valores de $h_3(B)$ hacen que $h_3$ sea consistente? 3. ¿Qué valores de $h_3(B)$ harán que la búsqueda $A^*$ del grafo expanda el nodo $A$, luego el nodo $C$, luego el nodo $B$, y luego el nodo $D$ en ese orden? **Problema 9**. $A^*$ es un algoritmo que se usa profusamente en los sistemas de navegación (por ejemplo, para ayudar a la conducción de vehículos), pero habitualmente la búsqueda se orienta por medio de una heurística de mínima distancia, cuando no siempre es lo deseable. Por ejemplo: promocionar rutas turísticas/paisajísticas, facilitar trayectos en los que se producen giros más sencillos, compensar los tiempos de tráfico denso en determinadas zonas, sistemas de transporte multimodal, etc. Idea y diseña (haciendo uso de las posibilidades que tiene NetLogo desde el punto de vista gráfico y de agentes) situaciones en las que tenga sentido el uso de heurísticas distintas (o de combinación de heurísticas) en sistemas de recomendación de rutas o en sistemas de navegación automática.