LOCATION ENHANCEMENT SYSTEM AND METHOD BASED ON TOPOLOGY CONSTRAINTS

• US 20110082643A1
• Filed: 10/05/2009
• Published: 04/07/2011
• Est. Priority Date: 10/05/2009
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Chen, Henry, Plocher, Tom, Huseth, Steve
• Granted Patent: US 8,306,748 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence

Abstract

A method for enhanced location sensing based on topology constraints. A potential position value and a corresponding probability value with respect to an observed position data of an object within a structure can be calculated utilizing a normal probability distribution function. Thereafter, an optimal route between adjacent observed time periods may be calculated utilizing a heuristic search algorithm. The potential position value and the optimal route can be calculated by accessing a pre-installed topology data associated with the structure. An optimization problem can then be solved to refine the observed position data. The position between a pair of observed time periods can be interpolated and the position of the object before a next observed time can be predicted by interpolation based on the spatial constraints.

Claims

1. A method for enhanced location tracking, said method comprising:

determining at least one potential position value and a corresponding probability value with respect to observed position data of an object utilizing a normal probability distribution function and a structure topology data;

calculating an optimal route and a length of said optimal route between adjacent time periods based on said structure topology data in order to thereafter solve an optimization problem to refine said observed position data; and

interpolating said at least one potential position value between a pair of observed position values in order to predict a position of said object at an adjacent observed time period based on a spatial constraint and thereby effectively locate and track said object based on said structure topology data.

2. The method of claim 1 further comprising predicting said position of said object before said adjacent observed time based on said spatial constraint in response to interpolating said at least one potential position value at the next observed time period.

3. The method of claim 1 further comprising pre-installing said structure topology data to obtain said potential position value and said optimal route.

4. The method of claim 1 wherein determining said at least one potential position value and said corresponding probability value of said object, further comprises:

implementing a circle in association with said observed position data as a center and a variance with respect to a radius in order to thereafter calculate at least one compartment intersecting said circle; and

selecting a sample point with respect to said at least one compartment intersecting said circle in association with an intersection part in order to calculate said probability value based on said probability distribution function.

5. The method of claim 1 further comprising adding a time variable to said at least one potential position value and said probability value.

6. The method of claim 1 wherein calculating said optimal route between adjacent times based on said structure topology data, further comprises:

implementing a heuristic route search in order to split an image obtained from said structure topology data into a plurality of grids; and

analyzing said optimal route between at least two grids.

7. The method of claim 1 further comprising refining said observed position data utilizing said probability value and a route length associated with said optimal route.

8. The method of claim 1 wherein interpolating said at least one potential position between said pair of observed time period, further comprises:

obtaining said position between said pair of observed time periods utilizing a curve fitting process and a fitting curve thereof; and

locating said predicted position on said fitting curve.

9. A system for enhanced location tracking, said system comprising:

a processor;

a data bus coupled to said processor; and

a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

determining at least one potential position value and a corresponding probability value with respect to observed position data of an object utilizing a normal probability distribution function and a structure topology data;

calculating an optimal route and a length of said optimal route between adjacent time periods based on said structure topology data in order to thereafter solve an optimization problem to refine said observed position data; and

interpolating said at least one potential position value between a pair of observed position values in order to predict a position of said object at an adjacent observed time period based on a spatial constraint and thereby effectively locate and track said object based on said structure topology data.

10. The system of claim 9 wherein said instructions are further configured for predicting said position of said object before said adjacent observed time based on said spatial constraint in response to interpolating said at least one potential position value at the next observed time period.

11. The system of claim 9 wherein said instructions for determining said at least one potential position value and said corresponding probability value of said object, are further configured for:

implementing a circle in association with said observed position data as a center and a variance with respect to a radius in order to thereafter calculate at least one compartment intersecting said circle; and

selecting a sample point with respect to said at least one compartment intersecting said circle in association with an intersection part in order to calculate said probability value based on said probability distribution function.

12. The system of claim 9 wherein said instructions are further configured for adding a time variable to said at least one potential position value and said probability value.

13. The system of claim 9 wherein said instructions for calculating said optimal route between adjacent times based on said structure topology data, are further configured for:

implementing a heuristic route search in order to split an image obtained from said structure topology data into a plurality of grids; and

analyzing said optimal route between at least two grids.

14. The system of claim 9 wherein said instructions are further configured for refining said observed position data utilizing said probability value and a route length associated with said optimal route.

15. The system of claim 9 wherein said instructions for interpolating said at least one potential position between said pair of observed time period, are further configured for:

obtaining said position between said pair of observed time periods utilizing a curve fitting process and a fitting curve thereof; and

locating said predicted position on said fitting curve.

16. A computer-usable medium for enhanced location tracking, said computer-usable medium embodying computer program code, said computer program code comprising computer executable instructions configured for:

determining at least one potential position value and a corresponding probability value with respect to observed position data of an object utilizing a normal probability distribution function and a structure topology data;

calculating an optimal route and a length of said optimal route between adjacent time periods based on said structure topology data in order to thereafter solve an optimization problem to refine said observed position data; and

interpolating said at least one potential position value between a pair of observed position values in order to predict a position of said object at an adjacent observed time period based on a spatial constraint and thereby effectively locate and track said object based on said structure topology data.

17. The computer-usable medium of claim 16 wherein said embodied computer program code further comprises computer executable instructions configured for:

predicting said position of said object before said adjacent observed time based on said spatial constraint in response to interpolating said at least one potential position value at the next observed time period; and

pre-installing said structure topology data to obtain said potential position value and said optimal route.

18. The computer-usable medium of claim 16 wherein said embodied computer program code comprising computer executable instructions for determining said at least one potential position value and said corresponding probability value of said object, further comprises:

implementing a circle in association with said observed position data as a center and a variance with respect to a radius in order to thereafter calculate at least one compartment intersecting said circle; and

selecting a sample point with respect to said at least one compartment intersecting said circle in association with an intersection part in order to calculate said probability value based on said probability distribution function.

19. The computer-usable medium of claim 16 wherein said embodied computer program code further comprises computer executable instructions configured for:

adding a time variable to said at least one potential position value and said probability value;

implementing a heuristic route search in order to split an image obtained from said structure topology data into a plurality of grids; and

analyzing said optimal route between at least two grids.

20. The computer-usable medium of claim 16 wherein said embodied computer program code further comprises computer executable instructions configured for:

refining said observed position data utilizing said probability value and a route length associated with said optimal route;

obtaining said position between said pair of observed time periods utilizing a curve fitting process and a fitting curve thereof; and

locating said predicted position on said fitting curve.