ASPIRADORA

Anlisis general

Disponemos de un mundo en el que habitan dos agentes. Este mundo es un recinto cerrado en forma de cuadrcula de tamao nxn, en el que cada casilla podr tener suciedad, un obstculo o nada (zona de paso). Los agentes poseen dos sensores, uno de suciedad y otro de choque y cuatro efectores, para moverse en las cuatro direcciones cardinales, y tienen la misin de succionar ms cantidad de suciedad que el adversario.

El mundo est compuesto por casillas vacas con o sin suciedad y por obstculos, las primeras podrn ser recorridas y limpiadas por los agentes, mientras que los obstculos, no podrn ser atravesados. Adems, el mundo no es estocstico, ya que la suciedad y distribucin de obstculos en l es determinada al principio y slo vara por la accin de los agentes, acciones que ambos agentes conocern en todo momento.

Cada agente conoce a priori el mapa del mundo, incluyendo la distribucin de muros y casillas sucias. Tambin sabe el grado de suciedad que tienen las casillas sucias, medido en nmeros enteros crecientes, empezando en 0 para casillas limpias. En esta ocasin nuestros agentes tienen la habilidad de succionar la suciedad de una casilla con slo pasar sobre ella, por contra, dejarn un rastro en cada casilla que han atravesado de forma que esa casilla no puede ser visitada de nuevo por ninguno de los dos agentes.

La percepcin del tiempo para los agentes es discreta y slo podrn realizar un movimiento en turnos alternos, a no ser que algn agente quede bloqueado sin poder moverse.Solucin propuesta Hemos diseado un agente reactivo con memoria y a la vez un agente de bsqueda en profundidad, el agente posee un vector de caractersticas con las siguientes componentes: Coordenada X del agente en el mapa interno. Coordenada Y del agente en el mapa interno. ltimo movimiento realizado.

Para la toma de decisiones, el agente hace uso de los sensores de percepcin y de varios Mdulos de Conocimiento que determinarn la accin a realizar. Bsicamente, el funcionamiento del agente consiste en repetir los siguientes pasos:

Llamar a los Mdulos de Conocimiento "actualizarMapa" y "actualizarPos" para actualizar la representacin interna del mundo segn el estado del sensor de choque y la posicin del agente. Comprobar si el sensor de suciedad se ha activado, en caso afirmativo, limpiar la casilla. Si la casilla est limpia, el agente llamar al Mdulo de Conocimiento "modoExploracion" que buscar en la representacin interna si una de las cuatro posibles casillas a las que el agente puede desplazarse en el prximo turno no ha sido nunca explorada. En caso afirmativo se desplazar a esa posicin. Si las cuatro casillas estn exploradas, el "modoExploracion" indicar al agente que permanezca inactivo, en ese caso el agente acudir al segundo Mdulo de Conocimiento denominado "modoMasAntigua" que buscar en la representacin interna la casilla de su alrededor (de las cuatro posibles) que lleve ms tiempo sin visitar y que no sea un muro. Finalmente indicar al agente que se mueva en la direccin oportuna.

La razn de aplicar este comportamiento es que como no podemos saber qu casilla se ensucia ms o menos puesto que es aleatorio, el agente tratar siempre de ir hacia casillas que lleven ms tiempo sin ser visitadas y, por tanto, que tengan mayor probabilidad de estar sucias. Este algoritmo, a pesar de ser muy sencillo, es bastante eficaz.Estructura Interna del Agente

void actualizarMapa() Mdulo que actualiza el mapa interno segn la posicin y el estado del sensor de choque "bump_". Adems, cada casilla que ya est descubierta se incrementa en 1, reflejando as el nmero de turnos que el agente no ha pasado por dicha casilla (antigedad). Por lo tanto, existen una serie de valores posibles para cada casilla del mapa, que son: -1 : Casilla que nunca ha sido visitada (sin explorar). 0 : Muro. 1 : ltima casilla visitada (debe ser un hueco). >1 : Casilla visitada hace n turnos (debe ser un hueco).

En el proceso de actualizacin del mapa, llama a buscarLimites() para intentar descubrir los lmites del mapa.

void actualizarPos(int direccion) Actualiza las coordenadas del agente segn la direccin que va a tomar. Adems, almacena el movimiento como el ltimo que ha hecho. NOTA: Este mdulo debe ejecutarse despus de decidir qu accin va a realizarse pero antes de realizar el movimiento.

