Probabilistic map matching from a plurality of observational and contextual factors
First Claim
1. A method comprising:
- receiving, via one or more communication connections of a computing device, first location data from a location measuring sensor and receiving second location data from the location measuring sensor;
in response to receiving at least one of the first location data or the second location data, determining, by one or more processors associated with the computing device, multiple routes between a first point corresponding to the first location data and a second point corresponding to the second location data;
assigning, by the one or more processors and to each of the multiple routes, a relative probability that each of the multiple routes corresponds to a location of the location measuring sensor based on a combination of a plurality of factors, the plurality of factors comprising;
a comparison between a direct distance between the first point and the second point and an actual distance between the first point and the second point for each of the multiple routes, the direct distance comprising a distance of a straight line spanning between the first point and the second point, the actual distance comprising a distance to be traveled using a route of the multiple routes between the first point and the second point; and
at least one of a total distance efficiency or a total time efficiency of a first route of the multiple routes relative to a second route of the multiple routes; and
predicting, by the one or more processors, that an entity associated with the location measuring sensor is traversing one of the multiple routes based, at least in part, on the relative probabilities assigned to each of the multiple routes.
2 Assignments
0 Petitions
Accused Products
Abstract
Systems, methods, and devices are described for implementing map matching techniques relating to measured location data. Probabilistic models, including temporal Bayesian network models and Hidden Markov Models, may be used for combining multiple classes of evidence relating to potential locations of points traversed on routes over time. Multiple route segments and overall routes may be maintained under relative uncertainty as candidates. The candidate route segments and overall routes may then be reduced into a smaller number of candidates or a single most likely route as a trip progresses. As the trip progresses, route segments in proximity to each location point are identified and candidate matches are determined. A probability of an entity traversing a candidate match at a given time and a probability of an entity traversing between a first candidate match at a first time and a second candidate match at a second time are determined based on a plurality of factors. Different modalities may be used to measure and transmit the location data.
37 Citations
20 Claims
-
1. A method comprising:
-
receiving, via one or more communication connections of a computing device, first location data from a location measuring sensor and receiving second location data from the location measuring sensor; in response to receiving at least one of the first location data or the second location data, determining, by one or more processors associated with the computing device, multiple routes between a first point corresponding to the first location data and a second point corresponding to the second location data; assigning, by the one or more processors and to each of the multiple routes, a relative probability that each of the multiple routes corresponds to a location of the location measuring sensor based on a combination of a plurality of factors, the plurality of factors comprising; a comparison between a direct distance between the first point and the second point and an actual distance between the first point and the second point for each of the multiple routes, the direct distance comprising a distance of a straight line spanning between the first point and the second point, the actual distance comprising a distance to be traveled using a route of the multiple routes between the first point and the second point; and at least one of a total distance efficiency or a total time efficiency of a first route of the multiple routes relative to a second route of the multiple routes; and predicting, by the one or more processors, that an entity associated with the location measuring sensor is traversing one of the multiple routes based, at least in part, on the relative probabilities assigned to each of the multiple routes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A system comprising:
-
a memory communicatively coupled to one or more processors; one or more computer-executable instructions stored in the memory that when executed by the one or more processors cause the system to perform operations comprising; determining one or more routes between a first point corresponding to a first location and a second point corresponding to a second location; and assigning, to each of the one or more routes, a relative probability that an entity is currently traversing each of the one or more routes based on a plurality of factors, at least one of the plurality of factors comprising historical data associated with the entity traversing the one or more routes, the assigning comprising; analyzing the historical data to identify a particular route between the first point and the second point that the entity has traversed at a previous time; and based at least in part on identifying the particular route between the first point and the second point that the entity has traversed at the previous time, assigning to the particular route the relative probability that the entity is currently traversing the particular route. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. One or more computer storage media including computer-executable instructions that, when executed by one or more processors, direct the one or more processors to perform operations comprising:
-
determining one or more routes between a first point corresponding to a first location and a second point corresponding to a second location; assigning, to each of the one or more routes, a relative probability that an entity is traversing each of the one or more routes based on a combination of a plurality of factors, at least one of the plurality of factors comprising a traffic condition of the one or more routes; calculating a direct distance between the first point and the second point, the direct distance comprising a distance of a straight line spanning between the first point and the second point; and disregarding a particular route of the one or more routes when a difference between the direct distance and an actual distance of the particular route exceeds a predetermined threshold, the actual distance comprising a distance to be traveled using the particular route between the first point and the second point. - View Dependent Claims (19, 20)
-
Specification