Methods and systems for route generation through an area

Patent metadata

Field	Value
Publication number	US-10976164-B2
Application number	US-201816218020-A
Country	US
Kind code	B2
Filing date	Dec 12, 2018
Priority date	Dec 12, 2018
Publication date	Apr 13, 2021
Grant date	Apr 13, 2021

Abstract

A method, a system, and a computer program product are provided for generating route data of one or more routes through an area. The method includes obtaining from a map database, a plurality of map-matched links corresponding to area and determining one or more first links and one or more second links from the plurality of map-matched links. The method further includes searching the map database, in the downstream of each of the first links for one or more missing downstream links and searching the map database in the upstream of each of the second links for one or more missing upstream links, and generating the route data of the routes based on the first link, the second link, the missing downstream links, the missing upstream links, and the plurality of map-matched links.

First claim

We claim:

1. A method for generating route data of one or more routes through an area, the method comprising:
obtaining from a map database, by a processor, a plurality of map-matched links corresponding to the area, wherein the plurality of map-matched links corresponds to a first plurality of point-based road feature observations associated with a plurality of sensor observations made by a plurality of vehicles;
determining one or more first links and one or more second links from the plurality of map-matched links based on relationships between the plurality of map-matched links,
wherein at least a third link of the plurality of map-matched links is upstream of each of the one or more first links, and
wherein at least a fourth link of the plurality of map-matched links is downstream of each of the one or more second links;

searching the map database by the processor, downstream of each of the one or more first links, for one or more missing downstream links based on one or more link attributes of each of the one or more first links and a downstream distance threshold,
searching the map database by the processor, upstream of each of the one or more second links, for one or more missing upstream links based on one or more link attributes of each of the one or more second links and an upstream distance threshold, and
generating the route data of the one or more routes based on the one or more first links, the one or more second links, the one or more missing downstream links, the one or more missing upstream links, and the plurality of map-matched links.

2. The method of claim 1 , wherein the generating of the route data comprises:
identifying at least one start link from one of the one or more second links or the one or more missing upstream links; and
identifying at least one end link from one of the one or more first links or the one or more missing downstream links.

3. The method of claim 2 , wherein the route data comprises location data and heading data of each of the at least one start link and the at least one end link.

4. The method of claim 1 , wherein the one or more link attributes of each of the one or more first links comprise one or more of a functional class of a first link, a link start location and a link end location of the first link, a link downstream heading of the first link, and a length of the first link.

5. The method of claim 1 , wherein the one or more link attributes of each of the one or more second links comprise one or more of a functional class of a second link, a link start location and a link end location of the second link, a link upstream heading of the second link, and a length of the second link.

6. The method of claim 1 , wherein obtaining the plurality of map-matched links comprises:
clustering the first plurality of point-based road feature observations, based on an observation type, a location and a heading of each of the first plurality of point-based road feature observations to generate at least one cluster; and
map-matching the generated at least one cluster to a plurality of links based on the observation type, the location and the heading of each point-based road feature observation in the generated at least one cluster, to obtain the plurality of map-matched links.

7. The method of claim 6 , wherein the observation type is one of a road marking, a road sign, a bollard, a cone, a road barrier, or a guardrail.

8. The method of claim 1 , further comprising outputting a traversable route on an output interface of one or more vehicles based on the generated route data.

9. A system for generating route data of one or more routes through an area, the system comprising:
at least one memory configured to store computer program code instructions; and
at least one processor configured to execute the computer program code instructions to:
obtain from a map database, a plurality of map-matched links corresponding to the area, wherein the plurality of map-matched links corresponds to a first plurality of point-based road feature observations associated with a plurality of sensor observations made by a plurality of vehicles;
determine one or more first links and one or more second links from the plurality of map-matched links based on relationships between the plurality of map-matched links,
wherein at least a third link of the plurality of map-matched links is upstream of each of the one or more first links, and
wherein at least a fourth link of the plurality of map-matched links is downstream of each of the one or more second links;

search the map database downstream of each of the one or more first links, for one or more missing downstream links based on one or more link attributes of each of the one or more first links and a downstream distance threshold;
search the map database upstream of each of the one or more second links, for one or more missing upstream links based on one or more link attributes of each of the one or more second links and an upstream distance threshold; and
generate the route data of the one or more routes based on the one or more first links, the one or more second links, the one or more missing downstream links, the one or more missing upstream links, and the plurality of map-matched links.

10. The system of claim 9 , wherein to generate the route data, the at least one processor is further configured to:
identify at least one start link from one of the one or more second links or the one or more missing upstream links; and
identify at least one end link from one of the one or more first links or the one or more missing downstream links.

11. The system of claim 10 , wherein the route data comprises location data and heading data of each of the at least one start link and the at least one end link.

12. The system of claim 9 , wherein the one or more link attributes of each of the one or more first links comprise one or more of a functional class of a first link, a link start location and a link end location of the first link, a link downstream heading of the first link, and a length of the first link.

13. The system of claim 9 , wherein the one or more link attributes of each of the one or more second links comprise one or more of a functional class of a second link, a link start location and a link end location of the second link, a link upstream heading of the second link, and a length of the second link.

14. The system of claim 9 , wherein to obtain the plurality of map-matched links, the at least one processor is further configured to:
cluster the first plurality of point-based road feature observations, based on an observation type, a location and a heading of each of the first plurality of point-based road feature observations to generate at least one cluster; and
map-match the generated at least one cluster to a plurality of links based on the observation type, the location, and the heading of each point-based road feature observation in the generated at least one cluster, to obtain the plurality of map-matched links.

15. The system of claim 14 , wherein the observation type is one of a road marking, a road sign, a bollard, a cone, a road barrier or a guardrail.

16. The system of claim 9 , wherein the at least one processor is further configured to output a traversable route on an output interface of one or more vehicles, based on the generated route data.

17. A computer program product comprising at least one non-transitory computer-readable storage medium having stored thereon computer-executable program code instructions which, when executed by a computer, cause the computer to

Assignees

• Here Global Bv

Inventors

• Zhang Zhenhua
• Stenneth Leon

Classifications

• G01C21/34 Primary

  Route searching; Route guidance · CPC title

• G01C21/3815

  Road data · CPC title

• G01C21/3811

  Point data, e.g. Point of Interest [POI] · CPC title

• G01C21/3841

  Data obtained from two or more sources, e.g. probe vehicles · CPC title

• G01C21/3446 Primary

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