Systems and methods to track movement of a device in an indoor environment

• US 10,117,061 B2
• Filed: 03/26/2018
• Issued: 10/30/2018
• Est. Priority Date: 09/02/2016
• Status: Expired due to Fees

• Current Assignee: Anthentek Innovation, Inc.
• Original Assignee: Athentek Incorporated
• Inventors: De Lorenzo, David S.
• Primary Examiner(s): Khan, Mehmood B.
• Application Number:
  US15/935,995
• Publication Number:
  US 20180220268A1
• Time in Patent Office: 218 Days
• CPC Class Codes: H04B 17/27 for locating or positioning the transmitter
• CPC Class Codes: H04B 17/318 Received signal strength
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Systems and methods to track a device in an indoor environment having polygonal obstructions are disclosed. In one variation, a computer-implemented method to localize the device involves receiving, at a server, a signal strength profile from the device, wherein the signal strength profile includes signal strengths of wireless signal transceivers in the indoor environment; determining a raw estimated location in a coordinate plane representing the indoor environment by using a K-nearest neighbor algorithm; calculating a straight-line path in the coordinate plane from an immediately preceding location to the raw estimated location; selecting the raw estimated location as a candidate location when the straight-line path connects the two locations without intersecting any of the polygonal obstructions; calculating a weighted-average location using the immediately preceding location and the candidate location; and storing the weighted-average location as a new location when a hypothetical velocity is less than or equal to a saturation velocity.

Claims

1. A system to localize a device in an indoor environment, the system comprising:

wireless signal transceivers positioned in the indoor environment, wherein the indoor environment contains one or more polygonal obstructions;

a server comprising a processing unit, a memory unit, and a server communication unit, and the processing unit is programmed to;

receive a signal strength profile, wherein the signal strength profile includes at least one of signal strengths of the wireless signal transceivers received at the device in the indoor environment and signal strengths of the device received at the wireless signal transceivers in the indoor environment;

determine a raw estimated location of the device in a coordinate plane representing the indoor environment by using a K-nearest neighbor (KNN) algorithm to compare the signal strength profile with reference profiles stored in a database;

calculate a straight-line path in the coordinate plane connecting the raw estimated location to an immediately preceding location of the device;

select the raw estimated location as the candidate location if the straight-line path does not intersect any of the polygonal obstructions in the coordinate plane using a polyxpoly( ) function as follows;

if isempty(polyxpoly[(x_old x_raw], [y_old y_raw], keepouts_x, keepouts_y))

[x_est, yet]=LPF(dt, x_old, y_old, e_raw, y_raw, p_gain, v_lim),

 

wherein x_old and y_old represent the immediately preceding location,

 

wherein x_raw and y_raw represent the raw estimated location, and

 

wherein x_est and y_est represent the candidate location;

calculate a weighted-average location using the immediately preceding location and the candidate location; and

store the weighted-average location as a new location of the device in the indoor environment when a hypothetical velocity calculated using an elapsed time and a distance separating the immediately preceding location and the weighted-average location is less than or equal to a saturation velocity.

2. The system of claim 1, wherein the processing unit is further programmed to:

generate an interlinking point using an x-axis coordinate of the immediately preceding location and a y-axis coordinate of the raw estimated location or the y-axis coordinate of the immediately preceding location and the x-axis coordinate of the raw estimated location; and

select the interlinking point as the candidate location when;

a first linear segment connects the immediately preceding location and the interlinking point without intersecting any of the polygonal obstructions, and

a second linear segment connects the raw estimated location and the interlinking point without intersecting any of the polygonal obstructions.

3. The system of claim 2, wherein the processing unit is further programmed to:

determine a first polyline path from the immediately preceding location to the raw estimated location, wherein a portion of the first polyline path traverses a first artery lane in the indoor environment;

determine a second polyline path from the immediately preceding location to the raw estimated location, wherein a portion of the second polyline path traverses a second artery lane in the indoor environment; and

select the first artery lane as a preferred artery lane when the first polyline path is shorter than the second polyline path;

select the second artery lane as the preferred artery lane when the second polyline path is shorter than the first polyline path;

generate an artery entrance location using an x-axis coordinate of the immediately preceding location and a y-axis coordinate of the preferred artery lane or using the y-axis coordinate of the immediately preceding location and the x-axis coordinate of the preferred artery lane; and

select the artery entrance location as the candidate location.

4. The system of claim 3, wherein the processing unit is further programmed to:

calculate a straight-line segment from the immediately preceding location to the artery entrance location prior to selecting the artery entrance location as the candidate location;

determine a laterally displaced location when the straight-line segment intersects any of the polygonal obstructions, wherein the laterally displaced location is determined using a y-axis coordinate of the immediately preceding location and an x-axis coordinate of the raw estimated location; and

select the laterally displaced location as the candidate location.

5. The system of claim 1, wherein the processing unit is further programmed to:

compare the raw estimated location of the device in the coordinate plane with coordinates representing borders of the polygonal obstructions prior to calculating the straight-line path;

