INTELIGENCIA EN REDES DE COMUNICACIÓN

PRÁCTICA FINAL

ENTORNOS DE SIMULACIÓN: RARS

Raúl Alonso Moreno Sofía Martínez Andrés

ÍNDICE

• Historia de Rars • Una panorámica de los simuladores de coches de carreras en la actualidad • El simulador Rars: Robot Auto Racing Simulator

• Introducción al Rars • Funcionamiento del robot: ejemplo básico de robot (Modelo físico y programa de

control)

- Modelo físico - Información esencial: la estructura “situation” - Información del robot: programa de control

• Funcionamiento del simulador (Display gráfico)

• Nuestro Robot

1. Algoritmos utilizados 2. Código del robot

• Conclusiones

HISTORIA DE RARS

La Historia de RARS (Robot Auto Racing Simulator) se puede decir que empezó en 1995 gracias a Mitchell Timin cuando un 30 de Abril se celebró un meeting en el que los participantes enviaron sus robots a una dirección de Internet programados en ANSI, C o C++. Se utilizó la versión de RARS 0.50.

Los coches que producían errores de compilación (Borland 3.1) o daban errores producidos por

otros participantes eran descalificados. Por esta razón, a pesar de haber una fecha límite para participar, todos los robots estaban listos con muchos días de antelación.

Los concursantes optaban a tres premios:

- El primer premio era el software "Street Wizard 5.0", que era un buscador de mapas y direcciones.

- El segundo premio era un libro de Mark Watson's McGraw-Hill titulado "C++

Power Paradigms", en el cual se habla de algoritmos genéticos, redes neuronales, etc.

- El tercer premio era otro libro de Mark Watson's Springer-Verlag llamado

"Common LISP Modules. Artificial Intteligence in the Era of Neural Networks and Chaos Theory".

La competición se realizó en 6 pistas en las cuales se corrían dos veces en cada pista. Se elegía un orden de salida aleatorio para la primera carrera y en la segunda se invertía el orden de salida. Las pistas eran las siguientes:

ANEW.TRK 8 laps OVAL2.TRK 20 laps V03.TRK 15 laps STEF2.TRK 15 laps SPEED2.TRK 10 laps ZANDVORT.TRK 8 laps

El número máximo de coches era 16. En caso de haber más, se recurrían a sesiones eliminatorias obteniendo así los 16 finalistas.

No se permitía que los códigos de los robots accedieran a zonas de memoria reservada, ni

realizaran llamadas al sistema indebidas. En caso contrario eran descalificados.

Los robots tenían que estar en código fuente o en un fichero objeto y no podían disponer de más de 25K de memoria RAM. Se debía ejecutar en no más de 3 milisegundos con el fin de no ralentizar la carrera y que pareciera lo más real posible.

Los resultados de estas primeras carreras dieron como vencedores a los siguientes participantes:

Randy Saint - Ramdu (Texas) Jussi Pajala - WappuCar (Finland, Wappu = Mayday) Mike Inman - Indretti (Florida) Safai Ma - Burns (Canadá) Bill Benedict - Rusty (U.S., at Rose-Hulman Tech) Grant Reeve - Grant1 (New Zeeland) Oscar Gustavsson- OscCar2 (Sweden) Tristrom Cooke - Bingo (Australia) Patrick Tierney - Heath (Australia)

En los últimos años los coches han mejorado mucho gracias a la utilización de algoritmos

genéticos, redes neuronales, autoaprendizaje….

UNA PANORÁMICA DE LOS SIMULADORES DE COCHES DE CARRERAS EN LA ACTUALIDAD

El objetivo de la práctica es simular la conducción de un coche de carreras mediante un algoritmo que, a partir de un conjunto de datos de entrada (velocidad, aceleración, inclinación, tipo de tramo…), mantenga al coche dentro de un circuito, intentando conseguir la mejor trazada. Se trata por lo tanto de la simulación de un conductor de carreras.

En principio el simulador propuesto para esta práctica era el TORCS, el cual tiene sus

versiones en Windows y Linux. La versión de Windows no funcionaba, no se podía arrancar el ejecutable que traía por defecto

y nuestro “querido” profesor ;) nos aconsejó utilizar Linux puesto que él tampoco había conseguido compilarlo en Windows y es aquí donde empieza la odisea y la lucha constante entre Linux y lo que acabó denominándose GAT o Grupo de Afectados por Torcs.

Ya sabíamos que su instalación en Linux no era sencilla puesto que requiere, por un lado,

disponer de privilegios de root, y por otro, la instalación y compilación de múltiples librerías. En la página oficial de Torcs hay disponible un detallado tutorial para dicha instalación el cual seguimos a “rajatabla”, pero tras completar satisfactoriamente los múltiples pasos el programa no ejecutaba.

Pensamos que podía ser la versión de Linux utilizada (Knoppix basado en Debian) por lo tanto

instalamos una versión de Debian actualizada, y cuál fue nuestra sorpresa al ver que la cosa no mejoró.

Consultamos con otro de los miembros del GAT el cual probó a utilizar otra distribución de

Linux y de nuevo nos quedamos absortos al comprobar que seguía sin funcionar. Así pasaban los días y tras un último intento de instalar Linux sin éxito alguno y tras la presión

que supuso ver en nuestro correo un e-mail de nuestro “querido” maestro recordándonos las fechas de entrega, decidimos entre polvorón y sidra, buscar algún otro simulador.

Encontramos varios (mirar los links al final de la nota) pero entre que unos seguían siendo

Linux (y no queríamos más pruebas, por lo de la presión) y otros no dejaban compilarlos en Windows, botamos por la opción del Rars el cual se podía programar, compilar y ejecutar con el Visual C++ de Windows.

Nos llevamos una gran alegría al ver que por fin podíamos empezar a trabajar en nuestro

