D_Star 算法 介绍

D _Star einführen

Dynamic A Star
Der D_Star-Algorithmus ist ein Suchalgorithmus. Es handelt sich um eine Erweiterung des A_Star-Algorithmus.

D星算法是一个搜索算法，他可以被视作是A星算法的拓展。

A_Star als auch der Dijkstra-Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während oder nach der Expansion nicht reagieren.

A_Star以及Dijkstra的算法在其基本形式上是不灵活的，不能对扩张过程中或扩张后的图的变化做出反应。

Wie bei A_Star wird auch bei D_Star zunächst der Weg vom Start zum Ziel gewählt. Anders als bei A_Star wird jedoch die Reihenfolge umgekehrt: vom Ziel zum Start.

与A_Star 一样，D_Star 也是选择从起点到终点的路径。然而，与A_Star不同的是，顺序是相反的：从终点到起点。

Das hat den Vorteil, dass jeder expandierte Knoten auf den nächsten zum Ziel führenden Knoten verweist und die exakten Kosten zum Ziel (nach der Expansion) kennt.

这样做的好处是，每个扩展的节点都指向通往目的地的下一个节点，并知道到目的地的确切成本（扩展后）。

Wenn sich der Zustand eines Knotens in der Mitte dynamisch ändert, muss der Roboter den Weg neu planen, weshalb es sich um einen dynamischen Suchalgorithmus handelt.

当中间某节点状态有动态改变，需要重新寻路，所以才是一个动态寻路算法。

Erstellen wir eine openList und eine CloseLit.

Knoten werden mit einem der folgenden Zustände gekennzeichnet

1. NEU, d.h. es wurde noch nie auf die OPEN-Liste gesetzt
2. OPEN, d.h. sie steht derzeit auf der OPEN-Liste
3. Closed, d.h. es steht nicht mehr auf der OPEN-Liste
4. RAISE, d.h. es kostet mehr als beim letzten Mal, als es auf der OPEN-Liste stand
5. LOWER, d.h. es kostet weniger als beim letzten Mal, als es auf der OPEN-Liste stand

h>k变成了“raise”态，（h=k为lower态）

h: Der h-Wert jedes Punktes steht für die Kosten des aktuellen Knotens bis zum Endknoten, d. h. dem Zielpunkt G. Bei der ersten Suche nach dem Startknoten werden die h aller Knoten aktualisiert und auf die gleiche Weise wie beim dijkstr-Algorithmus berechnet, indem die Kosten zweier benachbarter Knoten + die Kosten des vorherigen Knotens addiert werden.

h: 每个点的h值代表当前该点，到终点，也就是目标点G的代价。第一次搜索到起点时时，所有点的h会被更新，计算方式同dijkstr算法，是用相邻两点的代价+上一个点的代价累加得到。

k: der minimale h-Wert für diesen Knoten. k wird nach der Aktualisierung des h-Wertes dieses Knotens berechnet, wenn dieser Knoten “new” ist, ist k=h; wenn dieser Punkt “open” ist, wird das aktuelle k und das new_h-Minimum genommen, wenn dieser Knoten ‘closed’, nehmen Sie das aktuelle h und new_h Minimum; zusammenfassend wird k auf ein Minimum gehalten, das die minimalen Kosten dieses Knotens zum G-Knoten in der vollständigen Graphenumgebung darstellt.

Übersetzt mit www.DeepL.com/Translator (kostenlose Version)
k: 该点最小的h值。k的计算在更新过本节点的h后，如果本点‘new’,k=h；如果本点’open’，那就取一下当前k和new_h最小值，如果本点是’closed’，取当前h和new_h最小值； 总而言之，k将会保持到最小，它表示了本点在全图环境中到G点的最小代价。

Erklärung

1. h steht für die Kosten dieses Knotens zum Endknoten, dem Zielknoten G.
2. k ist das Minimum aller h, die an diesem Knoten übergeben werden.
3. b ist der übergeordnete Knoten.(Vater Knoten)

h代表该节点到终节点，也就是目标节点G的代价。k是该节点所有过的h的最小值。b是父节点。

当机器人走到这个节点： Wenn der Roboter diesen Punkt erreicht hat，

封锁 Blockade

出现封锁 Eine Blockade tritt auf

当机器人走到这个节点： Wenn der Roboter diesen Punkt erreicht hat, tritt eine Blockade auf.

Der Roboter sucht nach Knotenpunkten in der Umgebung und findet einen Knoten, der den h-Wert senkt.

机器人会寻找周边的节点，看哪一个会降低h值。

Sobald dieser Punkt gefunden wurde, ist es der neue Vater Knoten.Der Pfeil zeigt auf diesen neuen Knoten.箭头会指向这个新的节点

Endgültige Pfadplanung