Determining location and direction of travel using map vector constraints

• US 9,429,437 B2
• Filed: 06/07/2013
• Issued: 08/30/2016
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: MacGougan, Glenn Donald, Rhee, Stephen J., Mayor, Robert, Huang, Ronald K.
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/913,006
• Publication Number:
  US 20130346423A1
• Time in Patent Office: 1,180 Days
• Field of Search: 707/748
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G01S 19/52 Determining velocity
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Systems, methods, and computer program products for determining the location and direction of travel of a mobile device using map vector constraints is disclosed.

Claims

1. A method comprising:

performing, by a particle filter running on a computing device, particle seeding on an outdoor road network based on a satellite-based position measurement, wherein the particle seeding includes;

determining a measure of position uncertainty associated with the satellite-based position measurement;

determining a distance based at least in part on the measure of position uncertainty;

selecting a set of one or more road links in the road network that are within the distance of the satellite-based position measurement;

assigning a particle to each road link in the set of one or more road links;

determining a score for each assigned particle; and

determining a relative likelihood value for each assigned particle;

calculating, by the computing device, relative particle weights;

resampling, by the computing device, the particles;

computing, by the computing device, a particle filter solution;

comparing, by the computing device, the particle filter solution with an instantaneous matcher; and

calculating, by the computing device, a map-match given the particles,

wherein the method is performed by one or more hardware processors of the computing device.

2. The method of claim 1, wherein selecting a set of one or more road links in the road network that are within a distance of the satellite-based position measurement and assigning a particle to each road link, further comprises:

determining a closest point on each road link in the set of one or more road links based on the distance and a direction of travel for the closest point; and

assigning a particle to the closest point.

3. The method of claim 2, wherein the set of one or more road links is selected based on road width and changes in direction to the satellite-based position measurement.

4. The method of claim 1, further comprising:

determining, by the computing device, a ratio of a highest to a second highest relative likelihood values;

determining, by the computing device, that the ratio exceeds a threshold; and

responsive to the determining, generating an instantaneous map-match solution.

5. The method of claim 1, wherein the score is determined from a multivariate normal distribution given by

6. The method of claim 5, wherein the relative likelihood value for a jth particle wj is given by

7. The method of claim 1, wherein propagating the particles along the road network further comprises:

determining, by the computing device, a motion context from a sensor of the computing device;

determining, by the computing device, a process noise value based on the motion context; and

propagating, by the computing device, the particles along road links and across intersections using the process noise value.

8. The method of claim 1, wherein computing a particle filter solution includes computing the particle filter solution based on a union of particles propagated along two or more road links.

9. A computing device comprising:

one or more processors;

memory coupled to the one or more processors and configured to store instructions, which, when executed by the one or more processors, causes the one or more processors to perform operations comprising;

particle seeding for a particle filter on an outdoor road network based on a satellite-based position measurement, wherein the particle seeding includes;

determining a measure of position uncertainty associated with the satellite-based position measurement;

determining a distance based at least in part on the measure of position uncertainty;

selecting a set of one or more road links in the road network that are within the distance of the satellite-based position measurement;

assigning a particle to each road link in the set of one or more road links;

determining a score for each assigned particle; and

determining a relative likelihood value for each assigned particle;

propagating the particles along the road network;

calculating relative particle weights;

resampling the particles;

computing a particle filter solution;

comparing the particle filter solution with an instantaneous matcher; and

calculating a map-match given the particles.

10. The computing device of claim 9, wherein selecting a set of one or more road links in the road network that are within a distance of the satellite-based position measurement and assigning a particle to each road link, further comprises:

determining a closest point on each road link in the set of one or more road links based on the distance and a direction of travel for the closest point; and

assigning a particle to the closest point.

11. The computing device of claim 9, wherein the set of one or more road links is selected based on road width and changes in direction to the satellite-based position measurement.

12. The computing device of claim 9, the operations further comprising:

determining a ratio of a highest to a second highest relative likelihood values;

determining that the ratio exceeds a threshold; and

responsive to the determining, generating an instantaneous map-match solution.

13. The computing device of claim 9, wherein the score is determined from a multivariate normal distribution given by

14. The computing device of claim 13, wherein the relative likelihood value for a jth particle wj is given by

15. The computing device of claim 9, wherein propagating the particles along the road network further comprises:

determining a motion context from a sensor of the computing device;

determining a process noise value based on the motion context; and

propagating the particles along road links and across intersections using the process noise value.

16. The computing device of claim 9, wherein computing a particle filter solution includes computing the particle filter solution based on a union of particles propagated along two or more road links.

17. A non-transitory, computer-readable storage medium having instructions stored thereon, which, when executed by one or more processors, cause the one or more processors to perform operations comprising:

particle seeding for a particle filter on an outdoor road network based on a satellite-based position measurement, wherein the particle seeding includes;

determining a measure of position uncertainty associated with the satellite-based position measurement;

determining a distance based at least in part on the measure of position uncertainty;

selecting a set of one or more road links in the road network that are within the distance of the satellite-based position measurement;

assigning a particle to each road link in the set of one or more road links;

determining a score for each assigned particle; and

determining a relative likelihood value for each assigned particle;

propagating the particles along the road network;

calculating relative particle weights;

resampling the particles;

computing a particle filter solution;

comparing the particle filter solution with an instantaneous matcher; and

calculating a map-match given the particles.

18. The computer-readable storage medium of claim 17, wherein selecting a set of one or more road links in the road network that are within a distance of the satellite-based position measurement and assigning a particle to each road link, further comprises:

determining a closest point on each road link in the set of one or more road links based on the distance and a direction of travel for the closest point; and

assigning a particle to the closest point.

19. The computer-readable storage medium of claim 17, wherein the set of one or more road links is selected based on road width and changes in direction to the satellite-based position measurement.

20. The computer-readable storage medium of claim 17, the operations further comprising:

determining a ratio of a highest to a second highest relative likelihood values;

determining that the ratio exceeds a threshold; and

responsive to the determining, generating an instantaneous map-match solution.