Comecocos vs Laberintos con técnicas de búsqueda.

Índice:

1. Introducción al contexto del estudio. 2

2. Breve descripción de la estructura de la memoria. 2

3. Búsqueda en Profundidad. 3

    3.1. Objetivo. 3

    3.2. Solución al problema propuesto. 3

    3.3. Ventajas e inconvenientes detectados. 5

    3.4. Pseudocódigo. 6

    3.5. Pruebas y resultados. 8

4. Búsqueda en Anchura. 9

    4.1. Objetivo. 9

    4.2. Solución al problema propuesto. 9

    4.3. Ventajas e inconvenientes detectados. 10

    4.4. Pseudocódigo. 10

    4.5. Pruebas y resultados. 12

5. Búsqueda usando el Algoritmo A*. 13

    5.1. Objetivo. 13

    5.2. Solución al problema propuesto y heurística elegida. 13

    5.3. Ventajas e inconvenientes detectados. 13

    5.4. Pseudocódigo. 14

    5.5. Pruebas y resultados. 16

6. Comparativa sobre el comportamiento de los agentes desarrollados. 17

7. Conclusión. 

1.    Introducción al contexto de la práctica.

La siguiente memoria pretende aclarar y exponer el trabajo llevado a cabo para la realización de un estudio relacionado en el contexto de la Inteligencia Artificial, este estudio se llevará a cabo mediante el uso del famoso juego "Comecocos", de ahí su nombre  "Comecocos vs Laberintos con técnicas de búsqueda". Para ello, se intentará explicar con la mayor claridad y brevedad posible el trabajo llevado a cabo en el periodo de realización del mismo.

En este contexto, se describirán los métodos de búsqueda utilizados, tanto informados como no informados, siendo esta última una  metodología que realiza un recorrido en el espacio de búsqueda de una forma sistemática, pero sin tener en cuenta ningún tipo de información sobre el dominio del problema que se está resolviendo.

2. Breve descripción de la estructura de la memoria.

A continuación se detalla la estructura que seguirá la presente memoria, para facilitar en la medida de lo posible su comprensión.

Basándonos en que el objetivo de este estudio consiste en la resolución de tres problemas usando en cada uno un tipo de algoritmo en concreto, la explicación de cada uno de estos se dividirá en tres bloques. Y a su vez, en cada uno de estos, se detallan las siguientes secciones:

·    Objetivo: Se comenta brevemente los que se quiere conseguir, y cuál es el algoritmo a desarrollar.

·    Solución al problema propuesto: Es decir, cómo ha sido resuelto el problema desde un punto de vista conceptual y sin entrar en detalles de implementación.

·     Ventajas e inconvenientes detectados: Antes y después del proceso de implementación.

·     Pseudocódigo: Detalles sobre la implementación del algoritmo.

·     Pruebas y resultados: Testeo del funcionamiento del algoritmo con el mayor detalle posible.

Además,  en la descripción de los algoritmos se pretenderá utilizar una notación y un nivel de detalle que  faciliten la comprensión de los mismos.

3.    Búsqueda en Profundidad.

3.1. Objetivos

El objetivo en este punto es diseñar un agente "Pacman" basado en un algoritmo de búsqueda en profundidad no informado. El cual, deberá comerse todos los puntos del tablero de la forma más ordenada posible para ir completando los diferentes niveles que se ofrecen.


3.2. Solución al problema propuesto.

Al intentar resolver este tipo de problemas, es necesario establecer una serie de pautas que ayudarán a determinar un orden en su resolución. Para ello, se establecerán una serie de simplificaciones, desde un punto de vista conceptual, que serán útiles para dejar las ideas un poco más claras, dejando así, de forma transitoria de lado la parte de implementación del algoritmo, para centrarnos exclusivamente en la idea de resolución del problema.

En primer lugar, consideraremos en principio que el espacio de búsqueda es un grafo, lo que simplifica bastante las operaciones, ya que de este modo será posible generar un algoritmo que no recaiga en bucles infinitos, permitiendo así la posibilidad de ir almacenando los nodos visitados y cerrados para no repetir caminos, cosa que no se puede realizar usando búsqueda en árboles.

