Assessing road traffic conditions using data from multiple sources

ES 2 373 336 T3

DESCRIPTION

Assessing road traffic conditions using data from mobile data sources

The following description generally relates to techniques for evaluating road traffic conditions based on data obtained from various data sources, such as inferring traffic-related information for roads of interest based on data samples that reflect a true displacement in those roads.

As road traffic has continued to increase faster than the increase in road capacity, the effects of increased traffic congestion have had increasing detrimental effects on business and government operations and on the well-being of people. Consequently, efforts have been made to combat the increase in traffic congestion in various ways, such as obtaining information about current traffic conditions and providing information to individuals and organizations. Such information on the current traffic situation can be provided to interested parties in a number of ways (for example, through frequent radio broadcasts, an internet website displaying a map of a geographic area with color-coded information about congestion current traffic on some main roads in the geographic area, information sent to mobile phones and other portable consumer devices, etc.).

One source for information about current traffic conditions includes human-supplied observations (e.g. traffic helicopters providing general information about traffic flow and accidents, driver reports via mobile phones, etc.), while another source in some larger metropolitan areas is traffic sensor networks capable of measuring traffic flow on various roads in the area (for example, via sensors embedded in the road pavement). While human-supplied observations may provide some value in limited situations, such information is typically limited to only a few areas at a time and typically lacks sufficient detail to be of meaningful use.

Traffic sensor networks can provide more detailed information about traffic conditions on some roads in some situations. However, there are several issues regarding such information, as well as information provided by other similar sources. For example, many roads do not have road sensors (for example, geographic areas that do not have road sensor networks and / or major roads that are not large enough to have road sensors as part of a nearby network), and even Roads that have road sensors often cannot provide accurate data, greatly diminishing the value of the data provided by the traffic sensors. A cause of inaccurate and / or unreliable data includes traffic sensors that are broken, thus not providing data, data is intermittent, or data readings are incorrect. Another cause of inaccurate and / or unreliable data includes a temporary data transmission problem from one or more sensors, resulting in intermittent delivery, delayed delivery, or no data delivery. Also, many traffic sensors are not configured or designed to report information about their operational status (for example, whether they are operating normally or not), and even if the operational status information is reported, it may be incorrect (for example example reporting that they are operating normally when in fact they are not), thus making it difficult or impossible to determine whether the data provided by the traffic sensors is accurate. Furthermore, some traffic-related information may be available only in raw and / or itemized form, and therefore may be of limited utility.

Thus, it would be beneficial to provide improved techniques for obtaining and evaluating traffic-related information, as well as providing various additional related capabilities.

Document US2004034467 A1 describes a system and a method for maintaining a road network traffic status database that is composed of map segments with the network in which the positions and speeds of the vehicles with the network are received from wirelessly and are used to update an average speed of the map segments and in which an optimal route between a first and a second position is determined from the database.

Document WO98 / 5468 describes a system that generates map database information from vehicle movement by passive geographic location and tracking of at least one vehicle carrying a mobile transmitter. The information generated can be stored for other purposes in a position-sensitive database. Personalized travel-related information is provided to a vehicle by passively geographically locating the vehicle's mobile transmitter which selects the relevant travel-related information from a position-sensitive database and sending the selected information to the receiver. vehicle mobile.

The object of the present invention is to provide a method, a system and a computer-readable medium for an improved evaluation of data samples representing vehicles moving on the road.

The object is resolved with the subject-object of the independent claims.

ES 2 373 336 T3

Preferred embodiments of the present invention are defined in the dependent claims.

The invention will be described in more detail below, together with the related art.

Brief description of the drawings

Figure 1 is a block diagram illustrating data flows between components of one embodiment of a system for evaluating road traffic conditions based at least in part on data obtained from vehicles and other mobile data sources.

Figures 2A-2E illustrate examples of evaluating road traffic conditions based at least in part on data obtained from vehicles and other mobile data sources.

Figure 3 is a block diagram illustrating a calculation system suitable for executing an embodiment of the described Data Sample Manager system.

Figure 4 is a flow chart of an exemplary embodiment of a Data Sample Filtering routine related to the present invention.

Figure 5 is a flow chart of an exemplary embodiment of a Data Sample Outlier Remover routine related to the present invention.

Figure 6 is a flow chart of an exemplary embodiment of a Data Sample Rate Evaluator routine related to the present invention.

Figure 7 is a flow chart of an exemplary embodiment of a Data Sample Flow Evaluator routine related to the present invention.

Figure 8 is a flow chart of an exemplary embodiment of a Mobile Data Source Information Provision routine related to the present invention.

Figures 9A-9C illustrate examples of actions of mobile data sources in obtaining and providing information about road traffic conditions.

Figures 10A-10B illustrate examples of rectification of data samples obtained from road traffic sensors.

Figure 11 is a flow chart of an exemplary embodiment of a Sensor Data Read Error Detector routine related to the present invention.

Figure 12 is a flow chart of an exemplary embodiment of a Sensor Data Read Error Corrector routine related to the present invention.

Figure 13 is a flow chart of an exemplary embodiment of a Sensor Data Read Totalizer routine related to the present invention.

Figure 14 is a flow chart of an exemplary embodiment of a Traffic Flow Estimator routine related to the present invention.

Detailed description

Techniques are described for evaluating road traffic conditions in various ways based on data obtained related to traffic, such as data samples from vehicles and other mobile data sources traveling on roads and / or from road traffic sensors. road (for example, physical sensors that are embedded in or otherwise close to roads). Furthermore, in at least some embodiments, the data samples from the mobile data sources can be supplemented with data from one or more other sources, such as obtaining data readings from physical sensors that are near or embedded in the roads. The evaluation of road traffic conditions is based on samples obtained from data (for example, data readings from road traffic sensors, individual or grouped data points from mobile data sources, etc.) can include various filters and / o conditioning of samples and data readings, and of various inferences and determinations by probability of characteristics of interest related to traffic.

As noted, in some embodiments the data obtained from road traffic condition information may include multiple data samples provided by mobile data sources (e.g., vehicles), road-based traffic sensor data readings ( for example, loop sensors embedded in road pavement), and data from other data sources. The data can be analyzed in various ways to facilitate the determination of the characteristics of interest of the traffic conditions, such as the estimated average speed of the traffic and the total estimated volume of vehicles for particular sections of roads of interest, and to allow such determinations of traffic conditions are made in a

ES 2 373 336 T3 in a real-time or near-real-time manner (eg, within a few minutes of receiving samples and / or subordinate data reads). For example, the data obtained can be conditioned in various ways in order to detect and / or correct errors in the data. The data obtained from information on road traffic conditions can be further filtered in various ways in various embodiments in order to remove data from consideration if it is inaccurate or otherwise unrepresentative of the true characteristics of interest of road conditions. traffic, including the identification of data samples that are not of interest based at least in part on roads with which the data samples and / or data samples are associated to which are statistical outliers relative to other data samples - in In some embodiments, the filtering may further include associating the data samples with particular roads. The filtered data samples may further include data samples that would otherwise reflect positions or activities of vehicles that are not of interest (e.g., parked vehicles, vehicles circling a lot or parking structure, etc.) and / or data samples that are otherwise unrepresentative of true vehicle movements on roads of interest. The evaluation of the data obtained may, in at least some embodiments, include the determination of traffic conditions (for example, traffic flow and / or average traffic speed) for various sections of a road network in a particular geographical area. , based at least in part on data samples obtained. The evaluated data can then be used to perform other functions related to analyzing, predicting, forecasting and / or providing traffic-related information. In at least some embodiments, a data sample manager system uses at least some of the techniques described to prepare data for customer use of traffic data, such as a predictive traffic information provider system that generates multiple predictions of traffic conditions at various future times, as described in more detail below.

In some embodiments, conditioning of data samples may include rectifying erroneous data samples, such as by detecting and / or correcting errors present in the data in various ways (for example, for data readings received from sensors). road traffic). In particular, techniques are described to assess the health of particular data sources (for example, road-based traffic sensors) in order to determine whether the data sources are working properly and to reliably provide accurate data samples. , such as based on the analysis of the data samples provided by those data sources. For example, in some embodiments, the current data readings provided by a particular traffic sensor can be compared to passing data readings provided by that traffic sensor (e.g., historical average data) in order to determine whether the current readings of traffic data is significantly different from typical past data reads, such as they may be caused by malfunctioning traffic sensor and / or other problems in the data, and / or may instead reflect unusual current traffic conditions. Such detection and analysis of possible errors with particular data sources and / or current traffic data reads can be accomplished in various ways in various embodiments, as discussed in greater detail below, including those based at least in part on technical such as using neuralgic networks, Bayesian classifiers, decision trees, etc.

After detecting unreliable data samples, such as malfunctioning broken data sources, such unreliable data samples (as well as missing data samples) can be corrected or otherwise rectified in various ways. For example, missing and unreliable data samples for one or more data sources (e.g., traffic sensors) can be rectified in some embodiments using one or more related information sources, such as through contemporaneous samples of data from nearby or otherwise related traffic sensors that are working properly (for example, averaging data readings provided by adjacent traffic sensors), through predictive information related to missing or unreliable data samples (for example, determining expected data readings for the one or more data sources using predicted and / or forecasted traffic condition information for those data sources) , through historical information for the one or more data sources (for example, using historical mean data readings), through adjustments of incorrect data samples that use information about consistent trend or other types of errors that cause errors that can be compensated, etc. Additional details related to rectifying missing and unreliable data samples are included below.

In addition, techniques are described to further estimate traffic condition information in various other ways, such as in cases where currently available data may not allow rectification of data samples for a particular data source (e.g., a sensor traffic) is performed reliably. For example, the presence of multiple unhealthy nearby traffic sensors that are malfunctioning can result in insufficient data to assess traffic flow information with sufficient confidence for those individual traffic sensors. In such cases, the traffic condition information can be estimated in various other ways, including those based on groups of related traffic sensors and / or other information related to the structure of a road network. For example, as described in greater detail below, each road of interest can be modeled or represented using multiple road segments, each of which can have multiple associated traffic sensors and / or data available from one or more of the road segments. more different data sources (for example, mobile data sources). If so, the road traffic condition information can be estimated for a particular road segment (or another group of multiple related traffic sensors) in various ways, such as using

ES 2 373 336 T3 information on evaluated traffic conditions for neighboring road segments, predicted information for the particular road segment (for example, which is generated for a limited future time period, such as three hours, based at least on part in current and recent conditions at the time of the forecast), forecast information for the particular road segment (for example, which is generated for a longer future time period, such as two weeks or more, in a way that does not use some or all of the current and recent condition information used for the prediction), historical average conditions for the particular road segment, etc. Using such techniques, traffic condition information can be provided even in the presence of little or no current traffic condition data for one or more nearby traffic sensors or other data sources. Additional details related to such an estimate of traffic condition information are included below.

As indicated above, information about road traffic conditions can be obtained from mobile data sources in various ways in various embodiments. In at least some embodiments, the mobile data sources include the vehicles on the road, which each may include one or more calculation systems that provide the data about the movement of the vehicle. For example, each vehicle can include a GPS device (Global Positioning System: Global Location System) and / or other geographical location device capable of determining the geographical position, speed, direction and / or other data that characterizes or is otherwise related to the movement of the vehicle, and one or more devices in the vehicle (be it geolocation devices or a different communication device) may from time to time provide such data (for example, via a wireless connection) to one or more systems capable of using the data (eg, a data sample manager system, as described in more detail below). Such vehicles may include, for example, a distributed network of vehicles driven by individual unrelated users, fleets of vehicles (for example, for delivery companies, taxi and bus companies, transportation companies, government agencies or agencies, vehicles of a car rental service, etc.), vehicles that belong to commercial networks that provide related information (for example, the OnStar service), a group of vehicles driven in order to obtain such information on traffic conditions (for example, traveling on predefined routes, or dynamically driven along roads, such as to obtain information about roads of interest), vehicles with mobile phone devices on board (for example, equipment incorporated and / or in possession of a vehicle occupant) capable of providing location information (for example, based on GPS capabilities of the devices and / or based on geographic location capabilities provided by the mobile phone network), etc.

In at least some embodiments, the mobile data sources may include or be based on computing devices and other mobile devices of users who travel on the roads, such as users who are the drivers and / or passengers of vehicles on the roads. Such user devices may include devices with GPS capabilities (eg, mobile phones and other handheld devices), or the position and / or movement information may instead be produced in other ways in other embodiments. For example, devices in vehicles and / or user devices can communicate with external systems that can detect and track information about devices (for example, for devices that pass through each of multiple transmitters / receivers in a network managed by the system. ), thus allowing the position and / or movement information for the devices to be determined in various ways and with various levels of detail, or such external systems may be otherwise capable of detecting and tracking information about vehicles and / or users without interacting with the devices (for example, camera systems that can observe and identify license plates and / or the faces of users) . Such external systems may include, for example, mobile phone networks and towers, other wireless networks (for example, a network of places with WiFi), vehicle transponder detectors that use various communication techniques (for example, RFID or Radio Frequency Identification ;), other vehicle detectors and / or users (for example, using infrared scopes, sonar, radar or laser to determine the position and / or speed of vehicles), etc.

Information on road traffic conditions obtained from mobile data sources can be used in a number of ways, either alone or in combination with other information on road traffic conditions from one or more other sources (for example, from road sensors). road traffic). In some embodiments, such road traffic condition information obtained from mobile data sources is used to provide information similar to that of road sensors but for roads that do not have working road sensors (for example, for roads that lack sensors, such as for geographic areas that do not have road sensor networks and / or for main roads that are not significantly large to have road sensors, for road sensors that are broken, etc.), to verify duplicate information that is received from road sensors or other sources, to identify road sensors that provide inaccurate data (for example, due to temporary or progressive problems), etc. Furthermore, road traffic conditions can be measured and represented in one or more of several ways, either based on data samples from mobile data sources and / or data readings from traffic sensors, such as in terms Absolute (for example, average speed; volume of traffic for a specified period of time; average occupation time of one or more traffic sensors or other positions on a road, such as to indicate the average percentage of time that a vehicle is over or otherwise activating a sensor; one of multiple numbered levels of road congestion, such as measured based on one or more other measures of traffic conditions; etc.) and / or in relative terms (for example, to represent a difference from normal or maximum).

ES 2 373 336 T3

In some embodiments, some road traffic condition information may take the form of data samples provided by various data sources, such as data sources associated with vehicles to report vehicle movement characteristics. Individual data samples can include varying amounts of information. For example, data samples provided by mobile data sources may include one or more of a source identifier, an indication of speed, an indication of a heading or direction, an indication of a position, a timestamp, and a time stamp. a state id. The source identifier can be a number or a character string that identifies the vehicle (or person or other device) acting as a mobile data source. In some embodiments, the mobile data source identifier may be associated permanently or temporarily (e.g., for the life of the mobile data source; for one hour; for a current session of use, such as assigning a new identifier. every time a vehicle or data source device is turned on; etc.) with the mobile data source. In at least some embodiments, source identifiers are associated with mobile data sources in such a way that privacy concerns related to data from mobile data sources (associated either permanently or temporarily) are minimized, such as creating and / or manipulating the source identifiers in a way that prevents the mobile data source associated with an identifier from being identified based on the identifier. The speed indication can reflect the instantaneous or average speed of the mobile data source expressed in various ways (for example, miles or kilometers per hour). The heading can reflect a direction of travel and be an angle expressed in degrees or another measure (for example, in compass-based or radian bearings). The position indication can reflect a physical position expressed in various ways (for example, latitude / longitude pairs or Universal Transverse Mercator coordinates). The timestamp may denote the time when a given sample of data was recorded by the mobile data source, such as in local time or UTC (Universal Coordinated Time) time. A status indicator can indicate the status of the mobile data source (for example, that the vehicle is moving, stationary, stationary with the engine running, etc.) and / or the status of at least part of the monitoring devices. detection, recording and / or transmission (eg low battery, poor signal strength, etc.).

In some embodiments, the road network in a given geographic area can be modeled or it can be represented using multiple road segments. Each road segment can be used to represent a stretch of a road (or multiple roads), such as dividing a given physical road into multiple road segments (for example, with each road segment being a particular length, such as a one mile length of road or with road segments selected to reflect road sections that share similar characteristics of traffic conditions) - such multiple road segments may be successive road sections, or alternatively in some embodiments overlap or have intermediate road sections of road that are not part of any road segment. In addition, a road segment can represent one or more travel lanes on a given physical road. Accordingly, a particular multi-lane highway that has one or more lanes to travel in each of the two directions can be associated with at least two road segments, with at least one road segment associated with travel in one direction and with at least one road segment associated with travel in the other direction. Also, in some situations, multiple lanes of a single road for one-way travel may be represented by multiple road segments, such as if the lanes have different characteristics of travel conditions. For example, a given highway system may have high-occupancy or fast vehicle (HOV) lanes that can be beneficial to represent by road segments other than highway segments that represent regular lanes (e.g., non-HOV). that travel in the same direction as the express or HOV lanes. The road segments may be further connected or otherwise associated with other adjacent road segments, thereby forming a network of road segments.

Figure 1 is a block diagram illustrating the flow of data between components of a Data Sample Manager system embodiment. The illustrated data flow diagram is intended to reflect a logical representation of data flow between data sources, the components of an embodiment of a Data Sample Manager system, and traffic data clients. That is, the true data flow can occur through a variety of mechanisms including direct flows (for example, implemented through the passing of parameters or network communications such as messages) and / or indirect flows through one or more database systems or other storage mechanisms, such as file systems. The illustrated system 100 Data Sample Manager includes a Data Sample Filter component 104, a Sensor Data Conditioner component 105, a Data Sample Outlier Remover component 106, a Data Sample Rate Evaluator component 107 and a Data Sample Flow Evaluator component 108 and an optional Sensor Data Totalizer component 110.