conductor, pero a partir de aquí no todo fue un camino de rosas puesto que, a pesar de que hay un tutorial bastante bueno (http://rars.sourcefourge.net ) que explica la realización de los puntos básicos para la realización de un conductor, en ningún momento explica como instalarlo ni qué ficheros (librerías,*.h,*.cpp) hay que modificar para agregar nuestro código al proyecto y conseguir que funcione nuestro conductor o robot como lo llaman, trabajo que nos llevó más de un día y nos hizo plantearnos el cambiar de práctica. Tras una dura batalla conseguimos salir airosos y continuar con ello.

Los links a otros simuladores son los siguientes:

- Vamos Automotive Simulator: http://vamos.sourceforge.net/- Racer: http://www.racer.nl/- XRacer : http://xracer.sourceforge.net/

EL SIMULADOR RARS: ROBOT AUTO RACING SIMULATOR

• INTRODUCCION AL RARS

El Rars consiste en una simulación física del comportamiento del coche de carreras en un circuito, un display gráfico de la carrera y un programa de control de cada coche que cada programador diseña de forma independiente para poder competir entre si.

Se disponen de una serie de variables de entrada comunes propias del circuito (situación

actual del coche en la pista con todas sus variables: longitud del tramo, radio del tramo…), que cada coche recibe, las interpreta de alguna manera y según el algoritmo utilizado proporciona unas variables de salida propias del coche (velocidad y dirección).

• FUNCIONAMIENTO DEL ROBOT: Modelo físico y programa de control - Modelo físico:

Para poder implementar el algoritmo, es necesario conocer una serie de variables físicas que determinan el comportamiento del coche. Para explicar su significado nos apoyaremos en la siguiente figura:

El rectángulo representa el coche y sobre el se establece un sistema de coordenadas como el que se muestra en la figura, en el cual se representan los siguientes vectores:

- V: es el vector velocidad, orientado sobre el eje x, que indica la velocidad a la que se

desplaza el coche.

- P: es un vector unitario que indica la dirección y sentido que lleva el coche respecto al eje de coordenadas.

El ángulo que forman estos dos vectores es el ángulo de inclinación del coche (alpha). - W: este vector representa la velocidad de las ruedas del coche que giran en sentido

contrario a la dirección de desplazamiento, por eso su valor es negativo.

Suponiendo que suministramos a las ruedas una velocidad vc, llegamos a la conclusión de que W va a ser un vector de sentido contrario al vector P y de módulo vc.

PvcW ⋅−=

- L: es el vector que indica el desplazamiento que sufre el coche debido al ángulo de inclinación.

- F: es el vector que representa la fuerza que mantiene al coche dentro de la pista.

Los vectores V, L y F poseen sus respectivas componentes normales y tangenciales a los ejes.

Como se puede observar en la figura se cumple WVL += puesto que la velocidad del

coche sobre el eje X (V), es la que llevan las ruedas (W) menos el derrapaje que estas sufren (L) y de sentido contrario. Con esto se obtiene las siguientes relaciones:

)()cos(

alphasenvcLalphavcvL

PvcVL

n

t

⋅−=⋅−=⋅−=

También es necesario definir una función de fricción )(luf = que se descompone en:

lLluF ⋅−= )(

cuyas componentes tangenciales y normales son:

lLfF

lLfF

nn

tt

⋅−=

⋅−=

Por último definimos la potencia como:

( ) ( )( )alphasenFalphaFvcpwr nt ⋅+⋅⋅= cos

- Información esencial: La estructura “situación”

Para comprender mejor el funcionamiento del robot es necesario hacer una introducción a los datos de entrada de los que disponemos. Estos datos son variables de la estructura “situation”, las cuales son accesibles por todos los coches a través de la librería “cars.h”. Para su mejor comprensión nos apoyaremos en la siguiente figura:

• cur_rad: indica el radio de la curva en la que se encuentra el coche en cada momento. Será positiva si la curva es a izquierdas, negativa si la curva es a derechas y valdrá cero si el robot se encuentra en una recta. El radio se indica en unidades de pies y está referido al margen interior de la curva.

• to_end: devuelve en cada momento la distancia que queda hasta el final del tramo en el que nos encontremos.

• to_lft, to_rgt: indican la distancia al extremo izquierdo y derecho de la calzada respectivamente. Son negativas si te sales de la carretera.

• v: es la velocidad que lleva el coche en cada instante. Sus unidades son pies por segundo.

• vn: es la componente normal de v. Es positiva si nos desplazamos a la izquierda y negativa si lo hacemos a la derecha.

• nex_rad: indica lo mismo que cur_rad pero sobre la curva siguiente al tramo en el que nos encontramos.

• dead_ahead: indica cuando tenemos un coche próximo con el cual puede darse una colisión. Detecta un obstáculo cercano con un ángulo de º20± .

• nearby: se trata de un array de estructuras que nos informará de la situación y comportamiento de los tres coches más cercanos en cada momento, por lo tanto su dimensión es tres. La estructura posee los siguientes parámetros:

1. who: devuelve un identificador del objeto detectado, el cual tiene que estar entre 0 y 15 para que sea un valor válido de un coche.

2. rel_x: es la distancia sobre el eje perpendicular a la dirección del coche, respecto al coche que tiene delante. Es positivo si lo detecta a la derecha y negativo a la izquierda.

3. rel_y: es la distancia en la dirección de la velocidad del coche, hasta el coche que tiene delante. Siempre es positiva puesto que no se detectan coches por detrás.

4. rel_xdot: indica la distancia relativa al coche detectado en el eje x. De esta forma si nuestro coche va segpies10 más rápido que el de enfrente, esta variable tomara el valor 10− .

5. rel_ydot: es igual que rel_xdot pero en la componente del eje y.

Hay más variables las cuales están explicadas en el anexo. NOTA: La componentes de distancia son en pies, las de velocidad en segpies , los ángulos

en radianes, y la longitud de un tramo esta en pies si es una recta y radianes si es una curva.

- Información del robot: programa de control

Una vez explicados los datos de entrada al robot, disponibles a través de la estructura situation, es necesario introducir estos datos al robot, el cual tomará en función de estos y del algoritmo utilizado, una decisión de salida. Esta se indicará mediante dos variables: vc (velocidad a transmitir) y alpha (grado de inclinación del coche).

A continuación detallamos las variables de salida: • vc: es la velocidad que se le imprime al coche a partir de la situación en la que se

encuentre y en la que se va a encontrar, teniendo en cuenta si nos encontramos en una curva, si esta es cerrada, si estamos en una recta, si el tramo siguiente es una curva, si estamos adelantando, etc.

• alpha: indica el grado de inclinación del coche, marcado por el que forman la velocidad y la dirección que lleva el coche, como quedo explicado anteriormente. Al igual que con vc, hay que tener en cuenta multitud de parámetros, sobre todo en las curvas, donde según el algoritmo el coche tendrá un comportamiento muy diferente, puesto que en las rectas este factor no influye en gran medida, salvo a la hora de adelantar o realizar algún giro brusco.

En un posterior apartado explicaremos con mayor detalle como hemos implementado estas dos variables según el algoritmo utilizado.

PROGRAMA DE CONTROL BÁSICO:

El código básico en el que nos hemos basado para implementar nuestro robot es el

mostrado en el Tutorial4, cuyo enlace es le siguiente http://rars.sourceforge.net/help.html .

El algoritmo que utiliza es muy básico, simplemente lo que hace es mantener el coche “pegado” al lateral de la calzada. Para ello utiliza la variable “lane” que hace que en las rectas se quede en la situación en la que se encuentra, y en las curvas se pegue al lado interno.

Nosotros hemos modificado este algoritmo como se explicará posteriormente, pero

básicamente lo que hacemos es hacer que el coche aproveche las rectas para abrirse y así poder afrontar las curvas con mayor ángulo y con el consiguiente aumento de velocidad y tracción.

En cuanto a la velocidad el algoritmo utilizado también es muy sencillo, simplemente

acelera en las rectas hasta llegar a una curva, donde calcula la velocidad de entrada en curva y lo mantiene a lo largo de esta. Nosotros también hemos mejorado este aspecto haciendo que la velocidad en curva vaya variando gradualmente según el coche va abandonando esta.

El tercer aspecto, y quizás el más importante a la hora de trazar una curva, es el ángulo

“alpha” de inclinación del coche respecto a su dirección. Para ello tiene en cuenta la posición en la que esta, y en la que debería estar, así saca el ángulo con el que girar el coche. A éste ángulo se le añade una componente “bias” que le hará aumentar en el caso de las curvas, para así poder trazar mejor. El problema de este algoritmo es que solo tiene en cuenta la curva en la que está para modificar este valor. Nosotros, en cambio, hemos realizado un algoritmo basado en un árbol de profundidad 3, es decir miramos la curva en la que estamos y las dos siguientes y en función de esto modificamos el ángulo de una forma u otra.

El último aspecto a tener en cuenta es como se afrontan las colisiones. Este algoritmo trata

de evitarlas bien, frenando si no tiene otra opción, o tratando de adelantar al coche que ha detectado por donde tenga espacio en la pista, pero no tiene en cuenta si la siguiente curva va a ser a un lado u otro. Puesto que siempre es conveniente coger el lado bueno de la pista, será conveniente adelantar por un lado u otro según convenga. Éste aspecto si lo tenemos en cuenta en nuestro código.

• FUNCIONAMIENTO DEL SIMULADOR (Display gráfico) Tras ejecutar el programa aparece una interfaz gráfica como se muestra en la siguiente

figura. Su manejo es sencillo a la par que elegante e intuitivo.

Podemos diferenciar los siguientes campos: En el margen izquierdo podemos seleccionar la pista (track), el número de vueltas (Laps),

el modo de visualización (OpenGL), etc. En la ventana de texto principal aparecen los datos de la pista seleccionada así como los

tiempos y velocidades de la última sesión en dicha pista. Por debajo de esta última ventana de texto aparecen otras dos, con los coches disponibles y

los coches seleccionados para la carrera, los cuales se van añadiendo con los botones correspondientes.

Una vez seleccionada la pista y los participantes, así el resto de opciones, se pulsa “Start

Race” y comienza la carrera.

Aparece el siguiente entorno gráfico:

Ahora ya podemos empezar a competir, solo hay que pulsar la tecla S, D o F según queramos que se ejecute menos o más rápidamente. También podemos cambiar el zoom con las teclas + y –, así como seleccionar un coche (AvPag, RePag) a seguir y pintar su trazada (T). Todo esto también se puede hacer desde el menú.

En la parte inferior de la pantalla se irán mostrando las velocidades de cada coche, así

como su posición y más datos a tener en cuenta (carburante, daños…).

NUESTRO ROBOT

1. ALGORITMO UTILIZADO Los algoritmos que se suelen utilizar para optimizar el código suelen ser algoritmos heurísticos

como la búsqueda A* o algoritmos de aprendizaje como algoritmos de prueba y error, algoritmos genéticos o redes neuronales.

Algunos de los coches que compiten en el Rars utilizan un búsqueda A* el cual se basa en una

algoritmo de Primero el mejor donde se utiliza una función de evaluación de cada nodo y se expande el nodo mejor evaluado no expandido. La idea es evitar expandir caminos que ya son muy costosos y alcanzar la solución óptima.

Otro de los algoritmos que se utilizan para la optimización es un algoritmo genético: algoritmo

de aprendizaje inductivo que considera el conjunto de reglas como una población de “pseudos-organismos”. Los organismos pueden: cruzarse unos con otros (operadores de cruce sexuales), o mutar y así producir nuevos elementos de la población (operadores de mutación) y la selección natural hace que sobrevivan los mejores individuos (operadores de selección). La función de evaluación congela el proceso si se alcanza el objetivo.

Si utilizas redes neuronales: estas son capaces de aprender la relación existente entre sus

entradas y salidas. El algoritmo que utilizamos nosotros es un árbol de decisión que tiene en cuenta el tramo en el

que está y los dos siguientes. A continuación pasamos a explicarlo en detalle: El algoritmo a utilizar tiene que considerar ante todo 5 aspectos:

� Posición del coche respecto a los laterales de la carretera � Velocidad del coche. � Ángulo de inclinación del coche. � Colisiones � Boxes

1.1 Posición del coche

1.1.1 Rectas

Cuando el coche se encuentra en una recta miramos si el siguiente tramo es una curva y en cuyo caso comprobamos si es a izquierdas o a derechas.

Si la curva es a derechas hacemos que el coche se vaya pegando poco a

poco a lo largo de recta hacia la izquierda de la pista, y si fuera a izquierdas se pegaría a la derecha.

Comprobamos en cada instante si la distancia al final de la recta es

suficiente como para poder frenar y entrar con la velocidad adecuada a la curva. Esta distancia la llamamos distancia de frenado en la cual el coche ira decrementando su velocidad además de su posición, puesto que lo iremos desplazando al interior para poder tomar la curva a más velocidad.

En las rectas comprobamos siempre que el coche no se salga de la calzada. Para ello dejamos un margen de seguridad en ambos lados entre los que se tiene que encontrar el coche. Este margen viene marcado por la constante MARGIN.

1.1.2 Curvas Las curvas son el tramo fundamental en las carreras. Es donde más tiempo

puedes ganar o perder, por tanto, el algoritmo tiene que tener en cuenta las múltiples posibilidades y casos de curvas. Para ello hemos optado por un algoritmo en forma de árbol con tres niveles, es decir, miramos el tipo de curva en el que estamos, el siguiente y el siguiente al siguiente. De esta forma determinamos como debe el coche entrar y salir de la curva, mientras que en el tramo central trata de estar lo mas pegado al interior de esta.

Además de mirar los tres niveles de profundidad dividimos la curva en tres

tercios: entrada, tramo medio y salida, así podemos variar la velocidad e inclinación del coche en cada parte de la curva de forma independiente procurando que sea lo más lineal posible y no realizar cambios bruscos en medio de la curva, lo cual provocaría pérdidas de tiempo y posibles accidentes.

Hemos creado una función llamada salidaCurva() que precisamente lo que

hace es mirar los tres niveles del árbol y así tomar la decisión (ir abriéndose o ir cerrándose) para poder afrontar las curvas de forma adecuada. Por ejemplo en una sucesión de curvas a la derecha el coche debería cerrarse más en la curva. Por el contrario si afronta una a la derecha seguida de una a la izquierda tiene que ir abriéndose a la salida de la primera para encarar de forma óptima la segunda.

1.2 Velocidad del coche

Para el cálculo de la velocidad también tomamos dos casos, que estemos en una

curva o que estemos en una recta.

1.2.1 Rectas En las rectas hay que tener en cuenta un parámetro fundamental que es la

distancia de frenado. En principio en una recta el coche podría ir a su velocidad máxima si no fuera porque al final de la recta hay una curva ante la cual el coche debe frenar para poder entrar sin salirse de ella.

Por tanto lo que hacemos es acelerar siempre. Cuando estemos en una

recta y todavía no hayamos llegado a su parte final (marcada por dicha distancia de frenado) donde el coche comienza a frenar (teniendo en cuenta la capacidad de frenado del coche en cada momento), afrontamos la curva teniendo en cuenta si la velocidad que lleva en ese instante es muy alta o moderadamente alta, para hacer un frenado más o menos brusco, incluso llegando a acelerar si fuera preciso, para ello primero calculamos la velocidad óptima en una curva según su radio:

kgradioVcurva **=

donde g es la gravedad en 2segpies y k una constante que indica la fuerza lateral sobre el coche.

1.2.2 Curvas

En las curvas la idea es la misma pero con ciertas modificaciones, así lo primero es calcular la distancia al final de la curva y ver si nos encontramos ya en la distancia de frenado (teniendo en cuenta que en una curva la capacidad de frenado del coche es menor que en la recta). En cada punto de la curva se calcula una teórica “velocidad siguiente” que es la que deseamos alcanzar en cada momento y vamos adaptando nuestra velocidad bien sea acelerando si se puede, o manteniendo la velocidad en caso contrario.

Para esto tenemos una variable llamada “tercio” que nos indica en que

tercio de la curva nos encontramos, de tal forma que en el primer tercio entra más despacio, en el segundo va manteniendo la velocidad y en el último tercio sale acelerando.

Hay que tener en cuenta que en las curvas el coche se encuentra con un

cierto grado de inclinación por lo tanto la velocidad tendrá que ir ponderada por el coseno de dicho ángulo.

1.3 Ángulo de inclinación del coche

Mediante el ángulo de inclinación (alpha) lo que conseguimos es posicionar el

coche con la inclinación suficiente como para afrontar un tramo del trazado, claramente este factor será determinante en curvas.

En general este ángulo tiene que ser proporcional a la diferencia entre, la

posición de la pista donde estamos y donde queremos estar, es decir, si queremos estar a 1m del margen derecho y estamos a 1.5m, el coche tendrá que cambiar su trayectoria en proporción a su diferencia (0.5m). Por otro lado también tiene que tener en cuenta la anchura de la calzada, puesto que si la anchura es alta, la inclinación será menor, por lo tanto, es inversamente proporcional a dicha anchura. Por otro lado también tiene que influir la velocidad a la que circula el coche y su componente normal. De esta forma si hay una componente normal muy grande el coche necesitará menos ángulo, pues la propia inercia le llevará al lado que quiere, siempre normalizado respecto a la velocidad del coche.

Estos aspectos son comunes tanto en rectas como en curvas, sin embargo hay

otro factor fundamental que depende del tramo en el que nos encontremos. Es un factor aditivo a este “alpha” llamado “bias” que proporciona una corrección sobre el primero puesto que en las curvas queremos que el ángulo de inclinación sea mayor para recortar la curva y por lo tanto ganar velocidad, es decir para conseguir una trazada correcta por curva (siempre suponemos que hablamos de un circuito de carreras, esto no se puede aplicar a la vida real pues hay carriles bien delimitados y te puedes estrellar ☺ ) acontinuación detallamos este ángulo:

1.3.1 Rectas En las rectas el “bias” debería mantenerse a cero por defecto, puesto que

el coche va paralelo a los laterales, pero distinguimos varias situaciones: si el coche está en una recta y no tiene un bias = 0 significa que sale de una curva o que lo ha modificado en algún adelantamiento, por lo tanto para que este factor no vuelva a cero de forma brusca y el coche de “cabezazos” detectamos si se encuentra en esta situación y decrementamos el bias poco a poco, sin ser cero directamente, esto lo realizamos en el inicio de la recta.

1.3.2 Curvas

En las curvas es donde este término cobra especial interés, y determina en gran medida el comportamiento del coche, en las cuales toma el siguiente valor:

bias =((s.v*s.v/(speed*speed)) * atan(BIG_SLIP /

speed) )+(1-(s.to_end /s.cur_len ))*salidaCurva(s); Como podemos observar, el ángulo es proporcional la velocidad que lleva

el coche pero ponderado por la velocidad calculada para el siguiente instante de tiempo. Si lleva una velocidad y se calcula que tiene que aumentar ésta, el ángulo disminuirá y viceversa. Por otro lado podemos calcular el ángulo como la arco tangente del ángulo formado por una constante (que indica una especie de derrapaje que a la vez marca la inclinación del coche) con la velocidad calculada, es decir se calcula mediante un triangulo imaginario cuyos catetos son por un lado la velocidad (tangencial a la trayectoria) y por otro el derrape (normal a la trayectoria).

El último sumando lo hemos diseñado ayudándonos de la función

salidaCurva(), la cual realiza una búsqueda en tres niveles según sea la curva actual y las dos siguientes, de esta forma determina si el coche ha de abrir su trayectoria en la curva o debe cerrarla, devolviendo unos coeficientes de modificación del “bias” que aumentarán el ángulo si se tiene que cerrar y lo disminuirá si se tiene que abrir. Estos coeficientes irán, por otro lado, ponderados por la distancia al final de la curva, de tal forma que cobran más importancia a la salida de la curva que a la entrada para que el coche trace de forma gradual la curva.

1.4 Colisiones Para evitar colisiones el rars dispone de la estructura nearby a través de la cual

podemos acceder a la distancia absoluta y distancia relativa de los tres coches más cercanos al nuestro mediante sus coordenadas. De esta forma podemos detectar cuando un coche está delante nuestro y puede provocar un golpe, y por que lado se va a producir este.

En primer lugar comprobamos si el o los coches que están a nuestro alrededor

se están acercando a nosotros, o nosotros a ellos, en cuyo caso se estima el punto de colisión y el tiempo en el cual se va a producir la colisión, pudiendo así computarlos ayudándonos de las dimensiones del coche y de la pista para decidir si es necesario frenar y/o esquivar a dicho coche.

Si tras estas comprobaciones decidimos que se va a producir una colisión entonces procedemos a tratar de evitarla atendiendo a, como en el resto de parámetros, si nos encontramos en una curva o en una recta.

1.4.1 Rectas

En rectas lo primero que hacemos es comprobar si la colisión se va a producir a nuestra izquierda o a la derecha, y una vez hecha esta realizamos una segunda comprobación que es si la siguiente curva es a izquierdas o a derechas. Si hay espacio suficiente para adelantar por el interior de la curva, sería lo óptimo y si no lo hay se adelanta por el exterior de la curva. El adelantamiento se realiza variando la separación del coche a los arcenes y aumentando o decrementando la velocidad según proceda.

1.4.2 Curvas

En curvas el algoritmo es similar, es decir, si hay espacio suficiente para adelantar por el interior se procede a ello y si no lo hay adelantamos por el exterior.

Para disponer de velocidad suficiente a la hora de adelantar aumentamos

esta un poco para poder realizar el adelantamiento lo antes posible aunque para ello se perjudica un poco la trazada y la estabilidad del coche.

1.5 Boxes

Cuando el coche se encuentra con un nivel bajo de gasolina o un nivel alto de daños se realiza la parada en boxes y se echa gasolina y se reparan los daños.

2. CÓDIGO DEL ROBOT //-------------------------------------------------------------------------- // I N C L U D E //-------------------------------------------------------------------------- #include <stdlib.h> #include <math.h> #include "car.h" //-------------------------------------------------------------------------- // D E F I N E S //-------------------------------------------------------------------------- // parameters to tinker with: // accelerations are in feet/second per second. // slips are in feet/second // distances are in feet const double CORN_MYU = 0.9;//1.00; // lateral g's expected when cornering const double BRAKE_ACCEL = -33.0; // acceleration when braking on straight const double BRAKE_SLIP = 6.5; // tire slip when braking const double BRK_CRV_ACC = -27.0; // acceleration when braking in curve const double BRK_CRV_SLIP = 3.5; // tire slip for braking in curve const double MARGIN = 10.0; // target distance from curve's inner rail const double MARGENIZQ = 8.0; //distancia al margen izquierdo const double MARGENDCH = 8.0; //distancia al margen derecho const double MARG2 = MARGIN+10.0; // target for entering the curve const double ENT_SLOPE = .33; // slope of entrance path before the curve const double STEER_GAIN = 1.0; // gain of steering servo const double DAMP_GAIN = 1.2; // damping of steering servo const double BIG_SLIP = 9.0; // affects the bias of steering servo const double CURVE_END = 4.0; // when you are near end of curve, widths const double TOO_FAST = 1.02; // a ratio to determine if speed is OK in curve const double DELTA_LANE = 2.5; // if collision predicted, change lane by this //A partir de aqui son nuestras variables double distfrenado = 0.0; //margen para haber cambiado de lado ante una curva double angulocd=0.0; //angulo para el cambio de lado ante una curva a derecha. double anguloci=0.0; //angulo para el cambio de lado ante una curva a izquierda. int izqdch=0; int rectainicio=0; double rdch=0.0; double rizq=0.0; static double lane; // target distance from left wall, feet double lane_was; static double lane0; // value of lane during early part of straightaway double tangente=0.0; int frena=0; int curva=0; double gira=0.0; double tercio=0.0; double bias=0.0; // added to servo's alpha result when entering curve double rec_lane=0.0; double rec_alpha=0.0; double acelera_curva=1.0; //-------------------------------------------------------------------------- // Class SofiaRaul

//--------------------------------------------------------------------------

//------------FUNCIONES QUE YA ESTABAN--------------------------------------- double corn_spd(double radius) // returns maximum cornering speed, fps {

// MUST NEVER CALL THIS ROUTINE WITH ZERO OR NEGATIVE ARGUMENT! return sqrt(radius * 32.2 * CORN_MYU); // compute the speed }

// Calculates the critical distance necessary to bring a car from speed // v0 to speed v1 when the braking acceleration is "a", ft per sec^2. // Speeds are in fps. ("a" should be negative) double CritDist(double v0, double v1, double a) {

double dv;

dv = v1 - v0; if(dv > 0.0) // this saves having such a test in the caller return(0.0); return (v0 + .5 * dv) * dv / a; }

//--------------------NUEVAS FUNCIONES--------------------------------------------- double cambioCarril(double anchura,double distancia) {

return atan(anchura/distancia); }

