Lebenslange Planung A * - Lifelong Planning A*

Klasse	Suchalgorithmus
Datenstruktur	Graph

LPA * oder Lebenslange Planung A * ist ein inkrementeller heuristischer Suchalgorithmus, der auf A * basiert . Es wurde erstmals 2001 von Sven Koenig und Maxim Likhachev beschrieben.

Beschreibung

LPA * ist eine inkrementelle Version von A *, die sich an Änderungen im Diagramm anpassen kann, ohne das gesamte Diagramm neu zu berechnen, indem die g-Werte (Abstand vom Start) der vorherigen Suche während der aktuellen Suche aktualisiert werden, um sie bei Bedarf zu korrigieren. Wie A * verwendet LPA * eine Heuristik, die eine untere Grenze für die Kosten des Pfades von einem bestimmten Knoten zum Ziel darstellt. Eine Heuristik ist zulässig, wenn sie garantiert nicht negativ ist (Null ist zulässig) und niemals höher als die Kosten des billigsten Wegs zum Ziel.

Vorgänger und Nachfolger

Mit Ausnahme des Start- und Zielknoten, wobei jeder Knoten $n$ hat Vorgänger und Nachfolger :

Jeder Knoten, von dem eine Kante zu $n führt,$ ist ein Vorgänger von $n$ .
Jeder Knoten, zu dem eine Kante von $n führt,$ ist ein Nachfolger von $n$ .

In der folgenden Beschreibung beziehen sich diese beiden Begriffe nur auf die unmittelbaren Vorgänger und Nachfolger, nicht auf Vorgänger von Vorgängern oder Nachfolger von Nachfolgern.

Entfernungsschätzungen starten

LPA * verwaltet zwei Schätzungen der Startentfernung $g * (n)$ für jeden Knoten:

$g (n)$ der zuvor berechnete g-Wert (Startabstand) wie in A *
$rhs (n)$ , ein Lookahead-Wert basierend auf den g-Werten der Vorgänger des Knotens (das Minimum aller $g (n ') + d (n', n)$ , wobei $n '$ ein Vorgänger von $n$ und $d (x, ist) y)$ sind die Kosten für die Kante, die $x$ und $y verbindet$ )

Für den Startknoten gilt immer Folgendes:

{\ displaystyle rhs (start) = g (start) = 0}

Wenn $rhs (n)$ gleich $g (n) ist$ , wird $n$ als lokal konsistent bezeichnet . Wenn alle Knoten lokal konsistent sind, kann ein kürzester Pfad wie bei A * bestimmt werden. Wenn sich jedoch die Randkosten ändern, muss die lokale Konsistenz nur für die Knoten wiederhergestellt werden, die für die Route relevant sind.

Prioritätswarteschlange

Wenn ein Knoten lokal inkonsistent wird (weil sich die Kosten seines Vorgängers oder die Kante, die ihn mit einem Vorgänger verbindet, geändert haben), wird er zur erneuten Bewertung in eine Prioritätswarteschlange gestellt . LPA * verwendet einen zweidimensionalen Schlüssel:

{\ displaystyle k (n) = {\ begin {bmatrix} k_ {1} (n) \\ k_ {2} (n) \\\ end {bmatrix}} = {\ begin {bmatrix} min (g (n ), rhs (n)) + h (n, Ziel) \\ min (g (n), rhs (n)) \\\ end {bmatrix}}}

Die Einträge sind nach $k 1$ geordnet (was direkt den in A * verwendeten f-Werten entspricht) und dann nach $k 2$ .

Knotenerweiterung

Der oberste Knoten in der Warteschlange wird wie folgt erweitert:

Wenn der rhs-Wert eines Knotens gleich seinem g-Wert ist, ist der Knoten lokal konsistent und wird aus der Warteschlange entfernt.
Wenn der rhs-Wert eines Knotens kleiner als sein g-Wert ist (als lokal überkonsistenter Knoten bezeichnet), wird der g-Wert so geändert, dass er mit dem rhs-Wert übereinstimmt, wodurch der Knoten lokal konsistent wird. Der Knoten wird dann aus der Warteschlange entfernt.
Wenn der rhs-Wert eines Knotens größer als sein g-Wert ist (als lokal unterkonsistenter Knoten bezeichnet), wird der g-Wert auf unendlich gesetzt (wodurch der Knoten entweder lokal überkonsistent oder lokal konsistent wird). Wenn der Knoten dann lokal konsistent ist, wird er aus der Warteschlange entfernt, andernfalls wird sein Schlüssel aktualisiert.

Da das Ändern des g-Werts eines Knotens auch die rhs-Werte seiner Nachfolger (und damit ihre lokale Konsistenz) ändern kann, werden sie ausgewertet und ihre Warteschlangenmitgliedschaft und ihr Schlüssel werden bei Bedarf aktualisiert.

Die Erweiterung der Knoten wird mit dem nächsten Knoten oben in der Warteschlange fortgesetzt, bis zwei Bedingungen erfüllt sind:

Das Ziel ist lokal konsistent und
Der Knoten oben in der Prioritätswarteschlange hat einen Schlüssel, der größer oder gleich dem Schlüssel für das Ziel ist.

Erster Lauf

Der Graph wird initialisiert, indem der rhs-Wert des Startknotens auf 0 und sein g-Wert auf unendlich gesetzt wird. Für alle anderen Knoten wird angenommen, dass sowohl der g-Wert als auch der rhs-Wert unendlich sind, bis etwas anderes zugewiesen wird. Dies macht den Startknoten zunächst zum einzigen lokal inkonsistenten Knoten und damit zum einzigen Knoten in der Warteschlange. Danach beginnt die Knotenerweiterung. Der erste Lauf von LPA * verhält sich also wie A * und erweitert dieselben Knoten in derselben Reihenfolge.

Kostenänderungen

Wenn sich die Kosten einer Kante ändern, untersucht LPA * alle von der Änderung betroffenen Knoten, dh alle Knoten, an denen eine der geänderten Kanten endet (wenn eine Kante in beide Richtungen durchlaufen werden kann und die Änderung beide Richtungen betrifft, werden beide Knoten durch verbunden die Kante werden untersucht):

Die rhs-Werte der Knoten werden aktualisiert.
Lokal konsistente Knoten werden aus der Warteschlange entfernt.
Knoten, die lokal inkonsistent geworden sind, werden der Warteschlange hinzugefügt.
Bei Knoten, die lokal inkonsistent bleiben, werden die Schlüssel aktualisiert.

Danach wird die Knotenerweiterung fortgesetzt, bis die Endbedingung erreicht ist.

Den kürzesten Weg finden

Sobald die Knotenerweiterung abgeschlossen ist (dh die Ausgangsbedingungen erfüllt sind), wird der kürzeste Pfad ausgewertet. Wenn die Kosten für das Ziel gleich unendlich sind, gibt es keinen Pfad mit endlichen Kosten vom Start bis zum Ziel. Andernfalls kann der kürzeste Weg durch Rückwärtsbewegen ermittelt werden:

Beginnen Sie am Ziel.
Gehen Sie zum Vorgänger $n '$ des aktuellen Knotens $n,$ für den $g (n') + d (n ', n)$ am niedrigsten ist (wenn die niedrigste Punktzahl von mehreren Knoten geteilt wird, ist jeder eine gültige Lösung und jeder von ihnen kann es sein willkürlich gewählt).
Wiederholen Sie den vorherigen Schritt, bis Sie den Start erreicht haben.

Pseudocode

Dieser Code nimmt eine Prioritätswarteschlange an queue, die die folgenden Vorgänge unterstützt:

topKey() Gibt die (numerisch) niedrigste Priorität eines Knotens in der Warteschlange zurück (oder unendlich, wenn die Warteschlange leer ist).
pop() Entfernt den Knoten mit der niedrigsten Priorität aus der Warteschlange und gibt ihn zurück
insert(node, priority) Fügt einen Knoten mit einer bestimmten Priorität in die Warteschlange ein
remove(node) Entfernt einen Knoten aus der Warteschlange
contains(node) Gibt true zurück, wenn die Warteschlange den angegebenen Knoten enthält, andernfalls false

void main() {
  initialize();
  while (true) {
    computeShortestPath();
    while (!hasCostChanges())
      sleep;
    for (edge : getChangedEdges()) {
        edge.setCost(getNewCost(edge));
        updateNode(edge.endNode);
    }
  }
}

void initialize() {
  queue = new PriorityQueue();
  for (node : getAllNodes()) {
    node.g = INFINITY;
    node.rhs = INFINITY;
  }
  start.rhs = 0;
  queue.insert(start, calculateKey(start));
}

/** Expands the nodes in the priority queue. */
void computeShortestPath() {
  while ((queue.getTopKey() < calculateKey(goal)) || (goal.rhs != goal.g)) {
    node = queue.pop();
    if (node.g > node.rhs) {
      node.g = node.rhs;
      for (successor : node.getSuccessors())
        updateNode(successor);
    } else {
      node.g = INFINITY;
      updateNode(node);
      for (successor : node.getSuccessors())
        updateNode(successor);
    }
  }
}

/** Recalculates rhs for a node and removes it from the queue.
 * If the node has become locally inconsistent, it is (re-)inserted into the queue with its new key. */
void updateNode(node) {
  if (node != start) {
    node.rhs = INFINITY;
    for (predecessor: node.getPredecessors())
      node.rhs = min(node.rhs, predecessor.g + predecessor.getCostTo(node));
    if (queue.contains(node))
      queue.remove(node);
    if (node.g != node.rhs)
      queue.insert(node, calculateKey(node));
  }
}

int[] calculateKey(node) {
  return {min(node.g, node.rhs) + node.getHeuristic(goal), min(node.g, node.rhs)};
}

Eigenschaften

Da LPA * A * algorithmisch ähnlich ist, teilt es viele seiner Eigenschaften.

Jeder Knoten wird für jeden LPA * -Lauf höchstens zweimal erweitert (besucht). Lokal überkonsistente Knoten werden höchstens einmal pro LPA * -Lauf erweitert, sodass der anfängliche Lauf (bei dem jeder Knoten in den überkonsistenten Zustand wechselt) eine ähnliche Leistung aufweist wie A *, bei dem jeder Knoten höchstens einmal besucht wird.
Die Schlüssel der Knoten, die für jeden Lauf erweitert werden, nehmen mit der Zeit monoton ab, wie dies bei A * der Fall ist.
Je informierter (und damit größer) die Heuristiken sind (und dennoch die Zulässigkeitskriterien erfüllen), desto weniger Knoten müssen erweitert werden.
Die Implementierung der Prioritätswarteschlange hat einen erheblichen Einfluss auf die Leistung, wie in A *. Die Verwendung eines Fibonacci-Heaps kann zu einer signifikanten Leistungssteigerung gegenüber weniger effizienten Implementierungen führen.

Für eine A * -Implementierung, bei der Verbindungen zwischen zwei Knoten mit gleichen f-Werten zugunsten des Knotens mit dem kleineren g-Wert (der in A * nicht genau definiert ist) unterbrochen werden, gelten auch die folgenden Aussagen:

Die Reihenfolge, in der lokal überkonsistente Knoten erweitert werden, ist identisch mit A *.
Von allen lokal überkonsistenten Knoten müssen nur diejenigen erweitert werden, deren Kosten die des Ziels nicht überschreiten, wie dies bei A * der Fall ist.

LPA * hat zusätzlich folgende Eigenschaften:

Wenn sich die Kantenkosten ändern, übertrifft LPA * A * (vorausgesetzt, letzteres wird von Grund auf neu ausgeführt), da nur ein Bruchteil der Knoten erneut erweitert werden muss.

Varianten

D * Lite , eine Neuimplementierung des D * -Algorithmus basierend auf LPA *

Languages

In other projects