Scalable routing for mobile station navigation with location context identifier

• US 9,157,745 B2
• Filed: 01/10/2011
• Issued: 10/13/2015
• Est. Priority Date: 01/14/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Das, Saumitra Mohan, Khorashadi, Behrooz, Hardie, Edward Thomas Lingham
• Primary Examiner(s): To, Tuan C.
• Assistant Examiner(s): Kan, Yuri
• Application Number:
  US12/987,922
• Publication Number:
  US 20110172906A1
• Time in Patent Office: 1,737 Days
• Field of Search: 701/414, 701/424, 701/457, 701/500, 701/533, 701/436, 701/1, 701/431, 455/404.2, 455/456.3
• US Class Current: 1/1
• 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: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3644 Landmark guidance, e.g. using POIs or conspicuous other objects
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence
• CPC Class Codes: G01S 5/0269 Inferred or constrained positioning, e.g. employing knowledge of the physical or electromagnetic environment, state of motion or other contextual information to infer or constrain a position

Abstract

Examples disclosed herein may relate to identifying up to a specified amount of points of interest nearest to an estimated position of a mobile station on a first map, selecting a second map identified by a first location context identifier associated with a first point of interest of the identified points of interest, and determining a route from the estimated position of the mobile station to a destination point using the first map and the second map.

Claims

1. A method in a device, the method comprising:

estimating a first position of a mobile station on a first map, wherein the first map is associated with a first location context identifier;

identifying, by the device, one or more transition areas nearest to the position of the mobile station, on the first map associated with a first location context identifier;

identifying, by the device, a second location context identifier associated with at least a first transition area of the one or more transition areas, wherein the second location context identifier is associated with a second map; and

obtaining the second map.

2. The method of claim 1, wherein the first map comprises a map of an outdoor area, and wherein the second map comprises a map of an indoor area, and further comprising identifying a transition area leading outdoors.

3. The method of claim 1, further comprising:

identifying a second transition area of the one or more transition areas on the second map;

identifying, by the device, a third location context identifier associated with at least the second transition area, wherein the third location context identifier is associated with a third map; and

obtaining the third map.

4. The method of claim 1, and further comprising displaying:

a graphical representation of a first area based at least in part on the first map; and

a first plurality of transition areas from the one or more transition areas.

5. The method of claim 4, wherein the first plurality of transition areas further individually comprise a visual marker.

6. The method of claim 4, wherein the first plurality of transition areas comprises one or more pointers to a respective one or more maps.

7. The method of claim 2, wherein said second map comprises a routing graph of the indoor area.

8. The method of claim 7, wherein the routing graph comprises:

a plurality of vertices individually representing one of a plurality of hallway intersections;

one or more indoor area entrance points; and

a plurality of edges, comprising one or more edges to individually connect two or more of the plurality of hallway intersections and further comprising one or more edges to individually connect one of the plurality of hallway intersections and one of the one or more indoor area entrance points.

9. The method of claim 8, further comprising:

assigning one or more first weight values to a respective one or more of the plurality of edges according to a distance between two or more of the plurality of hallway intersections; and

assigning one or more second weight values to another respective one or more of the plurality of edges according to a distance between a first indoor area entrance point of the one or more indoor area entrance points and a hallway intersection of the plurality of hallway intersections.

10. The method of claim 9, further comprising determining a path from the first transition area to a destination point.

11. The method of claim 10, wherein determining the path comprises:

determining a first path from the first transition area to the first indoor area entrance point; and

determining a second path from the first indoor area entrance point to the destination point.

12. The method of claim 11, wherein determining the first path comprises determining a shortest route from the first transition area to the first indoor area entrance point based at least in part on locations of one or more of the plurality of hallway intersections, and further based at least in part on the one or more first weight values of the respective one or more of the plurality of edges connecting the two or more of the plurality of hallway intersections.

13. The method of claim 11, wherein determining the second path from the first indoor area entrance point to the destination point comprises plotting a line from the first indoor area entrance point to the destination point.

14. The method of claim 11, wherein determining the second path from the first indoor area entrance point to the destination point comprises:

generating a grid of the indoor area comprising partitioning the indoor area into a plurality of areas;

identifying one or more areas of the plurality of areas that do not contain obstructions; and

determining a shortest path through the one or more areas identified as not containing obstructions from the first indoor area entrance point to the destination point.

15. The method of claim 11, wherein said first indoor area entrance point comprises a location context identifier identifying the map of the indoor area, and wherein determining the second path from the first indoor area entrance point to the destination point comprises determining the second path using the map of the indoor area.

61. The method of claim 1, wherein each of the one or more transition comprises one of:

a staircase;

an elevator;

an escalator;

a moving walkway;

an external door;

an internal door separating two indoor portions of a building;

or

an internal door separating a connection between buildings.

62. The method of claim 1, wherein each of the one or more transition areas comprises a transition point on the first map that identifies a transition point to the second map.

63. The method of claim 1, wherein the first map and the second map both identify indoor areas.

64. The method of claim 1, wherein the first map comprises a map of an outdoor area, and wherein the second map comprises a map of an indoor area, and further comprising:

identifying a transition area leading outdoors;

identifying a second transition area of the one or more transition areas on the second map;

identifying, by the device, a third location context identifier associated with at least the second transition area, wherein the third location context identifier is associated with a third map; and

obtaining the third map.

65. The method of claim 1, wherein identifying, by the device, the one or more transition areas comprises identifying, by the device, the one or more transition areas up to a specified number of transition areas.

66. The method of claim 1, further comprising sending the second location context identifier to a server.

67. The method of claim 1, further comprising estimating a second position of a mobile station on the second map.

68. The method of claim 1, further comprising receiving, at the device, a destination point.

69. The method of claim 1, further comprising determining a route from the position to a destination point that includes the first transition area, using the first map and the second map.

70. The method of claim 3, further comprising determining a route from the position to a destination point that includes the first transition area and the second transition area, using the first map, the second map and the third map.

16. An article, comprising:

a non-transitory storage medium having stored thereon instructions executable by a processor of a mobile station to;

estimate a first position of the mobile station on a first map, wherein the first map is associated with a first location context identifier;

identify, by a device, one or more transition nearest to the position of the mobile station, on a first map associated with a first location context identifier;

identify, by the device, a second location context identifier associated with at least a first transition area of the one or more transition areas, wherein the second location context identifier is associated with a second map; and

obtaining the second map.

17. The article of claim 16, wherein the first map comprises a map of an outdoor area, and wherein the second map comprises a map of an indoor area, and wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to identify a transition area leading outdoors.

18. The article of claim 16, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to:

identify a second transition area of the one or more transition areas on the second map; and

identifying, by the device, a third location context identifier associated with at least the second transition area, wherein the third location context identifier is associated with a third map; and

obtaining the third map.

19. The article of claim 16, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to:

display a graphical representation of a first area based at least in part on the first map; and

display a first plurality of transition areas from the one or more transition areas.

20. The article of claim 19, wherein the first plurality of transition areas further individually comprise a visual marker.

21. The article of claim 19, wherein the first plurality of transition areas comprises one or more pointers to a respective one or more maps.

22. The article of claim 17, wherein said second map comprises a routing graph of the indoor area.

23. The article of claim 22, wherein the routing graph comprises:

a plurality of vertices individually representing one of a plurality of hallway intersections;

one or more indoor area entrance points; and

a plurality of edges, comprising one or more edges to individually connect two or more of the plurality of hallway intersections and further comprising one or more edges to individually connect one of the plurality of hallway intersections and one of the one or more indoor area entrance points.

24. The article of claim 23, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to:

assign one or more first weight values to a respective one or more of the plurality of edges according to a distance between two or more of the plurality of hallway intersections; and

assign one or more second weight values to another respective one or more of the plurality of edges according to a distance between a first indoor area entrance point of the one or more indoor area entrance points and a hallway intersection of the plurality of hallway intersections.

25. The article of claim 24, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to determine a path from the first transition area to a destination point.

26. The article of claim 25, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to determine the path at least in part by:

determining a first path from the first transition area to the first indoor area entrance point; and

determining a second path from the first indoor area entrance point to the destination point.

27. The article of claim 26, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to determine the first path at least in part by determining a shortest route from the first transition area to the first indoor area entrance point based at least in part on locations of one or more of the plurality of hallway intersections, and further based at least in part on the one or more first weight values of the respective one or more of the plurality of edges connecting the two or more of the plurality of hallway intersections.

28. The article of claim 26, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to determine the second path from the first indoor area entrance point to the destination point at least in part by plotting a line from the first indoor area entrance point to the destination point.

29. The article of claim 26, wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to determine the second path from the first indoor area entrance point to the destination point at least in part by:

generating a grid of the indoor area comprising partitioning the indoor area into a plurality of areas;

identifying one or more areas of the plurality of areas that do not contain obstructions; and

determining a shortest path through the one or more areas identified as not containing obstructions from the first indoor area entrance point to the destination point.

30. The article of claim 26, wherein said first indoor area entrance point comprises a location context identifier identifying the map of the indoor area, and wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to determine the second path from the first indoor area entrance point to the destination point at least in part by determining the second path using the map of the indoor area.

31. A mobile station, comprising:

a memory to store a plurality of maps for navigation operations; and

a processor to

estimate a first position of the mobile station on a first map,

wherein the first map is associated with a first location context identifier;

identify, by a device, one or more transition areas nearest to the position of the mobile station on a first map associated with a first location context identifier;

identify, by the device, a second location context identifier associated with at least a first transition area of the one or more transition areas, wherein the second location context identifier is associated with a second map; and

obtaining the second map.

32. The mobile station of claim 31, wherein the first map comprises a map of an outdoor area, and wherein the second map comprises a map of an indoor area, the further the processor to identify a transition area leading outdoors.

33. The mobile station of claim 31, the processor further to:

identify a second transition area of the one or more transition areas on the second map;

identify, by the device, a third location context identifier associated with at least the second transition area, wherein the third location context identifier is associated with a third map; and

obtain the third map.

34. The mobile station of claim 31, further comprising a display screen to display:

a graphical representation of a first area based at least in part on the first map; and

a first plurality of transition areas from the one or more transition areas.

35. The mobile station of claim 34, wherein the first plurality of transition areas further individually comprise a visual marker.

36. The mobile station of claim 34, wherein the first plurality of transition areas comprises one or more pointers to a respective one or more maps.

37. The mobile station of claim 32, wherein said second map comprises a routing graph of the indoor area.

38. The mobile station of claim 37, wherein the routing graph comprises:

a plurality of vertices individually representing one of a plurality of hallway intersections;

one or more indoor area entrance points; and

a plurality of edges, comprising one or more edges to individually connect two or more of the plurality of hallway intersections and further comprising one or more edges to individually connect one of the plurality of hallway intersections and one of the one or more indoor area entrance points.

39. The mobile station of claim 38, the processor further to:

assign one or more first weight values to a respective one or more of the plurality of edges according to a distance between two or more of the plurality of hallway intersections; and

assign one or more second weight values to another respective one or more of the plurality of edges according to a distance between a first indoor area entrance point of the one or more indoor area entrance points and a hallway intersection of the plurality of hallway intersections.

40. The mobile station of claim 39, the processor further to determine a path from the first transition area to a destination point.

41. The mobile station of claim 40, the processor further to determine the path at least in part by:

determining a first path from the first transition area to the first indoor area entrance point; and

determining a second path from the first indoor area entrance point to the destination point.

42. The mobile station of claim 41, the processor further to determine the first path by determining a shortest route from the first transition area to the first indoor area entrance point based at least in part on locations of one or more of the plurality of hallway intersections, and further based at least in part on the one or more first weight values of the respective one or more of the plurality of edges connecting the two or more of the plurality of hallway intersections.

43. The mobile station of claim 41, the processor further to determine the second path from the first indoor area entrance point to the destination point at least in part by plotting a line from the first indoor area entrance point to the destination point.