In the illustrated embodiment, components 104-108 and 110 of the Data Sample Manager system 100 obtain data samples from various data sources, including vehicle-based data sources 101, road traffic sensors 103, and other sources. 102 of data. The vehicle-based data sources 101 may include multiple vehicles traveling on one or more roads, each of which may include one or more computing systems and / or other devices that provide data about the vehicle's motion. As described in more detail elsewhere, each vehicle may include GPS and / or other geolocation devices capable of determining the position, speed and / or other data related to the movement of the vehicle.

ES 2 373 336 T3 vehicle. Such data can be obtained with the components of the Data Sample Manager system by wireless data links (for example, satellite uplink and / or cellular network) or in other ways (for example, through a wired physical connection that is does after a vehicle reaches the position with the physical position, such as when a vehicle from slack returns to its base of operations). Highway traffic sensors 102 may include multiple sensors that are installed on or near various streets, expressways, or other highways, such as pavement-embedded loop sensors that are capable of measuring the number of vehicles passing over the sensor. per unit of time, the speed of the vehicle and / or other data related to the data flow. Data can also be obtained from road traffic sensors 102 via wired or wireless data links. Other data sources 103 may include a variety of other types of data sources, including map services and / or databases that provide information regarding road networks such as inter-road connections as well as related traffic control information. with such roads (for example, the existence and / or position of traffic control signs and / or speed zones).

Although the illustrated data sources 101-103 in this example provide data samples directly to various components 104-108 and 110 of the Data Sample Manager system 100, the data samples may instead be processed in various ways in other prior embodiments. to be provided to those components. Such processing may include organizing and / or aggregating data samples into logical collections based on time, position, geographic region, and / or the identity of the individual data source (eg, vehicle, traffic sensor, etc.). ). Furthermore, such processing may include merging or otherwise combining higher order data samples, logical data samples, or other values. For example, data samples obtained from multiple geographically located road traffic sensors can be merged into a single logical data sample by averaging or totaling. In addition, such processing may include the derivation or otherwise synthesizing of data samples or data sample elements based on one or more obtained data samples. For example, in some embodiments, at least some vehicle-based data sources may each provide the data samples that include only a source identifier and a geographic location, and if that is the case for groups of multiple samples of distinct data provided periodically in a particular time interval or other time period can thus be associated with each other as if it had been provided by a particular vehicle. Such groups of data samples can then be further processed in order to determine other information related to displacement, such as a heading for each data sample (for example by calculating the angle between the position of a data sample and the position of a previous and / or subsequent data sample) and / or a rate for each data sample (for example, calculating the distance between the position of a data sample and the position of a previous and / or subsequent data sample, and dividing the distance by the corresponding time).

The data sample filter component 104 obtains data samples from the vehicle-based data sources 101 and the other data sources 102 in the illustrated embodiment, and then filters the obtained data samples before providing them to the data remover component 106. Data Sample Outliers and optionally to component 108 Data Sample Flow Evaluator. As discussed in greater detail elsewhere, such filtering may include the association of data samples with road segments that correspond to roads in a geographic area and / or the identification of data samples that do not correspond to road segments of interest or otherwise reflect vehicle positions or activities that are not of interest. Associating data samples with road segments may include using the reported position and / or heading from each data sample to determine whether the position and heading correspond to a previously defined road segment. Identifying data samples that do not correspond to cart segments of interest may include removing or otherwise identifying such data samples so that they will not be modeled, considered, or otherwise processed by other components of the system 100 Manager Data Samples - such data samples to be deleted may include those for roads of certain functional road classes (for example, residential streets) that are not of interest, those corresponding to particular roads or road segments that are not of interest, those corresponding to parts or sections of roads that are not of interest (for example, ramps and secondary roads / distribution lanes / highway roads), etc. Identifying data samples that otherwise reflect positions or activities of vehicles that are not of interest may include identifying data samples that correspond to vehicles that are in a stopped state (for example, parked with the engine running) , which are driven in a parking structure (for example, circling at very low speed), etc. Additionally, filtering in some embodiments may include identifying road segments that are (or are not) of interest for further presentation or analysis. For example, such filtering may include analysis of the variability of the traffic flow and / or level of congestion of various road segments in a particular time period (e.g. hour, day, week), such as excluding some or all road segments with low variability between time periods and / or low congestion (for example, for road segments for which sensor data readings are not available or whose road functional class otherwise indicates a smaller or less traveled road) from further analysis as being of less interest than other roads or road segments. highway.

Sensor Data Conditioner component 105 helps rectify erroneous data samples, such as detecting and correcting errors in readings obtained from road traffic sensors 103. For example,

ES 2 373 336 T3 data samples that are detected by the Sensor Data Conditioner component as being unreliable are not forwarded to other components for use (or indications of the unreliability of particular data samples are provided so that the other components can handle those data samples accordingly), such as the Data Sample Outlier Remover component 106. If that is the case, the Data Sample Outlier Remover component can then determine if sufficient reliable data samples are available and if not initiate corrective action. Alternatively, the Sensor Data Conditioner component may further perform at least some corrections to the data samples, as discussed in more detail below, and then provide the corrected data to the Sensor Data Totalizer component 110 (and optionally to other components such as the Data Sample Outlier Eliminator component and / or the Data Sample Flow Evaluator component). Detecting erroneous data samples can use various techniques, including statistical measures that compare the distribution of current data samples reported by a given road traffic sensor with the historical distribution of data samples reported by that road traffic sensor during a corresponding period of time (for example, the same day of the week and time of day). The extent to which the true and historical distributions differ can be calculated by statistical measures, such as the Kullback-Leibler divergence, which provides a convex measure of the similarity between two probability distributions and / or by statistical entropy of information. In addition, some road sensors can report sensor health indications and such indications can also be used to detect errors in data samples. If errors are detected in samples obtained from data, erroneous data samples can be rectified in a number of ways, including replacing such data samples by averages of adjacent data samples (e.g., neighbors) from adjacent / neighboring road sensors. that have been determined not to be in error. Furthermore, erroneous data samples can be rectified by using instead predicted and / or predicted values ​​previously or at the same time, such as can be provided by a predictive traffic information system. Additional details regarding predictive traffic information systems are provided elsewhere.

The Data Sample Outlier Remover component 106 according to the present invention obtains filtered data samples from the Data Sample Filter component 104 and / or otherwise conditioned or rectified data samples of the Data Conditioner component 105. Sensor, and then identifies and removes to disregard those data samples that are not representative of actual vehicle movements on the roads or road segments of interest. In the illustrated embodiment, for each road segment of interest, the component analyzes a group of data samples that were recorded during a particular time period and associated with the road segment (for example, by component 104 Data) in order to determine which, if any, should be removed. Such determinations of unrepresentative data samples can be performed in a number of ways, including those based on techniques that detect data samples that are statistical outliers with respect to the other data samples in the data sample pool. Additional details regarding removing outliers from data samples are provided elsewhere.

The Data Sample Rate Evaluator component 107 obtains data samples from the Data Sample Outlier Remover component 106, such that the data samples obtained in the illustrated embodiment are representative of the actual movement of vehicles on the roads and road segments of interest. The Data Sample Speed ​​Evaluator component then analyzes the obtained data samples to evaluate one or more speeds of road segments of interest for at least one time period of interest based on a group of data samples that have been associated. with the road segment (for example, by the Data Sample Filter component 104 or by readings from traffic sensors that are part of the road segment) and the time period. In some embodiments, the speed (s) evaluated may include an average of the speeds for multiple data samples in the group, possibly weighted by one or more attributes of the data samples (e.g., age, such as to give greater weight. to more recent data samples and / or the source or type of the data samples, such as varying the weight for data samples from mobile data sources or road sensors to give more weight to sources with higher expected reliability or availability) or by other factors. More details regarding the rate evaluation of data samples are provided elsewhere.

Component 108 Data Sample Flow Evaluator assesses traffic flow information for road segments of interest over at least one time period of interest, such as to evaluate traffic volume (e.g., expressed as a number total or average number of vehicles arriving on, or traversing, a road segment in a particular amount of time, such as per minute or hour), to assess traffic density (for example, expressed as an average or total number of vehicles per unit of distance, such as per mile or kilometer), to assess traffic occupancy (for example, expressed as an average or total amount of time that vehicles occupy a particular point or area in a particular amount of time, such as per minute or hour), etc. The evaluation of the traffic flow information in the illustrated embodiment is based at least in part on the traffic speed related information provided by the Data Sample Rate Evaluator component 107 and the Outlier Remover component 106. Data Samples, and optionally on traffic data sample information provided by

ES 2 373 336 T3 the Sensor Data Conditioner component 105 and the Data Sample Filter component 104. Additional details regarding the data sample flow evaluation are provided elsewhere.

If present, the Sensor Data Totalizer component 110 totals the sensor-based traffic condition information provided by the Sensor Data Conditioner component 105, such as after the Sensor Data Conditioner component has removed any samples not present. reliable data and / or rectified any missing and / or unreliable data samples. Alternatively, the Sensor Data Totalizer component may instead perform any removal and / or correction of missing and / or unreliable data samples. In some cases, Sensor Data Totalizer component 110 may provide traffic flow information for each of several road segments by totalizing (e.g., averaging) the information provided by the multiple individual traffic sensors associated with each. one of those road segments. As such, when present, the Sensor Data Totalizer component 110 may provide information that is complementary to the evaluated information of traffic conditions provided by components such as the Data Sample Rate Evaluator component 107 and / or the Data Sample Flow Evaluator, or instead it can be used if no data samples are available from mobile data sources at all or in sufficient quantity of reliable data samples to allow other components such as component 107 Sensor Sample Rate Evaluator and component 108 Flow Evaluator Data Samples provide accurate assessed information of road traffic conditions.

The one or more traffic data clients 109 may obtain evaluated information on road traffic conditions (eg, speed and / or flow data) provided by the Data Sample Rate Evaluator component 107 and / or the component 108 Data Sample Flow Evaluator, and can use such data in various ways. For example, traffic data clients 109 may include other traffic information components and / or systems managed by the operator of the Data Sample Manager system 100, such as a predictive traffic information provider system that uses traffic condition information to generate predictions of future traffic conditions at multiple future times and / or a presentation of traffic information in real time (or near real time) or Provider system that provides information on traffic conditions in real time (or close to real time) to end users and / or third party clients. Furthermore, the traffic data clients 109 may include computing systems operated by third parties to provide traffic information services to their clients. Furthermore, the one or more traffic data clients 109 may optionally in some circumstances (for example, in cases where insufficient data is available for the Data Sample Rate Evaluator component and / or the Data Sample Flow evaluator component to perform accurate evaluations and / or if no data is available from vehicle-based data sources or others) obtain information on road traffic conditions provided by component 110 Sensor Data Totalizer, either instead of or in addition to the data from the Data Sample Rate Evaluator component and / or the Data Sample Flow Evaluator component.

For illustrative purposes, some embodiments and aspects related to the present invention are described below in which specific types of road traffic conditions are evaluated in specific ways and in which such evaluated traffic information is used in various specific ways.

Figures 2A-2E illustrate examples of evaluating road traffic conditions based on data obtained from vehicles and other mobile data sources, as can be done with one embodiment of the Data Sample Manager system. In particular, Figure 2A illustrates an example data sample filtering for an example area 200 with multiple highways 201, 202, 203, and 204, and with a legend indication 209 indicating the north direction. In this example, highway 202 is a divided limited access highway such as a highway or toll road, with two distinct sets of lanes 202a and 202b for west and eastbound vehicle travel, respectively. Lane group 202a includes one HOV lane 202a2 and multiple other regular lanes 202a1, and lane group 202b similarly includes one HOV lane 202b2 and multiple other regular lanes 202b1. Highway 201 is a main highway with two lanes 201a and 201b for the movement of vehicles in the south and north directions, respectively. Highway 201 passes over Highway 202 (for example, via an overpass or bridge), and Highway 204 is a ramp connecting the northbound lane 201b of Highway 201 with the eastbound lane group 202b from Highway 202. Highway 203 is a local service highway adjacent to Highway 202.

The roads represented in Figure 2A can be represented in various ways for use by the Data Sample Manager system. For example, one or more road segments may be associated with each physical road, such as to have northbound and southbound road segments with the northbound lane 201b and the southbound lane 201a respectively. Also, at least one westbound highway segment and at least one eastbound highway segment may be associated with westbound lane group 202a and eastbound highway group 202b of highway 202, respectively. For example, the portion of eastbound lane group 202b east of highway 201 may be a separate highway segment from the portion of eastbound lane group 202b west of highway 201, such as based on conditions. of highway traffic that often or normally varies between highway parts (for example, due to a normally significant entry of vehicles into lane group 202b east of highway 201 from ramp 204, such as that can normally cause more congestion in lane group 202b when

ES 2 373 336 T3 east of Highway 201). In addition, one or more lane groups may be broken down into multiple road segments, such as if different lanes normally or often have different characteristics of road traffic conditions (for example, to represent some given part of the lane group 202b as a first road segment corresponding to lanes 202b1 based on those lanes that share similar characteristics of traffic conditions, and as a second road segment that corresponds to the lane of HOV 202b2 due to its different characteristics of traffic conditions) - in other such situations, only a single road segment can be used for such a group of lanes, but some data samples (for instance, those corresponding to the lane of HOV 202b2) can be excluded from being used (such as by a Data Sample Filtering component and / or a Data Sample Outlier Eliminator component) when evaluating road traffic conditions for the group of lanes. Alternatively, some embodiments may represent multiple lanes of a given road as a single road segment, even if the lanes are used for travel in opposite directions, such as if road traffic conditions are normally similar in both directions - for For example, service road 205a may have two opposing lanes of travel, but may be represented by a single road segment. Road segments can be determined at least in part in a variety of other ways, such as being associated with geographic information (e.g., physical dimensions and / or heading (s)) and / or traffic-related information (e.g., road limits). speed).

Figure 2A further depicts multiple data samples 205a-k reported by multiple mobile data sources (e.g., vehicles, not shown) moving in zone 200 during a particular time interval or other time period (e.g. example 1 minute, 5 minutes, 10 minutes, 15 minutes, etc.). Each of the data samples 205a-k is represented as an arrow indicating a heading for the data sample, as reported by one of the multiple mobile data sources. Data samples 205a-k are overlaid over zone 200 in such a way that they reflect the positions reported for each of the data samples (for example, expressed in units of latitude and longitude, such as those based on GPS readings), which may be different from the true vehicle positions when that data sample was recorded (for example, due to inaccurate or erroneous reading, or due to a degree of variability that is inherent in the position sensing mechanism used). For example, data sample 205g shows a position that is slightly north of highway 202b, which may reflect a vehicle that was pulled off the north side of lane 202b2 (for example, due to mechanical dysfunction), or in change may reflect an inaccurate position for a vehicle that was actually traveling eastbound in lane 202b2 or another lane. In addition, a single mobile data source may be the source of more than one of the illustrated data sources, such as if both samples 205i and 205h were reported by a single vehicle based on its eastbound travel on Highway 202 during the period. time period (eg, through a single transmission containing multiple data samples for multiple previous time points, such as reporting data samples every 5 minutes or every 15 minutes). More details regarding storing and providing multiple acquired samples of data are illustrated below.

The Data Sample Manager system can filter the obtained data samples, such as to plot data samples on predefined road segments and / or identify data samples that do not correspond to such road segments of interest. A data sample can be associated with a road segment if its reported position is within a predetermined distance (for example, 5 meters) of the position of a road and / or the lanes corresponding to the road segment and if its heading is within of a predetermined angle (eg, plus or minus 15 degrees) from the heading of the road and / or the corresponding lanes of the road segment. Road segments can be associated with enough position-based information (e.g., road segment heading, road segment physical boundaries, etc.) to make such a determination, although association of data samples with road segments also it can be done before the data samples are available to the Data Sample Manager system.

As an illustrative example, data sample 205a can be associated with a road segment that corresponds to highway 203, because its reported position falls within the limits of highway 203 and its heading is the same (or nearly the same) as for at least one of the directions associated with Highway 203. In some cases, when a single road segment is used to represent multiple lanes, some of which travel in opposite directions, the heading of a data sample can be compared to both road segment heads to determine whether the data sample can be associated with the road segment. For example, data sample 205k has a bearing approximately opposite to that of data sample 205a, but can also be associated with the road segment that corresponds to road 203, if that road segment is used to represent the two opposite lanes. from Highway 203.

However, due to the proximity of highway 203 and lane group 202a, it may also be possible for the data sample 205k to reflect a vehicle traveling in lane group 202a, such as if the reported position of the sample 205k of data is within a margin of error for vehicle positions traveling in one or more of the lanes of lane group 202a, since the heading of data sample 205k is the same (or nearly the same) as the heading of lane group 202a. In some cases, such cases can be disambiguated from multiple possible road segments for a data sample based on other information associated with the data sample - for example, in this case, an analysis of the reported speed of the sample. 205k of data can be used to help disambiguate, such as if the lane group

ES 2 373 336 T3

