Localization using grid-based representation of map contraints

Patent metadata

Field	Value
Publication number	US-12106014-B2
Application number	US-202017134227-A
Country	US
Kind code	B2
Filing date	Dec 25, 2020
Priority date	Dec 25, 2020
Publication date	Oct 1, 2024
Grant date	Oct 1, 2024

Abstract

A method and a device for localization using grid-based localization of map constraints are described. In an example, an indoor space is divided into a grid of tessellated polygonal tiles in a hierarchical structure. The grid is correlated with physical entities in the indoor space by associating each physical entity with a polygonal tile. Further, an absolute probability value indicative of presence of a device therein is associated with each polygonal tile. As part of associating, the absolute probability value is allocated to each polygonal tile in each hierarchical level to create a probability map for the indoor space. The probability map is used to generate a grid map for the indoor space and the grid map is usable to determine location of the device in the indoor space.

First claim

What is claimed is:

1. A computer implemented method comprising:
dividing, by a processor, an indoor space into a grid of a plurality of polygonal tiles abutting adjacent polygonal tiles, the grid comprising a hierarchical structure of the plurality of polygonal tiles, wherein a polygonal tile at a level in the hierarchical structure is representable by polygonal tiles at other levels in the hierarchical structure;
correlating, by the processor, the grid with physical entities in the indoor space, the correlating comprising associating each physical entity with a polygonal tile from amongst the plurality of polygonal tiles;
associating, by the processor, with each of the plurality of polygonal tiles an absolute probability value of presence of a mobile device therein, wherein the associating comprises allocating the absolute probability value with each of the plurality of polygonal tiles in each hierarchical level in the hierarchical structure to create a probability map for the indoor space, and wherein the absolute probability value indicates whether the mobile device can be present in the polygonal tile, without any temporal context, instead of indicating the probability of the mobile device being present in the polygonal tile at any given instant, and wherein different absolute probability values are associated with different polygonal tiles based on a distance of the polygonal tile from the physical entity in another polygonal tile;
generating, by the processor, a grid map for the indoor space based on the probability map;
based on the probability map based grid map, performing calibration of the indoor space for generating a fingerprint map for the indoor space, the calibration comprising obtaining spatial data at known locations for each of the georeferenced polygonal tile in the various hierarchical levels in the grid; and
providing, by the processor, indoor positioning services to mobile devices in the indoor space using the grid map, wherein the mobile devices are to perform localization based on corresponding spatial data in conjunction with the fingerprint map.

2. The method of claim 1 , wherein the absolute probability value associated with a polygonal tile increases as distance of the polygonal tile from a wall in the indoor space increases.

3. The method of claim 1 , wherein the absolute probability value is maximum for the polygonal tile located in a mid-region of a narrow path in the indoor space.

4. The method of claim 1 , wherein the absolute probability value is minimum for the polygonal tile located adjacent to a wall in the indoor space.

5. The method of claim 1 , wherein the correlating comprises:
georeferencing each of the physical entities in the indoor space; and
spatially indexing the grid with the physical entities in the indoor space to correlate a georeference of each physical entity with the polygonal tile from amongst the plurality of polygonal tiles at each hierarchical level.

6. The method of claim 1 , wherein the absolute probability value associated with the polygonal tile is based on a physical entity correlated to the polygonal tile, the correlation indicative of presence of the physical entity in that polygonal tile.

7. The method of claim 1 , wherein the physical entities comprise walls, passages, elevator shafts, escalators, open spaces, and doorways.

8. The method of claim 1 , wherein the plurality of polygonal tiles have a symmetrical hexagon shape.

9. The method of claim 1 , wherein the plurality of polygonal tiles have one of a same asymmetrical polygon shape and different symmetrical polygon shapes.

10. The method of claim 1 , wherein a first set of polygonal tiles in one hierarchical level in the hierarchical structure are symmetrical and of a first shape and a second set of polygonal tiles in another hierarchical level in the hierarchical structure are symmetrical and of a second shape, wherein a plurality of second set of polygonal tiles cover a single polygonal tile from the first set.

11. A server computing device comprising:
a processor; and
a memory storing a set of instructions, the instructions executable in the processor to:
divide an indoor space into a grid of a plurality of polygonal tiles abutting adjacent polygonal tiles, the grid comprising a hierarchical structure of the plurality of polygonal tiles, wherein each polygonal tile at a level in the hierarchical structure is representable by polygonal tiles in other levels in the hierarchical structure;
correlate the grid with physical entities in the indoor space, the correlating comprising associating each physical entity with a polygonal tile from amongst the plurality of polygonal tiles;
associate with each of the plurality of polygonal tiles an absolute probability value indicative of a potential instantaneous location of a mobile device therein, wherein the associating comprises allocating the absolute probability value with each of the plurality of polygonal tiles in each hierarchical level in the hierarchical structure to create a probability map for the indoor space, and wherein the absolute probability value indicates whether the mobile device can be present in the polygonal tile, without any temporal context, instead of indicating the probability of the mobile device being present in the polygonal tile at any given instant, and wherein different absolute probability values are associated with different polygonal tiles based on a distance of the polygonal tile from the physical entity in another polygonal tile;

generate a grid map for the indoor space based on the probability map;
based on the probability map based grid map, perform calibration of the indoor space for generating a fingerprint map for the indoor space, the calibration comprising obtaining spatial data at known locations for each of the georeferenced polygonal tile in the various hierarchical levels in the grid; and
providing, by the processor, indoor positioning services to mobile devices in the indoor space using the grid map, wherein the mobile devices are to perform localization based on corresponding spatial data in conjunction with the fingerprint map.

12. The server computing device of claim 11 , wherein the absolute probability value associated with a polygonal tile increases as distance of the polygonal tile from a wall in the indoor space increases.

13. The server computing device of claim 11 , wherein the absolute probability value is maximum for the polygonal tile located in a mid-region of a narrow path in the indoor space.

14. The server computing device of claim 11 , wherein the absolute probability value is minimum for the polygonal tile located adjacent to a wall in the indoor space.

15. The server computing device of claim 11 further comprising instructions executable in the processor to;
georeferenced each of the physical entities in the indoor space; and
spatially index the grid with the physical entities in the indoor space to correlate a georeference of each physical entity with the polygonal tile from amongst the plurality of polygonal tiles at each hierarchical level.

16. The server computing device of claim 11 , wherein the absolute probability value associated with the polygonal tile is based on a physical entity correlated to the polygonal tile, the correlation indicative of presence of the physical entity in that polygonal tile.

17. The server computing device of claim 11 , wherein the physical entities comprise walls, passages, elevator shafts, escalators, open spaces, and doorways.

18. The server computing device of claim 11 , where

Assignees

• Karon Joshua
• Mahmood Ahmed
• Huberman Sean
• Mapsted Corp

Inventors

• Karon Joshua
• Mahmood Ahmed
• Huberman Sean

Classifications

• G01C21/3878

  Hierarchical structures, e.g. layering · CPC title

• G06F2111/08

  Probabilistic or stochastic CAD · CPC title

• G06F2111/04

  Constraint-based CAD · CPC title

• G01C21/3881

  Tile-based structures · CPC title

• G01C21/3804

  Creation or updating of map data · CPC title