Probabilistic map matching from a plurality of observational and contextual factors

• US 8,645,061 B2
• Filed: 06/16/2010
• Issued: 02/04/2014
• Est. Priority Date: 06/16/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Newson, Paul E., Krumm, John C., Horvitz, Eric J.
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): Do, Truc M
• Application Number:
  US12/816,496
• Publication Number:
  US 20110313648A1
• Time in Patent Office: 1,329 Days
• Field of Search: 701/446, 701/454, 701/460, 701/469
• US Class Current: 701/469
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

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.

Claims

1. A system comprising:

a memory communicatively coupled to a processor;

one or more computer-executable instructions stored in the memory that cause the processor to perform operations comprising;

determining an uncertainty of a measured geographic location;

selecting, based at least partly on the determined uncertainty, one or more sensors to collect one or more time-adjacent points each corresponding to the measured geographic location;

determining, for each time-adjacent point, zero or more candidate matches in proximity to the geographic location; and

computing a transition probability of moving from a first candidate match corresponding to a first point to a second candidate match corresponding to a second point subsequent in time to the first point based on one or more factors.

2. The system of claim 1, wherein the one or more factors relate to at least one of the following:

a distance, a time, a velocity, historical information known about an entity, a network, or behavior in the network, an efficiency of a route, a complexity of a route through the network, and one or more points between the first point and the second point.

3. The system of claim 1, wherein the operations further comprise computing a measurement probability for each candidate match that the candidate match corresponds to its respective time-adjacent point, the measurement probability representing a likelihood that the candidate match either will be or has previously been traversed at the respective time-adjacent point.

4. The system of claim 3, wherein the measurement probability is computed based on the one or more factors.

5. The system of claim 1, wherein the operations are performed using a probabilistic model.

6. The system of claim 1, wherein the transition probability represents a likelihood that an entity traveled from the first candidate match to the second candidate match, the first candidate match and the second candidate match each comprising a road segment in proximity to their respective geographic locations.

7. The system of claim 1, wherein the operations further comprise decreasing the transition probability when a hypothesized route deviates from a predicted route.

8. The system of claim 1, wherein the operations further comprise disregarding time-adjacent points that cause a lack of a path between a first time-adjacent point and a subsequent time-adjacent point.

9. The system of claim 1, wherein the first point and the second point are measured utilizing the one or more sensors or other information sources.

10. The system of claim 1, wherein the one or more factors include a comparison between a direct distance between the first point and the second point and a total distance for each of one or more routes.

11. The system of claim 10, wherein the operations further comprise disregarding a particular one of the one or more routes when a difference between the direct distance and a total distance of the particular route exceeds a predetermined threshold.

12. The system of claim 1, wherein the one or more factors include a difference between a time of an optimal route between the first point and the second point and a measured time taken between the first point and the second point.

13. The system of claim 1, wherein the one or more factors include historical information known about an entity, historical information known about an environment or behavior in the environment, or both.

14. The system of claim 1, wherein the one or more factors include an efficiency of a route between the first point and the second point.

15. The system of claim 1, wherein the one or more factors include a complexity of a route through a network or a velocity of an entity.

16. The system of claim 1, wherein the operations further comprise:

determining one or more routes between the first point and the second point; and

assigning a relative probability to each of the one or more routes based on the one or more factors.

17. The system of claim 16, wherein the relative probability of a route being selected is inversely related to a distance between a direct distance and a total distance of the route.

18. A method comprising:

under a control of one or more processors,

determining an uncertainty of a location point;

estimating a potential reduction in the uncertainty that would result from measuring one or more additional location points using one of a plurality of different sensors;

estimating a potential cost of measuring the one or more additional location points using one of the plurality of sensors;

selecting one or more sensors from the plurality of sensors based on the estimated potential reduction in uncertainty and the estimated potential cost; and

collecting one or more time-adjacent location points using the one or more selected sensors.

19. The method of claim 18, wherein the potential cost relates to time, money, energy, or a combination thereof.

20. The method of claim 18, wherein the location point is a previous time-adjacent location point or a predicted location.

21. The method of claim 18, further comprising adjusting a sample rate for the selected one or more sensors based on a type of sensor selected and an environment in which the one or more time-adjacent location points are collected.

22. A method comprising:

under a control of one or more processors,

receiving a plurality of time-adjacent points, each of the plurality of time-adjacent points representing a geographic location at a different time;

determining a route based on one or more route segments in proximity to the plurality of time-adjacent points;

determining the route without considering one or more time-adjacent points of the plurality of time adjacent points; and

in response to determining the route without considering the one or more time-adjacent points, deleting the one or more time-adjacent points.

23. The method of claim 22, further comprising deleting each of the plurality of time-adjacent points that is not needed to reconstruct the route.

24. The method of claim 22, further comprising deleting a particular time-adjacent point of the plurality of time-adjacent points in response to determining that the particular time-adjacent point either adds no value in computing the route or makes a correct determination of the route more difficult.