Method and apparatus for providing semantic-free traffic prediction

Patent metadata

Field	Value
Publication number	US-10909470-B2
Application number	US-201715439622-A
Country	US
Kind code	B2
Filing date	Feb 22, 2017
Priority date	Feb 22, 2017
Publication date	Feb 2, 2021
Grant date	Feb 2, 2021

Abstract

An approach is provided for semantic-free traffic prediction. The approach involves dividing a travel-speed data stream into a plurality of travel-speed patterns. The travel-speed data stream represents vehicle travel speeds occurring in a road network. The approach also involves representing each of the plurality of travel-speed patterns by a respective token. The respective token is selected from a dictionary of tokens representing a plurality of travel-speed templates determined from historical travel-speed data. The approach further involves matching a sequence of the respective tokens corresponding to said each of the plurality of travel-speed patterns to a best-fit sequence of tokens determined from the historical travel-speed data. The approach further involves determining a predicted sequence of tokens based on the best-fit sequence of tokens, and generating a traffic prediction for the road network based on the predicted sequence of tokens.

First claim

What is claimed is:

1. A method for predicting traffic from travel-speed data using tokenized travel-speed patterns comprising:
dividing a travel-speed data stream into a plurality of travel-speed patterns, wherein the travel-speed data stream represents vehicle travel speeds occurring in a road network;
clustering the plurality of travel-speed patterns according to similar shapes and lengths;
representing each of the clustered travel-speed patterns by a respective token, wherein the respective token is selected from a dictionary of tokens representing a plurality of travel-speed templates determined from historical travel-speed data;
matching a sequence of the respective tokens corresponding to said each of the clustered travel-speed patterns to a best-fit sequence of tokens determined from the historical travel-speed data;
determining a number of the plurality of travel-speed patterns to include in the sequence that is matched based on a stopping criterion that specifies a predetermined number of the tokens for prediction of future traffic:
determining that the matched sequence is not unique or the stopping criterion is not met;
dynamically increasing the number of the plurality of the travel-speed patterns to include in the sequence until the sequence is unique or the stopping criterion is met;
determining a predicted sequence of tokens based on the best-fit sequence of tokens; and
generating a traffic prediction for the road network based on the predicted sequence of tokens.

2. The method of claim 1 , wherein the sequence that is matched further comprises:
matching a predetermined number of a most recent of the plurality of the travel-speed patterns to the dictionary of tokens; and
predicting a future traffic pattern that corresponds to the most recent of the plurality of the travel-speed patterns.

3. The method of claim 1 , further comprising:
processing, using machine learning, the historical travel-speed data to determine clusters of historical travel-speed patterns,
wherein the plurality of travel-speed templates represented in the dictionary of tokens correspond to a respective summary of each of the determined clusters.

4. The method of claim 1 , wherein the travel-speed data stream is a probe data stream collected from one or more probes traveling in the road network, a sensor data stream from one or more speed sensors operating in the road network, or a combination thereof.

5. The method of claim 1 , wherein the travel-speed data stream is divided at one or more points at fixed times of day, at one or more arbitrary times of day, or a combination thereof.

6. The method of claim 1 , wherein the travel-speed data stream is divided at one or more points where a travel speed transitions from a free-flow value to a predetermined congestion value, or from the predetermined congestion value to the free-flow value.

7. The method of claim 1 , further comprising:
determining an average speed value of the travel-speed data stream,
wherein the travel-speed data stream is divided at one or more points where a probe speed crosses the average speed value.

8. The method of claim 1 , further comprising:
determining one or more commonly occurring sequences of historical tokens from the dictionary of tokens; and
matching the sequence of the respective tokens to the commonly occurring sequences of the historical tokens.

9. The method of claim 8 , further comprising:
determining a next token in the commonly occurring sequences of the historical tokens is not unique, wherein the next token is not unique if a token of a previous interval of the plurality of the travel-speed patterns results in two possible historical sequences; and
determining a next previous interval to find a next previous token to match with the occurring sequences of the historical tokens.

10. An apparatus for predicting traffic from travel-speed data using tokenized travel-speed patterns comprising:
at least one processor; and
at least one memory including computer program code for one or more programs,
the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,
divide a travel-speed data stream into a plurality of travel-speed patterns, wherein the travel-speed data stream represents vehicle travel speeds occurring in a road network;
cluster the plurality of travel-speed patterns according to similar shapes and lengths;
represent each of the clustered travel-speed patterns by a respective token, wherein the respective token is selected from a dictionary of tokens representing a plurality of travel-speed templates determined from historical travel-speed data;
match a sequence of the respective tokens corresponding to said each of the clustered travel-speed patterns to a best-fit sequence of tokens determined from the historical travel-speed data;

determine a number of the plurality of travel-speed patterns to include in the sequence that is matched based on a stopping criterion that specifies a predetermined number of the tokens for prediction of future traffic;
determine that the matched sequence is not unique or the stopping criterion is not met;
dynamically increase the number of the plurality of the travel-speed patterns to include in the sequence until the sequence is unique or the stopping criterion is met;
determine a predicted sequence of tokens based on the best-fit sequence of tokens; and
generate a traffic prediction for the road network based on the predicted sequence of tokens.

11. The apparatus of claim 10 , wherein the sequence that is matched further comprises:
match a predetermined number of a most recent of the plurality of the travel-speed patterns to the dictionary of tokens; and
predicting a future traffic pattern that corresponds to the most recent of the plurality of the travel-speed patterns.

12. The apparatus of claim 10 , wherein the apparatus is further caused to:
process, using machine learning, the historical travel-speed data to determine clusters of historical travel-speed patterns,
wherein the plurality of travel-speed templates represented in the dictionary of tokens correspond to a respective summary of each of the determined clusters.

13. The apparatus of claim 11 , wherein the travel-speed data stream is a probe data stream collected from one or more probes traveling in the road network, a sensor data stream from one or more speed sensors operating in the road network, or a combination thereof.

14. The non-transitory computer-readable storage medium for predicting traffic from travel-speed data using tokenized travel-speed patterns, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:
dividing a travel-speed data stream into a plurality of travel-speed patterns, wherein the travel-speed data stream represents vehicle travel speeds occurring in a road network;
representing each of at least a subset of the plurality of travel-speed patterns by a respective token, wherein the respective token is selected from a dictionary of tokens representing a plurality of travel-speed templates determined from historical travel-speed data;
matching a sequence of the respective tokens corresponding to said each of the subset of the plurality of travel-speed patterns to a best-fit sequence of tokens determined from the historical travel-speed data;
determining a number of the plurality of travel-speed patterns to include in the sequence that is matched based on a stopping criterion that specifies a

Assignees

• Here Global Bv

Inventors

• PIETROBON Davide
• Lewis Andrew
• Macfarlane Jane

Classifications

• G08G1/0112 Primary

  from the vehicle, e.g. floating car data [FCD] · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G08G1/0129

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

• G08G1/0133

  for classifying traffic situation · CPC title

• G08G1/0141

  for traffic information dissemination · CPC title