Biblioteca astar

De Wikihaskell
Saltar a: navegación, buscar
Biblioteca astar
Biblioteca para el algoritmo de búsqueda A*
Lenguaje Haskell
Biblioteca astar
Autores Elisa Leiva
Diego Barrios
Raúl Núñez

La biblioteca astar implementa en Haskell el famoso algoritmo de búsqueda heurística A*. Fue desarrollada por Cale Gibbard en 2008 y construida utilizando la Biblioteca de empaquetamiento Cabal. Esta biblioteca funciona sobre GHC o GHCi, por lo tanto, para probar los ejemplos que se exponen a continuación se deberá usar este compilador de Haskell.

Contenido

Introducción al algoritmo A*

El algoritmo A* es un algoritmo de búsqueda en grafos y fue presentado en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael. El algoritmo encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y un nodo objetivo.

El problema de algunos algoritmos de búsqueda en grafos informados, como puede ser el algoritmo voraz, es que se guían en exclusiva por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante intuitivo el hecho de que un buen algoritmo de búsqueda informada debería tener en cuenta ambos factores, el valor heurístico de los nodos y el coste real del recorrido.

Así, el algoritmo A* utiliza la siguiente función de evaluación:


f(n) = g(n) + h'(n)


donde h'(n) representa el valor heurístico del nodo a evaluar hasta el final y g(n) el coste real del camino recorrido para llegar al nodo evaluado.

El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que h'(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.

La biblioteca astar nos proporciona una implementación de este algoritmo para que pueda ser usado en programación bajo Haskell. Se ha desarrollado utilizando el compilador nativo de código libre Glasgow Haskell Compiler (GHC), por lo que para su funcionamiento es necesario utilizar dicho compilador.

Introducción a la biblioteca astar

Esta biblioteca implementa una función para calcular el camino mínimo en un grafo utilizando el algoritmo A*. Dicha función tiene la siguiente declaración:

aStar :: (Ord a, Ord c, Num c) => (a -> Set a) -> (a -> a -> c) -> (a -> c) -> (a -> Bool) -> a -> Maybe [a]

A continuación, vamos a ver que significado tiene cada parámetro que recibe la función:

  • a -> Set a: Este parámetro es el grafo en el cual estamos bucando el camino mínimo. Viene dado a través de una función que indica como moverse desde un vértice hasta sus vecinos.
  • a -> a -> c: Función distancia entre los vértices del grafo. Esta función no se aplicará a los vértices que no son vecinos.
  • a -> c: Distancia heurística hasta el objetivo.
  • a -> Bool: El objetivo, especificado como un predicado booleano en los vértices.
  • a: El vértice desde el cual se comienza la búsqueda.
  • Maybe [a]: La función devuelve un camino óptimo, si existe algún camino. El resultado excluye el vértice de partida.

Instalación

Instalando GHC

En primer lugar debemos instalar el compilador GHC. Esto podemos hacerlo fácilmente si estamos en Ubuntu GNU/Linux con:

sudo apt-get update && sudo apt-get install ghc6 

o usando aptitude:

sudo aptitude update && sudo aptitude install ghc6

En el caso de Gentoo GNU/Linux podemos instalar ghc fácilmente ejecutando en un terminal:

emerge -av ghc

Si estamos en Windows, podemos instalar el compilador GHC descargándolo desde aquí: [1] y siguiendo el proceso de instalación normal.

Instalando Cabal

Una vez instalado GHC debemos instalar también la herramienta Cabal [2] para instalar nuestra biblioteca astar. Esta herramienta nos permitirá instalar la biblioteca astar con todas sus dependencias. Para instalar cabal podemos seguir los pasos expuestos en Biblioteca de empaquetamiento Cabal.

Instalando la biblioteca Astar

Antes de instalar la biblioteca hay que actualizar la lista de paquetes de cabal:

cabal update

Y entonces se instala esta biblioteca con el comando:

cabal install astar

Esto instala la biblioteca y sus dependencias (base, container y PSQueue).

Cómo cargar la biblioteca

Una vez dentro de GHCi hacemos:

Prelude> :m + Data.Graph.AStar

y ya podemos usarla. Podemos observar que ahora cambia el prompt a:

Prelude Data.Graph.AStar>

Qué debemos definir

Debemos definir los siguientes parámetros de la función astar:

  • Estado inicial.
  • Estado final (objetivo).
  • Conjunto de reglas.
  • Función para calcular el coste de desplazarnos a un nodo desde el actual.
  • Función heurística.

Ejemplos de uso