determine the raw estimated location is within the borders of one of the polygonal obstructions;

adjust at least one coordinate of the raw estimated location to place the raw estimated location outside of the borders of the polygonal obstruction.

6. The system of claim 1, wherein the processing unit is further programmed to:

set a saturated location as the new location of the device when the hypothetical velocity calculated using the elapsed time and the distance separating the immediately preceding location and the weighted-average location is greater than the saturation velocity,

wherein the saturated location is generated using the saturation velocity, and

wherein the saturated location is closer in distance to the immediately preceding location than the weighted-average location.

7. The system of claim 1, wherein the indoor environment comprises between one wireless signal transceiver per 150 square meters and one wireless signal transceiver per 57 square meters.

8. The system of claim 1, wherein the wireless signal transceivers include at least one of WiFi access points and Bluetooth®

beacons.

9. A computer-implemented method to localize a device in an indoor environment, the method comprising:

receiving, at a server, a signal strength profile, wherein the signal strength profile includes at least one of signal strengths of wireless signal transceivers received at the device in the indoor environment and signal strengths of the device received at wireless signal transceivers in the indoor environment, and wherein the indoor environment contains one or more polygonal obstructions;

determining, using a processing unit of the server, a raw estimated location of the device in a coordinate plane representing the indoor environment by using a K-nearest neighbor (KNN) algorithm to compare the signal strength profile with reference profiles stored in a database;

calculating, using the processing unit of the server, a straight-line path in the coordinate plane from an immediately preceding location of the device to the raw estimated location;

selecting, using the processing unit of the server, the raw estimated location as a candidate location when the straight-line path connects the two locations without intersecting any of the polygonal obstructions in the coordinate plane using a polyxpoly( ) function as follows;

if isempty(polyxpoly[(x_old x_raw], [y_old y_raw], keepouts_x, keepouts_y))

[x_est, yet]=LPF(dt, x_old, y_old, e_raw, y_raw, p_gain, v_lim),

 

wherein x_old and y_old represent the immediately preceding location,

wherein x_raw and y_raw represent the raw estimated location, and

wherein x_est and y_est represent the candidate location;

calculating, using the processing unit of the server, a weighted-average location using the immediately preceding location and the candidate location; and

storing, using the processing unit of the server, the weighted-average location as a new location of the device in the indoor environment when a hypothetical velocity calculated using an elapsed time and a distance separating the immediately preceding location and the weighted-average location is less than or equal to a saturation velocity.

10. The computer-implemented method of claim 9, further comprising:

generating, using the processing unit of the server, an interlinking point using an x-axis coordinate of the immediately preceding location and a y-axis coordinate of the raw estimated location or the y-axis coordinate of the immediately preceding location and the x-axis coordinate of the raw estimated location; and

selecting, using the processing unit of the server, the interlinking point as the candidate location when;

a first linear segment connects the immediately preceding location and the interlinking point without intersecting any of the polygonal obstructions, and

a second linear segment connects the raw estimated location and the interlinking point without intersecting any of the polygonal obstructions.

11. The computer-implemented method of claim 10, further comprising:

determining, using the processing unit of the server, a first polyline path from the immediately preceding location to the raw estimated location, wherein a portion of the first polyline path traverses a first artery lane in the indoor environment;

determining, using the processing unit of the server, a second polyline path from the immediately preceding location to the raw estimated location, wherein a portion of the second polyline path traverses a second artery lane in the indoor environment; and

selecting, using the processing unit of the server, the first artery lane as a preferred artery lane when the first polyline path is shorter than the second polyline path;

selecting, using the processing unit of the server, the second artery lane as the preferred artery lane when the second polyline path is shorter than the first polyline path;

generating, using the processing unit of the server, an artery entrance location using an x-axis coordinate of the immediately preceding location and a y-axis coordinate of the preferred artery lane or using the y-axis coordinate of the immediately preceding location and the x-axis coordinate of the preferred artery lane; and

selecting, using the processing unit of the server, the artery entrance location as the candidate location.

12. The computer-implemented method of claim 11, further comprising:

calculating, using the processing unit of the server, a straight-line segment from the immediately preceding location to the artery entrance location prior to selecting the artery entrance location as the candidate location;

determining, using the processing unit of the server, a laterally displaced location when the straight-line segment intersects any of the polygonal obstructions, wherein the laterally displaced location is determined using a y-axis coordinate of the immediately preceding location and an x-axis coordinate of the raw estimated location; and

selecting, using the processing unit of the server, the laterally displaced location as the candidate location.

13. The computer-implemented method of claim 9, further comprising:

comparing, using the processing unit of the server, the raw estimated location of the device in the coordinate plane with coordinates representing borders of the polygonal obstructions prior to calculating the straight-line path;

determining, using the processing unit of the server, the raw estimated location is within the borders of one of the polygonal obstructions;

