DETERMINING A LIKELIHOOD OF A DIRECTIONAL TRANSITION AT A JUNCTION IN AN ENCODED ROUTABILITY GRAPH DESCRIPTION

• US 20130096885A1
• Filed: 12/01/2011
• Published: 04/18/2013
• Est. Priority Date: 10/17/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Gupta, Rajarshi
• Granted Patent: US 8,706,413 B2
• Time in Patent Office: Days
• US Class Current: 703/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation

Abstract

Techniques are provided, which may be implemented in various methods, apparatuses, and/or articles of manufacture, to obtain an encoded routability graph representative of feasible paths in an indoor environment represented by an encoded map, and assign likelihoods of transition from an ingress edge in the encoded routability graph to individual egress edges through a junction connecting the ingress edge to a plurality of egress edges based, at least in part, on one or more features of the encoded map.

Claims

1. A method comprising, with a computing platform:

obtaining an encoded routability graph representative of feasible paths in an indoor environment represented by an encoded map; and

assigning likelihoods of transition from an ingress edge in said encoded routability graph to individual egress edges through a junction connecting said ingress edge to a plurality of egress edges based, at least in part, on one or more features of said encoded map.

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

assigning said likelihoods of transition based, at least in part, on possible origination paths in said encoded routability graph connected to said junction through said ingress edge and possible destination paths connected to said junction through said individual egress edges.

3. The method of claim 2, and further comprising, with said computing platform:

determining said likelihoods of transition based, at least in part, on a ratio of a number of said possible destination paths through said individual egress edges leading away from said junction to a number of said possible origination paths through said ingress edge leading toward said junction.

4. The method of claim 2, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes in a reduced version of said encoded routability graph.

5. The method of claim 4, wherein at least one of said nodes in said reduced version of said encoded routability graph is assigned a weight value that is based, at least in part, on a number of an encoded connectivity graph nodes represented by said at least one of said nodes.

6. The method of claim 2, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes representing points of interest in said encoded map along said encoded routability graph.

7. The method of claim 6, wherein at least one of said nodes representing at least one of said points of interest is assigned a weight value relative to at least one other node representing at least another one of said points of interest.

8. The method of claim 2, and further comprising, with said computing platform:

affecting at least one weight value assigned to at least one node in said encoded routability graph corresponding to said junction.

9. The method of claim 2, wherein at least one of said likelihoods of transition is representative of a possible turn-back transition at said junction in which said ingress edge further represents one of said plurality of egress edges.

10. The method of claim 9, wherein said at least one of said likelihoods of transition that is representative of said possible turn-back transition comprises a predetermined value.

11. The method of claim 2, and further comprising, with said computing platform:

determining at least one of said possible origination paths in said encoded routability graph using an all-pairs shortest path (APSP) algorithm.

12. The method of claim 1, wherein at least one of said likelihoods of transition comprises an a priori direction probability value.

13. The method of claim 12, wherein said a priori direction probability value is configured for use by a positioning engine in a mobile device to estimate a potential destination regarding a disposition of said mobile device with regard to said encoded routability graph.

14. The method of claim 1, and further comprising, with said computing platform:

providing at least one of said likelihoods of transition to at least one mobile device.

15. The method of claim 1, wherein said computing platform is provided within a mobile device.

16. An apparatus for use in a computing platform, the apparatus comprising:

means for obtaining an encoded routability graph representative of feasible paths in an indoor environment represented by an encoded map; and

means for assigning likelihoods of transition from an ingress edge in said encoded routability graph to individual egress edges through a junction connecting said ingress edge to a plurality of egress edges based, at least in part, on one or more features of said encoded map.

17. The apparatus of claim 16, and further comprising:

means for assigning said likelihoods of transition based, at least in part, on possible origination paths in said encoded routability graph connected to said junction through said ingress edge and possible destination paths connected to said junction through said individual egress edges.

18. The apparatus of claim 17, and further comprising:

means for determining said likelihoods of transition based, at least in part, on a ratio of a number of said possible destination paths through said individual egress edges leading away from said junction to a number of said possible origination paths through said ingress edge leading toward said junction.

19. The apparatus of claim 17, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes in a reduced version of said encoded routability graph.

20. The apparatus of claim 19, wherein at least one of said nodes in said reduced version of said encoded routability graph is assigned a weight value that is based, at least in part, on a number of an encoded connectivity graph nodes represented by said at least one of said nodes.

21. The apparatus of claim 17, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes representing points of interest in said encoded map along said encoded routability graph.

22. The apparatus of claim 21, wherein at least one of said nodes representing at least one of said points of interest is assigned a weight value relative to at least one other node representing at least another one of said points of interest.

23. The apparatus of claim 17, and further comprising:

means for affecting at least one weight value assigned to at least one node in said encoded routability graph corresponding to said junction.

24. The apparatus of claim 17, wherein at least one of said likelihoods of transition is representative of a possible turn-back transition at said junction in which said ingress edge further represents one of said plurality of egress edges.

25. The apparatus of claim 17, and further comprising:

means for determining at least one of said possible origination paths in said encoded routability graph.