double salidaCurva(situation &s) {

double abrir= -0.50; double cerrar=-0.20; if(s.nex_rad ==0)//recta { /**********/ if(s.after_rad ==0)//recta {

return abrir; // (IZQ o DCH) RECTA RECTA // si estoy en una curva y los dos tramos siguientes son rectas }

else //estoy en curva y lo siguiente es una curva {

if(s.after_rad >0) ////estoy en curva y lo siguiente es una recta y luego curva a izq {

if(s.cur_rad <0) return abrir;// DCH RECTA IZQ return abrir; // IZQ RECTA IZQ

}else //curva derch

{if(s.cur_rad <0)

return abrir; // DCH RECTA DCHA return abrir; // IZQ RECTA DCHA }

}/**********/

} else // lo siguiente es una curva { if(s.nex_rad >0)//curva izq {

/********/ if(s.after_rad == 0) //recta {

if(s.cur_rad <0) return abrir; // DCHA IZQ RECTA return cerrar; // IZQ IZQ RECTA }

else {

if(s.after_rad >0)//curva izq {

if(s.cur_rad <0) return abrir; // DCHA IZQ IZQ return cerrar; // IZQ IZQ IZQ }

else //curva derch {

if(s.cur_rad <0) return abrir; // DCHA IZQ DCHA return cerrar; // IZQ IZQ DCHA }

}/*********/

}else //curva derch

