Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-03-07
2001-11-27
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S200000, C701S202000, C701S208000, C340S990000, C340S995190, C707S793000
Reexamination Certificate
active
06324470
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to navigation systems and more particularly the present invention relates to a way to avoid prohibited driving maneuvers when using a navigation system to determine a route to a destination.
Navigation systems provide useful features, such as calculating a route to a desired destination and providing guidance for following the route. In order to provide these features, navigation systems use geographic data that include information about the locations of roads and intersections, estimated travel times along road segments, the speed limits along roads, etc. Using geographic data, programming algorithms used in navigation systems can find an optimal (e.g, fastest or shortest) route to a specified destination.
The geographic data used by navigation systems also include data about traffic restrictions, such as one-way streets, no-left-turns, etc., so that the navigation system can calculate a legal route (i.e., a route that conforms to applicable traffic laws and regulations). For example,
FIG. 1
illustrates a simple intersection at which it is illegal to make a right turn from road “A” to road “B.” In the geographic data, a data record used to represent the intersection of road A and road B may include information about this turn restriction. Similarly, if a road is a one-way street, information about this direction of travel restriction is included in the one or more data records that represent the road.
In addition to traffic restrictions that involve only two road segments, there are types of traffic restrictions that involve more than two road segments. Two examples of traffic restrictions that involve several segments (three or more segments) are shown in
FIGS. 2 and 3
.
FIG. 2
illustrates lanes in one direction of traffic on an expressway where traffic flows from segment
2
to
3
to
4
. Segment
1
represents an entrance ramp on the left, and segment
5
represents an exit ramp on the right. If segment
3
is too short to safely allow a vehicle entering the expressway on segment
1
from exiting via segment
5
, traffic authorities may prohibit such a maneuver.
In
FIG. 3
, roads X and Y represent major arteries, while segments
5
,
6
, and
7
represent local roads. In many cases, a municipality will restrict drivers from taking a short cut from road X to road Y by prohibiting the sequence
1
-
5
-
6
-
4
and require drivers to follow the sequence
1
-
2
-
3
-
4
. Turns are permitted into and out of the neighborhood as long as the illegal sequence is not followed.
In a navigation system, several-segment (3 or more) restricted driving maneuvers are more difficult for routing algorithms to deal with than two-segment restricted driving maneuvers. Several-segment restricted driving maneuvers require that the database include information that flags each segment in the several-segment restricted driving maneuver. Routing algorithms check every segment examined for this flag and ensure that the expanded route does not follow an illegal sequence. This becomes more complex if the routing algorithm is a two-ended A* algorithm and the several-segment restricted driving maneuver occurs where the source and destination search trees meet. Due to the complexity of implementation and extra processing required, some database compilers drop this data. Other database compilers may include it, but the in-vehicle routing application ignores it. As a result, illegal routes may be generated even when the data exists to prevent such routes.
Accordingly, there is a need for an improved means to handle several-segment restricted driving maneuvers.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention comprises a method that facilitates complying with traffic restrictions that involve three or more connected road segments when using a navigation system to determine a route. The method includes forming multiple instances of data representing each intermediate road segment between an entrance segment and an exit segment and storing data defining restrictions that apply to only two connected road segments, such that a valid driving paths exists between the entrance segment and the intermediate segment and between the intermediate segment and the exit segment, but that no valid driving paths exist between the entrance segment and the exit segment.
The present invention also includes a geographic database that embodies the described method for representing restricted driving maneuvers that involve three or more connected road segments, wherein the geographic database is stored on a computer-readable medium.
REFERENCES:
patent: 4862373 (1989-08-01), Meng
patent: 4888698 (1989-12-01), Driessen et al.
patent: 5031104 (1991-07-01), Ikeda et al.
patent: 5036471 (1991-07-01), Tamura et al.
patent: 5041983 (1991-08-01), Nakahara et al.
patent: 5072395 (1991-12-01), Bliss et al.
patent: 5170353 (1992-12-01), Verstaete
patent: 5513110 (1996-04-01), Fujita et al.
patent: 5953722 (1999-09-01), Lampert et al.
patent: 5963956 (1999-10-01), Smartt
patent: 5968109 (1999-10-01), Israni et al.
patent: 5974419 (1999-10-01), Ashby
patent: 6122593 (2000-09-01), Friederich et al.
patent: WO 99/58934 (1999-11-01), None
Samet, Hanan: “The Strategies for Optimizing the Use of Redundancy in Spatial Databases”,The Design and Analysis of Spatial Data Structures, ISBN 0-201-50255-0, Chapter 2.4 (1996).
Matsuyama, et al.: “A file Organization for Geographic Information Systems Based on Spatial Proximity”,Computer Vision, Graphics and Image Processing26, 303-318. (1984).
Arthur Gertrude
Cuchlinski Jr. William A.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corporation
LandOfFree
Method and system for representing restricted driving maneuvers 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 system for representing restricted driving maneuvers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for representing restricted driving maneuvers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583151