Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
2000-11-16
2004-11-30
Black, Thomas G. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C701S200000, C073S17800T, C340S995190, C340S995240
Reexamination Certificate
active
06826472
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for generating routing information, including the generation of driving guides for display to a user.
2. Discussion of the Background
Navigational Aids built upon small portable, and powerful computers and specialized electronics have revolutionized the concept of maps and methods of finding routes from an origin to a specific destination. One recent breakthrough fueling this revolution is illustrated in
FIG. 1
, the concept of an automobile based map and direction finding system
100
, as described in Loughmiller, Jr. et al., U.S. Pat. No. 4,914,605, issued Apr. 3, 1990, entitled “Apparatus and Method for Displaying a Map,” incorporated herein by reference, in its entirety. Additional methods and navigation functionality are also described in Honey et al., U.S. Pat. No. 4,796,191, issued Jan. 03, 1989, entitled “VEHICLE NAVIGATION SYSTEM AND METHOD,” also incorporated herein by reference, in its entirety.
Such systems provide a map display
110
that is properly oriented so as to be easily read by a driver and provide navigational aid. Modern systems are end-point oriented and can provide a path to a specific destination. They usually include an option for a map, the ability to select a zoom factor, list turn by turn directions, and other options. Other specialized features of such systems include the ability to change a display of an area surrounding the driver as a location of the driver progresses, display a desired destination entered by the driver, and provide a symbol on the display indicating the current location of the driver.
A typical system involving maps with routes utilize a mathematical structure called a directed graph. A directed graph consists of a set of points called nodes, along with a set of connections called “links.”
FIG. 2A
shows an exemplar directed graph which shows eastbound oneway street
50
and two-way street
52
, both intersecting with two-way street
54
. Street
50
intersects with street
54
at intersection
60
. Street
52
intersects with street
54
at intersection
70
. At intersection
60
are two nodes,
62
and
64
. The circle represents where the node is located and the tail represents where a traveler would come from to reach that node.
In
FIG. 2A
, The node symbol is displaced from the actual intersection for purposes of visibility. Links represent a path between nodes. For example, from node
64
a traveler can make a right turn at intersection
60
to enter road
54
or can proceed straight on road
50
. Link
86
represents travel starting from intersection
60
on road
50
facing east, making a right turn at intersection
60
and proceeding south on road
54
. Thus, link
86
connects node
64
to node
72
.
FIG. 2A
only shows links drawn for nodes
62
and
64
. If links are drawn for all nodes, the directed graph would become too crowded and would be difficult to read. Thus, the directed graph is simplified and redrawn as in FIG.
2
B.
The directed graph of
FIG. 2B
is used to symbolically represent the data structure stored for a map. A similar system may be utilized in any of the prior navigation systems. These systems do not actually store an image of a directed graph. Rather, a data structure representing the graph (or similar system) is stored. Each entry in the data structure represents a node. For each node, the data structure stores the location of the node (e.g., latitude and longitude), a list of neighboring nodes (nodes which can be traveled to via one link) and the various costs associated with getting to the neighboring nodes. The nodes and links are maintained in a database which is then searched to find routes in which to navigate the graph or network.
One general problem with navigation systems is that of how to search or determine the proper navigational route from the possible choices. This problem is particularly difficult when presented with a large network having many possible routes within which to navigate. However, once a network is known, systems for determining routes are also known. One example would be an application of Dijkstra's Search Algorithm (E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, Vol. 1, pp. 269-271 [1959]) to the directed graph.
Poppen et al., U.S. patent application Ser. No. 08/802,733, filed Feb. 20,1997, entitled “CACHING FOR PATHFINDING,” incorporated herein by reference, in its entirety, teaches a system for determining routes for a directed graph. This and other route finding systems look at a network as a set of individual paths and piece together an acceptable route by iteratively and intelligently selecting and comparing possible routes.
One method for increasing the efficiency of the iterative route determination systems is to utilize a system of tiles representing an area (network) to be navigated. Such a system is described in Amakawa et al., U.S. Pat. 6,016,485, Ser. No. 09/023,504, filed Feb. 13, 1998, entitled “A SYSTEM FOR PATHFINDING,” incorporated herein by reference, in its entirety. Briefly described, the network is broken into tiles having plural entrance and exit nodes, which are then utilized as entrance and exit points to the tiles. Route planning within a tile does not change, but the routes between tiles are well known and quickly calculated. Thus navigation or route planning need only be calculated for travel within an origin tile and a destination tile.
Determining the cost of a particular route is also important to a successful navigation aid. Such cost may be measured in $ (tolls), gasoline, or time, for example. U.S. Pat. No. 5,729,458, entitled “COST ZONES,” incorporated herein by reference, teaches about the use of costs.
The above-discussed technical innovations have led to modern mapping and navigation systems for automotive, marine, and other transport systems, that are cost efficient and provide quality, needed information to users. The above technologies are also applicable to computing networks and communications systems that also require route planning (telecom applications, static applications, Internet applications, PC applications, etc, for example).
However, in today's fast paced environment many people do not necessarily have the time to learn new navigation systems. Even once learned, inputting starting locations and destinations can be time consuming and cumbersome. Even a simple mechanism for inputting a destination would necessarily divert some of a drivers attention from the task at hand (driving, for example). Sometimes the starting location and/or destination is not precisely known at the beginning of a trip.
Current routing, guidance, and map display systems only provide limited help to a driver who does not enter a destination. Furthermore, large amounts of real time traffic information is currently available via electronic communication and other means that provides relevant information that a driver would want to consider in determining a selected route. Such information is generally too abundant to be effectively displayed for consideration by the driver.
SUMMARY OF THE INVENTION
A navigation device would be very useful, and alleviate many of the problems in the prior art, if driving directions would be presented without a requirement of a destination. Roughly described, the present invention provides a navigational device that computes and displays driving directions and/or information to any of general destinations, including, but not limited to, any of the following: major cities, landmarks, streets, routes, waypoints, waypaths (such as a highway), and other general destinations without a specific destination or origin input requirement from a user.
The invention is particularly useful in a case where there are at least two possible destinations (and in general several). The invention gives a user information necessary (and at the appropriate time) to make decisions (choices between alternative general destinations). For example, suppose a user has agr
Kamei Asao
Suranyi Edward J.
Black Thomas G.
Fliesler & Meyer LLP
Hernandez Olga
Tele Atlas North America, Inc.
LandOfFree
Method and apparatus to generate driving guides does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus to generate driving guides, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to generate driving guides will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3339666