Determining a likelihood of a directional transition at a junction in an encoded routability graph description

• US 8,706,413 B2
• Filed: 12/01/2011
• Issued: 04/22/2014
• Est. Priority Date: 10/17/2011
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Gupta, Rajarshi
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): Trivedi, Atul
• Application Number:
  US13/309,304
• Publication Number:
  US 20130096885A1
• Time in Patent Office: 873 Days
• Field of Search: 701/400, 701408-422, 701433-434, 701468-471, 701/522
• US Class Current: 701/434
• 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;

(i) one or more features of said encoded map,

(ii) a number of possible origination paths in said encoded routability graph connected to said junction through said ingress edge leading toward said junction, and

(iii) a number of possible destination paths connected to said junction through said individual egress edges leading away from said junction.

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

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

3. The method of claim 1, 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.

4. The method of claim 3, 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.

5. The method of claim 1, 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.

6. The method of claim 5, 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.

7. The method of claim 1, 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.

8. The method of claim 1, 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.

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

10. The method of claim 1, 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.

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

12. The method of claim 11, 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.

13. 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.

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

15. 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;

(i) one or more features of said encoded map,

((ii) a number of possible origination paths in said encoded routability graph connected to said junction through said ingress edge leading toward said junction, and

(iii) a number of possible destination paths connected to said junction through said individual egress edges leading away from said junction.

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

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

17. The apparatus of claim 15, 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.

18. The apparatus of claim 17, 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.

19. The apparatus of claim 15, 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.

20. The apparatus of claim 19, 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.

21. The apparatus of claim 15, 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.

22. The apparatus of claim 15, 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.

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

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

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

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

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

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

27. 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;

(i) one or more features of said encoded map,

(ii) a number of possible origination paths in said encoded routability graph connected to said junction through said ingress edge leading toward said junction, and

(iii) a number of possible destination paths connected to said junction through said individual egress edges leading away from said junction.

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

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

29. The computing platform of claim 27, 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.

30. The computing platform of claim 29, 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.

31. The computing platform of claim 27, 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.

32. The computing platform of claim 31, 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.

33. The computing platform of claim 27, 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.

34. The computing platform of claim 27, 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.

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

36. The computing platform of claim 27, 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.

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

38. The computing platform of claim 27, 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.

39. The computing platform of claim 27, wherein said computing platform is provided within a mobile device.

40. 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;

(i) one or more features of said encoded map,

(ii) a number of possible origination paths in said encoded routability graph connected to said junction through said ingress edge leading toward said junction, and

(iii) a number of possible destination paths connected to said junction through said individual egress edges leading away from said junction.

41. The article of claim 40, 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 said number of said possible destination paths through said individual egress edges leading away from said junction to said number of said possible origination paths through said ingress edge leading toward said junction.

42. The article of claim 40, 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.

43. The article of claim 42, 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.

44. The article of claim 40, 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.

45. The article of claim 44, 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.

46. The article of claim 40, 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.

47. The article of claim 40, 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.

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

49. The article of claim 40, 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.

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

51. The article of claim 40, 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.

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