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

Patent metadata

Field	Value
Publication number	US-11821739-B2
Application number	US-202017118048-A
Country	US
Kind code	B2
Filing date	Dec 10, 2020
Priority date	Jun 3, 2020
Publication date	Nov 21, 2023
Grant date	Nov 21, 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 an indication of a route request between an origin and a destination; generating a route between the origin starting road segment and the destination target road segment, the route including a plurality of road segments; identifying one or more intermediate segments from the plurality of road segments, each intermediate segment having an anchor point; generating a plurality of route fragments from the route; encoding each route fragment by applying an XOR algorithm to identifiers of route fragment road segments of a respective route fragment; and providing the encoded route fragments and one or more anchor points of the one or more intermediate segments in response to the route request.

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 an indication of a route request between an origin and a destination;
identify a starting road segment corresponding to the origin;
identify a target road segment corresponding to the destination;
generate a route between the starting road segment and the target road segment, the route comprising a plurality of road segments;
identify one or more intermediate segments from the plurality of road segments, each intermediate segment having an anchor point;
generate a plurality of route fragments from the route, each route fragment including one or more route fragment road segments;
encode each route fragment by applying an XOR algorithm to identifiers of the route fragment road segments of a respective route fragment; and
provide the encoded route fragments and one or more anchor points of the one or more intermediate segments in response to the route request.

2. The apparatus of claim 1 , wherein the route request between the origin and the destination includes identification of an anchor point and elevation of a road segment corresponding to the origin and identification of an anchor point and elevation of a road segment corresponding to the destination, and wherein causing the apparatus to identify the starting road segment and to identify the target road segment comprises causing the apparatus to:
identify the starting road segment based on the anchor point and elevation of the road segment corresponding to the origin; and
identify the target road segment based on the anchor point and elevation of the road segment corresponding to the destination.

3. The apparatus of claim 1 , wherein causing the apparatus to establish a plurality of route fragments from the route comprises causing the apparatus to:
establish route fragments comprising one or more road segments between the starting road segment and a first intermediate road segment, between a last intermediate road segment and the target road segment, and between any intermediate road segments.

4. The apparatus of claim 1 , wherein causing the apparatus to identify one or more intermediate segments comprises causing the apparatus to:
select one or more intermediate road segments along the route between the starting road segment and the target road segment, wherein the one or more intermediate road segments is less than a total number of road segments between the starting road segment and the target road segment.

5. The apparatus of claim 4 , wherein the one or more intermediate road segments are selected based on a number of intermediate road segments and a total length of the route.

6. The apparatus of claim 1 , wherein each of the one or more intermediate segments further comprises an elevation, and wherein causing the apparatus to provide the encoded route fragments and one or more anchor points of the one or more intermediate segments in response to the route request comprises causing the apparatus to provide the encoded route fragments, the one or more anchor points of the one or more intermediate segments, and the one or more elevations of the one or more intermediate segments in response to the route request.

7. The apparatus of claim 1 , wherein the encoded route fragments include a first encoded route fragment extending between a starting point of a corresponding first route fragment and an ending point of the first route fragment, and wherein the apparatus is further caused to:
receive a request for a revised encoded route fragment to replace the first encoded route fragment and at least one banned road segment;
generate a revised route fragment between the starting point of the first route fragment and the ending point of the first route fragment, wherein the revised route is generated to exclude the at least one banned road segment;
encode the revised route fragment to generate a revised encoded route fragment; and
provide the revised encoded route fragment in response to the request for the revised encoded route fragment.

8. 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 an indication of a route request between an origin and a destination;
identify a starting road segment corresponding to the origin;
identify a target road segment corresponding to the destination;
generate a route between the starting road segment and the target road segment, the route comprising a plurality of road segments;
identify one or more intermediate segments from the plurality of road segments, each intermediate segment having an anchor point;
generate a plurality of route fragments from the route, each route fragment including one or more route fragment road segments;
encode each route fragment by applying an XOR algorithm to identifiers of the route fragment road segments of a respective route fragment; and
provide the encoded route fragments and one or more anchor points of the one or more intermediate segments in response to the route request.

9. The computer program product of claim 8 , wherein the route request between the origin and the destination includes identification of an anchor point and elevation of a road segment corresponding to the origin and identification of an anchor point and elevation of a road segment corresponding to the destination, and wherein the program code instructions to identify the starting road segment and to identify the target road segment comprise program code instructions to:
identify the starting road segment based on the anchor point and elevation of the road segment corresponding to the origin; and
identify the target road segment based on the anchor point and elevation of the road segment corresponding to the destination.

10. The computer program product of claim 8 , wherein the program code instructions to establish a plurality of route fragments from the route comprise program code instructions to:
establish route fragments comprising one or more road segments between the starting road segment and a first intermediate road segment, between a last intermediate road segment and the target road segment, and between any intermediate road segments.

11. The computer program product of claim 8 , wherein the program code instructions to identify one or more intermediate segments comprise program code instructions to:
select one or more intermediate road segments along the route between the starting road segment and the target road segment, wherein the one or more intermediate road segments is less than a total number of road segments between the starting road segment and the target road segment.

12. The computer program product of claim 11 , wherein the one or more intermediate road segments are selected based on a number of intermediate road segments and a total length of the route.

13. The computer program product of claim 8 , wherein each of the one or more intermediate segments further comprises an elevation, and wherein the program code instructions to provide the encoded route fragments and one or more anchor points of the one or more intermediate segments in response to the route request comprise program code instructions to provide the encoded route fragments, the one or more anchor points of the one or more intermediate segments, and the one or more elevations of the on

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel
• Falla Cepeda David

Classifications

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• G01C21/3889

  Transmission of selected map data, e.g. depending on route · CPC title