Para simular este grafo, se decide usar una función recursiva, de tal manera que se establece como nodo raíz la posición en la que se encuentra el pacman a la hora de realizar una nueva búsqueda, y tras comprobar si este es objetivo se expande generando los hijos a los que puede acceder. En el siguiente ejemplo se detalla gráficamente, siendo el nodo (1,0) el nodo raíz, y los nodos (1,1) y (1,2) los hijos de este. (Ver Figuras 1 y 2).

En este punto, es correcto mencionar que se realizará una nueva búsqueda cada vez que el pacman pretende comerse un nuevo punto. Así conseguimos reducir considerablemente el coste computacional necesario para realizar una búsqueda de estas características, ya que se alcanzarán profundidades más manejables.

      

(Figura 1 y 2)

Con todo lo anterior, es fácil comprender que dentro de la función recursiva, primero se comprobará si el estado actual es objetivo, y posteriormente se comprueba si existe alguna rama hija que permita alcanzar el objetivo establecido.

Para realizar la comprobación anterior, se selecciona el primer hijo que se encuentra y se llama a la función recursiva pasándole este como argumento. En cada llamada a esta función, se realiza un cambio de contexto en el estado del algoritmo, es decir, el nodo que antes era hijo,  pasa a ser un nodo raíz, para posteriormente poder expandir sus hijos y seguir con la búsqueda.

Con esta transformación se consigue ir recorriendo paso a paso todos los nodos del grafo basándonos en los “estados virtuales[1]”, para así estudiar el camino a seguir de la forma más sencilla posible. Una vez encontrado el objetivo, se transforman los estados por los que se ha ido pasando, en los movimientos que tiene que realizar pacman para llegar.

Si por esta rama no se encuentra el objetivo, se retornará false, y se realizará la misma comprobación con todos los hijos. Así, se tiene conciencia de que estamos usando un algoritmo en profundidad.

Para que la realización del algoritmo sea posible, es necesario utilizar una serie de estructuras de datos. En concreto, se utiliza una lista para almacenar los nodos visitados, y una pila donde se almacenará los movimientos que tiene que realizar pacman hasta llegar al objetivo.

Además, y como extra al algoritmo, cada vez que se retorna un camino válido hasta el objetivo, se comprueba que tenga el menor número de pasos posibles. Con esto se tiene la certeza de que el camino encontrado en cada búsqueda será óptimo.


3.3. Ventajas e Inconvenientes detectados.

Como ya se ha comentado anteriormente, una de las ventajas de usar un algoritmo de búsqueda en profundidad basado en grafos, es que se pueden almacenar los nodos visitados para no recaer en bucles infinitos.

Al principio del desarrollo de la práctica, en vez de usar este tipo de estructuras de datos, pensé en resolver el problema mediante árboles, pero tras analizar el problema en profundidad y realizar algunas pruebas de implementación, pude observar que el pacman realizaba muchos movimientos absurdos y en ocasiones incluso no pasaba del primer nivel.

Se observa además que el algoritmo consume mucho coste computacional, sobre todo en niveles elevados, ya que como los puntos están más separados, es necesario expandir más nodos y la profundidad de la búsqueda se hace realmente compleja.


3.4. Pseudocódigo.

A groso modo el algoritmo implementado se divide en tres funciones: chooseMove, CapturaMovimiento y BusquedaProfundidad. Siendo esta última donde se desarrolla verdaderamente la búsqueda en profundidad.

La Función chooseMove, es la encargada de pasar el movimiento que tiene que realizar el pacman al programa general, en esta inicialmente se procede a guardar el estado actual del pacman, se inicializan las estructuras de datos usadas para almacenar los nodos visitados y para almacenar los movimientos y se llama a la función BusquedaProfundidad.

La función CapturaMovimiento, es usada dentro de la función BusquedaProfundidad para transformar todos los estados por los que ha pasado pacman para llegar el objetivo, a los movimientos necesarios para llegar a este. A continuación se presenta el pseudocódigo de esta función:

La función recibe como argumentos 2 estados, el origen y donde queremos ir.

