METHOD, APPARATUS, AND SYSTEM FOR PROVIDING AN ESTIMATED TIME OF ARRIVAL WITH UNCERTAIN STARTING LOCATION

An approach is provided for providing an estimated time of arrival (ETA) with a uncertain starting location. The approach, for example, involves determining an uncertainty time window that spans from a timestamp of a location point of a sparse location data feed to a time of interest. The approach also involves determining a speed of the device at the location point based on the location data feed. The approach further involves processing map data based on the speed to predict possible locations to which the device may have traveled during the uncertainty time window and to determine one or more respective probabilities of the device has traveled to the possible locations. The approach further involves determining respective ETA at a destination from the possible locations. The approach further involves calculating a total estimated time of arrival based on the respective estimated times of arrival and the respective probabilities.

BACKGROUND

Navigation and travel related services (e.g., ride-hailing, ridesharing, etc.) often rely on accurate calculation of estimated times of arrival (ETAs). The accuracy of ETA calculations can often depend on the accuracy of input parameters such as starting locations and routes taken by a vehicle or user. In many cases, these parameters are determined from sparse location sensor data feeds that include location data points captured at designated sampling frequencies (e.g., every 5 seconds, 10 seconds, 30 seconds, etc.). This sparse data creates an uncertainty time window or time delta error between any two location data points during which the vehicle/user's location and/or route taken is uncertain or not known. The uncertainty can lead to less certain or less accurate ETAs particularly on shorter routes where the length of the uncertainty time window represents a larger portion of the overall trip length. Accordingly, service providers face significant technical challenges to provide accurate ETA calculation when location data is sparse.

SOME EXAMPLE EMBODIMENTS

Therefore, there is a need for provide an estimated time of arrival (ETA) when ETA input parameters (e.g., location data feeds, starting locations, etc.) are sparse or uncertain.

According to one embodiment, a method comprises determining, by a processor, an uncertainty time window that spans from a timestamp of a location point of a sparse location data feed to a time of interest. The sparse location data feed is determined from at least one location sensor of a device. The method also comprises determining a speed of the device at the location point based on the sparse location data feed. The method further comprises processing map data based on the speed to predict one or more possible locations to which the device may have traveled during the uncertainty time window and to determine one or more respective probabilities of the device has traveled to the one or more possible locations. The method further comprises determining one or more respective estimated times of arrival (ETAs) at a destination from the one or more possible locations. The method further comprises calculating a total estimated time of arrival based on the one or more respective ETAs and the one or more respective probabilities. The method further comprises providing the total estimated time of arrival as an output to a location-based service.

According to another embodiment, an apparatus comprises at least one processor, and at least one memory including computer program code for one or more computer programs, the at least one memory and the computer program code configured to, with the at least one processor, cause, at least in part, the apparatus to determine an uncertainty time window that spans from a timestamp of a location point of a sparse location data feed to a time of interest. The sparse location data feed is determined from at least one location sensor of a device. The apparatus is also caused to determine a speed of the device at the location point based on the sparse location data feed. The apparatus is further caused to process map data based on the speed to predict one or more possible locations to which the device may have traveled during the uncertainty time window and to determine one or more respective probabilities of the device has traveled to the one or more possible locations. The apparatus is further caused to determine one or more respective estimated times of arrival (ETAs) at a destination from the one or more possible locations. The apparatus is further caused to calculate a total estimated time of arrival based on the one or more respective ETAs and the one or more respective probabilities. The apparatus is further caused to provide the total estimated time of arrival as an output to a location-based service.

According to another embodiment, a computer-readable storage medium carries one or more sequences of one or more instructions which, when executed by one or more processors, cause, at least in part, an apparatus to determine an uncertainty time window that spans from a timestamp of a location point of a sparse location data feed to a time of interest. The sparse location data feed is determined from at least one location sensor of a device. The apparatus is also caused to determine a speed of the device at the location point based on the sparse location data feed. The apparatus is further caused to process map data based on the speed to predict one or more possible locations to which the device may have traveled during the uncertainty time window and to determine one or more respective probabilities of the device has traveled to the one or more possible locations. The apparatus is further caused to determine one or more respective estimated times of arrival (ETAs) at a destination from the one or more possible locations. The apparatus is further caused to calculate a total estimated time of arrival based on the one or more respective ETAs and the one or more respective probabilities. The apparatus is further caused to provide the total estimated time of arrival as an output to a location-based service.

According to another embodiment, an apparatus comprises means for determining, by a processor, an uncertainty time window that spans from a timestamp of a location point of a sparse location data feed to a time of interest. The sparse location data feed is determined from at least one location sensor of a device. The apparatus also comprises means for determining a speed of the device at the location point based on the sparse location data feed. The apparatus further comprises means for processing map data based on the speed to predict one or more possible locations to which the device may have traveled during the uncertainty time window and to determine one or more respective probabilities of the device has traveled to the one or more possible locations. The apparatus further comprises means for determining one or more respective estimated times of arrival (ETAs) at a destination from the one or more possible locations. The apparatus further comprises means for calculating a total estimated time of arrival based on the one or more respective ETAs and the one or more respective probabilities. The apparatus further comprises means for providing the total estimated time of arrival as an output to a location-based service.

For various example embodiments, the following is applicable: An apparatus comprising means for performing a method of the claims.

DESCRIPTION OF SOME EMBODIMENTS

FIG. 1is a diagram of a system capable of providing an estimated time of arrival (ETA) with a uncertain starting location (i.e., of a vehicle), according to one embodiment. Travel time is a basic attribute considered by various mobility services, such as personal navigation, travel planning, ride-hailing, ridesharing, fleet management, etc. The users of the mobility services make decisions based on an average travel time or ETA.