202a corresponds to a highway with a speed limit of 65 mph, Highway 203 is a local service highway with a speed limit of 30 mph, and a reported speed from the data sample is 75 mph (resulting in an association with the expressway lanes which is much more likely than an association with the local service road). More generally, if the reported speed from the 205k data sample is more similar to the observed or advertised speed for highway 203 than the observed or advertised speed for lane group 202a, such information can be used as part of the determination to associate the data sample with highway 203 and not with lane group 202a. Alternatively, if the reported 205k data sample speed is more similar to the observed or advertised speed for lane group 202a than the observed or advertised speed for highway 203, it can be associated with lane group 202a and not the highway 203. Similarly, other types of information may be used as part of such disambiguation (e.g., position; heading; status; information about other related data samples, such as other recent data samples from the same mobile data source; etc. .), such as part of a weighted analysis to reflect a degree of agreement for each type of information for a data sample with a candidate road segment.

For example, regarding the association of data samples 205a with an appropriate road segment, its reported position occurs in an overlap between lane 201b and lane group 202a and is close to lane 201a as well as other highways. However, the heading reported from the data samples (roughly northbound) matches the heading of lane 201b (northbound) much more closely than that of other candidate lanes / roads, and thus will likely be associated with the road segment corresponding to lane 201b in this example. Similarly, the data sample 205c includes a reported position that can match multiple roads / lanes (e.g., lane 201a, lane 201b, and lane group 202a), but its heading (roughly west) can be used to selecting a road segment for lane group 202a as the most appropriate road segment for the data sample.

Continuing with this example, data sample 205d cannot be associated with any road segment, because its heading (approximately east) is in the opposite direction as that of lane group 202a (west) whose position corresponds to position informed of the data samples. If there are no other appropriate candidate road segments that are close enough (e.g., within a predetermined distance) to the position reported from the data samples 205d, such as if the lane group 202b with a similar bearing is too far away, during Filtering this data sample can be excluded from subsequent use in the analysis of the data samples.

Data sample 205e can be associated with a road segment that corresponds to lane group 202a, such as a road segment that corresponds to a lane of HOV 202a2, since its reported position and heading correspond to that position and heading. lane, such as whether a position-based technique used to position the data sample has sufficient resolution to differentiate between lanes (for example, differential GPS, infrared, sonar or radar locating devices. Data samples can also be associated with a particular lane on a multi-lane road based on factors other than position-based information, such as whether the lanes have different characteristics of traffic conditions. For example, in some cases the reported velocity of a data sample can be used to fix or match the data sample to a particular lane by modeling an expected distribution (for example, a normal or Gaussian distribution) of observed velocities (or other traffic flow measurements) of data samples for each of such candidate lanes and determine a best fit for the data sample with the expected distributions. For example, data sample 205e may be associated with the road segment that corresponds to the lane of HOV 202a2 because the reported speed from that data sample is closer to an inferred or historical observed average speed of vehicles moving in the lane. from HOV 202a2 than from an inferred or historical observed average speed of vehicles traveling on regular lanes 202a1, such as by determining an observed or inferred average speed based on other data samples (eg, using data readings provided by one or more road traffic sensors) and / or analysis of other related current data.

In a similar way, data samples 205f, 205h, 205i, and 205j can be associated with the road segments that correspond to lane 201a, lanes 202b1, lanes 202b1, and ramp 204, respectively, because their reported positions and bearings correspond to the positions and bearings of those roads or lanes.

Data samples 205g can be associated with a road segment that corresponds to lane group 202b (for example, a road segment for HOV lane 202b2) even though its reported position is outside the boundaries of the illustrated road, because the Reported position can be within the predetermined distance (eg 5 meters) from the road. Alternatively, the data sample 205g cannot be associated with some road segment if its reported position is distant enough from the road. In some cases, different predetermined distances may be used for data samples provided by different data sources, such as to reflect a known or expected level of precision from the data source. For example, data samples provided by mobile data sources using uncorrected GPS signals may use a relatively high predetermined distance (for example, 30 meters), while

ES 2 373 336 T3 data samples provided by mobile data sources using differential corrected GPS devices can be compared using a relatively low predetermined distance (eg 1 meter).

In addition, filtering data samples may include identifying data samples that do not correspond to road segments of interest and / or are poorly representative of true vehicle travel on roads. For example some data samples can be eliminated from being considered because they have been associated with roads that are not considered by the Data Sample Manager system. For example, in some cases data samples associated with roads of lower functional road classes (for example, residential streets and / or major roads) may be filtered. Referring back to Figure 2A, for example, the 205a and / or 205k data samples may be filtered because Highway 203 is a local service highway that is of a low enough functional rating not to be considered by the system. Data Sample Manager, or the 205j data sample can be filtered because the ramp is too short to be of interest independent of the highway. Filtering may also be based on other factors, such as inferred or reported activity from mobile data sources versus inferred or reported activity from other mobile data sources on one or more road segments. For example, a series of data samples associated with a road segment and provided by a single mobile data source all indicating the same position probably indicates that the mobile data source has stopped. If all other data samples associated with the same road segment indicate moving mobile data sources, the data samples that correspond to the stopped mobile data source may be filtered out as being poorly representative of the true movement of the vehicle in the segment. road, such as because the mobile data source is a parked vehicle. In addition, in some cases, the data samples may include informed indications of the vehicle's driving status (for example, that the vehicle's transmission is in park with the engine running, such as a vehicle stopped to make a delivery), and If that is the case, such prompts can similarly be used to filter out such data samples as being unrepresentative of actual moving vehicles.

Figure 2B illustrates a graphical view of multiple data samples associated with a single road segment obtained from multiple data sources during a particular time interval or other time period, with the data samples plotted on a graph 210 with measured time. on the x-axis 210b and the velocity measured on the y-axis 210a. In this example, the illustrated data samples have been obtained from multiple mobile data sources as well as one or more road traffic sensors associated with the road segment, and are displayed in different ways as illustrated in the displayed legend ( that is, with darkened diamonds (♦) for data samples obtained from road traffic sensors, and with empty squares' (for data samples obtained from mobile data sources). The illustrated samples of mobile data source data may have been associated with the road segment as described with reference to Figure 2A.

Examples of data samples include road traffic sensor data samples 211a-d and mobile data source data samples 212a-d. The reported speed and recording time of a given data sample can be determined by its position on the graph. For example, the mobile data source data sample 212d has a reported speed of 15 miles per hour (or other unit of speed) and was recorded at a time of approximately 37 minutes (or other unit of time) with respect to some starting point. As will be described in greater detail later, some case examples may analyze or otherwise process the collected data samples within particular time intervals during the time period being plotted, such as time interval 213. In this example, time interval 213 contains data samples logged over a 10 minute time interval from the 30 minute time to the 40 minute time point. In addition, some case examples may further divide the group of data samples that occur within a particular time interval into two or more groups, such as group 214a and group 214b. For example, it should be noted that the illustrated data samples appear to reflect a two-mode distribution of reported speeds, with most data samples reporting speeds in the 25-30 mph range or in the 0- 8 miles per hour. Such a two-mode or multiple-mode distribution of speeds can occur, for example, because the essential patterns of traffic flow are not uniform, such as due to a traffic control signal that causes traffic to flow in a non-uniform pattern. stop and go, or to the road segment that includes multiple lanes of traffic moving at different speeds (for example, an HOV or express lane with relatively higher speeds than other non-HOV lanes). In the presence of such multi-mode distributions of speed data, some case examples may divide the data samples into two or more groups for further processing, such as producing better processing precision or resolution (for example, by calculating different average speeds that more accurately reflect the speeds of various traffic flows) as well as additional information of interest (for example, the rate differential between HOV traffic and non-HOV traffic), or to identify a group of data samples to exclude (for example, not include HOV traffic as part of a subsequent analysis). Although not illustrated herein, such distinct groups of data samples can be identified in a number of ways, including modeling a distinct distribution (eg, a normal or Gaussian distribution) for the observed velocities of each group.

Figure 2C illustrates an exemplary embodiment of removing outliers from data samples to filter or otherwise exclude consideration of those data samples that are poorly representative of vehicles traveling on a particular road segment, which in this The example is based on the reported speed for the

ES 2 373 336 T3 data samples (although in other cases one or more attributes of the data samples may instead be used as part of the analysis, either instead of or in addition to the reported rates). In particular, Figure 2C shows a table 220 illustrating data sample outlier removal that is performed on an example group of ten data samples (in true use, the number of data samples that are analyzed can be be much bigger). The illustrated data samples may, for example, be all data samples that occur within a particular time interval (such as time interval 213 in Figure 2B), or alternatively they may include only a subset of the data samples from a particular time interval (such as those included in group 214a or 214b of Figure 2B) or can include all available data samples for a larger time period.

In the present example, unrepresentative data samples are identified as being statistical outliers with respect to other data samples in a given group of data samples by determining the velocity deviation of each data sample in a group of data samples from the average velocity of the other data samples in the group. The deviation of each data sample can be measured, for example, as a function of the number of difference of standard deviations from the mean speed of the other data samples in the group, with data samples whose deviations are greater than a predetermined threshold ( for example 2 standard deviations) that are identified as outliers and excluded from further processing (for example, being discarded).

Table 220 includes a heading row 222 that describes the content of multiple columns 221a-f. Each row 223a-j of Table 220 illustrates a data sample outlier elimination analysis for the different of the ten data samples, with column 221a indicating the data sample being analyzed for each row when each sample of data is analyzed, it is excluded from the other samples of the group to determine the resulting difference. The data sample in row 223a can be referred to as the first data sample, the data sample in row 223b can be referred to as the second data sample, and so on. Column 221b contains the reported speed of each of the data samples, measured in miles per hour. Column 221c lists the other data samples in the group against which the data sample in a given row will be compared, and column 221d lists the approximate average speed of the group of data samples indicated by column 221c. Column 221e contains the approximate deviation between the speed of the excluded data sample in column 221b and the average speed listed in column 221d of the other data samples, measured in the number of standard deviations. Column 221f indicates whether the given sample of data would be eliminated, based on whether the deviation listed in column 221e is more than 1.5 standard deviations for the purposes of this example. Also, the mean speed 224 for the 10 data samples is shown to be approximately 25.7 miles per hour, and the standard deviation 225 for the 10 data samples is shown to be approximately 14.2.

Thus, for example, row 223a illustrates that the speed of data sample 1 is 26 miles per hour. The average speed of the other data samples 2-10 is then calculated as approximately 25.7 miles per hour. The deviation of the speed of data sample 1 from the mean speed of the other data samples 2-10 is then calculated as being approximately 0.02 standard deviations. Finally, data sample 1 is determined as not being an outlier since its deviation is below the threshold of 1.5 standard deviations. In addition, row 223c illustrates that the speed of data sample 3 is 0 miles per hour and that the average speed of the other data samples 1-2 and 4-10 is calculated as approximately 28.6 miles per hour. Next, the deviation of the speed of data sample 3 from the mean speed of the other data samples 1-2 and 4-10 is calculated as being approximately 2.44 standard deviations. Finally, data sample 3 is determined to be removed as an outlier since its deviation is above the threshold of 1.5 standard deviations.

More formally, given N data samples, v0, v-ι, v2, ..., vn, recorded in a given time period and associated with a given road segment, a current data sample vi will be removed if h ' r ~ ^? l _c (7_AND^_ where i saw is the speed of the current data sample being analyzed; . is the average of the velocity of the other data samples (v0, ..., v¡-1, v¡ + 1, ..., vn); σi is the standard deviation of the other data samples; and c is a constant threshold (for example, 1.5). Furthermore, as a special case for handling a potential division by zero, the current sample v, will be eliminated if the standard deviation of the other data samples, o, is zero and the velocity of the current data sample is not equal to the average speed of the other data samples, · ..

It should be noted that for each vi it ​​is not necessary to iterate through all the other data samples (v0, ..., v, -1, v, + 1, ..., vn) in order to calculate the mean and the standard deviation o¡. The^μί. mean of the other samples of Vo, ..., v¡_i, v¡ + i, ..., vn can be expressed as follows:

ES 2 373 336 T3 jVv - V¡

<img file="ES2373336T3_D0001.tif" />

and the standard deviation σi of the other data samples v0, ..., v¡-1, v¡ + 1, ..., vn can be expressed as follows:

<img file="ES2373336T3_D0002.tif" />

where N is the total number of data samples (including the current data sample); is the average of all data samples v0, v-ι, v2, ..., vn; vi is the current data sample, and σ is the standard deviation of all data samples v0, v1, v2, ..., vn. Using the above formulas, means and standard deviations can be efficiently calculated and in particular can be calculated for constant time. Since the algorithm above calculates an average and a standard deviation for each data sample on each road segment, the algorithm runs at a time O (MN), where M is the number of road segments and N is the number of data samples per road segment.

Another algorithm for outlier detection and / or data removal comprises techniques based on neural network classifiers, simplistic Bayesian classifiers, and / or regression modeling, as well as techniques in which groups of multiple data samples are considered at the same time. time (for example, if at least some data samples are not independent of other data samples).

Figure 2D illustrates an example average speed evaluation embodiment using data samples, and shows examples of data samples similar to those depicted in Figure 2B for a particular road segment and time period. The data samples have been plotted on a graph 230, with time measured on the x-axis 230b and speed measured on the y-axis 230a. In some cases, the average speed for a given road segment can be calculated periodically (for example every 5 minutes). Each calculation can consider multiple data samples within a predetermined time interval (or interval), such as 10 minutes or 15 minutes. If the average speeds are calculated at such time intervals, such as at or near the end of the time intervals, the data samples within a time interval can be weighted in various ways by totaling the rates of the data samples. such as taking into account the age of the data samples (for example, to discount older data samples based on intuition and the hope that they will not provide information as accurate as true traffic conditions at the end of the time interval or another current time as more recent data samples recorded relatively closer to the current time due to changing traffic conditions). Similarly, other attributes of data samples can be considered when weighting data samples, such as a type of data source or a particular data source for a data sample (for example, to weight data samples with more weight if they come from a data source type or a particular data source believed to be more accurate than others or otherwise providing better data than others), as well as one or more types of weighting factors.

In the illustrated example, an average speed for the highway segment example is calculated every five minutes in a time interval of 15 minutes. The example represents the relative weights of two illustrative data samples, 231a and 231b, as they contribute to the calculated mean speed of each of two time intervals, 235a and 235b. Time interval 235a includes data samples recorded between times 30 and 45, and time interval 235b includes data samples recorded between times 35 and 50. The two data samples 231a and 231b fall within both time intervals. 235a and 235b.

In the illustrated example, each data sample in a given time interval is weighted in proportion to its age. That is, older data samples weigh less (and therefore contribute less to average speed) than newer data samples. Specifically, the weight of a given sample of data decreases exponentially with age in this example. This down weighting function is illustrated by two weight graphs 232a and 232b corresponding to time intervals 235a and 235b, respectively. Each weight graph 232a and 232b plots the recording time of the data samples on the x-axis (horizontal) versus the weight on the y-axis (vertical). Samples recorded later in time (for example, closer to the end of the time interval) weigh more than samples recorded earlier in time (for example, closer to the beginning of the time interval). The weight for a given sample of data can be visualized by dropping a vertical line down the sample of data on graph 230 to where it intersects the curve of the weight graph corresponding to the time interval of interest. For example, the weight chart 232a corresponds to the time interval 235a, and according to the relative ages of the data samples 231a (oldest) and 231b (most recent), the weight 233a of the data sample 231a is less than the weight 233b of the data sample 231b. Furthermore, the weight graph 232b corresponds to the time interval 235b, and similarly it can be seen that the weight 234a of the data sample 231a is less than the weight 234b of the data sample 231b. Furthermore, it is evident that the weight of a given sample of dice decays with time with respect to subsequent intervals of time. For example, the weight 233b, of the data sample 231b in the time interval 235a is greater than the weight 234b

ES 2 373 336 T3 of the same data sample 231b in the later time interval 235b, because the data sample 231b is relatively more recent during the time interval 235a compared to the time interval 235b.

More formally, the weight of a data sample recorded at time t with respect to a time conclusion at time T can be expressed as follows:

<img file="ES2373336T3_D0003.tif" />

where e is the well-known mathematical constant and α is a variable parameter (eg 0.2). Given the above, a weighted average velocity for N data samples v0, v-ι, v2, ..., vn, at the conclusion of the time interval at time T can be expressed as follows, with you being the moment which represents the data sample vi (for example, the time it was recorded):

Weighted Average FeIOocíCGC = —-------—

Furthermore, an error estimate for the calculated mean speed can be calculated as follows:

to

Err estimate = —— where N is the number of data samples and σ is the standard deviation of the samples v0, v1, v2, ..., vn of the mean velocity. Similarly, other forms of confidence values ​​can be determined for calculated or generated average speeds.

As noted, data samples can be weighted based on other factors, either instead of or in addition to how recent the data samples are. For example, data samples can be weighted over time as described above but using different weight functions (for example, the weight of a data sample decreases linearly, rather than exponentially, with age). . In addition, the weighting of data samples can be further based on the total number of data samples in the time interval of interest. For example, the variable parameter α described above may depend or otherwise vary based on the total number of data samples, such that larger numbers of data samples result in higher penalties (e.g., lower weights) for Older data samples, to reflect the increased probability that more low latency data samples (for example, newer) will be available in order to calculate the average speed. Additionally, data samples can be weighted based on other factors, including the type of data source. For example, it may be the case that it is known (for example, based on reported status information) or expected (for example, based on historical observations) that particular data sources (for example, particular road traffic sensors or all traffic sensors on a particular network) are unreliable or otherwise inaccurate. In such cases, data samples obtained from such road traffic sensors (for example, such as data sample 211a of Figure 2B) may have less weight than data samples obtained from mobile data sources (for example, data sample 212a of Figure 2B).

Figure 2E provides an exemplary embodiment of traffic flow evaluation for road segments based on data samples, such as may include inferring traffic volumes, densities, and / or occupancy. In this example, the traffic volume of a given road segment is expressed as a total number of vehicles flowing in a given interval of time through the road segment or a total number of vehicles arriving on the road segment during the interval of time, the traffic density of a given road segment is expressed as a total number of vehicles per unit of distance (for example, miles or kilometers), and traffic occupancy is expressed as an average amount of time that a particular road segment or point of the road segment is occupied by a vehicle.

Given several different mobile data sources observed traveling on a given road segment during a given time interval, and a known or expected percentage of total vehicles that are mobile data sources, it is possible to infer a total volume of traffic - the total number of vehicles (including vehicles that are not mobile data sources) moving along the road segment during the time interval. From the total inferred volume of traffic and evaluating the average speeds for vehicles in the highway segment, it is also possible to calculate the traffic density as well as the occupation of the highway.

An unsophisticated approach to estimating the total volume of traffic on a particular road segment during a particular time interval would be to simply divide the number of mobile data sample sources for that time interval by the percentage of true vehicles that are expected to be mobile sources of data samples - thus, for example, If mobile data samples are received from 25 mobile data sources during the time interval and 10% of the total vehicles in the highway segment are expected to be mobile data sample sources, the estimated total volume would be 250 true vehicles for the amount of time in the time interval. However, this approach can lead to large variability of volume estimates for adjacent time intervals due to the inherent variability of the rates of

ES 2 373 336 T3 arrival of vehicles, particularly if the expected percentage of mobile data sample sources is small. As an alternative that provides a more sophisticated analysis, the total traffic volume of a given road segment can be inferred as follows. Given an observation of a number of different mobile data sources (for example, individual vehicles), n, on a road segment of length l, during a given time period τ, the Bayesian statistic can be used to infer an average rate essential arrival of mobile data sources λ. The arrival of mobile data sources in the road section that corresponds to the road segment can be modeled as a random and discrete process in time, and therefore can be described with Poisson statistics, in such a way that:

<img file="ES2373336T3_D0004.tif" />

From the above formula, the probability that n mobile data sources are observed can be calculated, given an average arrival rate λ and an observed number of vehicles n. For example, assuming a mean arrival rate of λ = 10 (vehicles / time unit) and an observation of n = 5 vehicles. Substitution fields

10³and^the pGilJO = - * 0.038 indicating a 3.8% probability of actually observing n = 5 vehicles. Similarly, the probability of actually observing 10 arriving vehicles (that is, n = 10) if the average arrival rate is λ = 10 (vehicles / time unit) is approximately 12.5%.

The above formula can be used in conjunction with Bayes' Theorem in order to determine the probability of a particular arrival rate λ given an observation of n. As is known, Bayes' Theorem is:

<img file="ES2373336T3_D0005.tif" />

By substituting and eliminating constants, the following can be obtained:

<img file="ES2373336T3_D0006.tif" />

From the above, a proportional or relative probability of an arrival rate λ, given an observation of mobile data sources n, can be calculated, providing a probability distribution about possible values ​​of λ given various observed values ​​for n. For a particular value of n, the probability distribution at various values ​​of the arrival rate allows a unique representative value of the arrival rate to be selected (for example, a mean or an average) and a degree of confidence in that value. that is going to be evaluated.

Furthermore, given a known percentage q of total vehicles on the road that are mobile data sources, also referred to as the penetration factor, the volume of the total traffic arrival rate can be calculated as λ

Volume, total traffic = &lt;1

The total volume of traffic for a road segment during a period of time can alternatively be expressed as a total number of vehicles k flowing in a time τ along a length l of the road segment.

Figure 2E illustrates the probability distribution of various total traffic volumes given observed sample sizes, given an example mobile data source penetration factor of q = 0.014 (1.4%). In particular, Figure 2E represents a three-dimensional graph 240 that plots the observed number of mobile data sources (n) on the y-axis 241 versus the inferred volume of traffic arrival rate on the x-axis 242 and versus the probability of each inferred traffic volume value on the z-axis 243. For example, the graph shows that given an observed number of mobile data sources of n = 0, the probability that the true volume of traffic is close to zero is approximately 0.6 (or 60%), as illustrated by the bar 244a, and the probability that the true volume of traffic is close to 143 vehicles per unit time is approximately 0.1, as illustrated by bar 244b. Furthermore, given an observed number of mobile data sources of n = 28, the probability that the total true volume of traffic is close to 2,143 vehicles per unit time (corresponding to approximately 30 mobile data sources per unit time) , given the example penetration factor) is approximately 0.1, as illustrated by bar 244c, which appears to be close to the median value for true total volume of traffic.