CapturaMovimiento( Estado sOrigen, Estado sFinal){

Creamos lista à legalMoves, con los movimientos legales de sOrigen.

    Generamos un estado auxiliar à sAux, vacío;

    Para ( todos los legalMoves ) hacer

     

     Asignamos a sAux, el movimiento legalMove, actual.

     

Si ( El estado sAux, es igual a sFinal, con el legalMove actual)

Retornamos ese legalMove;

Fin_para

// No se puede acceder al estado sFinal,con ningún movimiento

Retornamos null;

}

     

Por último, se procede a comentar la función BusquedaProfundidad. Como se ha comentado anteriormente esta es una función recursiva, que recibe como argumento un Estado y el número de puntos que hay actualmente en el tablero. Este segundo argumento ayudará a descubrir si en el estado actual pacman llega al objetivo, es decir, se ha comido un punto.

En esta situación, se retornará una lista con todos los estados que han llevado al objetivo, y se devolverá el control a la función chooseMove.

La primera vez que se llama a la función el estado actual será el correspondiente a la situación inicial del juego y el número de dots será 0. El pseudocódigo será el siguiente:

ArrayList de estados: BusquedaProfundidad ( State sActual, int NumeroDots){

      Si ( el estado actual sActual es objetivo) entonces

           

            Capturamos el historial de estados hasta esta situación.

            Retornamos la lista con los estados.          

      Sino

            Si ( La posición de sActual no ha sido visitada )

                  Se guarda en la estructura de datos de visitados.

            legalMoves = Capturamos los movimientos legales de sActual.

            Para ( Todos los legalMoves ) hacer

                  sNext = estado siguiente con el movimiento actual.

Si ( sNext no ha sido visitado, y no es el padre del estado actual sState ) entonces

ListaEstados (lista de estados a el Objetivo) = BusquedaProfundidad(sNext, Número de dots con sActual);

     

Si (ListaEstados no es vacia ) entonces

Comprobamos si el número de estados que tiene es mejor, que el camino encontrado anteriormente. Y si es mejor, seleccionamos esta.

                        Fin_si

                  Fin_si

Fin_para

Fin_si

Si llegamos hasta este punto, no existe ningún camino al objetivo, desde el hijo actual.

Entonces retornamos null;

}


3.5. Pruebas y resultados.

Para probar el funcionamiento del algoritmo se realizan múltiples pruebas, y se recogen 7 ejecuciones de este.

Bus. Profundidad	Eje. 1	Eje. 2	Eje. 3	Eje. 4	Eje. 5
Nodos Cerrados.	39890	39364	37840	33935	35464
Nodos Expandidos.	40051	39638	38075	34018	35655
Nivel.	15	15	15	15	15
Puntuación	24251050	24220770	24286570	24241940	24229820

Se observa con claridad como aumenta la cantidad de nodos cerrados y expandidos según avanzamos de nivel.

Por ejemplo:

Ghosts: []

Nodos Cerrados :12768

Nodos Expandidos :12778

Puntuación :550

Starting level 2

Nodos Cerrados :17028

Nodos Expandidos :17058

Puntuación :1100

Starting level 3

Nodos Cerrados :19803

Nodos Expandidos :19841

Puntuación :2120

Starting level 4

Nodos Cerrados :22485

Nodos Expandidos :22540

Puntuación :4370

Starting level 5

Nodos Cerrados :23759

Nodos Expandidos :23822

Puntuación :9500

4.    Búsqueda en Anchura.

4.1. Objetivo

Para este segundo problema se pide realizar un agente pacman que utilice un algoritmo de búsqueda en anchura. El cual, ha de ser capaz de encontrar el camino correcto hasta el punto más cercano he ir a este por el camino más optimo posible.


4.2. Solución al problema propuesto.

Para llegar a la solución del problema propuesto, se decide realizar un algoritmo basado en búsqueda en Anchura mediante árboles (ver Figura 3).

(Figura 3)

Al igual que para el algoritmo de búsqueda en profundidad, se utilizará una función recursiva para simular el recorrido en anchura. Si bien es cierto que se podría haber resuelto sin ningún problema con una función iterativa, pero desde mi punto de vista el uso de la recursión en este aspecto ayuda a la simplicidad del código y a un mejor entendimiento de este.

