Routing method and device for realising said method

FIELD: physics, navigation.

SUBSTANCE: invention relates to navigation systems. The device includes means of determining a first route based on a traffic situation and for determining a second route taking into account change in the road situation, means for determining a measure of the effect of change in the road situation on the route, decision means for deciding on whether said measure (TDV) exceeds the effect of a first threshold value given by a user, and output means for offering the user two routes for selection for further navigational guidance if the measure of the effect of the first threshold value is exceeded.

EFFECT: high accuracy of estimating measures of effect of the road situation on a route.

9 cl, 6 dwg

The present invention relates to a device and method described in the independent claims.

Known navigation system for vehicles, providing navigational support of the motion of the vehicle, i.e. able to "hold" the driver of a vehicle through visual or voice guidance from your current location on the calculated route to the destination. The calculation of the route is, as a rule, in the sense of optimizing the route using at least one optimization criterion, such as the fastest or the shortest path.

From the publication DE 4008460 A1 is known a navigation system for a ground vehicle, receiving messages about road conditions, continuously analyzing their first computes the route without taking into account reports of traffic and the second traffic route with regard to received messages about road conditions. If the comparison of the first route with the second shows that the second route is supposedly faster than the first route, the second route is the route information to the output device of the navigation system and navigation support of the motion of a ground vehicle to the destination is performed by the second route is that.

With this approach, which is also called automatic dynamic, with every change in road conditions calculates an alternative route and further navigational support of motion to the destination is carried out automatically based on the new route.

From the publication JP 07-083685 known navigation system, in which, in addition, alternatively, the first route is the second route and the driver given the choice between the first and second route. This approach to dynamization, which is hereinafter referred to as manual dynamics, the driver receives information about each change in road conditions and should actively make decisions about how to move on whether with regard to old or new traffic conditions corresponding to this setting route. In some systems, it may do so with the help of the routes.

Both of the above-described embodiments dynamization have specific advantages and disadvantages.

A key advantage of automatic dynamization is the fact that the navigation system does not unnecessarily distracting the driver and allows the driver to fully concentrate on the traffic. The disadvantage is that the driver is unlikely to affect navigation. Thus, the alternative route is t used even in the case if he does not give a noticeable gain, in comparison with the old route, or if the source of the message traffic conditions (e.g., RDS-TMC, Mcrgo or HMM-TMS) is classified as less reliable.

When manual dynamization of the driver due to the possibility of active participation in navigation gets the advantage that, depending on the subjective assessment of changes in the route it can be used for further navigation support old or an alternative route. The disadvantage is that the driver of the vehicle at each change of background information about the road condition is actively involved in the selection of the route and thus distracted from their main task - active participation in traffic.

Thus, one advantage of this method is the lack of the other. On the one hand, both advantages very user-friendly, on the other hand, both lack quite problematic.

In the publication EP 0838797 B1 describes the manual option dynamization facilitate route selection by the user in the sense that it offers directions for both routes, and selecting one of the two routes is carried out by following one of the rules, i.e. by conclusive action.

The invention having the features of independent claims invented the I, this has the advantage that it combines the advantages of both the above approaches, i.e. automatic and manual dynamization, and simultaneously away from the disadvantages of both methods.

To do this, in the process of routing destination for navigation support of the motion of the vehicle to the destination, including the first route based on the road conditions, determining a second route to reflect changes in the traffic conditions, the definition of the measure of the impact of changes in road conditions on the route, the user is prompted for further navigational support both route choice only if the specified measure of the impact exceeds the first threshold value set by the user.

Thus, the burden of route choice lies with the user only if due to changes in road conditions most favorable to the new conditions, the route leads along the original route to a significant change in the route, in particular to the deterioration of the route, for example to make a big hook.

If the measure of impact does not exceed the first threshold value, then one of two routes, it is expedient to assign to the next navigational support automatically. This allows for small differences show the oil routes when replacing the first route second, so, when a small route change, not to burden the user's choice of route.

If the measure of influence is less than zero, i.e. when there is a better route, for example, you receive a shorter route, such as reducing the intensity of the traffic conditions or for other reasons, it is advisable to automatically choose the second route, i.e. to carry out automatic dynamic, without entering into a dialogue with the user.

