Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
1999-07-15
2001-05-08
Issing, Gregory C. (Department: 3662)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
Reexamination Certificate
active
06230099
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method of determining a route from a starting point to a destination in a route network, especially a network of roads or streets, which is represented by a group of straight edges and nodes in a memory, in which each edge is correlated with a path resistance and the route is determined as a successive sequence of edges by minimizing the sum of all the path resistances.
2. Prior Art
In vehicles, such as motor vehicles, aircraft or ships, installed navigation systems guide the driver of the vehicle rapidly, reliably and easily to the desired destination, without the previous effort of planing a route and acquiring and studying map or chart materials. Navigation data is stored, for example on CD-ROM, in navigation systems, which includes appropriate data from charts, maps or road maps. The navigation apparatus, for example, uses GPS (Global Positioning System), in order to establish a momentary position and to compute appropriate navigation directions for guidance to a predetermined destination. The navigation data preferably includes data regarding streets and roads for a motor vehicle.
Suitable algorithms for route planning have been used in navigation systems, which compute an optimum route of travel from a starting point to a destination using stored navigation data together with the starting point and the destination. This sort of algorithm for route planning is based on the best path algorithms according to Ford and Moore, which are known from graph theory and are adjusted to the special requirements of self-sufficient vehicle navigation systems.
As is apparent from
FIG. 1
, the road network is represented by a route algorithm such as a graph with edges k and nodes p, for mathematical processing in which the edges correspond to roads or streets and the nodes correspond to intersections of the roads or road network. In
FIG. 1
four edges k
1
, k
2
, k
3
and k
4
and four nodes p
1
, p
2
, p
3
and p
4
are provided. Since the traffic flow is directional in real road traffic, an edge k must be represented as a directional vector. Furthermore a resistance, the so-called path resistance, which is a variable representing the effort required to travel from one node in the network to another, is associated with each edge k. For example, the edge length is used as the path resistance. Alternatively the travel time along the edge can be used as the path resistance, thus including the average travel speed along the respective edge. In a further alternative embodiment a cost function is provided, which involves a weighted mixed computation of various properties, such as the edge length, travel time on an edge or the width of an edge (construction condition). Also a resistance is associated with the respective nodes, which reflects the cost of vehicle maneuvers (straight out, left/right deviations, turns, etc). All best path algorithms determine only a route between a starting edge and a destination edge on a directional graph with the property that the sum of all road resistances of the edges of the determined route and if necessary with the node resistance considered is minimized.
This sort of best path algorithm calculates the route by reverse iteration and tests all edges in the graph, evaluating them in relation to the best path to the destination road or edge. In other words, starting from the destination edge, in each iteration step a best path in regard to resistance back to the edges in the list which were optimized in the previous iteration step is determined. As a result the method provides an optimum route to the destination edge from each edge in the graph. A so-called route table for the calculated result is set up in the memory of the navigation device. This sort of route table is shown for example below for the graph shown in FIG.
1
.
TABLE I
ROUTE
+Following
−Following
Edge
+Resistance
edge
−Resistance
edge
K
1
∞
−
∞
−
K
2
∞
−
∞
−
K
3
∞
−
∞
−
K
4
∞
−
∞
−
For each edge in the graph the resistance to the destination edge in the graph and the edge following in the destination direction are given. The resistance is given an “infinite” value (symbol ∞) and the following edge is set as “undefined” (symbol −) as respective initial values. A positive sign in the resistance and following edge columns stands for consideration of the respective edge in its arrow direction, whereas a negative sign stands for consideration of the respective edge opposite to its arrow direction.
Before the start of the iterative optimization the destination edge in the route table is initialized (see above) with a null resistance. As an example the edge k
3
is selected to be that destination edge. The following stored route table II results from a destination initialization.
TABLE II
ROUTE
+Following
−Following
Edge
+Resistance
edge
−Resistance
edge
K
1
∞
−
∞
−
K
2
∞
−
∞
−
K
3
0
−
0
−
K
4
∞
−
∞
−
Furthermore the destination edge k
3
is added to a list stored in the navigation device of the already optimized edges, so that a list of the already optimized edges according to the following list 1 results.
Furthermore a second list of the edges to be tested in the next optimization step is provided, which is empty at the start of the method, according to the following list I.
The method now starts, since it consider all edges listed in List I as fixed actual positions of the vehicle and all edges interconnected with this “actual-edge”, the so-called “incoming-edges”, participating in the optimization. In the exemplary embodiment (
FIG. 1
) the edges interconnected with the “actual-edge” read +k
2
, −k
3
and −k
4
. In the optimization testing now the resistance of a respective incoming-edge is compared with the resistance to the destination that the incoming-edge would have when it leads to the destination over the actual-edge. At this point a so-called resistance optimization condition is set forth:
Resistance(incoming edge)>path resistance (incoming-edge)+Resistance(actual edge).
Here “resistance” represents the resistance added into the route table and “path resistance” represents a path resistance associated with a respective edge in the graph. When this resistance optimization condition is fulfilled, the resistance of the incoming-edge in the route table is replaced by the new smaller value, the actual-edge is entered as the following edge and the optimized incoming edge is input to the list II. If all edges from the list 1, as already described, are processed, the list I and list II are interchanged and subsequently the list 2 is empty. The process ends when list 1 is found to be empty.
Subsequently this process will be explained in more detailed using the road network according to FIG.
1
. In this embodiment the edges k
1
, k
2
and k
3
have the path resistance
10
and the edge k
4
has the path resistance
30
. Sine the sol-called turning resistance is not of significance for this process, it remains unconsidered in the present example. In step 1 the actual-edge is set equal to +k
3
and the list I is as follows:
Now all incoming-edges for +k
3
are tested with the resistance optimization conditions, as illustrated in FIG.
2
. The resistance optimization conditions results:
−k
3
0>10+0 resistance optimization condition not fulfilled
+k
2
∞>10+0 resistance optimization condition fulfilled
−k
4
∞>30+0 resistance optimization conduction fulfilled.
At the end of step 1 the following contents result for list II and the route table III:
TABLE III
ROUTE
+Following
−Following
Edge
+Resistance
edge
−Resistance
edge
K
1
∞
−
∞
−
K
2
10
+k
3
∞
−
K
3
0
−
0
−
K
4
∞
−
30
+k
3
Now the lists I and I
Issing Gregory C.
Robert & Bosch GmbH
Striker Michael J.
LandOfFree
Method of determining a route from a starting point to 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 Method of determining a route from a starting point to a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining a route from a starting point to a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2506294