Navigation and mapping service providers are continually challenged to optimize urban mobility. One area of interest has been improving user experience of location-based services, such as ride-hailing, ridesharing, etc. In many real world mobility services, when a backend system running an optimizing algorithm (such as choosing the best taxi, or simply estimating its ETA) only has access to GPS coordinates taken in a sparse way, the backend system is uncertain regarding a starting location of a target vehicle (e.g., the taxi). As mentioned, most GPS sensors in user devices emit GPS data feeds (location points) at designated sampling frequencies (e.g., every 5 seconds, 10 seconds, 30 seconds, etc.) (i.e., in a sparse manner) to conserve resources consumption, such as battery power, bandwidth, storage, calculation time, etc.

In many mobility related algorithms, ETA is generated as a sole output or used as an input in a bigger optimizing algorithm for urban navigation. In urban scenarios, many of the routes for which to calculate ETAs are relatively short. As such, the sparsity of the location sensor data feed (e.g., GPS data) leads to uncertainty of a starting location of a vehicle (e.g., a taxi), and its estimated time of arrival (ETA). Therefore, the existing ETA solutions simply assume the last known location of the vehicle or the last known map-matched location of the vehicle (thus correcting GPS errors) as the starting location of the vehicle. The existing ETA solutions then use the starting location and the heading of the vehicle at a starting time to estimate an ETA, in conjunction with either only historical ETA data or the historical ETA data plus routing map data. These solutions The is no solution dealing specifically with short term ETA predictions that addresses both GPS errors and timedelta errors due to GPS sparsity. A timedelta errors occur during a time window/duration absent of GPS data which is a result of GPS sparsity. Such timedelta/window/duration can be between a time of interest (e.g., a current time) and a past time point when the vehicle was at a location point of a sparse location data feed (e.g., a last known location). Such short term ETA predictions and timedelta errors due to GPS sparsity can be magnified in urban short term settings.

Referring back to the taxi example, a taxi is usually close by a pickup location and can arrive in less than 10 minutes. For such a short distance, a small difference of the starting location and/or a driving direction can significantly change their respective ETAs. For example, during a 30-second time window (“timedelta”), the taxi may or may not turn into a long one-way street leading towards the opposite direction of the pickup destination. Such a turn may double ETA. The existing ETA solutions do not address to such timedelta errors due to GPS sparsity.

To address these problems, the system100ofFIG. 1introduces a capability to provide an ETA with a uncertain starting location (i.e., of a vehicle), by translates the starting location uncertainty in a sparse GPS data feed into a weighted average of multiple sources using sensor data and map data to estimate velocity, possible locations, and a total estimated time of arrival (UETA). It is noted that the term “starting location” refers to an estimated location of a probe (e.g., a vehicle or a user device travelling with the vehicle) at a time of interest (any time, e.g., a current time) after a uncertainty time window passed since the vehicle was at a location point of a sparse location data feed (e.g., a last known location). The term “sparse location data feed” is a location data feed including location data points captured by a location sensor at designated sampling frequencies (e.g., every 5 seconds, 10 seconds, 30 seconds, etc.). As mentioned, this sparse data creates the uncertainty time window or time delta error between any two location data points during which the vehicle/user's location and/or route taken is uncertain or not known.

The system100can improve the ETA prediction for short rides in various cases where many turns and locations are possible. As such, the system100can calculate a change in ETA due to GPS sparsity, which can be a difference between the UETA and an original ETA determined based on the existing methods), thereby correcting the ETA difference/error accordingly. The system100cab be used in handling many mobility optimization applications, such as ride-hailing, ridesharing, etc., for example, to provide the UETA to the riders and drivers, so the users will have better expectation based on UETA (i.e., more likely ETA).

In one embodiment, the system100collects a plurality of instances of probe data and/or vehicle sensor data from one or more vehicles101a-101n(also collectively referred to as vehicles101) (e.g., autonomous vehicles, HAD vehicles, semi-autonomous vehicles, etc.) having one or more vehicle sensors103a-103n(also collectively referred to as vehicle sensors103) (e.g., global positioning system (GPS), LiDAR, camera sensor, etc.) and having connectivity to an ETA platform105via a communication network107. In one instance, the real-time probe data may be reported as probe points, which are individual data records collected at a point in time that records telemetry data for that point in time. A probe point can include attributes such as: (1) probe ID, (2) longitude, (3) latitude, (4) heading, (5) speed, and (6) time.

In one instance, the system100can also collect the real-time probe data and/or sensor data from one or more user equipment (UE)109a-109n(also collectively referenced to herein as UEs109) associated with the a vehicle101(e.g., an embedded navigation system), a user or a passenger of a vehicle101(e.g., a mobile device, a smartphone, etc.), or a combination thereof. In one instance, the UEs109may include one or more applications111a-111n(also collectively referred to herein as applications111) (e.g., a navigation or mapping application). In one embodiment, the probe data and/or sensor data collected may be stored in the probe database113, the geographic database115, or a combination thereof.

In one instance, the system100may also collect real-time probe data and/or sensor data from one or more other sources such as government/municipality agencies, local or community agencies (e.g., a police department), and/or third-party official/semi-official sources (e.g., a services platform117, one or more services119a-119n, one or more content providers121a-121m, etc.).

FIG. 2is a diagram of an example use case for providing an estimated time of arrival with a uncertain starting location, according to one embodiment. By way of example, a vehicle101was last reported at a time “t” at a location point “L” (i.e., a last known location) based on a real-time sparse location data feed reported by the vehicle101as shown in a map201. The system100can calculate an ETA from location L to a destination “D” as 3.5 minutes. Although the system100does not have a current location of the vehicle101during a location data reporting time window/interval (“T”), the system100can calculate a speed (“v”) of the vehicle101based on the real-time sparse location data feed, using a formula203: v=f (L, t, T). By way of example, the speed v of the vehicle101is calculated from two reported location points of the sparse location data feed.

