D*

D * - algorithm is an extension of the A * algorithm, and thus a direct " descendant " of the Dijkstra algorithm. Both A * as well as the Dijkstra's algorithm are inflexible in their basic form, and may not react to changes in the graph, during or after expansion. In both cases, the user can discard all the results and start over again. Especially when working with robots or agents under real conditions (limited sensor range, unfamiliar environment ), it happens that large maps are constantly updated. Anthony Stentz developed a way to A * to modify so that it works with the new requirements at Carnegie Mellon University.

• 2.1 Function: expand
• 2.2 Check whether Raise exists

• 3.1 Expansion of points
• 3.2 Lower / Raise decision

• 5.1 The Open List
• 5.2 Check points
• 5.3 Focusing metric
• 5.4 " The rock in the surf "
• 5.5 termination conditions
• 5.6 multithreading

Procedure

Initial expansion

As with A * first *, the path from start to the destination is selected even when D. Unlike A *, however, the order is reversed: from the target to start. This has the advantage that each expanded node points to the next leading to the destination node, and the exact cost of the target ( after expansion ) knows.

Depending on whether a focusing metric is used to support and whether is canceled after finding the starting point, points are more or less expanded and are therefore later than willing support. The expansion is analogous to A *. If the start node is expanded, the algorithm can be terminated. The Open List must not be emptied.

Completed expansion

A blockage occurs

When a blockage occurs, all points that are affected by it, added back in the Open List. However, they will raise as points marked ( orange dots on the map ). However, before a Raise - point passes on the cost increase on to their daughter products, it checks whether there is a point in its neighborhood, which can reduce its costs. Now Raise a wave passes through all relevant points. This wave is followed by a lower- wave (green dots ), in that there is such. Lower points are points that distribute a cost reduction. In this example, the point on the far right has the opportunity to lead via an alternative neighbor to the destination. He now represents a lower- status and puts behind the Raise shaft. This is the heart of the D *. By this point will prevent a number of other points ever need to be "handled ". It only edit the points that are actually affected by the change in cost.

Ongoing expansion

Another blockade occurs

This time, the blockage can not be as elegant round. None of the points on a neighbor find a new route to the destination. Therefore, they propagate their costs increase further. Only outside the channel can be found points that provide a route to the destination. This is where two lower- waves that expand as unattainable points marked with a new route information.

Expansion

New route found

The algorithm

While ( openList.nichtLeer ()) {    point = openList.erstesElement ();    expanding (dot); } Function: expand

Void expanding ( aktuellerPunkt )    {     boolean istRaise = istRaise ( aktuellerPunkt );     double cost;     foreach ( neighbor in aktuellerPunkt.getNachbarn ())     {      if ( istRaise )      {       if ( nachbar.nächsterPunkt == aktuellerPunkt )       {        nachbar.setztNächstenPunktUndAktualisiereKosten ( aktuellerPunkt );        openList.hinzufüge ( neighbor );       }       else       {        cost = nachbar.berechneKostenÜber ( aktuellerPunkt );        if ( cost < nachbar.getKosten ())        {         aktuellerPunkt.minimaleKostenAufAktuelleKostenSetzen ();         openList.hinzufügen ( aktuellerPunkt );        }       }      }      else      {        cost = nachbar.berechneKostenÜber ( aktuellerPunkt );        if ( cost < nachbar.getKosten ())        {         nachbar.setztNächstenPunktUndAktualisiereKosten ( aktuellerPunkt );         openList.hinzufüge ( neighbor );        }      }     }    } Checking whether Raise exists

Boolean istRaise (dot) {   double cost;   if ( punkt.getAktuelleKosten () > punkt.getMinimaleKosten ())   {    foreach ( neighbor in aktuellerPunkt.getNachbarn ())    {     cost = aktuellerPunkt.berechneKostenÜber ( neighbor );     if ( cost < punkt.getAktuelleKosten ())     {      aktuellerPunkt.setztNächstenPunktUndAktualisiereKosten ( neighbor );     }    }   }   return punkt.getAktuelleKosten () > punkt.getMinimaleKosten (); } The algorithm in words

All known items are noted on the Open List. In the beginning, this is only the end point. As long as the points on the Open List, are the first point is always removed from the open list and expanded.

Expansion of points

First, it is judged whether the current point to be expanded in the raise - state or not (and therefore automatically in the lower state). If there is a lower- state procedure is similar to A *. All the neighbors are examined to see whether they can be better achieved from the current point than before. If this is the case, then the current point to the predecessor of neighbors, calculates the cost of this new and added in the Open List. If there is a raise - state, the costs are passed on immediately to all neighbors which are found on the current point to the target. For all the other points, it is checked whether the current point may be a reduction in cost. If so, the minimum cost of the current point is set to its current cost (it is thus the Lower state) and put back into the Open List to propagate its cost optimization in the next expansion.

Lower / Raise decision

The decision whether a Raise or Lower condition exists is decided on the basis of current and minimum cost. If the current is greater than the minimum path cost, there is a raise state. Before this increase in cost, however, be passed, it is checked whether there is a point in the vicinity, which could reduce the cost of the current point. If there is such a point, this is set as the new predecessor and calculates the cost of new. If all neighbors have been tested, is again checked whether the minimum cost is the actual cost. If this is the case, now there is a lower state, otherwise it is a raise the cost and be propagated.

Minimum cost / actual cost

At D *, it is important to distinguish between actual and minimum cost. The former interest only at the time of the survey, last are critical, because according to them the Open List is sorted. The function always returns the minimum cost while the lowest cost, which was the point since his first " addition " to the Open List. When you add a blockade is to make sure that this function has a lower value than the current cost of the item.

