D* - D*

D* (ausgesprochen "D-Stern") ist einer der folgenden drei verwandten inkrementellen Suchalgorithmen :

• Das ursprüngliche D* von Anthony Stentz ist ein informierter inkrementeller Suchalgorithmus.
• Focused D* ist ein informierter inkrementeller heuristischer Suchalgorithmus von Anthony Stentz, der Ideen von A* und dem ursprünglichen D* kombiniert . Focused D* entstand aus einer Weiterentwicklung des ursprünglichen D*.
• D* Lite ist ein inkrementeller heuristischer Suchalgorithmus von Sven Koenig und Maxim Likhachev, der auf LPA* aufbaut , einem inkrementellen heuristischen Suchalgorithmus, der Ideen von A* und Dynamic SWSF-FP kombiniert .

Alle drei Suchalgorithmen lösen die gleiche Annahme basierte Wegplanung Probleme, einschließlich der Planung mit der freien Speicherplatz Annahme, wo ein Roboter gegeben Ziel Koordinaten in unbekanntem Gelände zu navigieren hat. Es macht Annahmen über den unbekannten Teil des Geländes (zB dass es keine Hindernisse enthält) und findet unter diesen Annahmen einen kürzesten Weg von seinen aktuellen Koordinaten zu den Zielkoordinaten. Der Roboter folgt dann der Bahn. Wenn es neue Karteninformationen (zB bisher unbekannte Hindernisse) beobachtet, fügt es die Informationen zu seiner Karte hinzu und plant gegebenenfalls einen neuen kürzesten Weg von seinen aktuellen Koordinaten zu den gegebenen Zielkoordinaten neu. Er wiederholt den Vorgang, bis er die Zielkoordinaten erreicht oder feststellt, dass die Zielkoordinaten nicht erreicht werden können. Beim Durchqueren von unbekanntem Terrain können häufig neue Hindernisse entdeckt werden, daher muss diese Neuplanung schnell erfolgen. Inkrementelle (heuristische) Suchalgorithmen beschleunigen die Suche nach Folgen ähnlicher Suchprobleme, indem sie die Erfahrung mit den vorherigen Problemen nutzen, um die Suche nach dem aktuellen zu beschleunigen. Unter der Annahme, dass sich die Zielkoordinaten nicht ändern, sind alle drei Suchalgorithmen effizienter als wiederholte A*-Suchen.

D* und seine Varianten werden häufig für die Navigation von mobilen Robotern und autonomen Fahrzeugen verwendet . Aktuelle Systeme basieren in der Regel auf D* Lite und nicht auf dem ursprünglichen D* oder Focussed D*. Tatsächlich verwendet sogar das Labor von Stentz in einigen Implementierungen D* Lite anstelle von D*. Zu diesen Navigationssystemen gehören ein auf den Mars-Rovers Opportunity und Spirit getesteter Prototyp sowie das Navigationssystem des Gewinnerbeitrags der DARPA Urban Challenge , die beide an der Carnegie Mellon University entwickelt wurden .

Das ursprüngliche D* wurde 1994 von Anthony Stentz eingeführt. Der Name D* leitet sich vom Begriff "Dynamic A*" ab, da sich der Algorithmus wie A* verhält, außer dass sich die Bogenkosten während der Ausführung des Algorithmus ändern können.

Operation

Die grundlegende Funktionsweise von D* wird unten beschrieben.

Wie der Algorithmus von Dijkstra und A* verwaltet D* eine Liste von auszuwertenden Knoten, die als "OPEN-Liste" bekannt ist. Knoten sind mit einem von mehreren Zuständen gekennzeichnet:

• NEU, d.h. es wurde noch nie auf die OPEN-Liste gesetzt
• OFFEN, d.h. es befindet sich derzeit auf der OFFEN-Liste
• GESCHLOSSEN, d.h. es steht nicht mehr auf der OFFEN-Liste
• RAISE, was darauf hinweist, dass die Kosten höher sind als beim letzten Mal, als es auf der OPEN-Liste stand
• LOWER, was darauf hinweist, dass die Kosten niedriger sind als beim letzten Mal auf der OPEN-ListeEN

Erweiterung

Der Algorithmus funktioniert, indem er iterativ einen Knoten aus der OPEN-Liste auswählt und auswertet. Es propagiert dann die Änderungen des Knotens an alle benachbarten Knoten und platziert sie auf der OPEN-Liste. Dieser Ausbreitungsprozess wird als "Expansion" bezeichnet. Im Gegensatz zum kanonischen A*, das dem Pfad von Anfang bis Ende folgt, beginnt D* mit der Rückwärtssuche vom Zielknoten aus. Jeder erweiterte Knoten hat einen Rückzeiger, der auf den nächsten Knoten verweist, der zum Ziel führt, und jeder Knoten kennt die genauen Kosten für das Ziel. Wenn der Startknoten der nächste zu erweiternde Knoten ist, ist der Algorithmus fertig und der Weg zum Ziel kann einfach durch Folgen der Backpointer gefunden werden.

