Emparejamiento de mapas para la predicción de trayectorias

Emparejamiento de mapas para predicción de trayectorias

¿A dónde vas? ¿Deberías ir en esa dirección?

Foto de Mateusz Wacławek en Unsplash

Este artículo presenta un método para predecir trayectorias de vehículos en una red vial digital utilizando una base de datos de viajes pasados muestreados a partir de sensores GPS ruidosos. Además de predecir direcciones futuras, este método también asigna una probabilidad a una secuencia arbitraria de ubicaciones.

El centro de esta idea es utilizar un mapa digital en el que proyectamos todas las ubicaciones muestreadas, agregándolas en trayectorias individuales y luego emparejándolas con el mapa. Este proceso de emparejamiento discretiza el espacio continuo de GPS en ubicaciones y secuencias predefinidas. Después de codificar estas ubicaciones en tokens geoespaciales únicos, podemos predecir más fácilmente secuencias, evaluar la probabilidad de observaciones actuales y estimar direcciones futuras. Esto es lo esencial de este artículo.

Los Problemas

¿Qué problemas estoy tratando de resolver aquí? Si necesitas analizar datos de trayectorias de vehículos, es posible que necesites responder preguntas como las del subtítulo del artículo.

¿A dónde vas? ¿Deberías ir en esa dirección?

¿Cómo evalúas la probabilidad de que la trayectoria observada siga direcciones frecuentemente transitadas? Esta es una pregunta importante, ya que al responderla podrías programar un sistema automatizado para clasificar los viajes según su frecuencia observada. Una nueva trayectoria con una puntuación baja causaría preocupación y generaría una alerta inmediata.

¿Cómo predices qué maniobras hará el vehículo a continuación? ¿Seguirá recto o girará a la derecha en la próxima intersección? ¿Dónde esperas ver el vehículo en los próximos diez minutos o diez millas? Respuestas rápidas a estas preguntas ayudarán a una solución de software de seguimiento en línea a proporcionar respuestas e información a planificadores de entregas, optimizadores de rutas en línea o incluso sistemas de carga oportunista.

Solución

La solución que presento aquí utiliza una base de datos de trayectorias históricas, cada una consistiendo en una secuencia temporal de posiciones generadas por el movimiento de un vehículo específico. Cada registro de posición debe contener tiempo, información de posición, una referencia al identificador del vehículo y el identificador de la trayectoria. Un vehículo tiene muchas trayectorias y cada trayectoria tiene muchos registros de posición. Una muestra de nuestros datos de entrada se muestra en Figura 1 a continuación.

Figura 1 — La tabla de arriba muestra una pequeña muestra de una trayectoria del Conjunto de Datos de Energía de Vehículos Extendidos. Aunque cada fila contiene más propiedades que las mostradas, solo necesitamos el orden implícito y las ubicaciones. Ten en cuenta que hay muchas ubicaciones duplicadas debido a la estrategia de muestreo. Abordaremos este problema más adelante. (Fuente de la imagen: Autor)

Los datos anteriores fueron extraídos del Conjunto de Datos de Energía de Vehículos Extendidos (EVED) [1]. Puedes construir la base de datos correspondiente siguiendo el código de uno de mis artículos anteriores.

Estimación del Tiempo de Viaje Usando Quadkeys

Este artículo explica cómo estimar los tiempos de viaje utilizando vectores de velocidad conocidos indexados por quadkeys.

towardsdatascience.com

Nuestro primer trabajo es emparejar estas trayectorias con un mapa digital de apoyo. El propósito de este paso no solo es eliminar los errores de muestreo de los datos de GPS, sino, lo más importante, coercer los datos de viaje adquiridos a una red vial existente donde cada nodo y arista son conocidos y fijos. Cada trayectoria grabada se convierte así en una secuencia de tokens numéricos que coinciden con los nodos del mapa digital existente. Aquí utilizaremos datos y software de código abierto, con datos de mapa obtenidos de OpenStreetMap (compilado por Geofabrik), el paquete de emparejamiento de mapas Valhalla y H3 como el tokenizador geoespacial.

Coincidencia de bordes versus coincidencia de nodos

La coincidencia de mapas es más compleja de lo que parece a primera vista. Para ilustrar lo que implica este concepto, veamos la Figura 2 a continuación.

