Construir un buscador desde cero

Hemos visto que para representar un problema como una búsqueda en un Espacio de Estados necesitamos los siguientes elementos:

• Espacio de Estados: $X$
• Estado inicial: $s_0\in X$
• Estados finales: $G\subseteq X$
• Función de transición (acciones): $T:X\to \mathcal{P}(X)$

Las transiciones aportan una estructura interna al espacio completo de estados, $X$, que lo convierte en un espacio conectado, donde tiene sentido plantearse si hay caminos que conecten $s_0$ con $G$ y, en caso afirmativo, intentar construir el camino más deseable (el más óptimo, desde algún punto de vista). Aunque a veces $T$ viene dado con el problema, muchas veces determinar el par $(X,T)$ es parte de la representación del problema.

En cierta forma, el par $(X,T)$ se comportaría como un espacio topológico, en donde las conexiones entre estados por medio de transiciones están definiendo una relación de conectividad que configura el espacio de una cierta forma... si cambiamos las transiciones disponibles, la forma del espacio cambia. En los problemas que hacen uso de este tipo de representación la elección adecuada de $X$ y de $T$ puede modificar sensiblemente la resolubilidad del problema original.

El tipo de problemas que se puede resolver con esta representación es variado, dependiendo de los requerimientos adicionales (no excluyentes entre sí) que consideremos para dar una solución:

• Si solo indicamos si existe un camino, pero no especificamos cúal, estamos resolviendo un problema de decisión.
• Si $G$ viene dado por un conjunto de propiedades que deben verificarse en los estados alcanzados, entonces el problema se podría ver como un problema de satisfacción de restricciones.
• Si, además, proporcionamos un estado de $G$ al que podemos llegar desde $s_0$, estamos resolviendo un problema de construcción.
• Si, por encima de las dos anteriores, además estamos dando el conjunto de transiciones/acciones que me llevarían desde $s_0$ a un elemento de $G$, estamos resolviendo un problema de planificación.
• Si en cualquiera de los problemas anteriores preferimos dar uno de los caminos que verifique propiedades adicionales, entonces al problema de búsqueda le añadimos un problema de optimización.

Lo más habitual es no disponer de $X$ de forma explícita y completa al principio de la búsqueda, sino que hemos de ir construyéndolo/descubriéndolo a partir de $s_0$ por aplicación sucesiva de elementos de $T$. Grosso modo, cuando $T$ se puede expresar como un conjunto finito de aplicaciones, $T=\{t_1,\dots,t_n\}$, esta construcción la podemos ver como un proceso iterativo en el que, partiendo de $s_0$, construimos por niveles los estados que podemos alcanzar por aplicación de los elementos de $T$:

En general, para cualesquiera $\{i_1\dots i_k i_{k+1}\}\subseteq \{1,\dots,n\}$ podríamos considerar:

$f\circ g$ representa la composición de aplicaciones: $f\circ g(x)=f(g(x))$.

Si el espacio $(X,T)$ es fuertemente conexo (es decir, desde cualquier estado puedo conseguir cualquier otro por aplicación sucesiva de elementos de $T$), entonces el problema de búsqueda tendrá solución, independientemente de $s_0$ y $G$, es decir, que sabemos que hay al menos una sucesión de transiciones que lleva desde $s_0$ hasta una solución. Muchas veces la situación no es esa, y entonces dependerá de $T$ para que al menos podamos alcanzar algún elemento de $G$ desde un $s_0$ prefijado.

Además, en caso de que sí sea alcanzable, puede haber más de un camino que lleve a un estado final, pudiendo variar de un camino a otro en el orden de aplicación de las transiciones que se han aplicado, en la longitud de la cadena de transiciones aplicadas, o en las propiedades que verifiquen las transiciones elegidas (por ejemplo, si son conmutativas, $t_i\circ t_j=t_j\circ t_i$, asociativas, $t_i\circ (t_j\circ t_k)=(t_i\circ t_j)\circ t_k$, etc.), entre otras muchas. Conocer a priori las propiedades que verifica $T$ puede simplificar la generación de los estados de $X$, ya que puede evitar la creación de estados repetidos innecesariamente.

Partiendo de esta visión iterada de cómo construir elementos de $X$, podemos dar las funciones necesarias para hacerlo de forma compacta en un lenguaje como NetLogo (aunque lo que hagamos aquí se puede aplicar de forma directa en muchísimos otros lenguajes de programación).