void buscarLimites() Recorre la matriz interna para buscar los lmites del mapa (permetro) y, si los encuentra, los marca como muros. Basta con encontrar 2 huecos separados entre s 6 filas o 2 huecos separados 6 columnas. Se puede hacer aprovechando que se sabe que es un recinto cerrado de 10x10. Este mdulo no ofrece una gran mejora de eficacia y slo es til en mapas en los que el agente puede chocar contra los cuatro lados del permetro del mapa. Pero se deja activo ya que est hecho y funciona.

int modoExploracion()Busca una casilla sin explorar de las cuatro posibles de alrededor del agente (los cuatro puntos cardinales). Devuelve la accin que debe realizar el agente para ir a la casilla sin explorar o "actIDLE" en caso de que las cuatro posibles casillas hayan sido ya exploradas. En caso de que haya ms de una casilla sin explorar, se aplicarn las siguientes reglas, en orden de prioridad: La casilla sin explorar est en la misma direccin tomada el turno anterior. La casilla sin explorar est arriba. La casilla sin explorar est abajo. La casilla sin explorar est a la izquierda. La casilla sin explorar est a la derecha.

En caso de que las cuatro casillas ya estn exploradas el mdulo devuelve "actIDLE".

int modoMasAntigua() Busca la casilla que haya sido visitada al menos una vez y que ms tiempo lleve sin visitar de las cuatro posibles de alrededor del agente. Devuelve el movimiento a realizar para ir a esa casilla.

void Think() Es el mdulo principal del agente, se encarga de llamar al resto de mdulos para determinar la accin a realizar. Su funcionamiento ya ha sido explicado en la seccin "Descripcin de la Solucin Propuesta".Ahora se tendr que usar una interfaz grfica para poder observar la realizacin del programa grficamente:Utilizaremos el algoritmo MINIMAXSe ha aplicado el clsico algoritmo Mini Max con una pequea variacin: Si el nivel de profundidad es menor que 10. Generar posibles movimientos. Si se est en un nodo Max, tomar el movimiento generado con mayor valor heurstico. Si se est en un nodo Min, tomar el movimiento generado con menor valor heurstico.

Si no se ha generado ningn movimiento, significar que el agente no se puede mover. Por tanto, tomar el valor que retorne de aplicar el algoritmo al estado actual, cambiando el turno del jugador. Si el nivel de profundidad es 10 o ms. Aplicar la funcin heurstica para el estado actual y el jugador que llam por primera vez al algoritmo. Devolver el movimiento elegido por Max.

HeursticaLa heurstica usada utiliza tres parmetros ponderados:

Distancia manhattan desde el agente al punto sucio ms cercano, con una ponderacin de 0.59. Nmero de muros alrededor del agente, slo contando los cuatro puntos cardinales, tiene una ponderacin de 0.19. Nmero de veces que ha estado el agente en esa posicin (envejecimiento) contando desde la ltima casilla limpia. Esto quiere decir que cuando se limpia una casilla se reinician los contadores de todas las casillas visitadas. Se ha puesto 0.22 de ponderacin.

Conclusiones: Elegimos el agente reactivo con memoria, cuyo nico conocimiento inicial del entorno es que se est en un recinto cerrado de 10x10 casillas que se ensucian de forma aleatoria. El robot debe maximizar la suciedad aspirada y minimizar el consumo.

Usamos el agente deliberativo que use bsqueda en profundidad con conocimiento de la localizacin de la suciedad y de los muros de un recinto de tamao NxN. El robot debe maximizar el nmero de casillas limpiadas y minimizar el consumo.

Creamos un agente deliberativo que use bsqueda basada en un mtodo de escalada con conocimiento de la localizacin de la suciedad y de los muros de un recinto de tamao NxN. El robot debe maximizar el nmero de casillas limpiadas y minimizar el consumo.

Elaboramos un agente deliberativo que use bsqueda MINIMAX con profundidad limitada. Este agente estar en el entorno (conocido) con otro agente aspiradora y debe tratar de aspirar ms suciedad que su rival. Adems, para este problema en concreto, los agentes dejan una estela por las casillas que atraviesan, impidiendo que se vuelva a poder pasar por ellas.

Estructura