Dispositivo de navegación y método para crear datos para acelerar la búsqueda de una ruta.

Un método de creación de datos de mapa, que incluye datos de aceleración de búsqueda dispuestos para aumentar la velocidad a la que se puede planificar una ruta a través de un mapa electrónico,

usando al menos un aparato de procesamiento para procesar el mapa electrónico que comprende una pluralidad de segmentos navegables cada uno que representa segmentos de una ruta navegable en el área cubierta por el mapa, el método que comprende:

dividir el mapa en una pluralidad de regiones jerárquicas (1906) que pertenecen a al menos un nivel más tosco (600) y un nivel de más detalle colindante (602, 604, 606, 608) de manera que cada segmento navegable se categoriza en al menos una región en cada uno de los niveles más toscos y de más detalle y en donde cualquier región del nivel más tosco contiene una pluralidad de regiones del nivel de más detalle;

determinar, para una región de destino dada, la extensión de un área de visibilidad (1908), que comprende al menos la región de nivel más tosco que contiene la región de destino, valorando si las regiones cercanas a la región de nivel más tosco que contienen la región de destino se deberían añadir al área de visibilidad y añadir esas regiones si la valoración es positiva;

determinar, para los segmentos navegables en el área de visibilidad de la región de destino, si un segmento navegable es parte de una ruta de coste mínimo a la región de destino (1910), en donde la búsqueda realizada para hacer dicha determinación se restringe por el área de visibilidad;

disponer los datos de aceleración de búsqueda para comprender una información que indica dicha determinación para los segmentos navegables; y

generar los datos de mapa.

Dispositivo de navegación y método para crear datos para acelerar la búsqueda de una ruta Campo de la invención

La presente invención se refiere a un método informatizado de generación de datos de mapa y sistemas relacionados. En particular, pero no exclusivamente, el método de generación de datos de mapa se usa para facilitar la planificación de ruta entre al menos dos puntos según una función de coste predeterminada. Las realizaciones de la invención pueden generar datos de aceleración de búsqueda que, cuando se usan en una planificación de ruta, reducen el tiempo que lleva generar una ruta.

Antecedentes de la invención

Los dispositivos de planificación de ruta (a menudo denominados como Nav. por Satélite, Dispositivos de Navegación Portátiles (PND) o similares) junto con los sitios web accesibles a través de la Red Informática Mundial (WWW) tales como http://routes.tomtom.com/ son bien conocidos y permiten a un usuario de los mismos planificar una ruta entre dos puntos. Tal tecnología se puede denominar genéricamente como planificación de ruta electrónica o sólo planificación de ruta.

Los datos de mapas de tal planificación de ruta electrónica llegan de vendedores de mapas especialistas tales como Tele Atlas NV. Cuando se realiza en un PND tal planificación de ruta típicamente se usan datos de ubicación de un sistema de GPS. No obstante, otras aplicaciones pueden permitir a un usuario introducir su ubicación u otro punto a ser considerado para propósitos de planificación de ruta.

Tales datos de mapa comprenden una pluralidad de carreteras (y otros trayectos navegables) que se pueden describir como líneas - es decir vectores o segmentos de carretera (por ejemplo un punto de inicio, punto final, dirección de una carretera, con una carretera entera que está compuesta de muchos cientos de tales segmentos, cada uno definido únicamente por parámetros de dirección de punto de inicio/punto final). Un mapa es entonces un conjunto de tales vectores de carretera, datos asociados con cada vector (límite de velocidad; dirección de viaje, etc.) más puntos de interés (POI), más nombres de carreteras, más otros rasgos geográficos como límites de parques, límites de ríos, etc., todos los cuales se definen in términos de vectores. Todos los rasgos de mapa (por ejemplo vectores de carretera, POI, etc.) se definen típicamente en un sistema de coordenadas que corresponde con o se refiere al sistema de coordenadas GPS, permitiendo que una posición del dispositivo que se determina a través del sistema de GPS sea localizada sobre la carretera relevante mostrada en un mapa y para que una ruta óptima sea planificada a un destino.