Figura 2 — El mapa de arriba muestra una trayectoria ruidosa tomada del EVED en azul. Como puedes ver, no coincide con la carretera más cercana y necesita coincidir con el mapa. Una vez que proyectamos los vértices de la línea azul en el mapa, obtenemos una secuencia de proyecciones de los puntos originales en los bordes del mapa inferido, y puedes ver la trayectoria resultante en rojo. Sin embargo, esta trayectoria no coincide con el mapa subyacente en algunos lugares, especialmente en el centro de la imagen, donde la línea roja salta entre carreteras. Nuestro objetivo es reconstruir la ruta del viaje en el mapa, como se representa con la línea verde, que sigue los nodos del mapa subyacente. (Fuente de la imagen: Autor utilizando Folium e imágenes de OpenStreetMap)

La Figura 2 anterior muestra que podemos obtener dos trayectorias a partir de una secuencia GPS original. Obtenemos la primera trayectoria proyectando las ubicaciones GPS originales en los segmentos de la red de carreteras más cercanos (y más probables). Como puedes ver, la polilínea resultante solo seguirá la carretera en ocasiones, ya que el mapa utiliza nodos de grafo para definir sus formas básicas. Al proyectar las ubicaciones originales en los bordes del mapa, obtenemos nuevos puntos que pertenecen al mapa pero que pueden desviarse de la geometría del mapa cuando se conectan a los siguientes mediante una línea recta.

Al proyectar la trayectoria GPS en los nodos del mapa, obtenemos una ruta que se superpone perfectamente al mapa, como se muestra en la línea verde de la Figura 2. Aunque esta ruta representa mejor la trayectoria inicialmente recorrida, no necesariamente tiene una correspondencia de ubicación uno a uno con la original. Afortunadamente, esto no será un problema, ya que siempre asignaremos cualquier trayectoria al mapa a los nodos del mapa, por lo que siempre obtendremos datos coherentes, con una excepción. El código de coincidencia de mapas de Valhalla siempre proyecta los puntos iniciales y finales de la trayectoria en los bordes, por lo que los descartaremos sistemáticamente, ya que no corresponden a los nodos del mapa.

Tokenización H3

Desafortunadamente, Valhalla no informa los identificadores únicos de los nodos de la red de carreteras, por lo que debemos convertir las coordenadas de los nodos en tokens enteros únicos para el cálculo posterior de la frecuencia de secuencia. Aquí es donde entra en juego H3 al permitirnos codificar las coordenadas de los nodos en un número entero de sesenta y cuatro bits de forma única. Tomamos la polilínea generada por Valhalla, eliminamos los puntos iniciales y finales (estos puntos no son nodos, sino proyecciones de bordes) y asignamos todas las coordenadas restantes a índices H3 de nivel 15.

El grafo dual

Utilizando el proceso anterior, convertimos cada trayectoria histórica en una secuencia de tokens H3. El siguiente paso es convertir cada trayectoria en una secuencia de tripletas de tokens. Tres valores en una secuencia representan dos bordes consecutivos del grafo de predicción, y queremos conocer las frecuencias de estos, ya que serán los datos fundamentales tanto para la predicción como para la evaluación de la probabilidad. La Figura 3 a continuación representa este proceso visualmente.

Figura 3 — La lista de tokens geoespaciales a la izquierda se expande a otra lista de tripletas, que representan una visión dual del grafo implícito. Cada token es un nodo en el grafo geoespacial, y su secuencia representa los bordes. La lista transformada considera cada borde como un nodo en el grafo dual, y el token del medio es el nuevo borde, como se muestra en la columna de la derecha. (Fuente de la imagen: Autor)

La transformación anterior calcula el dual del grafo vial, invirtiendo los roles de los nodos y aristas originales.

Ahora podemos empezar a responder las preguntas propuestas.

¿Deberías ir en esa dirección?

Necesitamos conocer la trayectoria del vehículo hasta un momento dado para responder a esta pregunta. Hacemos la coincidencia y tokenización de la trayectoria utilizando el mismo proceso que se menciona arriba, y luego calculamos la frecuencia de cada triplete de trayectoria utilizando las frecuencias históricas conocidas. El resultado final es el producto de todas las frecuencias individuales. Si el triplete de entrada es desconocido, su frecuencia será cero como probabilidad final de ruta.