{/*********/

if(s.after_rad ==0)//recta {

if(s.cur_rad <0) return cerrar; // DCHA DCHA RECTA return abrir; // IZQ DCHA RECTA

}else

{if(s.after_rad >0)//curva izq

{if(s.cur_rad <0)

return cerrar; // DCHA DCHA IZQ return abrir; // IZQ DCHA IZQ }

else //curva derch {

if(s.cur_rad <0) return cerrar; // DCHA DCHA DCHA return abrir; //IZQ DCHA IZQ }

}/*********/

}}

}

//----------ESTA SI ESTABA--------------------------------------------- con_vec SofiaRaul(situation &s) // This is the robot "driver" function: {

con_vec result = CON_VEC_EMPTY; // This is what is returned. double alpha, vc; // components of result double speed; // target speed for curve (next curve if straightaway) double speed_next = 0.0; // target speed for next curve when in a curve, fps. double width; // track width, feet double to_end; // distance to end of present segment in feet. static int rad_was = 0; // 0, 1, or -1 to indicate type of previous segment static double lane_inc = 0.0; // an adjustment to "lane", for passing

// service routine in the host software to handle getting unstuck from // from crashes and pileups: if(stuck(s.backward, s.v,s.vn, s.to_lft,s.to_rgt, &result.alpha,&result.vc)) return result;

