Method and apparatus for accounting for user experience in pedestrian navigation routing

• US 8,392,113 B2
• Filed: 07/29/2010
• Issued: 03/05/2013
• Est. Priority Date: 12/11/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Gupta, Rajarshi, Das, Saumitra Mohan, Jeong, Min-Wook
• Primary Examiner(s): Zeender, Ryan
• Assistant Examiner(s): CHEIN, ALLEN C
• Application Number:
  US12/846,672
• Publication Number:
  US 20110144903A1
• Time in Patent Office: 950 Days
• Field of Search: 701/433, 701/426, 701/438, 701/434, 701/400, 701/409, 701/410, 701/526, 701/533, 701/541, 701/425
• US Class Current: 701/426
• 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/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

The subject matter disclosed herein relates to a system and method for determining navigation instructions within a pedestrian navigation environment. For example, a system and method are provided for determining an optimal path to a destination. An optimal path may be determined based at least in part on a measurement of similarity between one or more points of interest and one or more destinations. Such a measurement of similarity may be based at least in part on predefined criteria between the one or more destinations and one or more points of interest.

Claims

1. A method, comprising:

receiving, in a processor, user input comprising identities of one or more destinations;

determining, in the processor, an optimal path from an estimated location of a mobile device to the one or more destinations based at least in part on a measurement of similarity between one or more points of interest along the optimal path and the one or more destinations; and

presenting the optimal path to a user.

2. The method of claim 1, wherein the optimal path comprises a lowest cost path.

3. The method of claim 1, further comprising determining the one or more destinations based at least in part on a user input indicating a category of destinations.

4. The method of claim 1, further comprising determining the measurement of similarity based at least in part on predefined criteria characterizing the one or more destinations and one or more points of interest.

5. The method of claim 4, wherein a destination properties vector is associated with at least one destination of the one or more destinations and one or more points of interest properties vectors are associated with the one or more points of interest.

6. The method of claim 5, wherein the predefined criteria comprises one or more dot products between the destination properties vector and the one or more points of interest properties vectors.

7. The method of claim 5, wherein the destination properties vector and the one or more points of interest properties vectors comprise weights for predefined characteristics.

8. The method of claim 1, wherein the method is adapted to determine the optimal path within a pedestrian navigation environment.

9. The method of claim 1, wherein a cost for a point of interest is projected onto one or more nodes along the optimal path.

10. The method of claim 9, wherein the cost for the point of interest is projected onto at least two nodes along the optimal path based at least in part on physical dimensions of the point of interest.

11. The method of claim 1, wherein the presenting the optimal path comprises presenting one or more navigation instructions.

12. An apparatus, comprising:

a user input device adapted to receive a user input comprising identities of one or more destinations;

a processing unit adapted to determine an optimal path from an estimated location of a mobile device to the one or more destinations based at least in part on a measurement of similarity between one or more points of interest along the optimal path and the one or more destinations; and

an output device to present the optimal path to a user.

13. The apparatus of claim 12, wherein the optimal path comprises a lowest cost path.

14. The apparatus of claim 12, wherein the processing unit is adapted to determine the one or more destinations based at least in part on a user input indicating a category of destinations.

15. The apparatus of claim 12, wherein the processing unit is adapted to determine the measurement of similarity based at least in part on predefined criteria characterizing the one or more destinations and one or more points of interest.

16. The apparatus of claim 15, wherein a destination properties vector is associated with at least one destination of the one or more destinations and one or more points of interest properties vectors are associated with the one or more points of interest.

17. The apparatus of claim 16, wherein the predefined criteria comprises one or more dot products between the destination properties vector and the one or more points of interest properties vectors.

18. The apparatus of claim 16, wherein the destination properties vector and the one or more points of interest properties vectors comprise weights for predefined characteristics.

19. The apparatus of claim 12, wherein the processing unit is adapted to determine the optimal path within a pedestrian navigation environment.

20. The apparatus of claim 12, wherein the processing unit is adapted to project a cost for a point of interest onto one or more nodes along the optimal path.

21. The apparatus of claim 20, wherein the cost for the point of interest is projected onto at least two nodes along the optimal path based at least in part on physical dimensions of the point of interest.

22. The apparatus of claim 12, wherein the output device comprises a display device.

23. The apparatus of claim 12, wherein the output device comprises a speaker.

24. An apparatus, comprising:

means for receiving a user input comprising identities of one or more destinations;

means for determining an optimal path from an estimated location of a mobile device to the one or more destinations based at least in part on a measurement of similarity between one or more points of interest along the optimal path and the one or more destinations; and

means for presenting the optimal path to a user.

25. The apparatus of claim 24, wherein the optimal path comprises a lowest cost path.

26. The apparatus of claim 24, further comprising means for determining the one or more destinations based at least in part on a user input indicating a category of destinations.

27. The apparatus of claim 24, further comprising means for determining the measurement of similarity based at least in part on predefined criteria characterizing the one or more destinations and one or more points of interest.

28. The apparatus of claim 27, wherein a destination properties vector is associated with at least one destination of the one or more destinations and one or more points of interest properties vectors are associated with the one or more points of interest.

29. The apparatus of claim 28, wherein the predefined criteria comprises one or more dot products between the destination properties vector and the one or more points of interest properties vectors.

30. The apparatus of claim 28, wherein the destination properties vector and the one or more points of interest properties vectors comprise weights for predefined characteristics.

31. The apparatus of claim 24, further comprising means for determining the optimal path within a pedestrian navigation environment.

32. The apparatus of claim 24, further comprising means for projecting a cost for a point of interest onto one or more nodes along the optimal path.

33. The apparatus of claim 32, wherein the means for projecting is adapted to project the cost for the point of interest onto at least two nodes along the optimal path based at least in part on physical dimensions of the point of interest.

34. An article, comprising:

a non-transitory computer-readable medium comprising instructions executable by a special purpose apparatus, the instructions comprising;

code to receive a user input comprising identities of one or more destinations;

code to determine an optimal path from an estimated location of a mobile device to the one or more destinations based at least in part on a measurement of similarity based at least in part on a measurement of similarity between one or more points of interest along the optimal path and the one or more destinations; and

code to generate one or more signals to present the optimal path to a user.

35. The article of claim 34, wherein the optimal path comprises a lowest cost path.

36. The article of claim 34, wherein the instructions further comprise code to determine the one or more destinations based at least in part on a user input indicating a category of destinations.

37. The article of claim 34, wherein the instructions further comprise code to determine the measurement of similarity based at least in part on predefined criteria characterizing the one or more destinations and one or more points of interest.

38. The article of claim 37, wherein a destination properties vector is associated with at least one destination of the one or more destinations and one or more points of interest properties vectors are associated with the one or more points of interest.

39. The article of claim 38, wherein the predefined criteria comprises one or more dot products between the destination properties vector and the one or more points of interest properties vectors.

40. The article of claim 38, wherein the destination properties vector and the one or more points of interest properties vectors comprise weights for predefined characteristics.

41. The article of claim 34, wherein the instructions further comprise code to determine the optimal path within a pedestrian navigation environment.

42. The article of claim 34, wherein the instructions further comprise code to project a cost for a point of interest onto one or more nodes along the optimal path.

43. The article of claim 42, wherein the instructions further comprise code to project the cost for the point of interest onto at least two nodes along the optimal path based at least in part on physical dimensions of the point of interest.

44. The article of claim 34, wherein the one or more signals comprise one or more display signals to present the optimal path via a display device.