Patent Description:
Modern navigation systems in vehicles include traffic flow estimation in order to provide users of vehicles with an estimated travel time for a particular route the user wants to take. However, traffic flow estimation is inaccurate and cumbersome since generally, only a limited number of sensors is available that provide sparse measurements of a real traffic situations in space and time. The main task in estimating the traffic flow is in processing these measurements and providing an estimate of a desired traffic variable for every position on a road and every point in time with the goal to reconstruct prevailing real traffic conditions most accurately.

In recent years, the availability of Floating Car Data (FCD) or other speed measurement data corresponding to the speed of a traffic flow in the road network has quickly spread and is increasingly available for traffic flow estimation in a road network. Using FCD is advantageous since it provides the possibility to obtain traffic data on each position along a road network. Besides this highly spatial resolution of available data, another advantage of FCD is the ever-decreasing cost of retrieving said data such that FCD will be further increasingly available in the future. However, time intervals between two reported trajectories in a road segment of the road network can vary strongly. In addition, FCD usually do not explicitly contain traffic state data - e.g. data on a traffic density (traffic density data) and/or a traffic flow (traffic flow data). Further, FCD is generally only sparsely available over the vehicle network. This sparsity of FCD and non-availability of traffic state data coupled with high spatiotemporal traffic dynamics along the road network are a major challenge for accurate traffic estimations.

To address the above problems, traffic flow estimation approaches have been introduced that take into consideration traffic dynamics. Said traffic flow estimation approaches can be classified into two categories. The first category comprises analytical flow models coupled with data assimilation techniques. However, in practice, said traffic flow estimation approaches require traffic state data (i.e. traffic flow data and traffic density data) in addition to FCD, thereby limiting the applicability in large scale since it adds further complexity to data acquisition and data processing for traffic flow estimation. The second category of traffic flow estimation comprises estimation methods based on empirical traffic theory. In particular, one approach uses FCD for estimating velocities in the road network by classifying traffic on the road network into one of the following traffic phases: free-flow-phase, synchronized flow phase and wide moving jam phase. A major drawback, however, is that velocities within the traffic phases are estimated as constant over space and time. Doing so strongly limits the accuracy of the said traffic phase estimations. Other methods belonging to the second category of approaches apply basic filtering operations to measured data. They tend to unconditionally propagate low velocities up- and downstream although low velocities might be part of stationary congestion upstream a bottleneck. Hence, when only sparse probe data is available, the estimated velocities in stationary congestion patterns lack accuracy.

<CIT> describes methods for reporting traffic conditions on road segments containing a bottleneck. The methods include calculating an amount of traffic congestion on a segment of a roadway, the segment containing a bottleneck, based on a free-flow speed specific to a subsection of the segment from which a report of an observed speed is received; and communicating, by the computer processor, information indicative of the amount of traffic congestion on the segment to a client. Apparatuses for reporting traffic conditions on road segments containing a bottleneck are also described.

<NPL>, describes assessing the Generalized Adaptive Smoothing Method as online traffic speed estimator with Floating Car Data as single source of data. The main challenges originating from the sparseness and delay in collecting FCD are addressed and a procedure using the GASM is proposed that allows estimating traffic velocities continuously. In a subsequent study, the method is applied to real FCD recorded by a huge fleet of privacy-aware mobile sensors during a common congestion pattern on German freeway A99. Focus of the study is to assess the accuracy of traffic speed estimation using the online GASM with respect to varying data densities and delays.

<NPL>, describes a method for obtaining spatio-temporal information from aggregated data of stationary traffic detectors, the "adaptive smoothing method", in which a nonlinear spatio-temporal lowpass filter is applied to the input detector data. This filter exploits the fact that, in congested traffic, perturbations travel upstream at a constant speed, while in free traffic, information propagates downstream. As a result, one obtains velocity, flow, or other traffic variables as smooth functions of space and time. Applications include traffic-state visualization, reconstruction of traffic situations from incomplete information, fast identification of traffic breakdowns (e.g., in incident detection), and experimental verification of traffic models.

In <CIT>, a method is disclosed for determining the traffic state in a traffic network with effective bottlenecks with a classification at least into the "freely flowing traffic", "synchronized traffic" and "moving widespread congestion" state phases and into patterns of dense traffic upstream of effective bottlenecks. FCD traffic data which includes information relating to the location and the speed of the vehicle is recorded at time intervals for a respective route section, and by reference to the information it is determined whether an effective bottleneck is present. If this is the case, from the current FCD traffic data, a pattern of dense traffic, which fits it, is continuously determined as a currently present pattern of dense traffic.

<CIT> discloses assigning an average vehicle speed, a traffic flow and a traffic density to a traffic phase.

In <CIT>, integrated results of traffic categories are evaluated in terms of probability based on rules or criteria (use of thresholding) to identify the type of traffic situation represented by the vehicle speed data.

Therefore, it is an object of the present invention to overcome the above-mentioned drawbacks by accurately estimating traffic velocity along a road network based on sparse probe data as input.

This problem is solved by the independent claims. Preferred embodiments are described in the dependent claims.

According to a first aspect, a computer system is defined in claim <NUM>.

The at least one device may be e.g. an external device, e.g. a mobile device, which is assigned to a particular vehicle. the mobile device may be a smart phone that may run an appropriate application, app, providing the functionality to send the speed measurement data to the computational unit. The mobile device may send the speed measurement data to the computational unit e.g. whenever a connection allowing data transfer (e.g. Bluetooth, etc.) is established with the vehicle and the vehicle sends a notification to the device that it is in a driving mode.