In a preferred embodiment of the invention by comparing predicted on the basis of the second road conditions results follow the second route, the first route will determine the gains from changing the route, in particular, the gain in time of the movement, and automatically choose the second route, if the gains from changing the route exceeds the second threshold value, and measure the impact does not exceed the first threshold value.

In a preferred embodiment of the invention by comparing predicted on the basis of the second road conditions results follow the second route, the first route will determine the gains from changing the route and automatically choose the first route, if the measure of influence is not above the first threshold and not lower than the third threshold, and if the gain of the ISM is in route does not exceed the second threshold value. Above the third threshold value may be less than or equal to zero.

To support the user selecting one of the routes that can be offered for selection, the user appropriate output effects associated with the alternative route, in particular the above-mentioned measure of influence, or the difference between the metrics of the routes when replacing the first route, the second, and preferable, and the gains from changing the route from the first to the second, in this case especially, the gain in time of the movement. Instead, or additionally it may be possible output of the respective characterizing the route parameters, in particular parameters on the basis of which was determined above measure of influence, such as path length, and, for example, the gain in time of movement in relation to offered a choice of routes.

As described above, the threshold value or threshold value on the basis of which the decision to perform automatic or manual dynamization or not dynamization may be set manually by the user. Thus, the behavior of the system, given the factory setting, can be adapted to the preferences of a specific user. In a preferred embodiment of the invention the threshold value or threshold value automatic is Eski adjusted on the basis of behavior of the user when the navigation system automatically. To this end user decisions in cases where his choice of two routes, subjected to statistical evaluation.

The object of the invention is also a device for implementing the method of the destination of the route for navigation support of the motion of the vehicle to the destination, containing:

means for determining a first route based on the road conditions and to determine a second route to reflect changes in road conditions,

means for determining a measure of the influence of changes in the traffic on the route

- a decision making tool for deciding whether the specified measure the impact of the first threshold value set by the user, and

- output to supply the user with two routes to choose from for further navigational support in case of exceeding the measure of influence of the first threshold value.

Below the invention is explained in more detail with examples of its implementation:

in Fig. 1 is a structural diagram of a device for carrying out the invention method,

in Fig. 2 - part of the road network,

in Fig. 3 is another fragment of the road network,

figure 4 is a first diagram

figure 5 is a second diagram and

figure 6 is a third diagram.

The implementation of the invention

Figure 1 p is the position 1 labeled proposed in the invention, the device for carrying out the invention method. Thus in this case, as an example, and without limiting the generality of the invention, a navigation device, which, in particular, is for temporary or long-term use on the vehicle.

The navigation device 1 includes, as is well known, the means 11 for determining its own location, and therefore to determine the current location of a vehicle, for example a receiver of signals from satellites of the global positioning system GPS, preferably an additional inertial sensors and other similar media, and on the basis of the combination of these signals is determined by the current in a given time location. Using the remote control 12, preferably with the controls, the user can enter the destination. Then the module 13 calculation of the route, which is preferably a software module executing in the processor of the Central unit 10 controls the navigation system 1, calculates a route from the current vehicle location to the entered destination, passing through the road network represented by the map data stored in the external storage device 14 large capacity. This route is stored in memory 18 routes. With this, the calc is lenii route data on traffic problems distributed, for example, radio messages about road conditions (TMC messages). from the English. Traffic Message Channel) and received by the receiver 15. Accounting messages about road conditions or, more precisely, they contain events related to traffic conditions, preferably implemented event - and scale-dependent correction assigned to the elements of the road network weights, such as travel times, speeds, etc. Calculated route is the basis for the subsequent navigation tracking movement of the vehicle to the destination, whereby during movement of the vehicle's current location is tracked and mapped to the line of route, and as necessary are generated guidance route, and these instructions are issued by the device 16 output, for example, acoustically using synthesized speech.

