Latent Oscillator Frequency Estimation For Ranging Measurements

Patent metadata

Field	Value
Publication number	US-2018267162-A1
Application number	US-201815920730-A
Country	US
Kind code	A1
Filing date	Mar 14, 2018
Priority date	Mar 15, 2017
Publication date	Sep 20, 2018
Grant date	—

Abstract

Time of Flight ranging using double-sided two-way ranging (DS-TWR) is a conventional method of ranging with ultra-wideband (UWB) radios and has been shown to have ranging accuracies on the order of tens of centimeters. This approach requires several transmissions for each range measurement, which does not scale well for multi-agent robotics because of the bandwidth needed for ranging measurements. This disclosure proposes a latent model for clock frequencies using a factor graph that enables greater consistency of clock synchronization and increases the rate of useful range measurements. This model is an effective and robust improvement to conventional DS-TWR that can leverage shared information from a network of robots. An increase in the rate of range measurements of 232% was obtained as compared to DS-TWR with the same hardware and transmission rate, and with a mean square error of range measurements of 20 cm.

First claim

What is claimed is:

1 . A computer-implemented method for determining location of objects in a space, each object is equipped with a wireless transceiver and transmits messages amongst the objects via the wireless transceiver, comprising:
modeling a system of objects using a factor graph having a plurality of variable vertices interconnected by a plurality of factor vertices, where a given variable vertex in the factor graph represents a location of a particular object at a given time and another variable vertex corresponding to the given variable vertex represents frequency of an oscillator driving the wireless transceiver of the particular object; computing, by a given object, time of flight for each of a plurality of transmissions between the given object and objects in the space from which transmissions are received by the given object; and estimating, by the given object, location of the objects in the space using the computed time of flight values for the plurality of transmissions and the factor graph.

2 . The method of claim 1 further comprises modeling location of a particular object over time as a chain in the factor graph and modeling frequency of an oscillator over time as a chain in the factor graph.

3 . The method of claim 2 further comprises constraining location estimates using range factors, where range factors are represented by factor vertices that interconnect location vertices and frequency vertices a given variable vertex to another variable vertex corresponding to the given variable vertex and representing frequency.

4 . The method of claim 3 wherein the range factor is defined as a difference between an expected range based on distance between objects and a time of flight measurement with scaling based on an estimate of relative frequencies of the two objects at the time the measurement took place.

5 . The method of claim 4 further comprises constraining location estimates using position factors, where position factors are represented by factor vertices that interconnect the variable vertices that represent location.

6 . The method of claim 5 further comprises measuring movement of the given object using a sensor associated with the object and constraining location estimates for the given object using the measured movement.

7 . The method of claim 6 further comprises constraining location estimates using frequency factors, where frequency factors are represented by factor vertices that interconnect the variable vertices that represent frequency.

8 . The method of claim 7 wherein the frequency factor is modeled as a zero mean Gaussian.

9 . The method of claim 1 wherein computing time of flight further comprises transmitting messages over time amongst the objects in the space and computing time of flight values between objects using the plurality of transmitted messages.

10 . The method of claim 1 wherein estimating location of the objects further comprises solving a least squares problem using the computed time of flight values for the plurality of transmissions.

11 . The method of claim 10 further comprises solving a least square problem using one of a gradient descent method or a Gauss-Newton method.

12 . The method of claim 1 further comprises directly observing frequency of an oscillator in one or more objects and updating the factor graph using the observed frequencies.

13 . The method of claim 1 wherein at least one of the modeled objects in the factor graph includes an atomic clock.

14 . A computer-implemented method for determining location of objects in a space, each object is equipped with a wireless transceiver and transmits messages amongst the objects via the wireless transceiver, comprising:
modeling a system of objects using a factor graph, the factor graph having a plurality of variable vertices interconnected by a plurality of factor vertices, where a given variable vertex in the factor graph represents a particular location of a particular object at a given time and an associated variable vertex corresponding to the given variable vertex that represents frequency of an oscillator driving the wireless transceiver of the particular object and a chain in the factor graph representing the frequency of the oscillator over time; transmitting a plurality of messages over time amongst the objects in the space, computing, by a given object, time of flight for each of the plurality of messages between the given object and objects in the space from which messages are received by the given object; and estimating, by the given object, location of the objects in the space while constraining location estimates using frequency factors, where the estimating location of objects is performed using the computed time of flight values for the plurality of transmissions and the frequency factors are represented by factor vertices that interconnect the variable vertices that represent frequency.

15 . The method of claim 14 wherein the frequency factors are modeled as a zero mean Gaussian.

16 . The method of claim 15 further comprises constraining location estimates using range factors, where range factors are represented by factor vertices that interconnect a given variable vertex to another variable vertex corresponding to the given variable vertex and representing frequency.

17 . The method of claim 16 wherein the range factor is defined as a difference between an expected range based on distance between objects and a time of flight measurement with scaling based on an estimate of relative frequencies of the two objects at the time the measurement took place.

18 . The method of claim 17 further comprises constraining location estimates using position factors, where position factors are represented by factor vertices that interconnect the variable vertices that represent location.

19 . The method of claim 18 further comprises measuring movement of the given object using a sensor associated with the object and constraining location estimates for the given object using the measured movement.

Assignees

• Univ Michigan Regents

Inventors

• Olson Edwin
• Messenger Sean M
• Mamish John

Classifications

• G01S13/767

  Responders; Transponders (teaching or practice apparatus for gun-aiming or gun-laying using reflecting targets or active targets F41G3/26) · CPC title

• G01S13/765 Primary

  with exchange of information between interrogator and responder · CPC title