La probabilidad de un triplete es la relación entre el conteo de una secuencia específica (A, B, C) y el conteo de todos los tripletes (A, B, *) , como se muestra en Figura 4 a continuación.

Figura 4: La probabilidad de un triplete es la relación de su frecuencia con la frecuencia de todos los tripletes con los mismos dos tokens iniciales. (Fuente de la imagen: Autor)

La probabilidad de la ruta es simplemente el producto de los tripletes de viaje individuales, como se muestra en Figura 5 a continuación.

Figura 5: La probabilidad de la ruta es el producto simple de todos los tripletes coincidentes. (Fuente de la imagen: Autor)

¿A dónde vas?

Utilizamos los mismos principios para responder a esta pregunta, pero comenzamos con el último triplete conocido solamente. Podemos predecir los k sucesores más probables utilizando este triplete como entrada, enumerando todos los tripletes que tengan como sus dos primeros tokens los dos últimos de la entrada. Figura 6 a continuación ilustra el proceso de generación y evaluación de secuencias de tripletes.

Figura 6: En este caso ficticio, el siguiente triplete más probable es aquel con la frecuencia observada más alta: (B, C, D). (Fuente de la imagen: Autor)

Podemos extraer los k tripletes sucesores principales y repetir el proceso para predecir el viaje más probable.

Implementación

Estamos listos para discutir los detalles de la implementación, comenzando con la coincidencia de mapas y algunos conceptos asociados. A continuación, veremos cómo usar el conjunto de herramientas Valhalla desde Python, extraer las rutas coincidentes y generar las secuencias de tokens. El paso de preprocesamiento de datos terminará una vez que almacenemos el resultado en la base de datos.

Finalmente, ilustro una interfaz de usuario simple usando Streamlit que calcula la probabilidad de cualquier trayectoria dibujada a mano y luego la proyecta hacia el futuro.

Coincidencia de mapas

La coincidencia de mapas convierte las coordenadas GPS muestreadas de la trayectoria de un objeto en movimiento en un grafo de carreteras existente. Un grafo de carreteras es un modelo discreto de la red de carreteras físicas subyacentes que consiste en nodos y aristas de conexión. Cada nodo corresponde a una ubicación geoespacial conocida a lo largo de la carretera, codificada como una tupla de latitud, longitud y altitud. Cada arista dirigida conecta nodos adyacentes siguiendo la carretera subyacente y contiene muchas propiedades como la dirección, velocidad máxima, tipo de carretera y más. Figura 7 a continuación ilustra el concepto con un ejemplo sencillo.

Figura 7: En la imagen de arriba se muestra una pequeña red vial digital resaltando una intersección. Cada punto rojo representa una ubicación geoespacial conocida a lo largo de la carretera existente. Las líneas azules representan las aristas de conexión entre los nodos. Tenga en cuenta que estas aristas suelen ser dirigidas y también pueden ser múltiples. (Fuente de la imagen: Autor)

Cuando tiene éxito, el proceso de ajuste al mapa produce información relevante y valiosa sobre la trayectoria muestreada. Por un lado, el proceso proyecta los puntos GPS muestreados en ubicaciones a lo largo de los bordes del grafo de carreteras más probable. El proceso de ajuste al mapa “corrige” los puntos observados colocándolos correctamente sobre los bordes inferidos del grafo de carreteras. Por otro lado, el método también reconstruye la secuencia de nodos del grafo proporcionando la ruta más probable a través del grafo de carreteras que corresponde a las ubicaciones GPS muestreadas. Hay que tener en cuenta que, como se explicó anteriormente, estas salidas son diferentes. La primera salida contiene coordenadas a lo largo de los bordes de la ruta más probable, mientras que la segunda salida consiste en la secuencia reconstruida de nodos del grafo. La Figura 8 a continuación ilustra el proceso.

Figura 8 — El diagrama de arriba ilustra el proceso de ajuste al mapa, donde los puntos verdes representan las coordenadas GPS observadas y los diamantes naranjas son las ubicaciones proyectadas a lo largo de los bordes conocidos. Hay que tener en cuenta que, para el ejemplo simplificado anterior, solo podemos reconstruir de manera segura la ruta entre los nodos 2 y 3. Esta situación no es tan grave como parece porque, en los mapas reales, las trayectorias coinciden con muchos más bordes que solo uno, por lo que la pérdida de información es mínima. (Fuente de la imagen: Autor)