width = s.to_lft + s.to_rgt; // compute width of track if ((s.cur_rad ==0)&&(rectainicio==0)) { distfrenado=0.15*s.cur_len ; angulocd = cambioCarril((width - s.to_rgt - MARGIN) ,(s.cur_len - distfrenado)); rdch=s.to_rgt ; anguloci = cambioCarril((width - s.to_lft - MARGIN) ,(s.cur_len - distfrenado)); rizq=s.to_lft ; rectainicio=1;

}

// This is a little trick so that the car will not try to change lanes // during the "dragout" at the start of the race. We set "lane" to // whatever position we have been placed by the host. if(s.starting) // will be true only once lane = lane0 = s.to_lft; // better not to change lanes during "dragout"

// Set "lane" during curves. This robot sets "lane" during curves to // try to maintain a small fixed distance to the inner rail. if(s.cur_rad > 0.0) // turning left {

if(s.to_end >((2*s.cur_len) /3))//primer tercio {

lane = MARGIN; tercio=0; rec_alpha=0;

}else

{if(s.to_end >(s.cur_len /3))//segundo tercio

{lane = MARGIN;

tercio=0.2; rec_alpha=0; }

else//tercer tercio {

lane = MARGIN; tercio=1.3; rec_alpha=0; }

}lane_was=lane;

