Recocido Simulado en Webots con Naos

Breve descripción del medio ambiente. 

El medio ambiente se desarrolla a partir del simulador 3D Simspark, el cual es el simulador oficial para las competencias dentro de la Robocup Standard League y contiene todas las reglas para oficiales para llevar a cabo partidos de fútbol con los robots bípedos llamados Nao. El simulador contiene diferentes elementos básicos que definen las dimensiones de la cancha, así como la ubicación de las porterías y la pelota. Además incluye a diferentes Naos para ambos equipos y con la posibilidad de especializar sus acciones para que sean porteros, defensas o delanteros. El objetivo final primordial para cada jugador de cada equipo será meter la bola en el arco contrario y así realizar un gol para aumentar en un punto el marcador de su equipo.

Para la realización de la fase 2 del proyecto en la implementación de los algoritmos del recocido simulado y LMS de aprendizaje, hemos utilizado el simulador Webots para Windows, el cual contiene características similares a las del Simspark pero posee una interfaz más útil para el desarrollo de nuestras pruebas.

Descripción detallada del problema de optimización – da al menos un ejemplo en donde se vea por qué es un problema de optimización. 

El problema para optimizar radica en que el Nao debe encontrar la distancia más deseable para patear la bola, y que el tiro sea efectivo en cuestiones de velocidad y alcance. La interacción entre el Nao y el ambiente nos regresa distintas percepciones como la distancia del Nao a la bola o el saber si la bola se ha movido, esto nos ayudará a calcular la distancia ideal a patear la cual será la variable que se optimizará. 

El algoritmo de optimización nos ayudará a encontrar la distancia ideal, considerando que si el Nao patea y no golpea la bola significará que está muy lejos del balón y se necesitará reducir la distancia para patear, de esta forma la próxima vez que patee tratará de acercarse a la bola y patearla correctamente. Existe un caso en que aumentaría la distancia de la cercanía para patear y este se da cuando el Nao mueve la bola sin haber pateado, en esta situación el algoritmo de optimización aumentará la tendencia para aumentar la cercanía entre el Nao y la bola.

Ejemplo del problema de optimización:

Inicialmente el Nao comenzará con una variable aleatoria que definirá su distancia a patear, supongamos que es una distancia de 0.75.

optBallDist = 0.75

El Nao va a tratar de patear al balón desde la distancia actual, pero el éxito o falla del disparó va a determinar si es que es correcta la distancia y definirá la tendencia del posible próximo valor. En este caso indicamos que el Nao patea en el aire sin pegarle a la bola, por lo tanto la optimización va encaminada a disminuir el rango para patear, obteniendo así valores más cercanos a la bola.

optBallDist = 0.7

En el caso que el Nao empiece a probar con valores muy cercanos a la bola, esta distancia hará que Nao no llegue a patearla y ésta se mueva con su caminado. De esta forma la tendencia de la optimización aumentará el rango de cercanía con la bola para que en los próximos intentos no se acerque tanto.

Supongamos ahora que el Nao aún no encuentra la distancia ideal y sigue pateando en el aire,  y en otros casos golpea la bola sin antes patear, esto permitirá que se siga ajustando el valor de la variable a:

optBallDist = 0.3

Nuevamente el Nao va a tratar de buscar la bola y patearla, pero esta vez se acerca y la patea exitosamente, esto significa que nuestro algoritmo encontró el valor óptimo o un valor cercano a lo óptimo para la distancia de pateo.

Solución planteada al problema utilizando el método de recocido simulado. Describe con detalle cada elemento del planteamiento: 

Para resolver el problema podemos utilizar el método del recocido simulado ya que el Nao tratará de encontrar un punto de equilibrio o un extremo global en una gráfica de valores, para tomarlo como distancia óptima para patear el balón. El algoritmo planteado define rangos que aumentan o disminuyen el espacio de una variable aleatoria que representa la distancia a optimizarse. Considerando esta variación como un cambio de temperatura, la función objetivo analizará el rendimiento de la variable aleatoria para definir el comportamiento gradual de la temperatura.

1) Configuración

El método de optimización se aplica sobre un programa de simulación que contiene la información y estados necesarios para la utilización de los algoritmos implementados, los cuales para el caso de la fase 2 del proyecto obtenemos como información más relevante la ubicación del robot y la bola en la cancha: 