adjusting, using the processing unit of the server, at least one coordinate of the raw estimated location to place the raw estimated location outside of the borders of the polygonal obstruction.

14. The computer-implemented method of claim 9, further comprising:

setting, using the processing unit of the server, a saturated location as the new location of the device when the hypothetical velocity calculated using the elapsed time and the distance separating the immediately preceding location and the weighted-average location is greater than the saturation velocity,

wherein the saturated location is generated using the saturation velocity, and

wherein the saturated location is closer in distance to the immediately preceding location than the weighted-average location.

15. A non-transitory computer-readable medium comprising instructions stored thereon, that when executed by a processing unit, perform the steps of:

receiving a signal strength profile, wherein the signal strength profile includes at least one of signal strengths of wireless signal transceivers received at a device in the indoor environment and signal strengths of a device received at wireless signal transceivers in the indoor environment and wherein the indoor environment contains one or more polygonal obstructions;

determining a raw estimated location of the device in a coordinate plane representing the indoor environment by using a K-nearest neighbor (KNN) algorithm to compare the signal strength profile with reference profiles stored in a database;

calculating a straight-line path in the coordinate plane connecting the raw estimated location to an immediately preceding location of the device;

selecting the raw estimated location as the candidate location if the straight-line path does not intersect any of the polygonal obstructions in the coordinate plane using a polyxpoly( ) function as follows;

if isempty(polyxpoly[(x_old x_raw], [y_old y_raw], keepouts_x, keepouts_y))

[x_est, yet]=LPF(dt, x_old, y_old, e_raw, y_raw, p_gain, v_lim),

 

wherein x_old and y_old represent the immediately preceding location,

wherein x_raw and y_raw represent the raw estimated location, and

wherein x_est and y_est represent the candidate location;

calculating a weighted-average location using the immediately preceding location and the candidate location; and

storing the weighted-average location as a new location of the device in the indoor environment when a hypothetical velocity calculated using an elapsed time and a distance separating the immediately preceding location and the weighted-average location is less than or equal to a saturation velocity.

16. The non-transitory computer-readable medium of claim 15, further comprising instructions stored thereon, that when executed by a processing unit, perform the steps of:

generating an interlinking point using an x-axis coordinate of the immediately preceding location and a y-axis coordinate of the raw estimated location or the y-axis coordinate of the immediately preceding location and the x-axis coordinate of the raw estimated location; and

selecting the interlinking point as the candidate location when;

a first linear segment connects the immediately preceding location and the interlinking point without intersecting any of the polygonal obstructions, and

a second linear segment connects the raw estimated location and the interlinking point without intersecting any of the polygonal obstructions.

17. The non-transitory computer-readable medium of claim 16, further comprising instructions stored thereon, that when executed by a processing unit, perform the steps of:

determining a first polyline path from the immediately preceding location to the raw estimated location, wherein a portion of the first polyline path traverses a first artery lane in the indoor environment;

determining a second polyline path from the immediately preceding location to the raw estimated location, wherein a portion of the second polyline path traverses a second artery lane in the indoor environment; and

selecting the first artery lane as a preferred artery lane when the first polyline path is shorter than the second polyline path;

selecting the second artery lane as the preferred artery lane when the second polyline path is shorter than the first polyline path;

generating an artery entrance location using an x-axis coordinate of the immediately preceding location and a y-axis coordinate of the preferred artery lane or using the y-axis coordinate of the immediately preceding location and the x-axis coordinate of the preferred artery lane; and

selecting the artery entrance location as the candidate location.

18. The non-transitory computer-readable medium of claim 17, further comprising instructions stored thereon, that when executed by a processing unit, perform the steps of:

calculating, using the processing unit of the server, a straight-line segment from the immediately preceding location to the artery entrance location prior to selecting the artery entrance location as the candidate location;

determining, using the processing unit of the server, a laterally displaced location when the straight-line segment intersects any of the polygonal obstructions, wherein the laterally displaced location is determined using a y-axis coordinate of the immediately preceding location and an x-axis coordinate of the raw estimated location; and

selecting, using the processing unit of the server, the laterally displaced location as the candidate location.

19. The non-transitory computer-readable medium of claim 15, further comprising instructions stored thereon, that when executed by a processing unit, perform the steps of:

comparing the raw estimated location of the device in the coordinate plane with coordinates representing borders of the polygonal obstructions prior to calculating the straight-line path;

determining the raw estimated location is within the borders of one of the polygonal obstructions;

adjusting at least one coordinate of the raw estimated location to place the raw estimated location outside of the borders of the polygonal obstruction.

20. The non-transitory computer-readable medium of claim 15, further comprising instructions stored thereon, that when executed by a processing unit, perform the steps of:

setting a saturated location as the new location of the device when the hypothetical velocity calculated using the elapsed time and the distance separating the immediately preceding location and the weighted-average location is greater than the saturation velocity,

wherein the saturated location is generated using the saturation velocity, and

wherein the saturated location is closer in distance to the immediately preceding location than the weighted-average location.