rad_was = 1; // set this appropriate to curve. rectainicio = 0; izqdch=0; curva=1; frena=0; } else{

if(s.cur_rad < 0.0) // turning right {

if(s.to_end >((2*s.cur_len) /3))//primer tercio {

lane = width - MARGIN; tercio=0; rec_alpha=0;

}else

{if(s.to_end >(s.cur_len /3))//segundo tercio

{lane = width-MARGIN;

tercio=0.2; rec_alpha=0; }

else//tercer tercio {

lane = width-MARGIN; tercio=1.3; rec_alpha=0; }

}lane_was=lane;

rad_was = -1; // set this appropriate to curve. rectainicio = 0; izqdch=0; curva=1; frena=0; }

else // straightaway: {

// We will let the car go down the straigtaway in whatever "lane" it // comes out of the turn. // If we just came out of a turn, then: if(curva==0) {

if(s.nex_rad >0) {

if(lane<width) lane=lane*1.01; }

else {

if(lane>MARGIN) lane=lane*0.99;

}}

if(curva==1) //indica que ya se ha tomado una curva {

/**/ if(s.nex_rad < 0.0) //curva a la dcha {

izqdch=1; lane=MARGIN+tan(anguloci)*(s.to_end-distfrenado) ; if(s.to_end > 0.90*s.cur_len ) {

lane=lane_was; lane_was =lane*0.7; }

