System and method for localization and tracking

• US 10,386,493 B2
• Filed: 09/30/2016
• Issued: 08/20/2019
• Est. Priority Date: 10/01/2015
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Irish, Andrew, Madhow, Upamanyu
• Primary Examiner(s): Liu, Harry K
• Application Number:
  US15/281,997
• Publication Number:
  US 20170299727A1
• Time in Patent Office: 1,054 Days
• Field of Search: 34235725
• CPC Class Codes: G01S 19/22 Multipath-related issues
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G01S 19/428 using multipath or indirect path propagation signals in position determination

Abstract

A method of determining location of a user device includes receiving global navigation satellite system (GNSS) fix data that represents GNSS calculated position of the user device, receiving signal strength data associated with each satellite communicating with the user device, and receiving satellite data regarding locations of satellites. The method further includes retrieving satellite blocking values from a cache that describe a likelihood of a satellite signal being blocked at a plurality of possible locations. A non-linear filter, implemented by one or more processors, is applied to the GNSS fix data, signal strength data, and satellite blocking values to generate an updated position estimate of the user device.

Claims

1. A localization system comprising:

a memory manager to load data values indicative of a satellite signal being blocked at one or more locations into a cache; and

a non-linear filter, including one or more processors, to;

receive from a user device a first position estimate and a signal strength data associated with at least one satellite; and

generate a second position estimate based on the first position estimate, the signal strength data, and the stored data values indicative of the at least one satellite being blocked at one or more locations;

wherein the data values indicative of a satellite signal being blocked at one or more locations is comprised of a plurality of quantized ephemeris bins that represent possible locations of each of the plurality of satellites, wherein each quantized ephemeris bin includes probabilities of the satellite being blocked with respect to each of the plurality of possible locations.

2. The localization system of claim 1, wherein the memory manager distributes at least a portion of the data values indicative of a satellite signal being blocked at one or more locations to a local cache maintained locally by the user device.

3. The localization system of claim 2, wherein the cache distributed by the memory manager to the user device includes data values associated only with those satellites likely to be visible by the user device.

4. The localization system of claim 1, wherein the non-linear filter is configured to utilize a signal-to-noise ratio (SNR) model to determine the likelihood of a particle being located at a particular position given the observed signal strength from each of the plurality of satellites and data values indicative of a satellite signal being blocked from the cache.

5. The localization system of claim 4, wherein the user device implements the non-linear filter locally.

6. The localization system of claim 1, wherein the SNR model utilizes first order reflections to further refine the likelihood of a particle being located at a particular position.

7. The localization system of claim 1, wherein the cache is maintained remotely from the user device.

9. The localization system of claim 1, wherein the memory manager selects the data values to load into the cache based on the first position estimate received from the user device.

8. A localization system comprising:

a memory manager to load data values indicative of a satellite signal being blocked at one or more locations into a cache; and

a non-linear filter, including one or more processors, to;

receive from a user device a first position estimate and a signal strength data associated with at least one satellite; and

generate a second position estimate based on the first position estimate, the signal strength data, and the stored data values indicative of the at least one satellite being blocked at one or more locations;

wherein the SNR model utilizes first order reflections to further refine the likelihood of a particle being located at a particular position; and

wherein the measured signal strength is identified as a first-order reflection in response to the measured signal strength exceeding a threshold and in response to the data value indicative of a satellite signal being blocked indicating a high likelihood that the satellite signal between the plurality of possible locations and the satellite are blocked.

10. A method of determining location of a user device, the method comprising:

receiving global navigation satellite system (GNSS) fix data that represents GNSS calculated position of the user device;

receiving signal strength data associated with each satellite communicating with the user device;

receiving satellite data regarding locations of satellites;

retrieving satellite blocking values from a cache that describe a likelihood of a satellite signal being blocked at a plurality of possible locations; and

applying, by one or more processors, a non-linear filter to the GNSS fix data, signal strength data, and satellite blocking values to generate an updated position estimate of the user device;

