ROUTABILITY GRAPH WITH PREDETERMINED NUMBER OF WEIGHTED EDGES FOR ESTIMATING A TRAJECTORY OF A MOBILE DEVICE

• US 20130345967A1
• Filed: 06/21/2012
• Published: 12/26/2013
• Est. Priority Date: 06/21/2012
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: PAKZAD, Payam
• Application Number:
  US13/530,005
• Publication Number:
  US 20130345967A1
• Time in Patent Office: Days
• US Class Current: 701/431
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/16 by integrating acceleration or speed, i.e. inertial navigation
• 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

Abstract

Various methods, apparatuses and/or articles of manufacture are provided for use in one or more mobile devices to provide positioning based, at least in part, on a routability graph comprising a predetermined number of weighted edges for estimating a trajectory of a mobile device. Various methods, apparatuses and/or articles of manufacture are provided for use in one or more electronic devices to support mobile device positioning based, at least in part, on a routability graph comprising a predetermined number of weighted edges for estimating a trajectory of a mobile device.

Claims

1. A method comprising, with a mobile device:

receiving a weight value for at least one edge connected to at least one node of a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node;

affecting a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value; and

presenting navigation information that is generated based, at least in part, on said trajectory.

2. The method as recited in claim 1, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges.

3. An apparatus for use in a mobile device, the apparatus comprising:

means for receiving a weight value for at least one edge connected to at least one node of a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node;

means for affecting a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value;

means for generating navigation information based, at least in part, on said trajectory; and

means for presenting said navigation information to a user.

4. A mobile device comprising:

a communication interface;

an output unit;

one or more processing units to;

receive, via said communication interface, a weight value for at least one edge connected to at least one node of a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node;

affect a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value;

determine navigation information based, at least in part, on said trajectory; and

initiate presentation of said navigation information to a user via said output unit.

5. An article for use by a mobile device, the article comprising:

a non-transitory computer readable medium having stored therein computer implementable instructions executable by one or more processing units in said mobile device to;

receive a weight value for at least one edge connected to at least one node of a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node;

affect a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value;

determine navigation information based, at least in part, on said trajectory; and

initiate presentation of said navigation information to a user via an output unit.

6. A method comprising, with a mobile device:

obtaining a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges;

obtaining a weight value for at least one edge connected to said at least one node, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node; and

affecting a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value.

7. The method as recited in claim 6, and further comprising, with said mobile device:

obtaining one or more measurement values indicative of movement of said mobile device within said indoor environment; and

affecting said motion model in estimating said trajectory of said mobile device based, at least in part, on said one or more measurement values.

8. The method as recited in claim 7, and further comprising, with said mobile device:

obtaining said one or more measurement values via one or more sensors, said one or more sensors comprising at least one of;

one or more communication interfaces;

one or more inertial sensors; and

/or one or more environmental sensors.

9. The method as recited in claim 6, and further comprising, with said mobile device:

obtaining measurement information indicative of one or more positions of said mobile device applied to samples of a probability distribution approximated, at least in part, using past measurements of positions of said mobile device and/or other mobile devices within said indoor environment; and

affecting said motion model in estimating said trajectory of said mobile device based, at least in part, on said measurement information.

10. The method as recited in claim 6, and further comprising, with said mobile device:

identifying an edge length value for at least said at least one edge, said edge length value representing a corresponding distance traveled in said indoor environment with respect to said electronic map; and

affecting said motion model in estimating said trajectory of said mobile device based, at least in part, on said edge length value.

11. The method as recited in claim 6, and further comprising, with said mobile device:

obtaining a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge; and

affecting said decision of said motion model to transition said state along said at least one edge in estimating said trajectory of said mobile device based, at least in part, on said second weight value.

12. The method as recited in claim 11, wherein said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

13. The method as recited in claim 6, wherein said intersecting points of said multi-dimensional grid are uniformly distributed with regard to at least one dimension.

14. The method as recited in claim 13, wherein said multi-dimensional grid comprises a two-dimensional square grid.

15. The method as recited in claim 6, wherein said threshold number of edges is based on a maximum number of neighboring nodes.

16. An apparatus for use in a mobile device, the apparatus comprising:

means for obtaining a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges;

means for a weight value for at least one edge connected to said at least one node, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node; and

means for affecting a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value.

17. The apparatus as recited in claim 16, and further comprising:

means for obtaining one or more measurement values indicative of movement of said mobile device within said indoor environment; and

