Usando datos del mapa del cliente para mejorar el posicionamiento en tiempo real

Este artículo fue publicado originalmente el 13 de julio de 2021 en eng.lyft.com, por Karina Goot, Tony Zhang, Burak Bostancioglu, Bobby Sudekum y Erik Kamp y fue traducido por Kevin Woo.

Introducción

Las señales de GPS son significativamente ruidosas y poco confiables (Fig. 1). Uno de los principales retos para el equipo de mapping (mapeo) en Lyft es traducir las señales ruidosas del GPS de los dispositivos de nuestros conductores y pasajeros a ubicaciones precisas en el mapa. Esto mejora la capacidad de emparejar a conductores y pasajeros, tomar decisiones, predicciones de tiempos de llegada acertadas, y mucho más. Llamamos a este proceso map matching (emparejamiento de mapas).

Fig 1. Ejemplo de una ubicación ruidosa en un área urbana densa y las mejoras tras el emparejamiento de mapas

Los datos del mapa ayudan al proceso de emparejamiento porque pueden reducir el espacio de ubicaciones a sólo los caminos. Por esta razón, históricamente, corríamos nuestro algoritmo de map matching solamente del lado del servidor para utilizar los datos de mapa subyacentes.

Durante 2020, estuvimos creando un sistema de localización para el dispositivo. Tener capacidades de localización en el cliente nos permite tener lecturas de sensores más precisas, reducir la latencia, localizar conductores cuando pierden la recepción móvil, y desbloquear nuevos casos de uso para el producto a través de la plataforma de Lyft.

A diferencia de los sistemas de localización en los servidores, la localización del lado del cliente está extremadamente restringida por la memoria y los requerimientos de latencia. Como resultado, no podemos utilizar datos de los mapas eficientemente sin impactar en la memoria del dispositivo (guardar mucha información hará que el dispositivo se quede sin memoria) o en los costos de red (descargar mapas con datos celulares es caro).

Estas restricciones nos orillaron a diseñar un sistema que soporta datos de mapas del lado del cliente para aprovechar la mejora en la exactitud de la localización sin introducir presión innecesaria en la memoria.

¿Por qué es útil tener información del mapa del lado del cliente?

Mejora la navegación:

• Al entender la red de caminos y sus características, podemos mejorar nuestros algoritmos de redireccionamiento y de detección de rutas fuera del camino.
• La disponibilidad de la red celular no está garantizada. Con un mapa disponible en el dispositivo, podemos localizar y redireccionar a los conductores incluso cuando estén fuera de línea (por ejemplo, en túneles o áreas rurales).

Mejora el seguimiento de la localización:

• Hacer emparejamiento de mapas en el dispositivo permite que los modelos de localización sean recientes.
• Mover cómputos costosos de los servidores al cliente simplifica la arquitectura del servidor, reduce costos de hospedaje y reduce la latencia servidor-cliente.
• El acceso directo a datos de sensores de alta frecuencia mejora la calidad de la ubicación.

Ayuda a construir funcionalidades de seguridad para nuestros conductores:

• Notificando a nuestros conductores sobre sitios donde no está permitido dejar y recoger pasajeros basados en los bordes de las banquetas.
• Mostrando límites de velocidad.
• Enseñando elementos del mapa como semáforos y señales de alto.

Diseñando el sistema

Descompusimos el proyecto en tres componentes principales:

1. Generación liviana de mapas.
2. Plataforma del cliente en la capa de red para iOS y Android.
3. Biblioteca principal en C++.

Generación liviana de mapas

Para poder determinar el formato de la información de los mapas, su generación y su uso, dividimos el LyftMap completo en conjuntos pequeños de S2Cells construidas sobre la biblioteca S2Geometry. La unidad básica para los datos del LyftMap es un MapElement que guarda dos tipos de información:

1. Metadatos del camino para generar un grafo de la red de caminos.
2. Secuencias de segmentos para inferir restricciones de vueltas y evitar giros indebidos.

Cada S2Cell es una compilación de MapElements para una región, donde cada celda tiene un identificador numérico único. Partimos el mapa en celdas que abarcan aproximadamente 1x1 km (Fig. 2).

Fig 2. Celdas de nivel S2 sobre la región de San Francisco

Cuando el cliente intenta descargar la información del mapa del servidor, va a especificar el identificador de la celda y la versión del mapa. El servidor regresará el mapa serializado como S2CellElements.

Descargamos las celdas con base en la ubicación actual del usuario y construimos dinámicamente un grafo de red de caminos en memoria. Con este diseño, tenemos un grafo local construido del lado del cliente, brindando las mismas funcionalidades base de un grafo creado en el lado del servidor.

Plataforma del cliente en la capa de red (iOS y Android)

Después, creamos un servicio de backend, MapAttributes, que lee los elementos del mapa de DynamoDB con base en un índice geoespacial S2. GetElementssByCellID obtiene elementos de mapa serializados de Dynamo, los deserializa y los filtra con los tipos de elementos solicitados. Finalmente, los convierte en objetos S2CellElements para construir una respuesta.

Para mejorar la fiabilidad, reducir la latencia y reducir los costos de mantenimiento del servidor MapAttributes, usamos una CDN CloudFront para almacenar en caché las respuestas de MapAttributes. CloudFront regresará los resultados del borde del servidor en caché sin tener que llamar al servicios de MapAttributes. Si no se encuentra en caché, Cloudfront redirige la petición a MapAttributes vía Envoy y la respuesta se guarda en caché para futuras peticiones.