Un primer ejemplo

En primer lugar siempre tenemos que cargar las siguientes bibliotecas:

ghci> :m + Data.Graph.AStar
ghci> :m + Data.Set

Supongamos que tenemos un tablero de 11 filas y 11 columnas y que nuestro estado inicial será la casilla (10,10) y el estado final la (0,0). EjemploTablero.png

Nuestro conjunto de reglas será:

  • Desplazarnos una casilla hacia la derecha.
  • Desplazarnos una casilla hacia la izquierda.
  • Desplazarnos una casilla hacia arriba.
  • Desplazarnos una casilla hacia abajo.

Para expresar ese conjunto de reglas definimos una función de vecindad:

ghci> let vecinos (x,y) = Data.Set.fromList $ [(x+k,y) | k <-[-1,1]] ++ [(x,y+k) | k <- [-1,1]]

Esta función devuelve el conjunto de las coordenadas de las 4 casillas a las que se puede viajar desde la casilla dada. Ejemplo:

ghci> vecinos (1,1)
fromList [(0,1),(1,0),(1,2),(2,1)]
Vecino1
Vecino2
X
Vecino3
Vecino4

El siguiente paso es creamos una función para calcular el coste de ir desde un nodo a otro. Tomaremos simplemente la distancia euclídea para representar este coste: distancia (a,b) (a',b') = (a-a')^2 + (b-b')^2

ghci> let distancia (x,y) (x',y') = (x-x')^2 + (y-y')^2

Como función heurística usaremos también la distancia euclídea, pero al objetivo (0,0) heuristica (x,y) = x^2 + y^2

ghci> let heuristica (x,y) = x^2 + y^2

Como hemos mencionado, nuestro objetivo será llegar a la casilla (0,0). Por tanto, tendremos una función objetivo para comprobar si hemos llegado a dicha casilla:

ghci> let objetivo (x,y) = (x,y) == (0,0)

Por último, aplicamos el algoritmo desde el punto inicial:

ghci> aStar vecinos distancia heuristica objetivo (10,10)

Y nos devuelve el camino con menor coste para llegar al estado inicial (casilla (0,0)):

Just [(9,10),(9,9),(8,9),(8,8),(7,8),(7,7),(6,7),(6,6),(5,6),(5,5),(4,5),
      (4,4),(3,4),(3,3),(2,3),(2,2),(1,2),(1,1),(0,1),(0,0)]

Podemos ver el camino que se ha seguido en la siguiente figura:

Solucion1.PNG

Cambiando el terreno

Podemos simular dificultades en el terreno modificando la función distancia: distancia (a,b) (a',b') = (a-a')^2 + (b-b')^2 + \frac{(a+a')/2}{(1+(b-b')^2)}

let distancia (x,y) (x',y') = (x-x')^2 + (y-y')^2 + ((x+x')/2)/(1+(y-y')^2)

Y ahora cuando aplicamos el algoritmo desde el punto inicial nos devuelve:

Just [(10.0,9.0),(10.0,8.0),(10.0,7.0),(9.0,7.0),(8.0,7.0),(8.0,6.0),(7.0,6.0),
      (7.0,5.0),(6.0,5.0),(6.0,4.0),(5.0,4.0),(4.0,4.0),(4.0,3.0),(3.0,3.0),
      (3.0,2.0),(2.0,2.0),(2.0,1.0),(1.0,1.0),(0.0,1.0),(0.0,0.0)]

Este camino puede visualizarse como:

CaminoSegundaFuncionDistancia.png

Problema del 8-puzzle 8puzzle.hs

El tradicional juego del 8-puzzle consiste en un tablero con 9 casillas, las cuales van enumeradas del 1 al 8, más una casilla vacía. Dicha casilla es la que, con movimientos horizontales y verticales, debe ser desplazada e intercambiada con alguno de sus vecinos, de manera que dada una configuración inicial se llegue a una configuración final.

Aunque las reglas del juego sean sencillas de realizar conlleva una complejidad mayor en el momento de obtener la solución, es por esta razón se utiliza habitualmente como un ejemplo clásico y muy didáctico para poner en práctica algoritmos de búsqueda que encuentren la solución eficiente a una configuración de 8-puzzle.

8 puzzle.png

La representación elegida para este ejemplo es una lista, de forma que, por ejemplo, nuestro estado final (correspondiente a la figura) será la lista [1,2,3,8,0,4,7,6,5]. Puesto que todos los elementos de una lista tienen que ser del mismo tipo, representaremos la casilla vacía con el número 0.

