D * algorithm

from Wikipedia, the free encyclopedia

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

Procedure

Initial expansion

As with A *, the route from the start to the destination is first chosen for D *. In contrast to A *, the order is reversed: from the finish to the start. This has the advantage that each expanded node refers to the next node leading to the destination and knows the exact costs to the destination (after the expansion).

Depending on whether a focussing metric is used for support and whether it is canceled after the starting point has been found, more or fewer points are expanded and are therefore available later as support. The expansion is analogous to A *. If the start node is expanded, the algorithm can be canceled. The OpenList must not be emptied.

  • ongoing expansion

  • completed expansion

A blockage occurs

As soon as a blockage occurs, all items that are affected are added back to the OpenList. However, they are marked as raise points (orange points on the map). However, before a raise point passes the cost increase on to its follow-up points, it checks whether there is a point in its neighborhood that can reduce its costs. A raise wave now runs through all affected points. This wave is followed by a lower wave (green dots), insofar as there is one. Lower points are points that spread a reduction in costs. In this example, the point on the far right has the option of leading to the destination via an alternative neighbor. From now on it is a lower state and follows the raise wave. This is the heart of the D *. This point prevents a whole series of other points from having to be “touched” at all. Only those points are processed that are actually affected by the cost change.

  • Blockage entered and affected points marked

  • ongoing expansion

Another blockage occurs

This time the blockage cannot be circumvented so elegantly. None of the points can find a new route to the destination via a neighbor. That is why they continue to propagate their cost increase. Only outside of the channel can points be found that provide a route to the destination. Here two lower waves are created, which expand points marked as unreachable with new route information.

  • Passage closed

  • expansion

  • New route found

The algorithm

while(openList.nichtLeer())
{
  punkt = openList.erstesElement();
  expandiere(punkt);
}

Function: expand

  void expandiere(aktuellerPunkt)
  {
   boolean istRaise = istRaise(aktuellerPunkt);
   double kosten;
   foreach(nachbar in aktuellerPunkt.getNachbarn())
   {
    if(istRaise)
    {
     if(nachbar.nächsterPunkt == aktuellerPunkt)
     {
      nachbar.setztNächstenPunktUndAktualisiereKosten(aktuellerPunkt);
      openList.hinzufüge(nachbar);
     }
     else
     {
      kosten = nachbar.berechneKostenÜber(aktuellerPunkt);
      if(kosten < nachbar.getKosten())
      {
       aktuellerPunkt.minimaleKostenAufAktuelleKostenSetzen();
       openList.hinzufügen(aktuellerPunkt);
      }
     }
    }
    else
    {
      kosten=nachbar.berechneKostenÜber(aktuellerPunkt);
      if(kosten < nachbar.getKosten())
      {
       nachbar.setztNächstenPunktUndAktualisiereKosten(aktuellerPunkt);
       openList.hinzufüge(nachbar);
      }
    }
   }
  }

Checking whether there is a raise 

boolean istRaise(punkt)
{
 double kosten;
 if(punkt.getAktuelleKosten() > punkt.getMinimaleKosten())
 {
  foreach(nachbar in punkt.getNachbarn())
  {
   kosten = punkt.berechneKostenÜber(nachbar);
   if(kosten < punkt.getAktuelleKosten())
   {
    punkt.setztNächstenPunktUndAktualisiereKosten(nachbar);
   }
  }
 }
 return punkt.getAktuelleKosten() > punkt.getMinimaleKosten();
}

The algorithm in words

All known points are noted on the OpenList. At the beginning this is just the end point. As long as there are points on the OpenList, the first point is always removed from the OpenList and expanded.

Expansion of points

First it is decided whether the point to be expanded is in the raise state or not (and thus automatically in the lower state). If there is a lower state, the procedure is analogous to A *. All neighbors are examined to see whether they can be reached more easily from the current point than before. If this is the case, the current point becomes the predecessor of the neighbor, its costs are recalculated and this is added to the OpenList. If there is a raise status, the costs are immediately passed on to all neighbors who can find the goal via the current point. For all other points it is checked whether the current point could represent a cost reduction. If so, the minimum costs of the current point are set to its current costs (it becomes the lower state) and put back into the OpenList in order to propagate its cost optimization during the next expansion.

Lower / raise decision

The decision as to whether there is a raise or a lower state is made on the basis of the current and minimum costs. If the current path costs are greater than the minimum, there is a raise state. Before this cost increase is passed on, however, it is checked whether there is a point in the neighborhood that could lower the cost of the current point. If there is such a point, it is set as the new predecessor and the costs are recalculated. If all neighbors have been checked, it is checked again whether the minimum costs correspond to the current costs. If this is the case, there is now a lower state, otherwise it remains a raise and the costs are propagated.

Minimal cost / current cost

With D * it is important to distinguish between current and minimum costs. The former are only of interest at the time of the survey, the latter are critical because the OpenList is sorted according to them. The function of the minimum costs always provides the lowest costs that the item has had since its first "addition" to the OpenList. When adding a blockage, make sure that this function returns a lower value than the current cost of the point.

optimization

The D * algorithm described so far does not work optimally. The following measures either cost a lot of programming effort or have negative effects, so you have to weigh up the implementation.

The OpenList