if(s.to_end < distfrenado) {

if(frena==0) {

tangente=tan(cambioCarril(0.4*width-s.to_lft,s.to_end)); frena=1; }

lane=0.4*width-(s.to_end *tangente); if(lane < 0.9*(width-MARGIN)) {

lane=lane+8; rec_alpha=1; }

}

}else

{

if(s.nex_rad > 0.0) //curva a la izq {

izqdch=2; tangente=tan(angulocd); lane=width-(MARGIN+tangente*(s.to_end-distfrenado)) ; if(s.to_end > 0.90*s.cur_len ) {

lane=lane_was; lane_was =lane*1.3; }

if(s.to_end < distfrenado) {

if(frena==0) {

tangente=tan(cambioCarril(0.4*width-s.to_lft,s.to_end)); frena=1; }

lane=width-(0.6*width+(s.to_end *tangente ) ); if(lane > 1.1*(MARGIN)) {

lane=lane-8; rec_alpha=1; }

}}

}/**/

}else //esoy y estaba en una recta

{if (izqdch==1)

{lane =MARGIN + rizq + (sin(anguloci)*(s.cur_len -

s.to_end)); }

if(izqdch==2) {

lane =width - (sin(angulocd)*(s.cur_len - s.to_end) + rdch )-MARGIN; }

}lane_was=lane;

rad_was = 0; }

}if (s.to_lft<MARGIN)

{ lane=lane*1.2; } if (s.to_rgt>(width-MARGIN)) { lane=lane*0.8; } // This is for the transition from straight to left turn. If we are // in a transition zone near the end of the straight, then set lane to // a linear function of s.to_end. During this zone, "lane" will change // from "lane0" upon entering the zone to MARG2 upon reaching the end // of the straightaway. ENT_SLOPE is the change in lane per change in // s.to_end. // if(s.to_end < (lane0 - MARG2) / ENT_SLOPE) { // lane = MARG2 + ENT_SLOPE * s.to_end;

// set the bias: // Bias is an additive term in the steering servo, so that the servo // doesn't have to "hunt" much for the correct alpha value. It is an // estimate of the alpha value that would be found by the servo if there // was plenty of settling time. It is zero for straightaways.

// Also, for convenience, we call the corn_spd() function here. On // the straightaway, we call it to find out the correct speed for the // corner ahead, using s.nex_rad for the radius. In the curve we of // course use the radius of the curve we are in. But also, we call it // for the next segment, to find out our target speed for the end of // the current segment, which we call speed_next. if(s.cur_rad == 0.0) {

if(bias != 0.0) {

bias= bias*0.6; }

if (s.to_end <0.6*s.cur_len ) {

bias = 0.0; }

if(s.nex_rad > 0.0) speed = corn_spd(s.nex_rad + MARGIN); else if(s.nex_rad < 0.0) speed = corn_spd(-s.nex_rad + MARGIN); else

speed = 250.0; // This should not execute, for a normal track file

//speed=1.1*speed; } else // we are in a curve: { if(s.nex_rad == 0.0) speed_next = 250.0; else

speed_next = corn_spd(fabs(s.nex_rad) + MARGIN); speed = corn_spd(fabs(s.cur_rad) + MARGIN + fabs(lane_inc)); speed = speed + 0.25*tercio*speed; bias =( (s.v*s.v/(speed*speed)) * atan(BIG_SLIP / speed) )+(1-(s.to_end /s.cur_len ))*salidaCurva(s);//+tercio*salidaCurva(s); if(s.cur_rad < 0.0) // bias must be negative for right turn bias = -bias; }

// set alpha: (This line is the complete steering servo.) alpha = STEER_GAIN * (s.to_lft - lane)/width - DAMP_GAIN * s.vn/s.v + bias;//+0.05*rec_alpha;//+(1.3-tercio); // set vc: if(s.cur_rad == 0.0) // If we are on a straightaway, { // if we are far from the end, distfrenado=CritDist(s.v, speed, BRAKE_ACCEL+10); distfrenado=0.25*s.cur_len *distfrenado; if(s.to_end > CritDist(s.v, speed, BRAKE_ACCEL)) vc = s.v + 50.0; // pedal to the metal! else // otherwise, adjust speed for the coming turn: {

if(s.v > TOO_FAST * speed) // if we're a little too fast, vc = s.v - BRAKE_SLIP; // brake hard. else if(s.v < speed/TOO_FAST) // if we're a little too slow,

vc = 1.2 * speed; // 1.1 accelerate hard. else // if we are very close to speed, vc = .5 * (s.v + speed); // approach the speed gently. }

}else // This is when we are in a curve: (seek correct speed)

