Midpoint-Based Map-Agnostic Navigation Routing

Patent metadata

Field	Value
Publication number	US-2016370193-A1
Application number	US-201514745652-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 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, 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 geographic data for each path segment along the navigation route, the geographic data comprising latitude and longitude values at a midpoint of each path segment; 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 segment 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 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 . 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 segments and latitude and longitude values for each midpoint of each path segment for the sequence of path segments between the starting location and the destination location; and analyzing the encoded navigation route, using a processor of the navigation device, to determine whether the sequence of path segments 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 segment in the sequence of path segments does not match with a corresponding path segment in the map version of the navigation device, the updated route request identifying the at least one unmatched path segment; receiving an updated encoded navigation route, the updated encoded navigation route comprising an updated sequence of path segments that avoids the at least one unmatched path segment; and analyzing the updated encoded navigation route, using the processor of the navigation device, to determine whether the updated sequence of path segments 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 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.

10 . The method of claim 6 , wherein the analyzing of the encoded navigation route comprises assigning costs for the sequence of path segments, wherein each cost is defined as a measured distance between the midpoint in the encoded navigation route and a respective path segment in the map version of the navigation device, and
wherein the path segment of the encoded navigation route is rejected if the respective measured distance is too large.

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 geographic data for each path segment along the navigation route, the geographic data comprising latitude and longitude values at a midpoint of each path segment; 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 segment 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 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.

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

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

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

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 segments and latitude and longitude values for each midpoint of each path segment for the sequence of path segments between the starting location and the destination location; and identify whether the sequence of path segments is compatible with a map version of the navigation device.

17 . The navigation device of claim 16 , wherein 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 segment in the sequence of path segments does not match with a corresponding path segment in the map version of the navigation device, the updated route request identifying the at least one unmatched path segment; receive an updated encoded navigation route, the updated encoded navigation route comprising an updated sequence of path segments that avoid

Assignees

• Here Global Bv

Inventors

• Maischberger Mirko
• Rolf Daniel

Classifications

• 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

• 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/096816

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