Optimization

The previously described D * algorithm will not work optimally. The following measures cost either too much effort or have adverse effects, therefore, is to make an assessment in the implementation.

The Open List

The implementation of the Open List has the greatest impact on the running time of the algorithm. There may be a period of about 10 sec ( simple static array ) can be reduced to less than 100 ms ( Balanced Tree) readily, so here is worth much effort. However, the optimization is not as easy as A *. A balanced tree is not the optimal solution, or with a normal balanced tree does not D *. It requires at least a balanced tree that can handle the fact that two objects have the same numerical value, however, are not equal. He must also be able to pick out a special among several identical objects. The default implementations in Java or. NET can not. Even if one uses as a B- tree, this is suboptimal. During the first expansion phase, no Raise states occur. The Open List is filled " in the rear third " and emptied from the front. The tree continuously builds up until it reaches its maximum size ( the Lower - wave has the largest dimension) and then back continuously. When expanding a blockage occurs (up and down ) at transitions of raise -to lower- waves to frequent changes in the minimum cost. This item can be found in the tree, it must be marked and are then inserted or rearranged again, which may result in a massive reduction depending on the implementation and frequency of those changes removed or otherwise. Different data structures for Lower and Raise can remedy this situation or equal to use a completely different storage / access structure.

Check points

The D * algorithm, as described here, has a problem with becoming inaccessible points. Includes a adventitious blockade any area completely from the expansion of, he does not terminate. The problem lies in the Raise method. Before checking whether a raise condition is present, it will try to find a neighbor who offers the lowest cost. When a neighbor of a blockade that is, every point except the blockade itself Raise The Point " is linking " to a neighbor, only to be in the next expansion by these neighbors pulled back up to once again to become the Raise - state. Which terminates in a loop in which the cost of the items are drawn upwards. One can encounter this problem with two options:

• Fixed upper limit: It establishes a ceiling above which a point is considered " unreachable " and no neighbors may serve as a route to the destination. So the loop would die down at this boundary. This method, however clumsily, and the second option offers even more later optimizing capability.
• A validity check: Before a point is made ​​at check - raise to its predecessor, it goes through a validation process. This checks whether the point results in a loop is in the open list, has no predecessor (which may only be the end point ) is marked as unreachable or blockage. There is one of these four cases, the point is ignored. You can drive this exam from the desired point to the end point, but that takes time. To prevent infinite loops, however, is sufficient to consider the next two points.

Focusing metric

Up to now, been made ​​on the metric used no statement. In the example images, a " jump" metric was used. This means that all points are treated equally and a circular expansion is made. A focusing metric would be, as in A * for geographical problems, the number of jumps from point to destination plus the air line between the point and the start. By this metric is always expands to the last known or optimal path to the starting point. The metric should be calculated quickly and always must always underestimate the actual cost, otherwise there will be errors. In contrast to A * D * can be irreparably damaged by this so that no route is found to the destination.

" The rock in the surf "

A problem that goes hand in hand with focusing metrics are spontaneous Lower / Raise waves in the outer area of ​​the map. The picture to Raise a shaft ( red) can be seen. This is strongly pulled by the focusing property of the metric in a direction whereby their lateral extent is rather low. The point A is expanded first. As its predecessors, however, were not yet covered by the Raise wave he is regarded as valid and offers its costs. A Lower - wave. This phenomenon can only occur when points are more likely to expand at a high distance to the destination, as points that are closer to the destination point. One point that really " invalid" or changed at least later by a Raise wave is used as a new goal-oriented neighbor during a Raise checks. The Raise - point is consequently in the lower- state, since it can enhance all the points available within its path costs. Now pulsate Lower - waves followed by Raise waves in a radius around this point until a final Lower / Raise wave finally propagates the correct distance costs. This problem can be curbed only conditionally. The advantage of a focused metric is too great for that one can be bothered by such "effects" in the border area. On the validity of the test problem is only partially get at. Even with a sample from the putative point to the target point may still come about such a situation. In addition, such a high sampling depth would bring extreme runtime increases with it. Heuristic: In a N * N matrix, a sampling depth of N/20 suppresses most of these effects in the first 2 /3 of the points to be expanded.

Termination conditions

Is also amplified the gain of time by a premature termination, especially with a focusing metric. Like A *, the algorithm can be terminated as soon as the starting point is expanded and - this is D * - specific - this is in the lower- state (applies only to clean implementation). When canceling the Open List must not be empty, since otherwise not all paths to circumvention are known at a blockage occurring. Unlike A * is given away by a premature termination but also potential. D * benefited from knowing so many alternative routes as possible to bring back a valid state from these very quickly. However, one breaks from always, once you have found the optimal path converges D * in case of failure slower ( but still faster than A *).

Multithreading

The question of Abbruches not be required once you can fall back on a multithreaded platform. Normally, the D * algorithm is not programmed and used without any deeper meaning is ( except for academic purposes ). It is used for controlling robots / agents or swarms. Usually, it also takes some time before these devices are powered up. This is where the multithreading. The D * algorithm is started first. Instead of just, however, to block the program execution, the computation is outsourced to a single thread, the highest priority is assigned. This is to ensure that almost all other threads are blocked and only the route is calculated. Once the algorithm has reached the point where one would normally terminate him ( Erstexpansion the starting point ) you share with all perhaps waiting threads that the route is now available. At the same time you take the thread of the CPU and but numbered him again, this time with the lowest priority. So any excess processing power is used to expand map. In general, the excess computing power is sufficient to have the card fully expanded until the agent is ready to use. The same applies to the calculation of blockages. Here the calling thread is blocked until the thread has calculated a new route is found, then the card is further expanded, while the agent receives new orders.