wherein the cache is comprised of a plurality of quantized ephemeris bins that represent possible locations of each of the plurality of satellites, wherein each quantized ephemeris bin includes probabilities of the satellite being blocked with respect to each of the plurality of particles.

11. The method of claim 10, wherein the non-linear filter includes, at least in part, an SNR measurement model to assign weights to each of the plurality of particles representing possible user device locations included in a particle set based on the retrieved satellite blocking values retrieved from the cache and the received signal strength data.

12. The method of claim 10, wherein the SNR model utilizes first order reflections to further refine the likelihood of a particle being located at a particular position.

13. A method of determining location of a user device, the method comprising:

receiving global navigation satellite system (GNSS) fix data that represents GNSS calculated position of the user device;

receiving signal strength data associated with each satellite communicating with the user device;

receiving satellite data regarding locations of satellites;

retrieving satellite blocking values from a cache that describe a likelihood of a satellite signal being blocked at a plurality of possible locations; and

applying, by one or more processors, a non-linear filter to the GNSS fix data, signal strength data, and satellite blocking values to generate an updated position estimate of the user device;

wherein the SNR model utilizes first order reflections to further refine the likelihood of a particle being located at a particular position; and

wherein the measured signal strength is identified as a first-order reflection in response to the measured signal strength exceeding a threshold and in response to the satellite blocking values indicating a high likelihood that the satellite signal between the plurality of possible locations and the satellite are blocked.

14. A method of determining location of a user device, the method comprising:

receiving global navigation satellite system (GNSS) fix data that represents GNSS calculated position of the user device;

receiving signal strength data associated with each satellite communicating with the user device;

receiving satellite data regarding locations of satellites; and

applying, by one or more processors, a non-linear filter to the GNSS fix data and signal strength data to generate an updated position estimate of the user device, wherein the non-linear filter utilizes a signal-to-noise ratio (SNR) model to assign weights to each of a plurality of particles representing possible user device locations included in a particle set based on calculated likelihoods of satellite signals being blocked at each of the plurality of particles and the received signal strength data, wherein the SNR model utilizes first order reflections to further refine the likelihood of a particle being located at a particular position.

15. The method of claim 14, wherein the measured signal strength is identified as a first-order reflection in response to the measured signal strength exceeding a threshold and in response to satellite blocking values indicating a high likelihood that the satellite signal between the plurality of possible locations and the satellite are blocked.

16. The method of claim 14, wherein the satellite blocking values indicating a likelihood of the satellite signal being blocked is calculated using ray tracing from the location of each particle to each of the plurality of satellites.

17. The method of claim 14, wherein the satellite blocking values are fetched from a cache populated with pre-calculated likelihoods of satellite signals being blocked from a plurality of possible locations.

18. A computer readable medium containing program instructions for determining location of a user device, wherein execution of the program instructions by one or more processors of a computer system causes the one or more processors to carry out the steps of:

receiving global navigation satellite system (GNSS) fix data that represents GNSS calculated position of the user device;

receiving signal strength data associated with each satellite communicating with the user device;

receiving satellite data regarding locations of satellites;

retrieving satellite blocking values from a cache that describe a probability of a satellite signal being blocked at a plurality of possible locations; and

applying, by one or more processors, a non-linear filter to the GNSS fix data, signal strength data, and shadow matching data to generate an updated position estimate of the user device,

wherein the cache is comprised of a plurality of quantized ephemeris bins that represent possible locations of each of the plurality of satellites, wherein each quantized ephemeris bin includes probabilities of the satellite being blocked with respect to each of the plurality of particles.

19. The computer readable medium of claim 18, wherein the non-linear filter includes, at least in part, an SNR measurement model to assign weights to each of the plurality of particles representing possible user device locations included in a particle set based on the retrieved satellite blocking values retrieved from the cache and the received signal strength data.

20. The computer readable medium of claim 19, wherein the SNR measurement model utilizes first order reflections to further refine the likelihood of a particle being located at a particular position.