Method and apparatus for filtering measurements used in a generalized positioning system

• US 6,535,833 B1
• Filed: 11/22/1999
• Issued: 03/18/2003
• Est. Priority Date: 11/22/1999
• Status: Expired due to Term

• Current Assignee: III Holdings 3, LLC
• Original Assignee: Nokia Mobile Phones UK Limited (Nokia Corporation)
• Inventors: Syrjärinne, Jari
• Primary Examiner(s): Barlow, John
• Assistant Examiner(s): Washburn, Douglas N
• Application Number:
  US09/444,880
• Time in Patent Office: 1,212 Days
• Field of Search: 342/357.09, 342/357, 342/357.04, 342/357.03, 324/326, 701/215, 701/214, 701/216, 379/59, 379/60, 455/31.1, 455/426, 455/456
• US Class Current: 702/150
• CPC Class Codes: G01S 19/39 the satellite radio beacon positioning system transmitting time-stamped messages, e.g. GPS [Global Positioning System], GLONASS [Global Orbiting Navigation Satellite System] or GALILEO
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type
• CPC Class Codes: H03H 17/0257 KALMAN filters

Abstract

A positioning system based on an extended Kalman filter (EKF), or other filter, responsive to measurements provided on the basis of information received from, in some applications, cellular base stations, as well as, optionally, satellites, where, in the case of measurements by satellites, and also in other aspects of the invention as used with cellular positioning data, the EKF is modified for greater responsiveness based on use of calculated association probabilities for each measurement in a set of measurements of position at a particular instant of time, the association probabilities used in the calculation of a combined measurement innovation (residual) used in calculating the next estimate of position (and other state information, including velocity). By using a combined measurement innovation, the positioning system is able to accept simultaneous measurements based on information received from different sources of information, including both satellites and cellular base stations.

Claims

1. A positioning system, comprising:

a) a filter, responsive to an initial estimate of a state of motion of an object, and an initial value of state covariance, and further responsive to a succession of a plurality of measurements of the state, each plurality of measurements of the state corresponding to a different instant of time, for statistically determining a succession of state estimates; and

b) a measurement engine, responsive to information provided at least in part by a cellular base station and from which a measurement of the state can be determined, for providing the succession of the pluralities of measurements of the state;

wherein the filter comprises means for determining individual association probabilities, each corresponding to a respective state measurement from among the pluralities of state measurements at respective instants of time, for weighting innovations corresponding to each of the measurements in the pluralities of measurements of the state.

2. A positioning system as in claim 1, wherein the filter further comprises:

a) means for determining an additional association probability providing a value for the probability that none of the plurality of measurements is correct;

b) means for combining into a combined measurement innovation the individual innovations using the individual association probabilities as weightings; and

c) means for providing an updated state and for determining a covariance of the updated state based on the individual association probabilities, and the association probability for providing a value for the probability that none of the measurements is correct, and also the combined measurement innovation.

3. A positioning system as in claim 1, wherein each measurement has a corresponding measurement innovation, wherein the means for determining the association probability at a k^th instant of time for a j^th measurement out of m(k) state measurements is represented by β

_j(k) and is given by ${\mathrm{\beta <br><br>}}_j<br><br>\left(k\right)={e_j<br><br>\left(k\right)<br><br>\left[b<br><br>\left(k\right)+\underset{i=1}{\overset{M<br><br>\left(K\right)}{\sum <br><br>}}<br><br>e_i<br><br>\left(k\right)\right]}^{-1}$

for j=1 . . . m(k), where

4. A positioning system as in claim 3, wherein the filter is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

5. A positioning system as in claim 1, further comprising an output display, wherein both the measurement engine and the output display are co-located with the object for which the state information is to be measured, and further wherein the filter, the means for determining association probabilities, the means for combining into a combined measurement innovation each individual innovation, and the means for determining the covariance of the updated state are all hosted by a non-local facility, one that is separate and remote from the object for which the state information is to be measured, and wherein the non-local facility and the measurement engine and the output display are in radio communication.

6. A positioning system as in claim 1, wherein the filter is responsive to a finite gate width γ

of a validation region, and wherein the filter rejects a measurement from among the plurality of measurements all at a same instant of time if the measurement falls outside the validation region.

