Method, apparatus, and computer program product for generating and communicating low bandwidth map version agnostic routes

Patent metadata

Field	Value
Publication number	US-11733059-B2
Application number	US-202017118104-A
Country	US
Kind code	B2
Filing date	Dec 10, 2020
Priority date	Jun 3, 2020
Publication date	Aug 22, 2023
Grant date	Aug 22, 2023

Abstract

Provided herein is a method of generating low bandwidth map format agnostic routes between origins and destinations for route communication between different map formats or versions using reduced bandwidth. Methods may include: receiving one or more intermediate segment anchor points and encoded server-provided route fragments for a requested route between an origin and a destination; identifying one or more intermediate segments corresponding to the one or more intermediate segment anchor points; generating a route between the origin and the destination, the route including the one or more intermediate segments and a plurality of client-generated route fragments; encoding each client-generated route fragment by application of an XOR algorithm to the client-generated route fragment road segments; comparing the encoded client-generated route fragments to the encoded server-provided route fragments; and providing navigational assistance for traveling along the route in response to the encoded client-generated route fragments corresponding with the encoded server-provided route fragments.

First claim

That which is claimed:

1. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processor, cause the apparatus to at least:
receive one or more intermediate segment anchor points for a requested route between an origin and a destination;
receive encoded server-provided route fragments;
identify one or more intermediate segments corresponding to the one or more intermediate segment anchor points;
generate a route between the origin and the destination, the route comprising the one or more intermediate segments and a plurality of client-generated route fragments, each client-generated route fragment including one or more client-generated route fragment road segments;
encode each client-generated route fragment by application of an XOR algorithm to the client-generated route fragment road segments of a respective client-generated route fragment;
compare the encoded client-generated route fragments to the encoded server-provided route fragments; and
provide navigational assistance for traveling along the route in response to the encoded client-generated route fragments corresponding with the encoded server-provided route fragments.

2. The apparatus of claim 1 , wherein the client-generated route fragments comprise route fragments extending between a starting road segment corresponding to the origin and an intermediate segment of the one or more intermediate segments, between intermediate segments in response the one or more intermediate segments comprising two or more intermediate segments, and between an intermediate segment of the one or more intermediate segments and a target road segment corresponding to the destination.

3. The apparatus of claim 1 , wherein the apparatus is further caused to:
provide an indication of a revised route fragment request between a starting point of a first encoded client-generated route fragment and an ending point of the first encoded client-generated route fragment in response to the first encoded client-generated route fragment failing to correspond to a first encoded server-generated route fragment.

4. The apparatus of claim 1 , wherein the apparatus is further caused to:
provide a request for a map update in response to at least one of:
a first encoded client-generated route fragment failing to correspond with a first encoded server-generated route fragment; or
one or more intermediate segment anchor points failing to correspond to the one or more intermediate segments.

5. The apparatus of claim 4 , wherein the request for the map update comprises a request for a map update to a finite region of the map, and wherein the finite region corresponds to a region including a road segment associated with the first encoded client-generated route fragment that failed to correspond with a first encoded server-generated route fragment or the one or more intermediate segment anchor points that fail to correspond to the one or more intermediate segments.

6. The apparatus of claim 1 , wherein causing the apparatus to provide an indication of a route request between an origin and a destination comprises causing the apparatus to provide an indication of an anchor point of a road segment corresponding to the origin and an anchor point of a road segment corresponding to the destination.

7. The apparatus of claim 1 , wherein causing the apparatus to identify one or more intermediate segments corresponding to the one or more intermediate segment anchor points comprises causing the apparatus to:
map match the one or more intermediate segment anchor points to a corresponding intermediate road segment, wherein the one or more intermediate segment anchor points comprise a midpoint of a respective intermediate road segment and an elevation level of the respective intermediate road segment.

8. The apparatus of claim 1 , wherein causing the apparatus to provide an indication of a route request between an origin and a destination comprises causing the apparatus to provide an indication of a number of intermediate segment anchor points between the origin and the destination, and wherein causing the apparatus to receive one or more intermediate segment anchor points for the route between the starting road segment and the target road segment comprises causing the apparatus to receive the requested number of intermediate segment anchor points between the origin and the destination.

9. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions configured to:
receive one or more intermediate segment anchor points for a requested route between an origin and a destination;
receive encoded server-provided route fragments;
identify one or more intermediate segments corresponding to the one or more intermediate segment anchor points;
generate a route between the origin and the destination, the route comprising the one or more intermediate segments and a plurality of client-generated route fragments, each client-generated route fragment including one or more client-generated route fragment road segments;
encode each client-generated route fragment by application of an XOR algorithm to the client-generated route fragment road segments of a respective client-generated route fragment;
compare the encoded client-generated route fragments to the encoded server-provided route fragments; and
provide navigational assistance for traveling along the route in response to the encoded client-generated route fragments corresponding with the encoded server-provided route fragments.

10. The computer program product of claim 9 , wherein the client-generated route fragments comprise route fragments extending between a starting road segment corresponding to the origin and an intermediate segment of the one or more intermediate segments, between intermediate segments in response the one or more intermediate segments comprising two or more intermediate segments, and between an intermediate segment of the one or more intermediate segments and a target road segment corresponding to the destination.

11. The computer program product of claim 9 , further comprising program code instructions to:
provide an indication of a revised route fragment request between a starting point of a first encoded client-generated route fragment and an ending point of the first encoded client-generated route fragment in response to the first encoded client-generated route fragment failing to correspond to a first encoded server-generated route fragment.

12. The computer program product of claim 9 , further comprising program code instructions to:
provide a request for a map update in response to at least one of:
a first encoded client-generated route fragment failing to correspond with a first encoded server-generated route fragment; or
one or more intermediate segment anchor points failing to correspond to the one or more intermediate segments.

13. The computer program product of claim 12 , wherein the request for the map update comprises a request for a map update to a finite region of the map, and wherein the finite region corresponds to a region including a road segment associated with the first encoded client-generated route fragment that failed to correspond with a first encoded server-generated route fragment or the one or more intermediate segment anchor points that fail to correspond to the one or more intermediate segments.

14. The computer program pr

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel
• Falla Cepeda David

Classifications

• G01C21/3815 Primary

  Road data · CPC title

• G01C21/3407

  specially adapted for specific applications · CPC title

• G01C21/3676

  Overview of the route on the road map · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G01C21/387 Primary

  Organisation of map data, e.g. version management or database structures · CPC title