Inteligencia artificial para videojuegos/Búsqueda en el espacio de estados

Introducción

Resolutor. Se donde estoy y dónde está la salida, tengo que encontrar el camino.

Resolutor mediante búsqueda

El resolutor reflejo simple es ideal si tienes espacio y tiempo para aprender.

Si sabemos algo sobre la solución es mejor usar al menos un resolutor basado en objetivos. En una búsqueda clásica se asume representación atómica de problemas, soluciones y sus relaciones, y también que la solución es una secuencia fija de operadores aplicados para resolver el problema, es decir, pasar de una configuración inicial a un objetivo.

Un resolutor basado en objetivos ignora toda medida de éxito, por tanto, la formulación del objetivo es crítica, y esta sí se hace en base al problema (y también pensando en cierta eficiencia).

Una vez fijado el objetivo hay que escoger qué configuraciones y operadores usar para representar el dominio de trabajo. Esta formulación del dominio también es crucial, esto supone un ejercicio de abstracción.

Para elegir entre varios operadores posibles tenemos que explorar las configuraciones resultantes, y los posibles operadores siguientes. Además asumimos conocer el dominio de trabajo y que el problema es completamente visible, determinista y discreto.

     Formulación         →         Búsqueda         →        Ejecución
(objetivo y dominio)         (Conf ini → Conf obj)        (De la solución)

Formulación del dominio de trabajo

Definir el problema:

Configuraciones posibles. Empezando por la inicial.
Operadores posibles. Una función determina los aplicables a una determinada configuración.
Modelo de transición. Función que devuelve la configuración resultante de aplicar un operador a una configuración.
Prueba de objetivo. Función que comprueba si una configuración es objetivo (Pueden serlo varias).
Coste de ruta(Path cost). Función que asigna un valor numérico a cada ruta. (La suma de los costes todas las transiciones(Step cost)).
- Coste Conf3 → Conf5 = (Conf3 → Conf4) + (Conf4 → Conf5)

Espacio de búsqueda o de estados. Todo lo anterior define un grafo dirigido con todas las configuraciones alcanzables.

Ruta. Cualquier secuencia de configuraciones conectadas por operadores.

Ejemplo

Juego de la aspiradora:

Mundo con 2 casillas: A y B.
- Puede haber o no haber polvo.
IA. Sabe en qué casilla está y si tiene polvo.
- Operadores: Aspirar, mover izquierda, mover derecha

Formulación del dominio:
- Configuraciones: si hay N casillas, hay N * 2^N configuraciones posibles.
  - N=2. 8 configuraciones.
  - Inicial. Robot en A y polvo en A y B.
- Operadores. Izquierda, derecha y aspirar.
- Modelo de transición. Moverse hacia fuera o aspirar sin polvo no tiene efecto alguno.
- Prueba de objetivo. Comprobar que no hay polvo en ninguna casilla.
- Coste de ruta. Es habitual considerar que cada transición cuesta 1. Coincidirá con el número de pasos.

Espacio de búsqueda. En este ejemplo sencillo se puede ver, pero suelen ser inabarcables, incluso infinitos.

Búsqueda de soluciones

Una vez formulado objetivo y dominio, el resolutor tiene que resolver.

Construimos un árbol de búsqueda:

Nodos: Configuraciones
Ramas: Operadores
Nodo raíz. Tiene configuración inicial.
Se examinan los nodos 1 a 1, y si no pasan la prueba de objetivo, se expanden, generando nodos hijos.
Nodos hojas. Representan la frontera del árbol en un momento determinado de la búsqueda.