Básicamente, la idea en la que se basa el algoritmo desarrollado, consiste en apoyarnos en dos estructuras de datos (colas), que nos permitirán ir avanzando por niveles y almacenar todos los nodos de cada nivel, para después comprobar si son objetivos.

De tal forma que, inicialmente se tendrá en una de las colas todos los nodos padres almacenados, y tras comprobar si cada uno de estos es objetivo, los expandiremos y almacenaremos en la segunda cola todos los nodos hijos de estos. Tras esto llamaremos a la función recursiva con la cola de nodos hijos, y realizaremos un cambio de contexto, donde estos últimos pasarán a ser ahora nodos padres, y así sucesivamente hasta encontrar el objetivo.

Se puede observar, que de esta forma nos aseguramos que siempre el camino encontrado hasta el objetivo será el camino más corto, pues será el que se encuentra a menos nivel de profundidad. Pero que cuanto más lejos se encuentren los puntos entre sí, mayor serán los nodos a visitar, y a la par, aumentará la complejidad de forma considerable.


4.3. Ventajas e inconvenientes detectados.

La mayor ventaja de usar este tipo de búsquedas es que se asegura que siempre se encontrará un camino hasta el objetivo, ya que este tipo de algoritmos son capaces de recorrer todas las situaciones posibles que pueden darse.

Por el contrario, se ha de destacar que se trata de un algoritmo que consume mucho coste computacional, cosa que hace verdaderamente complejo que pacman alcance niveles por encima del nivel 10, donde encontramos profundidades de hasta 70.

Esto es  debido a que en estos niveles el laberinto propuesto solo tiene un punto, que se encuentra en la esquina superior derecha del tablero, haciendo así que pacman tenga que recorrer todo el laberinto de forma virtual, antes de encontrar el camino hasta el objetivo.

Si bien, es cierto que la implementación de este tipo de búsquedas resulta bastante menos compleja que en los otros dos tipos de algoritmos que resuelven esta práctica.


4.4. Pseudocódigo.

El algoritmo implementado se divide en tres funciones: chooseMove, CapturaMovimiento y BusquedaAnchura. Siendo esta última donde se desarrolla verdaderamente la búsqueda en Anchura.

La función CapturaMovimiento se reutiliza del algoritmo de búsqueda en profundidad, siendo exactamente la misma que se describe en el punto 3.4 de esta memoria.

Inicialmente, la función chooseMove es la encargada de devolver el movimiento que tiene que realizar el pacman en cada transición. Además, tras inicializar todas las estructuras de datos y contadores a usar, llama a la función busquedaAnchura para que calcule el camino hasta el siguiente punto.

La función   BusquedaAnchura, recibe como argumento una cola cState. La primera vez que es invocada cState sólo contiene el estado inicial, es decir, donde se encuentra pacman actualmente.

En esta función, vamos sacando uno a uno los elementos que contiene cState, y comprobamos si el estado extraído es objetivo. Si es objetivo retornamos el camino y si no, expandimos el nodo y añadimos los nodos hijo a la cola de nodos hijos. Cuando hemos sacado todos los nodos hijos posibles del nivel actual de nodos padres, invocamos de nuevo BusquedaAnchura pasándole como argumento la cola de nodos hijos, y así sucesivamente. Se puede ver la implementación con más detalle en el siguiente pseudocódigo.

Cola de estados: BusquedaAnchura ( Cola cState ){

    cNextLevel à Declaramos cola de hijos.

    cFin à Cola que tendrá el camino hasta el objetivo, si se encuentra.

    Mientras ( cState tenga nodos ) hacer

     

      NodoActual = Extraemos el primer nodo de cState y lo borramos.

          Si ( es objetivo ) entonces

              Guardo el camino hasta objetivo en cFin;

              Retornamos cFin;

          Si_no

           

          legalMoves à Obtengo movimientos legales desde NodoActual;

             

Para ( todos los movimientos legales legalMoves ) hacer

           

   sNext = obtenemos el estado siguiente con el movimiento actual.

               Si ( sNext no es igual al padre del NodoActual) entonces

                        Guardo sNext en cNextLevel, Cola de hijos

              Fin_para

          Fin_si

      Fin_mientras

      Llamada a BusquedaAnchura(cNextLevel), con la cola de hijos.

}