When the change in road conditions in that the navigation device 1 is triggered to recalculate the route. Under traffic conditions is a set of available messages about road conditions, which are preferably stored in the memory 17 of the navigation device. These messages about traffic can be received by radio messages about road conditions, for example the so-called TMC (with the cu. from the English. Traffic Message channel traffic message) ISO 14819. However, changing road conditions defined in the additional message traffic received, for example, by a radio receiver 15 or otherwise, and such messages may still be missing in the memory 17, or can transmit information about the disappearance or weakening of existing still have traffic problems, the so-called leaving messages (below the description text leaving messages include messages about the weakening of the existing traffic problems), or as a result of the termination of obtaining some available in the memory 17 messages about road conditions. Thus, under the traffic situation in this case is a set available in the navigation device messages about traffic problems, i.e. information traffic conditions, which may differ from the actual road conditions, because the messages about road conditions do not always reflect the most recent changes, either because of these messages may not be received by the radio receiver 15, or for other reasons.

Figure 2 number 1 indicates as a navigation device of the vehicle, i.e. the location of the vehicle on which the navigation device is expluatiruesh. Based on the first traffic conditions navigational instrument was calculated first route R1 passing through the sections 21, 22 and 23. After calculation of the route was received new message about road conditions, which indicated the presence of difficulties 27 traffic route 22, such as a tube or other events that adversely affect traffic flow. As a result of receiving this new message about road conditions and the coming to him of a new second road conditions calculated new, the second route R2.

The changed situation presented in figure 3. Here also the number 1 indicates as a navigation device of the vehicle, i.e. the location of the vehicle on which the navigation device is operated. The current time route is the one that was calculated based on the changed road conditions, shown in figure 2, i.e. the second route R2. Over time again, a new traffic associated with the disappearance of the difficulties 27 movement, as reported, for example, leaving a message that is received by the receiver 15. The result of the receipt of the revocation message is that the resistance of the section 22 of the road again decreased to its initial value. In response to the emergence of a new road on the stop again is recalculating the route, which as the optimal route is created the third route R3, which corresponds to the first route R1. Thus, the change in road conditions can occur both when new, additional traffic problems, and with the disappearance of the traffic problems that existed before.

The device 10 controls the navigation device contains judging module 101 to assess differences between the original route R1 and the alternative route R2.

On the basis of indicators of the old route R1 and a new route R2 is determined by the difference TDV indicators routes when replacing the first route second, and preferably win TTA from route changes, in particular, the gain in time of movement.

The difference TDV indicators routes when replacing the first route, the second describes the difference between the old, the first route R1, which was calculated on the basis of the first road conditions, i.e. was laid to changes in road conditions, and alternatively, the second route R2, which was determined based on the changed second road conditions (figure 2). Thus, this difference is a measure of the impact of the new traffic conditions on the route itself. Corresponding to the optimization criterion ways, for example, a route with a higher speed, crutch ISI route, the optimal route, the most advantageous fuel consumption, route, etc. for this abstract is estimated resistance. The difference metrics of routes when replacing the first route, the second may take a positive value, which corresponds to the deterioration of the route from the point of view of the considered criterion, for example, lengthening of a new route R2 compared to the old route R1 (figure 2). The difference metrics of routes when replacing the first route, the second can also take negative values, which corresponds to positive effect, such as reducing new route R3 compared to the old route R2 (figure 3).

Win TTA from changes in the route, in contrast, describes the advantage, in case of winning in a time-movement - temporary advantage, a new alternative route R2 compared to the old route R1, and in both cases the basis of a new, second traffic (figure 2). Thus, the parameter TTA is a measure of the appropriateness of the choice of an alternative route R2 against the original route R1. However, the gain in time movement when new messages about road conditions on the route can only be greater or equal to zero, as in the case of dynamization possible alternative route should always be equivalent to the original mA is the route with obstruction or better, than he, otherwise, the alternative route is not installed.

A more accurate analysis of the reasons underlying the advantages and disadvantages of methods of dynamization, indicates the direction of development of the method, which combines the advantages of the known methods and eliminates their disadvantages.

In the case of the well-known "manual dynamization"described above, when the high frequency changes in the current traffic information, i.e. rapid changes in road conditions, continuous querying driver on selecting the appropriate route often interfere with the lead vehicle. However, these requests are of great interest when an alternative route is significantly worse compared to the original, i.e. the difference between the metrics of the routes when replacing the first route, the second is above a first threshold 31 (figure 4 and 6). With the improvements of the route, for example due to the receipt of the revocation message or cancel message traffic conditions, i.e. when the difference of the indices of routes when replacing the first route, the second is less than zero or smaller than a third threshold value 33, which is less than zero, the request of the driver in relation to the dynamization should not be.