The computational unit may be a backend server. Alternatively or additionally, the computational unit may (at least partly) be located in a vehicle. Alternatively or additionally, the computational unit may be part of the road infrastructure corresponding to the road network.

The at least one device may alternatively or additionally be a device integrated into the vehicle and providing the respective functionality for sending the speed measurement data, e.g. a navigation unit of the vehicle.

Alternatively or additionally, the at least one device may be a traffic sensor located along a road in the road network operable to assess speed measurement data of vehicles passing the traffic sensor.

Alternatively or additionally, the at least one device may be integrated into a vehicle on the road providing speed measurement data of at least one other vehicle that is in the proximity of the vehicle the device is assigned to.

Alternatively or additionally, the at least one device is a mobile device assessing speed measurement data of vehicles from above the road, e.g. a satellite, airplane, helicopter, quadrocopter.

The speed measurement data may be sent when the vehicle is in a driving mode periodically, e.g. every <NUM> second (s), every <NUM>, every <NUM>, every <NUM>, every <NUM>, or any other appropriate period of time for sending the speed measurement data. In the example where the at least one device is or comprises an external device (cf. above) or is integrated into the vehicle, the speed measurement data may be floating car data, FCD. In the example where the at least one device is or comprises a traffic sensor, the speed measurement data may be sent each time a vehicle passes the traffic sensor. Alternatively, the external sensor measures the speed of a predetermined amount of vehicles passing the traffic sensor, calculate an average speed of the vehicles and send the calculated average speed as speed measurement data to the computational unit. The terms FCD and speed measurement data will be used interchangeably hereinafter.

Each region is defined as a part of a road segment of length L, wherein the size and the boundaries of said region may change over time. Over time, said region may further divide into two or more regions, or two or more regions may merge into one region.

A road network may be a system of interconnecting lines and points (edges and nodes) that represent a system of streets or roads. The road network may be divided into one or more road segments. Further definitions for road network, road segment and region are provided below.

Especially in view of the vehicles supporting an autonomous driving mode, the accurate estimation of traffic velocity is no longer just a tool for estimating a travel time for a particular route to a driver, but rather represents important data for road safety in view of improving the autonomous driving mode. In particular, on the one hand, each vehicle operating in an autonomous driving mode may use the data/information for determining a best route to a destination (e.g. if the velocity is rather low on one route, an alternative route with a better velocity may be autonomously chosen by the vehicle). On the other hand, the data/information on the velocity may be used in order to improve the security of all traffic participants in the road network, since the velocity data may be used by autonomous vehicles and/or by navigation systems of any vehicles to foresee road segments with low velocity and adapt the driving behavior accordingly.

