Scalable Routing For Mobile Station Navigation With Location Context Identifier

• US 20110172906A1
• Filed: 01/10/2011
• Published: 07/14/2011
• Est. Priority Date: 01/14/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Hardie, Edward Thomas Lingham, Das, Saumitra Mohan, Khorashadi, Behrooz
• Granted Patent: US 9,157,745 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• 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, comprising:

estimating a position of a mobile station;

identifying up to a specified amount of points of interest nearest to the estimated position of the mobile, station on a first map; and

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.

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 one or more points of interest leading outdoors from the destination point.

3. The method of claim 1, further comprising:

identifying a second point of interest on the second map;

selecting a third map identified by a second location context identifier associated with the second point of interest for use by the mobile station in a subsequent navigation operation at least in part in response to said identifying the second point of interest; and

continuing to identify points of interest leading to other location context identifiers, to select additional maps identified by the other location context identifiers, and to analyze potential routes until a final routing solution from the estimated position of the mobile station to the destination point.

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 points of interest individually associated with one or more location context identifiers in the first map, the first plurality of points of interest comprising one or more of the identified points of interest.

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

6. The method of claim 4, wherein the one or more location context identifiers associated with the first plurality of points of interest individually comprise 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 point of interest to the destination point.

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

determining a first path from the first point of interest 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 said determining the first path comprises determining a shortest route from the first point of interest 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 1 wherein said 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 said 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 said 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.

16. An article, comprising:

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

estimate a position of the mobile station;

identify up to a specified amount of points of interest nearest to the estimated position of the mobile station on a first map;

select a second map identified by a first location context identifier associated with a first point of interest of the identified points of interest; and

determine a route from the estimated position of the mobile station to a destination point using the first map and 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 storage medium has stored thereon further instructions executable by the processor to identify one or more points of interest leading outdoors from the destination point.

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

identify a second point of interest on the second map;

select a third map identified by a second location context identifier associated with the second point of interest for use by the mobile station in a subsequent navigation operation at least in part in response to said identification of the second point of interest; and

continue to identify points of interest leading to other location context identifiers, to select additional maps identified by the other location context identifiers, and to analyze potential routes until a final routing solution is determined from the estimated position of the mobile station to the destination point.

19. The article of claim 16, wherein the 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 points of interest individually associated with one or more location context identifiers in the first map, the first plurality of points of interest comprising one or more of the identified points of interest.

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

21. The article of claim 19, wherein the one or more location context identifiers associated with the first plurality of points of interest individually comprise 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 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 storage medium has stored thereon further instructions executable by the processor to determine a path from the first point of interest to the destination point.

26. The article of claim 25, wherein the 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 point of interest 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 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 point of interest 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 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 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 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

identify up to a specified amount of points of interest nearest to an estimated position of a mobile station corresponds to a point of interest on a first map of the plurality of maps,

select a second map of the plurality of maps identified by a first location context identifier associated with a first point of interest of the identified points of interest, and

determine a route from the estimated position of the mobile station to a destination point using the first map and 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 to identify one or more points of interest leading outdoors from the destination point.

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

identify a second point of interest on the second map;

select a third map identified by a second location context identifier associated with the second point of interest for use by the mobile station in a subsequent navigation operation at least in part in response to said identifying the second point of interest; and

continue to identify points of interest leading to other location context identifiers, to select additional maps identified by the other location context identifiers, and to analyze potential routes until a final routing solution from the estimated position of the mobile station to the destination point.

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 points of interest individually associated with one or more location context identifiers in the first map, the first plurality of points of interest comprising one or more of the identified points of interest.

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

36. The mobile station of claim 34, wherein the one or more location context identifiers associated with the first plurality of points of interest individually comprise 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 point of interest to the destination point.

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

determining a first path from the first point of interest 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 to determine the first path by determining a shortest route from the first point of interest 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 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 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 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 position of a mobile station;

means for identifying up to a specified amount of points of interest nearest to the estimated position of the mobile station on a first map;

means for 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

means for determining a route from the estimated position of the mobile station to a destination point using the first map and 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 one or more points of interest leading outdoors from the destination point.

48. The apparatus of claim 46, further comprising:

means for identifying a second point of interest on the second map;

means for selecting a third map identified by a second location context identifier associated with the second point of interest for use by the mobile station in a subsequent navigation operation at least in part in response to said identification of the second point of interest; and

means for continuing to identify points of interest leading to other location context identifiers, to select additional maps identified by the other location context identifiers, and to analyze potential routes until a final routing solution from the estimated position of the mobile station to the destination point.

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 points of interest individually associated with one or more location context identifiers in the first map, the first plurality of points of interest comprising one or more of the identified points of interest.

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

51. The apparatus of claim 49, wherein the one or more location context identifiers associated with the first plurality of points of interest individually comprise 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 point of interest to the 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 point of interest 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 point of interest 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.