In addition, the system100can determine possible locations S1-S3on different streets around location L that the vehicle101travelled to via routes205a-205cat speed v during the reporting time window/interval T, based on map data stored locally or retrieved from the geographical database115. The system100can determine the respective probabilities Pa-Pc of traveling to S1-S3as, for example, Pa=0.5, Pb=0.25, Pc=0.25, based on historical traffic data, a machine learning model, etc. In other words, there is 50% likelihood that the vehicle101will go straight to reach location S1, 25% likelihood that the vehicle101will turn right to reach location S2, and 25% likelihood that the vehicle101will turn left to reach location S3.

The system100then can calculate a total estimated time of arrival (“UETA”) based on individual ETAs from the possible locations S1-S3and their respective probabilities, using a formula207: UETA=f (ETA205a, ETA205b, ETA205c, Pa=0.5, Pb=0.25, Pc=0.25). For example, from location S1, the vehicle101can continue route205aby making a left turn at location A to reach destination D, and the ETA is 3 minutes. From location S2, the vehicle101can continue route205bvia take an exit off the highway at location B, make a left turn at location E, and make a right turn at location F to reach destination D, and the ETA is 10 minutes. From location S3, the vehicle101can continue route205cvia taking an exit of the highway at a location C on the highway, take a right turn at location H to reach destination D, and the ETA is 20 minutes. In this example, UETA=0.5*3+0.25*10+0.25*20=9 (min).

In one embodiment, the real-time sparse location data feed is received directly from the vehicle101. In this embodiment, vehicle101can be configured to report probe data and/or sensor data (e.g., via a vehicle sensor103, a UE109, or a combination thereof) as probe points, which are individual data records collected at a point in time that records telemetry data for the vehicle101for that point in time. In another embodiment, the real-time sparse location data feed is received from one or more third party probe data aggregators, the probe database113, or a combination thereof. In one embodiment, a probe point may include the following five attributes (by way of illustration and not limitation): (1) probe ID; (2) longitude; (3) latitude; (4) speed; and (5) time.

FIG. 3is a diagram of the components of the ETA platform105, according to one embodiment. By way of example, the ETA platform105includes one or more components for providing an estimated time of arrival with a uncertain starting location, according to the various embodiments described herein. It is contemplated that the functions of these components may be combined or performed by other components of equivalent functionality. In one embodiment, the ETA platform105includes a data processing module301, a location predication module303, a probability module305, a communication module307, and a machine learning system123has connectivity to the probe database113and the geographic database115. The above presented modules and components of the ETA platform105can be implemented in hardware, firmware, software, or a combination thereof. Though depicted as a separate entity inFIG. 1, it is contemplated that the ETA platform105may be implemented as a module of any other component of the system100. In another embodiment, the ETA platform105, the machine learning system123, and/or the modules301-307may be implemented as a cloud-based service, local service, native application, or combination thereof. The functions of the ETA platform105, the machine learning system123, and/or the modules301-307are discussed with respect toFIG. 4.

FIG. 4is a flowchart of a process for providing an estimated time of arrival with a uncertain starting location, according to one embodiment. In various embodiments, the ETA platform105, the machine learning system123, and/or any of the modules301-307may perform one or more portions of the process400and may be implemented in, for instance, a chip set including a processor and a memory as shown inFIG. 8. As such, the ETA platform105and/or the modules301-307can provide means for accomplishing various parts of the process400, as well as means for accomplishing embodiments of other processes described herein in conjunction with other components of the system100. Although the process400is illustrated and described as a sequence of steps, its contemplated that various embodiments of the process400may be performed in any order or combination and need not include all the illustrated steps.

In one embodiment, the data processing module301can map-match the probe data and/or sensor data by processing the real-time sparse location data feed (e.g., probe data comprising GPS trace points or other location data) to identify which road, path, link, etc. a probe device (e.g., a vehicle101, a UE109, etc.) is travelling. The map matching process, for example, enables the data processing module301to correlate each location data point of a vehicle101to a corresponding location on a segment of the road network.

In step401, the data processing module301can determine an uncertainty time window “T” that spans from a timestamp of a location point (e.g., a GPS point) of a sparse location data feed to a time of interest (e.g., a time of possible location and probability assignment). The sparse location data feed is determined from at least one location sensor of a device (e.g., UE109). By way of example, the location point “L” is a last reported location point of the sparse location data feed, and the time of interest is a current time “t”.

In step403, the data processing module301can determine a speed of the device (e.g., UE109) at the location point “L” based on the sparse location data feed. In one embodiment, the speed “v” is determined from at last two reported location points of the sparse location data feed. By way of example, the data processing module301can calculate an effective speed ‘v’ based on previous two GPS tracks.

In step405, the location prediction module303can process map data based on the speed “v” to predict one or more possible locations “S” to which the device (e.g., UE109) may have traveled during the uncertainty time window “T” and to determine one or more respective probabilities “P” of the device has traveled to the one or more possible locations “S”, by working in conjunction with the probability module305.

By way of example, the location prediction module303can process map data retrieved from the geographic database115to determine that the vehicle101take different maneuver options, for example, different turn maneuvers including going straight (no turn), turning right, turning left at the location point “L”, that lead to different streets. The maneuver options for a real world decision point/location varies depending on the road layout, traffic, weather, etc. around the location. These three maneuver options are provided by way of simplified illustration and not as a limitation.

The location prediction module303can then determine the possible locations (e.g., S1-S3) reached at a time point “t+T” from the location “L” based on the speed “v”, the time window “T” (e.g., 30 seconds), and the maneuver options go straight, turn right, or turn left near the location point “L”. For examples, from the location point “L”, the vehicle101can reach the possible location S1by going straight (i.e., no turning) at speed “v” during the window “T”, the vehicle101can reach the possible location S2by turning right at speed “v” during the period “T”, and the vehicle101can reach the possible location S3by turning left at speed “v” during the period “T.”