Generando $X$ a partir de $s_0$

Vamos a suponer que tenemos $T$ en forma de colección (lista, en el caso de NetLogo, pero donde el orden de aparición no jugará ningún papel) de funciones anónimas:

donde cada $t_i:X\to X$.

Vamos a hacer uso de la función map, que recordemos que hace lo siguiente:

map f [a1 ... an] = [f(a1) ... f(an)]

es decir, aplica una función determinada a todos los elementos de una lista.

Como nosotros queremos aplicar una lista de funciones a un elemento fijo, podemos aprovechar esta estructura para hacerlo eligiendo adecuadamente qué función f aplicar. Si Tr es la lista que contiene las transiciones, entonces, para conseguir todos los estados alcanzables desde s basta hacer:

map [t -> (run-result t s)] Tr

Para empaquetar este proceso como una función podemos definir:

to-report children-state [s]
  report (map [t -> (run-result t s)] Tr)
end

Si disponemos de un predicado, final?, que indica cuándo un estado es final o no, podemos reproducir la construcción a partir de s0 como:

to-report Generate-X-from [s0]
  let Fr (list s0)
  let X Fr
  while [empty? filter final? Fr]
  [
    set Fr reduce sentence (map children-state Fr)
    set X sentence X Fr
  ]
  report X
end

Vemos que la generación de $X$ (hasta que encontremos elementos de $G$) es realmente directa gracias a las capacidades funcionales del lenguaje:

1. Partiendo de la frontera inicial: $Fr=\{s_0\}$.
2. Construimos los sucesores de $Fr$ por la aplicación de todas las transiciones disponibles a todos los elementos de la frontera.
3. Acumulamos $Fr$ en $X$ (para no perder los estados obtenidos).
4. Si en $Fr$ no hay elementos de $G$, repetir desde el paso 2. En caso contrario, devolver $X$.

Trabajar con la frontera ayuda a no estar calculando continuamente los sucesores de estados por los que ya hemos pasado en etapas anteriores (esto no asegura no tener repetidos, pero al menos no repite el mismo proceso una y otra vez sobre todos los elementos). Observa que no solo se ha usado map, sino que también se ha hecho uso de reduce: la aplicación de map sobre cada estado devuelve una lista de estados, por lo que la aplicación sobre la frontera resulta en una lista de listas, aplicar una reducción con sentence permite unir todas las listas en una sola.

Aunque así se ha simplificado mucho el proceso, se deja fuera una parte que es esencial en este proceso, pero que se puede introducir sencillamente gracias a la programación funcional: aunque se tenga una representación uniforme de los estados de $X$, es probable que haya elementos representables que no se correspondan con estados válidos (por ejemplo, una representación de estados como números, pero donde solo tengan sentido los números positivos). Para tener en cuenta estas limitaciones, es posible tomar dos estrategias:

• Restringir $T$: Las transiciones de $T$ solo generan estados válidos.
• Validar $T$: Tras generar posibles estados por elementos de $T$, se desechan aquellos que no son válidos.

La implementación de la segunda estrategia es directa (apenas un pequeño cambio) y facilita la construcción de $T$ desde el punto de vista de la programación. Supondremos que existe un predicado, valid?, que indica si un estado es válido o no (o, mejor dicho, si una representación realmente es un estado). Con este predicado, y la función de orden superior, filter, basta cambiar la función que calcula los sucesores de la siguiente forma:

to-report children-state [s]
  report filter valid? (map [t -> (run-result t s)] Tr)
end

No es necesario cambiar nada de los demás procedimientos, porque la generación de sucesores se ha restringido para devolver solo estados válidos.

Sin embargo, todavía se puede mejorar el proceso de generación eliminando los estados repetidos:

to-report Generate-X-from [s0]
  let Fr (list s0)
  let X Fr
  while [empty? filter final? Fr]
  [
    set Fr reduce sentence (map children-state Fr)
	set Fr remove-duplicates filter [s -> not member? s X] Fr
    set X sentence X Fr
  ]
  report X
end

La búsqueda como una generación selectiva

