Decision-based map-agnostic navigation routing

• US 10,317,222 B2
• Filed: 06/22/2015
• Issued: 06/11/2019
• Est. Priority Date: 06/22/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Maischberger, Mirko, Rolf, Daniel
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): King, Rodney P
• Application Number:
  US14/745,640
• Publication Number:
  US 20160370192A1
• Time in Patent Office: 1,450 Days
• 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: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3638 including 3D objects and buildings three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05

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 a sequence of path decisions 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, between a starting location and a destination location;

determining, using a processor, a navigation route from the received route request;

generating an encoded navigation route comprising a sequence of path decisions with a path decision at each intersection between the starting location and the destination location, each path decision having a pair of values representing a number of outlets at the respective intersection and an outlet to-be-taken at the respective intersection; and

transmitting the encoded navigation route to the navigation device,

whereby a map agnostic navigation route is encoded and transmitted.

2. The method of claim 1, further comprising:

receiving an updated route request from the navigation device, the updated route request providing at least one unmatched path decision between a map version of the navigation device and a map version of the processor;

determining, using the processor, an updated navigation route avoiding the at least one unmatched path decision;

encoding the updated navigation route with an updated sequence of path decisions; and

transmitting the encoded updated navigation route to the navigation device.

3. 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.

4. 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.

5. The method of claim 4, wherein the identifying comprises matching latitude and longitude values from midpoints of the starting location and destination location path segments from the navigation device with latitude and longitude values from midpoints of path segments in the map version of the processor.

6. The method of claim 1, wherein the value of the outlet to-be-taken is selected from a set of values comprising whole numbers from one to the number of outlets at the respective intersection.

7. The method of claim 1, wherein the sequence of path decisions do not reference a link identifier.

8. The method of claim 1, wherein the path decisions are independent of link identifiers.

9. The method of claim 1, wherein the path decisions are non-reliant on link identifiers.

10. A method comprising:

requesting, using a navigation device, a navigation route between a starting location and a destination location;

receiving an encoded navigation route based on the request, the encoded navigation route comprising a sequence of path decisions comprising a path decision at each intersection between the starting location and the destination location, each path decision having a pair of values representing a number of outlets at the respective intersection and an outlet to-be-taken at the respective intersection;

analyzing the encoded navigation route, using a processor of the navigation device, to determine whether the sequence of path decisions is compatible with a map version of the navigation device; and

decoding and displaying the navigation route when the sequence of path decisions is compatible with the map version.

11. The method of claim 10, further comprising:

requesting an updated route request when at least one path decision in the sequence of path decisions does not match with a corresponding path decision in the map version of the navigation device, the updated route request identifying the at least one unmatched path decision;

receiving an updated encoded navigation route, the updated encoded navigation route comprising an updated sequence of path decisions that avoids the at least one unmatched path decision; and

analyzing the updated encoded navigation route, using the processor of the navigation device, to determine whether the updated sequence of path decisions is compatible with the map version of the navigation device.

12. The method of claim 10, wherein the processor analyzes the encoded navigation route using a Dijkstra'"'"'s algorithm.

13. The method of claim 10, wherein the analyzing of the encoded navigation route comprises assigning costs for each path decision in the sequence of path decisions,

wherein the encoded navigation route is rejected if a sum of the costs is too large.

14. The method of claim 13, wherein a cost of a path decision is equal to 0 when an intersection in the map version of the navigation device has a same number of outlets as a map version of a provider of the encoded navigation route, or

wherein the cost of the path decision is equal to −

log(2^(−

M)) when the intersection in the map version of the navigation device has a different number of outlets as the map version of the provider, wherein M equals to that difference, or

wherein the cost of the path decision is equal to log(N) when the intersection is not present in the map version of the navigation device or in the map version of a provider, wherein N equals a number of outlets other than U-turns in the map version having the intersection.

15. 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 between a starting location and a destination location;

determine a navigation route;

encode the navigation route with a sequence of path decisions comprising a link identifier agnostic path decision at each intersection between the starting location and the destination location, each path decision having a pair of values representing a number of outlets at the respective intersection and an outlet to-be-taken at the respective intersection; and

transmit the encoded navigation route to the navigation device.

16. The apparatus of claim 15, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform:

receive an updated route request from the navigation device, the updated route request providing at least one unmatched path decision between a map version of the navigation device and a map version of the apparatus;

determine an updated navigation route avoiding the at least one unmatched path decision;

encode the updated navigation route with an updated sequence of path decisions; and

transmit the encoded updated navigation route to the navigation device.

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

18. The apparatus of claim 15, 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.

19. The apparatus of claim 18, wherein the identification of corresponding path segments comprises matching latitude and longitude values from midpoints of the starting location and destination location path segments from the navigation device with latitude and longitude values from midpoints of path segments in the map version of the processor.

20. A navigation device 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 navigation device to at least perform;

request a navigation route between a starting location and a destination location;

receive an encoded navigation route based on the request, the encoded navigation route comprising a sequence of path decisions comprising a link identifier agnostic path decision at each intersection between the starting location and the destination location, each path decision having a pair of values representing a number of outlets at the respective intersection and an outlet to-be-taken at the respective intersection; and

identify whether the sequence of path decisions is compatible with a map version of the navigation device.

21. The navigation device of claim 20, wherein the at least one memory and the computer program code are configured to cause the navigation device to further perform:

request an updated route request when at least one path decision in the sequence of path decisions does not match with a corresponding path decision in the map version of the navigation device, the updated route request identifying the at least one unmatched path decision;

receive an updated encoded navigation route, the updated encoded navigation route comprising an updated sequence of path decisions that avoids the at least one unmatched path decision; and

identify whether the updated sequence of path decisions is compatible with the map version of the navigation device.

22. The navigation device of claim 20, wherein the processor analyzes the encoded navigation route using a Dijkstra'"'"'s algorithm.

23. The navigation device of claim 20, wherein the analyzing of the encoded navigation route comprises assigning costs for each path decision in the sequence of path decisions,

wherein the encoded navigation route is rejected if a sum of the costs is too large.

24. The navigation device of claim 23, wherein a cost of a path decision is equal to 0 when an intersection in the map version of the navigation device has a same number of outlets as a map version of a provider of the encoded navigation route, or

wherein the cost of the path decision is equal to −

log(2^(−

M)) when the intersection in the map version of the navigation device has a different number of outlets as the map version of the provider, wherein M equals to that difference, or

wherein the cost of the path decision is equal to log(N) when the intersection is not present in the map version of the navigation device or in the map version of a provider, wherein N equals a number of outlets other than U-turns in the map version having the intersection.