In one instance, the location prediction module303can assume the vehicle101travels the same distance (e.g., v*T) to S1-S3at speed “v” during the period “T” via the different maneuver options. In another instance, the location prediction module303further considers traffic signs, real-time and/or historical traffic data, etc. associated with the maneuver options, to adjust the speed “vi” for each maneuver option and determine the respective distances (e.g., vi*T) to S1-S3.

In one embodiment, the probability module305can use one or more statistical or probability models to describe a probe maneuver activity distribution (e.g., probe count distribution of maneuver activities), depending on a maneuver activity type (e.g., turning, passing, merging onto a highway, braking, parking, etc.), the properties of the underlying road segment/network, etc. In other words, the probability module305can use any suitable statistic or discrete probability distribution to determine the odds or the likelihood of the possible probe maneuver activities (e.g., turning) such as but not limited to a uniform distribution, a Poisson distribution, a Gaussian approximation of the Poisson distribution, or the like. By way of example, the one or more respective turn probabilities are determined based on a uniform distribution. Referring back to the example depicted inFIG. 2, the probability module305can set a going straight (no turn) probability Pa=0.33, a turning right probability Pb=0.33, a turning right probability Pc=0.33 based on a uniform distribution.

In another embodiment, the one or more respective probabilities are determined based on historical traffic data. In this instance, the probability module305can retrieve historical traffic data associated with the location point “L” and the nearby road segment/network data from the geographic database115. The historical traffic data may already include the probability data of Pa, Pb, Pc. Otherwise, the probability module305can calculate the probability data of Pa, Pb, Pc based on the actual counts of going straight instances, turning right instances, and turning right instances at a time of the day/week/month corresponding to the time “t”. As a result, the probability module305can set Pa=0.5, Pb=0.25, Pc=0.25 based on historical traffic data for the time “t”.

In yet another embodiment, the one or more respective probabilities are determined using machine learning. In one instance, the machine learning is based on one or more features. Referring back to the Examiner depicted inFIG. 2, the one or more features can include a historic average of turns per time, a time of day, current traffic, a user preference, or a combination thereof.

In one instance, the historic average of turns per time can be defined as historic average counts of turns with respect to a location as a function of time, and high counts can be converted into higher probabilities. By way of example, more counts of the right turn than a count of going straight during morning rush hours, while more counts of the left turn than a count of going straight during after rush hours. In another instance, the probability module305can factor a current traffic on the street where the right turn will lead to by lower the probability of turning right. In other instances, the user preference may be associated with one or more contextual attributes, such as a transport mode, a travel speed, calendar data, etc. to tailor the probabilities to the user.

In one embodiment, the probability module305in connection with the machine learning system123can select respective weights of the one or more features. In one embodiment, the probability module305can train the machine learning system123to select or assign respective weights, correlations, relationships, etc. among the ranking criteria, the information types, the contextual attributes, the one or more features, or a combination thereof, for determining the possible locations and respective probabilities. In one instance, the probability module305can continuously provide and/or update a machine learning model (e.g., a support vector machine (SVM), neural network, decision tree, etc.) of the machine learning system123during training using, for instance, supervised deep convolution networks or equivalents. In other words, the probability module305trains the machine learning model using the respective weights of the one or more features to most efficiently select the possible locations and the respective probabilities, in order to render a total estimated time of arrival (UETA) as follows.

In step407, the data processing module301can determine one or more respective estimated times of arrival (ETAs) at a destination from the one or more possible locations “S”. Referring back to the example depicted inFIG. 2, the data processing module301can calculate a set ‘E’ of ETAs from each point (e.g., S1-S3) in ‘S’ to the destination D using statistical methods with an estimated variance set ‘V’. In probability statistics, variance is a standard statistical variance, i.e., the expectation of the squared deviation (SD) of a random variable from its mean. In one embodiment, the data processing module301can determine av estimated variance set ‘V’ by measuring how far the set ‘E’ of ETAs are spread out from their average value.

In step409, the data processing module301can calculate the UETA based on the one or more respective estimated times of arrival and the one or more respective probabilities. In one embodiment, the UETA is based on a weighted average of the one or more respective times of arrival with the one or more respective probabilities used for weighting. For example, the UETA can be a weighted average of ‘E’ with weights ‘P’, and expressed as a formula: UETA=sum_i {ETA|si}

In one embodiment, the data processing module301can determine a variance estimation of the UETA (“Var(UETA)”) based on a variance decomposition rule. For example, the Var(UETA) can be defined via variables Vi, Pi, and Ei associated with respective possible location Si are random on the same probability space, and the variance of UETA is finite, and expressed as a variance decomposition formula: Var(UETA)=sum_over_i {Vi*Pi}+(sum_over_i {Pi*Ei{circumflex over ( )}2}−[sum_over_i {Pi*Ei}]{circumflex over ( )}2)

In one embodiment, the UETA is calculated for a trip to the destination that is less than a threshold trip length. By way of example, such short trip can last 5 minutes, yet the data processing module301can calculate the UETA considering the possible distances travelling during the time window “T” (when the location data is absent due to GPS sparsity), and the subsequent distances travelled form the possible locations to the destination D.

In step411, the output module307can provide the UETA as an output to a location-based service. By way of example, the location-based service is a ride-hailing service or a ridesharing service.

In one embodiment, the output module307may provide the output to a vehicle101, a user of the vehicle101(e.g., a driver or a passenger), or a combination thereof via a UE109(e.g., an embedded navigation system, a mobile device, etc.) and/or an application111running on the UE109(e.g., a navigation application).FIG. 5is a diagram of an example user interface500depicting a total estimated time of arrival, according to one embodiment. The user interface500shows a current time4:03and a notification501of “a passenger waiting at location D”. The user interface500also shows a notification503of the UETA (e.g., 9 minutes4:12) via a navigation or mapping application111of a UE109when waiting for a vehicle101(e.g., a taxi, a shared vehicle, etc.).

