LPA * einführen

LPA-Algorithmus—Vollständiger Name Lifelong Planning A Algorithmus.

Es handelt sich um einen verbesserten A*-Algorithmus. Es wird verwendet, um das Kürzeste-Weg-Problem von einem gegebenen Startpunkt zu einem gegebenen Zielpunkt in einer dynamischen Umgebung zu behandeln.

Symbolische Darstellung

1. S: Die Menge der Pfadknoten in der Karte, s(Knoten) gehört zu S
2. succ(s): Nachfolger, die Menge der nachfolgenden Knoten von Knoten s, zB Knoten 1, 2, 3…i wurden der Reihe nach durchsucht, dann gehören alle Knoten außer 1~i zu succ(i).
3. pred(s): Vorgänger, die Vorgänger von Knoten s, haben die entgegengesetzte Bedeutung von succ(s).
4. c(s,s`): Die Kostenfunktion zwischen zwei Knoten.
5. g*(s): Die tatsächliche kürzeste Entfernung vom Knoten s zum Startpunkt Sstart.
6. g(s): Die geschätzte kürzeste Entfernung vom Knoten s zum Startpunkt. Dieser Wert ist ein geschätzter Wert, der sich mit dem Lösungsprozess des Algorithmus ständig ändert. Wenn g(s) von allen Knoten = rhs(s),ist der Wert von g(s) die tatsächliche kürzeste Entfernung zum Startpunkt, dh g(s)=g*(s).
7. rhs(s): rechte Seiten. Für alle benachbarten Knoten von s,berechnen wir ihren Abstand zu s plus den g-Wert des benachbarten Knotens selbst, und der kleinste Wert wird als rhs-Wert von s verwendet.
   
8. U ist die Prioritätswarteschlange, die nach dem Schlüsselwert jedes Knotens sortiert ist.
9. key[K1,K2]: Der Schlüsselwert, nach dem die Prioritätswarteschlange sortiert wird. Sie besteht aus zwei Teilen, K1 und K2. K1 wird zuerst verglichen, und wenn sie gleich sind, wird K2 für die Sortierung verglichen. K1 entspricht f(s) in A, K2 entspricht g(s) in A, und die Berechnungsmethoden von K1 und K2 sind in der folgenden Abbildung dargestellt.
   
10. h(s) Geschätzte Entfernung zum Zielpunkt

Es gibt insgesamt drei Zustände von Knoten: lokal konsistent g(s)=rhs(s), lokal überkonsistent g(s) > rhs(s), lokal unterkonsistent g(s) < rhs(s)

die Schritte

Initialisierung

Die Pfadsuche vor dem Kartenwechsel ist grundsätzlich die gleiche wie die A*-Suche.

1. Aktualisieren den rhs-Wert des Knotens.
2. Knoten, die lokal konsistent geworden sind, werden aus der Warteschlange entfernt.
3. Knoten, die lokal inkonsistent geworden sind, werden der Warteschlange hinzugefügt.
4. Der Schlüssel des teilweise inkonsistenten Knotens wurde aktualisiert.

Der Startpunkt ist der Knoten in der oberen rechten Ecke und der Zielknoten ist der Knoten in der unteren linken Ecke. Die erste Zahl beschreibt die kürzeste Entfernung von jedem Knoten zum Startknoten und den h-Wert von jedem Knoten zum Zielknoten. Die linke Seite ist der g*-Wert und die rechte Seite ist der h-Wert. Am Anfang werden alle Punkte rhs und g auf Unendlich gesetzt, und dann vom Startknoten aus wird der rhs des Startknotens auf 0 gesetzt und dann wird der Prozess der obigen Abbildung weiter iteriert, bis der kürzeste Pfad erhalten wird .

Geländezustand ändert

Wenn sich der Geländezustand ändert, wird in diesem Beispiel der Knoten (D, 1) zu einem Hindernis. Der Knoten wird zuerst aktualisiert und seine Nachkommenknoten werden in die Prioritätswarteschlange gestellt.Die Änderung des Knotens hat keine Auswirkung auf den Zustand des Elternknotens. Iterieren Sie ähnlich wie bei der ersten Suche kontinuierlich, bis der kürzeste Weg zum Zielort wieder gefunden wird.

当地形状态发生变动，在该例子中，节点(D,1)变为障碍。首先对该节点进行更新，并将其后代节点置于优先队列中，该节点的变动对父辈节点的状态并无影响。同第一次搜索类似，不断进行迭代直到再次找到到目标位置的最短路径。

Die folgende Abbildung stellt die Ergebnisse zweier Suchvorgänge dar. Der kürzeste Weg zum Startpunkt wird erreicht, indem von der Zielposition bis zum Erreichen des Startpunkts kontinuierlich der kleinste g+h-Wert (also der Wert in der Tabelle) gewählt wird.

Zusammenfassen

LPA schlägt eine Methode vor, um die Suche nach dem kürzesten Weg in einer dynamischen Umgebung zu lösen, zielt jedoch auf die Situation ab, in der der Startknoten und der Zielknoten fixiert sind.Wenn der Roboter den gesuchten kürzesten Weg entlangläuft, werden einige Knoten in der Umgebung auftreten Wenn Sie zu diesem Zeitpunkt einen neuen Pfad erhalten möchten, können Sie den aktuellen Knoten des Roboters als Startknoten verwenden und ihn mit dem LPA-Algorithmus erneut lösen.Diese Effizienz ist sehr gering.

LPA 提出了一种解决动态环境下的最短路径搜索方法，但是它针对的是起始节点和目标节点固定的情况，如果在机器人按照搜索到的最短路径行走过程中，环境中某些节点发生变化，这时如果想获得新的路径，就得以机器人当前节点为起始节点，重新用LPA 算法解算一次，这效率是很低的。

Der Autor des Artikels schlug den D* Lite-Algorithmus als effiziente Methode vor, um das Kürzeste-Weg-Problem in einer dynamischen Umgebung zu behandeln