means for affecting said motion model in estimating said trajectory of said mobile device based, at least in part, on said one or more measurement values.

18. The apparatus as recited in claim 17, and further comprising:

means for obtaining said one or more measurement values based, at least in part, one or more wireless signals, one or more sensed inertial forces, and/or one or more sensed environmental parameters.

19. The apparatus as recited in claim 16, and further comprising:

means for obtaining measurement information indicative of one or more positions of said mobile device applied to samples of a probability distribution approximated, at least in part, using past measurements of positions of said mobile device and/or other mobile devices within said indoor environment; and

means for affecting said motion model in estimating said trajectory of said mobile device based, at least in part, on said measurement information.

20. The apparatus as recited in claim 16, and further comprising:

means for identifying an edge length value for at least said at least one edge, said edge length value representing a corresponding distance traveled in said indoor environment with respect to said electronic map; and

means for affecting said motion model in estimating said trajectory of said mobile device based, at least in part, on said edge length value.

21. The apparatus as recited in claim 16, and further comprising:

means for obtaining a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge; and

means for affecting said decision of said motion model to transition said state along said at least one edge in estimating said trajectory of said mobile device based, at least in part, on said second weight value.

22. The apparatus as recited in claim 21, wherein said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

23. The apparatus as recited in claim 16, wherein said intersecting points of said multi-dimensional grid are uniformly distributed with regard to at least one dimension.

24. The apparatus as recited in claim 23, wherein said multi-dimensional grid comprises a two-dimensional square grid.

25. The apparatus as recited in claim 16, wherein said threshold number of edges is based on a maximum number of neighboring nodes.

26. A mobile device comprising:

one or more processing units to;

obtain a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges;

obtain a weight value for at least one edge connected to said at least one node, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node; and

affect a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value.

27. The mobile device as recited in claim 26, said one or more processing units to further:

obtain one or more measurement values indicative of movement of said mobile device within said indoor environment; and

affect said motion model in estimating said trajectory of said mobile device based, at least in part, on said one or more measurement values.

28. The mobile device as recited in claim 27, and further comprising:

at least one of;

one or more communication interfaces;

one or more inertial sensors; and

/or one or more environmental sensors; and

wherein said one or more processing units to further;

obtain said one or more measurement values via at least one of;

said one or more communication interfaces;

said one or more inertial sensors; and

/or said one or more environmental sensors.

29. The mobile device as recited in claim 26, said one or more processing units to further:

obtain measurement information indicative of one or more positions of said mobile device applied to samples of a probability distribution approximated at least in part using past measurements of positions of said mobile device and/or other mobile devices within said indoor environment; and

affect said motion model in estimating said trajectory of said mobile device based, at least in part, on said measurement information.

30. The mobile device as recited in claim 26, said one or more processing units to further:

identify an edge length value for at least said at least one edge, said edge length value representing a corresponding distance traveled in said indoor environment with respect to said electronic map; and

affect said motion model in estimating said trajectory of said mobile device based, at least in part, on said edge length value.

31. The mobile device as recited in claim 26, said one or more processing units to further:

obtain a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge; and

affect said decision of said motion model to transition said state along said at least one edge in estimating said trajectory of said mobile device based, at least in part, on said second weight value.

32. The mobile device as recited in claim 31, wherein said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

33. The mobile device as recited in claim 26, wherein said intersecting points of said multi-dimensional grid are uniformly distributed with regard to at least one dimension.

34. The mobile device as recited in claim 33, wherein said multi-dimensional grid comprises a two-dimensional square grid.

35. The mobile device as recited in claim 26, wherein said threshold number of edges is based on a maximum number of neighboring nodes.

36. An article for use by a mobile device, the article comprising:

a non-transitory computer readable medium having stored therein computer implementable instructions executable by one or more processing units in said mobile device to;

obtain a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges;

obtain a weight value for at least one edge connected to said at least one node, said weight value representing a predetermined likelihood that an estimated trajectory of an object having reached said at least one node subsequently follows said at least one edge away from said at least one node; and

affect a decision of a motion model to transition a state along said at least one edge in estimating a trajectory of said mobile device based, at least in part, on said weight value.

37. The article as recited in claim 36, said computer implementable instructions being further executable to:

obtain one or more measurement values indicative of movement of said mobile device within said indoor environment; and

affect said motion model in estimating said trajectory of said mobile device based, at least in part, on said one or more measurement values.