//Devuelve solución o fallo
funcion BUSCA-ARBOL(Conf ini, Conf objetivo)
{
    //Inicializamos frontera con la conf Inicial del problema
    frontera = new Frontera();
    frontera.push(ini);
    
    while(true)
    {
        //Si frontera vacía, devolvemos fallo
        if (frontera.empty())
            return fallo;
            
        //Elegimos nodo hoja y lo quitamos de la frontera
        Nodo hoja = frontera.pop();
        
        //Si la hoja tiene la conf Objetivo, devolvemos solución
        if (PruebaDeObjetivo(hoja.conf))
            return solucion;
            
        //Expandir nodo: añadir hijos a la frontera
        Queue <Operador> operadores = OperadoresPosibles(hoja);
        
        while(!operadores.empty())
        {
            Operador op = operadores.pop();
            
            Conf conf = ModeloDeTransicion(hoja.conf,op);
            
            Nodo hijo = new Nodo(conf);
            frontera.push(hijo);
        }
    }
}

Deberíamos evitar nodos repetidos por rutas redundantes (incluso cíclicas) con memoria: Manteniendo conjunto de nodos explorados.

//Devuelve solución o fallo
funcion BUSCA-GRAFO(Conf ini, Conf objetivo)
{
    //Inicializamos frontera con la conf Inicial del problema
    frontera = new Frontera();
    frontera.push(ini);
    
    //Inicializa conjunto explorado a vacío
    explorado = new Explorado();
    
    while(true)
    {
        //Si frontera vacía, devolvemos fallo
        if (frontera.empty())
            return fallo;
            
        //Elegimos nodo hoja y lo quitamos de la frontera
        Nodo hoja = frontera.pop();
        
        //Si la hoja tiene la conf Objetivo, devolvemos solución
        if (PruebaDeObjetivo(hoja.conf))
            return solucion;
            
        //Añade nodo a conjunto Explorado
        explorado.push(hoja);
            
        //Expandir nodo: añadir hijos a la frontera
        Queue <Operador> operadores = OperadoresPosibles(hoja);
        
        while(!operadores.empty())
        {
            Operador op = operadores.pop();
            
            Conf conf = ModeloDeTransicion(hoja.conf,op);
            
            Nodo hijo = new Nodo(conf);
            
            //Si nodo no está explorado ni en frontera
            if (!frontera.contains(hijo) && !explorado.contains(hijo))
                frontera.push(hijo);
        }
    }
}

Infraestructura

Los algoritmos de búsqueda necesitan cierta infraestructura para sostener el árbol de búsqueda que se va generando.

Cada nodo es una estructura de datos con un ejemplar de la configuración correspondiente, referencia a su nodo padre (salvo si es la raíz), referencia al operador que se aplicó al nodo padre para generar este nodo hijo (salvo si es la raíz), coste de ruta (calculando desde la raíz hasta aquí).

Se necesita la función de expandir nodos y algún tipo de “cola” para la frontera:

Cola (FIFO): Implementado mediante memoria circular o lista enlazada.

Pila (LIFO): Implementado con un array o lista enlazada.

Cola de prioridad ( Primero el más prioritario ): Utilizando un array o montículo.

Para el conjunto de nodos explorados suele usarse una tabla de dispersión, además, para reconocer las configuraciones iguales se puede usar alguna forma canónica de representación.

Medida del éxito en búsquedas

Se pueden usar diferentes algoritmos para decidir qué nodo debemos elegir primero para expandir.

El nivel de éxito del algoritmo se puede medir de varias formas:

Completitud. Si hay solución la encuentra.
Optimalidad. Encuentra la solución con menor coste de ruta de todas.
Complejidad temporal. Segundos del procesador.
Complejidad espacial. MiB ocupados en RAM.
- 1 megabyte(MB) = 10^6 bytes
- 1 mebibyte(MiB) = 2^20 bytes

Complejidad. Suele expresarse en función de un N:
- La suma de vértices y aristas. Si conocemos el espacio de búsqueda.
- El factor de ramificación R(Branching factor). Máximo número de hijos de un nodo.
- La profundidad P mínima hasta un nodo objetivo(depth). Número de pasos de la ruta.
- La profundidad M máxima de cualquier ruta. Número de pasos.

La complejidad funciona para árboles de búsqueda. En grafos, depende de la redundancia de las rutas.

Participantes

Federico Peinado.
Adriana del Castillo Espejo-Saavedra.
Alejandro Villar Rubio.
Sergio Gavilán Fernández.