7. A positioning system as in claim 6, wherein the validation region is defined by

8. A positioning system as in claim 7, wherein the filter is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

9. A positioning system as in claim 1, wherein the filter is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

10. A positioning system as in claim 1, further comprising an output display, wherein both the measurement engine and the output display are co-located with the object for which the state information is to be measured, and further wherein the filter is hosted by a non-local facility, one that is separate and remote from the object for which the state information is to be measured, and wherein the non-local facility and the measurement engine and the output display are in radio communication.

11. A positioning system as in claim 1, wherein the filter is an extended Kalman filter (EKF).

35. A positioning system as in claim 1, wherein the filter is a non-linear filter.

36. A positioning system as in claim 1, wherein the filter is a linear filter.

45. A positioning system as in claim 1, wherein the positioning system is a global positioning system (GPS).

12. A positioning system, comprising:

a) a filter, responsive to an initial estimate of a state of motion, and an initial value of state covariance, and further responsive to a succession of measurements of the state, each corresponding to a different instant of time, for statistically determining a succession of state estimates;

b) a measurement engine, responsive to information provided by positioning satellites, from which a measurement of the state can be determined, for providing the succession of measurements of the state;

c) means for determining association probabilities for a plurality of state measurements all at a same instant of time, each association probability corresponding to a particular state measurement at the instant of time, and also means for determining an association probability providing a value for the probability that none of the plurality of measurements is correct;

d) means for combining into a combined measurement innovation each individual innovation using the association probabilities as weightings; and

e) means for determining the covariance of the updated state based on the individual association probabilities, and the association probability for providing a value for the probability that none of the measurements is correct, and also the combined measurement innovation.

13. A positioning system as in claim 12, further comprising an output display, wherein both the measurement engine and the output display are co-located with the object for which the state information is to be measured, and further wherein the filter, the means for determining association probabilities, the means for combining into a combined measurement innovation each individual innovation, and the means for determining the covariance of the updated state are all hosted by a non-local facility, one that is separate and remote from the object for which the state information is to be measured, and wherein the non-local facility and the measurement engine and the output display are in radio communication.

14. A positioning system as in claim 12, wherein the filter is an extended Kalman filter (EKF).

37. A positioning system as in claim 12, wherein the filter is a non-linear filter.

38. A positioning system as in claim 12, wherein the filter is a linear filter.

46. A positioning system as in claim 12, wherein the positioning system is a global positioning system (GPS).

15. A method, comprising the steps of:

a) filtering, based on using a non-linear stochastic equation as governing the motion of an object, the filtering responsive to an initial estimate of a state of motion of the object, and an initial value of state covariance, and further responsive to a succession of pluralities of measurements of the state, each plurality of measurements of the state corresponding to a different instant of time, so as to statistically determine a succession of state estimates; and

b) measuring, responsive to information provided at least in part by a cellular base station, for providing the succession of pluralities of measurements of the state;

wherein individual association probabilities, each corresponding to a respective state measurement from among the pluralities of state measurements at respective instants of time, are used for weighting innovations corresponding to each of the measurements in the pluralities of measurements of the state.

16. A method as in claim 15, further comprising the steps of:

a) determining an additional association probability providing a value for the probability that none of the plurality of measurements is correct;

b) combining into a combined measurement innovation each individual innovation using the association probabilities as weightings;

c) providing an updated state and determining a covariance of the updated state based on the individual association probabilities, and the association probability for providing a value for the probability that none of the measurements is correct, and also the combined measurement innovation.

17. A method as in claim 15, wherein each measurement has a corresponding measurement innovation, wherein the association probability at a k^th instant of time for a j^th measurement out of m(k) state measurements is represented by β

_j(k) and is given by ${\mathrm{\beta <br><br>}}_j<br><br>\left(k\right)={e_j<br><br>\left(k\right)<br><br>\left[b<br><br>\left(k\right)+\underset{i=1}{\overset{m<br><br>\left(k\right)}{\sum <br><br>}}<br><br>e_i<br><br>\left(k\right)\right]}^{-1}$

for j=1 . . . m(k), where

18. A method as in claim 17, wherein the filtering is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

