Cómo Lyft crea mapas hiperprecisos con mapas de código abierto y datos en tiempo real

Rastros de GPS de Lyft en San Francisco.

Este artículo fue publicado originalmente el 6 de septiembre de 2019 en eng.lyft.com.

En Lyft, nuestro novedoso algoritmo de localización de conductores detecta errores en el mapa para crear un mapa hiperpreciso a partir de OpenStreetMap (OSM) y datos en tiempo real. Hemos corregido miles de errores en el mapa de OSM en áreas urbanas concurridas. Más adelante en la publicación, compartimos ejemplos de los errores de mapeo detectados en Minneapolis con la comunidad OSM para mejorar la calidad del mapa.

¿Por qué son importantes los mapas para Lyft?

La misión de Lyft de construir el mejor transporte del mundo depende de sus capacidades geoespaciales inherentes. Por ejemplo, para poder conectar a conductores y pasajeros eficientemente, se debe conocer con precisión la ubicación de ambos. De igual forma, necesitamos un conocimiento detallado de la red de caminos para calcular rutas eficientes y generar una predicción exacta del tiempo de llegada del conductor, partiendo desde su posición actual, al punto de encuentro con el pasajero y de dicho punto al destino final, una vez iniciado el viaje. Además, se requiere una comprensión meticulosa de la red de caminos para calcular correctamente la distancia recorrida por los conductores.

¿Cuál es el rol del equipo de mapeo?

Estos desafíos técnicos requieren un equipo con una sólida experiencia geoespacial. El equipo de Mapping (mapeo) de Lyft proporciona un modelo rico, fresco y preciso del mundo físico y cómo nuestros usuarios se mueven dentro de él. Así, hacemos posible lo siguiente:

• Generación óptima e inferencia de rutas probables para conductores y pasajeros.
• Predicciones de distancia y cálculos de tiempo certeros.
• Localización de conductores, pasajeros y vehículos.
• Construcción de bases de conocimientos de lugares físicos.
• Funcionalidades de inferencia de mapas.

¿Por qué es importante tener un mapa base preciso?

Nuestro mapa interno de la red de caminos se basa en OSM, que ha sido construido y mejorado a lo largo de los años por la comunidad open source. Recientemente, organizaciones grandes (como Apple, Microsoft, Mapbox, Mapillary, Facebook, Uber, Grab, Lyft, etc.)¹ también han contribuido a mejorar el mapa OSM. Al igual que Wikipedia, como enciclopedia libre u open source, el mapa de código abierto OSM puede contener datos faltantes o erróneos por varias razones. Por un lado, puede que existan caminos viejos que nunca han sido registrados, o que los nuevos no hayan sido mapeados aún; tal vez se reabrieron calles previamente cerradas o sufrieron “vandalismo digital”; incluso hay casos de edificios que no existen; quizás las indicaciones de tránsito, como las vueltas permitidas, sean erróneas, o los caminos estén mal identificados o etiquetados, y así sucesivamente. Debido a que OSM es una fuente para nuestro mapa base, necesitamos monitorear su calidad y precisión. Al detectar errores de mapas en OSM, trabajamos con nuestro equipo de Data Curation (curaduría de datos) para corregirlos. Esto se puede hacer utilizando nuestros datos privados.

Localización de conductores en la red de caminos: map-matching

Antes de hablar de detección de errores en el mapa, es necesario entender lo que es “coincidencia de mapa” (map-matching en inglés). En Lyft utilizamos los sensores de los teléfonos de nuestros conductores para conocer su ubicación. Esto incluye al receptor GPS que recibe localizaciones escasas (por las limitaciones de batería) y con ruido (debido a los cañones urbanos).

Si no tenemos un entendimiento de la red de caminos solo podemos utilizar un algoritmo de seguimiento de espacio libre como un filtro de Kalman, como se muestra en la Fig. 1. En consecuencia, los conductores no se localizarían dentro de la red de caminos.

Fig. 1 — La red de caminos se representa mediante líneas negras. Los puntos azules son la secuencia de ubicaciones de GPS emitidas por el teléfono del conductor. La ruta calculada por el filtro de Kalman, en verde, no aprovecha nuestro conocimiento de la red de caminos.

