Localization and tracking using location, signal strength, and pseudorange data

Patent metadata

Field	Value
Publication number	US-9766349-B1
Application number	US-201615396297-A
Country	US
Kind code	B1
Filing date	Dec 30, 2016
Priority date	Sep 14, 2016
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

A localization server improves position estimates of global navigation satellite systems (GNSS) using probabilistic shadow matching and pseudorange matching is disclosed herein. The localization server may utilize one or more of the following information: the locations of the satellites, the GNSS receiver's location estimate and associated estimated uncertainty, the reported pseudoranges of the satellites, the GNSS estimated clock bias, the SNRs of the satellites, and 3D environment information regarding the location of the receiver. The localization server utilizes a Bayesian framework to calculate an improved location estimate using the GNSS location fixes, pseudorange information, and satellite SNRs thereby improving localization and tracking for a user device.

First claim

What is claimed is:

1. A method for determining a location of a user device, the method comprising:
receiving a position fix location calculated by a GNSS receiver included in the user device, wherein the position fix location approximates an actual position of the user device and is calculated by the GNSS receiver using data received from a satellite system, wherein the satellite system includes a plurality of satellites;
receiving, from the GNSS receiver, signal strength data associated with at least one satellite of the satellite system;
receiving, from the GNSS receiver, pseudorange data associated with the at least one satellite of the satellite system;
accessing map information describing an environment surrounding the position fix location;
calculating a probabilistic shadow matching estimate for each of a plurality of hypothesized user device locations utilizing the signal strength data, the pseudorange data, and the map information, wherein each of the probabilistic shadow matching estimates is determined in part by a pseudorange measurement model; and
calculating, using a non-linear filter, an updated position estimate of the user device based at least in part on the calculated probabilistic shadow matching estimates.

2. The method of claim 1 , wherein each of the probabilistic shadow matching estimates represents a likelihood of the received signal strength data and a likelihood of received pseudorange data as a function of hypothesized user device locations within the environment described by the received map information.

3. The method of claim 1 , wherein, the pseudorange measurement model further comprising comprises:
determining, for a hypothetical user device location, a conditional probability of being line-of-sight or non-line-of-sight to each satellite of the GNSS communicating with the user device using the map information and a position of each satellite of the GNSS;
determining for the hypothetical user device location a likelihood of the received pseudorange data corresponding to each satellite of the GNSS indicating a line-of-sight relationship between the hypothetical user device location and the position of the GPS satellite and given a clock bias estimate; and
determining for the hypothetical user device location a likelihood of the received pseudorange data indicating a non-line-of-sight relationship between the hypothetical user device location and the position of the satellite of the GNSS and given the clock bias estimate.

4. The method of claim 3 , wherein the clock bias estimate is hypothetically generated along with the hypothetical user device location.

5. The method of claim 3 , wherein the clock bias estimate for each hypothetical user device location is calculated based on the received pseudorange data weighted by the determined conditional line-of-sight probability for each hypothetical user device location.

6. The method of claim 1 , wherein each of the probabilistic shadow matching estimates are calculated based on a shadow map retrieved from a shadow cache, wherein the shadow cache stores shadow maps corresponding to GNSS position data.

7. The method of claim 1 , wherein the non-linear filter is a bootstrap particle filter which operates by:
initializing an initial particle set based on a first data point of the received GNSS, SNR, and pseudorange data;
weighting each particle in the initial particle set based on probabilistic shadow matching estimates for each particle in the initial particle set, wherein the probabilistic shadow matching estimates are based on the first data point;
predicting a particle location for each particle in the initial particle set using a motion model;
sampling the particles at the predicted particle locations for each particle to create a second particle set;
weighting each particle in the second particle set based on probabilistic shadow matching estimates for each particle in the second particle set, wherein the probabilistic shadow matching estimates are based on a second data point of the received GNSS, SNR, and pseudorange data; and
predicting a particle location for each particle in the second particle set using a motion model.

8. The method of claim 7 , further comprising re-sampling the initial particle set based on the particle weights to create the second particle set.

9. The method of claim 1 , wherein the non-linear filter is an advanced particle filter which operates by:
receiving a first data point of GNSS, SNR, and pseudorange data;
generating an initial likelihood surface based on received GNSS data of the first data point;
weighting the initial likelihood surface based on probabilistic shadow matching estimates for the initial likelihood surface, wherein the probabilistic shadow matching estimates are based on the SNR and pseudorange data of the first data point;
generating an initial particle set by sampling from the weighted initial likelihood surface;
generating a predicted particle set for the initial particle set based on a motion model;
receiving a second data point of GNSS, SNR, and pseudorange data;
generating a second likelihood surface based on the predicted particle set and the GNSS data of the second data point;
weighting the second likelihood surface based on probabilistic shadow matching estimates for the second likelihood surface, wherein the probabilistic shadow matching estimates are based on the SNR and pseudorange data of the second data point; and
generating a second particle set based on the weighted second likelihood surface and the predicted particle set.

10. The method of claim 9 further comprising weighting the generated second particle set using road mapping.

11. A non-transitory computer readable storage medium storing instructions comprising:
receiving a position fix location calculated by a GNSS receiver included in the user device, wherein the position fix location approximates an actual position of the user device and is calculated by the GNSS receiver using data received from a satellite system, wherein the satellite system includes a plurality of satellites;
receiving, from the GNSS receiver, signal strength data associated with at least one satellite of the satellite system;
receiving, from the GNSS receiver, pseudorange data associated with the at least one satellite of the satellite system;
accessing map information describing an environment surrounding the position fix location;
calculating a probabilistic shadow matching estimate for each of a plurality of hypothesized user device locations utilizing the signal strength data, the pseudorange data, and the map information, wherein each of the probabilistic shadow matching estimates is determined in part by a pseudorange measurement model; and
calculating, using a non-linear filter, an updated position estimate of the user device based at least in part on the calculated probabilistic shadow matching estimates.

12. The non-transitory computer readable storage medium of claim 11 , wherein each of the probabilistic shadow matching estimates-represents a likelihood of the received signal strength data and a likelihood of received pseudorange data as a function of hypothesized user device locations within the environment described by the received map information.

13. The non-transitory computer readable storage medium of claim 11 , wherein the pseudorange measurement model further comprises:
determining, for a hypothetical user device location, a conditional probability of being line-of-sight or non-line-of-sight to each satellite of the GNSS communicating with the user device using the map information and a position of each satellite of the GNSS;
determ

Assignees

• Uber Technologies Inc

Inventors

• Madhow Upamanyu
• Irish Andrew

Classifications

• G01S19/09

  providing processing capability normally carried out by the receiver · CPC title

• G01S5/0036

  of measured values, i.e. measurement on mobile and position calculation on base station · CPC title

• G01S5/0027

  of actual mobile position, i.e. position determined on mobile · CPC title

• G01S19/393

  Trajectory determination or predictive tracking, e.g. Kalman filtering · CPC title

• G01S19/428

  using multipath or indirect path propagation signals in position determination · CPC title