Tales datos de mapa pueden ser extensos. Ello es conocido para mapas que cubren áreas que tienen por encima de 12.. vectores y un ejemplo de tales datos de mapa sería un mapa que cubriría el área de Europa y Rusia. Por tanto, los datos de mapa son complejos y puede llevar mucho tiempo. También, se conoce que tal planificación de ruta es un compromiso entre precisión y tiempo.

La técnica anterior que ha considerado ideas en mejorar la velocidad a la que puede darse el encaminamiento incluye la US 6.636.8 que trata refinamientos de la estrategia de búsqueda mejor-primero A* adecuada para tamaños de mapa mucho más pequeños tales como la red de autopistas de Europa Occidental (que tiene aproximadamente 4. vectores).

La tesis doctoral titulada Engineering and Augmenting Route Planning Algorithms de Daniel Delling (XP2612394) trata técnicas de aceleración para encaminamiento en escenarios aumentados, es decir dependientes del tiempo y de criterios múltiples. Una técnica tal se conoce como SHARC (Atajos + Marcas de Arco) y se describe además en el artículo periodístico titulado SHARC: Fast and Robust unidirectional Routing de Reinhard Bauer et al. (XP2612373) y el artículo periodístico titulado Time-Dependent SHARC Routing de Dan Halperin et al. (XP191727).

Compendio de la invención

Según un primer aspecto de la invención se proporciona un método de creación de datos de mapa según la reivindicación 1.

Tal método se considera ventajoso debido a que permite que los datos de aceleración de búsqueda sean calculados más rápido que los métodos de la técnica anterior. A su vez, los datos de aceleración de búsqueda se consideran ventajosos dado que permiten que la planificación de ruta que usa los datos de mapa sea realizada más rápido.

Una ventaja adicional de tal método es que el uso del área de las inmediaciones permite que el espacio de búsqueda, usado para generar los datos de aceleración de búsqueda, sea restringido y por tanto que la velocidad a la que se pueden crear los datos de aceleración de búsqueda sea aumentada.

Una ventaja adicional de tal método es que se puede aumentar la velocidad a la que se puede realizar la