38. The article as recited in claim 37, said computer implementable instructions being further executable to:

obtain said one or more measurement values via one or more sensors, said one or more sensors comprising at least one of;

one or more communication interfaces;

one or more inertial sensors; and

/or one or more environmental sensors.

39. The article as recited in claim 36, said computer implementable instructions being further executable to:

obtain measurement information indicative of one or more positions of said mobile device applied to samples of a probability distribution approximated at least in part using past measurements of positions of said mobile device and/or other mobile devices within said indoor environment; and

affect said motion model in estimating said trajectory of said mobile device based, at least in part, on said measurement information.

40. The article as recited in claim 36, said computer implementable instructions being further executable to:

identify an edge length value for at least said at least one edge, said edge length value representing a corresponding distance traveled in said indoor environment with respect to said electronic map; and

affect said motion model in estimating said trajectory of said mobile device based, at least in part, on said edge length value.

41. The article as recited in claim 36, said computer implementable instructions being further executable to:

obtain a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge; and

affect said decision of said motion model to transition said state along said at least one edge in estimating said trajectory of said mobile device based, at least in part, on said second weight value.

42. The article as recited in claim 41, wherein said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

43. The article as recited in claim 36, wherein said intersecting points of said multi-dimensional grid are uniformly distributed with regard to at least one dimension.

44. The article as recited in claim 43, wherein said multi-dimensional grid comprises a two-dimensional square grid.

45. The article as recited in claim 36, wherein said threshold number of edges is based on a maximum number of neighboring nodes.

46. A method comprising, with at least one computing platform:

obtaining a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths for an object to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges; and

determining a weight value for at least one edge connected to said at least one node, said weight value being based, at least in part, on a likelihood that an estimated trajectory of said object having reached said at least one node subsequently follows said at least one edge away from said at least one node.

47. The method as recited in claim 46, and further comprising, with said at least one computing platform:

identifying an edge length value of at least said at least one edge, said edge length value comprising one of a predetermined number of edge length values.

48. The method as recited in claim 47, wherein each of said predetermined number of edge length values represents a corresponding distance in said indoor environment.

49. The method as recited in claim 46, and further comprising, with said at least one computing platform:

determining a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge.

50. The method as recited in claim 49, and further comprising, with said at least one computing platform:

determining said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

51. The method as recited in claim 46, wherein said intersecting points of said multi-dimensional grid are uniformly distributed with regard to at least one dimension.

52. The method as recited in claim 51, wherein said multi-dimensional grid comprises a two-dimensional square grid.

53. The method as recited in claim 46, wherein said threshold number of edges is based on a maximum number of neighboring nodes.

54. The method as recited in claim 46, and further comprising, with said at least one computing platform:

initiating transmission of at least said weight value for said at least one edge to at least one mobile device.

55. The method as recited in claim 46, wherein said at least one computing platform is provided in a mobile device.

56. An apparatus comprising:

means for obtaining a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths for an object to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges; and

means for determining a weight value for at least one edge connected to said at least one node, said weight value being based, at least in part, on a likelihood that an estimated trajectory of said object having reached said at least one node subsequently follows said at least one edge away from said at least one node.

57. The apparatus as recited in claim 56, and further comprising:

means for identifying an edge length value of at least said at least one edge, said edge length value comprising one of a predetermined number of edge length values.

58. The apparatus as recited in claim 56, and further comprising:

means for determining a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge.

59. The apparatus as recited in claim 58, and further comprising:

means for determining said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

60. The apparatus as recited in claim 56, and further comprising:

means for transmitting at least said weight value for said at least one edge to at least one mobile device.

61. The apparatus as recited in claim 56, wherein said apparatus is provided in a mobile device.

62. A device comprising:

memory; and

one or more processing units to;

obtain a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths for an object to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges; and

determine a weight value for at least one edge connected to said at least one node, said weight value being based, at least in part, on a likelihood that an estimated trajectory of said object having reached said at least one node subsequently follows said at least one edge away from said at least one node.

63. The device as recited in claim 62, said one or more processing units to further:

identify an edge length value of at least said at least one edge, said edge length value comprising one of a predetermined number of edge length values.

64. The device as recited in claim 62, said one or more processing units to further:

determine a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge.

65. The device as recited in claim 64, said one or more processing units to further:

determine said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

66. The device as recited in claim 62, and further comprising:

a communication interface; and