44. The mobile station of claim 41, the processor further to determine the second path from the first indoor area entrance point to the destination point at least in part by:

generating a grid of the indoor area comprising partitioning the indoor area into a plurality of areas;

identifying one or more areas of the plurality of areas that do not contain obstructions; and

determining a shortest path through the one or more areas identified as not containing obstructions from the first indoor area entrance point to the destination point.

45. The mobile station of claim 41, wherein said first indoor area entrance point comprises a location context identifier identifying the map of the indoor area, the processor further to determine the second path from the first indoor area entrance point to the destination point at least in part by determining the second path using the map of the indoor area.

46. An apparatus, comprising:

means for estimating a first position of a mobile station on a first map, wherein the first map is associated with a first location context identifier;

means for identifying one or more transition areas nearest to the position of the mobile station, on the first map associated with a first location context identifier;

means for identifying, by the device, a second location context identifier associated with at least a first transition area of the one or more transition areas, wherein the second location context identifier is associated with a second map; and

means for obtaining the second map.

47. The apparatus of claim 46, wherein the first map comprises a map of an outdoor area, and wherein the second map comprises a map of an indoor area, and further comprising means for identifying a transition area leading outdoors.

48. The apparatus of claim 46, further comprising:

means for identifying a second transition area of the one or more transition areas on the second map; and

means for identifying, by the device, a third location context identifier associated with at least the second transition area, wherein the third location context identifier is associated with a third map; and

means for obtaining the third map.

49. The apparatus of claim 46, further comprising means for displaying:

a graphical representation of a first area based at least in part on the first map; and

a first plurality of transition areas from the one or more transition areas.

50. The apparatus of claim 49, wherein the first plurality of transition areas further individually comprise a visual marker.

51. The apparatus of claim 49, wherein the first plurality of transition areas comprises one or more pointers to a respective one or more maps.

52. The apparatus of claim 47, wherein said second map comprises a routing graph of the indoor area.

53. The apparatus of claim 52, wherein the routing graph comprises:

a plurality of vertices individually representing one of a plurality of hallway intersections;

one or more indoor area entrance points; and

a plurality of edges, comprising one or more edges to individually connect two or more of the plurality of hallway intersections and further comprising one or more edges to individually connect one of the plurality of hallway intersections and one of the one or more indoor area entrance points.

54. The apparatus of claim 53, further comprising:

means for assigning one or more first weight values to a respective one or more of the plurality of edges according to a distance between two or more of the plurality of hallway intersections; and

means for assigning one or more second weight values to another respective one or more of the plurality of edges according to a distance between a first indoor area entrance point of the one or more indoor area entrance points and a hallway intersection.

55. The apparatus of claim 54, further comprising means for determining a path from the first transition area to a destination point.

56. The apparatus of claim 55, wherein said means for determining the path comprises:

means for determining a first path from the first transition area to the first indoor area entrance point; and

means for determining a second path from the first indoor area entrance point to the destination point.

57. The apparatus of claim 56, wherein said means for determining the first path comprises means for determining a shortest route from the first transition area to the first indoor area entrance point based at least in part on locations of one or more of the plurality of hallway intersections, and further based at least in part on the one or more first weight values of the respective one or more of the plurality of edges connecting the two or more of the plurality of hallway intersections.

58. The apparatus of claim 56, wherein said means for determining the second path from the first indoor area entrance point to the destination point comprises means for plotting a line from the first indoor area entrance point to the destination point.

59. The apparatus of claim 56, wherein said means for determining the second path from the first indoor area entrance point to the destination point comprises:

means for generating a grid of the indoor area comprising partitioning the indoor area into a plurality of areas;

means for identifying one or more areas of the plurality of areas that do not contain obstructions; and

means for determining a shortest path through the one or more areas identified as not containing obstructions from the first indoor area entrance point to the destination point.

60. The apparatus of claim 56, wherein said first indoor area entrance point comprises a location context identifier identifying the map of the indoor area, and wherein said means for determining the second path from the first indoor area entrance point to the destination point comprises means for determining the second path using the map of the indoor area.