En ausencia de una respuesta de alguien en el equipo de Google Maps, me siento obligado, en base a mis credenciales que enumero al final de esta publicación, a actualizar mi respuesta para proporcionar más detalles y claridad. La publicación con ediciones de Iddo Gino ciertamente merece una buena cantidad de vistas y votos positivos, pero la publicación de Iddo aún subestima la complejidad de la tecnología de mapeo y navegación. Estoy publicando detalles aquí para aclarar cuánto más compleja es esta pregunta que un simple algoritmo de Dijkstra puede resolver. Dijkstra es solo una pequeña parte de ella. A * es aún menos importante. Para los aficionados a los algoritmos, todo lo que Dijkstra agrega a la tecnología de mapas es la idea de usar una cola prioritaria. (Disculpas, no puedo resistir esto: http://www.drdobbs.com/architect …).
Comencemos con la pregunta original: ¿Cómo funciona el algoritmo de Google Maps? La pregunta es engañosa porque los mapas y los sistemas de navegación tienen muchos algoritmos que incluyen:
- Algoritmos de indexación espacial y algoritmos de geometría computacional para organizar los datos del mapa y recuperarlos de manera eficiente.
- Algoritmos para dibujar mapas (por ejemplo, coordenadas de latitud y longitud del proyecto, rellenar los polígonos, nombres de lugares para calles, ciudades, negocios, parques, …).
- Algoritmos para comprender las consultas de los usuarios (NLU o NLP)
- Algoritmos para procesar señales GPS (en las cuales soy mucho menos experto que en otros temas aquí)
- Algoritmos para realizar lo que se llama geocodificación, convirtiendo direcciones en puntos (o polígonos) en un mapa.
- Algoritmos para realizar geocodificación inversa, convirtiendo puntos en direcciones usando algoritmos de punto en polígono (otro ejemplo de usar geometría computacional).
Llegaré a los algoritmos de cálculo de ruta, pero permítanme mencionar más de los otros aspectos complejos de los mapas y la navegación, especialmente aquellos relevantes para calcular rutas.
- Recopilación y organización de los datos: pueden provenir de muchas fuentes diferentes. Solo un ejemplo de un problema muy complejo que surge de eso es la geometría muy desordenada que resulta cuando las coordenadas del mapa de dos fuentes (latitud, longitud) están en ligero desacuerdo, especialmente polígonos y líneas. Además de los datos sobre carreteras, se necesitan datos sobre direcciones, negocios, parques, centros comerciales e instituciones.
- Iddo menciona “costos”. Sí, eso es importante y nada trivial por varias razones. Los costos son los “pesos” en los bordes del gráfico para usar la terminología de la teoría de gráficos, pero calcular esos pesos con precisión es complejo. Estas son algunas partes complejas de la determinación de costos:
- Recopilar y utilizar datos de tráfico para que sea menos probable que se elijan carreteras lentas en el cálculo de la ruta.
- Estimación de costos futuros cuando la ruta es larga y se maneja en el futuro.
- Tiempo para viajar a través de intersecciones de caminos. Todos los productos de navegación tienen en cuenta las diferencias de tiempo necesarias para realizar diferentes giros en una intersección porque los tiempos pueden variar significativamente: los giros a la izquierda generalmente tardan mucho más que los giros a la derecha, pero no siempre. Y las muchas y complejas variedades de configuraciones de intersecciones hacen que este sea un problema difícil.
- Los parámetros adicionales a considerar son los costos de combustible y la complejidad de la ruta. Si una ruta con pocas vueltas es solo un poco más larga que una ruta con muchas vueltas, es probable que sea una mejor opción para el conductor.
Mencioné las intersecciones. El siguiente diagrama puede proporcionar una idea de lo difícil que es lidiar con las intersecciones porque no se permiten todos los giros. Las restricciones que se muestran deben estar codificadas en el gráfico utilizado por el algoritmo de cálculo de ruta.
Bien, hablaré sobre los algoritmos de cálculo de ruta, pero recuerden que es solo un componente de muchos en el mapa y la tecnología de navegación. Como algunos han mencionado, calcular una ruta a lo largo de un mapa grande puede ser costoso y lento. Por lo tanto, se necesitan optimizaciones de Dijkstra:
- UNA*. A * ha sido un concepto muy importante en la IA tradicional, y muchos algoritmos de cálculo de ruta lo incluyen. Pero, en mi experiencia en el desarrollo de algoritmos, A * ofrece solo una pequeña mejora en el rendimiento, quizás un 30%. Para otras aplicaciones en IA, los gráficos pueden ser muy diferentes de tal manera que el A * ofrece una ventaja de rendimiento mayor, pero no mucho para las redes de carreteras.
- Bidireccional. Esta es una optimización algo más efectiva y casi todos los algoritmos de cálculo de ruta en la industria la usan, pero no principalmente por la ventaja de rendimiento que brinda. Significa que la ruta se calcula tanto hacia adelante desde el origen (con Dijkstra, A *, enrutamiento basado en el alcance, jerarquías de carreteras, jerarquías de contracción u otros métodos) y hacia atrás desde el destino. Al igual que A *, la técnica reduce el área buscada, pero lo que es más importante, algunos algoritmos más importantes (los que usan jerarquías de carreteras) requieren que funcione. Pero los cálculos de rutas bidireccionales traen sus propias complicaciones: el algoritmo debe determinar cuándo las dos búsquedas se han encontrado en un punto en una ruta óptima o casi óptima y eso es más complejo de lo que parece.
- Usando la jerarquía de la red de carreteras. Esta es la optimización de rendimiento más importante y se utilizó hace mucho tiempo en compañías como Etak de una manera práctica pero no académicamente formal. Mi invento y mi trabajo sobre el enrutamiento basado en el alcance llevaron el concepto a la academia y generaron más algoritmos de producción de investigaciones como las jerarquías de carreteras y las jerarquías de contracción. Desde que el autor principal de los artículos sobre Jerarquías de autopistas, Peter Sanders, dio una charla en Google, se ha especulado que Google ha utilizado las Jerarquías de autopistas:
- Atajos Este concepto reemplaza las secuencias de aristas con aristas simples en la preparación del gráfico. El concepto se usó en la industria antes de publicar mi artículo y lamento no tener espacio para mencionarlo en Trabajo adicional en mi documento. La gente de Karlsruhe en Alemania aprovechó al máximo los atajos en las Jerarquías de Carreteras y las Jerarquías de Contracción.
- Otros problemas que afectan los algoritmos:
- Incluso si ignoramos el rendimiento, Dijkstra no resuelve todos los problemas. Un problema es la dependencia del tiempo. A veces, los algoritmos deben permitir que los costos en los bordes cambien dependiendo del tiempo que la ruta lleve al usuario a un punto particular en las carreteras.
- Por ejemplo, la carretera podría estar cerrada en un momento determinado.
- O se podría predecir que el tráfico empeorará.
La mayoría de los algoritmos rápidos requieren procesamiento en los datos del mapa antes de que se calculen las rutas, pero algunos de los datos que afectan ese “preprocesamiento” cambian rápidamente, por ejemplo, datos de tráfico. Es muy difícil determinar qué parte del problema se resuelve en el preprocesamiento y qué parte se resuelve durante el cálculo de la ruta y cómo se resuelve.
Este diagrama muestra un poco de historia de los algoritmos:
Una lista final de complejidades que enfrentan las tecnologías de mapas y navegación:
- Orientación: ¿cómo se instruye al usuario en la ruta y cuándo?
- Detectar cuando el conductor se ha salido de la ruta y necesita una nueva ruta.
- Requisitos especiales según el tipo de transporte.
- Bicicletas que no pueden usar legalmente todos los caminos.
- Vehículos eléctricos que deben cargarse a lo largo de la ruta.
- Uso de trenes y autobuses.
- Viajes que combinan diferentes modos de transporte, incluido caminar
¿Dónde estacionará el vehículo? Eso no es trivial en centros urbanos como San Francisco.
¿Qué sucede si el dispositivo de navegación (por ejemplo, un teléfono celular) solo puede contener datos de mapas para áreas cercanas pero el conductor está en un viaje largo que a veces sale de la red celular?
Mantener los datos del mapa actualizados en teléfonos celulares.
Diferencias entre estados y países que afectan
- Reglas para el uso de carreteras.
- Lenguaje y sistemas de direccionamiento soportados por geocodificación.
Datos de mapas en 3D: organización y visualización. Complejos algoritmos gráficos en 3D aquí.
Mis credenciales:
- Trabajé en una de las primeras compañías en proporcionar mapas digitales para los conductores, calcular rutas para ellos y usar el GPS para proporcionar orientación: Etak.
- Trabajé en el inicio, Airflash, que desarrolló algunas de las primeras aplicaciones de mapas y navegación para teléfonos celulares.
- Escribí el artículo antes mencionado para el Dr. Dobbs.
- Desarrollé algoritmos de cálculo de ruta en Wavemarket (ahora llamados Location Labs)
- Escribí un artículo muy citado e importante sobre el tema del cálculo de ruta. Aquí está toda la historia: la respuesta de Ron Gutman a ¿Cuál es el mejor algoritmo de programación que hayas creado?
- Trabajé en mapeo en Yahoo.
- Trabajé en mapas y navegación usando GPS y teléfonos móviles en Telenav, donde leí muchos documentos sobre el tema del cálculo de rutas.
- Algunas patentes relacionadas.
