Decision-Based Map-Agnostic Navigation Routing

Patent metadata

Field	Value
Publication number	US-2016370192-A1
Application number	US-201514745640-A
Country	US
Kind code	A1
Filing date	Jun 22, 2015
Priority date	Jun 22, 2015
Publication date	Dec 22, 2016
Grant date	—

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; encoding the navigation route with 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; and transmitting the encoded navigation route to the navigation device.

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 . 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; and 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.

7 . The method of claim 6 , 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.

8 . The method of claim 6 , wherein the processor analyzes the encoded navigation route using a Dijkstra's algorithm.

9 . The method of claim 6 , 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.

10 . The method of claim 9 , 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.

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

12 . The apparatus of claim 11 , 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.

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

14 . The apparatus of claim 11 , 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.

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

16 . 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 path decision at each intersection between the starting location and the destination location, each path decision having a pair of values represent

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