In one embodiment, the output module307can provide the Var(UETA) as part of the output to the data processing module301for training the machine learning model. In another embodiment, the output module307can output to the geographic database115the probability data, UETA data, respective variance data, Var(UETA) data, etc. corresponding to a vehicle101for future use and/or training of the machine learning system123, to improve the speed and accuracy of the UETA processes of the ETA platform105.

Based actual GPS data of a sample city, the system100calculates UETA for short rides (e.g., 5 minutes) with heading information yields significant improvement over UETA calculated without heading information. In one instance, UETA results are similar on 80% of the GPS tracks, but are much better in the remaining 20% of the GPS tracks. For example, the 20% of the GPS tracks can occur in a short time window a moving vehicle can change its location by taking certain turns in a way that is similar to reverting its heading. Therefore, the system100can significantly improve ETA calculation for at least 20% of the short rides.

The above-discussed embodiments improve ETA using map data to predict ETA for short rides with a location uncertainty within a timeframe ‘T’. The improvement is high for some low coverage and/or high impact cases in urban settings, such as ride-hailing and carsharing.

Returning toFIG. 1, in one embodiment, the ETA platform105has connectivity over the communication network107to the services platform117(e.g., an OEM platform) that provides one or more services119a-119n(also collectively referred to herein as services119) (e.g., probe and/or sensor data collection services). By way of example, the services119may also be other third-party services and include mapping services, navigation services, traffic incident services, travel planning services, notification services, social networking services, content (e.g., audio, video, images, etc.) provisioning services, application services, storage services, contextual information determination services, location-based services, information-based services (e.g., weather, news, etc.), etc. In one embodiment, the services platform117uses the output (e.g. lane-level dangerous slowdown event detection and messages) of the ETA platform105to provide services such as navigation, mapping, other location-based services, etc.

In one embodiment, the ETA platform105may be a platform with multiple interconnected components. The ETA platform105may include multiple servers, intelligent networking devices, computing devices, components and corresponding software for providing parametric representations of lane lines. In addition, it is noted that the ETA platform105may be a separate entity of the system100, a part of the services platform117, a part of the one or more services119, or included within the vehicles101(e.g., an embedded navigation system).

In one embodiment, content providers121a-121m(also collectively referred to herein as content providers121) may provide content or data (e.g., including probe data, sensor data, etc.) to the ETA platform105, the UEs109, the applications111, the probe database113, the geographic database115, the services platform117, the services119, and the vehicles101. The content provided may be any type of content, such as map content, textual content, audio content, video content, image content, etc. In one embodiment, the content providers121may provide content that may aid in localizing a vehicle path or trajectory on a lane of a digital map or link. In one embodiment, the content providers121may also store content associated with the ETA platform105, the probe database113, the geographic database115, the services platform117, the services119, and/or the vehicles101. In another embodiment, the content providers121may manage access to a central repository of data, and offer a consistent, standard interface to data, such as a repository of the geographic database115.

By way of example, the UEs109are any type of embedded system, mobile terminal, fixed terminal, or portable terminal including a built-in navigation system, a personal navigation device, mobile handset, station, unit, device, multimedia computer, multimedia tablet, Internet node, communicator, desktop computer, laptop computer, notebook computer, netbook computer, tablet computer, personal communication system (PCS) device, personal digital assistants (PDAs), audio/video player, digital camera/camcorder, positioning device, fitness device, television receiver, radio broadcast receiver, electronic book device, game device, or any combination thereof, including the accessories and peripherals of these devices, or any combination thereof. It is also contemplated that a UE109can support any type of interface to the user (such as “wearable” circuitry, etc.). In one embodiment, a UE109may be associated with a vehicle101(e.g., a mobile device) or be a component part of the vehicle101(e.g., an embedded navigation system). In one embodiment, the UEs109may include the ETA platform105to provide an estimated time of arrival with a uncertain starting location.

In one embodiment, as mentioned above, the vehicles101, for instance, are part of a probe-based system for collecting probe data and/or sensor data for detecting traffic incidents (e.g., dangerous slowdown events) and/or measuring traffic conditions in a road network. In one embodiment, each vehicle101is configured to report probe data as probe points, which are individual data records collected at a point in time that records telemetry data for that point in time. In one embodiment, the probe ID can be permanent or valid for a certain period of time. In one embodiment, the probe ID is cycled, particularly for consumer-sourced data, to protect the privacy of the source.

In one embodiment, a probe point can include attributes such as: (1) probe ID, (2) longitude, (3) latitude, (4) heading, (5) speed, and (6) time. The list of attributes is provided by way of illustration and not limitation. Accordingly, it is contemplated that any combination of these attributes or other attributes may be recorded as a probe point. For example, attributes such as altitude (e.g., for flight capable vehicles or for tracking non-flight vehicles in the altitude domain), tilt, steering angle, wiper activation, etc. can be included and reported for a probe point. In one embodiment, the vehicles101may include sensors103for reporting measuring and/or reporting attributes. The attributes can also be any attribute normally collected by an on-board diagnostic (OBD) system of the vehicle101, and available through an interface to the OBD system (e.g., OBD II interface or other similar interface).

The probe points can be reported from the vehicles101in real-time, in batches, continuously, or at any other frequency requested by the system100over, for instance, the communication network107for processing by the ETA platform105. The probe points also can be map matched to specific road links stored in the geographic database115. In one embodiment, the system100(e.g., via the ETA platform105) can generate probe traces (e.g., vehicle paths or trajectories) from the probe points for an individual probe so that the probe traces represent a travel trajectory or vehicle path of the probe through the road network.