Un subproducto del proceso de ajuste al mapa es la estandarización de las ubicaciones de entrada mediante una representación compartida de la red de carreteras, especialmente al considerar el segundo tipo de salida: la secuencia más probable de nodos. Al convertir las trayectorias GPS muestreadas en una serie de nodos, las hacemos comparables al reducir la ruta inferida a una serie de identificadores de nodos. Podemos pensar en estas secuencias de nodos como frases de un lenguaje conocido, donde cada identificador de nodo inferido es una palabra y su disposición transmite información de comportamiento.

Este es el quinto artículo en el que exploro el Extended Vehicle Energy Dataset¹ (EVED) [1]. Este conjunto de datos es una mejora y revisión del trabajo anterior y proporciona las versiones ajustadas al mapa de las ubicaciones GPS originales (los diamantes naranjas en la Figura 8 anterior).

Desafortunadamente, el EVED solo contiene las ubicaciones GPS proyectadas y no incluye las secuencias de nodos reconstruidas de la red de carreteras. En mis dos artículos anteriores, abordé el problema de reconstruir las secuencias de segmentos de carretera a partir de las ubicaciones GPS transformadas sin ajuste al mapa. El resultado fue algo decepcionante, ya que esperaba menos del 16% de reconstrucciones defectuosas observadas. Puedes seguir esta discusión en los siguientes artículos.

Ajuste de Bordes de la Red de Carreteras con Triángulos

Los triángulos tienen propiedades poderosas para consultas geoespaciales

towardsdatascience.com

Más sobre el Ajuste de la Red de Carreteras

Travesuras en el ajuste de la red de carreteras

towardsdatascience.com

Ahora estoy examinando la herramienta de ajuste al mapa fuente para ver hasta dónde puede llegar en la corrección de las reconstrucciones defectuosas. Así que pongamos a Valhalla a prueba. A continuación se presentan los pasos, referencias y código que utilicé para ejecutar Valhalla en un contenedor Docker.

Configuración de Valhalla

Aquí sigo de cerca las instrucciones proporcionadas por Sandeep Pandey [2] en su blog.

En primer lugar, asegúrate de tener Docker instalado en tu máquina. Para instalar el motor de Docker, sigue las instrucciones en línea. Si trabajas en un Mac, una excelente alternativa es Colima.

Una vez instalado, debes obtener una imagen de Valhalla desde GitHub ejecutando los siguientes comandos en tu línea de comandos, como se muestra en el código de shell de la Figura 9 a continuación.

Figura 9 — Obteniendo la imagen de Docker de Valhalla desde la línea de comandos. (Fuente de la imagen: Autor)

Mientras ejecutas los comandos anteriores, es posible que debas ingresar tus credenciales de GitHub. Además, asegúrate de haber clonado el repositorio de GitHub de este artículo, ya que algunos archivos y estructuras de carpetas se refieren a él.

Una vez hecho esto, debes abrir una nueva ventana de terminal y ejecutar el siguiente comando para iniciar el servidor de la API Valhalla (MacOS, Linux, WSL):

Figura 10 — El comando anterior ejecuta la imagen de Valhalla en un contenedor Docker. Durante la ejecución inicial, el comando también descarga y prepara el último archivo de datos de Geofabrik Michigan antes de iniciar. (Fuente de la imagen: Autor)

La línea de comando anterior especifica explícitamente qué archivo de OSM descargar del servicio Geofabrik, el último archivo de Michigan. Esta especificación significa que al ejecutarse por primera vez, el servidor descargará y procesará el archivo y generará una base de datos optimizada. En llamadas posteriores, el servidor omitirá estos pasos. Cuando sea necesario, elimine todo lo que está debajo del directorio objetivo para actualizar los datos descargados y volver a iniciar Docker.

Ahora podemos llamar a la API de Valhalla con un cliente especializado.

Ingresa a PyValhalla

Este proyecto derivado simplemente ofrece enlaces empaquetados de Python al fantástico proyecto Valhalla.

Usar el paquete de Python PyValhalla es bastante simple. Comenzamos con un procedimiento de instalación ordenado utilizando la siguiente línea de comando.

Figura 11 — Puedes instalar PyValhalla usando PIP. (Fuente de la imagen: Autor)

