Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
2001-12-11
2004-03-09
Arthur, Gertrude (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C701S023000, C701S209000, C340S990000
Reexamination Certificate
active
06704645
ABSTRACT:
BACKGROUND OF THE INVENTION
Certain embodiments of the present invention relate to navigational route planning. In particular, certain embodiments of the present invention relate to determining a route through a road network.
Route planning devices are well known in the field of navigational instruments. Several algorithms utilized by planning devices calculate the route from one of the source and/or destination locations or from both simultaneously. Conventional planning algorithms operate based on a predefined stored data structure including data indicative of a geographic region containing the source and destination locations.
Some devices implement a straight line approach in determining the distance between source and destination locations. In the straight line approach, the processor creates a straight line from the present location to the final destination and measures that straight line distance. For example, if a desired destination is on a mountain, the straight line distance from a current location might be only six miles. However, if the only available road to that destination is a windy road around the mountain entailing 30 miles of actual driving, the route planning distance calculated by the straight line approach will be inaccurate.
Other devices implement a nodal analysis in which a number of potential paths are determined from a present location to a destination location based on stored data indicative of roadways between nodes. The nodal analysis then examines each potential path and determines an impedance or “cost” associated with each path (i.e. a measure of the amount of time or distance required to travel the path). Paths are eliminated based on criteria such as shortest distance, shortest time, lowest cost, or user inputted preferred routes.
However, conventional route planning devices will not find the most efficient route since they do not take into consideration certain factors that affect travel over a particular route. For example, a user may input desired source and destination locations, and request the route that covers the shortest distance. While only one particular route may be the physically shortest distance between source and destination locations, other near-shortest routes may exist that are only slightly longer. The shortest and near-shortest routes include travel along different combinations of roads and travel through unique combinations of road intersections. Each road in the shortest and near-shortest routes has an associated travel speed, representing the speed limit or range at which traffic typically travels over the road. Also, each road in the shortest and near-shortest routes passes through a combination of intersections. The shortest and near-shortest routes may be close in length, while the shortest route may include roads with slower travel speeds and/or more intersections and/or intersections that typically require more time (e.g., stop signs, stop lights, crossing larger/busier highways, turning across traffic onto a new road, etc.) as compared to one or more near-shortest routes.
Conventional route planning devices produce a shortest distance route which includes roads that are selected independent of whether the roads have slower traveling speeds. Conventional route planning devices do not include travel-time information for road intersections, nor account for delays at road intersections when planning a route. Although one route represents the shortest distance, a more efficient route may exist with a slightly longer distance (e.g., a near-shortest distance route). The difference between the length of the shortest distance route and the near-shortest distance route may be insignificant. Consequently, the user may travel for a longer period of time and encounter more traffic delays by taking the shortest distance route.
Conventional route planning devices do not take into consideration travel delays experienced at intersections, such as delays due to stop signs, stop lights, crossing lanes of on-coming traffic, turning onto or off of one-way roads, the angle at which roads intersect when a route turns from one road onto another, and the like. This is not desirable.
Thus, a need has long existed in the industry for a method and apparatus for determining impedance time through a road network that addresses the problems noted above and other problems previously experienced.
BRIEF SUMMARY OF THE INVENTION
Certain embodiments of the present invention relate to a method for estimating an impedance time through a node at an intersection between roads in a roadway network. The method includes identifying characteristic information that describes at least one feature of the intersecting roads. Based on the characteristic information, an impedance time associated with potential delays by traffic traveling through the node is estimated. The characteristic information may include speed information, such as speed categories or speed bands. A speed band identifies a speed range in which traffic travels on the road, and a speed differential between the speed bands of intersecting roads may be determined. Optionally, the characteristic information may include road-type or network routing level information, such as when the roadway network is divided into a hierarchy of road-types. A route level may be assigned to each road intersecting at a node, and a route level differential between the route levels of the roads may be determined. The characteristic information may include intersection angle information and/or cross traffic turn information.
In another embodiment of the present invention, a method is provided for calculating a navigation route between first and second geographic locations through a roadway network of roads that intersect at nodes. A data structure is provided that has data indicative of the roadway network of roads. The data includes feature data indicating traffic characteristics for the roads. Route impedance is calculated for a navigation route through the roadway between the first and second locations based on the feature data. The node impedance is determined for the navigation route where the navigation route intersects other roads. The node impedance may indicate a potential delay that traffic experiences when traveling through a node. The node impedance and route impedance are used to calculate the navigation route. The node and route impedances may be measured in time or distance.
The feature data may include speed information, one-way, and/or intersection angle information. A turn penalty may be assigned when the navigation route crosses on-coming traffic. Optionally, a neighborhood penalty may be added to the node or route impedance when the navigation route travels through residential areas that are not located at the first and second geographic locations. Optionally, an exit/entry ramp penalty may be added to the node or route impedance when the navigation route travels along an exit ramp from a first road directly onto an entry ramp back onto the first road.
In another embodiment of the present invention, a navigation device is provided comprising a memory and processor. The memory at least temporarily stores at least a portion of a data structure having data indicative of a roadway network of roads intersecting at nodes. The data structure includes feature data of traffic characteristics for roads. The processor accesses the memory and calculates a route through the roadway network between geographic locations from the data stored in the data structure. The processor estimates node impedances for intersection nodes, and utilizes the route impedance and node impedance to calculate the route. The feature data may include speed information, road-type information, routing level information, intersection angle information, and/or cross traffic information which is used to calculate node impedance. Optionally, the device may include an input buffer for temporarily storing a portion of the data structure received from an external storage device. In one embodiment, the device includes a display that presents
Beesley Darin J.
Childs Michael
Arthur Gertrude
Garmin Ltd.
Rolf Devon A.
LandOfFree
System and method for estimating impedance time through a... 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 and method for estimating impedance time through a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for estimating impedance time through a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214692