In one embodiment, as previously stated, the vehicles101are configured with various sensors (e.g., vehicle sensors103) for generating or collecting probe data, sensor data, related geographic/map data, etc. In one embodiment, the sensed data represents sensor data associated with a geographic location or coordinates at which the sensor data was collected. In one embodiment, the probe data (e.g., stored in the probe database113) includes location probes collected by one or more vehicle sensors103. By way of example, the vehicle sensors103may include a RADAR system, a LiDAR system, global positioning sensor for gathering location data (e.g., GPS), a network detection sensor for detecting wireless signals or receivers for different short-range communications (e.g., Bluetooth, Wi-Fi, Li-Fi, near field communication (NFC) etc.), temporal information sensors, a camera/imaging sensor for gathering image data, an audio recorder for gathering audio data, velocity sensors mounted on a steering wheel of the vehicles101, switch sensors for determining whether one or more vehicle switches are engaged, and the like. Though depicted as automobiles, it is contemplated the vehicles101can be any type of vehicle manned or unmanned (e.g., cars, trucks, buses, vans, motorcycles, scooters, drones, etc.) that travel through road segments of a road network.

Other examples of sensors103of the vehicle101may include light sensors, orientation sensors augmented with height sensors and acceleration sensor (e.g., an accelerometer can measure acceleration and can be used to determine orientation of the vehicle), tilt sensors to detect the degree of incline or decline of the vehicle101along a path of travel (e.g., while on a hill or a cliff), moisture sensors, pressure sensors, etc. In a further example embodiment, sensors103about the perimeter of the vehicle101may detect the relative distance of the vehicle101from a physical divider, a lane line of a link or roadway, the presence of other vehicles, pedestrians, traffic lights, potholes and any other objects, or a combination thereof. In one scenario, the vehicle sensors103may detect weather data, traffic information, or a combination thereof. In one embodiment, the vehicles101may include GPS or other satellite-based receivers103to obtain geographic coordinates from satellites125for determining current location and time. Further, the location can be determined by visual odometry, triangulation systems such as A-GPS, Cell of Origin, or other location extrapolation technologies.

In one embodiment, the UEs109may also be configured with various sensors (not shown for illustrative convenience) for acquiring and/or generating probe data and/or sensor data associated with a vehicle101, a driver, other vehicles, conditions regarding the driving environment or roadway, etc. For example, such sensors may be used as GPS receivers for interacting with the one or more satellites125to determine and track the current speed, position and location of a vehicle101travelling along a link or roadway. In addition, the sensors may gather tilt data (e.g., a degree of incline or decline of the vehicle during travel), motion data, light data, sound data, image data, weather data, temporal data and other data associated with the vehicles101and/or UEs109. Still further, the sensors may detect local or transient network and/or wireless signals, such as those transmitted by nearby devices during navigation of a vehicle along a roadway (Li-Fi, near field communication (NFC)) etc.

It is noted therefore that the above described data may be transmitted via communication network107as probe data (e.g., GPS probe data) according to any known wireless communication protocols. For example, each UE109, application111, user, and/or vehicle101may be assigned a unique probe identifier (probe ID) for use in reporting or transmitting said probe data collected by the vehicles101and/or UEs109. In one embodiment, each vehicle101and/or UE109is configured to report probe data as probe points, which are individual data records collected at a point in time that records telemetry data.

In one embodiment, the ETA platform105retrieves aggregated probe points gathered and/or generated by the vehicle sensors103and/or the UE109resulting from the travel of the UEs109and/or vehicles101on a road segment of a road network. In one instance, the probe database113stores a plurality of probe points and/or trajectories generated by different vehicle sensors103, UEs109, applications111, vehicles101, etc. over a period while traveling in a monitored area. A time sequence of probe points specifies a trajectory—i.e., a path traversed by a UE109, application111, vehicle101, etc. over the period.

FIG. 6is a diagram of a geographic database, according to one embodiment. In exemplary embodiments, probe data can be stored, associated with, and/or linked to the geographic database115or data thereof. In one embodiment, the geographic database115includes geographic data601used for (or configured to be compiled to be used for) mapping and/or navigation-related services, such as for personalized route determination, according to one embodiment. For example, the geographic database115includes node data records603, road segment or link data records605, POI data records607, probe data records609, other data records611, and indexes613. More, fewer or different data records can be provided. In one embodiment, the other data records611include cartographic (“carto”) data records, routing data, and maneuver data. In one embodiment, the probe data (e.g., collected from vehicles101) can be map-matched to respective map or geographic records via position or GPS data associations (such as using known or future map matching or geo-coding techniques), for example. In one embodiment, the indexes613may improve the speed of data retrieval operations in the geographic database115. The indexes613may be used to quickly locate data without having to search every row in the geographic database115every time it is accessed.

In various embodiments, the road segment data records605are links or segments representing roads, streets, paths, or lanes within multi-lane roads/streets/paths as can be used in the calculated route or recorded route information for determination of one or more personalized routes, according to exemplary embodiments. The node data records603are end points corresponding to the respective links or segments of the road segment data records605. The road segment data records605and the node data records603represent a road network, such as used by vehicles, cars, and/or other entities. Alternatively, the geographic database115can contain path segment and node data records or other data that represent pedestrian paths or areas in addition to or instead of the vehicle road record data, for example.

The road/link segments and nodes can be associated with attributes, such as geographic coordinates, street names, address ranges, speed limits, turn restrictions at intersections, lane number, and other navigation related attributes, as well as POIs, such as gasoline stations, hotels, restaurants, museums, stadiums, offices, automobile dealerships, auto repair shops, buildings, stores, parks, etc. The geographic database115can include data about the POIs and their respective locations in the POI data records607. The geographic database115can also include data about places, such as cities, towns, or other communities, and other geographic features, such as bodies of water, mountain ranges, etc. Such place or feature data can be part of the POI data records607or can be associated with POIs or POI data records607(such as a data point used for displaying or representing a position within a city).