En tu código de Python, debes importar las referencias necesarias, instanciar una configuración a partir de los archivos procesados de GeoFabrik y finalmente crear un objeto Actor, tu puerta de enlace a la API de Valhalla.

Figura 12 — El código anterior muestra lo fácil que es configurar PyValhalla en una aplicación o cuaderno de Python. (Fuente de la imagen: Autor)

Antes de llamar al servicio de coincidencia de mapas de Meili, debemos obtener las ubicaciones de GPS de la trayectoria utilizando la función que se muestra a continuación en Figura 13.

Figura 13 — La función anterior carga las posiciones únicas de la trayectoria de un vehículo, devolviendo un DataFrame de Pandas con latitud, longitud y marca de tiempo. (Fuente de la imagen: Autor)

Ahora podemos configurar el diccionario de parámetros para pasar a la llamada de PyValhalla para trazar la ruta. Consulta la documentación de Valhalla para obtener más detalles sobre estos parámetros. La función a continuación llama a la función de coincidencia de mapas en Valhalla (Meili) y está incluida en el script de preparación de datos. Ilustra cómo determinar la ruta inferida a partir de un DataFrame de Pandas que contiene las ubicaciones de GPS observadas codificadas como tuplas de latitud, longitud y tiempo.

Figura 14 — La función anterior acepta un objeto Actor de PyValhalla y un DataFrame de Pandas que contiene la ruta de origen y devuelve una cadena codificada de polyline. Esta cadena se decodifica más tarde en una lista de ubicaciones geoespaciales correspondientes a los nodos de la red de mapas digitales, excepto en los extremos, que se proyectan en los bordes. (Fuente de la imagen: Autor)

La función anterior devuelve la ruta coincidente como una cadena codificada de polyline. Como se ilustra en el código de preparación de datos a continuación, podemos decodificar fácilmente la cadena devuelta utilizando una llamada de biblioteca de PyValhalla. Ten en cuenta que esta función devuelve una polyline cuyas primeras y últimas ubicaciones se proyectan en los bordes, no en los nodos del grafo. Verás que estos extremos se eliminan mediante código más adelante en el artículo.

Veamos ahora la fase de preparación de datos, donde convertimos todas las trayectorias en la base de datos de EVED en un conjunto de secuencias de bordes de mapas, a partir de las cuales podemos derivar frecuencias de patrones.

Preparación de datos

La preparación de datos tiene como objetivo convertir las trayectorias adquiridas por GPS ruidosas en secuencias de tokens geoespaciales correspondientes a ubicaciones de mapas conocidas. El código principal itera a través de los viajes existentes, procesando uno a la vez.

En este artículo, utilizo una base de datos SQLite para almacenar todos los resultados del procesamiento de datos. Comenzamos llenando la ruta de la trayectoria coincidente. Puedes seguir la descripción utilizando el código en Figura 15 a continuación.

Figura 15 — El código anterior contiene el bucle de datos de preprocesamiento. Este bucle itera a través de las trayectorias conocidas, calcula sus rutas coincidentes con el mapa (si las hay), tokeniza los nodos y los expande en tripletas. El código almacena todos los resultados intermedios y finales en la base de datos. (Fuente de la imagen: Autor)

Para cada trayectoria, creamos una instancia de un objeto del tipo Actor (línea 9). Esto es un requisito no declarado, ya que cada llamada al servicio de coincidencia de mapas requiere una nueva instancia. A continuación, cargamos los puntos de la trayectoria (línea 13) adquiridos por los receptores GPS de los vehículos con el ruido añadido, como se indica en el artículo original de VED. En la línea 14, realizamos la llamada de coincidencia de mapas a Valhalla, recuperamos la ruta coincidente codificada como cadena y la guardamos en la base de datos. A continuación, decodificamos la cadena en una lista de coordenadas geoespaciales, eliminamos los extremos (línea 17) y luego las convertimos en una lista de índices H3 calculados en el nivel 15 (línea 19). En la línea 23, guardamos los índices H3 convertidos y las coordenadas originales en la base de datos para una asignación inversa posterior. Finalmente, en las líneas 25 a 27, generamos una secuencia de tripletas basadas en la lista de índices H3 y las guardamos para cálculos de inferencia posteriores.

