Determining location and direction of travel using map vector constraints

• US 9,933,527 B2
• Filed: 08/29/2016
• Issued: 04/03/2018
• 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:
  US15/250,792
• Publication Number:
  US 20170052031A1
• Time in Patent Office: 582 Days
• Field of Search: 707748
• 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:

initializing, by a computing device, a particle filter using a first set of state measurements, the initializing including selecting a first set of particles based at least in part on a satellite-based position measurement;

assigning, by the computing device, each particle in the first set of particles to a road link of a road network based on a distance of the road link from the satellite-based position measurement and an uncertainty in the satellite-based position measurement;

propagating, by the computing device, the particles along their respective road links;

calculating, by the computing device, a second set of state measurements for the propagated particles;

calculating, by the computing device, a particle weight for each propagated particle based on the second set of state measurements;

resampling, by the computing device, the particles, the resampling including selecting a subset of the set of particles based on the particle weights;

computing, by the computing device, a particle filter solution based on a union of particles in the subset of particles that were propagated along two or more road links; and

calculating, by the computing device, a map-match based on the particle filter solution to determine a location and direction of the computing device,

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

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

3. The method of claim 1, wherein calculating a map-match based on the particle filter solution further comprises:

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.

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

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

6. The method of claim 1, wherein propagating the particles along the road links 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 the road links and across intersections using the process noise value.

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

initializing a particle filter using a first set of state measurements, the initializing including selecting a first set of particles based at least in part on a satellite-based position measurement;

assigning each particle in the first set of particles to a road link of a road network based on a distance of the road link from the satellite-based position measurement and an uncertainty in the satellite-based position measurement;

propagating the particles along their respective road links;

calculating a second set of state measurements for the propagated particles;

calculating a particle weight for each propagated particle based on the second set of state measurements;

resampling the particles, the resampling including selecting a subset of the set of particles based on the particle weights;

computing a particle filter solution based on a union of particles in the subset of particles that were propagated along two or more road links; and

calculating, by the computing device, a map-match based on the particle filter solution to determine a location and direction of the computing device.

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

9. The computing device of claim 7, wherein calculating a map-match based on the particle filter solution further comprises:

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.

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

11. The computing device of claim 10, wherein the relative likelihood value for a jth particle w_j is given by

12. The computing device of claim 7, wherein propagating the particles along the road 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 the road links and across intersections using the process noise value.

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

initializing a particle filter of the computing device using a first set of state measurements, the initializing including selecting a first set of particles based at least in part on a satellite-based position measurement;

assigning each particle in the first set of particles to a road link of a road network based on a distance of the road link from the satellite-based position measurement and an uncertainty in the satellite-based position measurement;

propagating the particles along their respective road links;

calculating a second set of state measurements for the propagated particles;

calculating a particle weight for each propagated particle based on the second set of state measurements;

resampling the particles, the resampling including selecting a subset of the set of particles based on the particle weights;

computing a particle filter solution based on a union of particles in the subset of particles that were propagated along two or more road links; and

calculating, by the computing device, a map-match based on the particle filter solution to determine a location and direction of the computing device.

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

15. The computer-readable storage medium of claim 13, wherein calculating a map-match based on the particle filter solution further comprises:

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.