Methods and systems for generating maps corresponding to physical spaces, devices, and/or users

• US 10,484,829 B1
• Filed: 04/27/2018
• Issued: 11/19/2019
• Est. Priority Date: 04/27/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Viton, Fernando Nahuel, Vogel, Matthew Evan, Vandenbrouck, Gregory Christopher John
• Primary Examiner(s): Cumming, William D
• Application Number:
  US15/964,751
• Publication Number:
  US 20190335300A1
• Time in Patent Office: 571 Days
• Field of Search: 707602, 707760, 455411, 4554561
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: H04W 4/38 for collecting sensor information
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]

Abstract

Generating a map based on nodes of a hierarchical graph that defines a topology of a physical space and is configured to provide access to sensor data from devices within the physical space includes accessing the hierarchical graph. The hierarchical graph comprises a plurality of nodes, including a top node for the physical space and a plurality of other nodes coupled to the top node. One of the plurality of nodes comprises an area node that represents an area within the physical space. One of the plurality of nodes also comprises a device node representing a device located within the physical space and a user node. Map data corresponding to a particular node is generated. The generated map data is associated with generating at least a portion of a map corresponding to the particular node. The generated map data corresponding to the particular node is stored within the hierarchical graph.

Claims

1. A computer system configured to generate a map based on nodes of a hierarchical graph that stores and provides access to sensor data from devices within a physical space, the system comprising:

one or more processors; and

one or more computer-readable storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to perform at least the following;

access a hierarchical graph that defines a topology of a physical space and comprises a plurality of nodes, the plurality of nodes of the hierarchical graph comprising a top node for the physical space and a plurality of other nodes coupled, through zero or more intermediate nodes, to the top node of the physical space, one or more of the plurality of nodes comprising an area node or a sub-area node, each area node and sub-area node representing an area or sub-area within the physical space, one or more of the plurality of nodes also comprising a device node, each device node representing a device located within the physical space, each device being configured to provide data or receive control signals, one or more of the plurality of nodes also comprising a user node that represents a user associated with an area or a device within the physical space; and

for a particular node of the plurality of nodes,

generate map data corresponding to the particular node, the generated map data being associated with generating at least a portion of a map corresponding to the particular node; and

store the generated map data corresponding to the particular node within the hierarchical graph such that the stored generated map data can be used to generate the portion of the map corresponding to the particular node.

2. The computer system of claim 1, wherein the computer-executable instructions further include instructions that are executable to cause the computer system to generate a portion of a map corresponding to the particular node based on the generated map data.

3. The computer system of claim 2, wherein the generated map data comprises Binary Large Object (BLOB) data associated with generating a portion of a map corresponding to the particular node.

4. The computer system of claim 2, wherein the computer-executable instructions further include instructions that are executable to cause the computer system to display live sensor data associated with one or more sensors located at an area of the physical space corresponding to the generated portion of the map.

5. The computer system of claim 2, wherein the computer-executable instructions further include instructions that are executable to cause the computer system to:

spatially link one or more additional nodes to the particular node; and

generate a map portion corresponding to each of the one or more additional nodes based at least partially on the spatial link, such that each map portion is rendered within the map in a proper location relative to each other map portion.

6. The computer system of claim 1, wherein the computer system includes a BLOB type store that includes a plurality of BLOB types, each different BLOB type being formatted for utilization in generating a different map type, wherein one or more of the BLOB types is formatted for generating at least one of a wayfinding map, an electrical grid map, a heating, ventilation, and air conditioning (HVAC) map, or a water and sewer map.

7. The computer system of claim 1, wherein the computer-executable instructions further include instructions that are executable to cause the computer system to store within each given node in the hierarchical graph, a full path of the given node within the hierarchical graph.

8. The computer system of claim 7, wherein the computer-executable instructions further include instructions that are executable to cause the computer system to use the stored full path within a given node to perform a query that identifies at least one of (i) one or more parent nodes associated with the given node, or (ii) one or more child nodes associated with the given node.