Desde un punto de vista computacional, la generación anterior tiene muchas deficiencias. Aunque va generando todos los estados de $X$ que se pueden obtener a partir de $s_0$, no es un mecanismo que se pueda ofrecer como solución a problemas de búsqueda porque tiene muchas opciones de explotar exponencialmente (tanto en memoria, es decir, número de estados que van apareciendo, como en tiempo, por el número de aplicaciones de $T$ que se aplican en cada paso) en cuanto la media de transiciones aplicables desde cada estado sea mayor que $1$. Además, muchísimos de los estados generados en el proceso no tendrán ningún valor para la solución de la búsqueda.

Por ello, los algoritmos de búsqueda implementan estrategias que permitan recorrer/generar $X$ haciendo la expansión de un solo estado en cada paso, con el fin de controlar la complejidad del proceso de generación e intentar introducir algo de inteligencia en el proceso de selección.

La forma general de un proceso de búsqueda que usa selección de estados para expandir $X$ se puede obtener muy fácilmente a partir del algoritmo anterior:

to Selected-Search-from [initial-state]
  let Fr (list s0)
  let X Fr
  while [empty? filter final? Fr]
  [
    let sel-s select Fr
    set Fr sentence (children-state sel-s) (remove sel-s Fr)
    set X sentence X Fr
  ]
  report X
end

donde select sería la estrategia: una función que selecciona, de entre los estados de la frontera que podemos expandir, el estado que vamos a expandir en este paso.

Si, por ejemplo, se toma:

to-report select [C]
  report one-of C
end

el resultado será una búsqueda aleatoria.

Si Tr es una lista ordenada, su orden induce un orden de aparición de los estados durante la generación de $X$. Si no se dispone de información acerca de cómo construir una estrategia que acelere el proceso de búsqueda (lo que se denomina una búsqueda ciega) se podría usar el orden impuesto por Tr para recorrer $X$ de manera ordenada.

Por ejemplo, para seguir ordenadamente cada nivel de la estructura de $X$ que se genera desde $s_0$, bastaría con ir seleccionando de la frontera el primer estado disponible y añadir los estados que se generan desde él a la cola de la frontera (en programación, es lo mismo que usar una estructura de tipo FIFO), y entonces se puede escribir la búsqueda como sigue, que se conoce como búsqueda en anchura (BFS, por sus siglas en inglés):

to BFS-from [initial-state]
  let Fr (list s0)
  let X Fr
  while [empty? filter final? Fr]
  [
    let sel-s first Fr
    set Fr sentence (bf Fr) (children-state sel-s) 
    set X sentence X Fr
  ]
  report X
end

Si se quiere que la búsqueda sea en profundidad (en una estructura de tipo FILO) se puede seguir seleccionando el primer estado de la frontera, pero ahora se añaden los estados que se generan desde él a la cabeza de la frontera, lo que se conoce como búsqueda en profundidad (DFS, por sus siglas en inglés):

to DFS-from [initial-state]
  let Fr (list s0)
  let X Fr
  while [empty? filter final? Fr]
  [
    let sel-s first Fr
    set Fr sentence (children-state sel-s) (bf Fr)
    set X sentence X Fr
  ]
  report X
end

Si la estrategia de selección es muy eficiente, la búsqueda será más rápida porque no generará una sección muy grande de $X$ para poder resolver el problema.

Normalmente, la dificultad al resolver un problema de búsqueda no se encuentra en verificar las condiciones de $G$ ni en la aplicación de los elementos de $T$, sino en la cantidad de estados adicionales que hay que generar para poder encontrar una solución, así que es normal que muchos de los esfuerzos en la resolución de problemas de búsqueda vayan orientados a reconocer propiedades adicionales de la estructura de $X$ que sirvan para definir estrategias más eficientes. Los algoritmos de búsqueda que usan este tipo de estrategias se dice que realizan una búsqueda informada, y uno de sus representantes más claros es el algoritmo $A^*$, en el que la estrategia de búsqueda intenta minimizar el coste del camino recorrido:

Cuando la aplicación de cada transición lleva aparejado un coste (o lo que es lo mismo, la estructura $(X,T)$ se puede representar como un grafo ponderado, en el que la transición que lleva $s$ a $s'$ se representa como una arista dirigida $(s\to s')$ con un peso predeterminado y conocido), el algoritmo $A^*$ calcula el camino de menor peso entre $s_0$ y un elemento de $G$ considerando que la estrategia en cada paso selecciona el nodo de la frontera que minimiza:

$$ f(s)=c(s)+h^*(s) $$