4.5. Pruebas y Resultados.

Los datos de las pruebas se capturan al final del nivel al que llega pacman, aunque se realiza la búsqueda para encontrar cada punto, los datos aquí expuestos corresponderán a la suma total del último nivel completado, siendo este el más complejo computacionalmente.

Bus. Profundidad	Eje. 1	Eje. 2	Eje. 3	Eje. 4	Eje. 5	Eje. 6	Eje. 7
Nodos Cerrados.	268762	254572	1424393	67258	23259	252638	245095
Nodos Expandidos.	635660	636103	3639809	161819	56691	591073	596912
Nivel.	11	12	14	10	10	11	13
Puntuación	695840	1264070	8284770	469120	409400	654020	2969680

Pacman avanzará más o menos niveles según la complejidad que tenga el laberinto, porque cuanto más complejo es este, mayor coste computacional requiere. En niveles superiores al 10 nos encontramos con una barrera computacional, que hace que no se avance más en el juego.

5.    Búsqueda usando el Algoritmo A*.

5.1. Objetivo.

El objetivo de este último problema propuesto es realizar un algoritmo basado en la técnica de búsqueda informada conocida como A*. Para ello se describirá tanto la heurística[2] utilizada en la resolución como su implementación.

5.2. Solución al problema propuesto y Heurística elegida.

La solución del problema expuesto se basa en una heurística que ayuda a encontrar la solución de forma más rápida.  El problema ha sido resuelto mediante una función recursiva, al igual que los anteriores.

En este caso, en cada llamada a la función recursiva se le pasa un estado raíz. Después se  comprueba si es objetivo. Si es objetivo se retorna el camino hasta este, y si no,  se marca como visitado y se expande. Posteriormente, cada nodo hijo será evaluado por la heurística elegida.

Esta heurística consiste en comprobar si la distancia hasta el objetivo + el coste que supone llegar hasta él es la menor posible. Cuando se detecta la menor distancia, se pasa el nodo encontrado y pasa a ser el nuevo nodo raíz en la función recursiva.

5.3. Ventajas e Inconvenientes detectados.

Una de las mayores complicaciones encontradas se encuentra relacionada expresamente con la heurística elegida. Como se ha explicado anteriormente, consiste en elegir el nodo que se encuentra más cercano del próximo punto a comer.

A priori es una heurística completamente válida para resolver el problema de forma eficaz, pero se complica cuando la función que devuelve la distancia en Manhattan no tiene en cuenta los bloques y los cuenta como movimientos válidos. En esta situación, pacman no sabe cuál es el bueno y el algoritmo falla.

Para resolver este problema, se intenta definir una nueva función que calcule la distancia hasta el dot más cercano, pero teniendo en cuenta los bloques que impiden el paso. Para ello se implementa una búsqueda en profundidad que devuelve el coste real hasta el objetivo, pero como es de esperar, se dispara el coste computacional y se hace que el algoritmo A*, sea una simple búsqueda en profundidad. (Se añade este código como adjunto, CalculaCoste.txt).

Por falta de tiempo, se deja el algoritmo pensado inicialmente, aunque este no sea completamente funcional, y falle en esa situación completa. Intentando transmitir al equipo docente que aunque no se ha llegado a la resolución completa del problema, se ha entendido completamente el funcionamiento de este tipo de algoritmos.

5.4. Pseudocódigo.

El algoritmo implementado se divide en tres funciones: chooseMove, CapturaMovimiento y BusquedaAEstrella. Siendo esta última donde se desarrolla verdaderamente la búsqueda en Anchura.

La función CapturaMovimiento se reutiliza del algoritmo de búsqueda en profundidad, siendo exactamente la misma que se describe en el punto 3.4 de esta memoria.

Inicialmente, la función chooseMove es la encargada de devolver el movimiento que tiene que realizar el pacman en cada transición. Además, tras inicializar todas las estructuras de datos y contadores a usar, llama a la función BusquedaAEstrella para que calcule el camino hasta el siguiente punto y devolver uno a uno los movimientos hasta el objetivo.

