Práctica 1 - Vaccum Cleaner

Introducción

La práctica consiste en programar al robot usando un sistema reactivo para conseguir que recorra la mayor parte de la casa en el menor tiempo posible.

Concretamente programamos un autómata reactivo de estado finito, controlado con una máquina de estados que sigue el siguiente esquema:

En este breve vídeo se puede observar el comportamiento final del robot en cada estado:

Vemos cómo el robot comienza en el estado SPIRAL, cuando se choca pasa al estado TURNING, cuando termina el giro aleatorio pasa al estado FORWARD, y cuando lleva una distancia aleatoria sin chocarse pasa de nuevo al estado SPIRAL.

A continuación veremos los pasos y las diferentes estrategias seguidas que nos llevaron a conseguir que el robot tuviese dicho comportamiento.

Implementación

Primera estrategia: mismo giro siempre.

Como primera aproximación hice un programa reactivo que seguía en línea recta, hasta que chocaba con algo, momento en el que se disponía a girar sobre su propio eje (dado que el robot es holonómico no hay ningún problema con estos giros), siempre una cantidad concreta de grados hacia la derecha.

El ángulo de giro venía dado por una velocidad de giro constante (W=cte) durante un número de iteraciones constante.

En resúmen, el programa consta de una máquina de estados, que decide cuando cambiar o no de estado, con dos estados principales:

1. FORWARD: velocidad lineal constante hacia adelante (V=cte, W=0).
   
2. TURNING: velocidad angular constante (V=0, W=cte).

Problema: puesto que ese giro era el mismo en todo momento, el robot de vez en cuando entraba en habitaciones de la casa de las que no podía salir, ya que entraba en bucles aparentemente infinitos o muy largos.

 

Segunda estrategia: marcha atrás durante el giro.

Una segunda aproximación fue hacer que el robot diese marcha atrás (V constante negativa) durante el estado TURNING, para así desplazarse a la vez que giraba y evitar este tipo de bucle. Esto aparentemente funcionó para eliminar situaciones de bucles, pero introdujo otra situación difícil de evitar siguiendo esta misma estrategia.

Problema: cuando el robot retrocedía y se chocaba de nuevo con otra pared, la máquina de estados, al no haber perdido su reactividad, detectaba que se había chocado y entraba de nuevo en el estado TURNING, por lo que como resultado, entraba en otro bucle infinito dando archa atrás continuamente contra la pared que tenía detrás.

 

Tercera estrategia: no marchar hacia atrás y girar un ángulo aleatorio.

Primero intente solucionar el problema anterior introduciendo un ángulo de giro aleatorio en vez de constante, por lo que, en vez de girar siempre la misma cantidad, ahora giraba una cantidad aleatoria de grados durante el estado TURNING. Esto evitó en gran medida que el robot siguiese en este último bucle infinito, dando marcha atrás contra una pared, pero todavía seguía ocurriendo a veces, cuando se encontraba muy cerca de la pared.

Por ello decidí no mover el robot hacia atrás cuando se chocase, el nuevo comportamiento sería seguir hacia adelante y girar aleatoriamente cuando chocase, siguiendo cualquier otra dirección y repitiendo este comportamiento continuamente.

Ahora sí, teniendo una versión mínimamente estable comencé a hacer pruebas de rendimiento. Dejé esta ultima versión corriendo durante 2 horas en el simulador hasta que recorrió la mayor parte de la superficie de la casa, sin fallo alguno ni ningún otro bucle infinito.

Por lo que concluí que esta era la mejor estrategia a seguir con un comportamiento reactivo simple y sin localización, pero tal vez tardó demasiado en cubrir toda la superficie.

Mejoras

Mejora 1: espiral.

Problema: tardaba mucho en recorrer la habitación, por lo que decidí introducir un nuevo estado que mejorase su eficacia.

Para aplicar esta mejora, hice que la máquina de estados detectase, en función de un contador de iteraciones, cuando llevaba el suficiente tiempo en el estado FORWARD, como para comenzar una trayectoria en espiral, para abarcar más terreno, que acabaría cuando se chocase, volviendo al estado TURNING.

Para ello introduje un nuevo estado SPIRAL, que consistía en mantener constante la velocidad angular y aplicar una aceleración lineal, incrementando en cada iteración y de forma constante, la velocidad lineal (V=inc, W=cte).

En resumen, los nuevos estados quedarían de la siguiente manera:

1. FORWARD: velocidad lineal constante hacia adelante (V=cte, W=0).
2. TURNING:  velocidad angular constante (V=0, W=random).
3. SPIRAL:      velocidad lineal incremental y velocidad angular constante (V=inc, W=cte).

He aquí una demostración del nuevo comportamiento, en la que vemos cómo con múltiples espirales se recorre un área mayor que su hubiésemos ido en líneas rectas:

Una vez implementada esta mejora, debía ser probada. La dejé correr durante 15 min y estos fueron los resultados:

 Con esta mejora, en apenas 15 minutos ya había recorrido la mayor parte de la casa, teniendo en cuenta que en la zona sur de la casa es más complicado entrar debido a que se compone pasillos estrechos, y lo mismo con la zona este, debido a las mesas y los sofás.

Pero aún se podía mejorar un poco más.

Mejora 2: mínimo y máximo ángulo de giro.

Problema: observando me di cuenta de que cuando el robot chocaba, tardaba más de lo normal en adquirir una nueva trayectoria, porque a veces el ángulo era insuficiente y volvía a chocar, por tanto, entraba de nuevo en el estado TURNING. La peor parte de todo esto, es que al tener la velocidad angular del giro aleatorio entre el rango [-3, 3], podía girar en un sentido, y al acabar, volver a chocarse y girar en sentido contrario, haciendo que la maniobra de giro tuviese una innecesaria larga duración.

La solución a este problema fue hacer que solo girase en un sentido y poner unos ángulos mínimo y máximo apropiados para que no se quedase corto o se pasase, para evitar entrar en el estado TURNING demasiado tiempo, y manteniendo el giro aleatorio para seguir evitando bucles. Este nuevo rango de velocidades angulares fue [1, 3], que dio mejores resultados en el mismo tiempo (15 min):

 

 

 

Mejora 3: distancia recorrida en línea recta aleatoria.

Problema: a veces, al recorrer cierta distancia constante en línea recta en el estado FORWARD, cuando entraba en una habitación de determinadas dimensiones, tendía a quedarse dentro demasiado tiempo, ya que iba hacia el centro y hacía la espiral hasta que se chocaba y volvía a repetir el mismo proceso.

Para solucionar esto decidí, no solo aumentar esta distancia en línea recta, sino definirla aleatoriamente de igual forma que el giro, puesto que así también se podrían evitar posibles bucles. Al final el mínimo del rango de la velocidad aleatoria sería la velocidad que teníamos antes como constante, y el máximo lo definiríamos a base de prueba y error, finalmente siendo [2, 4] (definimos velocidades máximas y mínimas, ya que como se ha explicado anteriormente, la distancia recorrida o ángulo girado dependen de las velocidades lineales o angulares, ya que el número de iteraciones durante las que se aplican estas velocidades es constante).

Tras estas últimas modificaciones, los resultados habiendo pasado 10 minutos fueron los siguientes:

Vemos cómo en un tiempo record recorre la mayor parte del área de la habitación, y en poco más de media hora de ejecución, había recorrido la casa prácticamente entera: