In order to minimize the accidents, autonomous vehicles are being designed as the future of transportation. To fulfill this goal, we should look at vehicular intersections, where unfortunately most car accidents take place. In “Automation of a T-intersection using virtual platoons of cooperative autonomous vehicles”, the algorithm called “Target Vehicle Assignment(TVA)” was proposed to resolve the problem of deciding an order in which vehicles cross in a 4-way intersection. This article reviews this algorithm and uses it as starting point to propose novel algorithms that fix issues detected in the original algorithm. The newly proposed algorithms are designed to be used with Vehicle To Vehicle (V2V) communications and are descentralized to avoid dependency of specific hardware in any intersection. Keywords: Autonomous vehicles, autonomous intersection management, vehicular intersection control algorithms.
Cuando se tiene una intersección y existen varios
vehículos que quieren cruzar, se debe coordinar de
forma que los vehículos que crucen la intersección al
mismo tiempo no crucen sus trayectorias. Hoy en día
comúnmente se utilizan señaléticas o semáforos para
realizar esta coordinación, pero en el futuro próximo
se espera que los automóviles se comuniquen entre sí,
para establecer una coordinación mediante algoritmos
como los presentados en [
Si los vehículos se pueden comunicar dentro de los márgenes de una zona de cooperación (CZ del inglés Cooperation Zone) entonces se pueden definir algoritmos de coordinación que tomen información de los vehículos (como posición, velocidad, vehículos existentes en la CZ, etc), y definir cierto orden que asegure una intersección libre de colisiones.
2.1.
Algoritmo con Caravanas Virtuales (CV)
El primer algoritmo a analizar es el algoritmo de
Asignación de vehículo objetivo (Target Vehicle
Assignment) [
Data: v: Vehículo nuevo, L: Lista de vehículos viejos. Result: id: Identificador del vehículo a seguir. ordenaP orT poIngreso(L);//más nuevo al más viejo for v′ L do if cruzanCaminos(v; v′) then
return id(v′)
end
end
Algoritmo 1: Algoritmo TVA con caravanas [
En el trabajo donde se propone este algoritmo, se utilizan técnicas de collission avoidance para evitar estas colisiones. Sin embargo, en nuestra opinión, una mejor estrategia es diseñar métodos de asignación de cruce que eviten esto desde el inicio. 2.2.
Algoritmo con CV Mejorado
En vista del que el algoritmo anterior provoca colisiones, una posible mejora consiste en ordenar los vehículos de manera distinta, como se muestra en el algoritmo 2. Comparado con el algoritmo 1, aquí se agrega el factor de orden por profundidad en la caravana.
Data: v: Vehículo nuevo, L: Lista de vehículos viejos en la intersección Result: id: Identificador del vehículo a seguir ordenaP orT poIngreso(L);//más nuevo al más viejo ordP orP rof EnCarav(L);//de + a profundidad for v′ L do if cruzanCaminos(v; v′) then
return id(v′) end end
Algoritmo 2: Algoritmo TVA [
Con esa mejora, para el ejemplo anterior se obtiene una simulación como la que se ve en el cuadro 2. La única diferencia está en que V5 debe seguir ahora el vehículo V3, puesto que al calcular el nuevo orden, es el primer vehículo con el cual choca V5. Con esto la caravana queda como se ve en la Figura 2, evitando así la colisión que se presentó con el algoritmo anterior. Id V1 V2 V3 V4 V5 s 300 e n io200 s i l oC100 0
V4
V2 V1
V3
V5
Figura 2: Caravana formada con la primera mejora 3.
Los resultados que se ven en la Figura 3 dejan ver que la primera mejora disminuyó considerablemente la cantidad de colisiones, sobre todo cuando se aumenta la distancia mínima que tiene que haber entre los vehículos. Sin embargo, las colisiones no fueron eliminadas por completo.
Alg. Mejora No1 5
7 9 Distancia entre vehículos 11
Figura 3: Cantidad de colisiones variando distancia 4.
Dado que la mejora propuesta no soluciona el problema de colisiones, se proponen nuevos algoritmos que ahora toman en cuenta otros factores, tales como la velocidad del vehículo que ingresa, su posición, su distancia hasta la intersección y su tiempo dentro de la intersección.
Cabe destacar que si tenemos los vehículos de la Figura 4, podemos saber que V1 cruza trayectoria con V2 y V3, pero que entre ellos no cruzan trayectorias. Sin embargo, no podemos decir nada con respecto a la relación de cruce que existe entre V2 y V4 ó V1 y V4, ya que las relaciones descritas por “chocar” o “no chocar” no son transitivas.
V1
V3 V2
V4
Propuesta 1: Caravanas FIFO sin colisión Este algoritmo se basa en el anterior, pero además revisa si hay colisiones en las N potenciales caravanas. La descripción del algoritmo 3 asume que existe un árbol que guarda la información de las caravanas (vehículos ya asignados, jerarquía de seguimiento y tiempo de cruce asignado de cada vehículo).
Data: v: Vehículo nuevo, AC: Árbol de caravanas Result: vf : vehículo a seguir vehsQueCruza ; for Carav AC do for v′ Carav do if cruzanCaminos(v; v′) then
vehsQueCruza:append(v′); break; end end end vf vehM axT poDeCruce(vehsQueCruza); v:tpoCruce calcT poCruce(v); return vf
Algoritmo 3: Algoritmo de caravanas FIFO
Si bien no lo hemos demostrado formalmente, conjeturamos que este algoritmo está libre de colisiones. Un potencial problema es su eficiencia en el peor caso: cuando el vehículo que ingresa no cruza trayectoria con ningún otro, se debe comparar con todos los vehículos en la CZ. Dado que esto ya ocurre en el caso anterior (cuando hay sólo una caravana y no cruza trayectoria con ningún otro vehículo) su impacto es menor. Por otro lado, este algoritmo es conservador y asegura un orden FIFO, lo cual no siempre es óptimo. Concretamente, obliga a vehículos a siempre esperar a que el que entró primero salga primero, aun cuando podrían haber cruzado sin riesgo a colisión. 4.2.
Propuesta 2: Bloques de Tiempo
A fin de optimizar el algoritmo anterior en relación al tiempo de espera de los vehículos, permitimos a los vehículos ingresar en un orden no FIFO y así optimizar los tiempos de cruce y de espera. Se definen dos propiedades de los vehículos: origen y dirección. El primero es el lugar de donde viene el vehículo: Norte, Sur, Este u Oeste. La dirección que corresponde a la intención:“seguir derecho”, “doblar a la derecha”, “doblar a la izquierda” o “todos”1. Esto entrega 16 combinaciones distintas. La estructura de datos para este algoritmo consiste en 16 arreglos de tipo bool, uno para cada combinación. Cada arreglo asociado a una tupla <origen, dirección> representa el tiempo dividido en bloques, y el bloque k ésimo es verdadero si existe un vehículo que intenta cruzar la intersección en el tiempo k con el origen y destino indicados. El Algoritmo 4 define esta propuesta.
1La dirección “todos” se reserva para los casos donde hay algún vehículo en el mismo carril (mismo origen) y así poder calcular el tiempo mínimo de llegada tomando en cuenta vehículos que antecedan al vehículo que va ingresando.
Data: v: Vehículo nuevo, AB[ori][dir][tpo]: Arreglos de bloques de tiempo Result: bs: bloques de tiempo para cruzar tml tpoM inLlegadaIntersect(v); ti getT poInterseccion(v); arrsCol getArreglosColision(v); arrCol mergeArreglosColision(arrsCol); kBloques getBloquesDisponibles(arrCol; v); for k kBloques do
AB[v:ori][v:dir][k] true;
AB[v:ori][“todos”][k] true; end return kBloques
Algoritmo 4: Algoritmo de bloques de tiempo El tiempo mínimo de llegada a la intersección corresponde al tiempo que demora el vehículo en llegar hasta la intersección tomando en cuenta factores como la velocidad máxima y los vehículos que lo anteceden. Por otro lado, la función getArreglosColision retorna a todos los arreglos AB[orig′][dir′] que correspondan a orígenes y direcciones que crucen la intersección con el vehículo que va ingresando. La función mergeArreglosColision realiza un OR (“o lógico”) entre los bool, así obteniendo un sólo arreglo donde hay T rue sólo en los bloques donde pasan vehículos con los cuales se colisiona.
Por la forma en que se asignan los bloques de tiempo-espacio, conjeturamos que el algoritmo propuesto es optimal greedy. 5.
El algoritmo original presentado por Medina2015 [
En un futuro trabajo se buscará verificar la
correctitud de manera teórica y experimental de los algoritmos
propuestos. Para ello, se utilizará tanto en el
framework especializado diseñado Holloway16 [
Este proyecto ha sido financiado a través del NIC Chile Research Labs, el proyecto “RETRACT” ELAC 2015/T10-0761 y el Instituto de Sistemas Complejos de Ingeniería, ISCI (CONICYT: FB0816).