Traffic Speed Modeling

FIELD

0001The following disclosure relates to traffic speed modeling.

BACKGROUND

0002Road systems may involve collections of dozens, hundreds, or even thousands of individual roads or sections of road known as segments. A particular road system may have varying traffic densities, flows, events, or conditions in different geographic positions throughout the road system.

0003Accurate modeling of traffic speeds for all road segments is important to maintain most modern maps and to facilitate route planning software. Multiple applications and services depend on accurate traffic speed modeling. Updated traffic speed information is important to properly route vehicles and provide up to the minute estimated time of arrivals. Models should be able to take into consideration recent data, historical data, and/or vehicular behavior on multiple types of roads.

SUMMARY

0004In an embodiment, a server receives traffic data generated by one or more devices configured to record data indicating speeds of vehicles traveling a road segment. The server separates, with a processor, the traffic data into zero speed data and non-zero speed data. The server determines, with the processor, a zero speed data characteristic value of the zero speed data. The server determines, with the processor, at least one non-zero speed data characteristic value of the non-zero speed data. The server generates, with the processor, a representative traffic value for the road segment as a function of the zero speed characteristic value and the non-zero speed characteristic value.

0005In an embodiment, an apparatus comprising at least one processor and a memory including computer program code and operable to store traffic data generated by devices configured to record traffic data representing speeds of vehicles traveling a road segment. The at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to separate the traffic data into zero speed data and non-zero speed data, determine a zero speed characteristic value of the zero speed data, determine at least one non-zero speed characteristic value of the non-zero speed data, and generate a representative traffic value for the road segment as a function of the zero speed characteristic value and the non-zero speed characteristic value.

0006In an embodiment, a method comprising determining a location data value for a mobile device, sending the location data value to a server, and receiving a representative traffic data value from the server, wherein the representative traffic data value is generated by the server as a function of at least one zero speed data characteristic value from zero speed values and at least one non-zero speed data characteristic value of the non-zero speed data from nonzero speed values.

BRIEF DESCRIPTION OF THE DRAWINGS

0007Exemplary embodiments of the present invention are described herein with reference to the following drawings.

0008<figref idref="DRAWINGS">FIG. 1</figref> illustrates an example system for modeling traffic speed.

0009<figref idref="DRAWINGS">FIG. 2</figref> illustrates an example method for modeling traffic speed.

0010<figref idref="DRAWINGS">FIG. 3</figref> illustrates an example method for modeling traffic speed using histograms.

0011<figref idref="DRAWINGS">FIGS. 4A-C</figref> illustrate an example traffic speed model for free flowing traffic.

0012<figref idref="DRAWINGS">FIGS. 5A-C</figref> illustrate an example traffic speed model for arterial traffic.

0013<figref idref="DRAWINGS">FIG. 6A-C</figref> illustrate a Delta-Gamma distribution for arterial traffic.

0014<figref idref="DRAWINGS">FIGS. 7A and 7B</figref> illustrate example traffic speed data and histograms.

0015<figref idref="DRAWINGS">FIG. 8</figref> illustrates an example server.

0016<figref idref="DRAWINGS">FIG. 9</figref> illustrates an example mobile device.

0017<figref idref="DRAWINGS">FIG. 10</figref> illustrates an example method for modeling traffic speeds.

DETAILED DESCRIPTION

0018A Gaussian (or normal) distribution is a very commonly occurring continuous probability distribution (i.e. a function that tells the probability that any real observation will fall between any two real limits or real numbers) as the curve approaches zero on either side. <figref idref="DRAWINGS">FIG. 3A</figref> shows an example of this distribution.

0019The normal assumption is most valid for modeling traffic flow on highways where average speeds are high, and have relatively low variability. However, even there, a Gaussian distribution does not represent the constraint that speed be a positive value. This becomes significant during congested conditions, when average speed is low, because a normal distribution models a finite and large probability of segment travel times being below zero.

0020For non-limited access highways, a Gaussian distribution for traffic data points breaks down because on arterials and other secondary and tertiary roadways it is common for vehicles to be stationary for periods of time, even under free-flow conditions, and because speeds in a given direction on a segment of roadway cannot be negative. A more suitable model for arterial traffic speeds may be the mixture of a Dirac delta function at zero, with a Gamma distribution of continuous speeds greater than zero.

0021<figref idref="DRAWINGS">FIG. 1</figref> illustrates an example system for modeling traffic speeds. In <figref idref="DRAWINGS">FIG. 1</figref>, one or more probes <b>130</b>, <b>131</b> and/or other sensors are connected to the server <b>125</b> though the network <b>127</b>. A database <b>123</b> is also connected to the server <b>125</b>. The database <b>123</b> and server <b>125</b> make up a navigation system <b>121</b>. A mobile device <b>122</b> is connected to the server <b>125</b> through the network <b>127</b>. Additional, different, or fewer components may be included.

0022The probe(s) <b>130</b>, <b>131</b> may be a mobile device or a tracking device that provides samples of data for the location of a vehicle. The probe(s) <b>130</b>, <b>131</b> may be mobile phones running specialized applications that collect location data as people travel roads as part of their daily lives. The probe(s) <b>130</b>,<b>131</b> may also be integrated in or with a vehicle.

0023Traffic speed data may also be collected with a sensor, or collection of sensors, such as an inductance loop or optical detector (e.g., camera, light detection and ranging (LiDAR), or radar device). The probe(s) <b>130</b>, <b>131</b> and/or other sensor(s) may report the quantity, frequency, and/or speed of vehicles as they travel road segments. The road segment may be determined based on the geographical coordinates of the probe (e.g., global positioning system (GPS)).

0024The one or more probes <b>130</b>, <b>131</b> and/or other sensor(s) may be designed to measure the volume, occupancy, and speed of a large percentage of vehicular traffic for a given point on a roadway. This might be for fleet tracking purposes, or anonymized data collection from cell phones. Generally, only a percentage of the total vehicle population may be available.

0025The network <b>127</b> may include wired networks, wireless networks, or combinations thereof. The wireless network may be a cellular telephone network, a wireless local area network, such as an 802.11, 802.16, 802.20, WiMax (Worldwide Interoperability for Microwave Access) network, or wireless short range network. Further, the network <b>127</b> may be a public network, such as the Internet, a private network, such as an intranet, or combinations thereof, and may utilize a variety of networking protocols now available or later developed including, but not limited to TCP/IP based networking protocols.

0026The term server is used herein to collectively include the computing devices in a navigation system <b>121</b> for creating, maintaining, accessing, and updating the traffic speed database(s) <b>123</b>. The server <b>125</b> may be a host for a website or web service such as a mapping service and/or a navigation service. The mapping service may provide maps generated from the geographic data of the database <b>123</b>, and the navigation service may generate routing or other directions from the geographic data of the database <b>123</b>. Additional, different, or fewer components may be included.

0027The terms database and traffic speed database refer to a set of data or map data stored in a storage medium and may not necessarily reflect specific requirements as to the relational organization of the data or the map data. The database <b>123</b> may be a geographic database including road segments and road attributes. The database <b>123</b> may contain historical traffic speed data for each road segment.

