Midpoint-based map-agnostic navigation routing

Patent metadata

Field	Value
Publication number	US-9933269-B2
Application number	US-201514745652-A
Country	US
Kind code	B2
Filing date	Jun 22, 2015
Priority date	Jun 22, 2015
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

Systems, apparatuses, and methods are provided for determining a navigation route. A route is requested by a navigation device between a starting location and a destination location. The route request is received by an external processor for analysis. A navigation route is determined by the external processor and its associated map version. The determined navigation route is then encoded with geographic data for each path segment along the route. The encoded navigation route is transmitted to the navigation device.

First claim

What is claimed is:

1. A method comprising:
receiving a route request from a navigation device, the route request having a starting location and a destination location;
determining, using a processor, a navigation route from the received route request using a map version of the processor, wherein the navigation route comprises a plurality of path segments;
encoding, using the processor, the navigation route with geographic data for each path segment of the plurality of path segments along the navigation route, the geographic data comprising latitude and longitude values at a midpoint of each path segment of the plurality of path segments, wherein each midpoint refers to a position on the respective path segment halfway between two ends of the respective path segment as measured in a direction of travel along the path segment, and wherein the encoded navigation route includes a routing sequence of midpoints of the plurality of path segments; and
transmitting the encoded navigation route to the navigation device, wherein the navigation device is configured to decode and use the encoded navigation route when a map version of the navigation device is a same version as the map version of the processor and when the map version of the navigation device is a different version from the map version of the processor.

2. A method comprising:
receiving a route request from a navigation device, the route request having a starting location and a destination location;
determining, using a processor, a navigation route from the received route request using a map version of the processor, wherein the navigation route comprises a plurality of path segments;
encoding, using the processor, the navigation route with geographic data for each path segment of the plurality of path segments along the navigation route, the geographic data comprising latitude and longitude values at a midpoint of each path segment of the plurality of path segments, wherein each midpoint refers to a position on the respective path segment halfway between two ends of the respective path segment as measured in a direction of travel along the path segment, and wherein the encoded navigation route includes a routing sequence of midpoints of the plurality of path segments;
transmitting the encoded navigation route to the navigation device;
receiving an updated route request from the navigation device, the updated route request providing at least one unmatched path segment between the map version of the navigation device and the map version of the processor;
determining, using the processor, an updated navigation route avoiding the at least one unmatched path segment;
encoding the updated navigation route with geographic data comprising latitude and longitude values for each midpoint of each path segment along the updated navigation route; and
transmitting the encoded updated navigation route to the navigation device.

3. The method of claim 1 , wherein the geographic data further comprises z-level data representing a relative vertical location for each path segment from other potential path segments located above or below each respective path segment.

4. The method of claim 1 , wherein the navigation route is determined based on real-time traffic data, historical traffic data, forecasted traffic data, map speed data, or combinations thereof.

5. The method of claim 1 , further comprising, prior to determining the navigation route:
identifying corresponding path segments in the map version of the processor for the starting location and the destination location received from the navigation device.

6. An apparatus comprising:
at least one processor; and
at least one memory including computer program code for one or more programs; the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:
receive, from a navigation device, a route request having a starting location and a destination location;
determine a navigation route from the received route request using a map version of the apparatus, wherein the navigation route comprises a plurality of path segments;
encode the navigation route with geographic data for each path segment of the plurality of path segments along the navigation route, the geographic data comprising latitude and longitude values at a midpoint of each path segment of the plurality of path segments, wherein each midpoint refers to a position on the respective path segment halfway between two ends of the respective path segment as measured in a direction of travel along the path segment, and wherein the encoded navigation route includes a routing sequence of midpoints of the plurality of path segments; and
transmit the encoded navigation route to the navigation device, wherein the navigation device is configured to decode and use the encoded navigation route when a map version of the navigation device is a same version as the map version of the apparatus and when the map version of the navigation device is a different version from the map version of the processor.

7. An apparatus comprising:
at least one processor; and
at least one memory including computer program code for one or more programs; the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform:
receive, from a navigation device, a route request having a starting location and a destination location;
determine a navigation route from the received route request using a map version of the apparatus, wherein the navigation route comprises a plurality of path segments;
encode the navigation route with geographic data for each path segment of the plurality of path segments along the navigation route, the geographic data comprising latitude and longitude values at a midpoint of each path segment of the plurality of path segments, wherein each midpoint refers to a position on the respective path segment halfway between two ends of the respective path segment as measured in a direction of travel along the path segment, and wherein the encoded navigation route includes a routing sequence of midpoints of the plurality of path segments;
transmit the encoded navigation route to the navigation device;
receive an updated route request from the navigation device, the updated route request providing at least one unmatched path segment between the map version of the navigation device and the map version of the apparatus;
determine an updated navigation route avoiding the at least one unmatched path segment;
encode the updated navigation route with geographic data comprising latitude and longitude values for each midpoint of each path segment along the updated navigation route; and
transmit the encoded updated navigation route to the navigation device.

8. The apparatus of claim 6 , wherein the geographic data further comprises z-level data representing a relative vertical location for each path segment from other potential path segments located above or below each respective path segment.

9. The apparatus of claim 6 , wherein the navigation route is determined based on real-time traffic data, historical traffic data, forecasted traffic data, map speed data, or combinations thereof.

10. The apparatus of claim 6 , wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform, prior to determining the navigation route,
identify corresponding path segments in the map version of the apparatus for the starting location and the destination location received from the navigation device.

11. The method of claim 1 , wherein the geographic data further compri

Assignees

• Here Global Bv

Inventors

• Maischberger Mirko
• Rolf Daniel

Classifications

• G08G1/096816

  where the complete route is transmitted to the vehicle at once · CPC title

• G01C21/34 Primary

  Route searching; Route guidance · CPC title

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G08G1/09

  Arrangements for giving variable traffic instructions ({railroad crossing signals B61L; reflectors E01F, G08B}; indicating arrangements for variable information by selection or combination of individual elements G09F9/00) · CPC title