Sin embargo, OSM nos proporciona conocimiento de la red de caminos. Tomando como entrada una secuencia de trazos de GPS escasos y ruidosos y un mapa de la red de caminos, los algoritmos de “coincidencia de mapa” pueden inferir la trayectoria más precisa dentro de la red de caminos, como se muestra en la Fig. 2. Un ejemplo de un algoritmo de “map matching” es el basado en modelos ocultos de Márkov (HMM, Hidden Markov Models), desarrollado por Newson y Krumm². La calidad del mapa es esencial para el acoplamiento con el mapa.

Fig. 2 — La red de caminos se representa mediante líneas negras. Los puntos azules son la secuencia de ubicaciones de GPS emitidas por el teléfono del conductor. Un algoritmo tradicional de coincidencia de mapas [2], en rojo, aprovecha nuestro conocimiento de la red de caminos y calcula con precisión la trayectoria del conductor.

¿Cuáles son los posibles tipos de errores de mapeo en la red de caminos?

No todas las funciones de mapas en OSM son útiles para Lyft. Si bien las rutas de senderismo en OSM me encantan, esta no es una función de mapa crucial para la aplicación de Lyft. Las características de mapa más importantes y fundamentales para Lyft son las que caracterizan los componentes básicos de la red de caminos: la existencia de segmentos de caminos, sus sentidos y las restricciones de direcciones de giros.

En Lyft distinguimos dos tipos de errores de la red de caminos:

• Errores que desencadenan problemas de “coincidencia de mapa” y por ende problemas de redireccionamiento, denominados errores de mapa de tipo I
• Errores de la red de caminos que tienden a solo desencadenar problemas de redireccionamiento, denominados errores de mapa de tipo II

Errores de mapa de Tipo I: Basados en “coincidencia de mapa”

Debido a que los errores de mapa de Tipo I son los únicos que desencadenan problemas de “coincidencia de mapa”, podemos detectarlos encontrando dónde está fallando la localización del conductor en la red de carreteras. La Figura 3 muestra un caso en el que la “coincidencia de mapa” no logra reconstruir la trayectoria correcta del conductor.

Fig. 3 — La red de caminos se representa mediante líneas negras. Un camino faltante está en el centro del esquema. Los puntos azules son la secuencia de ubicaciones de GPS emitidas por el teléfono del conductor. Un algoritmo tradicional de “coincidencia de mapa”, en rojo, no detecta el camino que falta y calcula de forma inexacta la trayectoria del conductor en la red de caminos imperfecta.

Errores de mapa de tipo II: Basados en redireccionamiento

Debido a que los errores de mapa tipo II son los únicos que desencadenan problemas de enrutamiento sin desencadenar problemas de localización, podemos detectarlos encontrando en qué parte de la red de caminos falla el redireccionamiento pero no la localización.

En los dos ejemplos siguientes, la línea de puntos es un segmento de carretera que no existe en el mundo físico y, sin embargo, este camino está mapeado en OSM.

Asumiendo que las ubicaciones de GPS no son demasiado dispersas ni demasiado ruidosas, el segmento de camino adicional en OSM no causa fallas en la coincidencia de mapas, como se muestra en la Fig.4.

Fig. 4 — En este ejemplo, el camino adicional en la línea de puntos no causa errores de “Coincidencia de Mapa”.

Sin embargo, el segmento de camino adicional hace que los cálculos de la ruta más corta / más rápida sean incorrectos, lo que genera problemas de ruta, como se muestra en la Fig.5.

Fig. 5 — En este ejemplo, el camino adicional en la línea de puntos en OSM que no existe en el mundo físico hace que el enrutamiento sea incorrecto, ya que la trayectoria roja no es posible en el mundo físico. La estrella verde es el origen. La estrella roja es el destino.

Errores de mapa tipo I y II para la existencia de caminos, sus sentidos y restricciones de vueltas

Los errores del mapa relacionados con la existencia de los segmentos del camino, su sentido y las restricciones de direcciones de vueltas se pueden categorizar utilizando este marco, como se muestra en las siguientes tablas 1, 2 y 3.

Existencia del camino:

Tabla 1 — Errores de mapa de tipo I y tipo II para la existencia de caminos.

Sentido del camino:

Tabla 2 — Errores de mapa de tipo I y tipo II para sentido de caminos.

Restricciones de direcciones de vuelta del camino:

Tabla 3 — Errores de mapa de tipo I y tipo II para restricciones de giro.

¿Cómo adaptar la “coincidencia de mapa” a los errores de tipo I y encontrarlos?