0028<figref idref="DRAWINGS">FIG. 2</figref> illustrates a flow chart of an example embodiment for modeling traffic speed. As presented in the following sections, the acts may be performed using any combination of the components indicated in <figref idref="DRAWINGS">FIG. 1</figref>, <figref idref="DRAWINGS">FIG. 8</figref>, or <figref idref="DRAWINGS">FIG. 9</figref>. The following acts may be performed by mobile device <b>122</b>, server <b>125</b>, or a combination thereof. Additional, different, or fewer acts may be provided. The acts are performed in the order shown or other orders. The acts may also be repeated.

0029At act <b>250</b>, a server <b>125</b> receives traffic speed data generated by one or more devices <b>130</b>,<b>131</b> configured to record data indicating speeds of vehicles traveling a road segment. The traffic speed data may be one or more values that indicate a road segment identification, a speed of a vehicle, and a time the data point was recorded.

0030The traffic speed data may be generated by one or more devices <b>130</b>, <b>131</b> such as one or more probes <b>130</b>, <b>131</b> and/or other sensor(s). The probe(s) <b>130</b>, <b>131</b><i>s </i>and/or other sensor(s) may also be designed to measure the volume, occupancy and speed of vehicular traffic for a given point on a road segment.

0031Traffic speed data may be represented according to individual road segments. A road segment may be data representing a length or piece of road. Road segments may be defined according to nodes or intersections. For example, a road segment may extend from one node to another node. In rural areas, road segments may be relatively large because the distances between intersections are lengthy. In urban areas, road segments may be relatively small because the distances between intersections are short.

0032Recent traffic speed data may be collected, perhaps for a period of one to fifteen minutes. This recent traffic speed data may be taken to be representative of the current situation on a roadway or road segment. Because of the limited time-frame of collection, the recent traffic speed data may be sparse. Data may also be aggregated over time, such that a historical data model of generalized vehicle traffic speed can be generated. This may be important to validate how representative the recent traffic speed data is, and correct a model as needed. The recent traffic speed data may also include recent speed data collected from mobile devices and/or vehicles currently traveling the roadway.

0033At act <b>260</b>, the server <b>125</b> separates the traffic speed data into zero speed data and non-zero speed data. The zero speed data may include, for example, vehicles stopped at a traffic light or at a stop sign.

0034At act <b>270</b>, the server <b>125</b> determines a zero speed data characteristic value of the zero speed data. The zero speed data characteristic value may be determined using any technique. The zero speed data characteristic value may be a probability that a vehicle is stopped. In an embodiment that uses the probability that a vehicle is stopped, the number of zero speed data points is the numerator and the number of total data points is the denominator.

0035At act <b>280</b>, the server <b>125</b> determines at least one non-zero speed data characteristic value of the non-zero speed data. The non-zero speed data characteristic value may be determined using any technique. In an embodiment, to determine at least one non-zero speed data characteristic value, the server <b>125</b> may model a Delta-Gamma distribution of traffic flow speeds. Modeling the distribution of traffic flow speeds may require learning the parameters of a suitable model based on samples of speed information from vehicles traveling on those roadways over time. The server <b>125</b> may use Bayes' rule to help model the speed of vehicles.

0036The server <b>125</b> defines x to be the speed of a vehicle on a segment at a given time. The goal is to learn a set of model parameters, {θ} given a series of samples of x that maximize p({θ}|{x}). By Bayes' rule:

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><mo>{</mo><mi>θ</mi><mo>}</mo></mrow><mo>|</mo><mrow><mo>{</mo><mi>x</mi><mo>}</mo></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><mo>{</mo><mi>x</mi><mo>}</mo></mrow><mo>|</mo><mrow><mo>{</mo><mi>θ</mi><mo>}</mo></mrow></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mo>{</mo><mi>θ</mi><mo>}</mo></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mo>{</mo><mi>x</mi><mo>}</mo></mrow><mo>)</mo></mrow></mrow></mfrac></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>1</mn></mrow></mtd></mtr></mtable></math></maths><img file="US2016364983A1_D0001.tif" />

0037The server <b>125</b> determines the posterior distribution, p({θ}|{x}). By observing the empirical distributions of speeds on arterial segments as shown in <b>5</b>C, x may be generated from a distribution of the Delta-Gamma form which combines a spike in probability density at x=0 with a positive-skewed, nonnegative distribution of speeds above zero. Thus, the server <b>125</b> uses as a form for the posterior distribution, p(x|{θ}):

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>|</mo><mrow><mo>{</mo><mi>θ</mi><mo>}</mo></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mrow><mi>x</mi><mo>|</mo><mi>a</mi></mrow><mo>,</mo><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>a</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>δ</mi><mo></mo><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mi>a</mi></mrow><mo>)</mo></mrow><mo></mo><mfrac><mn>1</mn><mrow><mi>Γ</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mfrac><mo></mo><msup><mi>x</mi><mrow><mi>k</mi><mo>-</mo><mn>1</mn></mrow></msup><mo></mo><msup><mi></mi><mrow><mrow><mo>-</mo><mi>ω</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>x</mi></mrow></msup></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>2</mn></mrow></mtd></mtr></mtable></math></maths><img file="US2016364983A1_D0002.tif" />

0038Where Γ(k) is the Gamma function (continuous factorial) and aε[0,1], kε[1,+∞], ωε[0,+∞] represent the parameters to be estimated. To clarify:

0000a is probability of zero speed vehicles (eg. % of cars stopped at the “light”) <br /> x is the speed of a vehicle (km/h) on a segment at a point in time. <br /> k and ω are not interpretable, although the two can be converted into the mean and variance of the gamma distribution via a change of variables.

0039The Priors, p({9}), over the parameters may be separated into two elements; the first, the prior on a, which since a simply represented the probability of x being exactly equal to zero is a Bernoulli distribution for which the conjugate prior is Beta(α,β) where α=1+number of zero speeds, β=1+number of non-zero speeds. The second is the gamma distribution over non-zero speeds for which the conjugate prior has the form:

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow><mo>∼</mo><mfrac><mrow><msup><mi>p</mi><mrow><mi>k</mi><mo>-</mo><mn>1</mn></mrow></msup><mo></mo><msup><mi></mi><mrow><mrow><mo>-</mo><mi>ω</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>q</mi></mrow></msup></mrow><mrow><msup><mrow><mi>Γ</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mi>r</mi></msup><mo></mo><msup><mi>ω</mi><mrow><mo>-</mo><mi>ks</mi></mrow></msup></mrow></mfrac></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>3</mn></mrow></mtd></mtr></mtable></math></maths><img file="US2016364983A1_D0003.tif" />