ES 2 373 336 T3

Furthermore, the mean occupancy and density can be calculated using the inferred total traffic arrival rate volume for a given road segment (representing a number of vehicles k arriving during time τ at the road segment), the evaluated mean speed v and an average vehicle length, as follows:

Jt

Vehicles per mile, m = - 'vr

Occupation = md

As described above, the average speed v of the vehicles on the road segment can be obtained using speed evaluation techniques, such as those described with reference to Figure 2D.

Figures 10A-10B illustrate examples of conditioning and rectifying another mode of erroneous data samples from road traffic sensors, such as unreliable samples and missing data samples. In particular, Figure 10A shows several example data readings obtained from multiple traffic sensors at various times, arranged in a table 1000. Table 1000 includes multiple rows of data reads 1004a-1004 and each including a traffic sensor ID (identification) 1002a that uniquely identifies the traffic sensor that provided the reading, a value 1002b of traffic sensor data read including traffic flow information reported by the traffic sensor, a traffic sensor data reading time 1002c reflecting the time when the data reading was taken by the traffic sensor, and a traffic sensor status 1002d including an indication of the functional status of the traffic sensor. In this example, only speed information is displayed, although additional types of traffic flow information may be reported by traffic sensors (eg, traffic volume and occupancy), and the values ​​may be reported in other formats.

In the illustrated example, the data readings 1004a-1004y have been taken by multiple traffic sensors multiple times and recorded as depicted in Table 1000. In some cases, the data readings may be taken by traffic sensors in a similar way. periodically (for example, every minute, every five minutes, etc.) and / or be informed by the traffic sensors in such a periodic way. For example, traffic sensor 123 takes data readings every five minutes, as shown by data readings 1004a-1004d and 1004f-1004i that illustrate various data readings taken by traffic sensor 123 between 10:25 AM and 10:40 AM on two separate days (in this example, 08/13/06 and 08/14/06).

Each illustrated data read 1004a-1004y includes a data read value 1002b that includes traffic flow information observed or otherwise obtained by the data sensor. Such traffic flow information may include the speed of one or more vehicles traveling in, near or over a traffic sensor. For example, data readings 1004a-1004d show from observed traffic sensor 123, at four different times, vehicle speeds of 34 miles per hour (mph), 36 mph, 42 mph, and 38 mph, respectively. In addition, the traffic flow information may include totals or increments of vehicles traveling in, near or over a traffic sensor, either instead of or in addition to speed and / or other information. Total counts can be a cumulative count of vehicles observed by a traffic sensor since the sensor was installed or was otherwise activated. The incremental counts can be a cumulative count of vehicles observed by a traffic sensor since the sensor took a previous reading. The 1004w1004x data readings show that traffic sensor 166 counted, at two different times, 316 cars and 389 cars, respectively. In some cases, the logged data readings may not include data reading values, such as when a given traffic sensor has experienced sensor malfunction, such that it cannot make or record an observation or report an observation ( for example, due to a network failure). For example, the 1004k data reading shows that the traffic sensor 129 was not able to provide a data reading value at 10:25 AM on the 8/13/06 day, as indicated by a in the column 1002b of data read values.

In addition, a traffic sensor status 1002d may be associated with at least some data reads, as if a corresponding traffic sensor and / or communications network provided an indication of the functional status of the traffic sensor. Functional states can include indications that a sensor is working properly (for example, OK), that a sensor is in an off state (for example OFF), that a sensor is stuck reporting a single value (for example, STUCK), and / or that a communications link to the network is down (eg COM_DOWN), as illustrated by data readings 1004m, 1004k, 1004th, and 1004, respectively. In other cases, additional and / or different information related to the functional status of a traffic sensor may be provided, or such functional status information may not be available. Other traffic sensors, such as traffic sensors 123 and 166 in this example, are not configured to provide traffic sensor status indications, as indicated by a - in traffic sensor status column 1002d.

Rows 1004e, 1004j, 1004n, 1004q, 1004v and 1004y and column 1002e indicate that additional readings of traffic sensor data may be recorded in some cases and / or that additional information may be provided and / or recorded as part of each reading of data. Likewise, less information than is shown can be used as a basis for the techniques described herein.

ES 2 373 336 T3

Figure 10B illustrates examples of detection errors in traffic sensor data readings that may be indicative of poorly functioning traffic sensors. In particular, as many traffic sensors cannot provide an indication of the status of the traffic sensor, and as in some cases such indications of traffic sensor status may be unreliable (for example, indicating that a sensor is not working properly when in in fact it does, or indicating that a sensor is working properly when in fact it does not), It may be desirable to use statistical and / or other techniques to detect unhealthy traffic sensors based on the reported data from stock readings.

For example, an unhealthy traffic sensor can be detected by comparing a current distribution of data readings reported by a given traffic sensor over a period of time (for example, between 4:00 PM and 7:29 PM) on a particular day. with a historical distribution of data readings reported by the traffic sensor during the same time period in multiple past days (for example, the past 120 days). Such distributors can be generated, for example, by processing multiple readings of data obtained from a traffic sensor, such as those shown in Figure 10A.

Figure 10B shows three histograms 1020, 1030, and 1040 each representing a distribution of data readings based on data readings obtained from traffic sensor 123 over a time period of interest. The data represented in the 1020, 1030, and 1040 histograms are separated into 5 mile-per-hour intervals (for example, 0 to 4 miles per hour, 5 to 9 miles per hour, 10 to 14 miles per hour, etc. ) and are normalized such that each bar (for example, bar 1024) represents a probability between 0 and 1 that vehicle speeds within the 5 mph range for that bar occurred during the time period ( for instance, based on a percentage of data reads during the period of time that it is inside the cube). For example, bar 1024 indicates that vehicle speeds between 50 and 54 miles per hour were observed by traffic sensor 123 with a probability of approximately 0.23, such as based on approximately 23% of the data readings obtained. from traffic sensor 123 that had reported speeds between 50 and 54 miles per hour, inclusive. In other cases, one or more other fan sizes may be used, either in addition to or instead of a 5 mph fan. For example, a fan of 1 mph can provide a finer level of processing detail, but can also cause high variability between adjacent fans if not enough data readings are available for the time period, whereas a fan of 10 mph it would provide less variability but also less detail. Furthermore, while the current example uses average speed as the measure for analysis and comparison of data readings, one or more other measures can be used, either instead of or in addition to average speed. For example, traffic volume and / or occupancy can be used in a similar way.

In this example, histogram 1020 represents a historical distribution of data readings taken by traffic sensor 123 between 9:00 AM and 12:29 PM on Mondays for the last 120 days. Histogram 1030 represents a distribution of data readings taken by sensor 123 between 9:00 AM and 12:29 on a particular Monday when traffic sensor 123 was functioning properly. It can be visibly discerned that the shape of histogram 1030 resembles histogram 1020, given those traffic patterns on a particular Monday would be expected to be similar to traffic patterns on Mondays in general, and the degree of similarity can be calculated in several ways, as discussed later. Histogram 1040 represents a distribution of data readings taken by sensor 123 between 9:00 AM and 12:29 on a particular Monday when traffic sensor 123 was malfunctioning, and was instead sending data readings that did not reflect the actual flow of traffic. The shape of histogram 1040 differs markedly from that of histogram 1020, as is visibly discernible, reflecting erroneous data readings reported by traffic sensor 123. For example, a large peak in the distribution is visible at bar 1048, which may be indicative that sensor 123 was stuck for at least part of the time between 9:00 AM and 12:30 PM and reported a substantial number. identical reads that did not reflect true traffic flows.

In some cases, the Kullback-Leibler divergence between two distributions of traffic sensor data can be used to determine the similarity between the two distributions, although the similarities or differences between distributions can be calculated in other ways. The Kullback-Leibler divergence is a convex measure of the similarity of two probability distributions P and Q. It can be expressed as follows,

<img file="ES2373336T3_D0007.tif" />

Where Pi and Qi are values ​​of the separate probability distributions P and Q (For example, each Pi and Qi is the probability that the velocities will occur within the ith fan). In the illustrated example, the 1036 Kullback-Leibler (DKL) divergence between the data read distribution shown in histogram 1020 and the data read distribution shown in histogram 1030 for the healthy traffic sensor is approximately 0.076, whereas the Kullback-Leibler 1046 divergence between the distribution of data readings shown in histogram 1020 and the distribution of data readings shown in histogram 1040 for the unhealthy traffic sensor is approximately 0.568. As might be expected, the DKL 1036 is significantly smaller than the DKL 1046 (in this case, about 13% of the DKL 1046), reflecting the fact that the histogram 1030 (for example, representing the output of the traffic sensor 123 while working properly) is more similar

ES 2 373 336 T3 to histogram 1020 (for example, representing the average behavior of traffic sensor 123) that histogram 1040 (for example, representing sensor traffic 123 while failing) is similar to histogram 1020.

In addition, some cases may use other statistical measures to detect erroneous readings of data provided by traffic sensors, such as statistical entropy of information, either instead of or in addition to a similarity measure such as Kullback-Leibler divergence. The statistical entropy of a probability distribution is a measure of the diversity of the probability distribution. The statistical entropy of a probability distribution P can be expressed as follows,

<img file="ES2373336T3_D0008.tif" />

Where Pi is a value of the separate probability distributions P (For example, each Pi is the probability that the velocities occur within the ith fan of the histogram for P). In the illustrated example, the 1022 statistical entropy of the distribution shown in histogram 1020 is approximately 2.17, the 1032 statistical entropy of the distribution shown in histogram 1030 is approximately 2.14, and the 1042 statistical entropy of the distribution shown in the histogram 1040 is approximately 2.22. As might be expected, the 1042 statistical entropy is greater than the 1032 statistical entropy and the 1022 statistical entropy, reflecting the more chaotic output pattern exhibited by traffic sensor 123 while failing.

Furthermore, the difference between two statistical entropy measures can be measured by calculating the entropy difference measure. The measure of the entropy difference between two probability distributions P and Q can be expressed as

<img file="ES2373336T3_D0009.tif" />

where H (P) and H (Q) are the entropies of the probability distributions P and Q, respectively, as described above. In the illustrated example, the measurement (Em) 1034 of entropy difference between the distribution shown in the histogram 1020 and the distribution shown in the histogram 1030 is approximately 0.0010, and the measurement 1044 of the entropy difference between the distribution shown in histogram 1020 and the distribution shown in histogram 1040 is approximately 0023. As might be expected, the 1044 measure of entropy difference is significantly larger than the 1034 measure of entropy difference (in this case, more than twice as large), reflecting the larger difference between the statistical entropy of the distribution shown in the histogram 1040 and the statistical entropy of the distribution shown in the histogram 1020, compared to the difference between the statistical entropy of the distribution shown in histogram 1030 and the statistical entropy of the distribution shown in histogram 1020.

The statistical measurements described above can be used in a number of ways to detect unhealthy traffic sensors. In some cases, various information about a current distribution of data readings is provided as input to a sensor health classifier (or data read reliability), such as based on a neural network, Bayesian classifier, decision tree, etc. For example, the input information to the classifier may include, for example, the Kullback-Leibler divergence between a distribution of historical data readings for the traffic sensor and the current data reading distribution for the traffic sensor, and the Statistical entropy of the distribution of current data reads. The classifier then evaluates the health of the traffic sensor based on the inputs provided, and provides an output that indicates a healthy or unhealthy sensor. In some cases, additional information may also be provided as input to the classifier, such as an indication of the time of day (for example, a time period from 5:00 AM to 9:00 AM), day or weekdays (for example , Monday through Thursday, Friday, Saturday or Sunday) corresponding to the time of day and / or day of the week to which the distributions of historical data readings, the size of the mph fans, etc. Classifiers can be trained using true pre-reads of data, such as those that include traffic sensor status indications, as illustrated in Figure 10A.

In other cases, unhealthy traffic sensors can be identified without the use of a classifier. For example, a traffic sensor can be determined to be unhealthy if one or more statistical measurements are above a predetermined threshold value. For example, a traffic sensor can be determined to be unhealthy if the Kullback-Leibler divergence between a distribution of historical data readings for the traffic sensor and a distribution of current data readings for the traffic sensor is above of a first threshold value, if the statistical entropy of the current data read distribution is above a second threshold value and / or if the entropy difference measure between the current data read distribution and the historical data read distribution is above of a third threshold. In addition, other non-statistical information can be used, such as whether the traffic sensor is reporting a sensor status that can be interpreted as healthy or unhealthy.

As noted above, although the above techniques are primarily described in the context of traffic sensors reporting vehicle speed information, the same techniques can be used with respect to other traffic flow information, including volume, density, and traffic flow. traffic occupation.

ES 2 373 336 T3