{// calculate distance to end of curve:

if(s.cur_rad > 0.0) to_end = s.to_end * (s.cur_rad + MARGIN); else

to_end = -s.to_end * (s.cur_rad - MARGIN); // compute required braking distance and compare: // This is to slow us down for then next curve, if necessary: if(to_end <= CritDist(s.v, speed_next, BRK_CRV_ACC)) vc = s.v - BRK_CRV_SLIP; // but if there is a straight, or a faster curve next, then // we may want to accelerate: else if(to_end/width < CURVE_END && speed_next > speed) vc = 0.9 * (s.v + speed_next)/cos(alpha); else // normally, just calculate vc to maintain speed in corner vc = 0.9 * (s.v + speed)/cos(alpha); }

// Passing and anti-collision code: // This code first tries to predict a collision; if no collision is // predicted, it does nothing. Collision prediction is approximate, and // is based on linear extrapolation. This can work because it is // repeated eighteen times per second of simulated time. // If a collision is predicted, then it gradually changes the // lane_inc static variable which changes alpha. // The hope is to steer around the car. When no collision is // predicted then lane_inc is gradually brought back to zero. // If a crash is about to occur, medium hard braking occurs. double x, y, vx, vy, dot, vsqr, c_time, y_close, x_close; int kount; // counts cars that are in danger of collision kount = 0; acelera_curva=1.0; for(int i=0;i<3;i++) if (s.nearby[i].who<16) // if there is a close car { y=s.nearby[i].rel_y; // get forward distance (center-to-center) x=s.nearby[i].rel_x; // get right distance vx=s.nearby[i].rel_xdot; // get forward relative speed vy=s.nearby[i].rel_ydot; // get lateral relative speed // if the cars are getting closer, then the dot product of the relative // position and velocity vectors will be negative. dot = x * vx + y * vy; // compute dot product of vectors if(dot > -0.1) // no action if car is not approaching. continue;

vsqr = vx*vx + vy*vy; // compute relative speed squared // Time to closest approach is dot product divided by speed squared: c_time = -dot / vsqr; // compute time to closest approach if(c_time > 3.0) // ignore if over three seconds continue;

/* If the execution gets this far, it means that there is a car ahead of you, and getting closer, and less than 3.0 seconds away. Evaluate the situation more carefully to decide if evasive action is warranted: */

x_close = x + c_time * vx; // x coord at closest approach y_close = y + c_time * vy; // y coord at closest approach /* Due to the length of the cars, a collision will occur if x changes sign while y is less than CARLEN. This can happen before the center-to-center distance reaches its point of closest approach. */

// check if collision would occur prior to closest approach // if so, reduce c_time, re-calculate x_close and y_close: if(x_close * x < 0.0 && y < 1.1 * CARLEN) {

c_time = (fabs(x) - CARWID) / fabs(vx); x_close = x + c_time * vx; // x coord at closest approach y_close = y + c_time * vy; // y coord at closest approach }

// Will it be a hit or a miss? if(fabs(x_close) > 2 * CARWID || fabs(y_close) > 1.25 * CARLEN) continue; // this when a miss is predicted // If we get here there is a collision predicted ++kount; // This counts how many cars are in the way. if(kount > 1 || c_time < .85) // if more than one problem car, or if vc = s.v - BRK_CRV_SLIP; // car within .85 sec of collision, brake!

// steer to avoid the other car: // if there is room, we try to pass with least x deviation if(s.cur_rad > 0.0){ if(x_close < 0.0 || s.to_lft < MARGIN) {// avoid scraping the inside if(s.to_lft>((-1.2*x_close)+MARGIN+CARWID)) {

lane_inc-=1.5*DELTA_LANE; acelera_curva=1.3; }

else {

lane_inc += DELTA_LANE; acelera_curva=1.3; }

}else {

lane_inc -= DELTA_LANE; acelera_curva=1.3; }

}else

{if(s.cur_rad < 0.0)

{if(x_close > 0.0 || s.to_rgt < MARGIN)

{if(s.to_rgt>(1.2*x_close+MARGIN+CARWID))

{lane_inc+=1.5*DELTA_LANE;

acelera_curva=1.3; }

else {

lane_inc -= DELTA_LANE; acelera_curva=1.3; }

}else

{lane_inc += DELTA_LANE;

acelera_curva=1.3; }

}else

{if(x_close < 0.0)

{// on straights, pass with least x deviation if((s.nex_rad>0.0) && (s.to_lft>((-1.2*x_close)+MARGIN+CARWID)) && (s.to_end>2*CARLEN)) {

lane_inc-=1.5*DELTA_LANE; }

else {

lane_inc += DELTA_LANE; }

}else

{if((s.nex_rad<0.0) &&

(s.to_rgt>((1.2*x_close)+MARGIN+CARWID)) && (s.to_end>2*CARLEN)) {

lane_inc+=1.5*DELTA_LANE; }

else {

lane_inc -= DELTA_LANE; }

}}

}if(lane_inc > .25 * width)

{// limit the lane alteration to 1/4 width: lane_inc = .25 * width; }

else {

if(lane_inc < -.25 * width) {

lane_inc = -.25 * width; }

}

}

// Here we gradually reduce lane_inc to zero if no collision is predicted: if(!kount) if(lane_inc > .1) lane_inc -= .5*DELTA_LANE; else if(lane_inc < -.001) lane_inc += .5*DELTA_LANE;

// lane_inc represents an adjustment to the lane variable. This is // accomplished by changing alpha an amount equal to that which the

// steering servo would have done had lane actually been changed. result.vc =vc*acelera_curva; result.alpha = alpha - STEER_GAIN * lane_inc / width;

// Pit: if the fuel is too low // Fuel: full // Damage: repair all if( s.fuel<10.0 ) {

result.request_pit = 1; result.repair_amount = s.damage; result.fuel_amount = MAX_FUEL; }

return result; }