Geometrical scheduling algorithm for acoustic positioning beacons

Patent metadata

Field	Value
Publication number	US-10292015-B1
Application number	US-201715637108-A
Country	US
Kind code	B1
Filing date	Jun 29, 2017
Priority date	Mar 5, 2015
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

Described is an improved active-beacon/passive-listener time difference of arrival navigation system that relies on the multiple beacons to transmit uncoded acoustic pulses of a same frequency that propagate in the system at a same time for high-speed device tracking. Listening devices may receive multiple encoded radio frequency pulses (RF) prior to a single acoustic pulse, and then resolve which RF pulse corresponds to the acoustic pulse using triangulation techniques.

First claim

What is claimed is:

1. A computing device, comprising:
at least one processor;
a radio frequency (RF) receiver;
a microphone;
at least one memory including instructions that, when executed by the at least one processor, cause the computing device to:
receive, via the RF receiver, a first RF pulse corresponding to a first location of a first transmitter;
receive, via the RF receiver, a second RF pulse corresponding to a second location of a second transmitter;
receive, via the microphone and after receiving the first RF pulse and the second RF pulse, an acoustic pulse;
determine a first time difference between receipt of the first RF pulse and receipt of the acoustic pulse;
determine a second time difference between receipt of the second RF pulse and receipt of the acoustic pulse;
based at least in part on the first time difference and the second time difference, determine the acoustic pulse was emitted from the first location; and
based at least in part on the first location and the first time difference, determine a location of the computing device.

2. The computing device of claim 1 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
based at least in part on the first time difference, calculate a distance; and
determine the distance is less than a threshold distance,
wherein the threshold distance corresponds to a maximum distance that an acoustic pulse propagates from the first transmitter before dropping below a threshold strength.

3. The computing device of claim 2 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
based at least in part on the second time difference, calculate a second distance; and
determine the second distance is greater than a second threshold distance,
wherein the second threshold distance corresponds to a second maximum distance that an acoustic pulse propagates from the second transmitter before dropping below the threshold strength.

4. The computing device of claim 1 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
based at least in part on the second time difference, calculate a distance; and
determine the distance is less than a threshold distance,
wherein the threshold distance corresponds to a minimum separation distance between the computing device and the second transmitter.

5. The computing device of claim 1 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
calculate a first distance based at least in part on the first time difference;
calculate a second distance based at least in part on the second time difference;
determine an earlier location of the computing device, the earlier location being determined prior to receiving the first RF pulse, the second RF pulse, and the acoustic pulse;
determine a third distance between the earlier location and the location;
determine a maximum distance that the computing device could have traveled since the earlier location;
determine the first distance is less than a sum of the third distance and the maximum distance; and
determine the second distance is greater than the sum.

6. The computing device of claim 5 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
determine an amount of time that has transpired since the earlier location was determined; and
multiply the amount of time by a stored maximum speed of the computing device to determine the maximum distance.

7. The computing device of claim 1 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
calculate a first distance based at least in part on the first time difference;
calculate a second distance based at least in part on the second time difference;
receive a third RF pulse, the third RF pulse corresponding to a third location of a third transmitter;
after receiving the third RF pulse, receive a second acoustic pulse;
determine a third time difference between receipt of the third RF pulse and receipt of the second acoustic pulse;
calculate a third distance between the first location and the third location;
determine a sum of the first distance and the second distance;
determine the sum is greater than a third distance; and
based at least in part on the sum being greater than the third distance, determine the third transmitter did not emit the second acoustic pulse.

8. The computing device of claim 1 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
receive a third RF pulse corresponding to a third location of a third transmitter;
receive a fourth RF pulse corresponding to a fourth location of a fourth transmitter;
after receiving the third RF pulse and the fourth RF pulse, receive a second acoustic pulse;
determine a third time difference between receipt of the third RF pulse and receipt of the second acoustic pulse;
determine a fourth time difference between receipt of the fourth RF pulse and receipt of the second acoustic pulse;
receive a fifth RF pulse corresponding to a fifth location of a fifth transmitter;
after receiving the third RF pulse and the fourth RF pulse, receive a third acoustic pulse;
determine a fifth time difference between receipt of the fifth RF pulse and receipt of the third acoustic pulse;
calculate a first distance based at least in part on the first time difference;
calculate a second distance based at least in part on the third time difference;
calculate a third distance based at least in part on the fourth time difference;
calculate a fourth distance based at least in part on the fifth time difference;
perform at least a first calculation to determine a sixth location based at least in part on the first distance to the first location, the second distance to the third location, and the fourth distance to the fifth location;
perform at least a second calculation to determine a seventh location based at least in part on the first distance to the first location, the third distance to the fourth location, and the fourth distance to the fifth location; and
determine the second acoustic pulse was emitted from the third location based at least in part on the at least a first calculation and the at least a second calculation.

9. The computing device of claim 8 , wherein:
the at least a first calculation comprises at least a first non-linear least squares solution with at least a first residual error; and
the at least a second calculation comprises at least a second non-linear least squares solution with at least a second residual error.

10. The computing device of claim 8 , wherein the at least one memory further includes instructions that, when executed by the at least one processor, further cause the computing device to:
determine the sixth location is within spatial boundaries represented in stored map data; and
determine the seventh location is outside the spatial boundaries.

11. A computer-implemented method, comprising:
receiving, via a RF receiver of a computing device, a first RF pulse corresponding to a first location of a first transmitter;
receiving, via the RF receiver, a second RF pulse corresponding to a second location of a se

Assignees

• Amazon Tech Inc

Inventors

• Thiagarajan Arvind
• Jeng Evan Duke
• Price Andrew David

Classifications

• H04L5/005

  of common pilots, i.e. pilots destined for multiple users or terminals · CPC title

• G01S1/74

  Details · CPC title

• H04W4/029

  Location-based management or tracking services · CPC title

• H04W4/04 Primary

  Electricity · mapped topic

• G01S5/30

  Determining absolute distances from a plurality of spaced points of known location · CPC title