Figure 3 is a block diagram illustrating one embodiment of a computing system 300 that is suitable for performing at least some of the techniques described, such as running one embodiment of a Data Sample Manager system. The computing system 300 includes a central processing unit (CPU) 335, various input-output (I / O) components 305, a storage 340, and a memory 345, with the I / O components illustrated including a display 310, a network connection 315, a computer-readable media unit 320, and other I / O devices 330 (eg, keyboards, mice or other pointing devices, microphones, speakers, etc.).

In the illustrated embodiment, various systems are run in memory 345 in order to perform at least some of the techniques described, including a Data Sample Manager system 350, a Predictive Traffic Information Provider system 360, a system 361 Key Roads Identifier, a 362 Road Segment Determinant system, a 363 RT Information Provider system and other optional systems provided by 369 programs, with these various execution systems generally referred to in this specification as traffic information systems. The computing system 300 and its execution systems can communicate with other computing systems through a network 380 (eg, the internet, one or more mobile phone networks, etc.), such as various client devices 382, ​​sources 384 data and / or customers based on vehicles, 386 road traffic sensors, other 388 data sources and third-party calculation systems 390.

In particular, the Data Sample Manager system 350 obtains various information regarding current traffic conditions and / or data observed from previous cases from various sources, such as road traffic sensors 386, mobile data sources 384 based on vehicles and / or other mobile or non-mobile 388 data sources. The Data Sample Manager 350 system then prepares the obtained data for use by other components and / or systems by filtering (for example, removing some data samples from consideration) and / or conditioning (for example, correcting errors) of the data, and then evaluates road traffic conditions such as traffic flow and / or speed for various road segments using the prepared data. In this illustrated embodiment, the Data Sample Manager system 350 includes a Data Sample Filter component 352, a Sensor Data Conditioner component 353, a Data Sample Outlier Remover component 354, a Speed ​​Evaluator component 356. of Data Samples; a 358 Data Sample Flow Evaluator component and an optional 355 Sensor Data Totalizer component, with components 352-358 performing similar functions as described above for the corresponding components of Figure 1 (such as component 104 Sensor Data Filter). Data Samples component 105 Sensor Data Conditioner component 106 Data Sample Outlier Remover, Data Sample Rate Evaluator component 107, Data Sample Flow Evaluator component 108 and optional Sensor Data Totalizer component 110). Furthermore, in at least some embodiments the Data Sample Manager system performs its assessment of road traffic conditions substantially in real time or near real time, such as within minutes after obtaining the essential data (which can be obtained in a substantially real-time manner from the data sources).

The other third party traffic information systems 360-363 and 369 and / or calculation systems 390 can then use the data provided by the Data Sample Manager system in various ways. For example, the 360 ​​Predictive Traffic Information Provider system can obtain (either directly or indirectly through a storage device or database) prepared data to generate future predictions of traffic conditions for multiple future times, and provide the information predicted to one or more other recipients, such as one or more other traffic information systems, client devices 382, 384 customers based on vehicle and / or third party calculation systems 390. In addition, the RT Information Provider system 363 may obtain information about the evaluated road traffic conditions from the Data Sample Manager system and makes the road traffic condition information available to others (e.g., customer devices 382, 384 customers based on vehicles and / or third-party calculation systems 390) in a real-time or close-to-real-time manner - when the Data Sample Manager system also performs its evaluation in such a way in real time or close to in real time, Recipients of the RT Information Provider system data may be able to view and use information about current traffic conditions on one or more road segments based on the true contemporary movement of vehicles on those road segments (depending on what is happening). reported by mobile data sources traveling over those road segments and / or by sensors and other data sources that provide information about travel vehicle on those road segments).

Client devices 382 can take various forms and can generally include any communication device and other computing devices capable of making requests to and / or receiving information from traffic information systems. Sometimes client devices may run interactive console applications (for example, internet browsers) that users can use to make requests for traffic-related information (for example, predicted information on future traffic conditions, information on current conditions real-time or near real-time traffic, etc.), while in other cases at least some traffic-related information can be automatically sent to client devices (for example,

ES 2 373 336 T3 such as text messages, new web pages, data updates from specialized programs, etc.) from one or more of the traffic information systems.

Highway traffic sensors 386 include multiple sensors that are installed on or near various streets, expressways, or other highways, such as for one or more geographic areas. These sensors can include loop sensors that are capable of measuring the number of vehicles passing over the sensor per unit time, vehicle speed, and / or other data related to traffic flow. In addition, such sensors can include cameras, motion sensors, radar locating devices, RFID-based devices, and other types of sensors that are located adjacent to, or otherwise close to, a road. Highway traffic sensors 386 can periodically or continuously provide measured data readings over wired or wireless data links to Data Sample Manager 350 over network 380 using one or more data exchange mechanisms. data (for example, push, pull, polling, request-response, peer-to-peer, etc.). Also, while not illustrated here, one or more totalizers of such road traffic sensor information (eg, a government transportation agency that operates the sensors) may instead obtain the raw data and make it the data is available to traffic information systems (either in raw form or after it is processed).

The other 388 data sources include a variety of types of other data sources that may be used by one or more of the traffic information systems to provide traffic-related information to users, customers, and / or other systems. calculation. Such data sources may include map services and / or databases that provide information regarding road networks such as connectivity between roads as well as traffic control information related to such roads (for example, the existence and / or the position of traffic control signs and / or speed zones). Other data sources may also include sources of information about events and / or conditions that impact and / or reflect traffic conditions, such as short-term and long-term weather forecasts, school schedules and / or calendars, schedules and / or o event calendars, traffic incident reports provided by human operators (e.g. first aid, law enforcement personnel, highway personnel, news media, travelers, etc.), information on road works, holiday schedules, etc.

The vehicle-based customer / data sources 384 in this example may each be a computing system and / or communication system located within a vehicle that provides data to one or more traffic information systems and / or receives data from one or more of those systems. In some cases, the Data Sample Manager 350 system may utilize a distributed network of mobile vehicle-based data sources and / or other mobile user-based data sources (not shown) that provide information related to conditions. current traffic information for use by traffic information systems. For example, each vehicle or other mobile data source may have a GPS (Global Location System) device (eg, a mobile phone with GPS capabilities, a standalone GPS device, etc.) and / or other capable geolocation device. to determine the geographical position and possibly other information such as speed, direction, height and / or other data related to the movement of the vehicle, with geolocation devices or other non-communication devices obtaining and providing such data to one or more of the traffic information systems (eg, via a wireless connection) from time to time. Such mobile data sources are discussed in greater detail elsewhere.

Alternatively, some or all of the vehicle-based customer / data sources 384 may have a computing system and / or communication system located within a vehicle to obtain information from one or more of the traffic information systems, such as as for use by an occupant of the vehicle. For example, the vehicle may contain a console navigation system with an installed Internet browser or other console application that a user can use to make requests for traffic-related information over a wireless connection from one of the vehicle's systems. traffic information, such as the Predictive Traffic Information Provider system and / or the RT Information Provider system, or instead such requests can be made from a wearable device of a user in the Vehicle. Furthermore, one or more of the traffic information systems may automatically transmit traffic related information to the vehicle-based client device based on the receipt or generation of updated information.

Third-party computing systems 390 include one or more optional computing systems that are handled by parties other than the operators of the traffic information systems, such as parties receiving traffic-related data from one or more of traffic information systems and that use the data in some way. For example, third-party computing systems 390 may be systems that receive traffic information from one or more of the traffic information systems, and that provide related information (either the information received or other information based on the information received). to users or others (for example, through subscription services or web portals). Alternatively, third-party calculation systems 390 may be operated by other types of parties, such as media organizations that gather and report traffic conditions to their consumers, or online mapping companies that provide traffic-related information. to its users as part of a trip planning services.

As indicated above, the 360 ​​Predictive Traffic Information Provider system can use the data prepared by the 350 Data Sample Manager system and other components to generate future

ES 2 373 336 T3 traffic condition predictions for future multiple times. In some cases, predictions are generated using probability techniques that incorporate various types of input data to repeatedly produce future predictions in time series for each of numerous road segments, such as in a real-time manner based on current conditions. changes for a road network in a given geographical area. In addition, one or more Bayesian or other predictive models (for example, decision trees) can be automatically created for use in generating future traffic condition predictions for each geographic area of ​​interest, such as based on observed historical conditions of traffic for those geographic areas. Future predicted traffic condition information can be used in a variety of ways to aid travel or other purposes, such as planning optimal routes through a road network based on predictions about traffic conditions for the roads at multiple future times.

In addition, the Road Segment Determinant system 362 may utilize map services and / or databases that provide information regarding road networks in one or more geographic areas to automatically determine and manage road-related information that may be used by other traffic information systems. Such road-related information may include determinations of particular parts of roads to be treated as road segments of interest (for example, based on traffic conditions of those parts of roads and other nearby parts of road), as well as associations or relationships generated. automatically between segments of in a given road network and indications of other information of interest (for example, physical locations of road traffic sensors, event presentation venues and geographic signs; information about road functional classes and other traffic-related characteristics; etc.). In some cases, the Highway Segment Determinant system 362 may periodically execute and store the information it produces in storage 340 or in a database (not shown) for use by other traffic information systems.

In addition, the 361 Key Road Identifier system uses a road network representing a given geographic area and Traffic Conditions information for that geographic area to automatically identify the roads that are of interest for tracking and evaluating road traffic conditions. , such as to be used by other traffic information systems and / or traffic data clients. In some cases, the automatic identification of a road (or one or more road segments) as being of interest may be based at least in part on factors such as the magnitude of maximum traffic volume or other flow, the magnitude of maximum traffic congestion, inter-day variability of traffic volume or other flow, inter-day variability of road congestion, the inter-day variability of traffic volume or other flow and / or inter-day variability of road congestion. Such factors can be analyzed by, for example, principal component analysis, such as first calculating a covariance matrix S of traffic condition information for all roads (or road segments) in a given geographic area, and then calculating a Eigen decomposition of the covariance matrix S. In decreasing order of Eigenvalue, the Eigenvectors of S then represent the combinations of roads (or road segments) that independently contribute most strongly to the variance of observed traffic conditions.

In addition, a real-time traffic information provider or display system may be provided by an RT Information Provider system, or instead by one or more of the other programs 369. The information provider system may use data analyzed and provided by the Data Sample Manager 350 system and / or other components (such as the 360 ​​Predictive Traffic Information Provider system) in order to provide traffic information services to consumers. and / or business entities that manage or otherwise use 382 client devices, 384 vehicle-based clients, third-party calculation systems 390, etc., such as providing data in a real-time or near-real-time manner based at least in part on data samples obtained from vehicles and other mobile data sources.

It will be appreciated that the illustrated calculation systems are illustrative only and are not intended to limit the scope of the present invention. Calculation system 300 can be connected to other devices not illustrated, including over one or more networks such as the Internet or through the Web. More generally, a client or server computing device or system, or traffic information system and / or component, may comprise any combination of hardware or software that can interact and perform the described types of functionality, including without limitation desktop computers or others, database servers, network storage devices and other network devices, PDAs, mobile phones, cordless phones, pagers, electronic organizers, Internet appliances, television-based systems (eg, using overhead boxes and / or personal / digital video recorders), and various other consumer products that include appropriate intercom capabilities. In addition, the functionality provided by the illustrated system components can be combined into fewer components or distributed into additional components. Similarly, the functionality of some of the illustrated components may not be provided and / or additional functionality may be available.

Also, while various items are illustrated as being stored in memory or in storage while in use, these items or parts of them can be transferred between memory and other devices.

ES 2 373 336 T3 storage for memory management and / or data integrity purposes. Alternatively, some or all of the software components and / or modules may run in memory on another device and communicate with the illustrated computing system via computer-to-computer communication. Some or all of the system components or data structures may also be stored (for example, as software instructions or structured data) on a computer-readable medium, such as a hard drive, memory, network, or portable media item. to be read by an appropriate unit or through an appropriate connection. System components and data structures can also be transmitted as generated data signals (for example, as part of a carrier wave or other propagated analog or digital signal) on a variety of computer-readable transmission media, including wireless media. and wired, and can take various forms (eg, as part of a single or multiplexed analog signal, or as multiple packets or discrete digital frames). Such computer program products may also take other forms in other cases. Accordingly, the present invention can be practiced with other computer system configurations.

FIG. 4 is a flow chart of an exemplary embodiment of a Data Sample Filter routine 400 related to the present invention. The routine may be provided, for example, by executing an embodiment of a Data Sample Filter component 352 of Figure 3 and / or the Data Sample Filter component 104 of Figure 1, such as to receive data samples. data for roads in a geographic area and to filter out data samples that are not relevant for subsequent evaluations. The filtered data samples can then be used subsequently in various ways, such as to use the filtered data samples to calculate average speeds for particular road segments of interest and to calculate other characteristics related to traffic flow for such road segments. .

The routine begins at step 405, where a group of data samples is received for a geographic area for a particular time period. At step 410, the routine then optionally generates additional information for some or all of the data samples based on other related data samples. For example, if a particular sample of data for a vehicle or other mobile data source lacks information of interest (such as speed and / or heading or orientation for the mobile data source), such information can be determined in conjunction with one or both previous and subsequent data samples for the same mobile data source. Furthermore, in at least some embodiments the information from multiple data samples for a particular mobile data source may be totalized in order to evaluate additional types of information regarding the data source, such as to evaluate an activity of the data source. data source over a period of time spanning multiple data samples (for example, to determine if a vehicle has been parked for several minutes rather than temporarily stopping for a minute or two as part of the normal flow of traffic, such as at a stop sign or stop light).

After step 410, the routine continues with step 415 to attempt to associate each data sample with a road in the geographic area and a particular road segment of that road, although in other embodiments this step may not or may not be performed. other ways, such as if at least an initial association of a data sample with a road and / or road segment is received instead at step 405, or instead if the entire routine is performed at once for a single road segment in such a way that all the data samples received in step 405 as a group correspond to a single road segment. In the illustrated embodiment, associating a data sample with a road and road segment can be done in various ways, such as making an initial association based solely on a geographic position associated with the data sample (e.g., to associate the data display with the nearest road and road segment). In addition, the association can optionally include additional analysis to refine or revise that initial association - for example, if a position-based analysis indicates multiple possible road segments for a data sample (such as multiple road segments for a particular road). , or instead multiple road segments for nearby but otherwise related roads), Such additional analysis may use other information such as speed and orientation to effect the association (eg, combining the position information and one or more of such factors in a weighted manner). Thus, for example, if the reported position of a data sample is between a highway and a nearby service road, the information about the reported speed from the data sample can be used to assist in the association of the data sample. data with the appropriate road (for example, determining that a data sample with an associated speed of 70 miles per hour is unlikely to originate from a service road with a speed limit of 25 miles per hour). Also, in situations where a particular stretch of road or other part of the road is associated with multiple distinct road segments (for example, for a two-lane road where the one-way travel is modeled as a first segment of road and in which the displacement in the other direction is modeled as a second distinct segment of road, or instead a multi-lane highway in which an HOV lane is modeled as a separate road segment from the one or more adjacent non-HOV lanes), additional information about the data sample can be used such as speed and / or orientation to select the most likely road segment of the road for the data sample.

After step 415, the routine continues to step 420 to filter out any data samples that are not associated with road segments that are of interest for further processing, including data samples (if any) that are not associated with no road segment. For example, certain roads

ES 2 373 336 T3 or parts of roads may not be of interest for further analysis, such as excluding roads from certain functional road classes (for example, if the size of the road and / or its amount of traffic is not sufficiently large enough to be of interest), or exclude parts of roads such as a freeway ramp, secondary road or distribution road since the traffic characteristics of such parts of the road are not a reflection of the motorway as a whole. Similarly, in situations where multiple road segments are associated with a particular part of the road, some road segments may not be of interest for some purposes, such as excluding an HOV lane for a freeway if it is only of interest. the behavior of non-HOV lanes for a particular purpose, or if only one direction of a two-way highway is of interest. After step 420, the routine continues to step 425 to determine whether to filter the data samples based on the activity of the data sources, although in other embodiments such filtering may not or may always be done. In the illustrated embodiment, if filtering is to be performed based on source activity, the routine continues to step 430 to perform such filtering, such as removing data samples that correspond to data sources whose behavior does not reflect the activity of the traffic flow of interest to be measured (for example, to exclude vehicles that are parked with their engines running for an extended period of time, to exclude vehicles that are being driven around a parking lot, garage or other small area for an extended period of time, etc.). After step 430, or if instead it is determined in step 425 that it is not to be filtered based on the activity of the data source, the routine continues to step 490 to store the filtered data for later use, although in other embodiments the filtered data may instead be provided directly to one or more clients. The routine then continues to step 495 to determine whether to continue. If that is the case, the routine returns to step 405, and if not continues to step 499 and ends.

FIG. 5 is a flow diagram of an exemplary embodiment of a Data Sample Outlier Remover routine 500 related to the present invention. The routine may be provided, for example, by executing one embodiment of a Data Sample Outlier Remover component 354 of Figure 3 and / or the Data Sample Outlier Remover component 106 of Figure 1, such as to remove data samples for a road segment that are outliers with respect to the data samples for the road segment.

The routine begins at step 505, where a set of data samples is received for a road segment and a period of time. The received samples of data can be, for example, filtered samples of data obtained from the output of the Data Sample Filter routine. At step 510, the routine then optionally separates the data samples into multiple groups to reflect different parts of the road segment and / or different behaviors. For example, if multiple expressway lanes are included together as part of a single highway segment and the multiple lanes include at least one HOV lane and one or more non-HOV lanes, vehicles in the HOV lanes may be separated from the vehicles in the other lanes if the traffic flow during the time period is significantly different between the HOV and non-HOV lanes. Such grouping can be done in a number of ways, such as by filtering the data samples with multiple curves each representing the normal variability of data samples within a particular group of data samples (eg, a normal or Gaussian curve). In other embodiments, such clustering may not be performed, such as if the highway segment is divided instead in such a way that all data samples for the highway segment reflect similar behavior (for example, if a highway with a HOV lane and other non-HOV lanes are instead divided into multiple road segments).