Vamos a repasar cada uno de estos pasos y explicarlos en detalle.

Carga de Trayectorias

Hemos visto cómo cargar cada trayectoria desde la base de datos (ver Figura 13). Una trayectoria es una secuencia ordenada en el tiempo de ubicaciones GPS muestreadas, codificadas como un par de latitud y longitud. Tenga en cuenta que no estamos utilizando las versiones coincidentes de estas ubicaciones como se proporciona en los datos EVED. Aquí, utilizamos las coordenadas ruidosas y originales tal como existían en la base de datos inicial de VED.

Ajuste al Mapa

El código que llama al servicio de ajuste al mapa ya se presenta en la Figura 14 anterior. Su problema central son las configuraciones de ajuste; aparte de eso, es una llamada bastante sencilla. Guardar la cadena codificada resultante en la base de datos también es simple.

Figura 16 — El código anterior guarda la cadena de polilínea codificada en la nueva base de datos. (Fuente de la imagen: Autor)

En la línea 17 del bucle principal (Figura 15), decodificamos la cadena de geometría en una lista de tuplas de latitud y longitud. Tenga en cuenta que aquí eliminamos las ubicaciones iniciales y finales, ya que no se proyectan en nodos. A continuación, convertimos esta lista en su lista correspondiente de tokens H3 en la línea 19. Utilizamos el nivel máximo de detalle para tratar de evitar superposiciones y asegurar una relación uno a uno entre los tokens H3 y los nodos del grafo del mapa. Insertamos los tokens en la base de datos en las siguientes dos líneas. Primero, guardamos toda la lista de tokens asociándola a la trayectoria.

Figura 17 — La función anterior inserta la lista de tokens H3 de la trayectoria en la base de datos. (Fuente de la imagen: Autor)

A continuación, insertamos la asignación de coordenadas de nodos a tokens H3 para permitir dibujar polilíneas a partir de una lista dada de tokens. Esta característica será útil más adelante al inferir las direcciones de los viajes futuros.

Figura 18 — Insertamos una asignación entre tokens H3 y coordenadas de nodos para permitir la reconstrucción de una trayectoria a partir de tokens inferidos dados. (Fuente de la imagen: Autor)

Ahora podemos generar y guardar las correspondientes tripletas de tokens. La función a continuación utiliza la lista recién generada de tokens H3 y la expande a otra lista de tripletas, como se detalla en la Figura 3 anterior. El código de expansión se muestra en la Figura 19 a continuación.

Figura 19 — El código anterior convierte una lista de tokens H3 en una lista de las tripletas correspondientes. (Fuente de la imagen: Autor)

Después de la expansión de las tripletas, finalmente podemos guardar el producto final en la base de datos, como se muestra en el código de la Figura 20 a continuación. Mediante una consulta inteligente a esta tabla, inferiremos las probabilidades de viaje actuales y las trayectorias futuras más probables.

Figura 20 — La función anterior guarda las tripletas H3 en la base de datos. Este es el paso final de la fase de preparación de datos. Ahora podemos pasar a explorar la información que hemos recopilado. (Fuente de la imagen: Autor)

Ya hemos terminado un ciclo del bucle de preparación de datos. Una vez que se complete el bucle externo, tendremos una nueva base de datos con todas las trayectorias convertidas en secuencias de tokens que podemos explorar a nuestro gusto.

Puede encontrar el código completo de preparación de datos en el repositorio de GitHub.

Probabilidades y Predicciones

Ahora pasamos al problema de estimar las probabilidades de viaje existentes y predecir las direcciones futuras. Comencemos definiendo lo que quiero decir con “probabilidades de viaje existentes”.

Probabilidades de Viaje

Comenzamos con una ruta arbitraria proyectada en los nodos de la red vial a través del ajuste al mapa. Por lo tanto, tenemos una secuencia de nodos del mapa y queremos evaluar qué tan probable es esa secuencia, utilizando como referencia de frecuencia la base de datos de viajes conocidos. Utilizamos la fórmula en la Figura 5 anterior. En pocas palabras, calculamos el producto de las probabilidades de todas las tripletas de tokens individuales.

Para ilustrar esta característica, implementé una aplicación sencilla de Streamlit que permite al usuario dibujar un viaje arbitrario sobre el área de Ann Arbor cubierta y calcular inmediatamente su probabilidad.