Como siempre, tendremos que definir los parámetros que le pasaremos a la función aStar. Como hemos mencionado, los movimientos posibles son:

  • Intercambiar la casilla vacía con la ficha de su izquierda.
  • Intercambiar la casilla vacía con la ficha de su derecha.
  • Intercambiar la casilla vacía con la ficha superior.
  • Intercambiar la casilla vacía con la ficha inferior.

Estas reglas las representaremos en un fichero de la siguiente forma:

vecinos:: [Integer] -> [[Integer]]
vecinos l = case posHueco of
  0 -> [intercambia elem1 0 l] ++ [intercambia elem3 0 l]
  1 -> [intercambia elem0 0 l] ++ [intercambia elem2 0 l] ++ [intercambia elem4 0 l]
  2 -> [intercambia elem1 0 l] ++ [intercambia elem5 0 l]
  3 -> [intercambia elem0 0 l] ++ [intercambia elem4 0 l] ++ [intercambia elem6 0 l]
  4 -> [intercambia elem1 0 l] ++ [intercambia elem3 0 l] ++ [intercambia elem5 0 l] ++ [intercambia elem7 0 l]
  5 -> [intercambia elem2 0 l] ++ [intercambia elem4 0 l] ++ [intercambia elem8 0 l]
  6 -> [intercambia elem3 0 l] ++ [intercambia elem7 0 l]
  7 -> [intercambia elem4 0 l] ++ [intercambia elem6 0 l] ++ [intercambia elem8 0 l]
  8 -> [intercambia elem5 0 l] ++ [intercambia elem7 0 l]
  where posHueco = buscar 0 l
        elem0 = l !! 0
        elem1 = l !! 1
        elem2 = l !! 2
        elem3 = l !! 3
        elem4 = l !! 4
        elem5 = l !! 5
        elem6 = l !! 6
        elem7 = l !! 7
        elem8 = l !! 8

Como vemos, esta función hace uso de buscar, que devuelve la posición de un elemento en una lista dada:

 buscar :: Integer -> [Integer] -> Integer
 buscar e (x:xs) = if e /= x then 1 + buscar e xs else 0

y de la función intercambiar, que la usaremos para intercambiar la casilla vacía con su casilla vecina:

 intercambia:: Integer -> Integer -> [Integer] -> [Integer]
 intercambia _ _ [] = []
 intercambia a b (x:xs) = if x == a then [b] ++ intercambia a b xs 
                          else if x == b then [a] ++ intercambia a b xs 
                               else [x] ++ intercambia a b xs

También incluiremos en el fichero la función diferentes, que se usará para la heurística:

 diferentes [] [] = 0
 diferentes (x:xs) (y:ys) = if x /= y && x /= 0 then 1 + diferentes xs ys else diferentes xs ys

Cargamos el fichero (además de Data.Graph.AStar y Data.Set):

 ghci> :load 8puzzle.hs

Puesto que el primer parámetro que recibe aStar debe ser una función que devuelva un conjunto (a -> Set a), debemos hacer:

 ghci> let vecinosPuzzle puzzle = Data.Set.fromList $ vecinos puzzle

En este caso, nuestra función distancia será una función constante que siempre devuelve 1:

 ghci> let distancia puzzle1 puzzle2 = 1

Usaremos como heurística el número de fichas mal colocadas con respecto a nuestro estado objetivo (esto lo hace la función diferentes mencionada anteriormente):

 ghci> let heuristica puzzle = diferentes puzzle [1,2,3,8,0,4,7,6,5]

Por último, definiremos la función objetivo que comprobará si hemos alcanzado nuestro objetivo:

 ghci> let objetivo puzzle = puzzle == [1,2,3,8,0,4,7,6,5]

Ahora ya podemos llamar a la función aStar. Pondremos como estado inicial [2,8,3,1,6,4,7,0,5]:

 ghci> aStar vecinosPuzzle distancia heuristica objetivo [2,8,3,1,6,4,7,0,5]

esto nos devuelve como resultado:

 Just [[2,8,3,1,0,4,7,6,5],[2,0,3,1,8,4,7,6,5],[0,2,3,1,8,4,7,6,5],[1,2,3,0,8,4,7,6,5],[1,2,3,8,0,4,7,6,5]]

Referencias

  • La página desde la que se puede descargar la biblioteca y obtener una breve documentación sobre la misma es HackageDB.
  • Para obtener más información sobre el uso de la biblioteca, contactar con el creador de la misma a través de su correo electrónico: cgibbard@gmail.com
Herramientas personales