donde $c(s)$ es el coste real del camino que se ha construido desde $s_0$ hasta $s$, y $h^*(s)$ es una estimación del coste mínimo que habría desde $s$ hasta $G$ ($h^*$ se conoce como función heurística, y suele ser desconocida, por lo que se usan aproximaciones que podemos calcular... pero para asegurar que esta estrategia realmente devuelve el camino de coste mínimo usando estas aproximaciones, éstas deben verificar algunas propiedades adicionales).

to-report select-A* [C]
  let s* min-one-of C [s -> (c s) + (h s)]
  report s*
end

Extracción de caminos: Generación de $(X,T)$

Las secciones anteriores consiguen generar estados de $X$, pero no mantienen información acerca de qué transiciones han permitido llegar desde un estado a otro. Esto significa que se ha generado $X$, el espacio de estados (al menos, los estados alcanzables desde $s_0$), pero no $(X,T)$, la estructura interna que las transiciones proporcionan al espacio de estados. En este sentido, los métodos anteriores pueden resolver problemas de decisión, e incluso problemas de construcción de soluciones, pero no problemas de planificación.

Para generar $(X,T)$ se debe almacenar información acerca de qué transiciones son las que permiten llegar desde un estado a otro. La estructura natural que permite almacenar esta información sería la de un grafo dirigido, y así está definido en la librería de IA oficial del curso, (haciendo uso de sistemas multiagente), pero aquí, por motivos educativos solo se mostrarán implementaciones directas.

Para ello, se usará una estructura más rica para los estados manteniendo la información de:

s = (valor, valor-padre, transicion)

donde:

• valor es el valor que se almacena en el estado (lo que antes almacenábamos como estado completo), y que representa una posible solución al problema.
• valor-padre es el valor del estado que ha generado a s.
• transicion es la transición que ha llevado desde valor-padre hasta valor.

Aunque aquí se usarán simples listas para almacenar esta información, realmente se puede usar cualquiera de las estructuras de datos habituales en los lenguajes de programación (tablas/diccionarios, structs, arrays,...). NetLogo propociona una estructura muy distinta a los demás para mantener este tipo de información, combinando agentes normales (turtles, que pueden mantener los elementos de $X$) junto con agentes relacionales (links, que pueden mantener los elementos de $T$).

Para que sea independiente de la estructura usada, es más fácil considerar los siguientes constructores y accesos a la información de los estados:

• (new-state v f t) genera un estado con valor v, padre f, y transición t.
• (value-of s) devuelve el valor del estado s.
• (father-of s) devuelve el padre del estado s.
• (transition-of s) devuelve la transición que ha generado el estado s.

A partir de estos elementos se modifica adecuadamente el generador de descendientes de un estado como:

to-report children-state [s]
  let v value-of s
  report filter valid? (map [t -> (new-state (run-result t v) v t) ] Tr)
end

De donde es fácil construir la modificación del generador para almacenar (y considerar) los nuevos tipos de estados:

to-report Generate-XT-from [s0]
  let Fr (list (new-state initial-state initial-state "-"))
  let XT []  
  while [empty? filter final? Fr]
  [
    set XT sentence XT Fr
    set Fr reduce sentence (map children-state Fr)
    set Fr filter [s -> not member? (value-of s) (map value-of XT)] Fr
  ]
  set XT sentence XT (filter final? Fr)
  report XT
end

El resto de variantes vistas anteriormente se adaptan de forma similar.

Por último, el hecho de haber generado el espacio de estados estructurado, $(X,T)$, permite responder al problema de planificación (y, con el algoritmo adecuado, de optimización) devolviendo un camino que conecta el estado inicial con un estado final. Gracias a la información acumulada en los estados, se puede construir el camino de forma regresiva, yendo desde el objetivo/solución alcanzado hasta el estado inicial por medio de las transiciones aplicadas (que se han almacenado para eso):

to-report path-from [start goal XT]
  if start = goal [report (list new-state start start "-")]
  let s-g state-with-value goal XT
  let f-g father-of s-g
  report lput s-g (path-from start f-g XT)
end

donde start y goal son los valores de los estados inicial y final, respectivamente, y (state-with-value v XT) es una función que devuelve el estado (la estructura) de XT que tiene valor v.

Para usarlo como respuesta de una búsqueda, basta añadir las líneas que deuelven el camino encontrado:

let g value-of one-of (filter final? XT)
report path-from s0 g XT