Navegación autónoma (II): predicción de trayectoria
Rubén Rodríguez Abril
Los algoritmos de predicción transforman el rastreo pasado de objetos en un haz de trayectorias futuras probables. Se articulan en tres arquitecturas principales: grafos dinámicos (Trajectron++), que modelan interacciones entre agentes; polilíneas (VectorNet), que representan trayectorias y mapa como vectores; y transformers (Wayformer), que procesan escenas completas con mecanismos atención muy parecidos a los de las LLMs. Esta información de esta capa alimenta la navegación reactiva para evadir o perseguir objetos.
Introducción
Los algoritmos de predicción de trayectoria se encargan de anticipar el comportamiento de los objetos de una determinada escena, próximos al vehículo. A partir de los datos proporcionados por el sistema de rastreo —que ya fue objeto de otro artículo de esta serie—, estiman su evolución dinámica y generan una o varias trayectorias futuras, a las que pueden asignar una probabilidad.
Podemos representar este proceso mediante un espacio de estados cinemáticos ampliado, formado por las coordenadas espaciales y el tiempo. Cada objeto queda definido por un vector de estado que contiene su posición y, en los modelos más completos, su velocidad, aceleración y otras variables relevantes. Su evolución dibuja en este espacio una trayectoria espacio-temporal.
Hacia el pasado, el rastreo reconstruye la trayectoria a partir de las observaciones proporcionadas por los sensores:
x(t0),x(t1),x(t2),x(t3),…
Hacia el futuro, la trayectoria observada se abre en un haz de trayectorias posibles, cada una con una probabilidad asociada. Conforme aumenta el horizonte temporal, aumenta también la dispersión entre ellas y la incertidumbre de la predicción.
Los sistemas de predicción se articulan en diferentes categoría, según su tipología: basados en grafos, en polillíneas y en transformers.
Sistemas basados en grafos: G(V,E)
La red recibe como entrada un grafo en el que los nodos son los agentes que aparecen en escena —vehículos, peatones, ciclistas, etc.—, mientras que las aristas representan las posibles interacciones entre ellos. El grafo es dinámico: las aristas aparecen o desaparecen conforme los agentes entran o salen de sus respectivos radios de interacción.
Uno de los primeros modelos que utilizaron este paradigma fue Trajectron++, cuya arquitectura se compone de un codificador y un descodificador. El primero procesa la escena y genera una representación interna a partir de la cual se obtiene una variable latente z, mientras que el segundo utiliza esta información para generar las coordenadas futuras de un agente. El proceso se ejecuta para cada uno de los agentes cuya trayectoria se desea predecir, compartiendo los parámetros del modelo entre agentes de la misma clase. El agente observador se denomina vehículo ego.
La codificación tiene lugar del siguiente modo:
La trayectoria reciente del nodo o agente cuya posición se desea predecir es procesada por una LSTM.
Las interacciones del vehículo observado (cuyo comportamiento queremos predecir) con los demás agentes se agrupan por tipo. En cada instante, los vectores de posición relativa correspondientes a agentes de una misma clase se suman y la secuencia resultante es procesada por otra LSTM (red recurrente que ya hemos examinado en un artículo específico). Así, los estados de los peatones que interactúan con el agente se agregan entre sí; lo mismo sucede, separadamente, con los vehículos, incluido el vehículo ego cuando interactúa con el agente. Las representaciones obtenidas para los distintos tipos de interacción se combinan posteriormente mediante un mecanismo de atención.
El modelo incorpora además el futuro previsto del vehículo ego (Robot Future). Esta trayectoria no es generada por Trajectron++, sino proporcionada externamente por el motion planner como un posible plan de movimiento. El predictor puede así estimar no sólo qué harán los demás agentes a partir de su comportamiento observado, sino también cómo podrían reaccionar si nuestro propio vehículo ejecutase una determinada maniobra. Distintos movimientos candidatos del ego permiten obtener predicciones condicionadas diferentes.
Toda esta información se combina en una representación ex,R.
Junto a ella, el modelo debe determinar un modo de comportamiento dinámico para el agente, representado mediante una variable latente z. La necesidad de esta segunda variable se debe a que un mismo estado observado puede dar lugar a comportamientos diferentes. Un vehículo que se aproxima lentamente a una intersección puede continuar su marcha, detenerse o iniciar un giro; su posición, velocidad y relaciones con los demás agentes no determinan necesariamente cuál de estos futuros se producirá. La variable z permite representar estas diferentes posibilidades.
Una capa plenamente conectada toma ex,R y calcula una distribución de probabilidad sobre los 25 valores que puede adoptar z:
pθ(z|x,M,yR)
Sobre esta distribución se realiza un muestreo (sampling) que selecciona uno de los futuros dinámicos posibles. El muestreo permite abandonar una representación estrictamente determinista del movimiento: un mismo estado de la escena no conduce necesariamente a un único futuro. Siempre existirá un determinado grado de incertidumbre.
Figura 1. Esquema de Trajectron ++. Esta instancia concreta trata de predecir el comportamiento del coche 1, situado en el centro de la imagen. La escena es representada por un grafo, en el que cada elemento es un nodo. Las interacciones del coche 1 con el resto de vehículos son representadas por aristas. Nodos y aristas tienen LSTMs dedicados que transforman sus coordenadas en estados internos. Una red convolucional transforma la estructura geométrica de la imagen en un estado interno. En rosa, un LSTM transforma la trayectoria prevista para el agente-ego en un estado interno. En naranja, el comportamiento del nodo observado, que sólo se usa durante parte del entrenamiento, y no durante la inferencia. Por último, el descodificador, que predice las futuras coordenadas del agente observado, se representa en verde. Fuente: Trajectron++.
La segunda parte del algoritmo, el descodificador, produce como salida el estado dinámico del vehículo yt, y toma como entrada la representación de la escena, el modo dinámico, y el estado inmediatamente anterior yt-1. El núcleo del descodificador es una red recurrente GRU, que también se examina brevemente en el artículo correspondiente.
La segunda parte del algoritmo, el descodificador, genera sucesivamente los estados futuros del vehículo yt+1,yt+2,…. Toma como entrada la representación de la escena ex,R, el modo dinámico z y, en cada paso, el estado inmediatamente anterior yt. El núcleo del descodificador es una red recurrente GRU, que también se examina brevemente en el artículo correspondiente.
Sistemas basados en polilíneas {P1,….,PM}
En VectorNet y otros sistemas análogos, tanto las trayectorias observadas de los agentes como los elementos del mapa —carriles, bordes de calzada, pasos, etc.— se representan mediante polilíneas, compuestas de pequeños vectores/segmentos. La arquitectura aprende primero una representación de cada polilínea y después las relaciones globales entre ellas. A partir de ellas, se prolongan hacia el futuro las trayectorias de agentes móviles.
Figura 2. Los vectores se ensamblan en polilíneas. VectorNet predice los futuros vectores de la polilínea verde, correspondiente a la trayectoria de un agente móvil. Fuente: VectorNet.
El flujo de información a lo largo del algoritmo es el siguiente:
Vectores
Cada vector/segmento tiene la estructura siguiente:
Vi = [dsi,dei,ai,j]
donde dsi y de son las coordenadas de los puntos de origen y fin del vector, ai corresponde a los atributos del objeto (como tipo de vehículo, clase de carretera o sellos de tiempo para trayectorias) y j la id del objeto.
Polilíneas
A partir de estos vectores se obtiene la representación de cada polilínea. Así los vectores pertenecientes a una misma polilínea se ensamblan en una matriz y se hacen pasar por una capa lineal, seguida de normalización y una función ReLU. A continuación, se calcula el max-pooling sobre todos ellos, obteniendo un vector que resume globalmente la polilínea. Este vector se concatena con la representación individual de cada uno de sus vectores, duplicando así su dimensión.
Matricialmente, el algoritmo se expresaría así:
Xi = concat(lineal(Vi),max-pooling(lineal(Vi))
donde Xi son los vectores de la matriz de salida de la capa.
El proceso puede repetirse durante varias capas. En cada una, los vectores conservan su información individual, pero incorporan además la información global obtenida de la polilínea en la capa anterior.
Finalmente, una última capa de max-pooling la matriz X en un único vector pi que representa a la polilínea:
P = max-pooling(X)
Figura 3. Esquema del funcionamiento de cada capa del codificador. Los vectores que componen una polilínea se procesan individualmente mediante una capa lineal, seguida de normalización y ReLU (en azul). A continuación, se realiza un max-pooling entre todos ellos. El vector de pooling resultante se concatena con cada uno de los vectores individuales, duplicando así su dimensión. Fuente: VectorNet.
Escena al completo
La escena al completo se representa como un grafo global completamente conectado, en el que cada nodo corresponde a una polilínea y está conectado con todos los demás. Los vectores pi se agrupan en una matriz de polilíneas P.
Sobre esta matriz P se aplica un mecanismo de atención:
donde P es la matriz de polilíneas. La expresión de la derecha es similar al introducido por el célebre artículo Vaswani et al (2017), con el que se inauguró la arquitectura Transformer.
La atención hace que cada polilínea incorpore información procedente de las demás. Por ejemplo, la representación de la trayectoria del coche objetivo puede incorporar información de su carril, de otro coche, de una intersección, etc.
Cada vector obtenido a la salida del mecanismo de atención sigue representando una polilínea, pero ahora incorpora información del resto de la escena. En el caso de las polilíneas correspondientes a agentes móviles y sus trayectorias (en la Figura 2 están representados en verde), este vector se hace pasar por un descodificador, consistente en un perceptrón multicapa, que predice los desplazamientos espaciales del agente para una serie de instantes futuros:
Donde i es el índice de la polilínea, pi es su representación (es decir, un vector) en la salida del mecanismo de atención, φtraj es el descodificador y vi el desplazamiento de las coordenadas en el futuro. Para un espacio bimensional, el vector vi tiene 2N componentes, donde N es la cantidad de instantes de tiempo que predice el descodificador.
Sistemas basados en transformers/tokens
Un enfoque diferente fue desarrollado por Waymo Research, el mismo laboratorio responsable de VectorNet. Wayformer aborda el problema mediante una arquitectura basada en transformers, utilizando mecanismos de atención para modelar las relaciones espaciales y temporales entre los distintos elementos de la escena.
Los elementos de la escena se clasifican en cuatro categorías, cada una de las cuales se representa mediante un tensor de cuatro dimensiones:
Historial del agente objetivo (Agent History): codifica el estado dinámico de cada agente a lo largo del tiempo.
Interacciones de agentes (Agent Interactions): codifican las características de los agentes vecinos de cada agente objetivo. Puede entenderse como una matriz por agente y por instante, agrupadas conjuntamente en un tensor.
Mapa (Roadgraph): codifica los elementos de la infraestructura viaria próximos al agente, como carriles, bordes de calzada o pasos.
Semáforos (Traffic Lights): codifica la posición y el estado de los semáforos próximos a cada agente a lo largo del tiempo.
Las cuatro modalidades contienen características diferentes y presentan, por tanto, distintas dimensiones. Para homogeneizarlas, Wayformer hace pasar los elementos de cada tensor por una capa lineal seguida de una función ReLU:
x’m = ReLU(Wmxm + bm)
De este modo, las dimensiones originales Dh, Di, Dr, Dtls se transforman en una dimensión común D:
Los estados de los agentes, los elementos del mapa y los semáforos quedan así representados mediante vectores de la misma dimensión, que pueden ser procesados conjuntamente por los mecanismos de atención.
Figura 4. Los datos referidos a semáforos, carretera, historial de agentes e interacciones de agentes se codifican en cuatro tensores que, una vez proyectados a una dimensión común, entran en el codificador de escena, que tiene arquitectura transformer.
Codificador de escena
Ahora bien, Wayformer estudia tres formas diferentes de introducir y combinar esas cuatro modalidades en el codificador:
Early Fusion: se concatenan las cuatro modalidades antes del Transformer. El codificador recibe conjuntamente todos los elementos de la escena y la autoatención puede establecer desde el principio relaciones entre cualquiera de ellos.
Late Fusion: cada modalidad se procesa inicialmente de manera independiente mediante su propio encoder. La información sólo se combina posteriormente, en el Trajectory Decoder.
Hierarchical Fusion: solución intermedia. Cada modalidad recibe primero un procesamiento específico y las representaciones resultantes se combinan después mediante un encoder común.
La salida del codificador de escena es la matriz de escena que captura todo el contenido semántico de la misma relacionado con semáforos, trayectoria, agentes y relaciones entre ellas. La segunda entrada es un conjunto de semillas (seeds).
Descodificador
La entrada del descodificador es doble: la matriz de escena y las semillas dinámicas, que es una colección de vectores aprendidos que representan distintos modos dinámicos de movimiento (tipos de comportamiento) del vehículo y que permanecen fijos una vez concluido el entrenamiento.
Ambas entradas se combinan mediante atención cruzada: las semillas proporcionan las consultas (queries), mientras que las claves (keys) y los valores (values) proceden de la matriz de escena. Su salida es la matriz Y:
Y = atencion_cruzada(semillas,escena)
En la última fase, la matriz Y se utiliza para calcular las trayectorias y sus probabilidades. Wayformer genera tantas trayectorias como modos de movimiento —semillas— existen y asigna una probabilidad a cada una de ellas. Dos ramas del algoritmo, la rama de trayectoria y la rama de probabilidad, realizan estos cálculos:
T = lineal_t(Y) rama de trayectoria
P = softmax(lineal_p(Y)) rama de probabilidad
Cada fila de T representa una trayectoria bidimensional desplegada a lo largo de N instantes futuros. En cada instante, la posición se representa mediante una distribución (nube de probabilidad) gaussiana, definida por una media y una desviación típica para cada coordenada, x e y:
(μx, σx, μy, σy)
Por tanto, para K modos dinámicos y N instantes futuros, la matriz T tiene dimensión RKx4N.
Paralelamente, la rama de probabilidad genera un vector P en el que se determinan las probabilidades de las K trayectorias.
El resultado es, en fin, un conjunto de futuros posibles para cada agente, definidos no sólo por sus trayectorias y probabilidades respectivas, sino también por la incertidumbre (media, desviación típica) asociada a su posición en cada instante.
Conclusiones
La predicción de trayectorias, en cualquiera de las variedades expuestas en las secciones anteriores, transforma crucialmente los tracks pasados reconstruidos por el sistema de rastreo en un conjunto de futuros posibles. Esta información constituye una de las principales entradas de los algoritmos de reacción local, objeto del siguiente artículo de esta serie. Su función es reaccionar ante los objetos presentes en el entorno, ya sea esquivándolos o dirigiéndose hacia ellos, como ocurre en el caso de las municiones merodeadoras.