The routine then continues to step 515, for each of the one or more groups of data samples (with all data samples being treated as a single group if separation of the data sample from step 510 is not performed) , to calculate mean characteristics of traffic conditions for all data samples. Such average characteristics of traffic conditions may include, for example, an average speed, as well as corresponding statistical information such as a standard deviation from the average. The routine then continues to step 520, for each of the one or more groups of data samples, to successively perform an analysis leaving one out such that a particular target data sample is selected to be provisionally left out and determined. the average characteristics of traffic conditions for the remaining characteristics of traffic conditions. The larger the difference between the mean traffic condition characteristics for the remaining data samples and the mean traffic condition characteristics for all the data samples from step 515, the greater the probability that the target data samples from Target left out are outliers that do not reflect the common characteristics of the remaining data samples. At step 525, the routine then optionally performs one or more additional types of outlier analysis, such as successively leaving out groups of two or more target data samples in order to evaluate their binding effect, although in some embodiments such Additional analysis of outliers may not be performed. After step 522, the routine continues to step 590 to remove the data samples that are identified as outliers in steps 520 and / or 525, and store the remaining data samples for later use. In other embodiments, the routine may instead send the remaining data samples to one or more clients for use. The routine then continues to step 595 to determine whether to continue. If that is the case, the routine returns to step 505, and if not the routine continues to step 599 and ends.

ES 2 373 336 T3

FIG. 6 is a flow chart of an exemplary embodiment of a Data Sample Rate Evaluator routine 600 related to the present invention. The routine may be provided, for example, by executing a Data Sample Rate Evaluator component 356 of Figure 3 and / or the Data Sample Rate Evaluator component 107 of Figure 1, such as to evaluate the Current speed for a road segment over a period of time based on multiple data samples for the road segment. In this exemplary embodiment, the routine will perform successive calculations of the average speed for the road segment for each of multiple time intervals during the time period, although in other embodiments each invocation of the routine may instead be for a single timeslot (for example, with multiple timeslots evaluated through multiple invocations of the routine). For example, if the time period is thirty minutes, a new average speed calculation can be performed every five minutes, such as with 5-minute time intervals (and so on with each time interval that does not overlap with time intervals previous or successive intervals), nor with time intervals of 10 minutes (and thus overlap with adjacent time intervals).

The routine begins at step 605, where an indication of data samples (e.g., data samples from mobile data sources and physical readings of sensor data) is received for a road segment for a period of time, or from Insufficient data for a road segment for a period of time, although in some embodiments only one of the data samples may be received from mobile data sources and sensor data readings. The received samples of data can be obtained, for example, from the output of the Data Sample Outlier Remover routine. Similarly, the indication of insufficient data may be received from the Data Sample Outlier Remover routine. In some cases, the indication of insufficient data may be based on having an insufficient number of data samples, such as when there are no data samples from mobile data sources associated with the road segment for the time period and / or when some or all sensor data readings for the road segment are lost or found to be in error (for example, by component 105 Sensor Data Conditioner of Figure 1). In this example, the routine continues to step 610 to determine if an insufficient data indication has been received. If that is the case, the routine continues to step 615, and if not the routine continues to step 625.

At step 615, the routine executes one embodiment of the Traffic Flow Evaluator routine (described with reference to Figure 14) in order to obtain the estimated average traffic speed for the road segment for the time period. At step 620, the routine then provides an indication of the estimated average speed. In step 625, the routine selects the next time slot for which an average speed is to be evaluated, starting with the first time slot. At step 630, the routine then calculates a weighted average traffic rate for the data samples within the time interval, the weight of the data samples based on one or more factors. For example, in the illustrated embodiment, the weight for each data sample is varied (e.g., in a linear, exponential, or stepped manner) based on the latency of the data sample, such as to give more weight to sample data. data near the end of the time interval (as it may more reflect the true average speed at the end of the time interval). In addition, data samples can be given more weight in the illustrated embodiment based on the source of the data, such as weighting data readings from physical sensors differently from data samples from vehicles and other mobile data sources. , either give more or less weight. In addition, in other embodiments, various other factors may be used in weighting, including on a sample basis - for example, a data reading from one physical sensor may receive a different weight than a data reading from another physical sensor, such as to reflect available information about the sensors (for example, that one of the physical sensors is intermittently faulty or has a less accurate data reading resolution than another sensor), and a data sample from one vehicle or other mobile data source may be weighted differently from another vehicle or mobile data source based on information about the mobile data sources. Other types of factors that may be used in weighting in some embodiments include confidence values ​​or other estimates of the possible error in a particular sample of data, a degree of confidence that a particular sample of data should be associated with a particular road segment, etc. .

After step 630, the routine continues to step 635 to provide an indication of the calculated average traffic speed for the time interval, such as to store the information for later use and / or to provide the information to a customer. . At step 640, the routine then optionally obtains additional data samples for the period of time that has become available following receipt of information at step 605. It is then determined in step 645 whether more time slots are to be calculated for the time period, and if that is the case the routine returns to step 625. If instead there are no more time slots, or after the In step 620, the routine continues to step 695 to determine whether to continue. If that is the case, the routine returns to step 605, and if not continues to step 699 and ends.

FIG. 7 is a flow diagram of an exemplary embodiment of a Data Sample Flow Evaluator routine 700 related to the present invention. The routine may be provided, for example, by executing one embodiment of a Data Sample Flow Evaluator component 358 of Figure 3 and / or the Data Sample Flow Evaluator component 108 of Figure 1, such as evaluate characteristics of traffic flow conditions other than average speed for a particular road segment during a particular period of time. In this exemplary embodiment, the flow characteristics to be evaluated include a total volume of vehicles (or other mobile data sources) that arrive at, or are present in, a segment.

ES 2 373 336 T3 particular road during a period of time, and a percentage occupancy for the road segment during the time period to reflect the percentage of time that a point or area of ​​the road segment is covered by a vehicle.

The routine begins at step 705, where an indication of data samples is received for a road segment over a period of time and an average speed for the road segment during the time period, or insufficient data for a road segment. road for a period of time. The data samples can be obtained from, for example, the output of the Data Sample Outlier Remover routine and the average speed can be obtained from, for example, the output of the Data Sample Rate Evaluator routine. The indication of insufficient data may be obtained from, for example, the output of the Data Sample Outlier Remover routine. In some cases, the indication of insufficient data may be based on having an insufficient number of data samples, such as when there are no data samples from mobile data sources associated with the road segment for the time period and / or when some or all sensor data readings for the road segment are lost or found to be in error (for example, by component 105 Sensor Data Conditioner of Figure 1). The routine then continues to step 706 to determine if an insufficient data indication has been received. If that is the case, the routine continues to step 750, and if not the routine continues to step 710.

At step 750, the routine executes a run of the Traffic Flow Estimator routine (described with reference to Figure 14) in order to obtain the estimated total traffic volume and occupancy for the highway segment during the period of time. At step 755, the routine then provides an indication of the estimated total volume and occupancy.

In step 710, the routine determines various vehicles (or other mobile data sources) that provided the data samples, such as associating each data sample with a particular mobile data source. At step 720, the routine then determines by probabilities the most likely arrival rate on the highway segment of the vehicles providing the data samples, based in part on the determined number of vehicles. In some embodiments, the probability-based determination may further utilize usage information about the prior probability of the number of such vehicles and the prior probability of a particular arrival rate. In step 730, the routine then infers the total volume of all vehicles passing through the road segment during the time period, such as based on the determined number of vehicles and information about what percentage of the total number of vehicles They are vehicles that provide data samples and also evaluate a confidence interval for the inferred total volume. At step 740, the routine then infers the percentage occupancy for the road segment over the time period based on the inferred total volume, average speed, and an average vehicle length. Other types of traffic flow characteristics of interest can be similarly evaluated in other embodiments. In the illustrated embodiment, the routine then continues to step 790 to provide indications of the inferred total volume and the inferred percentage occupancy. After steps 755 or 790, if then it is determined at step 795 to continue; the routine returns to step 705, and if it does not continue to step 799 and ends.

FIG. 11 is a flow chart of an exemplary embodiment of a Sensor Data Read Error Detector routine 1100 related to the present invention. The routine may be provided, for example, by executing component 353 Sensor Data Conditioner of Figure 3 and / or component 105 Sensor Data Conditioner of Figure 1, such as to determine the health of one or more traffic sensors. In this exemplary embodiment, the routine is performed at various times of the day to determine the health of one or more traffic sensors, based on readings of traffic sensor data recently obtained during an indicated period of time. Furthermore, the data that is produced by a traffic sensor for one or more of the various types of traffic condition measurements can be routinely analyzed in various embodiments, such as speed, volume, traffic occupancy, etc. . In addition, the data for at least some of the traffic conditions can be measured and / or totalized in various ways, such as at various levels of detail (for example, 5 mph fans of data sets for speed information ), and the routine may in some embodiments analyze the data for a particular traffic sensor at each of one or more levels of detail (or another level of totalization) for each of one or more measures of traffic conditions.

The routine begins at step 1105 and receives an indication from one or more traffic sensors and a selected category of time (e.g., the most recent category of time, if the routine runs after each category of time to provide results in a manner close to real time, or one or more previous time categories selected for analysis), although in other embodiments multiple time categories may be indicated instead. In some embodiments, time may be modeled by time categories each including a time of day category (for example, 12:00 AM to 5:29 AM and 7:30 PM to 11:59 PM, 5:30 AM at 8:59 AM, from 9:00 AM to 12:29 PM, from 12:30 PM to 3:59 PM, from 4:00 PM to 7:29 PM, and from 12:00 AM to 11:59 PM) and / or a category of the day of the week (for example, Monday through Thursday, Friday, Saturday, and Sunday, or instead with Saturday and Sunday grouped together). Particular categories of time can be selected in various ways in various embodiments, including to reflect periods of time during which traffic is expected to have similar characteristics (for example, based on timing and calculation patterns, or other consistent activities that affect performance). traffic), such as grouping the afternoon and evening hours together

ES 2 373 336 T3 early in the morning if traffic is normally relatively light during those times. Furthermore, in some embodiments the time categories may be selected to differ between different traffic sensors (eg, by geographic area, road, individual sensor, etc.), either manually or in an automated manner by analyzing historical data to determine time periods that have similar traffic flow characteristics.

At steps 1110-1150, the routine then loops in which it analyzes traffic sensor data readings from each of one or more indicated traffic sensors for the indicated categories of time in order to determine the status of the traffic sensor. Traffic sensor health of each of the traffic sensors during that time category. At step 1110, the routine selects the next traffic sensor from the one or more indicated traffic sensors, starting with the first, and selects the indicated time category (or, if instead multiple time categories were indicated in step 1105, the next combination of traffic sensor and indicated time category). At step 1115, the routine retrieves an average historical distribution of data readings for the traffic sensor during the selected category of time. In some embodiments, the historical distribution of data readings may be based on data readings provided by the traffic sensor during the selected category of time (for example, between 4:00 PM and 7:29 PM on days of the week including Monday to Thursday) in an extended period of time, such as the last 120 days or a recent period of 120 days).

At step 1120, the routine determines a target sensor data distribution for the selected traffic sensor during the selected category of time. At step 1125, the routine then determines the similarity of the target distribution of traffic sensor data readings and the historical distribution of traffic sensor data readings. As described in more detail elsewhere, in some embodiments, such a measure of similarity can be determined by calculating the Kullback-Leibler divergence between the target distribution of traffic sensor data readings and the historical distribution of sensor data readings. of traffic. At step 1130, the routine then determines the information entropy of the target distribution of traffic sensor data readings, as discussed in greater detail elsewhere.

In step 1135, the routine then assesses the health of the selected traffic sensor for the selected time category using various information to perform a health classification (e.g., an indication of healthy or unhealthy, or a value in a health scale such as 1 to 100), which in this example includes the determined similarity, the determined entropy, and the selected category of time (for example, the selected category of time of day, such as 4:00 PM to 7:29 PM, and / or the selected category of day of the week, such as Monday through Thursday). In other embodiments, other types of information could be used, such as an indication of a degree of detail of the data being measured (eg, 5 mph fans of data sets for speed information). In one embodiment, a neuralgic network may be used for classification, while in other embodiments various other classification techniques may be used, including decision trees, Bayesian classifiers, etc.

At step 1140, the routine then determines the traffic sensor health status for the selected traffic sensor and selected time category (in this example as healthy or unhealthy) based on the evaluated traffic sensor health and / or other factors. In some embodiments, the health status for a traffic sensor can be determined to be healthy as long as the traffic sensor health for the selected category of time is evaluated as healthy in step 1135. In addition, the health status for the traffic sensor can be determined to be unhealthy as long as the traffic sensor health for the selected category of time is evaluated as unhealthy (for example, in step 1135), and the selected category Time has an associated category of time of day that spans a large enough period of time (for example, at least 12 or 24 hours). Furthermore, in some embodiments information about related time categories (for example, for one or more previous and / or subsequent time periods) can be retrieved and used, such as to classify traffic sensor health in a period. longer time (for example, one day). Such logic can reduce the risk of a false negative sensor health determination (for example, determining the traffic sensor health as unhealthy when in fact the traffic sensor is healthy) based on exceptional temporary traffic patterns. that the traffic sensor reports accurately.

For example, false negative determinations can occur due to substantial inter-day variability in data readings due to external factors (eg traffic accidents, weather incidents, etc.). An automobile accident that occurs at or near a particular traffic sensor, for example, may result in that traffic sensor providing outliers and erratic data readings for a relatively short period of time (for example, one to two hours). If a sensor health determination is based solely on data readings obtained primarily during the disturbance time caused by the traffic accident, a false negative determination will likely result. By basing the unhealthy sensor status determination on data readings obtained over relatively longer periods of time (eg, 12 or 24 hours) the risk of such false negative determinations can be reduced. On the other hand, false positive determinations (for example, determining traffic sensor health as healthy when in fact unhealthy) may be generally less likely, because failing traffic sensors are unlikely to provide data readings that are similar to historical data readings (for example, reflecting patterns of

ES 2 373 336 T3 ordinary traffic). As such, it may be appropriate to determine a traffic sensor health status as healthy based on relatively smaller time periods.

Some embodiments may perform such differential logic by executing the illustrated routine many times per day with the time category reflecting shorter periods of time (for example, executing the routine every three hours with a time category having a time of day category spanning the previous three hours) and at least once per day with a time category that reflects the entire previous day (for example, run the routine at midnight with a time category that has a time of day category that spans the previous 24 hours).

In addition, the sensor health determination may be based on other factors, such as whether a sufficient number of data readings can be obtained for the selected category of time (for example, because the traffic sensor intermittently reports data readings ) and / or based on sensor status indications provided by the traffic sensor (eg, that the traffic sensor is stuck).

At step 1145, the routine provides the determined traffic sensor health state. In some embodiments, the traffic sensor health status may be stored (for example, in a file system or database) for later use by other components (for example, the Sensor Data Totalizer component 110). Figure 1) and / or provided directly to other components (eg, a Data Sample Outlier Remover component). At step 1150, the routine determines whether more traffic sensors (or combinations of traffic sensors and time categories) need to be processed. If that is the case, the routine continues to step 1110, and if not, it continues to step 1155 and performs other actions as appropriate. Such other actions may include, for example; recalculate periodically (for example, once a day, once a week, etc.) or historical distributions of data readings (for example, for the last 120 days) for each of the one or more time categories for each of multiple traffic sensors. To periodically recalculate historical distributions of data readings, the routine can continue to provide accurate determinations of traffic sensor health status in view of gradually changing traffic conditions (for example, due to initiation or termination). of highway construction projects). After step 1155, the routine continues to step 1199 and returns.

FIG. 12 is a flow chart of an exemplary embodiment of a Sensor Data Read Error Corrector routine 1200 related to the present invention. The routine may be provided, for example, by executing component 353 Sensor Data Conditioner of Figure 3 and / or component 105 Sensor Data Conditioner of Figure 1, such as to determine corrected readings of data for one or more traffic sensors associated with a road segment. In the exemplary illustrated embodiment, this routine may be run periodically (eg, every 5 minutes) to correct data readings for traffic sensors that have been identified as unhealthy by the Sensor Data Read Error Corrector routine. In other embodiments, the routine may be run on demand, such as by the Sensor Data Totalizer routine, to obtain corrected readings of data for a particular road segment, or it may instead be unused in various circumstances. For example, data analysis and correction can be performed more generally by determining whether all data samples (for example, from multiple data sources, such as from multiple types that may include traffic sensors and one or more other types of mobile sources data) for a particular road segment provides sufficient data to analyze traffic flow conditions for that road segment, and if that is the case, do not perform any correction of individual traffic sensor data.

The routine begins at step 1205, where it receives an indication of a road segment with which one or more traffic sensors are associated (e.g., based on results from the Sensor Data Read Error Detector routine that one or more of the associated traffic sensors have been classified as unhealthy), and optionally one or more time categories to be processed (for example, time categories during which at least one of the associated traffic sensors has been classified as at least potentially unhealthy). In other embodiments, one or more traffic sensors of interest may be indicated in other ways, such as directly receiving indications from one or more traffic sensors. In steps 1210 to 1235, the routine loops in which it processes unhealthy traffic sensors on the indicated road segment to determine and provide corrected readings of data for those traffic sensors over one or more time categories (e.g. , the time categories indicated in step 1205).