A continuación se detalla el pseudocódigo de la función BusquedaAEstrella:

BusquedaAEstrella( Estado EstadoActual ){

DistanciaFinal à Inicialmente será infinito, es la variable que recoge la distancia mínima hasta el objetivo

Si ( El EstadoActual es el objetivo ) hacer

  Almaceno el camino hasta el objetivo en una lista común al módulo.

  Retorno void;

SiNo

  Si ( EstadoActual no ha sido visitado ) hacer

     Guardo Estado actual en la lista de visitados.

Fin_si

  sFinal à Variable que guardará el estado más cercano al objetivo.

  legalMoves à Capturamos todos los movimientos legales de EstadoActual.

  Para ( todos los legalMoves ) hacer

      sNext à Guardo el estado siguiente, con el movimiento actual.

      Si ( no ha sido visitado sNext ) entonces

Distanciaà Calculamos el coste de llegar a sNext + la distancia         en Manhattan hasta el punto más cercano.

 

        Si (sNext es objetivo ) entonces

            Distancia = 0;

            sFinal = sNext;

            DistanciaFinal = Distancia;

       

        SiNo

            Si ( Distancia < DistanciaFinal ) entonces

sFinal = sNext;

              DistanciaFinal = Distancia;

            Fin_si

            Fin_si

      Fin_si

  Fin_para

// Llamada Recursiva

   BusquedaAEstrella(sFinal);

Fin_si

}


5.5. Pruebas y Resultados.

Los datos de las pruebas se capturan al final del nivel al que llega pacman, aunque se realiza la búsqueda para encontrar cada punto, los datos aquí expuestos corresponderán a la suma total del último nivel completado, siendo este el más complejo computacionalmente.

Bus. Profundidad	Eje. 1	Eje. 2	Eje. 3	Eje. 4	Eje. 5	Eje. 6	Eje. 7
Nodos Cerrados.	164	124	192	116	52	116	168
Nodos Expandidos.	424	298	470	277	129	275	398
Nivel alcanzado.	3	2	3	2	1	2	3
Puntuación	2000	1230	2320	1150	510	1130	2110

Aunque se observa que rara vez se pasa del nivel tres debido al problema expuesto anteriormente, se observa que es un algoritmo más ligero, y consume mucho menos coste computacional.

6.   Comparativa sobre el comportamiento de los agentes desarrollados.

Como comparativa entre los tres algoritmos se ha de destacar que el más eficiente y óptimo corresponde a la búsqueda informada A*, ya que expande menos nodos y siempre encuentra un camino óptimo.

Por otro lado, se observa que aunque el método de búsqueda en anchura siempre encuentra la solución óptima en sus búsquedas, como comprueba absolutamente todos los posibles estados tiene un coste computacional muy elevado, cosa que se nota considerablemente a partir del nivel 10, donde solo se dispone de un dot.

Por último, mencionar que el algoritmo de búsqueda en profundidad es capaz de pasarse todos los niveles, pero si observamos cómo se mueve el agente pacman por el tableros, vemos que da muchas vueltas en algunas ocasiones. Además, si no se implementa sobre grafos, es prácticamente imposible encontrar buenas soluciones.

7.    Conclusión.

La resolución de problemas en IA requiere, normalmente, determinar una secuencia de acciones o decisiones. Esta secuencia será ejecutada posteriormente por un agente con el fin de alcanzar un objetivo a partir de  una situación inicial dada. Dependiendo del problema concreto, la ejecución de la secuencia de acciones o decisiones tiene asociado un coste que se tratará de minimizar.

Con el desarrollo de esta práctica, queda más claro que no todos los métodos a utilizar para la resolución de un problema tienen el mismo coste y en consecuencia la misma complejidad. Siendo los métodos de búsqueda informados más idóneos para el tipo de problema expuesto en esta ocasión.

---

[1] Nos basamos en la idea de que cuando se realiza cualquier búsqueda, pacman no se mueve realmente, si no que lo hace de forma transparente.

[2] D.R.A.E: Heurística = Arte de inventar; En algunas ciencias, manera de buscar la solución de un problema mediante métodos no rigurosos, como por tanteo, reglas empíricas, etc.