# US 2010/0063715 A1 · Method and structure for vehicular traffic prediction with link interactions and missing real-time data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0063715 A1
- Document ID: US20100063715A1
- Status: Published application
- Kind: A1
- Application number: 12/619,226
- Filed: 2009-11-16
- Published: 2010-03-11
- Earliest claimed: 2007-01-24
- Assignees: International Business Machines Corporation
- Inventors: Laura Wynter; Wanli Min; Benjamin G. Morris
- Web page: https://patentgrep.com/patent/US20100063715A1

## CPC

- G01C 21/3691: {Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions (arrangements for giving variable traffic instructions G08G1/09)}
- G08G 1/0104: {Measuring and analyzing of parameters relative to traffic conditions}
- G08G 1/096827: {where the route is computed onboard}
- G08G 1/096844: {where the complete route is dynamically recomputed based on new data}
- G08G 1/096888: {where input information is obtained using learning systems, e.g. history databases}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

A method and apparatus for predicting traffic on a transportation network where real time data points are missing. In one embodiment, the missing data is estimated using a calibration model comprised of historical data that can be periodically updated, from select links constituting a relationship vector. The missing data can be estimated off-line whereafter it can be used to predict traffic for at least a part of the network, the traffic prediction being calculated by using a deviation from a historical traffic on the network. The invention further discloses a method for in-vehicle navigation; and a method for traffic prediction for a single lane.

## Claims

### Claim 1

A method for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, said method comprising:
a) providing data points related to real time traffic conditions on each link, wherein at least one data point is missing for a given link;
b) estimating the value of said missing data point; and
c) using said estimated value to predict traffic for at least a portion of said transportation network by deviation from a historical traffic pattern of said network.

### Claim 2 (depends on 1)

The method of claim 1 wherein said missing data point in estimated in step (b) from a calibration model representative of historical data points.

### Claim 3 (depends on 1)

The method of claim 1 wherein a plurality of data points are missing from a plurality of given links.

### Claim 4 (depends on 1)

The method of claim 1 wherein said data points are provided from predetermined locations.

### Claim 5 (depends on 2)

The method of claim 2 wherein in said historical data points comprise that for the preceding six or more weeks for the links constituting the calibration model.

### Claim 6 (depends on 5)

The method of claim 5 wherein said calibration model is updated periodically.

### Claim 7 (depends on 1)

The method of claim 1 wherein said estimating step is performed off-line.

### Claim 8

An apparatus for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, said apparatus comprising:
a) a receiver to receive data points related to real time traffic conditions on each link, wherein at least one data point is missing from a given link;
b) an estimator to estimate the value of said missing data point; and
c) a calculator to calculate a traffic prediction by using said estimated value in a deviation from a historical traffic pattern of said network.

### Claim 9 (depends on 8)

The apparatus of claim 8 wherein said estimator comprises a calibrated model constituted of historical data points from all links in the relationship vector, except those from said given link.

### Claim 10 (depends on 8)

The apparatus of claim 8 wherein said data points are provided from predetermined locations.

### Claim 11

A computer readable medium containing an executable program for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, where said program performs the steps of:
a) receiving data points related to real time traffic conditions on each link wherein at least one data point is missing from a given link;
b) estimating the value of said missing data point; and
c) calculating a traffic prediction by using said estimated value in a deviation from a historical traffic pattern of said network.

### Claim 12 (depends on 11)

The computer readable medium of claim 11 wherein missing data point is estimated in step (b) from a calibration model representative of historical data points.

### Claim 13 (depends on 12)

The computer readable medium of claim 12 wherein the historical data points in said calibration model are periodically updated.

### Claim 14

A method of providing navigational guidance to a vehicle over a transportation network, said transportation network comprised of routes with traffic signals, the method comprising:
a) providing to a processor: trip information, said trip information comprising an origin and a destination for said vehicle; and a radius, said radius measured from said vehicle when said vehicle is on said transportation network;
b) obtaining data from one or more traffic signals within said radius, at intervals of time, said data relating to one or both of the following:
(i) information on the state of at least one of said traffic signals for a respective interval of time; and
(ii) routing table information, said routing table information indicative of state of traffic for routes to said destination on said transportation network
c) processing said data with said trip information to identify optimal route choices to said destination on said transportation network for said vehicle; and
d) providing said optimal route choices to said vehicle.

### Claim 15 (depends on 14)