Cuando el mapa es incorrecto, los filtros de Kalman funcionan mejor que el algoritmo tradicional de “coincidencia de mapa” con HMM. Sin embargo, el mapa suele ser correcto. Desarrollamos un algoritmo basado en un modelo múltiple semi-interactivo (sIMM, semi-interacting multiple model) en el que se ejecuta un filtro Kalman para ubicaciones “fuera de camino” en paralelo a un algoritmo “coincidencia de mapa” con HMM para ubicaciones sobre los caminos. Cuando el mapa es correcto, nuestro algoritmo utiliza la salida del HMM, mientras que se prefiere el filtro de Kalman cuando el mapa es incorrecto, como se explica en nuestro artículo aquí³. Nótese que un filtro de partículas podría sustituir fácilmente al HMM en esta metodología.

En Lyft, la salida del filtro de Kalman, las ubicaciones “fuera de camino”, se utilizan para detectar errores de mapa de tipo I, que abarcan los caminos que faltan, los caminos en OSM que están configurados en el sentido unidireccional incorrecto y las restricciones de dirección de vuelta que no deberían haber sido mapeadas en OSM. (En cierto sentido, esas son las características que restringen de más nuestro grafo de enrutamiento).

La figura 6 muestra un ejemplo de cómo funciona nuestro filtro sIMM, el cual emplea un filtro Kalman para ubicaciones “fuera de camino” y un HMM para ubicaciones en camino. Hay un camino faltante en el medio y un conductor viaja a través de ese camino faltante, como lo muestran las trazas del GPS.

El HMM utiliza la sección correcta del mapa (representada por la ruta roja a la izquierda) para calcular la trayectoria inicial del conductor. En la parte del mapa donde falta el camino (representada en verde), nuestro sistema detecta que el mapa es incorrecto y cambia al modo de filtro de Kalman “fuera de camino”. Finalmente, cuando el mapa vuelve a ser correcto, el algoritmo regresa al modo HMM en la carretera, como se muestra en la línea roja de la derecha.

Fig. 6 — La red de caminos se representa mediante líneas negras. Un camino faltante está en el centro del esquema. Los puntos azules son la secuencia de ubicaciones de GPS emitidas por el teléfono del conductor. El filtro sIMM captura cuándo el mapa es correcto y cuándo es incorrecto, y utiliza los modos en el camino (en rojo) y fuera de camino (en verde) en consecuencia.

Representación a gran escala de rastros “fuera de camino” como detector de errores de mapas

Cuando el mapa es incorrecto, la salida del filtro sIMM puede usarse para detectar errores de mapa de tipo I. Al aprovechar datos, recopilados durante semanas, de ubicaciones anónimas de los conductores de Lyft cuando están conectados a la aplicación y hacer un diagrama a gran escala de las trayectorias fuera de los caminos, podemos resaltar las áreas donde observamos errores de mapa tipo I. En Lyft descubrimos que la mayoría de los errores de mapa de tipo I se deben a caminos faltantes (aunque hemos observado algunos caminos con el sentido etiquetado erróneo y algunas restricciones de vuelta que desencadenan errores de mapa de tipo I). Usamos el paquete de Python “datashader” y nuestra herramienta de visualización interna para representar las trayectorias fuera del camino. Hicimos mosaicos rasterizados (“ráster”) de esas trayectorias “fuera de camino” para acelerar la carga de los errores de mapa detectados en las mismas. Aquí, los mosaicos ráster son más apropiados que los vectoriales. La carga de mosaicos vectoriales sería similar a volver a calcular cada polilínea de trayectoria fuera del camino para mostrarla a medida que nos desplazamos por el mapa, mientras que la carga de mosaicos ráster no requiere volver a calcular, a expensas de una menor interactividad — es difícil agregar metadatos en mosaicos ráster.

La figura 7 muestra ubicaciones fuera del camino en amarillo-rojo alrededor del aeropuerto MSP en Mineápolis. Un análisis de imágenes de satélite (obsoletas) muestra que los caminos probablemente se construyeron recientemente y que ahora son navegables por automóviles. OSM aún no está actualizado porque esos caminos aún no están mapeados.

Fig. 7 -Las ubicaciones fuera del camino en amarillo-rojo indican los caminos que faltan en el aeropuerto MSP en Minneapolis. Probablemente esto se deba a una construcción reciente. Las imágenes de satélite están desactualizadas.

La Figura 8 muestra ubicaciones fuera del camino en un estacionamiento en Minneapolis. El edificio del estacionamiento está mapeado en OSM. Sin embargo, debido a que los pasillos del estacionamiento no están mapeados, redireccionar dentro del estacionamiento no es posible, lo que activó las ubicaciones fuera de camino.

