System for determining a route and presenting navigational instructions therefor

Abstract

A system for determining a route and presenting navigational instructions therefor preferably includes a plurality of map records including a plurality of business records each identifying a business, a plurality of street records each identifying a street, and a plurality of node records each identifying a node. The system preferably further includes a computation module adapted to execute an algorithm for determining a route between a source location and a destination location using at least one of the map records. The algorithm is preferably adapted to manipulate a graph representation having vertices and edges, wherein each of the vertices corresponds to a respective one of the streets, each of the streets corresponds to exactly one of the vertices, each node corresponds to at least one of the edges, and each edge corresponds to exactly one node. The algorithm can be biased to discover the simplest path (minimum number of street changes) that traverses the minimum physical distance. The computation module preferably interacts with a user during the determination of the route to present a status of the determination to the user and/or to respond to a request of the user, such as a request to terminate the determination. The system preferably further includes a presentation module that generates and presents natural language navigational instructions for traversing the route.

What is claimed is:  
     
         1 . A system for determining a route, comprising a computation module adapted to: 
 a) receive source location information and use said source location information to identify a source location;    b) receive destination location information and use said destination location information to identify a destination location; and    c) execute an algorithm for determining a route between said source location and said destination location; wherein: 
 i) said algorithm manipulates a graph representation having vertices;  
 ii) each of said vertices corresponds to a respective street; and  
 iii) each of said streets corresponds to exactly one of said vertices.  
   
     
     
         2 . The system of  claim 1 , wherein: 
 a) said computation module is adapted to: 
 i) determine a set of source streets using said source location information, and  
 ii) determine a set of destination streets using said destination location information; and  
   b) said source location is associated with a source street included in said set of source streets and said destination location is associated with a destination street included in said set of destination streets.    
     
     
         3 . A system for determining a route, comprising: 
 a) a plurality of map records identifying a plurality of mapped objects; and    b) a computation module adapted to: 
 i) receive source location information;  
 ii) use at least one of said map records to determine a set of source streets using said source location information, said set of source streets being associated with a source location associated with a first mapped object;  
 iii) receive destination location information;  
 iv) use at least one of said map records to determine a set of destination streets using said destination location information, said set of destination streets being associated with a destination location associated with a second mapped object; and  
 v) determine a route between said source location and said destination location using at least one of said map records.  
   
     
     
         4 . A system for determining a route, comprising a computation module adapted to: 
 a) receive source location information and use said source location information to identify a source location and a source street associated with said source location;    b) receive destination location information and use said destination location information to identify a destination location and a destination street associated with said destination location; and    c) execute an algorithm for determining a route between said source location and said destination location, said route comprising a desired solution path; wherein: 
 i) when at least two of a plurality of possible routes between said source location and said destination location require an identical minimum number of street changes, said algorithm is biased toward determining said route as a shortest route of said at least two of said routes.  
   
     
     
         5 . The system of  claim 4 , wherein: 
 a) said algorithm manipulates a graph representation having a plurality of vertices and a plurality of edges;    b) each of said edges represents an adjacency between two of said vertices;    c) said algorithm initially: 
 i) designates a source vertex from said vertices, said source vertex representing a beginning street, said beginning street being one of said source street and said destination street,  
 ii) designates a destination vertex from said vertices, said destination vertex representing an ending street, said ending street being the other of said source street and said destination street,  
 iii) designates said source vertex as seen,  
 iv) designates each remaining vertex as unseen, and  
 v) places said source vertex in a head position of a first-in-first-out queue;  
   d) said algorithm thereafter executes a loop while said destination vertex is designated as unseen and said queue is not empty, in which said algorithm: 
 i) when all vertices adjacent to said head-positioned vertex are seen: 
 (1) removes said head-positioned vertex from said queue, and  
 (2) when a next vertex is next in said queue, places said next vertex in said head position;  
 
 ii) when at least one vertex adjacent to said head-positioned vertex is designated as unseen: 
 (1) considers in a consideration order each unseen vertex adjacent to said head-positioned vertex, and  
 (2) after all of said unseen vertices adjacent to said head-positioned vertex have been considered: 
 (a) removes said head-positioned vertex from said queue, and  
 (b) when a next vertex is next in said queue, places said next vertex in said head position;  
 
 
   e) each of said vertices cannot be simultaneously designated as both seen and unseen; and    f) said consideration order biases said algorithm toward determining said shortest route.    
     
     
         6 . The system of  claim 5 , wherein said consideration of each unseen vertex adjacent to said head-positioned vertex comprises in the alternate and thereafter terminates: 
 a) when said vertex under consideration is said destination vertex: 
 i) designating said head-positioned vertex as a predecessor of said destination vertex,  
 ii) determining a ratio of a distance along a candidate route between said source location and said destination location, said candidate route comprising a current candidate solution path between said beginning street and said ending street, to a distance along a straight line route between said source location and said destination location, and  
 iii) when said ratio is lower than a desired ratio: 
 (1) designating said current candidate solution path as said desired solution path, and  
 (2) designating said destination vertex as seen; and  
 
   b) when said vertex under consideration is not said destination vertex: 
 i) designating said vertex under consideration as seen after said vertex under consideration has been considered,  
 ii) designating said head-positioned vertex as a predecessor of said vertex under consideration, and  
 iii) placing said vertex under consideration in a tail position of said queue after said head-positioned vertex has been designated as said predecessor.  
   
     
     
         7 . The system of  claim 6 , wherein said desired ratio is approximately {square root}2:1.  
     
     
         8 . The system of  claim 5 , wherein said consideration of each unseen vertex adjacent to said head-positioned vertex comprises in the alternate and terminates otherwise: 
 a) when said vertex under consideration is said destination vertex and a previous candidate solution path between said beginning street and said ending street has not been designated: 
 i) designating said head-positioned vertex as a predecessor of said destination vertex,  
 ii) designating a current candidate solution path between said beginning street and said ending street as said previous candidate solution path, and  
 iii) terminating consideration of said vertex under consideration;  
   b) when said vertex under consideration is said destination vertex and said previous candidate solution path has been designated, comparing a distance along another current candidate solution path between said beginning street and said ending street with a distance along said previous candidate solution path, and terminating consideration of said vertex under consideration when not: 
 i) when said distance along said other current candidate solution path is shorter than said distance along said previous candidate solution path, comparing a number of vertices in said other current candidate solution path with a number of vertices in said previous candidate solution path, and performing in the alternate and otherwise terminating consideration of said vertex under consideration: 
 (1) when said number of vertices in said other current candidate solution path equals said number of vertices in said previous candidate solution path: 
 (a) designating said head-positioned vertex as a predecessor of said destination vertex,  
 (b) designating said other current candidate solution path as said previous candidate solution path, and  
 (c) terminating consideration of said vertex under consideration;  
 
 
 (2) when said number of vertices in said other current candidate solution path is a minimum number of vertices greater than said number of vertices in said previous candidate solution path, determining a ratio of said distance along said other current candidate solution path to said distance along said previous candidate solution path, and terminating consideration of said vertex under consideration when not: 
 (a) when said ratio is lower than a desired ratio: 
 (i) designating said head-positioned vertex as a predecessor of said destination vertex,  
 (ii) designating said other current candidate solution path as said previous candidate solution path, and  
 (iii)terminating consideration of said vertex under consideration; and  
 
 
 (3) when said number of vertices in said other current candidate solution path is a maximum number of vertices greater than said number of vertices in said previous candidate solution path, designating said previous candidate solution path as said desired solution path, designating said destination vertex as seen and terminating consideration of said vertex under consideration; and  
   c) when said vertex under consideration is not said destination vertex: 
 i) designating said vertex under consideration as seen after said vertex under consideration has been considered,  
 ii) designating said head-positioned vertex as a predecessor of said vertex under consideration,  
 iii) placing said vertex under consideration in a tail position of said queue after said head-positioned vertex has been designated as said predecessor, and  
 iv) terminating consideration of said vertex under consideration.  
   
     
     
         9 . The system of  claim 8 , wherein said minimum number is 1, said maximum number is 2 and said desired ratio is 0.7:1.  
     
     
         10 . The system of  claim 5 , wherein said consideration of each unseen vertex adjacent to said head-positioned vertex comprises: 
 a) designating said vertex under consideration as seen,    b) designating said head-positioned vertex as a predecessor of said vertex under consideration,    c) placing said vertex under consideration in a tail position of said queue after said head-positioned vertex has been designated as said predecessor, and    d) terminating consideration of said vertex under consideration.    
     
     
         11 . The system of  claim 10 , wherein said consideration order is established by: 
 a) each unseen vertex adjacent to said head-positioned vertex having associated therewith a position in a connection order relative to said head-positioned vertex;    b) pairing a first unconsidered vertex of said unseen vertices adjacent to said head-positioned vertex and, when available, a second unconsidered vertex of said unseen vertices adjacent to said head-positioned vertex, 
 i) said first unconsidered vertex being an unconsidered vertex next in one of increasing connection order position and decreasing connection order position from an entrance connection order position,  
 ii) said second unconsidered vertex being an unconsidered vertex next in the other of increasing connection order position and decreasing connection order position from the entrance connection order position, and  
 iii) said entrance connection order position being: 
 (1) when said head-positioned vertex is said source vertex, a connection order position corresponding to a connection order position, relative to said head-positioned vertex, of a vertex adjacent to said head-positioned vertex; and  
 (2) when said head-positioned vertex is not said source vertex, a connection order position, relative to said head-positioned vertex, of said predecessor vertex of said head-positioned vertex;  
 
   c) ordering according to a preference order said first unconsidered vertex and, when available, said second unconsidered vertex; and    d) enqueing for consideration, according to said preference order, at least one of said first unconsidered vertex and said second unconsidered vertex.    
     
     
         12 . The system of  claim 11 , wherein enqueing comprises enqueing for consideration, according to said preference order, both said first unconsidered vertex and said second unconsidered vertex.  
     
     
         13 . The system of  claim 11 , wherein said preference order is: 
 a) established by: 
 i) said head-positioned vertex having associated therewith an entrance intersection, said entrance intersection being intersected by a street represented by said head-positioned vertex;  
 ii) each of said first unconsidered vertex and, when available, said second unconsidered vertex having associated therewith: 
 (1) a respective vertex intersection, each of said respective vertex intersections being an intersection of: 
 (a) a street represented by said respective unconsidered next vertex, and  
 (b) said street represented by said head-positioned vertex; and  
 
 (2) a respective straight line distance from said respective vertex intersection to said entrance intersection; and  
 
   b) according to the shorter of said straight line distances.    
     
     
         14 . The system of  claim 11 , wherein said preference order is: 
 a) established by each of said first unconsidered vertex and, when available, said second unconsidered vertex having associated therewith: 
 i) a respective vertex intersection, each of said respective vertex intersections being an intersection of: 
 (1) a street represented by said respective unconsidered next vertex, and  
 (2) a street represented by said head-positioned vertex; and  
 
 ii) a respective straight line distance from said respective vertex intersection to one of: 
 (1) said source location, when said ending street is said source street, and  
 (2) said destination location, when said ending street is said destination street; and  
 
   b) according to the shorter of said straight line distances.    
     
     
         15 . The system of  claim 11 , wherein said connection order positions are established by: 
 a) a street represented by said head-positioned vertex having associated therewith a first end and a second end;    b) each vertex adjacent to said head-positioned vertex having associated therewith: 
 i) a respective vertex intersection, each of said respective vertex intersections being an intersection of: 
 (1) a street represented by said respective vertex adjacent to said head-positioned vertex and  
 (2) said street represented by said head-positioned vertex; and  
 
 ii) a respective distance from said respective vertex intersection to one of said first end and said second end along said street represented by said head-positioned vertex; and  
   c) ordering said vertices adjacent to said head-positioned vertex according to increasing said respective distances.    
     
     
         16 . The system of  claim 15 , wherein ordering according to increasing said respective distances comprises assigning a numerical value to each of said connection order positions to indicate a connection order position of each of said vertices adjacent to said head-positioned vertex relative to one another.  
     
     
         17 . A system for determining a route, comprising a computation module adapted to: 
 a) receive source location information and use said source location information to identify a source location;    b) receive destination location information and use said destination location information to identify a destination location;    c) determine a source-to-destination vector having a source end at said source location and a destination end at said destination location;    d) determine a source corridor vector perpendicular to said source-to-destination vector and determine a destination corridor vector perpendicular to said source-to-destination vector, said source corridor vector and said destination corridor vector defining a corridor area therebetween containing said source location and said destination location; and    e) execute an algorithm for determining a route between said source location and said destination location; wherein 
 i) said algorithm does not explore a possible route when a portion of said possible route falls outside said corridor area.  
   
     
     
         18 . The system of  claim 17 , wherein said source corridor vector passes through said source location and said destination corridor vector passes through said destination location.  
     
     
         19 . A system for determining a route, comprising: 
 a) a plurality of map records identifying a plurality of mapped objects; and    b) a computation module adapted to 
 i) receive source location information and use said source location information to identify a source location associated with a first mapped object;  
 ii) receive destination location information and use said destination location information to identify a destination location associated with a second mapped object;  
 iii) execute an algorithm for determining a route between said source location and said destination location using at least one of said map records; and  
 iv) interact with a user of said computation module while executing said algorithm.  
   
     
     
         20 . The system of  claim 19 , wherein said algorithm executes a sequence of iterations and said computation module provides status information to said user between two of said iterations.  
     
     
         21 . The system of  claim 20 , wherein said two iterations are successive.  
     
     
         22 . The system of  claim 19 , wherein said algorithm executes a sequence of iterations and said computation module checks for a user request between two of said iterations.  
     
     
         23 . The system of  claim 22 , wherein said two iterations are successive.  
     
     
         24 . The system of  claim 22 , wherein said computation module terminates said algorithm in response to said user request.  
     
     
         25 . The system of  claim 22 , wherein said computation module temporarily suspends said algorithm, responds to said user request, and subsequently resumes said algorithm.  
     
     
         26 . A system for determining a route, comprising: 
 a) a plurality of map records identifying a plurality of mapped objects; and    b) a computation module adapted to 
 i) receive source location information and use said source location information to identify a source location associated with a first mapped object;  
 ii) receive destination location information and use said destination location information to identify a destination location associated with a second mapped object; and  
 iii) determine a route between said source location and said destination location using at least one of said map records; and  
   c) a presentation module adapted to generate and present navigational instructions for traversing said route;    d) wherein said instructions comprise at least one of: 
 i) an instruction to read at least one of said mapped objects,  
 ii) an instruction to turn at one of said mapped objects,  
 iii) an instruction to pass by said one of said mapped objects, and  
 iv) a description of said one of said mapped objects;  
   e) said one of said mapped objects being associated with a vendor which has arranged for said presentation of said instructions.    
     
     
         27 . The system of  claim 26 , wherein said one of said mapped objects is at least one of a business, a street, an intersection, a sign, a billboard, an advertisement, a map, a schedule, a landmark, a building, a transit station, and a government facility.  
     
     
         28 . A system for determining a route, comprising: 
 a) a plurality of business records each identifying a business,    b) a plurality of street records each identifying a street,    c) a plurality of node records each identifying a node; and    d) a computation module adapted to 
 i) receive source location information and use said source location information to identify a source location associated with at least one of: 
 (1) a business identified by at least one of said business records,  
 (2) a street identified by at least one of said street records, and  
 (3) a node identified by at least one of said node records;  
 
 ii) receive destination location information and use said destination location information to identify a destination location associated with at least one of: 
 (1) a business identified by at least one of said business records,  
 (2) a street identified by at least one of said street records, and  
 (3) a node identified by at least one of said node records; and  
 
 iii) determine a route between said source location and said destination location using at least one of: 
 (1) at least one of said business records,  
 (2) at least one of said street records, and  
 (3) at least one of said node records.  
 
   
     
     
         29 . The system of  claim 28 , wherein at least one of said source location information and said destination location information comprises a coordinate pair, a latitude, a longitude, a signal from a global positioning system, at least a portion of a street name, at least a portion of a landmark name, at least a portion of a building name, at least a portion of a company name, at least a portion of a street address, at least a portion of a name of a transit station, and at least a portion of a name of a government facility.  
     
     
         30 . The system of  claim 28 , wherein said business records are maintained in at least one business database, said street records are maintained in at least one street database, said node records are maintained in at least one node database, and said computation module is adapted to access said business database, said street database and said node database.  
     
     
         31 . The system of  claim 28 , wherein each of said business records comprises at least one of a business unique identifier, a business street identifier, and a business coordinate pair.  
     
     
         32 . The system of  claim 28 , wherein each of said street records comprises at least one of a street unique identifier, a street name identifier, at least one incident node identifier, and a one-wayness indicator.  
     
     
         33 . The system of  claim 28 , wherein each of said node records comprises at least one of a node unique identifier, at least one intersecting street identifier, a node coordinate pair, and at least one transition constraint governing traversal of said node.  
     
     
         34 . The system of  claim 28 , wherein said route is a simplest route of a plurality of possible routes between said source location and said destination location, said simplest route presenting a minimum number of street changes.  
     
     
         35 . The system of  claim 34 , wherein said computation module executes an algorithm for determining the route, said algorithm comprising a breadth-first search algorithm.  
     
     
         36 . The system of  claim 28 , wherein said route is a minimum cost route of a plurality of possible routes between said source location and said destination location.  
     
     
         37 . The system of  claim 36 , wherein said minimum cost route presents at least one of a minimum amount of tolls, a minimum amount of transportation fees, a minimum amount of expected danger, a minimum amount of expected traffic congestion, and a minimum travel time.  
     
     
         38 . The system of  claim 37 , wherein said computation module executes an algorithm for determining the route, said algorithm comprising one of Dijkstra's algorithm and the Bellman-Ford algorithm.  
     
     
         39 . The system of  claim 28 , wherein: 
 a) said computation module executes an algorithm for determining the route;    b) said algorithm manipulates a graph representation having vertices and edges;    c) each of said vertices corresponds to a respective one of said streets;    d) each of said streets corresponds to exactly one of said vertices;    e) each node corresponds to at least one of said edges; and    f) each edge corresponds to exactly one node.    
     
     
         40 . The system of  claim 28 , wherein: 
 a) said computation module is adapted to: 
 i) use at least one of said business records, said street records and said node records to determine a set of source streets using said source location information, and  
 ii) use at least one of said business records, said street records and said node records to determine a set of destination streets using said destination location information;  
   b) said source location is a source street included in said set of source streets and said destination location is a destination street included in said set of destination streets; and    c) when said source location information identifies one of said nodes, said set of source streets includes all streets identified by said intersecting street identifiers.    
     
     
         41 . The system of  claim 28 , wherein: 
 a) said computation module is further adapted to: 
 i) determine a source-to-destination vector having a source end at said source location and a destination end at said destination location;  
 ii) determine a source corridor vector perpendicular to said source-to-destination vector;  
 iii) determine a destination corridor vector perpendicular to said source-to-destination vector;  
 iv) said source corridor vector and said destination corridor vector defining a corridor area therebetween containing said source location and said destination location;  
   b) none of said node records used by the computation module to determine the route identifies a node outside said corridor area.    
     
     
         42 . The system of  claim 41 , wherein said source corridor vector passes through said source location and said destination corridor vector passes through said destination location.  
     
     
         43 . The system of  claim 28 , further comprising a presentation module adapted to generate and present a map showing at least a portion of said route.  
     
     
         44 . The system of  claim 28 , further comprising a presentation module adapted to generate and present navigational instructions for traversing said route.  
     
     
         45 . The system of  claim 44 , wherein 
 a) said instructions comprise at least one of: 
 i) instructions to move in a direction;  
 ii) instructions to turn in a direction;  
 iii) instructions to move a distance;  
 iv) instructions to move for a period of time;  
 v) instructions to pay a toll;  
 vi) instructions to use at least one component of a mass transit system;  
 vii) instructions to read a navigational reference,  
 viii) instructions to turn at said navigational reference,  
 ix) instructions to pass by said navigational reference, and  
 x) a description of at least one of said source location, said destination location and said navigational reference; and  
   b) said navigational reference is at least one of: 
 i) at least one of said businesses,  
 ii) at least one of said streets,  
 iii) at least one of said nodes,  
 iv) a sign,  
 v) a billboard,  
 vi) an advertisement,  
 vii) a map,  
 viii) a schedule,  
 ix) a landmark,  
 x) a building,  
 xi) a transit station, and  
 xii) a government facility.  
   
     
     
         46 . The system of  claim 44 , wherein said presentation module is adapted to: 
 a) present said instructions to a user of said computation module; and    b) generate and present said instructions using at least one of: 
 i) demographic information pertaining to said user,  
 ii) a preference of said user,  
 iii) a characteristic of said user,  
 iv) a characteristic of a handheld device being used by said user,  
 v) information stored in said handheld device, and  
 vi) a characteristic of at least one of: 
 (1) at least one of said businesses,  
 (2) at least one of said streets, and  
 (3) at least one of said nodes.