Midpoint-based map-agnostic navigation routing

• US 9,933,269 B2
• Filed: 06/22/2015
• Issued: 04/03/2018
• Est. Priority Date: 06/22/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Maischberger, Mirko, Rolf, Daniel
• Primary Examiner(s): McPherson, James M
• Application Number:
  US14/745,652
• Publication Number:
  US 20160370193A1
• Time in Patent Office: 1,016 Days
• Field of Search: None
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/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 Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once

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.

Claims

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.

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.

11. The method of claim 1, wherein the geographic data further comprises z-level data representing a relative vertical location for each midpoint of a respective path segment.

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.

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.

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.

12. The apparatus of claim 6, wherein the geographic data further comprises z-level data representing a relative vertical location for each midpoint of a respective path segment.

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.