The method of claim 14 wherein said intervals of time are the same or different for data relating to (b)(i) and (b)(ii).

### Claim 16 (depends on 15)

The method of claim 15 wherein said intervals of time are regular or irregular.

### Claim 17 (depends on 14)

The method of claim 14 wherein the information on the state of said one or more traffic signals includes any one or more of the following: the point in a stop-go cycle a particular signal is at during said respective interval of time, how much time remains for said cycle, and the duration of said cycle.

### Claim 18 (depends on 14)

The method of claim 14 wherein said optimal route choices is based on any one or more of the following: remaining duration to said destination, average speed on said optimal route choices, number of starts and stops at said one or more traffic signals.

### Claim 19 (depends on 14)

The method of claim 14 wherein said routing table information indicative of state of traffic includes real or predicted travel time on one or more of the following: (i) routes to said destination; and (ii) routes in the vicinity of said one or more traffic signals.

### Claim 20 (depends on 19)

The method of claim 19 wherein for (i) said travel time on routes to said destination includes real or predicted travel time from one location on said route to a second location on said route.

### Claim 21 (depends on 14)

The method of claim 14 wherein said routing table information includes real or predicted travel time from said one or more traffic signals to one or more of the following: (i) a location on a route to said destination; and (ii) a location in the vicinity of said one or more traffic signals.

### Claim 22 (depends on 14)

The method of claim 14 wherein said optimal route choices are updated throughout the duration to said destination.

### Claim 23 (depends on 14)

The method of claim 14 wherein the processor is in said vehicle and said processing of step (c) is performed in whole or in part at any one or more of the following: at said one or more traffic signals, at the processor, or at a remote location.

### Claim 24 (depends on 14)

The method of claim 14 wherein the data of step (b) includes at least one missing data point, and said at least one missing data point is estimated to predict to predict traffic for a least a portion of said transportation network by deviation from a historical pattern of said transportation network.

### Claim 25

A method of predicting traffic for a specific lane on a transportation network comprised of links wherein said links constitute a relationship vector, which method comprises:
a) providing data points related to real time traffic conditions for a specific lane in a link of a transportation network;
b) updating a template representative of a historical traffic pattern for said specific lane in accordance with said data points; and
c) providing a prediction of traffic for said specific lane in accordance with said updated template.

### Claim 26 (depends on 25)

The method of claim 25 wherein said prediction of traffic includes any one or more of travel time, speed, density, flow, and occupation of said specific lane.

### Claim 27 (depends on 25)

The method of claim 25 wherein at least one of said real time data points for sais missing.

### Claim 28 (depends on 27)

The method of claim 27 wherein the value of said at least one missing data point is estimated.

### Claim 29 (depends on 28)

The method of claim 28 wherein the value is estimated from a calibration model representative of historical data points from said specific lane.

### Claim 30

A computer readable medium containing an executable program for predicting traffic on a transportation network, said transportation network comprised of links, said links constituting a relationship vector, wherein the program performs the steps of
a) providing data points related to real time traffic conditions on each link, wherein at least one data point is missing for a given link;
b) estimating the value of said missing data point; and
c) using said estimated value to predict traffic for at least a portion of said transportation network by deviation from a historical traffic pattern of said network.

### Claim 31

A computer readable medium containing an executable program for providing navigational guidance to a vehicle over a transportation network, said transportation network comprised of routes with traffic signals, wherein the program performs the steps of:
a) providing to a processor: trip information, said trip information comprising an origin and a destination for said vehicle; and a radius, said radius measured from said vehicle when said vehicle is on said transportation network;
b) obtaining data from one or more traffic signals within said radius, at intervals of time, said data relating to one or both of the following:
(i) information on the state of at least one of said traffic signals for a respective interval of time; and
(ii) routing table information, said routing table information indicative of state of traffic for routes to said destination on said transportation network
c) processing said data with said trip information to identify optimal route choices to said destination on said transportation network for said vehicle; and
d) providing said optimal route choices to said vehicle.

### Claim 32

A computer readable medium containing an executable program for predicting traffic for a specific lane on a transportation network comprised of links wherein said links constitute a relationship vector, wherein said program performs the steps of
a) providing data points related to real time traffic conditions for a specific lane in a link of a transportation network;
b) updating a template representative of a historical traffic pattern for said specific lane in accordance with said data points; and
c) providing a prediction of traffic for said specific lane in accordance with said updated template.