At step 1210, the routine selects the next unhealthy traffic sensor on the indicated road segment, starting with the first. The routine also selects a time category to use, such as one of the one or more time categories indicated in step 1205, by selecting one of the one or more time categories during which the traffic sensor was previously designated which was unhealthy, etc. At step 1215, the routine determines if there are enough other traffic sensors on the indicated road segment that are healthy and can be used to assist in correcting the readings for the unhealthy traffic sensor for the selected category of time. This determination may be based on whether there is at least a predetermined number (eg, at least two) and / or a predetermined percentage (eg, at least 30%) of healthy traffic sensors on the indicated road segment during the selected time category, and may further consider the relative position of the healthy traffic sensors on the indicated road segment (for example,

ES 2 373 336 T3 neighboring or otherwise close traffic sensors may be preferred to traffic sensors that are further from the unhealthy traffic sensor). If it is determined in step 1215 that there are sufficient healthy traffic sensors, the routine continues to step 1220, where it determines a corrected reading of data for the unhealthy traffic sensor based on data readings from other healthy traffic sensors in the road segment for the selected time category. A corrected data reading can be determined in a number of ways, such as by averaging two or more data readings obtained from healthy traffic sensors on the indicated road segment for the selected category of time. In some embodiments, all healthy traffic sensors can be used for averaging, while in other embodiments only selected healthy traffic sensors can be used. For example, if a predetermined percentage (for example, at least 30%) of traffic sensors on the indicated road segment are healthy during the selected category of time, all healthy traffic sensors can be used on average, and otherwise only a predetermined number (eg, at least two) of the closest sound traffic sensors can be used.

If it is determined in step 1215 that there are not enough healthy traffic sensors on the indicated road segment for the selected time category, the routine continues to step 1225, where it attempts to determine a corrected reading of data for the unhealthy road sensor. based on other information related to the traffic sensor and / or the road segment. For example, such information may include predicted traffic condition information for the road segment and / or the unhealthy traffic sensor, forecast traffic condition information for the road segment and / or the unhealthy traffic sensor, and / or average historical information of traffic conditions for the road segment and / or the unhealthy traffic sensor. Various logics can be implemented to reflect the relative reliability of various types of information. For example, in some embodiments, predicted traffic condition information may be used in preference to (e.g., whenever available) forecasting traffic condition information, which in turn may be used in preference to historical average road condition information. traffic. Additional details related to the prediction and forecast of future traffic flow conditions are available in US Patent Application No. 11 / 367,463, filed March 3, 2006 and entitled Dynamic Chronological Series Prediction of Future Traffic Conditions that it is incorporated herein by reference in its entirety. In other embodiments, steps 1215 and 1225 may not be performed, such as if the correction of data readings in step 1220 is always performed based on the best data that is available from other healthy traffic sensors during the selected category of time and / or related categories of time. For example, correction of data readings can be based on all healthy traffic sensors on the indicated road segment for the selected time category if they are at least a predetermined percentage healthy (for example, at least 30%). from those traffic sensors, or otherwise at the closest sound traffic sensors on the indicated and / or near segment of highway during the selected category of time and / or related categories of time.

After steps 1220 or 1225, the routine continues to step 1230 and provides the determined readings of traffic sensor data for use as a corrected reading for the traffic sensor during the selected category of time. In some embodiments, the determined reading of traffic sensor data may be stored (for example, in a file system or database) for later use by other components (for example, Sensor Data Totalizer component 110 of the Figure 1). At step 1235, the routine determines whether additional combinations of traffic sensors and time categories need to be processed. If that is the case, the routine returns to step 1210, and if it does not continue to step 1299 and back.

Figure 13 is a flow chart of an exemplary embodiment of a Sensor Data Read Totalizer routine 1300 related to the present invention. The routine may be provided, for example, by executing the Sensor Data Totalizer component 355 of Figure 3 and / or the Sensor Data Totalizer component 110 of Figure 1, such as to determine and provide information on operating conditions. traffic for multiple traffic sensors during a particular category of time or other period of time, such as for multiple traffic sensors associated with a particular road segment. In the exemplary illustrated embodiment, the routine is performed for particular road segments, but in other embodiments it may aggregate information from other types of multiple traffic sensor groups. In addition, this routine can provide traffic condition information that is complementary to information provided by other routines that perform evaluations of traffic condition information (for example, the Data Sample Flow Evaluator routine), such as providing information traffic conditions in situations where other routines cannot provide accurate assessments (for example, due to insufficient data).

The routine begins at step 1305 and receives an indication of one or more road segments and one or more time categories or other time periods. In step 1310, the routine selects the next road segment of the one or more road segments, starting with the first. In step 1315, the routine obtains some or all of the available traffic sensor data readings taken during the time periods indicated by all traffic sensors associated with the road segment. Such information may be obtained from, for example, Sensor Data Conditioner component 105 of Figure 1 and / or Sensor Data Conditioner component 353 of Figure 1. In particular, in some cases the routine may obtain traffic sensor data readings for traffic sensors determined to be healthy and / or corrected readings of traffic sensor data for traffic sensors determined to be unhealthy, such as those provided or determined. by the Sensor Data Readout Error Corrector routine in Figure 12.

ES 2 373 336 T3

At step 1320, the routine then generates the obtained data readings in one or more of a number of ways, such as to determine the average speed, volume, and / or occupancy for the road segment during the indicated time periods. Average speed can be determined, for example, by averaging data readings reflecting the speed of vehicles passing over one or more traffic sensors. Traffic volume can be determined with reference to data readings reporting vehicle counts. For example, given a loop sensor reporting a cumulative number of vehicles passing over the sensor since the sensor was triggered, a traffic volume can be inferred simply by subtracting two data readings obtained during the indicated time period and dividing the result by the time interval between data reads. Furthermore, the density can be determined based on the determined average speed, volume and average vehicle length, as described in more detail elsewhere. In some cases, data reads can be weighted in various ways (for example, by age), such that more recent data reads have a greater impact than older data reads on a mean flow determination.

At step 1325, the routine then determines whether more road segments (or other groups of multiple traffic sensors) need to be processed. If that is the case, the routine returns to step 1310, and otherwise continues to step 1330 to provide the determined traffic flow information. In some embodiments, the determined flow information may be stored (for example, in a file system or database) for subsequent provision to clients 109 of the traffic data of Figure 1 and / or to the system 363 Provider. Information RT of Figure 3. Then, the routine continues to step 1339 and returns.

Figure 14 is a flow chart of an exemplary embodiment of a Traffic Flow Estimator routine 1400 related to the present invention. The routine may be provided, for example, by executing a Traffic Flow Estimator component (not shown), such as to estimate various types of traffic flow information for a road segment in various ways. In this example embodiment, the routine may be invoked by the Data Sample Rate Evaluator routine of Figure 6 to obtain estimates of the mean rate and / or by the Data Sample Flow Evaluator routine of Figure 7 to obtain volume and / or occupancy estimates, such as in situations where those routines are not capable of obtaining sufficient data to otherwise accurately perform their respective evaluations.

The routine begins at step 1405 and receives an indication of a road segment, one or more time categories or other time periods, and one or more types of traffic flow information, such as speed, volume, density, occupancy, etc. In step 1410, the routine determines whether to estimate the indicated type of traffic flow information based on one or more related road segments, such as based on whether such road segments have accurate information for the one or more types. of traffic flow information during the one or more indicated periods of time. Related road segments can be identified in various ways. For example, in some cases, information about road segments may include information about relationships between road segments, such as a first road segment that typically has similar traffic patterns to a second (eg, neighbor) segment of the road. road, such that traffic flow information for the second road segment can be used to estimate the traffic flow on the first road segment. In some cases, such relationships may be determined automatically, such as based on a statistical analysis of the respective traffic flow patterns on the two road segments (for example, in a manner similar to that discussed above with respect to the identifying similar data distributions for a given traffic sensor at different times, but instead analyzing the similarity between two or more different traffic sensors, such as at the same time), if an analysis was performed previously and / or dynamically. Alternatively, one or more neighboring road segments may be selected as being related to an indicated road segment without having made any determination of a particular relationship between road segments. If it is determined that traffic flow information is to be estimated based on related road segments, the routine continues to step 1415 and estimates values ​​for the indicated types of traffic flow information based on the same types of traffic flow information. traffic for the one or more related road segments. For example, the average speed of the highway segment can be determined based on the average traffic speed of one or more neighboring highway segments (for example, using the traffic speed of a neighboring highway segment or averaging the traffic speeds of two or more neighboring road segments).

If instead in step 1410 it is determined not to estimate the traffic flow information for the indicated road segment based on related road segments, the routine continues to step 1420 and determines whether to estimate the traffic flow information for the indicated segment of highway during the one or more indicated periods of time based on the information predicted for the indicated segment of highway and on indicated periods of time. In some embodiments, such predicted information may be available only under certain conditions, such as if predictions are made repeatedly for multiple future times (eg, every 15 minutes for the next three hours) while accurate current data is available. As such, if accurate input data becomes available to generate predictions for a long time (for example, for more than three hours), it may not be possible to obtain future predictions of traffic condition information that can be used by this routine. . Alternatively, in some embodiments such future predicted traffic condition information may not be available for other reasons, such as should not be used in that embodiment, if it is determined in step 1420 that traffic flow information is to be estimated.

ES 2 373 336 T3 based on the predicted information, the routine continues to step 1425 and estimates the indicated types of traffic flow information for the indicated road segment and indicated time periods based on the predicted information obtained from, for example , the 360 ​​Predictive Traffic Information Provider system of Figure 3. Additional details related to the prediction and forecast of future traffic flow conditions are available in US Patent Application No. 11 / 367,463, filed March 3, 2006 and entitled Dynamic Prediction of Time Series of Future Traffic Conditions that it is incorporated in its entirety by reference herein.

If instead in step 1420 it is determined not to estimate the traffic flow information for the indicated segment based on predicted information (for example due to information that is not available), the routine continues to step 1430 and determines if it has been of estimating traffic flow information for the indicated road segment during the one or more indicated time periods based on forecast information for the road segment and the time periods. In some embodiments, traffic conditions can be predicted for future times beyond those for which traffic conditions are predicted, such as in a way that does not use at least some current condition information. As such, if predicted information is not available (for example, because accurate input data has not been available for more than three hours to generate predictions), it may still be possible to use forecast information, such as information generated significantly in advance. . If it is determined in step 1430 that traffic flow information is to be estimated based on the forecast information, the routine continues to step 1435 and estimates the indicated types of traffic flow information for the indicated road segment and periods. based on forecast information obtained from, for example, the 360 ​​Predictive Traffic Information Provider system.

If in step 1430 it is determined instead not to estimate traffic flow information for the indicated road segment based on the forecast information (eg, because the information is not available), The routine continues to step 1440 and estimates the indicated types of traffic flow information for the indicated road segments and the time periods based on the historical average flow information for the indicated road segment (for example, for the same road segment). time period or other corresponding, such as based on time categories that include a time of day category and / or day of the week category). For example, if forecast information is not available (for example, because the input data has not been available for longer than the period for which the most recent forecast and forecast was generated, such that it cannot be generated new predictions or new forecasts), the routine can use historical average flow information for the indicated road segment. Additional details related to the generation of historical mean flow information are available in US patent application no. (Proxy File Number 480234.410P1), filed concurrently and entitled Generation of Historical Data Highway Traffic Flow Representative Information, which is incorporated in its entirety in this memorandum by reference.

After steps 1415, 1425, 1435, or 1440, the routine continues to step 1445 and provides estimated traffic flow information of the indicated types for the indicated road segment and indicated time periods. The information provided can, for example, be returned to a routine (for example, the Data Sample Flow Evaluator routine) that called the routine and / or be stored (for example, in a file system or database). data) for later use. After step 1445, the routine continues to step 1499 and returns.

Figures 9A-9C illustrate examples of actions of mobile data sources in obtaining and providing information about road traffic conditions. Information about road traffic conditions can be obtained from mobile devices (either vehicle-based devices and / or user devices) in various ways, such as being transmitted using a wireless connection (e.g., satellite uplink, the mobile phone network, WI-FI, packet radio, etc.) and / or be physically downloaded when the device reaches an appropriate station or other connection point (for example, to download information from a fleet vehicle once it has returned to its primary base of operations or other destination with the appropriate equipment to perform the information download). While the information about road traffic conditions from a first time that are obtained in a later second time provides several benefits (for example, the verification of predictions about the first time, for use as observed case data in a subsequent improvement of a prediction process, etc.), such as may be the case for information that is physically downloaded from a device, Such information on road traffic conditions provides additional benefits when obtained in a real-time or near-real-time manner. Accordingly, in at least some embodiments mobile devices with wireless communication capabilities can provide at least some acquired information about road traffic conditions on a frequent basis, such as periodically (eg, every 30 seconds, 1 minute , 5 minutes, etc.) and / or when a sufficient amount of acquired information is available (for example, for each acquisition of a data point related to the information of the road traffic conditions; for every N acquisitions of such data, such as when N is a configurable number; when the acquired data reaches a certain storage and / or transmission size; etc.). In some embodiments, such frequent wireless communications of information acquired from road traffic conditions may be further supplemented with additional information acquired from road traffic conditions at other times (for example, following a subsequent physical download from a device, via communications

Less frequent wireless ES 2 373 336 T3 containing a larger amount of data, etc.), such as including additional data corresponding to each data point, to include aggregated information about multiple data points, etc.

While several benefits are provided by obtaining information acquired from road traffic conditions from mobile devices in a real-time or other frequent manner, in some embodiments such wireless communications of information acquired from road traffic conditions may be limited to several ways. For example, in some cases the cost structure of transmitting data from a mobile device over a particular wireless connection (e.g. satellite uplink) may be such that transmissions occur at less frequent intervals (e.g. for example, every 15 minutes), or mobile devices may have been pre-programmed to transmit at such intervals. In other cases, a mobile device may temporarily lose an ability to transmit data over a wireless connection, such as due to a lack of wireless coverage in an area of ​​the mobile device (for example, due to no nearby receiving station of the mobile device). mobile phone), due to other activities being carried out by the mobile device or a user of the device, or due to a temporary problem with the mobile device or an associated transmitter.

Accordingly, in some embodiments at least some such mobile devices may be designed or otherwise configured to store multiple data samples (or to cause such multiple data samples to be stored in another associated device) so that at least some information for multiple data samples may be transmitted at the same time during a single wireless transmission. For example, in some embodiments at least some mobile devices are configured to store acquired data samples of road traffic conditions information during periods when the mobile device may not be able to transmit the data over a wireless connection (e.g. example, such as for a mobile device that normally transmits each data sample individually, such as every 30 seconds or 1 minute), and then transmitting those stored data samples at once (or a subset and / or grouping of those samples) during the next wireless transmission to occur. Some mobile devices can also be configured to perform wireless transmissions periodically (for example, every 15 minutes, or when a specified amount of data is available to be transmitted), and in at least some embodiments they can be further configured to acquire and store multiple samples of data. information data on road traffic conditions (for example, with a predetermined sampling rate, such as 30 seconds or one minute) in the time interval between wireless transmissions and then similarly transmitting those stored data samples (or a subset and / or grouping of those samples) at the same time during the next wireless transmission. As an example, if a wireless transmission of up to 1000 units of information costs $ 0.25 and each data sample is 50 units in size, it may be advantageous to sample every minute and send a data set comprising 20 samples every 20 minutes ( rather than sending each sample individually every minute). In such embodiments, while the data samples may be slightly delayed (in the example of periodic transmissions, on average half the time period between transmissions, assuming regular acquisitions of data samples), the traffic condition information from Road obtained from the transmissions still provides information close to in real time. Furthermore, in some embodiments additional information can be generated and provided by a mobile device based on multiple stored data samples. For example, if a particular mobile device can acquire only information about a current instantaneous position during each data sample, but cannot acquire additional related information such as speed and / or direction, such additional related information can be calculated or determined. otherwise based on multiple subsequent data samples.

In particular, Figure 9A represents an example area 955 with several interconnected highways 925, 930, 935 and 940, and a legend indication 950 indicates the north direction for the highways (highways 925 and 935 running north-south, and running along highways 930 and 940 in an east-west direction). Although only a limited number of highways are listed, they may represent a large geographic area, such as highways interconnected over many miles, or a subset of city streets running through numerous blocks. In this example, a mobile data source (for example, a vehicle, not shown) has moved from position 945a to 945c in a 30 minute period, and is configured to acquire and transmit a data sample indicating the conditions current traffic every 15 minutes. Consequently, when the mobile data source begins to roam, it acquires and transmits a first data sample at position 945a (as indicated in this example with an asterisk *), it acquires and transmits a second data sample 15 minutes later at position 945b, and acquires and transmits a third data sample a total of 30 minutes later at position 945c. In this example, each data sample includes an indication of the current position (for example, in GPS coordinates), current direction (for example, heading north), current speed (for example, 30 miles per hour), and time current, as represented for transmission 945a using the data values ​​Pa, Da, Sa and Ta, and may also optionally include other information (eg, an identifier to indicate the mobile data source). While such information acquired and provided on current traffic conditions provides some benefit, numerous details cannot be determined from such data, including whether the route from position 945b to 945c occurred in part on Highway 930 or Highway 940. Furthermore, such a data sample does not allow, for example, road parts 925 between positions 945a and 945b to be treated as different road segments for which different traffic conditions can be reported and predicted.

