ROUTING GRAPHS FOR BUILDINGS

• US 20110082638A1
• Filed: 09/03/2010
• Published: 04/07/2011
• Est. Priority Date: 10/01/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Das, Saumitra Mohan, Khorashadi, Behrooz, Gupta, Rajarshi
• Granted Patent: US 9,116,003 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G06F 30/13 Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

The subject matter disclosed herein relates to systems, methods, etc. for creating a routing graph based at least partly on building information. For certain example implementations, a method includes obtaining building information descriptive of at least a portion of a building structure. A grid of points may be superimposed onto the building information. At least one routing graph may be created based at least in part on the superimposed grid of points and the building information. Other example implementations are also described.

Claims

1. A method comprising:

obtaining electrical signals representing building information descriptive of at least a portion of a building structure;

superimposing a grid of points onto said building information; and

generating electrical signals representing at least one routing graph based at least in part on said superimposed grid of points and said building information.

2. The method of claim 1, wherein said method further comprises:

interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links.

3. The method of claim 2, wherein said traversable links comprise links that do not intersect said building structure of said building information.

4. The method of claim 3, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

5. The method of claim 1, wherein said method further comprises:

determining multiple autonomous areas of said building information based at least in part on said superimposed grid of points and one or more walls of said building information.

6. The method of claim 5, wherein said method further comprises:

modeling doors of said building information in a closed state; and

interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information, said building structure including said doors that are modeled in a closed state.

7. The method of claim 6, wherein said interconnecting comprises:

forming multiple disconnected graphs from said superimposed grid of points, said multiple disconnected graphs comprising said multiple autonomous areas.

8. The method of claim 5, wherein said method further comprises:

identifying at least one point that is external to said building structure of said building information; and

ascertaining from said multiple autonomous areas at least one autonomous area that is external to said building structure of said building information based at least partly on said at least one point.

9. The method of claim 1, wherein said method further comprises:

determining one or more entrances and/or exits of said building structure of said building information based at least partly on at least one autonomous area, which is ascertained to be external to said building structure, using said superimposed grid of points.

10. The method of claim 1, wherein said method further comprises:

from multiple autonomous areas, determining which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible.

11. The method of claim 10, wherein said method further comprises:

modeling doors of said building information in an open state; and

interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information.

12. The method of claim 11, wherein said determining further comprises:

determining that a given autonomous area of said multiple autonomous areas is a feasible autonomous area if said given autonomous area is reachable from an external point by traversing the interconnected points of said superimposed grid of points; and

determining that a given autonomous area of said multiple autonomous areas is an infeasible autonomous area if said given autonomous area is not reachable from an external point by traversing the interconnected points of said superimposed grid of points.

13. The method of claim 1, wherein said method further comprises:

from multiple autonomous areas, detecting one or more hallways of said building information based at least partly on a predetermined threshold of doors to which a given autonomous area of said multiple autonomous areas is directly connected.

14. The method of claim 1, wherein said method further comprises:

overlaying annotation information from said building information onto at least one connectivity graph to produce said at least one routing graph with annotated building information.

15. The method of claim 1, wherein said method further comprises:

providing to a mobile device navigational information relating to said building structure using said at least one routing graph.

16. The method of claim 1, wherein said method further comprises:

executing instructions, by a special purpose computing device, to direct the special purpose computing device to implement said method.

17. A special purpose computing device comprising:

at least one memory to store instructions; and

one or more processors to execute said instructions to;

obtain building information descriptive of at least a portion of a building structure;

superimpose a grid of points onto said building information; and

create at least one routing graph based at least in part on said superimposed grid of points and said building information.

18. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links.

19. The device of claim 18, wherein said traversable links comprise links that do not intersect said building structure of said building information.

20. The device of claim 19, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

21. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

determine multiple autonomous areas of said building information based at least in part on said superimposed grid of points and one or more walls of said building information.

22. The device of claim 21, wherein said one or more processors are further to execute said instructions to:

model doors of said building information in a closed state; and

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information, said building structure including said doors that are modeled in a closed state.

23. The device of claim 22, wherein to interconnect said at least a portion of the adjacent points said one or more processors are further to execute said instructions using said traversable links by:

forming multiple disconnected graphs from said superimposed grid of points, said multiple disconnected graphs comprising said multiple autonomous areas.

24. The device of claim 21, wherein said one or more processors are further to execute said instructions to:

identify at least one point that is external to said building structure of said building information; and

ascertain from said multiple autonomous areas at least one autonomous area that is external to said building structure of said building information based at least partly on said at least one point.

25. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

determine one or more entrances and/or exits of said building structure of said building information based at least partly on at least one autonomous area, which is ascertained to be external to said building structure, using said superimposed grid of points.

26. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

from multiple autonomous areas, determine which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible.

27. The device of claim 26, wherein said one or more processors are further to execute said instructions to:

model doors of said building information in an open state; and

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information.

28. The device of claim 27, wherein to determine which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible said one or more processors are further to execute said instructions by:

determining that a given autonomous area of said multiple autonomous areas is a feasible autonomous area if said given autonomous area is reachable from an external point by traversing the interconnected points of said superimposed grid of points; and

determining that a given autonomous area of said multiple autonomous areas is an infeasible autonomous area if said given autonomous area is not reachable from an external point by traversing the interconnected points of said superimposed grid of points.

29. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

from multiple autonomous areas, detect one or more hallways of said building information based at least partly on a predetermined threshold of doors to which a given autonomous area of said multiple autonomous areas is directly connected.

30. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

overlay annotation information from said building information onto at least one connectivity graph to produce said at least one routing graph with annotated building information.

31. The device of claim 17, wherein said one or more processors are further to execute said instructions to:

provide to a mobile device navigational information relating to said building structure using said at least one routing graph.

32. An article comprising:

at least one storage medium having stored thereon instructions executable by one or more processors to;

obtain building information descriptive of at least a portion of a building structure;

superimpose a grid of points onto said building information; and

create at least one routing graph based at least in part on said superimposed grid of points and said building information.

33. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links.

34. The article of claim 33, wherein said traversable links comprise links that do not intersect said building structure of said building information.

35. The article of claim 34, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

36. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine multiple autonomous areas of said building information based at least in part on said superimposed grid of points and one or more walls of said building information.

37. The article of claim 36, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

model doors of said building information in a closed state; and

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information, said building structure including said doors that are modeled in a closed state.

38. The article of claim 37, wherein to interconnect said at least a portion of the adjacent points said at least one storage medium has stored thereon further instructions executable by one or more processors to:

form multiple disconnected graphs from said superimposed grid of points, said multiple disconnected graphs comprising said multiple autonomous areas.

39. The article of claim 36, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

identify at least one point that is external to said building structure of said building information; and

ascertain from said multiple autonomous areas at least one autonomous area that is external to said building structure of said building information based at least partly on said at least one point.

40. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine one or more entrances and/or exits of said building structure of said building information based at least partly on at least one autonomous area, which is ascertained to be external to said building structure, using said superimposed grid of points.

41. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

from multiple autonomous areas, determine which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible.

42. The article of claim 41, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

model doors of said building information in an open state; and

interconnect at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information.

43. The article of claim 42, wherein to determine which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible said at least one storage medium has stored thereon further instructions executable by one or more processors to:

determine that a given autonomous area of said multiple autonomous areas is a feasible autonomous area if said given autonomous area is reachable from an external point by traversing the interconnected points of said superimposed grid of points; and

determine that a given autonomous area of said multiple autonomous areas is an infeasible autonomous area if said given autonomous area is not reachable from an external point by traversing the interconnected points of said superimposed grid of points.

44. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

from multiple autonomous areas, detect one or more hallways of said building information based at least partly on a predetermined threshold of doors to which a given autonomous area of said multiple autonomous areas is directly connected.

45. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

overlay annotation information from said building information onto at least one connectivity graph to produce said at least one routing graph with annotated building information.

46. The article of claim 32, wherein said at least one storage medium has stored thereon further instructions executable by one or more processors to:

provide to a mobile device navigational information relating to said building structure using said at least one routing graph.

47. An apparatus comprising:

means for obtaining building information descriptive of at least a portion of a building structure;

means for superimposing a grid of points onto said building information; and

means for creating at least one routing graph based at least in part on said superimposed grid of points and said building information.

48. The apparatus of claim 47, further comprising:

means for interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links.

49. The apparatus of claim 48, wherein said traversable links comprise links that do not intersect said building structure of said building information.

50. The apparatus of claim 49, wherein points of said superimposed grid of points comprise nodes of said at least one routing graph, and said traversable links comprise edges of said at least one routing graph.

51. The apparatus of claim 47, further comprising:

means for determining multiple autonomous areas of said building information based at least in part on said superimposed grid of points and one or more walls of said building information.

52. The apparatus of claim 51, further comprising:

means for modeling doors of said building information in a closed state; and

means for interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information, said building structure including said doors that are modeled in a closed state.

53. The apparatus of claim 52, wherein said means for interconnecting said at least a portion of the adjacent points comprises:

means for forming multiple disconnected graphs from said superimposed grid of points, said multiple disconnected graphs comprising said multiple autonomous areas.

54. The apparatus of claim 51, further comprising:

means for identifying at least one point that is external to said building structure of said building information; and

means for ascertaining from said multiple autonomous areas at least one autonomous area that is external to said building structure of said building information based at least partly on said at least one point.

55. The apparatus of claim 47, further comprising:

means for determining one or more entrances and/or exits of said building structure of said building information based at least partly on at least one autonomous area, which is ascertained to be external to said building structure, using said superimposed grid of points.

56. The apparatus of claim 47, further comprising:

means for determining which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible from multiple autonomous areas.

57. The apparatus of claim 56, further comprising:

means for modeling doors of said building information in an open state; and

means for interconnecting at least a portion of adjacent points of said superimposed grid of points with traversable links that do not intersect said building structure of said building information.

58. The apparatus of claim 57, wherein said means for determining which one or more autonomous areas are feasible and whether one or more autonomous areas are infeasible comprises:

means for determining that a given autonomous area of said multiple autonomous areas is a feasible autonomous area if said given autonomous area is reachable from an external point by traversing the interconnected points of said superimposed grid of points; and

means for determining that a given autonomous area of said multiple autonomous areas is an infeasible autonomous area if said given autonomous area is not reachable from an external point by traversing the interconnected points of said superimposed grid of points.

59. The apparatus of claim 47, further comprising:

from multiple autonomous areas, means for detecting one or more hallways of said building information based at least partly on a predetermined threshold of doors to which a given autonomous area of said multiple autonomous areas is directly connected.

60. The apparatus of claim 47, further comprising:

means for overlaying annotation information from said building information onto at least one connectivity graph to produce said at least one routing graph with annotated building information.

61. The apparatus of claim 47, further comprising:

means for providing to a mobile device navigational information relating to said building structure using said at least one routing graph.