In some cases, the calculated alternative route give the em only very small and hardly noticeable advantage compared to the old route, gains from changes of the route is very small, i.e. less than a second threshold value 32 (figure 5 and 6). For example, the driver must exit the autobahn (highway) or the Federal highway and to avoid obstruction of traffic on country roads and local roads. This kind of alternative, giving a very small win TTA in time movements, often causes misunderstanding and rejection. So in this case it is preferable not to perform the dynamic setting, undesirable and prompt the user about it.

Both these aspects are independent from each other and can be correlated, as shown in Fig.6. Improvements of the route, i.e. the cases when the difference TDV is less than zero, can only take place when the cancel message traffic conditions. However, depending on particular criteria, for example the criterion of "best route", which is a combination of the criteria of "shortest route" and "fastest route", you may encounter a special situation when the gain in time will be equal in magnitude component of the movement of time in the resistance, determining the difference between the metrics of routes when replacing the first route second. Therefore, even if a small difference TDV indicators routes, less the first threshold 31 and most of the third peregovorochnaya 33, when receiving the revocation message dynamism in this case should not be implemented.

In accordance with the invention, the user request is performed only when the second route R2 would mean a deterioration of the route compared with the first route R1, i.e. when the difference between TDV, most of the first threshold 31 (area 41 figure 6). Next, consider as an example the preferred embodiment of the invention, if the difference between the metrics of the routes when replacing the first route, the second does not exceed the first threshold value 31, one of the two routes R1 or R2 is selected automatically. Because the user is no longer prompted by the system for every small occasion, he is less distracted from monitoring the situation on the road, but in the case of significant changes in the traffic behind it is still possible to influence route selection.

In summary, the user can choose the first route R1 and the second route R2 only if the difference TDV indicators routes when replacing the first route, the second exceeds the first threshold value 31 (manual dynamics, i.e. the dynamics, it is only performed after the interaction or dialogue with the user), otherwise, if the difference TDV indicators routes when replacing the first route is which does not exceed the first threshold value 31, one of the two routes is automatically selected.

Further, it is preferable to provide a variant of the invention, which also takes into account the gains from changing the route, in particular in the form of winnings TTA in time movements. The second threshold value 32 determines the minimum gain in time of the movement from which should happen automatically dynamics. Thus, in those cases when the difference TDV indicators routes when replacing the first route, the second does not exceed the first threshold value 31, should be done in the following steps:

a) if the winning TTA in time of the movement exceeds the second threshold value 32, automatically selects the second route R2 (automatic dynamics, i.e. the dynamics without user interaction);

b) if the winning TTA at the time the motion is not above the second threshold value 32, and the difference TDV indicators routes when replacing the first route, the second is not below the threshold value 33, based on the discussed preferred variant embodiment of the invention automatically selects the first route R1 (no dynamization) and

C) if the winning TTA at the time the motion is not above the second threshold value 32, and the difference TDV indicators routes when replacing the first route, the second is less than zero or below the third is ogopogo value 33, according to the considered preferred variant embodiment of the invention automatically selects the second route R2 (automatic dynamic).

With a small win from TTA route changes, but big changes TDV route manual dynamization is also preferred over a full block dynamization of considerations that messages about road conditions may not be wholly reliable or cannot accurately predict their impact on traffic flow, and hence the movement. In this case, the user is given the opportunity to decide in favor of one or another route on the basis of possible past experience movement on the respective parts of the route or of other preferences, such as the desire to avoid known venue for large-scale road works on one of the routes, etc.

On the basis of figure 2 the situation with routes, you can build the following example, the difference in index of routes when replacing the first route, the second is considered on the basis of distance, and the gains from change of route - a time-based movement (travel time).

Depending on the set threshold value, the navigation system may behave differently. While the loss when replacing the first route, the second in the form of a difference of indices of these routes lies below the threshold 31 (TDV_threshold.), a query against a dynamization is not possible, what happens when the threshold value TDV_threshold.=+20. If the threshold is so low that the difference in index of routes when replacing the first route, the second lies above it, for example TDV_threshold.=+5, then the user is prompted regarding the use of the old route R1 or a new route R2.