planificación de ruta usando los datos de aceleración de búsqueda. Los datos de aceleración de búsqueda se pueden considerar como un cartel a la región destino. Por ello aumentar el número de regiones que contienen datos de aceleración de búsqueda a regiones contenidas dentro del área de las inmediaciones aumenta el número de regiones que contienen `carteles a la región destino. Por lo tanto, se puede aumentar el tiempo para generar los datos de aceleración de búsqueda aunque el rendimiento de la planificación de ruta que usa los datos de aceleración de búsqueda también se puede aumentar.

La valoración en cuanto a si las regiones están cercanas a la región de nivel más tosco que contiene la región de destino se puede basar en un criterio predeterminado. Este criterio predeterminado puede ser uno cualquiera o una combinación de los siguientes: distancia de gráfico-teórico, distancia geográfica, tiempo de viaje, consumo de combustible y/o emisiones de C2. De hecho, en algunas realizaciones más cercanas se puede determinar que son regiones que son adyacentes a la región de nivel más tosco que contiene la región destino.

Las regiones añadidas al área de visibilidad pueden comprender al menos una de las siguientes: una o más regiones del nivel más tosco y una parte de una o más regiones del nivel más tosco.

Típicamente los datos de aceleración de búsqueda se calculan como una pluralidad de vectores de bits. Algunas realizaciones de la invención pueden calcular y pueden indicar a través de un bit de los datos de aceleración de búsqueda si un segmento de carretera es parte o no de una ruta de coste mínimo desde un segmento navegable de origen a una región de destino.

Los expertos apreciarán que generalmente cada segmento navegable o puede ser un nodo, dentro de los datos de mapa que tiene asociado con el mismo la función que varía con el tiempo. Por ejemplo, la función que varía con el tiempo puede comprender la velocidad media en el segmento navegable en varios intervalos de tiempo. Por ejemplo, la velocidad media puede ser especificada en intervalos de 5 minutos o similares.

Convenientemente, la red central se genera extrayendo segmentos navegables para los cuales se pueden recuperar más tarde los datos de aceleración de búsqueda. Tal método es ventajoso dado que permite que los datos de aceleración de búsqueda sean determinados para sustancialmente todos los segmentos navegables dentro del mapa electrónico por ello planificando la ruta a ser acelerada desde cualquier segmento navegable dentro del mapa.

Algunas realizaciones de la invención pueden utilizar una cualquiera o más de las siguientes técnicas para eliminar segmentos navegables del mapa electrónico anterior a la creación de los datos de aceleración de búsqueda:

cumplir un criterio predeterminado relacionado con la propiedad de la carretera;

eliminar segmentos navegables de la red que forman parte de la red que son suficientemente pequeños según algún criterio predeterminado y que podrían ser desconectados del resto de la red eliminando un conjunto de segmentos navegables que cumplen algún criterio predeterminado adicional;

colapsar nodos, lo cual ocurre en cruces entre segmentos navegables, uno sobre otro en situaciones predeterminadas; y

colapsar nodos uno sobre otro si tienen dos o menos de dos segmentos navegables conectados al mismo.

Tales técnicas se consideran ventajosas dado que reducen el número de segmentos navegables que necesitan ser considerados durante la generación de los datos de aceleración de búsqueda lo que aumenta, quizás significativamente, la velocidad a la que se pueden crear los datos de aceleración de búsqueda.

Adicionalmente o alternativamente, las realizaciones de la invención pueden utilizar una cualquiera o más de las siguientes técnicas... [Seguir leyendo]

1. Un método de creación de datos de mapa, que incluye datos de aceleración de búsqueda dispuestos para aumentar la velocidad a la que se puede planificar una ruta a través de un mapa electrónico, usando al menos un aparato de procesamiento para procesar el mapa electrónico que comprende una pluralidad de segmentos navegables cada uno que representa segmentos de una ruta navegable en el área cubierta por el mapa, el método que comprende:

dividir el mapa en una pluralidad de regiones jerárquicas (196) que pertenecen a al menos un nivel más tosco (6) y un nivel de más detalle colindante (62, 64, 66, 68) de manera que cada segmento navegable se categoriza en al menos una región en cada uno de los niveles más toscos y de más detalle y en donde cualquier región del nivel más tosco contiene una pluralidad de regiones del nivel de más detalle;

determinar, para una región de destino dada, la extensión de un área de visibilidad (198), que comprende al menos la región de nivel más tosco que contiene la región de destino, valorando si las regiones cercanas a la región de nivel más tosco que contienen la región de destino se deberían añadir al área de visibilidad y añadir esas regiones si la valoración es positiva;

determinar, para los segmentos navegables en el área de visibilidad de la región de destino, si un segmento navegable es parte de una ruta de coste mínimo a la región de destino (191), en donde la búsqueda realizada para hacer dicha determinación se restringe por el área de visibilidad;

disponer los datos de aceleración de búsqueda para comprender una información que indica dicha determinación para los segmentos navegables; y

generar los datos de mapa.

2. Un método según la reivindicación 1, en donde el procesamiento de un segmento de navegación para determinar si el segmento navegable que es parte de una ruta de coste mínimo comprende la realización de una búsqueda inversa desde la región de destino de vuelta hacia el segmento navegable e Incluye sustancialmente solamente los segmentos navegables en el área de visibilidad.

3. Un método según la reivindicación 1 o 2 en el que la valoración en cuanto a si las regiones están cerca de la región de nivel más tosco que contiene la región de destino está basada en un criterio predeterminado que comprende al menos uno de: distancia de gráfico teórico, distancia geográfica, tiempo de recorrido, consumo de combustible y emisión de C2.

4. Un método según la reivindicación 1 o 2, en donde una función que varía con el tiempo (752) está asociada con al menos algún y generalmente cada, segmento navegable.

5. Un método según la reivindicación 4, en donde la función que varía con el tiempo (752) asociada con un segmento navegable representa la velocidad media en el segmento navegable en una pluralidad de Intervalos de tiempo.

6. Un método según cualquier reivindicación precedente, que comprende:

reducir el número de segmentos navegables a ser considerados en la creación de los datos de aceleración de búsqueda extrayendo segmentos para formar una red central de segmentos navegables (192, 194).

7. Un método según la reivindicación 6 en el que los segmentos navegables se extraen del mapa electrónico (192, 194) anterior a la creación de los datos de aceleración de búsqueda según uno cualquiera o más de los siguientes criterios:

(i) extraer segmentos navegables que cumplen un criterio predeterminado relacionado con la propiedad de la

carretera;

(ii) colapsar nodos, lo que ocurre en confluencias entre segmentos navegables, unos en otros en situaciones predeterminadas; y

(iii) colapsar nodos unos sobre otros si tienen dos o menos de dos segmentos navegables conectados a los

mismos.

8. Un método según cualquier reivindicación precedente, en donde la pluralidad de segmentos navegables del mapa electrónico cada uno tiene una pluralidad de nodos asociados con el mismo y cada uno tiene al menos un atributo asociado que representa un parámetro de la ruta navegable, el al menos un atributo asociado con un segmento navegable incluye cualquiera de los siguientes:

(i) el tipo del segmento navegable;

(¡i) la velocidad media a lo largo del segmento navegable;

(i¡¡) la longitud del segmento navegable; y

(iv) la conectividad del segmento navegable a otros segmentos navegables,

y en donde la categorización de cada uno de los segmentos navegables usa una valoración del al menos un atributo para asegurar que los nodos asociados con los segmentos navegables están equilibrados a través de las regiones del mapa electrónico.

9. Un método según cualquier reivindicación precedente, en donde la ruta de coste mínimo se determina según uno de los siguientes criterios de coste: la distancia más corta, el tiempo de viaje más corto; el de menos impacto ambiental; el de menos combustible usado; y el de menos CO2 generado.

1. Un método según cualquier reivindicación precedente, que comprende:

determinar, para al menos alguno de los segmentos navegables, si un segmento navegable es parte de una ruta de coste mínimo a la región de destino según un primer criterio de coste y si el segmento navegable es parte de una ruta de coste mínimo a la región de destino según un segundo criterio de coste.

11. Un método según cualquier reivindicación precedente, en donde los datos de mapa generados comprenden un fichero lateral que incluye los datos de aceleración de búsqueda, el fichero lateral que está asociado con el mapa electrónico usado para generar el fichero lateral.

12. Un dispositivo informático dispuesto para realizar el método de cualquiera de las reivindicaciones precedentes.

13. Un medio legible por ordenador que contiene instrucciones que cuando se leen en una máquina hacen a la máquina realizar el método de cualquiera de las reivindicaciones precedentes.

14. Un dispositivo de navegación dispuesto para generar una ruta a través de un mapa electrónico a un destino usando un procesador del mismo para analizar datos de mapa, el dispositivo de navegación que comprende:

un mapa electrónico que comprende una pluralidad de segmentos navegables que representan segmentos de una ruta navegable en el área cubierta por el mapa, en donde el mapa se divide en una pluralidad de regiones jerárquicas que pertenecen a al menos un nivel más tosco y un nivel de más detalle colindante de manera que cada segmento navegable se categoriza en al menos una región en cada uno de los niveles más toscos y de más detalle y en donde cualquier región del nivel más tosco contiene una pluralidad de regiones del nivel de más detalle; y

datos de aceleración de búsqueda que Indican si un segmento navegable es parte de una ruta de coste mínimo a una reglón, los datos de aceleración de búsqueda para una región del nivel de más detalle que se restringen a datos que indican si un segmento navegable dentro de un área de visibilidad de la región de nivel de más detalle es parte de una ruta de coste mínimo a la reglón, el área de visibilidad que comprende la región de nivel más tosco que contiene la región de nivel de más detalle y cualquiera de las regiones determinadas que están cerca de la región de nivel más tosco;

en donde el procesador está dispuesto para:

realizar una búsqueda de ruta a través del mapa electrónico;

realizar, en un cálculo de coste en los nodos procesados durante la búsqueda los cuales representan segmentos navegables en el mapa electrónico, una valoración de si los segmentos navegables conectados a esos nodos están marcados, dentro de los datos de aceleración de búsqueda, como que son parte de una ruta de coste mínimo; y

si hay tales segmentos navegables explorar solamente esos segmentos navegables.

15. Un método de suministro de la planificación de ruta proporcionado por el dispositivo de navegación de la reivindicación 14.