19. A method as in claim 15, wherein the filtering is responsive to a finite gate width γ

of a validation region, and wherein the filter rejects a measurement from among the plurality of measurements all at a same instant of time if the measurement falls outside the validation region.

20. A method as in claim 19, wherein the validation region is defined by

21. A method as in claim 20, wherein the filtering is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

22. A method as in claim 15, wherein the filtering is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

23. A method as in claim 15, wherein the filtering is as performed by an extended Kalman filter (EKF).

39. A method as in claim 15, wherein the filtering is performed by a non-linear filter.

40. A method as in claim 15, wherein the filtering is performed by a linear filter.

24. A method, comprising the steps of:

a) filtering, based on using a non-linear stochastic equation as governing the motion of an object, the filtering responsive to an initial estimate of a state of motion, and an initial value of state covariance, and further responsive to a succession of pluralities of measurements of the state, each plurality of measurements of the state corresponding to a different instant of time, so as to statistically determine a succession of state estimates;

b) measuring, responsive to information provided by positioning satellites, for providing the succession of pluralities of measurements of the state;

c) determining association probabilities for a plurality of measurements of the state all at a same instant of time, each association probability corresponding to a respective state measurement at the instant of time, and also determining an association probability providing a value for the probability that none of the plurality of measurements is correct;

d) combining into a combined measurement innovation each individual innovation using the association probabilities as weightings; and

e) determining the covariance of the updated state based on the individual association probabilities, and the association probability for providing a value for the probability that none of the measurements is correct, and also the combined measurement innovation.

25. A method as in claim 24, wherein the filtering is as performed by an extended Kalman filter (EKF).

41. A method as in claim 24, wherein the filtering is performed by a non-linear filter.

42. A method as in claim 24, wherein the filtering is performed by a linear filter.

26. A positioning system filter, responsive to an initial estimate of a state of motion of an object, and an initial value of state covariance, and further responsive to a succession of pluralities of measurements of the state, each plurality of measurements of the state corresponding to a different instant of time, for statistically determining a succession of state estimates, wherein the filter is responsive to measurements provided by a measurement engine receiving at least some information from a cellular base station, and comprising means for determining individual association probabilities, each corresponding to a respective state measurement from among the pluralities of state measurements at respective instants of time, for weighting innovations corresponding to each of the measurements in the pluralities of measurements of the state.

27. A positioning system filter as in claim 26, further comprising:

a) means for determining an additional association probability providing a value for the probability that none of the plurality of measurements is correct;

b) means for combining into a combined measurement innovation the individual innovations using the individual association probabilities as weightings; and

c) means for providing an updated state and for determining a covariance of the updated state based on the individual association probabilities, and the association probability for providing a value for the probability that none of the measurements is correct, and also the combined measurement innovation.

28. A positioning system filter as in claim 26, wherein each measurement has a corresponding measurement innovation, wherein the means for determining the association probability at a k^th instant of time for a j^th measurement out of m(k) state measurements is represented by β

_j(k) and is given by ${\mathrm{\beta <br><br>}}_j<br><br>\left(k\right)={e_j<br><br>\left(k\right)<br><br>\left[b<br><br>\left(k\right)+\underset{i=1}{\overset{m<br><br>\left(k\right)}{\sum <br><br>}}<br><br>e_i<br><br>\left(k\right)\right]}^{-1}$

for j=1 . . . m(k), where

29. A positioning system filter as in claim 28, wherein the filter is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

30. A positioning system filter as in claim 26, wherein the filter is responsive to a finite gate width γ

of a validation region, and wherein the filter rejects a measurement from among the plurality of measurements all at a same instant of time if the measurement falls outside the validation region.

31. A positioning system filter as in claim 30, wherein the validation region is defined by

32. A positioning system filter as in claim 31, wherein the filter is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

33. A positioning system filter as in claim 26, wherein the filter is responsive to measurements provided by a measurement engine receiving information from both satellites and cellular base stations.

34. A positioning system filter as in claim 26, wherein the filter is an extended Kalman filter (EKF).

43. A positioning system filter as in claim 26, wherein the filter is a non-linear filter.

44. A positioning system filter as in claim 26, wherein the filter is a linear filter.