Each location of the vehicle may comprise a position of the vehicle at the road network. Each position may be obtained using navigation satellite systems comprising Global Positioning System (GPS), GLObal Navigation Satellite System (GLONASS), Galileo positioning system, and BeiDou Navigation Satellite System. In particular, each position may be obtained from a respective module located in the vehicle. In the example of the Global Positioning System, each GPS - position that may be determined by a GPS-Module located in the vehicle. In this example, each speed measurement data may comprise a current GPS-Position of the vehicle. Since the vehicle (or the device corresponding to the vehicle) transmits speed measurement data comprising corresponding GPS-data to the computational unit, the computational unit may track the position of the vehicle and determine position x along a corresponding road segment as part of the road network with x ∈ [<NUM>, L]. Each timestamp may correspond to a particular point in time t the vehicle was at the respective position x along the road segment. The GPS-Module may be located in the external device and in the traffic sensor, respectively (cf.

The velocity of the vehicle may be calculated from the speed measurement data, as is explained in more detail below, or may be obtained from a speed sensor as e.g. located in the vehicle and/or in the traffic sensor.

The direction of the vehicle c may be calculated from the speed measurement data or determined from a direction sensor that may be located in the vehicle.

The lane the vehicle is currently driving on may be determined from further sensors, e.g. one or more cameras located in and/or on the vehicle and/or at the traffic sensor.

The data on vehicles and their velocities surrounding the vehicle (sending the speed measurement data) may be determined from further sensors, e.g. cameras, RAdio Detection And Ranging (RADAR) sensors, Light Detection And Ranging (LIDAR) sensors, photo sensors, thermal imaging cameras located in and/or on the vehicle, and/or any further appropriate sensors for providing the appropriate data.

According to the invention, identifying the regions comprises:.

wherein P denotes probability; and p denotes phase.

According to a further embodiment, calculating criteria probabilities <MAT> comprises the following:
let <MAT> be <MAT> criteria that (t, x) needs to fulfill in order to belong to phase p, wherein each criterion is modelled as a fuzzy decider <MAT>.

According to a further embodiment, the independent probability <MAT> for each traffic phase p is calculated as follows: <MAT>.

According to a further embodiment, the uncertainty probability PU ∈ [<NUM>,<NUM>] that describes the probability that (t, x) does not belong to any of the phases Ω is calculated by: <MAT>.

According to a further embodiment, if there is an occurrence of a high probability of a region belonging to ( <MAT> and ( <MAT> or <MAT>)), the dominance of <MAT> is taken into account.

According to yet a further embodiment, determining the final phase probabilities Pp while taking into account the dominance of <MAT> for each region is performed as follows: <MAT> <MAT> <MAT>.

According to a further embodiment, calculating accurate estimations of traffic velocity based on a prevailing traffic phase in the road network comprises:.

According to a further embodiment, estimating phase-dependent velocity estimates <MAT> comprises: <MAT> with <MAT> denoting a convolution process smoothing the inverted trajectory velocities <MAT> with the convolution kernel <MAT>.

According to another embodiment, aggregating final-phase probabilities Pp and the corresponding velocity estimates <MAT> into velocity estimates VE comprises: <MAT> with VU = a speed limit of the respective region.

According to yet another embodiment, at least one of the vehicles driving on the road network supports an autonomous driving mode;.

Vehicles comprising/supporting an autonomous driving mode for (at least in part) autonomously transporting passengers form one location to another are known. However, the autonomous driving mode is not yet available in a fully automated manner. Some vehicles require periodic input from an operator, e.g. a driver or passenger, whereas other vehicles and/or the driver of the vehicle may switch from a manual to an autonomous mode and vice versa, whenever applicable and/or allowable. In order to improve the security and efficiency of autonomous driving modes, the computational unit may send the accurate estimations of traffic velocity to all vehicles supporting an autonomous driving mode and previously registered via an appropriate application to the computational unit. Hence, the vehicles may use the accurate estimations of traffic velocity to the vehicles which may be taken into account of the respective vehicles for the autonomous driving mode. The security and efficiency of the autonomous driving mode is hence greatly improved. Alternatively and/or additionally, the computational unit may send the accurate estimations of traffic velocity to each vehicle previously registered at the computational unit, irrespective of whether the vehicle supports an autonomous driving mode. In this example, a navigation module of the vehicle may take the accurate estimations of traffic velocity into account for planning trips, warning drivers from jams and accurately predicting a time of arrival.

According to another aspect, a computer-implemented method is defined in claim <NUM>.

According to another aspect, a computer program product is defined in claim <NUM>.

The invention will be described in more detail hereinafter with reference to examples of embodiment. However, it is apparent to the person skilled in the art that the invention is not limited to the examples of embodiment.

A road network may be a system of interconnecting lines and points (edges and nodes) that represent a system of streets or roads. The road network may be divided into one or more road segments. For example, each line (edge) between two interconnecting points (nodes) may be a road segment. However, the road network may be divided into road segments in any other appropriate manner. Moreover, traffic on each road segment may be divided into three traffic phases. The first traffic phase is the free flow phase (in the following also referred to as: free flow). The free flow describes a state of traffic where traffic flow and traffic density are nearly in a linear relation. In the free flow, traffic demand is lower than a capacity of the respective road segment. Therefore, there may exist a high spread of velocities between vehicles driving on different lanes of the road segment. The average velocity in free flow can be estimated to greater than or equal (≥) <NUM>/h (kilometers per hour) for roads with a speed limit greater of equal <NUM>/h or roads with unlimited speed limit.

The second traffic phase is the synchronized flow phase (also referred to hereinafter as: synchronized) is characterized by high vehicle densities. In particular, the traffic demand corresponds to the capacity of the respective road segment. The average velocity of vehicles in synchronized flow is significantly lower than the average velocity of vehicles in free flow and can be estimated between <NUM>/h and <NUM>/h. Further, the variance of velocities among vehicles on different lanes of the road segment is lower than the variance of velocities in free flow traffic. A transition from free flow to synchronized flow can appear spontaneously on each road segment, e.g. due to local perturbations such as lane changing maneuvers and/or can be induced by moving jams propagating upstream. A transition from free flow to synchronized flow may infer a drop in the road capacity, e.g. at a bottleneck (e.g. an on/off-ramp), a closure of a lane and/or a beginning of a constructions site. When a maximum road capacity reduces and the traffic demand significantly changes the synchronized traffic phase may persist.

The third traffic phase is the Wide Moving Jam (WMJ) - phase (in the following also referred to as WMJ). The average velocity (hereinafter also referred to as mean velocity) in the WMJ can be estimated to lower than or equal (≤) <NUM>/h. The WMJ may occur spontaneously, e.g. when a vehicle in a synchronized decelerates stronger than necessary, resulting in a shockwave that propagates upstream (i.e. backwards from the decelerating vehicle) forming an upstream front of a WMJ. In synchronized flow, i.e. when vehicle density is high, it is likely that an over-deceleration happens. In this case, the average velocity can decrease down to <NUM>/h.

A trajectory of a vehicle c ∈ {<NUM>,. , Nc} with Nc = a total number of vehicles (each vehicle corresponding to floating car data received at the computational unit), is a function xc(t) ∈ [<NUM>, L] denoting a position of vehicle c along a road segment with length <MAT> at time t.

Each road segment is a predefined part of the road network starting with a length unit (e.g. in m, km or any other appropriate unit of length) count of <NUM> and ending with length <MAT>. An exemplary road segment is shown in <FIG>, cf.

Accordingly, the derivative of the function xc(t) with respect to the time, vc(t), is the velocity of vehicle c at time (point in time) t.

Each vehicle c passes a space-time domain [<NUM>, L] × [<NUM>, T] of a road segment with length L, observed for time period T, provides information about a part of the space-time domain.

x<NUM> is the sum of a length of vehicle c (e.g. in centimeter cm, meter m, or any other appropriate unit of length representing the length of c) and a minimal distance to the preceding vehicle in queueing traffic. The minimal distance to the preceding vehicle in queueing traffic may be a constant, e.g. <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> or any other constant representing an appropriate or mandatory minimal distance to the preceding vehicle in queuing traffic.

A "minimal space gap" is a non-constant space gap between a first vehicle to a preceding second vehicle that increases linearly with velocity vc(t) depending on time headway T<NUM>, wherein time headway T<NUM> is an elapsed time between a first point in time the preceding second vehicle finishes passing a fixed point at the road segment and the first vehicle starts to pass that fixed point at the road segment.

The present approach presented within this application is also referred to as novel Phase-based Smoothing Method (PSM) approach.

In view of the above definitions, <FIG> shows an area Ψ(t, x) (also referred to as area or area Ψ) represented by space interval [xc(t),xc(t) + x<NUM> + T<NUM> · vc(t)] at time t that vehicle c occupies. The occupied area Ψ represented by space interval [xc(t),xc(t) + x<NUM> + T<NUM> · vc(t)] in space-time (t, x) signifies that in this area Ψ, only one vehicle c can exist on a single-laned road. Further, it is assumed that the vehicle's velocity is a representation of the traffic velocity in the occupied area.

In other words, area Ψ(t, x) is a function that indicates whether at time t <NUM>, position x <NUM> (wherein x <NUM> is an arbitrary position along the road segment with x ∈ [<NUM>, L] ) is occupied by any observed vehicle c: <MAT> with <NUM> = true (i.e. at time t <NUM>, position x <NUM> is occupied) and <NUM> = false (i.e. at time t <NUM>, position x <NUM> is not occupied), wherein
Ψ(t, x) has the following properties:.

Accordingly, <MAT> denotes the velocity data vc(t) reported by all (devices located in the corresponding) vehicles c combined into a single, two-dimensional function. This velocity is only valid in space-time (t, x) which is occupied by any vehicle c* (i.e. area Ψ(t, x) = <NUM>), and is set to the velocity of the closest vehicle upstream of (t, x): <MAT>.

In order to process data locally, the two-dimensional convolution is a common and often used operation. The function <MAT> represents a weighted continuous convolution. <MAT> denotes a kernel function and <MAT> a space-time-dependent weight of the input data, in this case the velocity measurements VFCD. Definitions of kernel functions and weightings are given further below. In order to use the convolution equation for smoothing operations, results of ΓVFCD need to be normalized. The normalization term is similar to the aforementioned convolution but omits velocity input VFCD: <MAT>.

Later, applied kernel Φ(t, x) and weighting w(t, x) are chosen in such a way that D(w, Φ, t, x) represents an estimate of the data density in the regions. The normalized convolution of weighted and velocity function Vc(t, x) with kernel Φ(t, x) is then stated as: <MAT>.

For example, given a kernel function that returns only positive/zero values and has its maximum at (<NUM>,<NUM>), eq. (<NUM>) describes a common smoothing process, as depicted in <FIG>. Then, for space-time (t, x) a weighted average velocity of all nearby velocities is computed (that are inside the occupied area Ψ(t, x)), where the weights depend on their distance to (t, x).

The convolution kernel Φ allows a great variety of operations in general. Within the scope of the present subject-matter, the convolution kernel Φ is used for smoothing operations. For traffic related smoothing with characteristic wave speeds, the following simple and effective kernel formulation is also adopted here: <MAT>.

It defines a main smoothing direction vdir that is used in order to interpolate velocities in a characteristic direction of shockwaves vdir (see (<NUM>) for more details). Its maximal value is located at (<NUM>s, <NUM>m) and function values decay exponentially toward zero. In <FIG>, a kernel with negative velocity vdir is depicted exemplarily as a discrete contourplot. Note that Φ is actually a continuous function.

<FIG> shows the steps <NUM> performed for estimating accurate velocities VE <NUM> in the road network. These steps are performed using floating car data, FCD, but, however, may also be performed using any kind of speed measurement data. In particular, it is shown how the FCD (hereinafter also referred to as 'raw trajectory data') VFCD <NUM> is estimated into a continuous velocity estimate VE(t, x).

First, a calculation of final phase probabilities Pp is performed <NUM>.

Let Ω = {F,S,J} be the set of the phases 'Free Flow' (F), 'Synchronized Flow' (S) and 'Wide Moving Jam'; also referred to as `WMJ' (J) (as outlined above). Then, Pp(t, x) ∈ [<NUM>,<NUM>] with p ∈ Ω denotes the probability for the traffic at time t and at position x to be in phase p.

In a first step, the FCD (also referred to herein as raw trajectory data) <NUM> is convolved with different smoothing kernels (cf. above, and equation (<NUM>)), resulting in smoothing data. Resulting values are evaluated to what extent they fulfill several fuzzy phase criteria. Respective criteria probabilities <MAT> denote the degree of fulfillment <NUM> at space-time (t, x). As described above, each traffic phase has different empirical characteristics, such as the aforementioned velocity ranges and respective traffic densities and traffic flows. The free flow phase has low traffic densities and high velocities, the synchronized flow phase lower velocities and higher densities and the Wide Moving Jam phase highest traffic densities and lowest velocity ranges. These empirical characteristics can be used in order to identify the phase p each space-time (t,x) probably belongs to. Let <MAT> be <MAT> criteria that (t, x) needs to fulfill in order to belong to phase p. Each criterion is modelled as a fuzzy decider <MAT>.

In a next step, the independent probability <MAT> is determined <NUM> as the product of all criteria probabilities for each phase individually: <MAT>.

For each phase, different criteria are aggregated into preliminary phase probabilities Pp'. Consequently, the preliminary phase probability Pp is always lower or equal to the lowest criteria probability <MAT>. In other words that means that all criteria need to be fulfilled to a certain degree in order to assign a point in space-time to phase p. A specific example for two different criteria is provided in more detail with respect to Table <NUM> below.

In a next step, probability PU ∈ [<NUM>,<NUM>] is estimated <NUM>, which describes the level of uncertainty in assigning (t, x) to any of the phases. In other words PU describes the probability that (t, x) does not belong to any of the phases: <MAT>.

For space-time (t, x) where the uncertainty is high a best-guess velocity VU needs to be assumed. The speed limit may be the best-guess velocity VU. In another example, other kinds of velocities, e.g. historical averages, may be the best guess velocity VU.

Then, the dominance of the J-phase (WMJ-phase) is taken into account <NUM>. Since Pp are independent, regions may occur especially in the presence of shockwaves, where both <MAT> and <MAT> or <MAT>) estimate high probabilities. That is due to the different shapes of the convolution kernels and according velocities that are considered for the determination of the phase. Since WMJs can propagate through other phases without interruption (cf. equation (<NUM>)), plus, probability <MAT> is supported by more distinctive criteria, it is reasonable to assume that these regions rather belong to the J phase than to one of the others. Consequently, in those cases dominance of the J phase over the other phases is determined.

Finally, the final phase probabilities Pp are determined <NUM>, taking into account the dominance of the J phase by: <MAT> <MAT> <MAT>.

Based on these and raw trajectory data, for each phase and each point in space-time a velocity estimate <MAT> is computed <NUM>. Additionally, a fallback velocity VU(t, x) is assumed that serves as a best-guess velocity in case the uncertainty PU is high. The fallback velocity (also referred to herein as best-guess velocity) may be a speed limit. In another example, the fallback velocity may be a historical average velocity or any other appropriate velocity.

Finally, the resulting estimate VE(t, x) is determined <NUM> by aggregating the probabilities Pp(t, x) and PU(t, x) and their respective velocity estimates <MAT> and VU(t, x).

The above steps are explained in the following example that is provided with respect to Table <NUM>.

Calculation of criteria probabilities <MAT> <NUM>.

For the sake of simplicity, an example is provided where two classes of criteria <MAT> are presented and later applied. However, it is clear to the person skilled in the art that the design of the approach allows the usage of a more than two criteria. In particular, further criteria might be used in order to further distinguish between phases p ∈ Ω with Ω = {F,S,J}. For example, if flow or density information is available that can be used in order to further differentiate between phases p by designing dedicated criteria. In addition to or alternatively, prior bottleneck data could be integrated into the procedure. If there are known bottlenecks, for the regions upstream of that bottleneck along the road segment, a prior probability as congested flow could be assigned. In this example, the approach would constitute a fusion of real data and expected congested regimes.

Back to the example: the first criterion is a velocity criterion <MAT> that uses velocity data of smoothed data for determining the phase probability. The second is a density criterion <MAT>. The density criterion <MAT> is applied to ensure that a phase hypothesis is supported by nearby data. In this context density refers to the data or, in other word, the number of velocity measurements nearby.

The velocity of vehicle c at time t vc(t) (herein also referred to as: 'velocity data') represents very important data for accurately determining to which traffic phase space-time (t, x) probably belongs to. The underlying idea of this criterion is to use velocity data measured in phase-characteristic directions around (t, x) and determine probability <MAT>. It is known that each transition from free flow to congested flow (in the following also referred to as: traffic breakdown) is a probabilistic event triggered by perturbations. A traffic breakdown is usually connected to a capacity drop of the road infrastructure and a significant drop in average velocities. Consequently, velocity suits well to distinguish between free flow and congested flow. In order to differentiate between free flow and congested flow, fuzzy thresholds <MAT> and <MAT> are applied.

The distinction between WMJ and synchronized as congested regimes is less obvious. In fact, the upper velocity of the WMJ is significantly smaller than the threshold to free flow. As outlined above, velocities in WMJ can decrease down to <NUM>/h, such that no lower bound is required.

A fuzzy decider function σ(v,vthres,λ) (sigmoid function, i.e. a bounded differentiable real function that is defined for all real input values and has a positive derivative at each point) is applied that translates a velocity v into a probability <MAT>. Parameters are threshold vthres and λ determining the strictness of the threshold. In other words, the higher λ, the higher the gradient of the transitionsection: <MAT>.

<FIG> shows the results of the sigmoid functions parameterized for free flow <NUM>, synchronized flow <NUM> and WMJ <NUM> with respect to different velocities.

Probabilities <MAT> and <MAT> are computed as follows: <MAT> <MAT>.

Where <MAT> and λp denote the parameters of the decider function with respect to the characteristic velocity ranges of the phase p. The velocities VF and VS are computed according to the normalized convolution process equation (<NUM>) as: <MAT> <MAT> with ΦF and ΦS denoting phase specific smoothing kernels, with characteristic speeds of <MAT> and parameters τp and σρ. w<NUM> denotes a standard weighting where w<NUM>(t, x) = <NUM>. The standard weighting implies that all smoothed raw data have an equal significance for the determination of the phase.

The velocity criterion for the J phase is more distinct. In particular, (t, x) can only be assigned to the J phase if, both, up- and downstream of (t, x) low velocities are observed. Doing so ensures that WMJs are not extrapolated far beyond measurements in order to reduce wrongly estimated congested regions.

In order to efficiently compute this condition, measurements up- and downstream of (t, x) smoothing data with differing kernels are identified and the probabilities are computed independently. Then, the product of both probabilities represents the need to fulfill both requirements. Therefore, <MAT> is computed as: <MAT>.

Where <MAT> and <MAT> denote the velocity fields computed as: <MAT> <MAT>.

The different applied kernel functions <MAT> and <MAT> (see above) defined as: <MAT> <MAT>.

Note that <MAT> only considers data upstream of (t, x), <MAT> only considers data downstream of (t, x). In that way data are smoothed in different directions. The combination of the sigmoid functions of the velocities <MAT> and <MAT> ensures that WMJs are only reconstructed in between low velocity measurements. Note that eq. (<NUM>) uses different velocity thresholds <MAT> and <MAT> for the sigmoid functions. The difference stems from the expectation that once, due to downstream velocities below <MAT> a WMJ is detected, this WMJ will propagate upstream as long as traffic upstream is in a state of critical flow-density (<NUM>). Since no density or flow data are available that state is assumed to be the congested region with the velocity threshold <MAT>.

By requiring both criteria to be fulfilled it is ensured that the J phase is only reconstructed between low velocity measurements but never extrapolated. Possibly, the moving jam emerged earlier than the time the first equipped vehicle perceived it and propagated further upstream than the last equipped vehicle passing through the moving jam. However, sparse data does not allow to get to know exactly when the WMJ emerged and when it dissolved. Extrapolating a shockwave upstream or downstream means to risk overestimating it. Thus, this approach can be described as cautious aiming at minimizing wrongly estimated low velocities.

The second criterion is a density criterion <MAT> that uses data density D (cf. equation (<NUM>) above) in order to quantify how well a phase hypothesis is supported by nearby data. This criterion enables coping with varying data density that comes along with FCD. Data density D(w<NUM>,Φp,t, x) is computed for each phase p ∈ Ω with Ω = {F,S,J}, using the respective kernel Φp. Since weighting w<NUM> and the applied kernels are greater than zero, also D(w<NUM>, Φp, t, x) is always positive (or zero). In order to translate density into the probability <MAT> its values are limited to an upper bound of <NUM>: <MAT>.

In that way, <MAT> equals to one if data is nearby, and converges to zero the greater the distance between (t, x) and the measurements. The validity of a measurement in space and time can be parametrized by adapting the kernel function or by modifying the weighting w<NUM>.

The phase probabilities <MAT> is the product of all phase criteria <MAT> and <MAT>.

After calculating the phase probabilities <MAT>, the uncertainty PU(t, x) is calculated. PU represents a probability that (t, x) does not belong to any of the phases: <MAT>.

Since in space-time (t, x) the uncertainty is high, a best-guess velocity VU(t, x) needs to be assumed. The speed limit is chosen in this example as best guess. However, it is clear to the skilled person that other kinds of velocities can be chosen as best guess, e.g. historical velocity averages. As outlined above, for the case where the uncertainty PU(t, x) is high, the best-guess velocity VU(t, x) is used as fallback-velocity that serves as best-guess velocity in case the uncertainty is high.

As outlined above, the independent phase probabilities Pp have been calculated. Since Pp are independent, there exists an occurrence of regions, especially in the presence of shockwaves, where both, <MAT> and <MAT> or <MAT> estimate high probabilities. This occurrence exists due to the different shapes of the convolution kernels and according velocities that are considered for the determination of each phase ∈ Ω, where Ω = {F,S,J}.

Since WMJs can propagate through other phases without interruption (<NUM>) and since the independent phase probabilities <MAT> are supported by more distinctive criteria it is reasonable to assume that these regions rather belong to the J phase (phase J) than to any other one of the others phases p. Consequently, in those cases dominance of the J phase over the other phases is applied.

In view of the above, final phase probabilities PP are set as: <MAT> <MAT> <MAT>.

After the calculation of the final phase probabilities, now the velocities in space-time are calculated <NUM>.

Phase-dependent velocity estimates <MAT> <NUM>.

As outlined above, the raw trajectory data <NUM> was taken in order to calculate the appropriate traffic phases p in space and time using characteristic smoothing kernels and several criteria that allow distinguishing between them.

Now, the calculated traffic phases p are taken to accurately calculating the traffic velocities. The traffic phases enable determining a region in space and time a velocity measurement has validity. For example, a low velocity measurement that is part of a Wide Moving Jam allows estimating the mean velocity of all vehicles that are part of the Wide Moving Jam. However, it does not enable a determination about a traffic velocity in an adjacent free flow or synchronized flow phase.

The calculation of phase-dependent velocities <MAT> is performed as follows: <MAT>.

Where <MAT> denotes the convolution process (cf. equation (<NUM>)) smoothing the inverted trajectory velocities <MAT> with the convolution kernel <MAT>. In this example, for numerical reasons, a minimal velocity of <NUM>/h is assumed. This enables that the smoothing process resembles a harmonic mean instead of an arithmetic one, which accounts for precision in travel time reconstruction (cf. equation (<NUM>)).

In addition, instead of a normal weighting w<NUM> as used in the smoothing for calculating the phase probabilities <NUM>, the final phase probabilities Pp are used as weights for the input data.

In other words, for the computation of each <MAT> mostly those measurements are taken into account that belong to phase p. Note that convolution kernels <MAT> can be parametrized differently from the convolution kernels Φp. The reason is that the shapes of Φp account for the characteristic propagation of phases, such as the propagation of J phases upstream and the stationary character of S phases. <MAT>, on the other hand influence how data inside an already identified phase is smoothed, where data is weighted with respect to the final phase probabilities Pp. A distinction between the parameters for example enables the reconstruction of a stationary synchronized flow phase with a large isotropic kernel ΦS and subsequently estimating velocities inside the phase with a smaller anisotropic kernel <MAT> that reconstructs minor shockwaves (narrow moving jams (<NUM>)) occurring inside the phase.

Finally, the phase probabilities Pp and respective velocities <MAT> are estimated. Additionally, probability PU is computed and best-guess velocity VU is assumed. For aggregating all velocities and probabilities into a final velocity estimate VE, a weighted average is applied: <MAT>.

To prove the accuracy of the above-mentioned approach for estimating traffic speed, a study was conducted with sparse FCD. To do so, real FCD collected during a traffic jam on German freeway A99 on the <NUM>th July, <NUM>, were used. First, available data and discretization of the approach are briefly described. Then, resulting probabilities and velocities applying the above are illustrated. Finally, the accuracy of the traffic speed estimation is compared to two other algorithms that are less accurate.

Available sparse FCD consist of timestamps and GPS positions sampled anonymously by individual vehicles with sampling times between <NUM> and <NUM>. An installed filter in the processing unit of the equipped vehicles retains packages of data, wherein each package of data contains a plurality of FCD for covering the case that, the vehicle's velocity does not match an expected velocity. The expected velocity is a state machine that is influenced by individually recorded velocities and provided velocity estimates. The results are fractions of complete trajectories being reported, with the positive result that individuals cannot be tracked along their journey. That filter mechanism was introduced to ensure each driver's privacy. Still, in case of congestion, detailed velocity data was collected. <FIG> shows raw trajectory data <NUM> for a road segment <NUM>, <NUM> (i.e. the congestion on German highway A99 direction north) are displayed. The triangles <NUM> mark positions of on- and off-ramps along the road segment <NUM>, <NUM>.

The pattern shows different characteristics often occurring in congested freeway traffic. As can be seen, around <NUM>:45am, a moving jam phase emerged that evolved into a WMJ and induced a traffic breakdown at the on-ramp at position <NUM>. The WMJ propagated further upstream and induced another traffic breakdown at a neighboring bottleneck. The pattern evolves into a General Pattern (GP) expanding over two bottlenecks where the downstream fronts of synchronized flow phases are fixed slightly downstream the on-ramp positions. In the pinch zone of the downstream synchronized flow phase a few WMJs originate and propagate upstream.

In order to apply estimation methods, time and space dimension are discretized into intervals of length ΔL = <NUM>m and ΔT = <NUM>s called grid cells. Average velocities between GPS positions and respective timestamps are computed and the grid cells the vehicle occupies are determined. Then, each trajectory c = <NUM>,. , Nc is written as a set of tuples r = {(t,x,v,w)<NUM>,. ,(t,x,v,w)ntr} where each tuple represents the mean velocity of the vehicle at space-time (t, x) referring to the center of the grid cell in space and time, and weight w ∈ [<NUM>,<NUM>] is used to mark the part of the cell that is occupied by the vehicle. If two velocities of different trajectories are assigned to the same cell, their mean value is determined and the weights w are added. The discretization of the approach requires to discretize the continuous 2D convolution. An efficient implementation of the discrete 2D convolution can be performed e.g. using the Fast Fourier Transform.

<FIG> depicts the computation of the final phase probabilities PP (PJ, PS and PF) <NUM> computed with all available trajectories. Based on the final phase probabilities PP <NUM>, for each phase p, a phase velocity <MAT> is computed <NUM>. Finally, the velocity estimate VE <NUM> is shown. Next to VE <NUM>, the probability (<NUM> - PU) <NUM> is depicted that can be interpreted as quality value, where a value of one means high and a value of zero means low certainty of the result.

For an objective evaluation of the accuracy of the calculated velocities, a comparison with other algorithms was performed. For comparison, two common approaches that do not require density or flow data are taken into consideration. The first approach is the Generalized Adaptive Smoothing Method (GASM) that is based on the observation that shockwaves in congested traffic propagate upstream and shockwaves in free traffic propagate downstream. Here, the GASM is applied as described in "<NPL>" (<NPL>" with an adaption to sparse FCD. The adaption describes how sparse FCD and a best-guess velocity can be fused in order to provide a continuous velocity estimate if no data is nearby. The weighting ratio of FC data to the velocity fallback is <NUM>:<NUM>. Parametrization is chosen according to Treiber. Further, an isotropic smoothing approach (naïve approach) is applied that smooths data mostly in time and slightly in space.

Applied PSM parameters are listed in Table <NUM>. The velocity thresholds <MAT> were explained above, the propagation directions <MAT> have been set similar to Treiber. The other parameters which are mainly the sizes of the kernels Φp and <MAT> have been set with respect to typically observed properties of congestion: WMJs often have a higher spatial than temporal extent, thus σJ is greater than τJ. Synchronized flow phases are rather stationary or, if not, their downstream fronts usually stick to adjacent upstream bottlenecks and remain there. Thus, the kernel has a relatively high value τS compared to σS, which results in a larger temporal smoothing. Kernel <MAT>, which is applied after identifying the S phase, is smaller in time but larger in space. Effectively, minor shockwaves are propagated correctly upstream. The kernels for the free flow phase are medium sized. In experiments, estimation accuracies were less sensitive to changes of these parameters.

In the following, estimation accuracy of the PSM, the GASM and the naïve approach are compared qualitatively and quantitatively. Since data density has the most significant impact on the accuracy of the result, for both comparisons this parameter is varied.

<FIG> shows the obtained estimation results applying the three approaches (PSM, GASM, naïve) with limited data coverage, i.e. sparse FCD <NUM>. As can be seen in plot <NUM>, the naïve approach manages to estimate the stationary traffic upstream the two bottlenecks well but fails in reconstructing moving jams. It smooths the low velocities that actually propagate upstream in temporal direction only, such that the estimation of the congestion pattern s is inaccurate.

As can be seen in Plot <NUM>, the GASM-approach manages to reconstruct the moving jams more accurately than the naïve approach, however, also here the estimation of velocities is wrong for many grid cells. For example, the latest moving jam is extrapolated further upstream than it actually propagated. Furthermore low velocities are smoothed slightly beyond the downstream bottleneck at kilometer <NUM>. Further, the queueing traffic at the bottlenecks are not accurately estimated. Zones that are actually in congested state are estimated as free flow.

The PSM-approach manages to accurately distinguish between the queueing traffic at the bottlenecks and the WMJs. The gaps in data that belong to moving jams are correctly classified as J phase and respective low velocities are estimated. Gaps in the stationary traffic upstream the bottlenecks are accurately reconstructed as synchronized flow phases such that appropriate velocities are estimated from data in the same phase. An expected estimation failure occurs at <NUM>:00am where the moving synchronized flow is treated as stationary congestion and velocities are smoothed in temporal direction. That improves as the velocities drop further and a J phase is identified. Comparing the reconstruction quality of moving jams calculated by the PSM approach and the GASM approach, estimated phase fronts by the PSM have sharper edges. This improved accuracy is very valuable feature for using the fronts for predictions in a navigation system and/or hazard warnings, especially for autonomous driving.

In order to evaluate an algorithm quantitatively, the set of Nc trajectories is divided into a training set and a test set. The training set is used in order to estimate velocities VE, and the test set is used to evaluate the accuracy of that estimate. The size <MAT>, <NUM> < NT < Nc of the test set TT is defined as: <MAT>.

With α ∈]<NUM>,<NUM>[. The size NE of the training (estimation) set is the (<NUM> - a) part of all trajectories. Additionally, that part is varied with another factor β ∈]<NUM>,<NUM>[ that is used in order to simulate different data densities: <MAT>.

For the sake of interpretation, NE is normalized with the analyzed time interval T, resulting in the data density δE: <MAT>.

Then, δE denominates the number of trajectories per hour that are used for the estimation process.

There exists a variety of quality measures. Since a deviation between estimate and ground truth is more critical in congested regimes than in free flow, here the Mean Absolute Percentage Error (MAPE) is applied as metric: <MAT>.

Where TT = {tr<NUM>,tr<NUM>,. , trNT} denotes the test set of trajectories tr, and <MAT> the total number of tuples in all test trajectories tr ∈ TT: <MAT>.

<FIG> shows the MAPE with respect to data densities δE between <NUM> traces/hour and <NUM> traces/hour for the naïve approach <NUM>, the GASM approach <NUM> and the PSM approach <NUM>. The presented error values are the mean MAPE of <NUM> iterations with randomly assigned training and test set in order to ensure robustness of the results.

Claim 1:
Computer system for calculating accurate estimations of traffic velocity in a road network such that the velocity data may be used by autonomous vehicles and/or by navigation systems of any vehicles to foresee road segments with low velocity and adapt a driving behavior accordingly, the road network comprising one or more road segments, the system comprising:
a plurality of devices, each device operable to deliver speed measurement data (<NUM>) corresponding to the speed of a traffic flow in the road network; and
at least one computational unit,
wherein each of the plurality of devices sends speed measurement data (<NUM>) to the computational unit,
characterized in that the computational unit is operable to calculate accurate estimations of traffic velocity in the road network by:
- identifying (<NUM>), based on the speed measurement data (<NUM>), regions with varying sizes and moving boundaries under the condition that within each region of the regions a corresponding traffic phase p is constant, wherein each traffic phase is one of a free-flow phase, a synchronized phase or a wide moving jam phase, and wherein each region of the regions is defined as a part of a road segment of a length (L), wherein the identifying (<NUM>) of the regions comprises:
- calculating (<NUM>), from the speed measurement data (<NUM>), criteria probabilities <MAT> for each traffic phase p;
- calculating (<NUM>), as the product of all criteria probabilities, the independent probability <MAT> for each traffic phase p;
- estimating (<NUM>) the uncertain probability PU ∈ [<NUM>,<NUM>], wherein PU describes a level of uncertainty in assigning (t, x) to any of the phases p;
- taking (<NUM>) into account the dominance of the wide moving jam phase; and
- determining (<NUM>) final phase probabilities Pp;
wherein P denotes probability; p denotes phase; x denotes a respective position along a respective road segment; and t denotes a point in time the vehicle was at the respective position along the respective road segment; and
- calculating (<NUM>) accurate estimations of traffic velocity (VE) in said regions based on the corresponding traffic phases.