**IAIC**
Soluciones 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 _puzzle 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úsquedas $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 plantilla 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.
!!!Alg:
**Solución**
Debido a que no hay una gran diferencia en la representación del problema para generar un espacio de estados y aplicar BFS sobre el espacio generado, solo vamos a mostrar un ejemplo de uso sobre uno de los problemas vistos en la práctica anterior: **el problema de las 2 jarras**.
La solución concreta la puedes encontrar en la práctica anterior, pero recordemos que dábamos una definición explícita de las transiciones aplicables:
~~~~~~~~~~~~~~
to-report Tr
report (list
(list "Empty(1)" ([ s -> (list 0 (last s)) ]))
(list "Empty(2)" ([ s -> (list (first s) 0) ]))
(list "Pour 1 to 2" ([ s -> pour1-2 (first s) (last s) ]))
(list "Pour 2 to 1" ([ s -> pour2-1 (first s) (last s) ]))
(list "Fill(1)" ([ s -> (list 3 (last s)) ]))
(list "Fill(2)" ([ s -> (list (first s) 4) ]))
)
end
to-report pour1-2 [x1 x2]
...
end
to-report pour2-1 [x1 x2]
...
end
to-report valid? [x]
let J1 first x
let J2 last x
report ((J1 <= 3) and (J2 <= 4) and (J1 >= 0) and (J2 >= 0))
end
to-report AI:children-states
report filter [ s -> valid? (first s) ] (map [ t -> (list (run-result (last t) content) t) ] Tr)
end
~~~~~~~~~~~~~~
Solo tenemos que añadirle los report asociados a reconocer si un estado es final, y el de igualdad. En este caso, ambos son absolutamente estándar y reutilizables para muchísimos casos:
~~~~~~~~~~~~~~
to-report AI:final-state? [params]
report ( content = params)
end
to-report AI:equal? [a b]
report a = b
end
~~~~~~~~~~~~~~
Podemos usar este caso para poner un ejemplo de cómo definir sencillamente un evaluador de estados finales que no sea llegar exactamente a un estado concreto. Por ejemplo, si se pidiera como solución al problema llegar a tener $2$ litros de agua en cualquiera de las jarras, podríamos definir:
~~~~~~~~~~~~~~
to-report AI:final-state? [params]
report member? 2 content
end
~~~~~~~~~~~~~~
Adicionalmente, puede ser interesante ver cómo podemos usar la función `BFS` proporcionada por la librería y recuperar el camino encontrado desde el estado inicial hasta un objetivo (se supone que tanto `Initial_State` como `Final_State` son los contenidos inicial y final, respectivamente, de las jarras, por ejemplo `[0 0]` y `[0 2]`):
~~~~~~~~~~~~~~
to test
ca
let p BFS Initial_State Final_State True True
if p != false [
ask p [
print "The solution is: "
foreach (map [ t -> [first rule] of t ] extract-transitions-from-path) print
]
]
end
~~~~~~~~~~~~~~
**Solución**
Una de las formas más directas de representar un estado en este problema es usar una matriz que sea una ordenación al azar de:
$$
\left[{\begin{array}{ccc}
0 & 1 & 2\\
3 & 4 & 5\\
6 & 7 & 8
\end{array} }\right]
$$
Como, por ejemplo:
$$
\left[{\begin{array}{ccc}
8 & 1 & 4\\
7 & 5 & 3\\
6 & 0 & 2
\end{array} }\right]
$$
donde $0$ representa el hueco.
Nosotros usaremos una representación en forma de lista, por lo que los estados anteriores serían en nuestro espacio:
$$[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8]$$
$$[8\ 1\ 4\ 7\ 5\ 3\ 6\ 0\ 2]$$
En el caso de querer resolver el problema con $A^*$ las reglas tendrán la forma `[ rep cost f ]`, donde:
* `rep` es una representación de la transición/acción/movimiento.
* `cost` es el coste de aplicar esa transición a un estado.
* `f` contiene la información necesaria para aplicar la transición de forma efectiva.
Para una posición dada de la lista que representa el estado, `h`, `(movements h)` devuelve la lista de posibles movimientos/intercambios con la ficha/hueco de la posición `h` (por ejemplo, la posición $0$ puede intercambiarse con $1$ y $3$).
~~~~~~~~~~
to-report movements [h]
let movs [[1 3] [0 2 4] [1 5] [0 4 6] [1 3 5 7] [2 4 8] [3 7] [6 4 8] [5 7]]
report item h movs
end
~~~~~~~~~~
Para un estado dado, `s`, `(swap i j s)` devuelve un nuevo estado en el que las fichas de las posiciones `i` y `j` han sido intercambiadas:
~~~~~~~~~~
to-report swap [i j s]
let old-i item i s
let old-j item j s
let s1 replace-item i s old-j
let s2 replace-item j s1 old-i
report s2
end
~~~~~~~~~~
El procedimiento `AI:children-states` devuelve los sucesores del estado actual: una lista de pares `[ns tran]`, donde `ns` es el contenido del nuevo estado, y `tran` es la transición aplicable para obtenerlo (en este caso, todas ellas con igual coste, $1$). Este report busca el hueco (posición del $0$), calcula los movimientos posibles desde esa posición (con `movements`), y los aplica (con `swap`):
~~~~~~~~~~
to-report AI:children-states
let i (position 0 content)
let indexes (movements i)
report (map [ j -> (list (swap i j content) (list (word "T-" j) 1 "regla")) ] indexes)
end
~~~~~~~~~~
El estado final es un estado concreto, por lo que podemos usar la misma función de detección de los algoritmos anteriores, y lo mismo con el report que decide la igualdad de estados:
~~~~~~~~~~
to-report AI:final-state? [params]
report ( content = params)
end
to-report AI:equal? [a b]
report a = b
end
~~~~~~~~~~
Y ahora necesitamos definir la heurística que usarán los buscadores durante la selección del siguiente estado. Observa que la heurística depende del estado objetivo (que esperan como dato de entrada con `#Goal`).
La Heurística $H_1$ podría ser:
~~~~~~~~~~
to-report H1 [#Goal]
report length filter [ x -> x = False] (map = c #Goal)
end
~~~~~~~~~~
Las Heurísticas $H_2$ y $H_3$ podrían ser:
~~~~~~~~~~
to-report H2 [#Goal]
let pos [[0 0] [0 1] [0 2] [1 0] [1 1] [1 2] [2 0] [2 1] [2 2]]
let c [content] of current-state
report sum (map [ j -> mdist (item (position j c) pos) (item (position j #Goal) pos) ] (range 9))
end
to-report H3 [#Goal]
report (H1 #Goal) + 2 * (H2 #Goal)
end
~~~~~~~~~~
Finalmente, usamos la heurística que queramos:
~~~~~~~~~~
to-report AI:heuristic [#Goal]
report H1 #Goal
end
~~~~~~~~~~
Recordemos que la **Distancia de Manhattan** se puede calcular definiendo adecuadamente el procedimiento:
~~~~~~~~~~
to-report mdist [x y]
report sum map abs (map - x y)
end
~~~~~~~~~~
En el fichero `"8 puzzle A-star.nlogo"` del ZIP anterior puedes encontrar un uso de esta solución con una implementación visual del juego. Es un ejemplo de cómo se pueden usar las soluciones proporcionadas por un buscador para crear soluciones visuales.
**Solución**
Utiliza `"A-star_patches_tie.nlogo"` y `"A-star Turtles Geometric Network LT.nlogo"` para experimentar con las ideas que se proponen en el ejercicio.
**Enunciado**
Define los elementos necesarios para resolver el problema de ordenación de listas numéricas aplicando el algoritmo $A^*$ utilizando como transiciones válidas las transposiciones (la *transposición* $i$ en una lista $L$ intercambia los elementos que ocupan las posiciones $i$ e $i+1$ de $L$). Puedes suponer que todas las transposiciones tiene un coste uniforme de valor $1$.