Para mantener constante la huella de memoria, sólo cargamos celdas cercanas a la ubicación actual. Para compensar la latencia de la carga de datos, mantenemos un buffer de celdas cercanas para tener suficiente información del mapa alrededor de la ubicación actual. En la figura 3 se muestra que encontramos la celda correspondiente a la ubicación, L, y la llamamos S0. Después, traemos las celdas vecinas a S0 y las llamamos S1. De igual manera, computamos a las celdas vecinas a las S1 y las llamamos S2. De esta forma, por cada actualización de la ubicación, generamos 13 celdas circundantes. Mientras cambia la ubicación del usuario, computamos nuevamente la lista de celdas.

Fig 3. Nivel de cómputo 0, 1, y 2 de celdas vecinas

Funcionalidad de la biblioteca principal

Una vez que el cliente obtiene las celdas de mapa deseadas del servidor, pasa esta información a través de una capa de interfaz a una biblioteca de localización de C++ (Fig. 4).

Rastreamos los elementos del mapa en un objeto MapDataManager y, tras generar las 13 celdas de mapa, activamos el cómputo del grafo de una red de caminos. Este proceso ocurre de forma asíncrona debido a las actualizaciones de ubicación que ocurren cuando nuevas lecturas del GPS llegan al dispositivo.

Cuando el MapDataManager completa la creación del roadNetworkGraph, pasamos un puntero compartido a nuestro LocationTracker, permitiendo que el sistema aproveche los diferentes modelos basados en mapas (Map-Based Models) para la localización.

Fig 4. Vista general de alto nivel de la biblioteca de localización

Con este diseño, mientras el usuario se mueve por el mundo físico, podemos generar de forma dinámica nuevos RoadNetworkGraphs de sus alrededores y actualizar nuestro LocationTracker cuando el siguiente grafo está listo (Fig. 5).

Fig 5. Prototipo de visualización de las celdas cargando dinámicamente mientras cambia la ubicación del usuario

Los conductores de Lyft generalmente operan en un área única de servicios, y su localidad es muy concentrada, por lo que es posible hacer descargas duplicadas de la misma información. Repetir descargas lleva a un uso excesivo de datos de red para nuestros conductores.

Para resolver este problema, agregamos una capa de caché SQLite en la memoria del dispositivo directamente en C++. SQLite fue nuestra base de datos predilecta gracias a su simplicidad y a su soporte nativo en las plataformas del cliente.

Este caché secundario nos permite guardar los datos de la localidad directamente en el dispositivo del conductor. Al persistir la información del mapa en disco, podemos guardar información entre sesiones, así que sólo tenemos que actualizar el caché cuando la información subyacente del mapa cambia.

Con base en un análisis de los patrones de manejo de conductores, determinamos que con menos de 15 MB de datos guardados en el dispositivo podemos lograr un gran porcentaje de aciertos del caché para la gran mayoría de los conductores de Lyft (Fig. 6).

Fig 6. Estadísticas del uso de celdas de los conductores

Analizando los resultados

Una vez que finalizamos los prototipos iniciales y los planes de diseño, llegó el tiempo de validar que todo estuviera funcionando como se esperaba.

Determinamos que la mejor métrica para el éxito sería rastrear qué tan seguido los clientes móviles tienen celdas de mapa en el dispositivo. En el release actual, conseguimos métricas que muestran una disponibilidad de datos de mapa para más del 99% de los conductores del grupo experimental.

También monitoreamos el desempeño del sistema de datos de mapas para asegurar que sólo use un poder de cómputo razonable. En la experimentación, alcanzamos sub 10 ms de latencia para el p99 de tiempo de cómputo de nuestros modelos de emparejamiento de mapas.

Después, investigamos cómo los modelos de mapa del cliente afectan a la calidad. La figura 7 muestra una simulación de mapa local, donde los puntos azules representan las ubicaciones brutas con un segundo de diferencia. Los puntos rojos reflejan las localizaciones obtenidas del mapa, centradas sobre los segmentos de camino tal y como se espera.

Fig 7. Ubicaciones crudas y ajustadas al mapa

También comparamos diferentes estrategias de localización. En la figura 8, graficamos ubicaciones filtradas por Kalman, en amarillo, contra ubicaciones ajustadas a las calles en el mapa, en rosa. Incluso con un modelo básico de ajuste al mapa sin heurística adicional, las ubicaciones rosas son una mejor representación de dónde está el conductor en el camino.

Fig 8. Ubicaciones filtradas por Kalman y ubicaciones obtenidas del ajuste a las calles en el mapa

Finalmente, investigamos el impacto del caché SQLite contra la tasa de descarga de datos del mapa. En la gráfica de la figura 9, ordenamos a los conductores por la cantidad de datos del mapa que descargan de la red con y sin caché. Ver el orden de magnitud de la reducción en descargas nos ayudó a validar que la base de datos está funcionando.

Fig 9. Tasa de descarga de mapa con y sin caché de SQLite

Conclusión

El proyecto para tener el mapa del lado del cliente es una inversión fundamental para nuestras capacidades de rastreo de ubicación en Lyft. Con este proyecto completado, pudimos descargar mapas de Lyft, crear redes de caminos en memoria, computar modelos de emparejamiento de mapas e inyectar ubicaciones de regreso al servidor, ¡todo del lado del cliente móvil!

Viendo hacia el futuro, estamos emocionados por desarrollar una mejor precisión en los modelos de localización móviles, implementar direccionamiento y redireccionamiento offline, e introducir nuevas características que hagan que la navegación de los conductores y el hallar caminos en el mundo físico sea más seguros y confiables.

¡Estamos contratando! lyft.com/careers