• 

  Erweiterung im Gange. Der Zielknoten (gelb) liegt in der Mitte der oberen Punktereihe, der Startknoten in der Mitte der unteren Punktereihe. Rot zeigt ein Hindernis an; schwarz/blau zeigt erweiterte Knoten an (Helligkeit zeigt Kosten an). Grün kennzeichnet Knoten, die erweitert werden.

• 

  Erweiterung abgeschlossen. Der Pfad wird in Cyan angezeigt.

Hindernisbehandlung

Wenn ein Hindernis entlang des vorgesehenen Pfades erkannt wird, werden alle betroffenen Punkte wieder auf die Liste OPEN gesetzt, diesmal mit der Markierung RAISE. Bevor die Kosten eines RAISED-Knotens jedoch steigen, überprüft der Algorithmus seine Nachbarn und prüft, ob er die Kosten des Knotens reduzieren kann. Wenn nicht, wird der RAISE-Zustand an alle Nachkommen der Knoten weitergegeben, dh an Knoten, die Rückzeiger darauf haben. Diese Knoten werden dann ausgewertet und der RAISE-Zustand wird wellenförmig weitergegeben. Wenn ein RAISED-Knoten reduziert werden kann, wird sein Backpointer aktualisiert und übergibt den LOWER-Zustand an seine Nachbarn. Diese Wellen von RAISE- und LOWER-Zuständen sind das Herz von D*.

An diesem Punkt wird eine ganze Reihe anderer Punkte daran gehindert, von den Wellen "berührt" zu werden. Der Algorithmus hat daher nur an den Punkten gearbeitet, die von der Kostenänderung betroffen sind.

• 

  Ein Hindernis wurde hinzugefügt (rot) und Knoten mit der Markierung RAISE (gelb).

• 

  Erweiterung im Gange. Gelb bedeutet Knoten, die mit RAISE markiert sind, Grün zeigt Knoten an, die mit LOWER markiert sind.

Ein weiterer Deadlock tritt auf

Diesmal lässt sich der Deadlock nicht so elegant umgehen. Keiner der Punkte kann eine neue Route über einen Nachbarn zum Ziel finden. Daher propagieren sie ihre Kostensteigerung weiter. Es können nur Punkte außerhalb des Kanals gefunden werden, die über eine gangbare Route zum Ziel führen können. So entstehen zwei Lower-Wellen, die sich als als unerreichbar markierte Punkte mit neuen Routeninformationen erweitern.

• 

  Kanal durch zusätzliche Hindernisse blockiert (rot)

• 

  Erweiterung im Gange (Welle anheben in Gelb, Welle unten in Grün)

• 

  Neuer Pfad gefunden (cyan)

Pseudocode

while (!openList.isEmpty()) {
    point = openList.getFirst();
    expand(point);
}

Erweitern

void expand(currentPoint) {
    boolean isRaise = isRaise(currentPoint);
    double cost;
    for each (neighbor in currentPoint.getNeighbors()) {
        if (isRaise) {
            if (neighbor.nextPoint == currentPoint) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            } else {
                cost = neighbor.calculateCostVia(currentPoint);
                if (cost < neighbor.getCost()) {
                    currentPoint.setMinimumCostToCurrentCost();
                    openList.add(currentPoint);
                }
            }
        } else {
            cost = neighbor.calculateCostVia(currentPoint);
            if (cost < neighbor.getCost()) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            }
        }
    }
}

Auf Erhöhung prüfen

boolean isRaise(point) {
    double cost;
    if (point.getCurrentCost() > point.getMinimumCost()) {
        for each(neighbor in point.getNeighbors()) {
            cost = point.calculateCostVia(neighbor);
            if (cost < point.getCurrentCost()) {
                point.setNextPointAndUpdateCost(neighbor);
            }
        }
    }
    return point.getCurrentCost() > point.getMinimumCost();
}

Varianten

Fokussiert D*

Wie der Name schon sagt, ist Focused D* eine Erweiterung von D*, die eine Heuristik verwendet, um die Ausbreitung von RAISE und LOWER in Richtung des Roboters zu fokussieren. Auf diese Weise werden nur die relevanten Zustände aktualisiert, genauso wie A* nur die Kosten für einige der Knoten berechnet.

D* Lite

D* Lite basiert nicht auf dem ursprünglichen D* oder Focused D*, implementiert aber das gleiche Verhalten. Es ist einfacher zu verstehen und in weniger Codezeilen zu implementieren, daher der Name "D* Lite". In Bezug auf die Leistung ist es genauso gut oder besser als Focused D*. D* Lite basiert auf Lifelong Planning A* , das einige Jahre zuvor von Koenig und Likhachev eingeführt wurde. D* Lite

Minimale Kosten im Vergleich zu aktuellen Kosten

Für D* ist es wichtig, zwischen laufenden und minimalen Kosten zu unterscheiden. Ersteres ist nur zum Zeitpunkt der Sammlung wichtig und letzteres ist kritisch, da es die OpenList sortiert. Die Funktion, die die minimalen Kosten zurückgibt, ist immer die niedrigsten Kosten zum aktuellen Punkt, da sie der erste Eintrag der OpenList ist.

Verweise

Externe Links

• Webseite von Sven Koenig
• Webseite von Anthony Stentz