Methods and apparatuses for navigation in urban environments

• US 7,957,871 B1
• Filed: 09/29/2005
• Issued: 06/07/2011
• Est. Priority Date: 09/29/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Hopstop.com, Inc. (Apple Inc.)
• Inventors: Echeruo, Chinedu
• Primary Examiner(s): To; Tuan C
• Application Number:
  US11/238,224
• Time in Patent Office: 2,077 Days
• Field of Search: 701/54, 701/201, 709/223, 104/27, 104/28, 104/88.01, 105/215.2, 340/995.13, 340/995.27
• US Class Current: 701/54
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

Embodiments disclose methods, systems, and apparatuses for providing maps and directions, including walking and mass transit directions in urban environments where users do not drive cars. Additionally, driving directions can be included. Various criteria, including preferences for amount of walking, for or against particular streets, certain mass transit vehicle types, number of transfers between mass transit vehicles, and other preferences, are considered in the routing calculations, as well as non-individual information such as current conditions and other information. User feedback on various qualitative aspects of the directions is received and stored, and used in subsequent routing decisions. Embodiments disclosed include web services whereby third parties, such as members of the travel industry, can access such services which provide textual and graphical information. Further, clients can access and edit mass transit information through the web services.

Claims

1. An apparatus for displaying an integrated multi-modal transportation route, comprising:

one or more user interface controls for inputting a start point and an end point of a journey, and zero or more intermediate points;

one or more user interface controls whereby user criteria are set;

means for displaying one or more walking directions, comprising;

textual descriptions of the walking directions; and

graphical depictions of the walking directions;

means for displaying one or more mass transit directions, comprising;

textual descriptions of the mass transit directions; and

graphical depictions of the mass transit directions;

wherein the walking directions and the mass transit directions, taken together, comprise a complete set of directions from the start point to the end point, passing through the intermediate points; and

means for receiving user feedback on the quality of the directions.

2. The apparatus of claim 1, wherein the textual descriptions of the mass transit directions comprise:

one or more mass transit boarding directions; and

one or more mass transit exiting directions.

3. The apparatus of claim 1, wherein the textual descriptions of the walking directions comprise:

one or more street names; and

zero or more turns.

4. The apparatus of claim 1, wherein the user criteria comprise:

walking criteria, comprising;

preference for amount of walking; and

mass transit criteria, comprising;

preference for maximum number of transfers.

5. The apparatus of claim 1, wherein the graphical depictions of the walking directions comprise:

graphical display of one or more streets contained in the walking directions;

graphical display of one or more streets in the neighborhood of the streets contained in the walking directions.

6. The apparatus of claim 1, wherein the means for receiving user feedback on the quality of the directions additionally comprise:

means for allowing a user to provide feedback on the quality of at least one of textual description of the walking directions and the graphical description of the walking directions.

7. The apparatus of claim 1, wherein the means for receiving user feedback on the quality of the directions additionally comprise:

means for allowing a user to provide feedback on the quality of the textual description of the mass transit directions and the graphical description of the mass transit directions.

8. The apparatus of claim 1, additionally comprising

means for displaying driving directions, wherein the driving directions comprise:

one or more street names; and

zero or more turns;

wherein the driving directions are calculated according to a database of one or more impossible turns, wherein the impossible turns are excluded from the driving directions;

wherein the walking directions and the mass transit directions and the driving directions, taken together, comprise a complete set of directions from the start point to the end point, passing through the intermediate points.

9. The apparatus of claim 6 further comprising:

means for creating and maintaining a database about the user'"'"'s own preferences, for creating routes for that user;

means for updating the database used for all users; and

means for incorporating user-provided feedback on various aspects of a route into subsequent routing decisions.

10. The apparatus of claim 7 further comprising:

means for creating and maintaining a database about the user'"'"'s own preferences, for creating routes for that user;

means for updating the database used for all users; and

means for incorporating user-provided feedback on various aspects of a route into subsequent routing decisions.

11. The apparatus of claim 1 further comprising means for optimizing the directions according to the user input.

12. The apparatus of claim 1 further comprising means for optimizing the directions according to at least one of a single or plurality of records in a database representing user-provided feedback.

13. The apparatus of claim 1 comprising:

means for computing directions between a set of points, which means further comprise;

means for accepting user input for a trip in the form of two or more points, comprising a start point, an end point, and zero or more intermediate points;

means for computing one or more directions between the start point and the end point, the directions comprising;

one or more mass transit directions;

one or more walking directions; and

means for optimizing the directions according to one or more criteria.

14. The apparatus of claim 13 further comprising means for seeking optimal transit routes over a network of nodes in response to user input.

15. The apparatus of claim 14 further comprising means for connecting nodes closest to each other, from the start node to the end node, in finding an optimal transit route.

16. The apparatus of claim 13 further comprising means for storing and transforming transit data in a transit route search.

17. The apparatus of claim 13 further comprising means for implementing one or more of transit-route search utilities for an end user.

18. An apparatus for displaying an integrated multi-modal transportation route, comprising:

one or more user interface controls for inputting a start point and an end point of a journey, and zero or more intermediate points;

one or more user interface controls whereby user criteria are set;

means for displaying one or more walking directions, comprising;

textual descriptions of the walking directions; and

graphical depictions of the walking directions;

means for displaying one or more mass transit directions, comprising;

textual descriptions of the mass transit directions; and

graphical depictions of the mass transit directions;

wherein the walking directions and the mass transit directions, taken together, comprise a complete set of directions from the start point to the end point, passing through the intermediate points;

wherein the apparatus comprises at least one of an internet enabled computer, a personal digital assistant, a cell phone, a landline phone, and a laptop computer; and

means for receiving user feedback on the quality of the directions.

19. In an apparatus for displaying an integrated multi-modal transportation route, a method for calculating and displaying an integrated multi-modal transportation route, comprising:

inputting a start point and an end point of a journey, and inputting zero or more intermediate points;

inputting user criteria;

displaying one or more walking directions, comprising;

displaying textual descriptions of the walking directions; and

displaying graphical depictions of the walking directions;

displaying one or more mass transit directions, comprising;

displaying textual descriptions of the mass transit directions; and

displaying graphical depictions of the mass transit directions;

wherein the walking directions and the mass transit directions, taken together, comprise a complete set of directions from the start point to the end point, passing through the intermediate points.

20. The method of claim 19, additionally comprising the steps of:

receiving user feedback on one or more directions, the user feedback comprising;

one or more numerical ratings of quality of the directions;

adding the user feedback to a database;

wherein the directions are additionally optimized according to the user feedback.

21. The method of claim 19, wherein the directions additionally comprise:

driving directions, wherein the driving directions comprise;

one or more street names; and

zero or more turns;

wherein the driving directions are calculated according to a database of one or more impossible turns, wherein the impossible turns are excluded from the driving directions.

22. The method of claim 19 further comprising:

providing directions via a web service, comprising performing transactions providing directions for a trip, wherein the transactions further comprise;

a request from a client to a publisher;

user input comprising a date and time of a trip;

a computation, comprising computing one or more directions wherein the directions provide a route between a start point and an end point; and

wherein the directions are optimized according to the user input.

23. The method of claim 19 comprising processing a user request for directions which further comprises:

validating a user request by a web services client;

sending a request to a web service;

looking up a route id from start and destination addresses respectively when the route id has not been supplied by a user;

retrieving route information from the database when a route id has been supplied by a user;

validating start and destination addresses;

looking up validated start and destination addresses in a directed graph, and finding node numbers for the start and destination addresses; and

calculating an optimal route.