In one embodiment, the geographic database115can include probe data collected from vehicles101(e.g., probe vehicles). As previously discussed, the probe data include probe points collected from the vehicles101and include telemetry data from the vehicles101can be used to indicate the traffic conditions at the location in a roadway from which the probe data was collected. In one embodiment, the probe data can be map-matched to the road network or roadways stored in the probe database113, the geographic database115, or a combination thereof. In one embodiment, the probe data can be further map-matched to individual lanes (e.g., any of the travel lanes, shoulder lanes, restricted lanes, service lanes, etc.) of the roadways for subsequent processing according to the various embodiments described herein. By way of example, the map-matching can be performed by matching the geographic coordinates (e.g., longitude and latitude) recorded for a probe-point against a roadway or lane within a multi-lane roadway corresponding to the coordinates.

The geographic database115can be maintained by a content provider121in association with the services platform117(e.g., a map developer). The map developer can collect geographic data to generate and enhance the geographic database115. There can be different ways used by the map developer to collect data. These ways can include obtaining data from other sources, such as municipalities or respective geographic authorities. In addition, the map developer can employ field personnel to travel by vehicle along roads throughout the geographic region to observe features and/or record information about them, for example. Also, remote sensing, such as aerial or satellite photography, can be used. In one embodiment, the data can include incident reports which can then be designated as ground truths for training a machine learning classifier to classify a traffic from probe data. Different sources of the incident report can be treated differently. For example, incident reports from municipal sources and field personnel can be treated as ground truths, while crowd-sourced reports originating from the general public may be excluded as ground truths.

As mentioned above, the geographic database115can be a master geographic database, but in alternate embodiments, the geographic database115can represent a compiled navigation database that can be used in or with end user devices (e.g., UEs109) to provide navigation-related functions. For example, the geographic database115can be used with the end user device UE109to provide an end user with navigation features. In such a case, the geographic database115can be downloaded or stored on the end user device UE109, such as in applications111, or the end user device UE109can access the geographic database115through a wireless or wired connection (such as via a server and/or the communication network107), for example.

The processes described herein for providing an estimated time of arrival with a uncertain starting location may be advantageously implemented via software, hardware (e.g., general processor, Digital Signal Processing (DSP) chip, an Application Specific Integrated Circuit (ASIC), Field Programmable Gate Arrays (FPGAs), etc.), firmware or a combination thereof. Such exemplary hardware for performing the described functions is detailed below.

A bus710includes one or more parallel conductors of information so that information is transferred quickly among devices coupled to the bus710. One or more processors702for processing information are coupled with the bus710.

Computer system700also includes a memory704coupled to bus710. The memory704, such as a random access memory (RAM) or other dynamic storage device, stores information including processor instructions providing an estimated time of arrival with a uncertain starting location. Dynamic memory allows information stored therein to be changed by the computer system700. RAM allows a unit of information stored at a location called a memory address to be stored and retrieved independently of information at neighboring addresses. The memory704is also used by the processor702to store temporary values during execution of processor instructions. The computer system700also includes a read only memory (ROM)706or other static storage device coupled to the bus710for storing static information, including instructions, that is not changed by the computer system700. Some memory is composed of volatile storage that loses the information stored thereon when power is lost. Also coupled to bus710is a non-volatile (persistent) storage device708, such as a magnetic disk, optical disk or flash card, for storing information, including instructions, that persists even when the computer system700is turned off or otherwise loses power.

Information, including instructions providing an estimated time of arrival with a uncertain starting location, is provided to the bus710for use by the processor from an external input device712, such as a keyboard containing alphanumeric keys operated by a human user, or a sensor. A sensor detects conditions in its vicinity and transforms those detections into physical expression compatible with the measurable phenomenon used to represent information in computer system700. Other external devices coupled to bus710, used primarily for interacting with humans, include a display device714, such as a cathode ray tube (CRT) or a liquid crystal display (LCD), or plasma screen or printer for presenting text or images, and a pointing device716, such as a mouse or a trackball or cursor direction keys, or motion sensor, for controlling a position of a small cursor image presented on the display714and issuing commands associated with graphical elements presented on the display714. In some embodiments, for example, in embodiments in which the computer system700performs all functions automatically without human input, one or more of external input device712, display device714and pointing device716is omitted.

Computer system700also includes one or more instances of a communications interface770coupled to bus710. Communication interface770provides a one-way or two-way communication coupling to a variety of external devices that operate with their own processors, such as printers, scanners and external disks. In general the coupling is with a network link778that is connected to a local network780to which a variety of external devices with their own processors are connected. For example, communication interface770may be a parallel port or a serial port or a universal serial bus (USB) port on a personal computer. In some embodiments, communications interface770is an integrated services digital network (ISDN) card or a digital subscriber line (DSL) card or a telephone modem that provides an information communication connection to a corresponding type of telephone line. In some embodiments, a communication interface770is a cable modem that converts signals on bus710into signals for a communication connection over a coaxial cable or into optical signals for a communication connection over a fiber optic cable. As another example, communications interface770may be a local area network (LAN) card to provide a data communication connection to a compatible LAN, such as Ethernet. Wireless links may also be implemented. For wireless links, the communications interface770sends or receives or both sends and receives electrical, acoustic or electromagnetic signals, including infrared and optical signals, that carry information streams, such as digital data. For example, in wireless handheld devices, such as mobile telephones like cell phones, the communications interface770includes a radio band electromagnetic transmitter and receiver called a radio transceiver. In certain embodiments, the communications interface770enables connection to the communication network105providing an estimated time of arrival with a uncertain starting location to the UE109.

Network link778typically provides information communication using transmission media through one or more networks to other devices that use or process the information. For example, network link778may provide a connection through local network780to a host computer782or to equipment784operated by an Internet Service Provider (ISP). ISP equipment784in turn provides data communication services through the public, world-wide packet-switching communication network of networks now commonly referred to as the Internet790.

A computer called a server host792connected to the Internet hosts a process that provides a service in response to information received over the Internet. For example, server host792hosts a process that provides information representing video data for presentation at display714. It is contemplated that the components of system can be deployed in various configurations within other computer systems, e.g., host782and server792.

