Use of pattern matching to predict actual traffic conditions of a roadway segment

• US 7,755,509 B2
• Filed: 10/09/2007
• Issued: 07/13/2010
• Est. Priority Date: 09/20/2007
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Trafficcom Incorporated (Nokia Corporation)
• Inventors: Shokoufandeh, Ali, Bespalov, Dmitriy
• Primary Examiner(s): Wu; Daniel
• Assistant Examiner(s): WILSON, BRIAN P
• Application Number:
  US11/869,372
• Publication Number:
  US 20090079586A1
• Time in Patent Office: 1,008 Days
• Field of Search: None
• US Class Current: 340/905
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions

Abstract

Actual traffic conditions of a roadway segment are predicted by providing a plurality of historical roadway condition patterns of the roadway segment in a database, obtaining an electronic representation of a current roadway condition pattern of the roadway segment, identifying one or more of the historical roadway condition patterns that closely matches the current roadway condition pattern, and predicting the future actual traffic conditions of the roadway segment by using the conditions associated with the one or more identified historical patterns.

Claims

1. A computer-implemented method for predicting traffic conditions of a roadway segment, comprising:

obtaining current roadway condition data for a roadway segment;

calculating a current congestion curve representing congestion conditions on the roadway segment using the obtained current roadway condition data;

calculating a first distance value from the current congestion curve to a previous congestion curve calculated using roadway condition data obtained most previously prior to obtaining the current roadway condition data for the roadway segment;

obtaining a second distance value from a database that is closest to the first distance value, wherein the second distance value is associated with a historical roadway condition pattern; and

predicting roadway conditions for the roadway segment at a future time by tracing the historical roadway condition pattern associated with the second distance value to the future time.

2. The method of claim 1, further comprising obtaining a feature vector for the roadway segment.

3. The method of claim 2, wherein the feature vector includes parameters representing type of day, events, and weather.

4. The method of claim 2, further comprising extracting historical roadway condition patterns from the database that match the feature vector and obtaining the second distance value from the extracted historical roadway condition patterns.

5. The method of claim 1, wherein calculating a first distance includes calculating a distance between two parabolas, wherein the two parabolas represent the current congestion curve and the previous congestion curve.

6. The method of claim 1, wherein the historical roadway condition pattern is generated by:

collecting roadway condition data for the roadway segment for a period of time;

identifying congestion conditions in the collected data;

fitting a curve to the congestion conditions; and

assigning a distance value to a pair of congestion curves.

7. The method of claim 6, further comprising compressing the roadway condition data for the roadway segment.

8. The method of claim 6, wherein identifying congestion conditions includes calculating a threshold value and identifying data within the collected roadway condition data that exceeds the threshold value.

9. The method of claim 8, wherein the threshold value is calculated using the formula:

δ

_congestion=lowest_20%+(std_dev·

std_dev_coeff)

where lowest_20% denotes an average of 20% of the lowest roadway condition data, std_dev denotes a standard deviation computed on the roadway condition data, and std_dev_coeff is a coefficient.

10. The method of claim 6, wherein fitting a curve to the congestion conditions includes fitting a parabola y=at²+bt+c, a<

0 to the congestion conditions.

11. The method of claim 10, wherein assigning a distance value to a pair of congestion curves includes calculating a distance between two parabolas representing congestion conditions on the roadway segment.

12. The method of claim 6, further comprising grouping similar congestion curves.

13. The method of claim 1, wherein obtaining a second distance value includes obtaining three closest distance values and predicting roadway conditions using a weighted average of three traces using three historical roadway condition patterns.

14. A computer-implemented method for predicting traffic conditions of a roadway segment, comprising:

storing historic roadway condition patterns in a database, wherein each of the historic roadway condition patterns includes at least two parabolas representing congestion conditions exceeding a threshold on a roadway segment and a distance value representing a distance between two of the at least two parabolas;

obtaining data representing current travel times for traveling through a roadway segment;

using the travel time data to calculate a current distance value;

comparing the current distance value to stored distance values to identify a historic roadway condition pattern having a closest distance value to the current distance value; and

using the identified historic roadway condition pattern to predict future conditions of the roadway segment.

15. The method of claim 14, wherein using the travel time data to calculate the current distance value includes fitting congestion curves to current travel time data and assigning a numerical value to a pair of congestion curves.

16. The method of claim 15, wherein assigning a numerical value includes calculating a distance between two parabolas.

17. The method of claim 15, wherein assigning a numerical value includes setting the numerical value to 1 if one of the current travel times or the historic roadway condition pattern indicates no congestion.

18. The method of claim 15, wherein assigning a numerical value includes calculating the formula

$d$

( p 1 , p 2 ) = 

s 1 - s 2 

MAX_SPEED

when both the current travel times and the historic roadway condition pattern indicates no congestion, where d(p₁,p₂) denotes a distance function, s₁ denotes average speed for p₁, s₂ denotes average speed for p₂, and MAX_SPEED denotes maximum speed value.

19. The method of claim 14, further comprising using a feature vector to extract a subset of the historic roadway condition patterns from the database and comparing the current distance value to extracted distance values.