The implementation of the OpenList has the greatest impact on the runtime of the algorithm. A running time of over 10 seconds (simple static array) can be reduced to less than 100 ms (balanced tree) without further ado, so that a lot of effort is worthwhile here. However, optimization is not as easy as with A *. A balanced tree is not the optimal solution, or D * does not work with a normal balanced tree. It requires at least one balanced tree that can handle the fact that two objects have the same numerical value but are not the same. In addition, he must be able to pick out a special one among several identical objects. The standard implementations under Java or .NET cannot.
Even if you use such a B-tree, this may be suboptimal. During the first expansion phase, no raise conditions occur. The OpenList is filled "in the back third" and emptied from the front. The tree builds up continuously until it has reached its maximum size (the Lower wave has the largest extent) and then continuously decreases again. When a blockage expands, there are frequent changes in the minimum costs (up and down) during transitions from raise to lower waves. In order for the element to be found in the tree, it has to be removed or otherwise marked and then reinserted or rearranged, which, depending on the implementation and frequency of these changes, can lead to an extreme slowdown. Different data structures for lower and raise can help here or use a completely different memory / access structure.

Check points

The D * algorithm as described here has a problem with points becoming unreachable. If an additional blockade completely excludes any area from expansion, it does not terminate. The problem lies in the raise method. Before checking whether there is a raise condition, an attempt is made to find a neighbor who offers lower costs. In the case of a neighbor of a blockade, this is every point except the blockade itself. The raise point "links" to a neighbor, only to be pulled up again in the next expansion by this neighbor, in order to become a raise state again . This ends in a loop in which the cost of the points is pulled up. There are two ways to counter this problem:

  • Fixed upper limit: You set an upper limit from which a point is considered "inaccessible" and no neighbor may serve as a route to the destination. So the loop would ebb at this limit. However, this method is bungled and the second variant offers further optimization options later.
  • A validity check: Before a point in the raise check is made a predecessor, it is subjected to a validity check. This checks whether the point leads into a loop in which OpenList is, has no predecessor (this may only be the end point), is marked as unreachable or blocked. If one of these four cases is present, the point is ignored. You can take this test from the desired point to the end point, but it takes time. To prevent endless loops, however, it is sufficient to check the next 2 points.

Focusing metric

So far, no statement has been made about the metric used . A "jump" metric was used in the sample images. As a result, all points are treated equally and a circular expansion is made. A focusing metric, like the A * for geographic problems, would be the number of jumps from the point to the destination plus the beeline between the point and the start. This metric always expands around the last known optimal path or towards the starting point. The metric should always be quick to calculate and must always underestimate the actual costs, otherwise errors will occur. In contrast to A *, D * can be irreparably damaged by this so that no route to the destination can be found.

"Solid as a rock"

"Solid as a Rock"

One problem associated with focusing metrics, however, is spontaneous lower / raise waves on the outside of the map. In the picture opposite you can see a wave of raises (red). Due to the focussing property of the metric, this is strongly pulled in one direction, so that its lateral expansion is rather small. Point A is expanded first. However, since its predecessors have not yet been captured by the raise wave, it is considered valid and offers its costs. A lower wave arises. This phenomenon can only occur when points that are far away from the target point are expanded rather than points that are closer to the target point. A point that is actually "invalid" or is at least changed later by a raise wave is used as a new target-oriented neighbor during a raise check. As a result, the raise point goes into the lower state, since it can improve all points in the vicinity with its path costs. Now lower waves pulsate followed by raise waves in the vicinity of this point until a final lower / raise wave finally propagates the correct distance costs.
This problem can only be contained to a limited extent. The advantage of a focused metric is too great to be disturbed by such "effects" in the edge area. The problem can only be addressed to a limited extent via the validity check. Even when scanning from the presumed point to the target point, such a constellation can still arise. In addition, such a high scanning depth would result in extreme increases in runtime.
Heuristic: With an N * N matrix, a scanning depth of N / 20 suppresses most of these effects in the first 2/3 of the points to be expanded.

Termination conditions

The time saved is also increased by a premature termination, especially with a focusing metric. As with A *, the algorithm can be aborted as soon as the starting point is expanded and - this is D * -specific - it is in the Lower state (only applies to a clean implementation). In the event of a termination, the OpenList must not be emptied, as otherwise not all ways to bypass it are known if a blockage occurs.
In contrast to A *, a premature termination also wastes potential. D * benefits from knowing as many alternative routes as possible in order to restore them to a valid status as quickly as possible. However, if one always terminates as soon as one has found the optimal path, D * converges more slowly in the event of an error (but still faster than A *).

Multithreading

The question of canceling is superfluous as soon as you can fall back on a multithreading-capable platform. Usually the D * algorithm is not programmed and used without a deeper meaning (except for academic purposes). It is used to control robots / agents or entire swarms. It usually takes time for these devices to start up. This is where multithreading comes in. The D * algorithm is started first. Instead of blocking program execution as before, however, the calculation is outsourced to a single thread, which is assigned the highest priority. This should ensure that almost all other threads are blocked and only the route is calculated. As soon as the algorithm has reached the point at which it would normally be terminated (initial expansion of the starting point), all threads that may be waiting are informed that the route is now available. At the same time you take the thread from the CPU and put it back in, but this time with the lowest priority. Any excess computing power is used to expand the card further. As a rule, the excess computing power is sufficient to have the card fully expanded until the agent is ready for use.
The same applies to the calculation of blockages. Here the calling thread is blocked until the calculating thread has found a new route, after which the map is expanded further while the agent receives new commands.

Web links