9. The computer system of claim 8, wherein the query comprises an O(1) operation.

10. A computer implemented method for generating a map based on nodes of a hierarchical graph that that stores and provides access to sensor data from devices within a physical space, the method implemented at a computer system that includes one or more processors, the method comprising:

accessing a hierarchical graph that defines a topology of a physical space and comprises a plurality of nodes, the plurality of nodes of the hierarchical graph comprising a top node for the physical space and a plurality of other nodes coupled, through zero or more intermediate nodes, to the top node of the physical space, one or more of the plurality of nodes comprising an area node or a sub-area node, each area node and sub-area node representing an area or sub-area within the physical space, one or more of the plurality of nodes also comprising a device node, each device node representing a device located within the physical space, each device being configured to provide data or receive control signals; and

for a particular node of the plurality of nodes,

generating map data corresponding to the particular node, the generated map data being associated with generating at least a portion of a map corresponding to the particular node; and

storing the generated map data corresponding to the particular node within the hierarchical graph such that the stored generated map data can be used to generate the portion of the map corresponding to the particular node.

11. The method of claim 10, further comprising:

generating a portion of a map corresponding to the particular node based on the generated map data.

12. The method of claim 11, wherein the generated map data comprises Binary Large Object (BLOB) data associated with generating a portion of a map corresponding to the particular node.

13. The method of claim 11, further comprising:

displaying live sensor data associated with one or more sensors located at an area of the physical space corresponding to the generated portion of the map.

14. The method of claim 11, further comprising:

spatially linking one or more additional nodes to the particular node; and

generating a map portion corresponding to each of the one or more additional nodes based at least partially on the spatial link, such that each map portion is rendered within the map in a proper location relative to each other map portion.

15. The method of claim 10, wherein the computer system includes a BLOB type store that includes a plurality of BLOB types, each different BLOB type being formatted for utilization in generating a different map type, wherein one or more of the BLOB types is formatted for generating at least one of a wayfinding map, an electrical grid map, a heating, ventilation, and air conditioning (HVAC) map, or a water and sewer map.

16. The method of claim 10, further comprising:

storing within each given node in the hierarchical graph, a full path of the given node within the hierarchical graph.

17. The method of claim 16, further comprising:

using the stored full path within a given node to perform a query that identifies at least one of (i) one or more parent nodes associated with the given node, or (ii) one or more child nodes associated with the given node.

18. The method of claim 17, wherein one or more of the plurality of nodes also comprises a user node that represents a user associated with an area or a device within a physical space.

19. A computer program product for generating a map based on nodes of a hierarchical graph that stores and provides access to sensor data from devices within a physical space, the computer program product comprising one or more computer readable storage devices having stored thereon computer-executable instructions that are executable by one or more processors of a computer system to cause the computer system to perform at least the following:

access a hierarchical graph that defines a topology of a physical space and comprises a plurality of nodes, the plurality of nodes of the hierarchical graph comprising a top node for the physical space and a plurality of other nodes coupled, through zero or more intermediate nodes, to the top node of the physical space, one or more of the plurality of nodes comprising an area node or a sub-area node, each area node and sub-area node representing an area or sub-area within the physical space, one or more of the plurality of nodes also comprising a device node, each device node representing a device located within the physical space, each device being configured to provide data or receive control signals; and

for a particular node of the plurality of nodes,

generate map data corresponding to the particular node, the generated map data being associated with generating at least a portion of a map corresponding to the particular node; and

store the generated map data corresponding to the particular node within the hierarchical graph such that the stored generated map data can be used to generate the portion of the map corresponding to the particular node.

20. The computer program product in accordance with claim 19, wherein the computer-executable instructions further include instructions that are executable to cause the computer system to generate a portion of a map corresponding to the particular node based on the generated map data.