Fig. 8 — Las ubicaciones fuera de camino en amarillo-rojo indican los caminos que faltan en un estacionamiento en Minneapolis.

La Figura 9 muestra ubicaciones fuera de camino cerca del centro comercial Northtown Mall en Minneapolis. Los caminos mapeados con precisión en lugares como los centros comerciales son cruciales para Lyft, ya que su ausencia puede significar problemas en la recogida de usuarios

Fig. 9 — Las ubicaciones fuera del camino en amarillo-rojo indican los caminos que faltan en el Northtown Mall en Minneapolis.

No obstante, hemos observado que nuestro detector de errores de mapa de tipo I no funciona bien en caminos anchos cuando la precisión del GPS es deficiente o cuando los conductores no observan la red de caminos. Esto se debe a que esto activaría el modo “fuera de camino” aunque el mapa sea correcto.

En OSM los caminos anchos se mapean como una sola línea sin grosor, y aunque hay una etiqueta que indica el ancho del camino, ésta a menudo no posee datos. Esta es la razón principal por la que nuestro algoritmo sIMM no funciona bien con caminos anchos.

La precisión del GPS es particularmente mala en los cañones urbanos donde la gran densidad de edificios altos corrompe las lecturas del GPS debido a múltiples rutas u oclusiones.

Incluso cuando la red de caminos es correcta, si, por ejemplo, un conductor decide ignorar una dirección de giro, el algoritmo generará ubicaciones fuera del camino. Desafortunadamente, esas ubicaciones fuera de camino indican falsamente que el mapa está equivocado.

Usando nuestro detector de errores de mapas, hemos corregido y contribuido con miles de errores críticos de mapas de tipo I en OpenStreetMap, con la esperanza de que sean beneficiosos para la comunidad OSM. Además, para obtener más comentarios de la comunidad y ver si una liberación de datos más grande sería útil, estamos publicando una muestra de nuestros errores de mapa tipo I detectados en Minneapolis en MapRoulette (ver Fig. 10). ¡Échales un vistazo aquí!

Fig. 10 — Interfaz de nuestro MapRoulette Challenge (enlace).

En Lyft, la elaboración de mapas y la evaluación de su calidad son fundamentales para nuestro negocio. Nuestro creciente equipo de creación de mapas está abordando los errores de mapas de tipo II basados en redireccionamiento, así como otros tipos de inferencia de mapas, como los elementos de control de tráfico (consulta el trabajo de Deeksha Goyal durante su pasantía en Lyft⁴). ¡Sigue este blog para mantenerte al tanto de más publicaciones emocionantes sobre mapeo!

Si te ha gustado este post, ¡síguelo y recomiéndalo! Para obtener más información, consulta nuestras otras publicaciones científicas.

¡Como siempre, Lyft está contratando! Si te apasiona desarrollar modelos cuantitativos de última generación o construir la infraestructura que los impulsa, lee más sobre nuestras funciones de ciencia e ingeniería y comunícate con nosotros.

Nos gustaría agradecer a toda la organización de Mapping por su contribución / apoyo a este trabajo, a Alex Kazakova y Spencer Jaquish por liderar el equipo de Data Curation (curaduría de datos), así como a los editores de texto Ryan Lane, Julien Silland, Andrew Hao y Mark Grover por sus comentarios. ¡Muchas gracias!

Referencias

[1] Corporate Editors in the Evolving Landscape of OpenStreetMap, Jennings Anderson et al., ISPRS Int. J. Geo.-Inf., 2019. Liga

[2] Hidden Markov Map Matching Through Noise and Sparseness, Paul Newson and John Krumm, In Proceedings of the 17th ACM SIGSPATIAL, 2009. Liga

[3] Map matching when the map is wrong: Efficient on/off road vehicle tracking and map learning, James Murphy, Yuanyuan Pao, Albert Yuen, arXiv, 2018. Liga

[4] Traffic Control Elements Inference using Telemetry Data and Convolutional Neural Networks, Deeksha Goyal, Albert Yuen, Han Suk Kim, James Murphy, KDD UrbComp Workshop 2019, 2019. Liga

Este artículo fue escrito originalmente por Albert Yuen, James Murphy, Sumanth Ravipati, Deeksha Goyal, Han Kim, Adithya Hemakumar, Milo Han, Alex Ung, Clare Corthell.