Una vez que el usuario dibuja puntos en el mapa que representan el viaje o las muestras hipotéticas de GPS, el código los ajusta al mapa para recuperar los tokens H3 subyacentes. A partir de ahí, es simplemente cuestión de calcular las frecuencias de las tripletas individuales y multiplicarlas para calcular la probabilidad total. La función en la Figura 21 a continuación calcula la probabilidad de un viaje arbitrario.

Figura 21 — La función anterior calcula una probabilidad de ruta arbitraria a partir de la base de datos de frecuencia de tripletes. (Fuente de la imagen: Autor)

El código recibe soporte de otra función que recupera los sucesores de cualquier par existente de tokens H3. La función que se muestra a continuación en Figura 22 consulta la base de datos de frecuencia y devuelve un objeto Counter de Python con los recuentos de todos los sucesores del par de tokens de entrada. Cuando la consulta no encuentra sucesores, la función devuelve la constante None. Observa cómo la función utiliza una caché para mejorar el rendimiento de acceso a la base de datos (código no mostrado aquí).

Figura 22 — La función anterior consulta la base de datos de frecuencia para los sucesores conocidos de cualquier par de tokens H3 y devuelve un objeto Counter con los recuentos de todos los sucesores. (Fuente de la imagen: Autor)

Diseñé ambas funciones de manera que la probabilidad calculada sea cero cuando no existen sucesores conocidos para cualquier nodo dado.

Veamos cómo podemos predecir la trayectoria más probable en el futuro.

Predicción de direcciones

Solo necesitamos los dos últimos tokens de una carrera en curso para predecir sus direcciones más probables en el futuro. La idea consiste en expandir todos los sucesores de ese par de tokens y seleccionar los más frecuentes. El código a continuación muestra la función como punto de entrada al servicio de predicción de direcciones.

Figura 23 — La función anterior rellena un objeto FeatureGroup de Folium con las rutas predichas del viaje proporcionado por el usuario. (Fuente de la imagen: Autor)

La función anterior comienza recuperando la trayectoria dibujada por el usuario como una lista de tokens H3 mapeados en el mapa y extrayendo el último par. Llamamos a este par de tokens la semilla y la expandiremos aún más en el código. En la línea 9, llamamos a la función de expansión de semilla que devuelve una lista de polilíneas correspondientes a los criterios de expansión de entrada: la ramificación máxima por iteración y el número total de iteraciones.

Veamos cómo funciona la función de expansión de la semilla siguiendo el código que se muestra a continuación en Figura 24.

Figura 24 — La función de expansión de la semilla utiliza la clase PredictedPath para gestionar cada iteración. Consulta más detalles sobre esta clase a continuación. (Fuente de la imagen: Autor)

Llamando a una función de expansión de ruta que genera las mejores rutas sucesoras, la función de expansión de semilla expande iterativamente las rutas, comenzando con la inicial. La expansión de ruta opera seleccionando una ruta y generando las expansiones más probables, como se muestra a continuación en Figura 25.

Figura 25 — La función de expansión de ruta anterior itera los sucesores más frecuentes de la ruta actual. Crea una nueva ruta para cada uno de los sucesores más frecuentes utilizando una función especializada (ver más abajo). (Fuente de la imagen: Autor)

El código genera nuevas rutas agregando los nodos sucesores a la ruta de origen, como se muestra en Figura 26 a continuación.

Figura 26 — Para generar una ruta “hija”, solo necesitamos agregar el nodo sucesor a una ruta existente, como se muestra a continuación. Observa que el código crea una copia de la ruta original antes de agregar el nuevo nodo. (Fuente de la imagen: Autor)

El código implementa rutas predichas utilizando una clase especializada, como se muestra en Figura 27.

Figura 27 — La clase anterior implementa una ruta predicha con soporte de ordenación de probabilidad, creación a partir de un par de tokens de semilla y generación de polilínea de mapa. (Fuente de la imagen: Autor)

La aplicación

Ahora podemos ver la aplicación Streamlit resultante en Figura 28 a continuación.