In one embodiment, the chip set800includes a communication mechanism such as a bus801for passing information among the components of the chip set800. A processor803has connectivity to the bus801to execute instructions and process information stored in, for example, a memory805. The processor803may include one or more processing cores with each core configured to perform independently. A multi-core processor enables multiprocessing within a single physical package. Examples of a multi-core processor include two, four, eight, or greater numbers of processing cores. Alternatively or in addition, the processor803may include one or more microprocessors configured in tandem via the bus801to enable independent execution of instructions, pipelining, and multithreading. The processor803may also be accompanied with one or more specialized components to perform certain processing functions and tasks such as one or more digital signal processors (DSP)807, or one or more application-specific integrated circuits (ASIC)809. A DSP807typically is configured to process real-world signals (e.g., sound) in real-time independently of the processor803. Similarly, an ASIC809can be configured to performed specialized functions not easily performed by a general purposed processor. Other specialized components to aid in performing the inventive functions described herein include one or more field programmable gate arrays (FPGA) (not shown), one or more controllers (not shown), or one or more other special-purpose computer chips.

The processor803and accompanying components have connectivity to the memory805via the bus801. The memory805includes both dynamic memory (e.g., RAM, magnetic disk, writable optical disk, etc.) and static memory (e.g., ROM, CD-ROM, etc.) for storing executable instructions that when executed perform the inventive steps described herein to provide an estimated time of arrival with a uncertain starting location. The memory805also stores the data associated with or generated by the execution of the inventive steps.

FIG. 9is a diagram of exemplary components of a mobile terminal (e.g., handset) capable of operating in the system ofFIG. 1, according to one embodiment. Generally, a radio receiver is often defined in terms of front-end and back-end characteristics. The front-end of the receiver encompasses all of the Radio Frequency (RF) circuitry whereas the back-end encompasses all of the base-band processing circuitry. Pertinent internal components of the telephone include a Main Control Unit (MCU)903, a Digital Signal Processor (DSP)905, and a receiver/transmitter unit including a microphone gain control unit and a speaker gain control unit. A main display unit907provides a display to the user in support of various applications and mobile station functions that offer automatic contact matching. An audio function circuitry909includes a microphone911and microphone amplifier that amplifies the speech signal output from the microphone911. The amplified speech signal output from the microphone911is fed to a coder/decoder (CODEC)913.

A radio section915amplifies power and converts frequency in order to communicate with a base station, which is included in a mobile communication system, via antenna917. The power amplifier (PA)919and the transmitter/modulation circuitry are operationally responsive to the MCU903, with an output from the PA919coupled to the duplexer921or circulator or antenna switch, as known in the art. The PA919also couples to a battery interface and power control unit920.

The encoded signals are then routed to an equalizer925for compensation of any frequency-dependent impairments that occur during transmission though the air such as phase and amplitude distortion. After equalizing the bit stream, the modulator927combines the signal with a RF signal generated in the RF interface929. The modulator927generates a sine wave by way of frequency or phase modulation. In order to prepare the signal for transmission, an up-converter931combines the sine wave output from the modulator927with another sine wave generated by a synthesizer933to achieve the desired frequency of transmission. The signal is then sent through a PA919to increase the signal to an appropriate power level. In practical systems, the PA919acts as a variable gain amplifier whose gain is controlled by the DSP905from information received from a network base station. The signal is then filtered within the duplexer921and optionally sent to an antenna coupler935to match impedances to provide maximum power transfer. Finally, the signal is transmitted via antenna917to a local base station. An automatic gain control (AGC) can be supplied to control the gain of the final stages of the receiver. The signals may be forwarded from there to a remote telephone which may be another cellular telephone, other mobile phone or a land-line connected to a Public Switched Telephone Network (PSTN), or other telephony networks.

Voice signals transmitted to the mobile station901are received via antenna917and immediately amplified by a low noise amplifier (LNA)937. A down-converter939lowers the carrier frequency while the demodulator941strips away the RF leaving only a digital bit stream. The signal then goes through the equalizer925and is processed by the DSP905. A Digital to Analog Converter (DAC)943converts the signal and the resulting output is transmitted to the user through the speaker945, all under control of a Main Control Unit (MCU)903—which can be implemented as a Central Processing Unit (CPU) (not shown).

The MCU903receives various signals including input signals from the keyboard947. The keyboard947and/or the MCU903in combination with other user input components (e.g., the microphone911) comprise a user interface circuitry for managing user input. The MCU903runs a user interface software to facilitate user control of at least some functions of the mobile station901to provide an estimated time of arrival with a uncertain starting location. The MCU903also delivers a display command and a switch command to the display907and to the speech output switching controller, respectively. Further, the MCU903exchanges information with the DSP905and can access an optionally incorporated SIM card949and a memory951. In addition, the MCU903executes various control functions required of the station. The DSP905may, depending upon the implementation, perform any of a variety of conventional digital processing functions on the voice signals. Additionally, DSP905determines the background noise level of the local environment from the signals detected by microphone911and sets the gain of microphone911to a level selected to compensate for the natural tendency of the user of the mobile station901.

The CODEC913includes the ADC923and DAC943. The memory951stores various data including call incoming tone data and is capable of storing other data including music data received via, e.g., the global Internet. The software module could reside in RAM memory, flash memory, registers, or any other form of writable computer-readable storage medium known in the art including non-transitory computer-readable storage medium. For example, the memory device951may be, but not limited to, a single memory, CD, DVD, ROM, RAM, EEPROM, optical storage, or any other non-volatile or non-transitory storage medium capable of storing digital data.

An optionally incorporated SIM card949carries, for instance, important information, such as the cellular phone number, the carrier supplying service, subscription details, and security information. The SIM card949serves primarily to identify the mobile station901on a radio network. The card949also contains a memory for storing a personal telephone number registry, text messages, and user specific mobile station settings.