Abstract:
In order to create a method for making available driving lane recommendations for each driving direction relating to at least one curb and interlinked with one another, as well as a system related thereto, which improve the quality of the driving instructions provided by a navigation device via optimized processing of the driving lanes on roads, in particular at intersections, it is recommended that (a) a curb ( 10, 11, 12; 10′, 12′, 15′ ) be assigned at least one lane list ( 20 ) whose elements ( 20   .a   .1.1, 20   .a   .1.2, 20   .a   .2 ) contain lane information on the totality of the driving lanes assigned to the curb ( 10, 11, 12; 10′, 12′, 15 ′); (b) each of the driving lanes be assigned at least one lane data list ( 30; 40 ) whose elements ( 30   .b   .1, 30   .b   .2; 40   .b   .1, 40   .b   .2 ) each contain lane data information on the particular driving lane; and (c) each follow-on driving lane succeeding the driving lane be assigned at least one follow-on lane list ( 50; 60; 70 ) whose elements ( 50   .c   .1, 50   .c   .2, 50   .c   .3, 50   .c   .4; 60   .c   .1, 60   .c   .2, 60   . c   .3, 60   .c   .4; 70   .c   .1, 70   .c   .2, 70   .c   .3, 70   .c   .4 ) each contain follow-on lane information, interlinked with the lane data information of the preceding driving lane, on the particular follow-on driving lane.