Figura 28 — La aplicación Streamlit muestra las dos características descritas en acción. La trayectoria de entrada está en azul y se puede dibujar usando el menú de herramientas en el lado izquierdo del mapa. Una vez dibujada, el código calcula su probabilidad y la muestra en la parte inferior. Las tres trayectorias rojas son las tres predicciones más probables con cincuenta bordes para dónde puede evolucionar la trayectoria original. Al hacer clic en cada trayectoria, aparece una ventana emergente con la probabilidad calculada. (Fuente de la imagen: Autor)

Conclusión

En este artículo, presenté un método para predecir la trayectoria futura de un vehículo al conducir a través de una red de carreteras digitalmente mapeada. Utilizando una base de datos de trayectorias históricas, este método asigna una probabilidad a cualquier viaje y también predice las direcciones más probables para el futuro cercano. En consecuencia, este método puede detectar trayectorias improbables o incluso novedosas que nunca se hayan visto antes.

Comenzamos con una extensa base de datos de trayectorias de vehículos en el área de interés. Cada camino es una secuencia cronológica de coordenadas geoespaciales (latitud y longitud) y otras propiedades relevantes como la velocidad. Por lo general, recopilamos estas trayectorias de receptores GPS a bordo y las compilamos de forma centralizada en una base de datos.

Las muestras de GPS son ruidosas debido a errores inevitables que ocurren durante la medición de la señal. Obstáculos naturales y artificiales, como cañones urbanos, pueden disminuir significativamente la precisión de la recepción de la señal y aumentar los errores de geolocalización. Afortunadamente, existen soluciones viables que resuelven este problema mediante la coincidencia probabilística de las muestras de GPS con un mapa digital. Esto es de lo que se trata el emparejamiento de mapas.

Al emparejar las muestras de GPS ruidosas con un mapa digital conocido, no solo corregimos el problema de precisión proyectando cada instancia en el segmento de carretera más probable del mapa, sino que también obtenemos una secuencia discreta de ubicaciones existentes definidas en el mapa por las que el vehículo probablemente pasó. Este último resultado es fundamental para nuestra predicción de trayectoria porque convierte esencialmente un conjunto de coordenadas GPS ruidosas en una colección limpia y bien conocida de puntos en el mapa digital. Estos marcadores digitales son fijos y nunca cambian, y al proyectar la secuencia de muestras de GPS en ellos, obtenemos una cadena de tokens bien conocidos que luego podemos usar para la predicción.

Calculamos todas las probabilidades utilizando las frecuencias de secuencia de tokens conocidas para trayectorias arbitrarias y su evolución futura. El resultado es un par de scripts de Python, uno para la preparación de datos y otro para la entrada de datos y la visualización utilizando la plataforma Streamlit.

Notas

  1. Los autores originales del artículo otorgaron una licencia a los datos bajo la Licencia Apache 2.0 (consulte los repositorios VED y EVED en GitHub). Tenga en cuenta que esto también se aplica al trabajo derivado.

Referencias

[1] Zhang, S., Fatih, D., Abdulqadir, F., Schwarz, T., & Ma, X. (2022). Extended vehicle energy dataset (eVED): an enhanced large-scale dataset for deep learning on vehicle trip energy consumption. arXiv. https://doi.org/10.48550/arXiv.2203.08630

[2] Efficient and fast map matching with Valhalla — Sandeep Pandey (ikespand.github.io)

[3] Map Matching done right using Valhalla’s Meili | by Serge Zotov | Towards Data Science

João Paulo Figueira es un científico de datos en tb.lx por Daimler Truck en Lisboa, Portugal.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Aprendizaje Automático

DeepMind presenta AlphaDev un agente de aprendizaje por refuerzo profundo que descubre algoritmos de clasificación más rápidos desde cero.

Desde la Inteligencia Artificial y el Análisis de Datos hasta la Criptografía y la Optimización, los algoritmos juega...

Inteligencia Artificial

Las etiquetas de ciberseguridad para dispositivos inteligentes están en camino

La Casa Blanca presenta un nuevo plan de etiquetado de ciberseguridad para informarte cuando tus dispositivos intelig...

Investigación

Los investigadores utilizan la IA para identificar materiales similares en imágenes.

Este método de aprendizaje automático podría ayudar en la comprensión de escenas robóticas, la edición de imágenes o ...

Inteligencia Artificial

Nuevo curso técnico de inmersión profunda Fundamentos de IA generativa en AWS

Generative AI Foundations en AWS es un nuevo curso de inmersión técnica que te proporciona los fundamentos conceptual...