0040so that:

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><mrow><msup><mi>p</mi><mrow><mi>k</mi><mo>-</mo><mn>1</mn></mrow></msup><mo></mo><msup><mi></mi><mrow><mrow><mo>-</mo><mi>ω</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>q</mi></mrow></msup></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mi>log</mi><mo></mo><mrow><mo>(</mo><mrow><msup><mrow><mi>Γ</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mi>r</mi></msup><mo></mo><msup><mi>ω</mi><mrow><mo>-</mo><mi>ks</mi></mrow></msup></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mi>Constant</mi></mrow><mo>=</mo><mrow><mrow><mrow><mo>(</mo><mrow><mi>k</mi><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow><mo></mo><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>p</mi></mrow><mo>-</mo><mrow><mi>ω</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>q</mi></mrow><mo>-</mo><mrow><mi>r</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>Γ</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mi>ks</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>ω</mi></mrow><mo>+</mo><mi>Constant</mi></mrow></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>4</mn></mrow></mtd></mtr></mtable></math></maths><img file="US2016364983A1_D0004.tif" />

0041Which has optima where

0000<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mfrac><mrow><mrow><mo>∂</mo><mi>log</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mo>∂</mo><mi>k</mi></mrow></mfrac><mo>=</mo><mrow><mrow><mn>0</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>and</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mfrac><mrow><mrow><mo>∂</mo><mi>log</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mo>∂</mo><mi>ω</mi></mrow></mfrac></mrow><mo>=</mo><mn>0</mn></mrow></mrow><mo>;</mo></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><mfrac><mrow><mrow><mo>∂</mo><mi>log</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mo>∂</mo><mi>k</mi></mrow></mfrac><mo>=</mo><mrow><mrow><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>p</mi></mrow><mo>-</mo><mrow><mfrac><mi>r</mi><mrow><mi>Γ</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mfrac><mo></mo><mfrac><mrow><mo>∂</mo><mrow><mi>Γ</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mrow><mrow><mo>∂</mo><mi>k</mi></mrow></mfrac></mrow><mo>+</mo><mrow><mi>s</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>log</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>ω</mi></mrow></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>5</mn></mrow></mtd></mtr><mtr><mtd><mrow><mfrac><mrow><mrow><mo>∂</mo><mi>log</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow></mrow><mrow><mo>∂</mo><mi>ω</mi></mrow></mfrac><mo>=</mo><mrow><mrow><mo>-</mo><mi>q</mi></mrow><mo>+</mo><mfrac><mi>ks</mi><mi>ω</mi></mfrac></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>6</mn></mrow></mtd></mtr></mtable></math></maths><img file="US2016364983A1_D0005.tif" />

0042So that:

0043Log Posterior:

0000<br />log <i>p</i>(<i>x|k</i>,ω)=(<i>k−</i>1)log <i>x−ωx</i>−log Γ(<i>k</i>)  Equation 7:

0044Given this model, the server <b>125</b> can decompose the Bayesian Estimation problem into two steps, firstly updating the hyper parameters for a:

0000<br />α←α+Σ_i=1ⁿ<i>x</i>_bin⁽ⁱ⁾<i>,β←β+n−Σ</i>_i=1ⁿ<i>x</i>_bin⁽ⁱ⁾,  Equation 8:

0045Where x_binis an indicator variable specifying whether x=0.

0046Then updating the hyper parameters for k, co as follows, as additional samples of x arrive:

0000<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mi>p</mi><mo>←</mo><mrow><mi>p</mi><mo></mo><mrow><munder><mo>∏</mo><mrow><mrow><mi>i</mi><mo>∈</mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow><mo>=</mo><mn>0</mn></mrow></munder><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow></mrow></mrow></math></maths><maths id="MATH-US-00006-2" num="00006.2"><math overflow="scroll"><mrow><mi>q</mi><mo>←</mo><mrow><mi>q</mi><mo>+</mo><mrow><munder><mo>∑</mo><mrow><mrow><mi>i</mi><mo>∈</mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow><mo>=</mo><mn>0</mn></mrow></munder><mo></mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow></mrow></mrow></math></maths><maths id="MATH-US-00006-3" num="00006.3"><math overflow="scroll"><mrow><mi>r</mi><mo>←</mo><mrow><mi>r</mi><mo>+</mo><mi>n</mi><mo>-</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><msubsup><mi>x</mi><mi>bin</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></math></maths><maths id="MATH-US-00006-4" num="00006.4"><math overflow="scroll"><mrow><mi>s</mi><mo>←</mo><mrow><mi>s</mi><mo>+</mo><mi>n</mi><mo>-</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><msubsup><mi>x</mi><mi>bin</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></math></maths>

0047At act <b>290</b>, the server <b>125</b> generates a representative traffic value for the road segment. The server <b>125</b> may use Bayes' rule to estimate a representative traffic value using the zero speed characteristic value and the non-zero characteristic value.

0048These update rules may be modified to incorporate time windowing information, and the blending of long-term historical data, recent historical data and recent time-window data points depending on the application of the estimate, which the server <b>125</b> performs below.

0049In this embodiment, recent or near-recent data points (within some time window, τ) may be scarce. As a result, the available recent data may be blended with time-of-day, day-of-week historical estimates of conditions. <figref idref="DRAWINGS">FIG. 7A</figref> illustrates historic windows and recent windows with 15 minute periods. Other time periods (e.g., 30 minutes, 1 hour, 2 hours, 12 hours, 1 day or others) may be substituted for the 15 minute epochs. Multiple time periods may be used depending on geography (e.g., rural versus urban) or time (e.g., night versus day). Blending the recent data with historical data essentially means that for a given epoch (period) the server <b>125</b> may adapt the updated rules above according to the following strategy.

0050A new estimate of recent conditions on a segment may be computed every epoch, using all data points received within an adjustable time window, T. Each estimate comprises three components; the parameters of the historical distribution for a current epoch, the previous estimated parameters for a previous epoch of recent estimation and the current epoch.

0000<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mrow><msubsup><mi>p</mi><mi>t</mi><mrow><mo>(</mo><mi>epoch</mi><mo>)</mo></mrow></msubsup><mo></mo><mrow><munder><mo>∏</mo><mrow><mrow><mi>i</mi><mo>∈</mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow><mo>=</mo><mn>0</mn></mrow></munder><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow></mrow></math></maths><maths id="MATH-US-00007-2" num="00007.2"><math overflow="scroll"><mrow><msub><mi>q</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>←</mo><mrow><msubsup><mi>q</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow><mrow><mo>(</mo><mi>hist</mi><mo>)</mo></mrow></msubsup><mo>+</mo><msubsup><mi>q</mi><mi>t</mi><mrow><mo>(</mo><mi>epoch</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mrow><munder><mo>∑</mo><mrow><mrow><mi>i</mi><mo>∈</mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow><mo>=</mo><mn>0</mn></mrow></munder><mo></mo><msup><mi>x</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msup></mrow></mrow></mrow></math></maths><maths id="MATH-US-00007-3" num="00007.3"><math overflow="scroll"><mrow><msub><mi>r</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>←</mo><mrow><msubsup><mi>r</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow><mrow><mo>(</mo><mi>hist</mi><mo>)</mo></mrow></msubsup><mo>+</mo><msubsup><mi>r</mi><mi>t</mi><mrow><mo>(</mo><mi>epoch</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi><mo>-</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><msubsup><mi>x</mi><mi>bin</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></math></maths><maths id="MATH-US-00007-4" num="00007.4"><math overflow="scroll"><mrow><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>←</mo><mrow><msubsup><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow><mrow><mo>(</mo><mi>hist</mi><mo>)</mo></mrow></msubsup><mo>+</mo><msubsup><mi>s</mi><mi>t</mi><mrow><mo>(</mo><mi>epoch</mi><mo>)</mo></mrow></msubsup><mo>+</mo><mi>n</mi><mo>-</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><msubsup><mi>x</mi><mi>bin</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></math></maths>

0051And for hyper parameters of the prior for the Bernoulli distribution:

0000<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><mrow><mi>α</mi><mo>←</mo><mrow><msup><mi>α</mi><mrow><mo>(</mo><mi>hist</mi><mo>)</mo></mrow></msup><mo>+</mo><msup><mi>α</mi><mrow><mo>(</mo><mi>epoch</mi><mo>)</mo></mrow></msup><mo>+</mo><mrow><msubsup><mi>Σ</mi><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo></mo><msubsup><mi>x</mi><mi>bin</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msubsup></mrow></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><mi>β</mi><mo>←</mo><mrow><msup><mi>β</mi><mrow><mo>(</mo><mi>hist</mi><mo>)</mo></mrow></msup><mo>+</mo><msup><mi>β</mi><mrow><mo>(</mo><mi>epoch</mi><mo>)</mo></mrow></msup><mo>+</mo><mi>n</mi><mo>-</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo></mo><msubsup><mi>x</mi><mi>bin</mi><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></msubsup></mrow></mrow></mrow></mrow></math></maths><img file="US2016364983A1_D0006.tif" />

0052An optimal ratio for recent to historical data may be refined over time as the traffic speed modeling becomes clear. The server <b>125</b> may contain separate specific ratios or recent to historical data that deliver the greatest accuracy and stability in light of the road segment attributes and environment. Time of day and/or day of week matching may be specific enough to allow for traffic speed monitoring even when there is little to no recent data available for certain road segments. In another embodiment, metadata for each road segment and traffic speed estimation may be stored in the database so that road segments may be grouped and analyzed per certain road attributes. Certain road segments may follow similar traffic speed estimates even with few or no recent data points.

0053In addition to weighting historical data versus recent data, other model parameters may be adjusted to maximize accuracy. Different sets of data may be collected to produce a model. Such parameters as Recent Window, Recent Data weight (mentioned above), or minimum Recent data points may be adjusted upwards or downwards.

0054One example is to set these parameters as follows: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0055">Recent Weight=1</li><li id="ul0002-0002" num="0056">Minimum Recent points=2</li><li id="ul0002-0003" num="0057">Recent window size in minutes=15</li></ul></li></ul>

0058Another example is: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0059">Recent Window (minutes): 15</li><li id="ul0004-0002" num="0060">Recent Weight: 1-3</li><li id="ul0004-0003" num="0061">Recent Data Points: 1 <br /> These parameters may be tuned by using ground truth data and validation data. Ground truth data is data acquired from specific vehicles driven with the flow of traffic. Validation data is data that is not sampled for use in the model. The purpose of both validation and ground truth data is to act as a benchmark to compare with the model's predicted results. Ideally, one would want to use all of the ground truth data as a benchmark. However, the amount of ground truth data is limited. As a result, it is necessary to sample from the recent data to represent the ground truth. Therefore, a resampling strategy is applied to produce the validation data set. </li></ul></li></ul>

0062In another embodiment, the server <b>125</b> performs maximum likelihood rather than full Bayesian estimation. In this approach, the server <b>125</b> directly estimates a by computing the percentage of zero speeds of a weighted combination of historical data for the epoch and the recent data in the corresponding time window. Then the server <b>125</b> uses a maximum-likelihood estimation to estimate the Gamma Distribution parameters k, ω based on the non-zero data points in the combination. This embodiment may reduce the computational complexity of performing a full Bayesian estimation.

0063<figref idref="DRAWINGS">FIG. 3</figref> illustrates a flow chart of an example embodiment for modeling traffic speed. As presented in the following sections, the acts may be performed using any combination of the components indicated in <figref idref="DRAWINGS">FIG. 1</figref>, <figref idref="DRAWINGS">FIG. 8</figref>, or <figref idref="DRAWINGS">FIG. 9</figref>. The following acts may be performed by mobile device <b>122</b>, server <b>125</b>, or a combination thereof. Additional, different, or fewer acts may be provided. The acts are performed in the order shown or other orders. The acts may also be repeated.

0064In certain embodiments, the probabilistic model may be supplemented with a histogram which also incorporates the delta function. A histogram may be used as representation of the traffic speed data. A histogram is an estimate of the probability distribution of the traffic speed data.

0065At act <b>301</b>, a server <b>125</b> receives recent traffic speed data from one or more devices <b>130</b>, <b>131</b> configured to record data indicating speeds of vehicles traveling a road segment. The recent traffic speed data may be a collection of data including values for speed, data/time, and a road segment identification.

0066At act <b>303</b>, the server <b>125</b> receives historical traffic speed data from a database <b>123</b>. The historical traffic speed data may include values for speed, data/time, and a road segment identification. The historical traffic speed data may be formatted into a histogram containing separate buckets for one or more speed bins. This distribution may be called the historical traffic speed Delta-Histogram. In this embodiment, an empirical delta-histogram may contain 21-bins as follows: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0067">[0], [0.5 kph], [5 kph,10 kph], [10 kph,15 kph], [15 kph,20 kph], [20 kph,25 kph], [25 kph,30 kph], [30 kph,35 kph], [35 kph,40 kph], [40 kph,45 kph], [45 kph,50 kph], [50 kph,55 kph], [55 kph,60 kph], [60 kph,65 kph], [65 kph,70 kph], [70 kph,75 kph], [75 kph,80 kph], [80 kph,85 kph], [85 kph,90,kph], [90 kph,95 kph], [95 kph+]</li></ul></li></ul>

0068In certain embodiments, the database <b>123</b> will also store the Delta-Gamma parameter(s) for the historical traffic speed data. The database <b>123</b> may store these parameter(s) in association with the road segment identifications. In such an embodiment, the parameters would not have to be recalculated each time the historical traffic speed data was used. In certain embodiments, the database <b>123</b> may only store the histogram values for the historical traffic speed data.

0069At act <b>305</b>, the server <b>125</b> generates the percentage of zero speeds in the recent traffic speed data. The percentage is a function of the amount of zero speed data points versus the amount of total traffic speed data points.

0070At act <b>307</b>, the server <b>125</b> determines gamma distribution parameters based one or more non-zero data points in the recent traffic speed data. The gamma distribution parameters may be converted into the mean and variance of the gamma distribution via a change of variables.

0071At act <b>309</b>, the server <b>125</b> generates a recent traffic distribution using the percentage of zero speeds and the gamma distribution parameters. The representative traffic model may estimate the speed of a vehicle on a road segment at a point in time.

0072At act <b>311</b>, the server <b>125</b> generates a recent traffic speed data histogram using the one or more recent speed values. The recent traffic speed data histogram may contain 21-bins as follows: <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0073">[0], [0.5 kph], [5 kph,10 kph], [10 kph,15 kph], [15 kph,20 kph], [20 kph,25 kph], [25 kph,30 kph], [30 kph,35 kph], [35 kph,40 kph], [40 kph,45 kph], [45 kph,50 kph], [50 kph,55 kph], [55 kph,60 kph], [60 kph,65 kph], [65 kph,70 kph], [70 kph,75 kph], [75 kph,80 kph], [80 kph,85 kph], [85 kph,90,kph], [90 kph,95 kph], [95 kph+]</li></ul></li></ul>

0074At act <b>313</b>, the server <b>125</b> generates the final delta histogram using the recent traffic speed data histogram and the historical traffic speed data histogram. To compute the overall estimate of current traffic conditions, the recent traffic speed data histogram and the historical traffic speed histograms may be combined into a single distribution, with recent to historical weighting, as follows:

0000<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>v</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><mfrac><mi>w</mi><mrow><mn>1</mn><mo>+</mo><mi>w</mi></mrow></mfrac><mo></mo><msub><mi>r</mi><mi>i</mi></msub></mrow><mo>+</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>+</mo><mi>w</mi></mrow></mfrac><mo></mo><msub><mi>h</mi><mi>i</mi></msub></mrow></mrow></mrow></mtd><mtd><mrow><mi>Equation</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>9</mn></mrow></mtd></mtr></mtable></math></maths><img file="US2016364983A1_D0007.tif" />

0000Where v_iis the output histogram speed count for bucket I; r_iis the recent speed count for bucket i from the Delta-Gamma window; h_iis the historic speed count for bucket i from the appropriate Delta-Gamma epoch; w is a weighting factor tuned per model tuning.

0075In certain embodiments, the server <b>125</b> may allow the combination of path data (connected segments of at least two data points) and single probe point data (single GPS location, velocity data points that cannot be successfully connected) for recent reasoning about speed on a given segment. Using the Delta-Gamma histogram, the server <b>125</b> may first generate the speed histograms for both the path and single recent data points separately. If there is path data, the single point data may be ignored. If there is a lack of path data, the single point data may be combined with the recent path data and/or the historic path data into a single hybrid recent delta-histogram.

0076<figref idref="DRAWINGS">FIGS. 4A-C</figref> illustrate a traffic speed model for free flowing traffic. <figref idref="DRAWINGS">FIG. 4B</figref> illustrates free flowing traffic on a segment of a highway <b>403</b> or freeway with a number of vehicles <b>401</b> traveling from left to right. The distribution of speeds may be illustrated by a Gaussian distribution as shown in <figref idref="DRAWINGS">FIG. 4A</figref>. <figref idref="DRAWINGS">FIG. 4A</figref> is a Gaussian distribution with speed (X Axis) of the vehicles <b>401</b> and number of vehicles (Y axis). The distribution of vehicle speeds will tend to bunch around a peak <b>405</b> of the curve. This peak will generally be centered on an expected speed for the roadway at the free flowing condition, if there is free flowing traffic. Vehicles speeds may drop, but they will generally drop for every vehicle on the roadway. <figref idref="DRAWINGS">FIG. 4C</figref> illustrates a fully congested segment of a roadway. Collected speeds here will be close to zero which may still be represented by a Gaussian distribution with a peak near zero.

0077<figref idref="DRAWINGS">FIGS. 5A-C</figref> illustrate a traffic speed model for arterial traffic. <figref idref="DRAWINGS">FIGS. 5A and 5B</figref> illustrate vehicle <b>401</b> traffic on an arterial road <b>503</b>. In <figref idref="DRAWINGS">FIGS. 5A and 5B</figref>, there are stop signs <b>501</b>. In <figref idref="DRAWINGS">FIG. 5A</figref>, each vehicle <b>401</b> comes to a complete stop (zero speed). In <figref idref="DRAWINGS">FIG. 5B</figref>, after the stop sign <b>501</b>, the vehicle(s) <b>401</b> may return to the vehicle(s)′ previous speed. In <figref idref="DRAWINGS">FIG. 5A</figref>, there are three vehicles that have reached zero speed at the stop sign. Under a situation where there was not a stop sign, an observer of the traffic speed data might determine that there was heavy congestion (at least 3 out of 6 vehicles show zero speed). This would be an inaccurate representation of the road. Because of the stop sign <b>501</b>, zero speeds are to be expected. <figref idref="DRAWINGS">FIG. 5C</figref> shows actual traffic speed data that was collected over a large period of time on one or more arterial roads. There is a significant uptick <b>505</b> in collected speeds at or around the zero speed bucket due to expected stops.

0078<figref idref="DRAWINGS">FIG. 6A</figref> illustrates a Delta-Gamma distribution for arterial traffic. The Delta-Gamma distribution models arterial traffic more optimally due to it taking into effect the increase in expected zero speed vehicles. <figref idref="DRAWINGS">FIGS. 6B and 6C</figref> illustrate empirical data (histograms), Delta-Gamma fit <b>605</b> and Gaussian fits <b>607</b> to (A) a speed greater than zero data set and (B) a speed greater than five data set. The roadway segment are a stop sign impeded segment and a stop light-impeded arterial roadway segment. In both cases the Delta-Gamma fit accommodates the significant percentage of zero data points in the empirical data (histogram bars), which the two Gaussian fits ignore. The Gaussian Fit distributions are truncated at zero (0). In terms of the computed speed values both (A) and (B) Gaussian fits significantly incorrectly estimates the speed of traffic flow on the segments, whereas the simple mean of all recent speeds (including zeros) somewhat underestimates the average speed. The stop sign impeded roadway in the epoch considered shows a significantly higher percentage of zero speeds than the stop light impeded roadway in the epoch illustrated here.

0079<figref idref="DRAWINGS">FIGS. 7A-C</figref> illustrate traffic speed data and a histogram. In an embodiment using a histogram approach, the server <b>125</b> maintains the Delta-Histogram distribution of the historical data for a segment-epoch, instead of the raw data. This embodiment mitigates the need to propagate the historical raw data points for every link-epoch and the need for the iterative algorithm; by replacing the explicit Delta-Gamma probabilistic model with an empirical histogram and incorporating a Delta function. <figref idref="DRAWINGS">FIG. 7A</figref> illustrates an example of traffic speed data received. Recent speed data is shown with a large dot <b>701</b>. Historical traffic speed data is shown as a small dot <b>703</b>. The graph may be split into 15 minute epochs (periods). The data may be sorted by the epochs into historical <b>705</b> and recent 707.

0080From the traffic speed data (illustrated in <figref idref="DRAWINGS">FIG. 7A</figref>), the server may be able to use a Delta-Gamma function to create histograms such as those in <figref idref="DRAWINGS">FIG. 7B</figref>. In <figref idref="DRAWINGS">FIG. 7B</figref>, the traffic speed data has been separated into a histogram for both historical speed data and recent speed data. In <figref idref="DRAWINGS">FIG. 7B</figref>, the histograms do not contain the same amount of data as recent speed data may be more sparse than historical speed data.

0081<figref idref="DRAWINGS">FIG. 8</figref> illustrates an example server <b>125</b>. The server <b>125</b> includes a processor <b>800</b>, a communication interface <b>805</b>, and a memory <b>801</b>. The server <b>125</b> may be coupled to a database <b>123</b>. Additional, different, or fewer components may be provided in the server <b>125</b>.

0082The server <b>125</b> may be a host for a website or web service such as a mapping service and/or a navigation service. The mapping service may provide maps generated from the geographic data of the database <b>123</b>, and the navigation service may generate routing or other directions from the geographic data of the database <b>123</b>. The mapping service may also provide traffic information generated from historical traffic speed data included in the database <b>123</b>. Historical traffic speed data may be stored with each road segment. The server <b>125</b> may also provide recent or current traffic conditions using the representative traffic value. As mentioned above, historical and recent traffic speed data may be blended to produce a more accurate traffic speed value. This may be necessary where there are little to no recent data collected.

0083The communication interface <b>805</b> may be configured to receive mobile device data representing locations and movements of a plurality of mobile devices <b>122</b>. The processor <b>800</b> may be configured to calculate traffic speed data for segments of road. In an embodiment, the processor <b>800</b> is configured to calculate probabilities of vehicle speed and vehicle speed values for road segments. As such, the processor <b>800</b> is configured to determine a probability of vehicle speed of road segments of a road network the road network involving a plurality of road segments using historical speed data or recent speed data. The processor <b>800</b> is configured to provide an indication of the calculated current traffic speed of the road segments.

0084The controller <b>200</b> and/or processor <b>800</b> may include a general processor, digital signal processor, an application specific integrated circuit (ASIC), field programmable gate array (FPGA), analog circuit, digital circuit, combinations thereof, or other now known or later developed processor. The controller <b>200</b> and/or processor <b>800</b> may be a single device or combinations of devices, such as associated with a network, distributed processing, or cloud computing.

0085The memory <b>204</b> and/or memory <b>801</b> may be a volatile memory or a non-volatile memory. The memory <b>204</b> and/or memory <b>801</b> may include one or more of a read only memory (ROM), random access memory (RAM), a flash memory, an electronic erasable program read only memory (EEPROM), or other type of memory. The memory <b>204</b> and/or memory <b>801</b> may be removable from the mobile device <b>122</b>, such as a secure digital (SD) memory card.

0086The communication interface <b>205</b> and/or communication interface <b>305</b> may include any operable connection. An operable connection may be one in which signals, physical communications, and/or logical communications may be sent and/or received. An operable connection may include a physical interface, an electrical interface, and/or a data interface. The communication interface <b>205</b> and/or communication interface <b>305</b> provides for wireless and/or wired communications in any now known or later developed format.

0087The database <b>123</b> may include geographic data used for traffic and/or navigation-related applications. The geographic data may include data representing a road network or system including road segment data and node data. The road segment data represent roads, and the node data represent the ends or intersections of the roads. The road segment data and the node data indicate the location of the roads and intersections as well as various attributes of the roads and intersections. Other formats than road segments and nodes may be used for the geographic data. The geographic data may include structured cartographic data or pedestrian routes.

0088The database <b>123</b> may also include other attributes of or about the roads such as, for example, geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, and/or other navigation related attributes (e.g., one or more of the road segments is part of a highway or toll way, the location of stop signs and/or stoplights along the road segments), as well as points of interest (POIs), such as gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The database <b>123</b> may also contain one or more node data record(s) which may be associated with attributes (e.g., about the intersections) such as, for example, geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, and other navigation related attributes, as well as POIs such as, for example, gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The geographic data may additionally or alternatively include other data records such as, for example, POI data records, topographical data records, cartographic data records, routing data, and maneuver data.

0089The database <b>123</b> may include historical traffic speed data for one or more road segments. The database <b>123</b> may also include traffic attributes for one or more road segments. A traffic attribute may indicate that a road segment has a high probability of traffic congestion.

0090The server <b>125</b> may overlay traffic information on a map provided by the database. Traffic information may be indicated by any technique. For example, colors and/or patterns are used to indicate traffic speed levels. In an embodiment, traffic speed is indicated using a plateaued threshold reporting scheme. For example, a series of traffic flow thresholds may be established such that a traffic speed value for a segment falls into a category defined by traffic speed threshold category boundaries. Each traffic speed threshold category may be indicated differently. For example, a segment having a high traffic speed category may be presented to a user differently than a segment having a low traffic speed category. Any indication that differentiates the different traffic flow levels may be used. In an embodiment, colors may be used for characterizations of traffic flow, and indicating the different traffic flow level comprises using different colors for a first segment and a second segment. Varying patterns or other indications may also be used to indicate different traffic levels for segments. In an embodiment, a congestion factor may be used to determine values for traffic level categories. For example, a heavy traffic category may have a congestion factor value between 0 and 10%. A moderately heavy traffic category may have a congestion factor value between 10% and 30%. A moderate traffic category may have a congestion factor between 30% and 80%, and a light or free flow traffic category may have a congestion factor between 80% and 100%. Any number of levels or categories may be provided.

0091Different indications of traffic information for various road segments may be provided to a mobile device <b>122</b>, such as a mobile device <b>122</b> described below with respect to <figref idref="DRAWINGS">FIG. 9</figref>. The mobile device <b>122</b> may be provided a visible representation of the traffic levels. Different graphics may be used for different traffic levels. For example, the segments or lengths of road having different traffic levels are presented in different colors, instead of a singular color for the entire length of road.

0092The server <b>125</b> may use the traffic speed data for each road segment in a routing service. The server <b>125</b> through the network <b>127</b> may be in contact with a mobile device <b>122</b>. The mobile device <b>122</b> may then use this traffic information to plan a route through a road system, or modify a current route through a road system. Updating the road segments most likely to be congested more often presents an accurate view of the probable traffic state for a mobile device <b>122</b> at any given time.

0093The network <b>127</b> may include wired networks, wireless networks, or combinations thereof. The wireless network may be a cellular telephone network, a wireless local area network, such as an 802.11, 802.16, 802.20, WiMax (Worldwide Interoperability for Microwave Access) network, or wireless short range network. Further, the network <b>127</b> may be a public network, such as the Internet, a private network, such as an intranet, or combinations thereof, and may utilize a variety of networking protocols now available or later developed including, but not limited to TCP/IP based networking protocols.

0094The mobile device <b>122</b> may be referred to as a navigation device. The mobile device may also be used as one or more probes <b>130</b>, <b>131</b> or sensor(s). The mobile device <b>122</b> includes a controller <b>200</b>, a memory <b>204</b>, an input device <b>203</b>, a communication interface <b>205</b>, position circuitry <b>207</b>, movement circuitry <b>208</b>, and an output interface <b>211</b>. The output interface <b>211</b> may present visual or non-visual information such as audio information. Additional, different, or fewer components are possible for the mobile device <b>122</b>. The mobile device <b>122</b> is a smart phone, a mobile phone, a personal digital assistant (PDA), a tablet computer, a notebook computer, a personal navigation device (PND), a portable navigation device, and/or any other known or later developed mobile device. In an embodiment, a vehicle may be considered a mobile device, or the mobile device may be integrated into a vehicle.

0095The mobile device <b>122</b> may be configured to execute routing algorithms to determine an optimum route to travel along a road network from an origin location to a destination location in a geographic region. Using input(s) including traffic speed data from the server <b>125</b>, a mobile device <b>122</b> examines potential routes between the origin location and the destination location to determine the optimum route. The navigation device <b>122</b> may then provide the end user with information about the optimum route in the form of guidance that identifies the maneuvers required to be taken by the end user to travel from the origin to the destination location. Some mobile device <b>122</b> show detailed maps on displays outlining the route, the types of maneuvers to be taken at various locations along the route, locations of certain types of features, and so on.

0096The mobile device <b>122</b> may be integrated into an autonomous vehicle or a highly assisted driving (HAD) vehicle. The mobile device <b>122</b> may be configured as a navigation system for an autonomous vehicle or a HAD. An autonomous vehicle or HAD may take route instruction based on the traffic speed data provided to the mobile device <b>122</b>.

0097As described herein, an autonomous vehicle may refer to a self-driving or driverless mode in which no passengers are required to be on board to operate the vehicle. An autonomous vehicle may be referred to as a robot vehicle or an automated vehicle. The autonomous vehicle may include passengers, but no driver is necessary. These autonomous vehicles may park themselves or move cargo between locations without a human operator. Autonomous vehicles may include multiple modes and transition between the modes.

0098As described herein, a highly assisted driving (HAD) vehicle may refer to a vehicle that does not completely replace the human operator. Instead, in a highly assisted driving mode, the vehicle may perform some driving functions and the human operator may perform some driving functions. Vehicles may also be driven in a manual mode in which the human operator exercises a degree of control over the movement of the vehicle. The vehicles may also include a completely driverless mode. Other levels of automation are possible.

0099The autonomous or highly automated driving vehicle may include sensors for identifying the surrounding and location of the car. The sensors may include GPS, light detection and ranging (LIDAR), radar, and cameras for computer vision. Proximity sensors may aid in parking the vehicle. The proximity sensors may detect the curb or adjacent vehicles. The autonomous or highly automated driving vehicle may optically track and follow lane markings or guide markings on the road.

0100The positioning circuitry <b>207</b>, which is an example of a positioning system, is configured to determine a geographic position of the mobile device <b>122</b>. The movement circuitry <b>208</b>, which is an example a movement tracking system, is configured to determine movement of a mobile device <b>122</b>. The position circuitry <b>207</b> and the movement circuitry <b>208</b> may be separate systems, or segments of the same positioning or movement circuitry system. In an embodiment, components as described herein with respect to the mobile device <b>122</b> may be implemented as a static device. For example, such a device may not include movement circuitry <b>208</b>, but may involve a traffic or speed detecting input device <b>203</b> such as a Doppler radar velocity detector or a contact sensing traffic volume measurement apparatus.

0101The input device <b>203</b> may be one or more buttons, keypad, keyboard, mouse, stylist pen, trackball, rocker switch, touch pad, voice recognition circuit, or other device or component for inputting data to the mobile device <b>122</b>. The input device <b>203</b> and the output interface <b>211</b> may be combined as a touch screen, which may be capacitive or resistive. The output interface <b>211</b> may be a liquid crystal display (LCD) panel, light emitting diode (LED) screen, thin film transistor screen, or another type of display. The output interface <b>211</b> may also include audio capabilities, or speakers. In an embodiment, the input device <b>203</b> may involve a device having velocity detecting abilities.

0102<figref idref="DRAWINGS">FIG. 10</figref> illustrates a flow chart of an example embodiment for modeling traffic speed. As presented in the following sections, the acts may be performed using any combination of the components indicated in <figref idref="DRAWINGS">FIG. 1</figref>, <figref idref="DRAWINGS">FIG. 8</figref>, or <figref idref="DRAWINGS">FIG. 9</figref>. The following acts may be performed by mobile device <b>122</b>, server <b>125</b>, or a combination thereof. Additional, different, or fewer acts may be provided. The acts are performed in the order shown or other orders. The acts may also be repeated.

0103At act <b>1001</b>, the mobile device <b>122</b> generates recent traffic data indicating the speed of a vehicle traveling a road segment. The mobile device <b>122</b> may use the positioning circuit <b>207</b> or the movement circuit <b>208</b> to determine a speed of a vehicle. The mobile device <b>122</b> may also be connected to a speedometer in a vehicle or other speed measuring device.

0104The positioning circuitry <b>207</b> may include suitable sensing devices that measure the traveling distance, speed, direction, and so on, of the mobile device <b>122</b>. The positioning system may also include a receiver and correlation chip to obtain a GPS signal. Alternatively or additionally, the one or more detectors or sensors may include an accelerometer and/or a magnetic sensor built or embedded into or within the interior of the mobile device <b>122</b>. The accelerometer is operable to detect, recognize, or measure the rate of change of translational and/or rotational movement of the mobile device <b>122</b>. The magnetic sensor, or a compass, is configured to generate data indicative of a heading of the mobile device <b>122</b>. Data from the accelerometer and the magnetic sensor may indicate orientation of the mobile device <b>122</b>. The mobile device <b>122</b> receives location data from the positioning system. The location data indicates the location of the mobile device <b>122</b>.

0105The positioning circuitry <b>207</b> may include a Global Positioning System (GPS), Global Navigation Satellite System (GLONASS), or a cellular or similar position sensor for providing location data. The positioning system may utilize GPS-type technology, a dead reckoning-type system, cellular location, or combinations of these or other systems. The positioning circuitry <b>207</b> may include suitable sensing devices that measure the traveling distance, speed, direction, and so on, of the mobile device <b>122</b>. The positioning system may also include a receiver and correlation chip to obtain a GPS signal. The mobile device <b>122</b> receives location data from the positioning system. The location data indicates the location of the mobile device <b>122</b>.

0106The movement circuitry <b>208</b> may include gyroscopes, accelerometers, magnetometers, or any other device for tracking or determining movement of a mobile device. The gyroscope is operable to detect, recognize, or measure the current orientation, or changes in orientation, of a mobile device. Gyroscope orientation change detection may operate as a measure of yaw, pitch, or roll of the mobile device. The movement circuitry <b>208</b> may be used alone, or with the positioning circuitry <b>207</b> to determine mobile device <b>122</b> movement.

0107At act <b>1003</b> the mobile device <b>122</b> transmits the recent traffic data to a server <b>125</b>. The communication interface <b>205</b> is configured to send mobile device movement and position data to a server <b>125</b>. The movement and position data sent to the server <b>125</b> may be used to determine traffic flows for a road and segments of the road. The communication interface <b>205</b> may also be configured to receive data indicative of an indication of traffic speed for road segments.

0108The mobile device <b>122</b> may send positional data to the server <b>125</b>. The position circuitry <b>207</b> is configured to determine the current location of the mobile device <b>122</b>. The mobile device <b>122</b> may not send traffic speed data with the positional data. The mobile device <b>122</b> may receive a potential route though one or more inputs. The mobile device <b>122</b> sends the current location and the potential route (one or more road segments) to the server <b>125</b>.

0109At act <b>1005</b>, the mobile device <b>122</b> requests a representative traffic data value for one or more road segments. The mobile device <b>122</b> may request the traffic for a current road segment, determined by positional data, or a different road segment or a series of road segments that may be part of a planned/potential route.

0110At act <b>1007</b>, the mobile device <b>122</b> receives the representative traffic data value from the server <b>125</b>. The representative traffic data value is generated by the server <b>125</b>. The representative traffic data value is generated by: separating the recent traffic data into one or more zero speed values and non-zero speed values; generating a zero speed data characteristic value from the zero speed values; determining at least one non-zero speed data characteristic value of the non-zero speed data; and generating the representative traffic value for the road segment as a function of the zero speed characteristic value and the non-zero speed characteristic value.

0111The server <b>125</b> may also use historical traffic speed data when generating the representative traffic data value. In an example embodiment, the historical traffic speed data is combined with the recent traffic speed data. This may be necessary if there are few data points for a recent epoch. The representative traffic data may be sent by the server <b>125</b> as a single value, a function, a curve, a histogram, and/or a probability function.

0112At act <b>1009</b>, the mobile device updates a visual indication of a route or road segment with the representative traffic data value. Different indications of traffic information for various road segments may be used by the mobile device <b>122</b>. The mobile device <b>122</b> may use a visible representation of the traffic levels. Different graphics may be used for different traffic levels. For example, the segments or lengths of road having different traffic levels are presented in different colors, instead of a singular color for the entire length of road. Alternatively, the lengths of road may be displayed in different shapes or widths to convey the traffic levels. In one example, the mobile device <b>122</b> generates a message with the traffic level in graphical or alphanumeric values. In one example, the mobile device <b>122</b> generates an audible alert.

0113The communication interface <b>205</b> may receive the representative traffic data value from the server <b>125</b> through the network <b>127</b>. The controller may pull the data from the communication interface <b>205</b>. The controller <b>200</b> may be configured to determine a visual indication to a display that represents different traffic speed levels that may be derived from the representative traffic data value. The output interface <b>211</b> may be configured to present a visual indication of the traffic speeds to a user of the mobile device <b>122</b>. The output interface <b>211</b> may also be configured to present directions incorporating the traffic speeds for road segments.

0114The term “computer-readable medium” includes a single medium or multiple media, such as a centralized or distributed database, and/or associated caches and servers that store one or more sets of instructions. The term “computer-readable medium” shall also include any medium that is capable of storing, encoding or carrying a set of instructions for execution by a processor or that cause a computer system to perform any one or more of the methods or operations disclosed herein.

0115In a particular non-limiting, exemplary embodiment, the computer-readable medium can include a solid-state memory such as a memory card or other package that houses one or more non-volatile read-only memories. Further, the computer-readable medium can be a random access memory or other volatile re-writable memory. Additionally, the computer-readable medium can include a magneto-optical or optical medium, such as a disk or tapes or other storage device to capture carrier wave signals such as a signal communicated over a transmission medium. A digital file attachment to an e-mail or other self-contained information archive or set of archives may be considered a distribution medium that is a tangible storage medium. Accordingly, the disclosure is considered to include any one or more of a computer-readable medium or a distribution medium and other equivalents and successor media, in which data or instructions may be stored.

0116In an alternative embodiment, dedicated hardware implementations, such as application specific integrated circuits, programmable logic arrays and other hardware devices, can be constructed to implement one or more of the methods described herein. Applications that may include the apparatus and systems of various embodiments can broadly include a variety of electronic and computer systems. One or more embodiments described herein may implement functions using two or more specific interconnected hardware modules or devices with related control and data signals that can be communicated between and through the modules, or as portions of an application-specific integrated circuit. Accordingly, the present system encompasses software, firmware, and hardware implementations.

0117In accordance with various embodiments of the present disclosure, the methods described herein may be implemented by software programs executable by a computer system. Further, in an exemplary, non-limited embodiment, implementations can include distributed processing, component/object distributed processing, and parallel processing. Alternatively, virtual computer system processing can be constructed to implement one or more of the methods or functionality as described herein.

0118Although the present specification describes components and functions that may be implemented in particular embodiments with reference to particular standards and protocols, the invention is not limited to such standards and protocols. For example, standards for Internet and other packet switched network transmission (e.g., TCP/IP, UDP/IP, HTML, HTTP, HTTPS) represent examples of the state of the art. Such standards are periodically superseded by faster or more efficient equivalents having essentially the same functions. Accordingly, replacement standards and protocols having the same or similar functions as those disclosed herein are considered equivalents thereof.

0119A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a standalone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

0120The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit).

0121As used in this application, the term ‘circuitry’ or ‘circuit’ refers to all of the following: (a) hardware-only circuit implementations (such as implementations in only analog and/or digital circuitry) and (b) to combinations of circuits and software (and/or firmware), such as (as applicable): (i) to a combination of processor(s) or (ii) to portions of processor(s)/software (including digital signal processor(s)), software, and memory(ies) that work together to cause an apparatus, such as a mobile phone or server, to perform various functions) and (c) to circuits, such as a microprocessor(s) or a portion of a microprocessor(s), that require software or firmware for operation, even if the software or firmware is not physically present.

0122This definition of ‘circuitry’ applies to all uses of this term in this application, including in any claims. As a further example, as used in this application, the term “circuitry” would also cover an implementation of merely a processor (or multiple processors) or portion of a processor and its (or their) accompanying software and/or firmware. The term “circuitry” would also cover, for example and if applicable to the particular claim element, a baseband integrated circuit or applications processor integrated circuit for a mobile phone or a similar integrated circuit in server, a cellular network device, or other network device.

0123Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and anyone or more processors of any kind of digital computer. Generally, a processor receives instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer also includes, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

0124To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a device having a display, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.

0125Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

0126The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

0127The illustrations of the embodiments described herein are intended to provide a general understanding of the structure of the various embodiments. The illustrations are not intended to serve as a complete description of all of the elements and features of apparatus and systems that utilize the structures or methods described herein. Many other embodiments may be apparent to those of skill in the art upon reviewing the disclosure. Other embodiments may be utilized and derived from the disclosure, such that structural and logical substitutions and changes may be made without departing from the scope of the disclosure. Additionally, the illustrations are merely representational and may not be drawn to scale. Certain proportions within the illustrations may be exaggerated, while other proportions may be minimized. Accordingly, the disclosure and the figures are to be regarded as illustrative rather than restrictive.

0128While this specification contains many specifics, these should not be construed as limitations on the scope of the invention or of what may be claimed, but rather as descriptions of features specific to particular embodiments of the invention. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable sub-combination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a sub-combination or variation of a sub-combination.

0129Similarly, while operations are depicted in the drawings and described herein in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

0130One or more embodiments of the disclosure may be referred to herein, individually and/or collectively, by the term “invention” merely for convenience and without intending to voluntarily limit the scope of this application to any particular invention or inventive concept. Moreover, although specific embodiments have been illustrated and described herein, it should be appreciated that any subsequent arrangement designed to achieve the same or similar purpose may be substituted for the specific embodiments shown. This disclosure is intended to cover any and all subsequent adaptations or variations of various embodiments. Combinations of the above embodiments, and other embodiments not specifically described herein, are apparent to those of skill in the art upon reviewing the description.

0131The Abstract of the Disclosure is provided to comply with 37 C.F.R. §1.72(b) and is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. In addition, in the foregoing Detailed Description, various features may be grouped together or described in a single embodiment for the purpose of streamlining the disclosure. This disclosure is not to be interpreted as reflecting an intention that the claimed embodiments require more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive subject matter may be directed to less than all of the features of any of the disclosed embodiments. Thus, the following claims are incorporated into the Detailed Description, with each claim standing on its own as defining separately claimed subject matter.

0132It is intended that the foregoing detailed description be regarded as illustrative rather than limiting and that it is understood that the following claims including all equivalents are intended to define the scope of the invention. The claims should not be read as limited to the described order or elements unless stated to that effect. Therefore, all embodiments that come within the scope and spirit of the following claims and equivalents thereto are claimed as the invention.