Decision-based map-agnostic navigation routing

Patent metadata

Field	Value
Publication number	US-10317222-B2
Application number	US-201514745640-A
Country	US
Kind code	B2
Filing date	Jun 22, 2015
Priority date	Jun 22, 2015
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

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.

First claim

What is claimed is:

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 se

Assignees

• Here Global Bv

Inventors

• Maischberger Mirko
• Rolf Daniel

Classifications

• 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

• G01C21/3638

  including 3D objects and buildings (three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05) · CPC title

• G01C21/32

  Structuring or formatting of map data · CPC title

• G01C21/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 title