ES 2 373 336 T3

In a manner similar to Figure 9A, Figure 9B depicts an example 905 with a mobile data source traveling through interconnected highways 925, 930, 935, and 940 from positions 945a to 945c in a 30 minute period, and with the mobile data source by transmitting information about traffic conditions every 15 minutes (as indicated by the asterisks displayed at positions 945a, 945b and 945c). However, in this example the mobile data source is configured to acquire and store data samples every minute, with a subsequent transmission including data from each of the data samples during the previous 15 minutes. Consequently, as the mobile data source moves between positions 945a and 945b, the mobile data source acquires a set 910b of 15 data samples 910b1-910b15, with each data sample indicated in this example by an arrow pointing at the address of the mobile data source at the time of data display. In this example, each data sample similarly includes an indication of the current position, current direction, current speed, and current time, and the subsequent transmission at position 945b includes those data values ​​for each of the 910b samples of data. Similarly, when the mobile data source moves between positions 945b and 945c, the mobile data source acquires 15 samples 910c1-910c15 of data and the subsequent transmission at position 945c includes the acquired data values ​​for each of those 15 data samples. By providing such additional data samples, a variety of additional information can be obtained. For example, it is now easily determined that the route from position 945b to 945c was partly on Highway 930 rather than Highway 940, allowing the corresponding traffic condition information to be attributed to Highway 930. In addition, particular data samples and their adjacent data samples can provide various information about smaller stretches of road, such as to allow road 925 between positions 945a and 945b to be represented as, for example, up to 15 different segments of road (for example, associating each data sample with a different road segment) that each has potentially different road traffic conditions. For example, it can be seen visually that the mean velocity for data samples 910b1-910b6 is approximately constant (since the data samples are approximately equally spaced), that the mean velocity increased for data samples 910b7 and 910b8 (since the data samples correspond to positions that are quite far apart, reflecting that greater distance was traveled during the 1 minute interval given between data samples for this example), and that the mean velocity decreased for the 910-11-910-15 data samples. While the data samples in this example directly provide information about such speed, in other embodiments such speed information may be derived from data sample information that includes only the current position.

Figure 9B depicts a third example 990 with a mobile data source traveling along a portion of the interconnected roads 965a to 965c in a period of 30 minutes, and with the mobile data source transmitting information about traffic conditions each 15 minutes (as indicated by the asterisks shown at positions 965a, 945b and 945c). As in Figure 9C, the mobile data source is configured in this example to acquire and store data samples every minute, with a subsequent transmission including data from each of at least some of the data samples during the 15 minutes. previous. Consequently, when the mobile data source moves between positions 965a and 965b, the mobile data source acquires a set 960b of 15 data samples 960b1-960b15. However, as illustrated with the 960b5-b13 placed data samples (using circles in this case instead of arrows because no movement was detected for these data samples, but shown separately instead of one on top of the other with For clarity purposes), in this example the mobile data source has been stopped for approximately 9 minutes at a position next to highway 925 (for example, to stop at a coffee shop). Accordingly, when the next transmission occurs at position 965b, the transmission may in some embodiments include all information for all data samples, or it may instead omit at least some of such information (e.g., omit information for data samples 960b6-960b12, since in this situation they do not provide additional useful information if the mobile data source is known to be stationary between data samples 960b5 and 960b13). Also, while not illustrated here, in other embodiments where the information for one or more such data samples is omitted, subsequent transmission may be delayed until 15 data samples are available to be transmitted (e.g., if periodic transmissions are made based on the amount of data to send rather than time). Also, when the mobile data source moves between positions 965b and 965c, the mobile data source acquires data samples 960c13 and 960c14 in an area where wireless communications are not currently available (as indicated in this example , with open circles instead of arrows). In other embodiments where each data sample is transmitted individually when acquired but not saved, these data samples would be lost, but in this example they are instead stored and transmitted along with the other 960c1-960c12 samples. and 960c15 of data at position 965c. Although not shown here, in some situations a mobile data source may also temporarily lose the ability to obtain one or more data samples using a primary means of data acquisition (for example, if a mobile data source loses capacity get GPS readings for a few minutes) - if that is the case, the mobile data source may in some implementations report the other collected data samples without further action (for example, such as to allow the recipient to interpolate or otherwise estimate those data samples if desired), although in other embodiments one may attempt to obtain data samples in other ways (for example, using a less precise mechanism to determine position , such as triangulating cell towers or estimating current position based on a previous known position and subsequent average speed and heading, such as through dead reckoning), even if those data samples have less precision or certainty (for example, they may be reflected by

ES 2 373 336 T3 include a lower degree of confidence or a higher degree of possible errors with those data samples, or by otherwise including an indication of how those and / or other data samples were generated).

While the example data samples in each of Figures 9B and 9C are illustrated for a single vehicle or other mobile data source for clarity, in other embodiments the multiple data samples for a particular mobile data source do not. can be used to determine a particular route taken by that mobile data source and more generally cannot even be associated with each other (for example, whether the source of each mobile data sample is anonymous or otherwise not distinguishable from other sources). For example, if multiple data samples from a particular mobile data source are not used by a canister to generate the aggregated data related to those data samples (for example, to generate speed and / or direction information based on successive samples of data providing only positional information), such as when such aggregated data is included with each data sample or not used, Such a container may not be provided in some embodiments with identifying data related to the source of the mobile data samples and / or with indications that the multiple data samples are from the same mobile data source (e.g. based on a decision design to increase privacy related to mobile data sources).

Instead, in at least some such embodiments, multiple mobile data sources are used together to determine information on road conditions of interest, such as using multiple data samples from all mobile data sources for a particular road segment. (or another section of a road) to determine aggregated information for that road segment. Thus, for example, during a period of time of interest (for example, 1 minute, 5 minutes, 15 minutes, etc.), numerous unrelated mobile sources of data can provide one or more data samples related to their own displacement. on a particular road segment during that time period, and if each such data sample includes speed and direction information (for example), An average totalized speed can be determined for that time period and that road segment for all mobile data sources moving generally in the same direction, such as in a manner similar to a road sensor that totals information for multiple vehicles that pass through the sensor. A particular data sample can be associated with a particular road segment in various ways, such as associating the position of the data samples with the road (or road segment) having the closest position (either for some road or just for roads that meet specified criteria, such as being of one or more of the indicated functional road classes) and then selecting the appropriate road segment for that road, or by using an indication provided by a mobile data source in conjunction with a data sample of an associated road (or road segment). In addition, in at least some embodiments, roads other than one-way roads will be treated as separate roads for the purposes of assigning data samples to roads and for other purposes (for example, to treat northbound lanes of a highway as they are a different highway than the southbound lanes of the highway), and if that is the case the address for a moving data sample can be further used to determine the appropriate road with which the data sample is associated - in other embodiments however, the roads can be modeled in other ways, such as treat a two-way city street as a single road (for example, with reported and predicted average traffic conditions for vehicles moving in both directions), treat each lane of a multi-lane highway or other roads as a separate logical road, etc.

In some embodiments, to facilitate the use of multiple mobile data sources to determine road condition information of interest, the fleet vehicles can be configured in various ways to provide the usage data samples. For example, if a large fleet of vehicles each leaves the same point of origin at a similar time each day, several of the fleet vehicles can be configured differently with respect to when and how often to start providing data samples. , such as minimizing a very large number of data points all close to the single point of origin and / or providing the variability for when the data samples will be acquired and transmitted. More generally, a mobile data source device can be configured in various ways regarding how and when to acquire data samples, including based on the total distance covered from a starting point (for example, an origin point for a group of fleet vehicles), the distance covered since a last acquisition and / or transmission of data sample, total time elapsed since an initial moment (for example, a departure time of a fleet vehicle from a point of origin), the time elapsed since a last acquisition and / or transmission of data sample, an indicated relationship that has occurred with respect to one or more indicated positions (for example, pass through, arrive at, depart from, etc.), etc. Similarly, a mobile data source device can be configured in various ways regarding how and when to transmit or otherwise provide one or more acquired samples of data, such as when predefined conditions are met, including those based on the total distance covered. from a starting point, the distance covered since a last acquisition and / or data sample transmission, total time elapsed since a start time, the total time elapsed since a last data sample acquisition and / or transmission, an indicated relationship that has occurred with respect to one or more indicated positions, an indicated number of data samples that have been collected, an indicated amount of data that have been gathered (for example, an amount such as filling or substantially filling a cache that is used to store the data samples on the mobile device, or an amount such as filling or substantially filling an indicated amount of time for a transmission), etc.

ES 2 373 336 T3

Figure 8 is a flow chart of an exemplary embodiment of a Mobile Data Source information Provision routine 800 related to the present invention, such as may be provided, for example, by operating a mobile source device of data for each of one or more of the vehicle-based data sources 384 of Figure 3 and / or other data sources 388 (for example, user devices) of Figure 3 and / or vehicle-based data sources 101 of Figure 1 and / or other data sources 102 of Figure 1. In this example, the routine acquires data samples for a mobile source data to indicate current traffic conditions, and stores the data samples as appropriate so that a subsequent transmission can include information for multiple data samples.

The routine begins at step 805, in which parameters that will be used as part of the acquisition and provision of data samples are retrieved, such as parameters that can be configured to indicate when data samples should be acquired and when data samples should occur. transmissions with information corresponding to one or more data samples. The routine continues to step 810 to wait until it is time to acquire a data sample, such as based on the retrieved parameters and / or other information (e.g., an indicated amount of time that has elapsed since a previous acquisition of data). data samples, an indicated distance that has been traveled since a previous acquisition of data samples, an indication to acquire data samples in a substantially continuous manner, etc.). The routine then continues to step 815 to acquire a data sample based on the current position and movement of the mobile data source and stores the data sample in step 820. If it is determined in step 825 that it is not yet time to transmit the data, such as based on the retrieved parameters and / or other information (e.g., an indicated amount of time that has passed since a previous transmission, an indicated distance that has traveled since a previous transmission, an indication to transmit data samples as soon as they become available or in a substantially continuous manner, etc.), the routine returns to step 810.

Otherwise, the routine continues to step 830 to retrieve and select any stored sample of data from the previous transmission (or from startup, for the first transmission). The routine then optionally at step 835 generates totalized data based on multiples of the selected data samples (e.g., an overall average speed for all data samples, an average speed, and a direction for each data sample if the acquired information provides only position information, etc.), although in other embodiments such aggregated data generation cannot be performed. At step 840, the routine then optionally removes some or all of the information acquired for some or all of the data samples from the selected set of data samples (e.g., to transmit only selected types of data for each data sample, to remove data samples that appear to be outliers or otherwise erroneous, to eliminate data samples that do not correspond to the true movement of the mobile data source, etc.), although in other embodiments such deletion of information may not be performed. At step 845, the routine then transmits the current information in the current set of data samples and any aggregated information for a recipient that will use the data in an appropriate manner. At step 895, the routine determines whether to continue (eg, whether the mobile data source continues to be in use and mobile), and whether that is the case, returning to step 810. Otherwise, the routine continues to step 899 and ends. In embodiments and situations where a mobile data source is unable to transmit data, either due to temporary conditions or instead to reflect the configuration or limitations of the mobile data source, steps 830-845 may not be performed until such time that the mobile data source is capable of transmitting or otherwise providing (for example, via physical download) some or all of the data samples that have been acquired and stored since a previous transmission.

As indicated above, once the information about road traffic conditions has been obtained, such as from one or more mobile data sources and / or from one or more other sources, the information on traffic conditions can be used in various ways, such as to report current road traffic conditions in a substantially real-time manner or to use past and current road traffic condition information to predict future traffic conditions at each of multiple future times. In some embodiments, the types of input data that are used to generate predictions of future traffic conditions may include a variety of current, previous, and expected future conditions, and the outputs of the prediction process may include the predictions generated from the expected traffic conditions in each of multiple target road segments of interest for each of future multiple times (for example, every 5, fifteen or 60 minutes in the future) within a predetermined time interval (for example, three hours or one day), as discussed in greater detail elsewhere. For example, the types of input data may include the following: information about current and past traffic amounts for various target road segments of interest in a geographic area, such as for a network of selected roads in the geographic area; information about recent and current traffic accidents; information about recent and current works; information about current, past and future weather conditions as expected (eg precipitation, temperature, wind direction, wind speed, etc.); information about at least one current, past and future planned event (for example, the type of event, the expected start and end times of the event, and / or a performance location or other location of the event, etc., such as for all events, events of indicated types, events that are large enough, such as those with expected attendance above a specified threshold (for example, 1000 or 5000 expected attendees), etc.); And the information

ES 2 373 336 T3 about school hours (for example, if the school is in season and / or the position of one or more schools). Furthermore, while in some embodiments the multiple future times when future traffic conditions are predicted are each point in time, in other embodiments such predictions may instead represent multiple time points (e.g., a period of time). time), such as representing an average or other aggregated measure of future traffic conditions during those multiple time points. Additionally, some or all of the input data may be known and represented with varying degrees of certainty (eg, expected weather), and additional information may be generated to represent degrees of confidence and / or other data describing data for the generated predictions. Furthermore, the prediction of future traffic conditions can be initiated for various reasons and at various times, such as on a periodic basis, (for example, every five minutes), when any or enough new input data is received, in response to a request from a user, etc.

Some of the same types of input data can be used to similarly generate longer-term forecasts of future traffic conditions (for example, one week in the future or one month in the future) in some implementations, but such forecasts are further Long-term may not use some of the input data types, such as information about current conditions at the time of forecast generation (for example, current traffic, weather or other conditions). Furthermore, such longer-term forecasts may be generated less frequently than shorter-term forecasts, and they may be made to reflect different future time periods than for shorter-term forecasts (for example, for every hour instead of every 15 minutes).

The roads and / or road segments for which future predictions and / or forecasts of traffic conditions are generated can also be selected in various ways in various embodiments. In some embodiments, future predictions and / or forecasts of traffic conditions are generated for each of multiple geographic areas (e.g., metropolitan areas), with each geographic area having a network of multiple interconnected highways - such geographic areas can be selected. in various ways, such as based on areas where current traffic condition information is readily available (for example, based on road sensor networks for at least some of the roads in the area) and / or where traffic congestion is a significant problem. In some such embodiments, the roads for which future traffic condition predictions and / or forecasts are generated including those roads for which current traffic condition information is readily available, while in other embodiments the selection of such roads may be based at least in part on one or more of other factors (for example, based on the size or capacity of roads, such as including major highways and expressways; based on the role that roads play in carrying traffic, such as including main roads and distribution roads that are primary alternatives to higher capacity roads such as major highways and expressways; based on the functional class of the highways, as designated by the Federal Highway Administration; etc.). In other embodiments, future predictions and / or forecasts of traffic conditions can be made for a single road, regardless of its size and / or relationship to other roads. Furthermore, the road segments for which future traffic condition predictions and / or forecasts are generated can be selected in various ways, such as treating each road sensor as a separate segment; grouping multiple road sensors together for each road segment (eg, to reduce the number of independent predictions and / or forecasts that are made, such as by grouping specific numbers of road sensors together); to select road segments to reflect logically related sections of a road where traffic conditions are typically the same or sufficiently similar (e.g., strongly related), such as based on traffic condition information from traffic sensors and / or from other sources (for example, data generated from vehicles and / or users traveling on the roads, as discussed in greater detail elsewhere); etc.

In addition, future traffic condition prediction and / or forecast information can be used in various ways in various embodiments, as discussed in greater detail elsewhere, including providing such information to users and / or organizations at various times ( for example, in response to requests, periodically sending the information, etc.) and in various ways (for example, transmitting the information to mobile phones and / or other portable consumer devices; displaying information to users, such as through application programs and internet browsers; providing the information to other organizations and / or entities that provide at least some information to users, such as third parties who provide the information after analyzing and / or modifying the information; etc.). For example, in some embodiments, the prediction and / or forecast information is used to determine suggested routes and / or travel times, such as an optimal route between a starting position and a finishing position over a road network and / or or an optimal time to carry out the indicated movement, with such determinations based on predicted and / or forecast information at each of multiple future times for one or more roads and / or road segments.

In addition, various embodiments provide various mechanisms for users and other customers to interact with one or more of the traffic information systems (e.g., the Data Sample Manager system 350, the RT Information Provider system 363 and / or the 360 Predictive Provider Traffic information from Figure 3, etc.). For example, some embodiments may provide an interactive console (for example, a client program that provides an interactive user interface, a browser-based interface of

ES 2 373 336 T3

Internet, etc.) from which customers can make requests and receive corresponding responses, such as requests for information related to current and / or predicted traffic conditions and / or requests to analyze, select and / or provide information related to routes Travel. In addition, some embodiments provide an API (Application Programmer Interface) that allows the customer to compute systems to do some or all of such requests programmatically, such as through network message protocols ( for example, Web services) and / or other communication mechanisms.

From the foregoing it will be appreciated that, although specific embodiments in accordance with the present invention and additional aspects related to the present invention have been described herein for purposes of illustration, various modifications may be made without departing from the scope of the invention. Accordingly, the invention is not limited except by the appended claims and the items set forth therein. Furthermore, while certain aspects of the invention are set forth in certain claim forms, the inventors contemplate the various aspects of the invention in any available claim form. For example, while currently only some aspects of the invention may be reported as being incorporated in a computer-readable medium, other aspects can be incorporated as well.