Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-09-06
2002-11-12
Nguyen, Tan (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S201000, C701S210000, C340S990000, C340S995190
Reexamination Certificate
active
06480785
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to systems for providing directions to travelers and more specifically to systems for determining a route and presenting navigational instructions therefor.
BACKGROUND OF THE INVENTION
Recent years have seen a rapid proliferation of devices that provide mobile access to electronic information, such as handheld computers, pagers and data-enabled cellular telephones. One compelling property of such handheld devices is their capacity to organize information dynamically according to the relative physical locations of the user, points of interest to the user, and available navigable pathways of various kinds. However, these devices do not determine a route between specified physical locations and do not present navigational instructions for traversing the route.
Related patents include the following. U.S. Pat. No. 6,047,236 “GEOGRAPHIC LOCATION REFERENCING SYSTEM AND METHOD” discloses an addressing scheme that allows physical locations to be globally uniquely addressed and specified, including via automatic position acquisition using a global positioning system. However, it does not include the generation and presentation of navigational directions.
U.S. Pat. No. 6,038,509 “SYSTEM FOR RECALCULATING A PATH” discloses the use of caching to accelerate recalculation of directions when deviation from an originally prescribed path occurs. U.S. Pat. No. 6,016,485 “SYSTEM FOR PATHFINDING” discloses the use of pre-computed sub-paths to accelerate the computation of minimal-cost routes in a network.
U.S. Pat. No. 6,026,384 “COST ZONES” discloses a technique for determining and displaying which destinations on a digital map have distances from a given location that are within a fixed cost according to a chosen cost function. However, it does not disclose the generation or presentation of navigational directions, either to destinations within the cost zone or otherwise.
U.S. Pat. No. 6,009,403 “TRAVEL PLAN PREPARING DEVICE” discloses a system for describing a kind of service and receiving information about areas near a travel route in which such service locations exist. A particular area can be specified, and the kinds of services available in that area are subsequently described. However, it does not disclose the generation or presentation of navigational directions that satisfy particular criteria.
U.S. Pat. No. 5,978,730 “CACHING FOR PATHFINDING COMPUTATION” discloses the background execution of a path-finding algorithm without instigation by a user, such that a pre-loaded cache of data and routes relevant to a routing request are available whenever the request is made. It further discloses a particular method, using Dijkstra's algorithm, for determining directions in a graph representing a map. The graph representation disclosed includes vertices that correspond to individual traversable segments conjoining pathway intersections, such that the vertices of the graph representation do not correspond to entire contiguous traversable pathways that potentially span multiple intersections, and such that every such intersection is not represented as an edge incident to the pathway's vertex.
U.S. Pat. No. 5,944,769 “INTERACTIVE NETWORK DIRECTORY SERVICE WITH INTEGRATED MAPS AND DIRECTIONS” discloses a networkbased system to communicate directory information with corresponding locale data, and discloses direction-finding functionality.
U.S. Pat. No. 4,954,958 “DIRECTIONAL INFORMATION SYSTEM” discloses related functionality.
Related commercial products include services from Kivera, a company that licenses location-based services to network access providers for mobile devices. One service is direction-finding.
SUMMARY OF THE INVENTION
The invention provides a system for determining a route and presenting navigational instructions therefor. The invention in one aspect enables a user to obtain instructions for travelling from any one selected location on a particular geophysical grid to any other location via real-world means of transit. Although the invention does not restrict utilization to a particular medium of computation, an embodiment includes a computation module as part of a client application resident on a handheld device having at least one locally cached database of geospatial information. The user may specify a source location (e.g., his or her current location) to the device. Additionally or alternately, the source location may be acquired automatically via global positioning technology. The computation module may alternatively be part of a remote server that receives a request from a handheld device that is wirelessly networked to the server.
Once the computation module receives the source location information and destination location information, the computation module dynamically determines a route between the source location and the destination location. The determination of the route preferably balances descriptive simplicity of the route with a minimal total distance traversed along the route. Prior art systems optimize for distance, time or simplicity individually but not in combination.
Once the route has been determined, a presentation module of the computation module provides a natural language description of the actions the user must take to follow the route. The available pathways may include one- and two-way streets, subway systems, bus routes, overland railways and/or any other form of transit. The instructions may be tailored to users who are on foot or in vehicles, and they may be enhanced with information directed to known characteristics of the user. For example, the presentation module may instruct the user to pass by or turn at specific apparent landmarks that are likely to be of interest to him or her.
In an embodiment, the system 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. As used herein, a “node” is defined as any uniquely specified location where traversable pathways coincide, a “business” is defined as any physical location represented in the system that a user might want to obtain information about, and a “street” is defined as any contiguously traversable pathway via which a person can move among a set of nodes on which the pathway is incident. The business records, street records, and node records are preferably maintained in a business database, a street database, and a node database, respectively.
The system preferably further includes a computation module that can access the map records and execute an algorithm for determining a route between a source location and a destination location using at least one of the map records. The computation module can receive source location information and use it to identify the source location, and can receive destination location information and use it to identify the destination location. The computation module determines a set of source streets associated with the source location and a set of destination streets associated with the destination location. The route between the source location and the destination location, as determined by the computation module, includes a desired solution path between a source street in the set of source streets and a destination street in the set of destination streets, as determined by the algorithm. The algorithm can be biased to discover, when multiple simplest paths exist, that simplest path which traverses the minimum physical distance. Therefore, when at least two of a plurality of possible routes between the source location and the destination location are the simplest routes (i.e., both require an identical minimum number of street changes), the algorithm preferably is biased toward determining the physically shortest route (i.e., the route traversing the minimum physical distance) of the at least two possible routes.
The system preferably further includes a presentation module adapted to generate and present navigational instructions for
Joerg David S.
McAuliffe Jon D.
Morrison & Foerster / LLP
Vindigo, Inc.
LandOfFree
System for determining a route and presenting navigational... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for determining a route and presenting navigational..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for determining a route and presenting navigational... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2994608