26. The apparatus of claim 16, wherein at least one of said likelihoods of transition comprises an a priori direction probability value.

27. The apparatus of claim 16, and further comprising:

means for providing at least said likelihoods of transition to at least one mobile device.

28. The apparatus of claim 16, wherein said computing platform is provided within a mobile device.

29. A computing platform comprising:

memory; and

one or more processing units to;

obtain, from said memory, an encoded routability graph representative of feasible paths in an indoor environment represented by an encoded map; and

assign likelihoods of transition from an ingress edge in said encoded routability graph to individual egress edges through a junction connecting said ingress edge to a plurality of egress edges based, at least in part, on one or more features of said encoded map.

30. The computing platform of claim 29, said one or more processing units to further:

assign said likelihoods of transition based, at least in part, on possible origination paths in said encoded routability graph connected to said junction through said ingress edge and possible destination paths connected to said junction through said individual egress edges.

31. The computing platform of claim 30, said one or more processing units to further:

determine said likelihoods of transition based, at least in part, on a ratio of a number of said possible destination paths through said individual egress edges leading away from said junction to a number of said possible origination paths through said ingress edge leading toward said junction.

32. The computing platform of claim 30, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes in a reduced version of said encoded routability graph.

33. The computing platform of claim 32, wherein at least one of said nodes in said reduced version of said encoded routability graph is assigned a weight value that is based, at least in part, on a number of an encoded connectivity graph nodes represented by said at least one of said nodes.

34. The computing platform of claim 30, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes representing points of interest in said encoded map along said encoded routability graph.

35. The computing platform of claim 34, wherein at least one of said nodes representing at least one of said points of interest is assigned a weight value relative to at least one other node representing at least another one of said points of interest.

36. The computing platform of claim 30, said one or more processing units to further:

affect at least one weight value assigned to at least one node in said encoded routability graph corresponding to said junction.

37. The computing platform of claim 30, wherein at least one of said likelihoods of transition is representative of a possible turn-back transition at said junction in which said ingress edge further represents one of said plurality of egress edges.

38. The computing platform of claim 37, wherein said at least one of said likelihoods of transition that is representative of said possible turn-back transition comprises a predetermined value.

39. The computing platform of claim 30, said one or more processing units to further:

determine at least one of said possible origination paths in said encoded routability graph using an all-pairs shortest path (APSP) algorithm.

40. The computing platform of claim 29, wherein said likelihoods of transition comprise a priori direction probability values.

41. The computing platform of claim 29, and further comprising:

a network interface; and

said one or more processing units to further;

initiate transmission of at least one of said likelihoods of transition to at least one mobile device.

42. The computing platform of claim 29, wherein said computing platform is provided within a mobile device.

43. An article for use in a computing platform, the article comprising:

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

obtain an encoded routability graph representative of feasible paths in an indoor environment represented by an encoded map; and

assign likelihoods of transition from an ingress edge in said encoded routability graph to individual egress edges through a junction connecting said ingress edge to a plurality of egress edges based, at least in part, on one or more features of said encoded map.

44. The article of claim 43, said computer implementable instructions being further executable by said one or more processing units to:

assign said likelihoods of transition based, at least in part, on possible origination paths in said encoded routability graph connected to said junction through said ingress edge and possible destination paths connected to said junction through said individual egress edges.

45. The article of claim 44, said computer implementable instructions being further executable by said one or more processing units to:

determine said likelihoods of transition based, at least in part, on a ratio of a number of said possible destination paths through said individual egress edges leading away from said junction to a number of said possible origination paths through said ingress edge leading toward said junction.

46. The article of claim 44, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes in a reduced version of said encoded routability graph.

47. The article of claim 46, wherein at least one of said nodes in said reduced version of said encoded routability graph is assigned a weight value that is based, at least in part, on a number of an encoded connectivity graph nodes represented by said at least one of said nodes.

48. The article of claim 44, wherein said possible origination paths and said possible destination paths are based, at least in part, on point-to-point connections between nodes representing points of interest in said encoded map along said encoded routability graph.

49. The article of claim 48, wherein at least one of said nodes representing at least one of said points of interest is assigned a weight value relative to at least one other node representing at least another one of said points of interest.

50. The article of claim 44, said computer implementable instructions being further executable by said one or more processing units to:

affect at least one weight value assigned to at least one node in said encoded routability graph corresponding to said junction.

51. The article of claim 44, wherein at least one of said likelihoods of transition is representative of a possible turn-back transition at said junction in which said ingress edge further represents one of said plurality of egress edges.

52. The article of claim 51, wherein said at least one of said likelihoods of transition that is representative of said possible turn-back transition comprises a predetermined value.

53. The article of claim 44, said computer implementable instructions being further executable by said one or more processing units to:

determine at least one of said possible origination paths in said encoded routability graph using an all-pairs shortest path (APSP) algorithm.

54. The article of claim 43, wherein at least one of said likelihoods of transition comprises an a priori direction probability value.

55. The article of claim 43, said computer implementable instructions being further executable by said one or more processing units to:

initiate transmission of at least said likelihoods of transition to at least one mobile device.

56. The article of claim 43, wherein said computing platform is provided within a mobile device.