Prediction of indoor location using decision trees

• US 8,639,640 B1
• Filed: 06/10/2011
• Issued: 01/28/2014
• Est. Priority Date: 06/10/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadous, Mohammed Waleed
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Kim, David H
• Application Number:
  US13/157,880
• Time in Patent Office: 963 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Decision trees may be built and executed to estimate an indoor location of a mobile device. In particular, a first attribute (e.g., received signal strength indication (RSSI) of one or more access points) is selected, and variations of that attribute throughout an indoor area are identified. These identified variations are mapped to the locations to generate a model. One or more decision trees are built based on the model, and an output of the decision trees estimates a location of a mobile device within the building. According to one aspect, a plurality of such decision trees may be built, and the outputs provided by the plurality of trees may be averaged to provide a more reliable result. Each of the plurality of trees may vary the attribute being analyzed, data values, or an order in which data is analyzed.

Claims

1. A method for determining a location of a mobile device within an indoor area, comprising:

storing, in a database, a model indicating variations in a first attribute at different points throughout the indoor area;

building, using a processor, a first decision tree including a starting node, at least one intermediate node, and an output node, the starting node presenting a first question related to the first attribute, each intermediate node presenting an additional question related to the first attribute, and the output node indicating a given point within the indoor area based on answers to the first and additional questions;

building, using the processor, at least a second decision tree, the second decision tree having a similar structure to the first decision tree, including second output nodes indicating points within the indoor area, the second decision tree varying from the first decision tree in that it presents different questions related to the first attribute or in that it presents questions related to a second attribute; and

comparing the output node from the first decision tree and the second output nodes from the second decision tree.

2. The method of claim 1, further comprising determining, using the processor, one or more equations correlating the variations in the first attribute with the different points throughout the indoor area, wherein the output node indicates which of the one or more equations to execute.

3. The method of claim 2, wherein a result of each equation is a latitude or longitude.

4. The method of claim 1, wherein the first attribute is a received signal strength of an access point, and wherein the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values.

5. The method of claim 1, further comprising:

averaging results from the first decision tree and the at least one second decision tree.

6. The method of claim 1, wherein:

the first attribute is a received signal strength of an access point;

the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values; and

for each of the at least one second decision trees, the predetermined values are varied.

7. The method of claim 1, wherein:

the first attribute is a received signal strength of an access point;

the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values; and

for each of the at least one second decision trees, the one or more particular access points are varied.

8. The method of claim 1, further comprising:

storing a second model indicating variations in a second attribute at the different points throughout the indoor area;

wherein the second decision tree presents questions related to the second attribute; and

combining results of the first decision tree and the second decision tree.

9. The method of claim 8, wherein the second attribute is one of direction, type of phone, lighting level, and time of day.

10. The method of claim 1, further comprising:

using the output of the first decision tree to estimate a location of a mobile device; and

determining, based on a similarity of results of the first and at least one second decision trees, whether the estimated location of a mobile device is accurate.

11. The method of claim 1, further comprising:

downloading at least one of the first decision tree and the at least one second decision tree to a mobile device within the indoor area; and

executing the downloaded decision tree to estimate a location of the mobile device.

12. The method of claim 1, wherein the given point indicated by the output node is provided as coordinates relative to a layout of the indoor area.

13. The method of claim 1, wherein the given point indicated by the output node is provided graphically on a display.

14. A system for determining a location of a mobile device within an indoor area, comprising:

a memory storing a model indicating variations in a first attribute at different points throughout the indoor area;

a processor, in communication with the memory, operable to;

build a first decision tree including a starting node, at least one intermediate node, and an output node, wherein the starting node presents a first question related to the first attribute, each intermediate node presents an additional question related to the first attribute, and the output node indicates a given point within the indoor area based on answers to the first and additional questions;

building at least a second decision tree, the second decision tree having a similar structure to the first decision tree, including second output nodes indicating points within the indoor area, the second decision tree varying from the first decision tree in that it presents different questions related to the first attribute or in that it presents questions related to a second attribute; and

comparing the output node from the first decision tree and the second output nodes from the second decision tree.

15. The system of claim 14, the processor further determining one or more equations correlating the identified variations in the first attribute with the different points throughout the indoor area, wherein the output node indicates which of the one or more equations to execute.

16. The system of claim 14, wherein the first attribute is a received signal strength of an access point, and wherein the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values.

17. The system of claim 14, the processor further averaging the results from the first decision tree and the at least one second decision tree.

18. The system of claim 17, wherein:

the first attribute is a received signal strength of an access point;

the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values; and

for each of the at least one second decision trees, the predetermined values are varied.

19. The system of claim 17, wherein:

the first attribute is a received signal strength of an access point;

the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values; and

for each of the at least one second decision trees, the one or more particular access points are varied.

20. The system of claim 14, further comprising:

the memory storing a model indicating variations in the second attribute at the different points throughout the indoor area; and

the processor further operable to

combine results of the first decision tree and the at least one second decision tree.

21. A system for determining a location of a mobile device within an indoor area, comprising:

means for storing a model indicating the variations in the first attribute at the different points throughout the indoor area;

means for building a first decision tree including a starting node, at least one intermediate node, and an output node, wherein the starting node presents a first question related to the first attribute, each intermediate node presents an additional question related to the first attribute, and the output node indicates a given point within the indoor area based on answers to the first and additional questions;

means for building at least a second decision tree, the second decision tree having a similar structure to the first decision tree, including second output nodes indicating points within the indoor area, the second decision tree varying from the first decision tree in that it presents different questions related to the first attribute or in that it presents questions related to a second attribute;

means for executing the decision tree to predict the location of the mobile device within the indoor area; and

means for comparing the output node from the first decision tree and the second output nodes from the second decision tree.

22. A method for predicting location of a mobile device in an indoor area, comprising:

detecting, using the mobile device, information related to a first attribute of the indoor area;

accessing a first decision tree corresponding to the indoor area, the first decision tree including a starting node, at least one intermediate node, and an output node, the starting node presenting a first question related to the first attribute, each intermediate node presenting an additional question related to the first attribute, and the output node indicating a given point within the indoor area based on answers to the first and additional questions;

accessing at least a second decision tree, the second decision tree having a similar structure to the first decision tree, including second output nodes indicating points within the indoor area, the second decision tree varying from the first decision tree in that it presents different questions related to the first attribute or in that it presents questions related to a second attribute;

executing the first decision tree and the at least one second decision tree using the detected information; and

determining a location of the mobile device based on the first decision tree and the at least one second decision tree.