Probabilistic Map Matching From A Plurality Of Observational And Contextual Factors

• US 20110313648A1
• Filed: 06/16/2010
• Published: 12/22/2011
• 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.
• Granted Patent: US 8,645,061 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 method 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 a relative probability to each of the one or more routes based on a combination of a plurality of factors.

2. The method of claim 1, wherein the first point and the second point are measured utilizing one of a plurality of types of sensors or other information sources.

3. The method of claim 1, wherein the relative probability is calculated based on the plurality of factors using a probabilistic model.

4. The method of claim 1, wherein one of the plurality of factors is a comparison between a direct distance between the first point and the second point and a total distance for each of the one or more routes.

5. The method of claim 4, wherein the relative probability of a route being selected is inversely related to a distance between the direct distance and the total distance.

6. The method of claim 4, further comprising disregarding a particular one of the one or more routes when a difference between the direct distance and a total distance of that route exceeds a predetermined threshold.

7. The method of claim 1, wherein one of the plurality of factors is 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.

8. The method of claim 1, wherein one of the plurality of factors is historical information known about an entity and/or historical information known about an environment or behavior in the environment.

9. The method of claim 1, wherein one of the plurality of factors is an efficiency of a route between the first point and the second point

10. The method of claim 1, wherein one of the plurality of factors is a complexity of a route through a network or a velocity of an entity.

11. 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;

collecting a plurality of time-adjacent points each corresponding to a 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 a combination of a plurality of factors.

12. The system of claim 11, wherein at least one of the plurality of factors relates to distance, time, velocity, historical information known about an entity, a network, or behavior in that network, an efficiency of a route, a complexity of a route through the network, or one or more points between the first point and the second point.

13. The system of claim 11, 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.

14. The system of claim 13, wherein the measurement probability is computed based on the combination of the plurality of factors.

15. The system of claim 11, wherein the operations are performed using a probabilistic model.

16. The system of claim 11, 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.

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

18. The system of claim 11, 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.

19. A method comprising:

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.

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

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

22. The method of claim 19, 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.

23. A method comprising:

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

determining a route taken based on route segments in proximity to the time-adjacent points; and

deleting one or more of the plurality of time-adjacent points if the route can be determined without considering the deleted time-adjacent points.

24. The method of claim 23, wherein the deleting further comprises deleting each of the plurality of time-adjacent points that is not needed to reconstruct the route taken.

25. The method of claim 23, wherein the deleting further comprises deleting a particular one of the plurality of time-adjacent points if it is determined that the time-adjacent point either adds no value in computing the route or makes a correct determination of the route more difficult.