Traffic predictions at lane level

Patent metadata

Field	Value
Publication number	US-11915583-B2
Application number	US-201916272726-A
Country	US
Kind code	B2
Filing date	Feb 11, 2019
Priority date	Feb 11, 2019
Publication date	Feb 27, 2024
Grant date	Feb 27, 2024

Abstract

An apparatus and method for determining a traffic level in the future. A road network including graph edges for a plurality of intersections and graph nodes for a plurality of road links is identified. A road link of interest is selected from the plurality of road links. A set of related link subset are calculated for the selected road link. Historical data is queried for the related link subset. A predicted traffic level is calculated for the selected road link in response to the historical data for the related link subset.

First claim

I claim:

1. A method for predicting future traffic for a roadway, the method comprising:
updating a geographic database including directions of travel by vehicles while the vehicles are traveling;
receiving road network data from the geographic database in a first road network format describing a road network including a plurality of road links and a plurality of intersections, wherein the first road network format includes graph edges for the plurality of road links and graph nodes for the plurality of intersections;
converting, by a processor, the road network data in the first road network format to a second road network format describing the road network by analyzing a direction of travel by the vehicles between at least one pair of the plurality of road links in the first road network format, wherein the second road network format includes graph edges for the plurality of intersections and graph nodes for the plurality of road links;
selecting, by the processor, a road link from the plurality of road links in the second road network format;
calculating, by the processor, a related link subset from the plurality of road links for the selected road link;
querying, by the processor, historical data for the related link subset from the geographic database;
calculating, by the processor, a predicted traffic level for the selected road link in response to the historical data for the related link subset; and
modifying, by the processor, a route generation in response to the predicted traffic level.

2. The method of claim 1 , further comprising:
identifying a multi-lane road link including a plurality of lanes with at least one lane upstream of the selected road link, the at least one lane connected to the selected road link in the second road network format.

3. The method of claim 2 , further comprising:
receiving position data from a mobile device; and
matching the multi-lane road link to the position data.

4. The method of claim 1 , wherein the related link subset includes a multiple level hierarchy of neighboring links connected to the selected road link in the second road network format.

5. The method of claim 4 , wherein the multiple level hierarchy includes at least one link downstream of the selected link and at least one link upstream of the selected link.

6. The method of claim 4 , wherein the multiple level hierarchy includes at least one link upstream of a road link that is downstream of the selected link.

7. The method of claim 4 , wherein the multiple level hierarchy includes at least one link downstream of the selected link and at least one link upstream of the selected link.

8. The method of claim 4 , wherein the multiple level hierarchy includes the road links in the second road network format that are connected to the selected link and upstream of the selected road link and includes the road links in the second road network format that are connected to the selected link and downstream of the selected road link.

9. The method of claim 8 , wherein the multiple level hierarchy includes the road links that are upstream of the road links in the second road network format that are connected to the selected link and downstream of the selected road link.

10. The method of claim 1 , further comprising:
accessing a prior patterns data set for the related link subset, wherein the prior patterns data set relates initial states of the related link subset to subsequent states of the related link subset.

11. The method of claim 10 , wherein the initial states and the subsequent states are discretized speed levels.

12. The method of claim 1 , further comprising:
accessing an epoch traffic pattern data set for the related link subset, wherein the epoch traffic pattern data set relates a frequency to stages of the related link subset.

13. The method of claim 1 , further comprising:
accessing a state transition data set for the related link subset, wherein the state transition data associates initial states to subsequent states for each of a plurality of time epochs.

14. The method of claim 1 , further comprising:
accessing a prior patterns data set for the related link subset, accessing an epoch traffic pattern data set for the related link subset, and accessing a state transition data set for the related link subset, wherein the predicted traffic level is calculated from a first probability determined from the prior patterns data set, a second probability determined from the epoch traffic pattern data set and a third probability determined from the state transition data set.

15. The method of claim 1 , wherein the first road network format includes an indicator of the direction of travel by the vehicles between the at least one pair of the plurality of road links, and the second road network format includes at least one pair of nodes connected based on the indicator of the direction of travel by the vehicles between the at least one pair of the plurality of road links from the first road network format.

16. A method for predicting future traffic for a roadway, the method comprising:
updating a geographic database including directions of travel by vehicles while the vehicles are traveling;
receiving road network data from the geographic database in a first road network format describing a road network including a plurality of road links and a plurality of intersections, wherein the first road network format includes graph edges for the plurality of road links and graph nodes for the plurality of intersections;
converting, by a processor, the road network data in the first road network format to a second road network format describing the road network by analyzing a direction of travel by the vehicles between at least one pair of the plurality of road links in the first road network format, wherein the second road network format includes graph edges for the plurality of intersections and graph nodes for the plurality of road links;
selecting, by the processor, a road link from the plurality of road links in the second road network format;
calculating, by the processor, a related link subset from the plurality of road links for the selected road link;
querying, by the processor, historical data for the related link subset from the geographic database;
calculating, by the processor, a predicted traffic level for the selected road link in response to the historical data for the related link subset;
accessing a prior patterns data set for the related link subset, accessing an epoch traffic pattern data set for the related link subset, and accessing a state transition data set for the related link subset, wherein a probability E t i of the selected road link (i) at time (t) that the predicted traffic level has a state X t based on the related link subset (MB) is calculated according to:
E t i =arg Max[ P ( MB t-k |X t )· P ( X t-k |X t )· P ( X t )],

wherein a first probability P(MB t-k |X t ) is determined from the prior patterns data set, a second probability P(X t-k |X t ) is determined from the epoch traffic pattern data set and a third probability P(X t ) is determined from the state transition data set; and
modifying, by the processor, a route generation in response to the predicted traffic level.

17. An apparatus for predicting future traffic for a roadway, the apparatus further comprising:
a processor configured to convert road network data, received from a geographic database including directions of travel by vehicles and updated while the vehicles are traveling, in a first road network format describing a road network

Assignees

• Here Global Bv

Inventors

• Fowe James

Classifications

• G08G1/0133 Primary

  for classifying traffic situation · CPC title

• G06N5/046

  Forward inferencing; Production systems · CPC title

• G08G1/012 Primary

  from other sources than vehicle or roadside beacons, e.g. mobile networks · CPC title

• G08G1/0129

  for creating historical data or processing based on historical data · CPC title

• G08G1/052

  with provision for determining speed or overspeed {(speed measuring in general G01P)} · CPC title