Description:
FIELD OF THE INVENTION 
   The present invention relates to the use, in a navigation device, of a method for making available driving lane recommendations for each driving direction relating to at least one curb or one segment of road and interlinked with one another. The present invention further relates to a system for implementing such a method. 
   BACKGROUND INFORMATION 
   In means of transportation such as motor vehicles, permanently installed navigation devices simply, quickly, and safely guide the driver of a means of transportation from the current location to a desired destination without the driver of the means of transportation first having to elaborately plan a route and obtain appropriate maps. 
   For this purpose, appropriate navigation data based on charts, maps, or street maps are available stored, for example, on CD-ROM (=Compact Disc-Read Only Memory) or on DVD (=Digital Versatile Disc). The navigation device uses GPS (=Global Positioning System), for example, in order to determine the current location and calculate the appropriate navigation instructions that lead to the predetermined destination. The navigation data, in this connection, preferably contains data on roads and paths for motor vehicles. 
   An important component of the above-mentioned basic function of a navigation device is the processing of the driving lanes on the roads, especially before, at, and after intersections. Driving lanes, in this case, are to be understood as the fanning out of the driving directions, in particular before an intersection, painted on the road. 
   The processing of such driving lanes, which may be found directly on the road surface or on signs installed above the roads such as in the form of sign bridges and/or electronic alternative-route indicators having directional symbols and/or distant destinations, will initially be required only at freeway interchanges, but later also at all other intersections having driving lanes. 
   In this context, it must be considered, however, that so far, in conventional navigation devices, the processing of linked consecutive driving lanes is still inadequate. The driver of the means of transportation is not provided with information by the navigation device enabling him to optimally navigate the means of transportation through street traffic, especially in the case of a rapid succession of multiple intersections or forks in the road. 
   SUMMARY OF THE INVENTION 
   Based on the above-mentioned disadvantages and shortcomings, the object of the present invention is to create a method as well as a system, of the type mentioned at the outset, which improve the quality of the driving instructions provided by a navigation device via optimized processing of driving lanes on roads, in particular at intersections. 
   According to the teaching of the present invention, all curbs of the respective lanes are therefore given attributes carrying certain information explained in more detail below. Inserting the driving lanes into the curbs is carried out according to a particularly inventive further development by attaching the driving lanes to the particular curbs as new attributes. 
   Independent of or in conjunction with this, the curbs should expediently only carry one lane situation in each driving direction, otherwise they should be divided. The information initially contains only one list of available lanes (=“lane list”) per driving direction, i.e., in digitization direction of the curb or counter to the digitization direction of the curb. The sequence of the elements of the lane list should in this connection expediently coincide with the sequence of the lanes on the street, and should be counted from the outer curb of the road. 
   According to an advantageous further development of the present invention, the information further contains the length on which the lanes are available starting from the particular end of the curb; this avoids partitions of the curb in an advantageous manner in case lanes are only available at the end of the curb. 
   Each element of the lane list preferably contains the directional symbol associated with it, as well as optional additional information on special uses and other restrictions such as reservation of the lane for buses, taxis, or the like. This may also include—in a manner essential to the present invention—information in each element of the lane list regarding whether or not the lane marker for two adjacent driving lanes, i.e., for the adjacent left-hand lane or the adjacent right-hand lane, may be crossed by the driver of the means of transportation. 
   A relevant component of the information may also be at least one intersection approaching in the driving direction which is reached via this lane. If a curb is referred to that also has lanes, reference may be made to one of these lanes if it is understood to be a continuation of the original lane. 
   According to an advantageous embodiment of the present invention, the curbs, reference having been made to themselves or to their lanes, are linked to the same intersection as the original curb, but do not have to be directly meshed with same, since the intersection may also be complex, i.e., it may not consist of only one node, but of multiple nodes. In this case, it cannot always be guaranteed that it is possible to follow the lanes within these complex intersections. 
   In connection with the practical implementation and the actual application possibilities of the present invention, attention must be paid to the fact that a situation-and/or time-dependent switching of the lanes must be expected, as happens with greater frequency today via electronic alternative-route indicators in light of increased traffic densities, especially in city traffic with access and exit roads or on freeways having emergency lanes. The design of the data, therefore, should expediently facilitate the representation of such a dependency accordingly. 
   Generally, in view of the present invention, the fact must be considered that the quality of the acquisition of lanes may not in some cases be as high as the quality of the attributes relevant for the route search (one-way streets, turning prohibitions and the like). This may possibly result in discrepancies between route search and navigation using driving lanes, i.e., there are driving lanes at an intersection, but it is not possible to find a driving lane corresponding to the calculated route. Construction sites or the like also come to mind in this regard, of course, which in most cases involve detours or at least shifting of lanes. 
   In an embodiment essential to the present invention, lane information may also be used to make a perspective representation of the intersection and/or street existing in reality more realistic. For this purpose, the described data model, implemented according to the present invention in terms of method as well as system, contains all relevant information. 
   According to the present invention, the possibility of at least one selected driving lane carrying distant-destination information must be considered, so that this information may be included for the purpose of creating directions for getting into the correct lane, regardless of where the actual destination is (—&gt;navigation device: “Take the lane for Dortmund!”) 
   Regarding the requirements on raw data for the method and the system according to the present invention, the data for a meaningful use of driving lanes for navigating must be selected such that the following categories and parameters may be filled with (data) content:
         number of driving lanes at the approaching end of the traveled curb;   type of symbols (if any) with which the individual driving lanes are marked on the road or on signs;   driving lanes that may be used, in other words those that are not bus or taxi lanes;   adjacent driving lanes, between which it is permitted to switch; and   driving lane/s that is/are to be used in order to reach the subsequent curb, calculated by the route search algorithm, and the correct driving lane for continuing the route.       

   In this connection, the present invention also extends to a starting point essential to the present invention, where driving lanes may be digitized as separate curbs. In this case, the route search algorithm would assume the task of selecting the correct driving lane. It must be noted, however, that, at least at the moment, there still exist various inherent inadequacies with a mode of this type such as a difficult-to-manage data quantity, a certain locating uncertainty, digitization only from aerial photos, as well as the need for frequent changes. 
   The present invention, finally, relates to a navigation device operating according to a method of the type described above and/or having at least one system of the type described above. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1A  schematically shows a navigational driving lane recommendation for the right-hand lane. 
       FIG. 1B  schematically shows a navigational driving lane recommendation for the two center lanes. 
       FIG. 2A  schematically shows a lane combination with exit lane. 
       FIG. 2B  schematically shows a curb diagram assigned to the driving lane combination from  FIG. 2A . 
       FIG. 2C  schematically shows an alternative curb diagram assigned to the driving lane combination from  FIG. 2A . 
       FIG. 3A  schematically shows a basic driving lane combination with intersection. 
       FIG. 3B  schematically shows a curb diagram assigned to the basic driving lane combination from  FIG. 3A . 
       FIG. 4A  schematically shows an expanded driving lane combination with two intersections. 
       FIG. 4B  schematically shows a curb diagram assigned to the expanded driving lane combination from  FIG. 4A . 
       FIG. 5A  schematically shows a further driving lane combination with branching of two expressways. 
       FIG. 5B  schematically shows a curb diagram assigned to the further driving lane combination from  FIG. 5A . 
       FIG. 6  schematically shows an “entity relationship” model of the present invention; and 
       FIG. 7  schematically shows a structure diagram of the interlinked lists in the present invention. 
   

   DETAILED DESCRIPTION 
   In the method and system according to the present invention, the driver of a means of transportation is able to receive information, in addition to the usual driving instruction, via driving lane information before reaching a decision point regarding which of the available driving lanes is best taken in order to be able to easily follow this driving instruction (see  FIG. 1A , according to which the driver of the means of transportation would have to pick the right-hand one of the three driving lanes). 
   In real street traffic situations, there may be multiple suitable driving lanes when choosing lanes (see  FIG. 1B , according to which the driver of the means of transportation would have to pick the middle, i.e., one of the two center lanes). While it is relatively simple to graphically represent such a situation, which is a little more complex than the situation in  FIG. 1A , the oral identification of multiple lanes is difficult, especially when more than three driving lanes are available. 
   The present invention provides a possible alternative embodiment where the graphical representation of the driving lanes on the display device or on the display of a navigation device should coincide as far as possible with what the driver of the means of transportation sees painted on the driving lane or marked on signs in front of him. The arrow symbols used there—if any—should be taken into consideration in the design of the graphics of the navigation device. 
   In this connection, a test should also be carried out to see whether the lane-changing instructions should replace or supplement the driving instructions at this location, and/or how the calculation of the driving instructions is affected by the presence of driving lanes. 
   In the driving lane recommendations according to  FIGS. 1A  or  1 B, the change in direction at the immediately following decision point determines the driving lane selection. Should multiple lanes be available in one direction (see  FIG. 1B  for the “straight-ahead” direction), the navigation device recommends both lanes equally. 
   There are, however, also complex driving lane combinations, where the most favorable driving lane may only be selected if the route is viewed across more than one intersection (see  FIG. 4A ). In order to get from street A to street C in the extended driving lane combination according to  FIG. 4A , the driver of the means of transportation on street A must take the center lane, then, on street B, the right-hand driving lane, in order to then be able to turn into street C. Should the driver of the means of transportation want to continue his journey on street E, the left-hand or center lane on street A would be available to him. Street D may only be reached if the left-hand driving lane on street A is used. 
   Such lane sequences are sometimes crucial for the driver of the means of transportation, i.e., if the driver of the means of transportation takes the incorrect lane—in other words the left-hand lane—on street A with the complex lane combination of  FIG. 4A , he is subsequently not permitted to change lanes again and must continue his journey in departure from the planned route on street B or street D. But even if there is no such constraint and it is still permissible to change lanes, it is desirable to provide information on the most favorable lane in any case in order to minimize the number of lane change maneuvers that are often critical in city traffic. 
   For the concept described above it is basically not necessary to know whether the driving lanes have dotted or solid lane markers, i.e., whether or not a lane change is permitted. If the linking of the lanes at the intersections is correctly digitized, the described route search algorithm will—if at all—select a lane sequence that will not require lane changes at the particular curbs. 
   A correct interlinking of the driving lanes, however, is only possible if the number of lanes along each of the curbs does not change. This means that the curbs must be divided in places where the number of driving lanes changes. At freeway exits, where typically the number of driving lanes increases by an exit lane, a lane combination as shown in  FIG. 2  results; here, the node or intersection point marked by a separate arrow in  FIG. 2B  only exists due to the change in the number of driving lanes. 
   Alternatively, the exit according to  FIG. 2A  may also be digitized using a different course of a curb. This is how the exit lane is regarded as a separate driving lane according to  FIG. 2C . The method according to the present invention may be used regardless of whether the curb diagram according to  FIG. 2B  or the curb diagram according to  FIG. 2C  has been chosen. 
   Regarding the “weave lanes” (merge or exit lanes), it must be added in this connection that, while in the lane combination depicted in  FIG. 2A  part of the expressway is recorded as having three lanes, this change in the number of lanes may only result in a lane change instruction if the expressway is to be left at the exit. In order to safely recognize this situation, the right-hand lane should be marked as a weave lane here. Lane-related instructions are only issued here if the weave lane must actually also be used. 
   However, it is not always possible to follow the selected route without changing lanes. Using the branching of two expressways shown as an example in  FIG. 5A  (in  FIGS. 5A and 5B  only the driving direction from right to left is shown), some situational examples can be illustrated; here it also becomes clear that for a complete description of the lane situation, the permissibility of crossing the lane markers must be known (dotted line, solid line, or both). 
   Route A-&gt;C-&gt;D, Route A-&gt;C-&gt;E: 
   Before the solid lane marker begins, the driver of the means of transportation must be guided into the right-hand driving lane (-&gt;route A-&gt;C-&gt;D) or into the left-hand driving lane (-&gt;route A-&gt;C-&gt;E) while still on street A in order to be able to follow the particular route. 
   Route A-&gt;C-&gt;F: 
   On street A, the driver of the means of transportation must first be guided into the left-hand driving lane and then into one of the left-hand lanes of street C; in other words, a lane change on street C is thus unavoidable. 
   Route B-&gt;C-&gt;D, Route B-&gt;C-&gt;E: 
   These routes cannot be followed by the driver of the means of transportation without crossing solid lines; there is a contradiction between the digitization of the driving lanes and the “turn restrictions,” but an automatic check of the data for such inconsistencies is possible. 
   Route B-&gt;C-&gt;F: 
   On this route no lane change is necessary, regardless of which driving lane is entered, and since no decision must be made, a driving instruction is also superfluous. 
   As far as the concrete implementation of the method, as well as the system, according to the present invention regarding following the course of a lane along a route is concerned, the presented data model makes it possible to select and output the most favorable driving lane based on the calculated route. Here, all curbs (“oncecells”) of the respective driving lanes are given attributes that carry certain information, explained in more detail below. 
   In this connection, curbs in each driving direction have only one lane situation, otherwise they are divided (see also the basic lane combination with intersection in  FIG. 3A , as well as the curb diagram in  FIG. 3B  assigned to the driving lane combination in  FIG. 3A , each in schematic form). 
   The procedure used in following the course of the lane will be explained via the schematic curb diagram according to  FIG. 4B  using the example of the complex driving lane situation with two intersections shown in  FIG. 4A . The route was calculated in the curb sequence  10 -&gt; 11 -&gt; 12  (see  FIG. 4B ). The means of transportation here is on curb  10 , and—according to the present invention—it must be determined which lane is the most advantageous for following the route. 
   Curb  10  as the starting curb has three lanes:
         Driving lane  1  points to curbs  15  and  16 ; curbs  15  and  16 , however, are not part of the route, so that following driving lane  1  may be aborted;   Driving lane  2  points to driving lane  1  of curb  11 ; curb  11  belongs to the route, so that driving lane  2  must continue to be followed to curb  11 ;   Driving lane  3  points to driving lane  2  of curb  11 ; curb  11  belongs to the route, so that driving lane  3  must continue to be followed to curb  11 .       

   Now two driving lanes—driving lane  2  and driving lane  3 —of curb  10  have to continue to be followed; unambiguity has not yet been achieved, and the algorithm must be continued. 
   Curb  11  is the route successor, which means it is the successor curb of curb  10 , and has two lanes that must continue to be followed:
         Driving lane  1  points to curbs  12  and  14 ; curb  12  belongs to the route, so that driving lane  1  must continue to be followed to curb  12 ; curb  14 , however, is not part of the route, so that following driving lane  1  on curb  14  is not necessary;   Driving lane  2  points to curbs  13  and  14 ; curbs  13  and  14 , however, are not part of the route, so that following driving lane  2  may be aborted.       

   Now only one lane—lane  1  of curb  11 —must continue to be followed, thus having achieved unambiguity, and the algorithm may be aborted, since driving lane  1  on curb  11  is the only “survivor,” and the predecessor-driving lane  2  on curb  10  is the driving lane to be determined. 
   The procedure of following lanes will be explained based on another example of the driving lane combination shown in  FIG. 5A  occasioning necessary lane changes due to the intersecting of two expressways, using the schematic curb diagram according to  FIG. 5B . The route was calculated in the curb sequence  10 ′-&gt; 12 ′-&gt; 15 ′. Here, the means of transportation is on curb  10 ′, and it is to be determined, according to the present invention, which driving lane is the most advantageous for following the route. 
   Curb  10 ′ as the originating curb has two driving lanes:
         Driving lane  1  points to driving lane  1  of curb  12 ′; curb  12 ′ belongs to the route, so that driving lane  1  must continue to be followed to curb  12 ′;   Driving lane  2  points to driving lane  2  of curb  12 ′; curb  12 ′ belongs to the route, so that driving lane  2  must continue to be followed to curb  12 ′.       

   Now two lanes—lane  1  and lane  2 —must continue to be followed; unambiguity has not yet been achieved, and the algorithm must be continued. 
   Curb  12 ′ is the route successor, which means it is the successor curb of curb  10 ′, and has four driving lanes that must continue to be followed:
         Driving lane  1  points to curb  13 ′; curb  13 ′, however, is not part of the route, so that following driving lane  1  of curb  12 ′ may be aborted.   Driving lane  2  points to curb  14 ′; curb  14 ′, however, is not part of the route, so that following driving lane  2  of curb  12 ′ may be aborted.       

   Now none of the lanes from curb  10 ′ to be followed runs along the calculated route.
         Driving lane  3  points to curb  15 ′; curb  15 ′ belongs to the route, so that driving lane  3  to curb  15 ′, which may be reached by a lane change from driving lane  2  at curb  12 ′, has to continue to be followed.   Driving lane  4  points to curb  15 ′; curb  15 ′ belongs to the route, so that driving lane  4  to curb  15 ′, which may be reached by a lane change from driving lane  2  at curb  12 ′ via driving lane  3 , has to continue to be followed.       

   Now two driving lanes—driving lanes  1  and  2  at curb  15 ′—have “survived,” so that the most advantageous driving lane sequence along the route is as follows: 
   Driving lane  2  in curb  10 ′
         -&gt;Driving lane  2  in curb  12 ′   -&gt;Change to driving lane  3  or driving lane  4  in curb  12 ′   -&gt;Driving lane  1  or driving lane  2  in curb  15 ′.       

   As a result, the method as well as the system according to the present invention may be abstracted in an abstract way in the form of an “entity-relationship” model shown in  FIG. 6 , where curb  10  carries digitization direction  82  and length  20 . a.   2  (-&gt;reference notation  80 ). Driving lane  84 , being assigned destination name  88 , symbol  86 , and driving lane number  50 . c.   1 , leads back to (-&gt;reference notation  90 ) curb  10 . 
   If this model is then implemented, the driving lanes are introduced into the curbs, wherein the driving lanes of the affected curbs are appended as a new annotation as seen in  FIG. 7 : 
   A curb  10  is assigned a lane list  20  whose elements  20 . a.   1 . 1 ,  20 . a.   1 . 2 ,  20 . a.   2  contain lane information on the totality of the two driving lanes assigned to curb  10 , namely the lane information
         on the driving lanes at the beginning of curb  10  (-&gt;reference notation  20 . a.   1 . 1 ),   on the driving lanes at the end of curb  10  (-&gt;reference notation  20 . a.   1 . 2 ), and   on the length of the driving lanes or on the fraction of the length of the driving lanes at curb  10  (-&gt;reference notation  20 . a . 2 ).       

   The sequence of elements  20 . a.   1 . 1 ,  20 . a.   1 . 2 ,  20 . a.   2  of lane list  20  here corresponds to the actual sequence of the two driving lanes, i.e., the right-hand driving lane corresponds to the first driving lane, and the left-hand driving lane corresponds to the second driving lane, counting from the outer side of the road. 
   As can be further seen in  FIG. 7 , each of the two driving lanes—that is the first (=right-hand) driving lane and the left-hand (second) driving lane—is assigned a lane data list  30  and  40 , respectively, whose elements  30 . b . 1 ,  30 . b.   2  and  40 . b . 1 ,  40 . b.   2 , respectively, contain lane data information on the particular driving lane. 
   Elements  30 . b . 1 ,  30 . b . 2  and  40 . b . 1 ,  40 . b . 2  of lane data lists  30  and  40 , respectively, contain lane data information for each of the driving lanes
         on the direction of the driving lane (-&gt;reference notation  30 . b . 1  and  40 . b . 1 , respectively) and   on the number of the at least one follow-on driving lane succeeding the driving lane (reference notation  30 . b . 2  and  40 . b . 2 , respectively). Furthermore, elements  30 . b . 1 ,  30 . b . 2  and  40 . b . 1 ,  40 . b . 2  of lane data lists  30  and  40 , respectively, contain additional lane data information such as on special uses of the driving lane or other restrictions on the driving lane.       

   Finally,  FIG. 7  also shows that each follow-on driving lane succeeding the driving lane is assigned a follow-on lane list  50  or  60  or  70  whose elements  50 . c . 1 ,  50 . c . 2 ,  50 . c . 3 ,  50 . c . 4  or  60 . c . 1 ,  60 . c . 2 ,  60 . c . 3 ,  60 . c . 4  or  70 . c . 1 ,  70 . c . 2 ,  70 . c . 3 ,  70 . c . 4  include follow-on lane information on the particular follow-on driving lane interlinked with the lane data information of the preceding driving lane. 
   Elements  50 . c . 1 ,  50 . c . 2 ,  50 . c . 3 ,  50 . c . 4  or  60 . c . 1 ,  60 . c . 2 ,  60 . c.   3 ,  60 . c . 4  or  70 . c . 1 ,  70 . c.   2 ,  70 . c . 3 ,  70 . c . 4  of follow-on lane list  50  or  60  or  70  include follow-on lane information for each of the follow-on driving lanes
         on the follow-on driving lanes at the beginning of assigned curb  11  or  12  or  13  (-&gt;reference notation  50 . c . 1  or  60 . c . 1  or  70 . c . 1 ),   on the follow-on driving lanes at the end of assigned curb  11  or  12  or  13  (-&gt;reference notation  50 . c . 2  or  60 . c . 2  or  70 . c . 2 ),   on the direction and/or position of assigned curb  11  or  12  or  13  (-&gt;reference notation  50 . c . 3  or  60 . c . 3  or  70 . c . 3 ) and   on the number of the follow-on driving lane (-&gt;reference notation  50 . c . 4  or  60 . c . 4  or  70 . c . 4 ) according to a reference to the identifier of succeeding assigned curb  11  or  12  or  13 .