In the case when the loss is for the well of the first route, the second in the form of a difference TDV indicators of these routes does not exceed the threshold value 31, direct dynamics is carried out only if the winning TTA at the time the motion is above a predetermined minimum winning TTA_threshold. in time movements. In the example shown the direct dynamics occurs only in case, if the threshold TTA_threshold. the memory was recorded value less than or equal to 0:05.

In the case of the disappearance of the traffic we get the following picture.

Due to the improved route is that users are not prompted about dynamization, and the decision is made on the basis of time savings movement. Depending on the correlation time of the motion and the threshold gain in time motion dynamics is carried out or not.

In the preferred private embodiment of the invention the threshold value, resulting in the interaction of the system with the user, automatically adapt to user behavior. In this case, the navigation system "learns" new thresholds automatically. To this end, the dynamization requiring confirmation from the user, determines the tendency to reject or confirm the user of the proposals using the threshold value.

Both routes R1 and R2 or R2 and R3, offer the user the choice, it is advisable to display on the display 19 of the navigation device 1, preferably laid on the map. On this map it is sensible to display existing reports of traffic problems on both routes R1 and R2, in the case of figure 2 - a message about the difficulty 27 movement. Then the routing can be done by clicking on the body of the control device 12 controls.

In another embodiment, it is also possible to envisage known from EP 0838797 B1 issuance of alternative directions for both routes R1 and R2, indicating that, according to the mu of the routes will continue the movement by following a certain instruction, for example: "To choose the former route, go straight and follow through A6. To select an alternative route, again calculated on the basis of a new message on the road, near the junction, take the A5 towards Karlsruhe and follow A5", and in this case one of the routes is selected by further movement in accordance with one of the instructions relating to one of the routes.

1. The way to the destination of the route for navigation support of the motion of the vehicle to the destination, including the first route (R1) on the basis of the traffic conditions, determining the second route (R2) to reflect changes in the traffic conditions, the definition of the measure of the impact of changes in road conditions on the route, and the user is prompted for further navigational support both routes (Rl, R2) only if the specified measure (TDV) the impact exceeds a first threshold value (31)defined by the user.

2. The method according to claim 1, characterized in that if the measure (TDV) the impact does not exceed the first threshold value (31), one of the two routes (Rl, R2) is indicated for subsequent navigation support automatically.

3. The method according to claim 1, characterized in that the second route (R2) designate automatically if the measure (TDV) influence of men is above zero.

4. The method according to claim 1, characterized in that on the basis of comparison of predicted based on the second road conditions results follow the second route (R2) and on the first route (R1) define win (TTA) from route changes, in particular, the gain in time of the movement, and automatically assign the second route (R2), if win (TTA) from the change of the route exceeds the second threshold value (32), and measure (TDV) the impact does not exceed the first threshold value (31).

5. The method according to claim 1, characterized in that on the basis of comparison of predicted based on the second road conditions results follow the second route (R2) and on the first route (R1) define win (TTA) from route changes and automatically select the first route (R1), if the measure (TDV) influence is not above the first threshold value (31) and not lower than the third threshold (33), and if you win (TTA) from changes in the route does not exceed the second threshold value (32).

6. The method according to claim 5, characterized in that the third threshold value (33) is zero.

7. The method according to claim 1, characterized in that for supporting a user selecting one of the proposed routes (Rl, R2) user output measure (TDV) influence, and preferably, and win (TTA) from route changes.

8. The method according to one of paragraphs. 1-7, characterized in that the first, and if you want the tees, other threshold values are automatically adapt to user behavior.

9. The device (1) for implementing the method of the destination of the route for navigation tracking movement of a vehicle to a destination, comprising:
- means (13) for determining the first route (R1) on the basis of the traffic conditions and to determine a second route (R2) to reflect changes in road conditions,
- means (101) for determining measures of the impact of changes in road conditions on the route,
- means (101) of the decision tree for deciding whether the specified measure (TDV) the influence of the first threshold value (31)defined by the user, and
- means (16, 19) o offers the user two routes (Rl, R2) for further navigational support in case of exceeding the measure of influence of the first threshold value (31).