[ (X-nao, Y-nao) , (X-bola, Y-bola) ] 

Analizando las diferentes posiciones que nos regresan variables adicionales como la distancia entre el Nao y la bola y  llegamos a los 3 posibles estados que utiliza el algoritmo del recocido simulado.

· Si el Nao patea antes de mover a la bola.

· Si el Nao patea la bola.

· Si el Nao no patea y mueve la bola.

2) Reordenamiento

El reordenamiento se aplica de igual forma al programa de simulación a través de reglas claves basadas en la Standard Robocup League. Por motivos de una demostración rápida para la optimización de la distancia a patear hemos obviado algunas reglas que básicamente quitan la acción de los contrincantes para que no interfieran con las acciones de nuestro Nao. Debido a que los algoritmos de búsqueda y caminado para el Nao no están optimizados encontramos además diversas limitaciones en nuestros estados:

· El Nao sigue una secuencia de movimientos al patear: se mueve un poco hacia la derecha, luego avanza unos pasos pequeños y procede a patear.

· El Nao al encontrar la bola tiene que direccionarse frente a la bola y frente al arco en posiciones definidas en el programa de simulación.

· La bola y el Nao interactúan con el ambiente, no permitiendo que excedan los límites de la cancha e impactando con los demás objetos que pueden provocar rebotes o caídas.

3) Función objetivo

La función objetivo de nuestro algoritmo está definida por el éxito de la patada con respecto a la bola, esto nos indica que el Nao ha pateado la bola a la distancia optimizada. El algoritmo reproduce variables aleatorias de distancias a patear, y aunque algunas veces podemos obtener una patada exitosa, el algoritmo de optimización sólo analiza las fallas para así limitar estas futuras posiciones.

F (distancia) -> Analiza si se patea la bola correctamente a la distancia indicada.

Ya en el código podemos ver esta función como:

  public void checkBallHit(){

      if (isBallMoving() == true && hasKicked == true){

      hasShot = true;

          System.out.println("NAO HIT THE BALL.");

          System.out.println();

          CalculateNewPoint();

      }

  }

4) Calendario de recocido

El recocido y el ajuste de la temperatura se comportan con respecto a los estados actuales que disminuyen la temperatura:

· Si el Nao patea antes de mover a la bola. > Disminuye el límite de espacios superior.

· Si el Nao no patea y mueve la bola. > Aumenta el límite de espacios inferior.

La próxima temperatura se define como:  

Ti+1 = α Ti

En dónde α representa la velocidad de cambio de la temperatura, que nuestro programa representa a través del aumento y disminución de los límites superior e inferior. 

El código que realiza el cambio de temperatura se define como:

  public void AdjustTemperature(){

 

 //Si ha pateado o golpeado la bola revisa que esté quieta.

      if (hasShot == true && (isBallMoving() == false)){

        hasShot = false;

      }

      

      checkBallHit();

      checkBallMovedNoShot();

      checkShotNoHit();

      hasKicked = false;

  }

Conclusiones después de la programación

Al desarrollar una aplicación con la teoría analizada en clase encontramos soluciones prácticas que resuelven objetivos claves y en el caso específico de nuestro proyecto: una optimización. El medio ambiente siempre es un problema cuando nos ofrece muchas limitaciones e influye en factores importantes para la implementación de nuestros algoritmos. Es por eso que tuvimos que primero modificar el medio ambiente para que permita una demostración clara de nuestras funciones. Luego, al aplicar las funciones nos dimos cuenta de la utilidad del recocido simulado y entender su objetivo primordial. Esto no hubiera sido tan claro si no lo hubiéramos llevado a una aplicación visual.

Lo interesante y útil fue que aprendimos tanto de la teoría de la inteligencia computacional como del simulador Webots. Esto nos ofrece nuevas ideas para optimizar dentro la simulación y para utilizar lo aprendido y desarrollado en aplicaciones futuras. Webots resultó ser un simulador fácil de entender y programar pero muy poderoso y documentado. Para realizar nuestro proyecto nos basamos para los comportamientos del Nao básico en un archivo que venía incluido en el simulador, estos comportamientos son reactivos y utilizan movimientos lentos que impedían pruebas rápidas, esta fue nuestra mayor limitación.