wherein said one or more processing units to further;

initiate transmission of at least said weight value for said at least one edge to at least one mobile device via said communication interface.

67. The device as recited in claim 62, wherein said device comprises a mobile device.

68. An article for use in at least one computing device, the article comprising:

a non-transitory computer readable medium having stored therein computer implementable instructions executable by one or more processing units of a computing platform to;

obtain a routability graph corresponding to an electronic map of at least a portion of an indoor environment, said routability graph specifying a predetermined number of feasible paths for an object to follow within said portion of said indoor environment, wherein at least one of said predetermined number of feasible paths is defined as passing through at least one of a plurality of nodes arranged at intersecting points of a multi-dimensional grid, and each of said plurality of nodes is interconnected to one or more neighboring nodes via at least one but no more than a threshold number of edges; and

determine a weight value for at least one edge connected to said at least one node, said weight value being based, at least in part, on a likelihood that an estimated trajectory of said object having reached said at least one node subsequently follows said at least one edge away from said at least one node.

69. The article as recited in claim 68, said computer implementable instructions being further executable to:

identify an edge length value of at least said at least one edge, said edge length value comprising one of a predetermined number of edge length values.

70. The article as recited in claim 68, said computer implementable instructions being further executable to:

determine a second weight value for said at least one edge, said second weight value being based, at least in part, on one or more features of said electronic map within a threshold distance of said at least one edge.

71. The article as recited in claim 70, said computer implementable instructions being further executable to:

determine said second weight value for said at least one edge based, at least in part, on one or more other weight values for at least one of said one or more neighboring nodes interconnected to said at least one node.

72. The article as recited in claim 68, said computer implementable instructions being further executable to:

initiate transmission of at least said weight value for said at least one edge to at least one mobile device.

73. The article as recited in claim 68, wherein said computing platform is provided in a mobile device.

74. A method comprising, with at least one computing platform:

determining one or more feasible paths in a routability graph corresponding to an electronic map for an indoor environment, the routability graph representing a two-dimensional grid comprising edges connecting nodes at angles selected from a predetermined set of discrete angles relative to a datum; and

selectively estimating a trajectory of a mobile device along said one or more feasible paths based, at least in part, on a sequence of measurements indicative of one or more positions of said device applied to samples of a probability distribution approximated at least in part using past measurements of positions of devices in said indoor environment.

75. The method as recited in claim 74, wherein edge length values of said edges are selected from a predetermined set of lengths.

76. The method as recited in claim 74, wherein said set of discrete angles are provided in 45 degree increments.

77. The method as recited in claim 74, wherein said nodes connected by said edges are arranged at intersecting points in a square grid.

78. The method as recited in claim 74, wherein said set of discrete angles comprises integer multiples of a discrete sub-angle.

79. The method as recited in claim 78, wherein said discrete sub-angle is 45 degrees.

80. An apparatus comprising:

means for determining one or more feasible paths in a routability graph corresponding to an electronic map for an indoor environment, the routability graph representing a two-dimensional grid comprising edges connecting nodes at angles selected from a predetermined set of discrete angles relative to a datum; and

means for selectively estimating a trajectory of a mobile device along said one or more feasible paths based, at least in part, on a sequence of measurements indicative of one or more positions of said device applied to samples of a probability distribution approximated at least in part using past measurements of positions of devices in said indoor environment.

81. A mobile device comprising:

one or more processing units to;

determine one or more feasible paths in a routability graph corresponding to an electronic map for an indoor environment, the routability graph representing a two-dimensional grid comprising edges connecting nodes at angles selected from a predetermined set of discrete angles relative to a datum; and

selectively estimate a trajectory of a mobile device along said one or more feasible paths based, at least in part, on a sequence of measurements indicative of one or more positions of said device applied to samples of a probability distribution approximated at least in part using past measurements of positions of devices in said indoor environment.

82. An article comprising:

a non-transitory computer readable medium having stored therein computer implementable instructions that are executable by one or more processing units in a computing platform to;

determine one or more feasible paths in a routability graph corresponding to an electronic map for an indoor environment, the routability graph representing a two-dimensional grid comprising edges connecting nodes at angles selected from a predetermined set of discrete angles relative to a datum; and

selectively estimate a trajectory of a mobile device along said one or more feasible paths based, at least in part, on a sequence of measurements indicative of one or more positions of said device applied to samples of a probability distribution approximated at least in part using past measurements of positions of devices in said indoor environment.