Wie unterscheiden sich die neuesten Algorithmen zur Pfadfindung für das Ändern von Graphen (D *, D * -Lite, LPA * usw.)?

In den letzten Jahren wurden viele Pfadfindungsalgorithmen entwickelt, mit denen der beste Pfad in Reaktion auf Diagrammänderungen viel schneller als mit A * berechnet werden kann - was sind sie und wie unterscheiden sie sich? Sind sie für verschiedene Situationen oder veralten einige andere?

Dies sind die, die ich bisher finden konnte:

• D * (1994)
• Fokussiertes D * (1995)
• DynamicSWSF-FP (1996)
• LPA (1997)
• LPA * / Inkrementelles A * (2001)
• D * Lite (2002)
• SetA * (2002)
• HPA * (2004)
• Jederzeit D * (2005)
• PRA * (2005)
• Feld D * (2007)
• Theta * (2007)
• HAA * (2008)
• GAA * (2008)
• LEARCH (2009)
• BDDD * (2009 - Ich kann nicht auf dieses Dokument zugreifen: |)
• Inkrementelles Phi * (2009)
• GFRA * (2010)
• MTD * -Lite (2010)
• Baum-AA * (2011)

Ich bin nicht sicher, welche davon für mein spezielles Problem zutreffen - ich lese sie bei Bedarf alle durch, aber es würde mir viel Zeit sparen, wenn jemand eine Zusammenfassung schreiben könnte.

Mein spezielles Problem: Ich habe ein Gitter mit einem Anfang, einem Ende und einigen Wänden. Ich benutze derzeit A *, um den besten Weg vom Start bis zum Ziel zu finden.

Der Benutzer wird dann eine Wand verschieben , und ich muss den gesamten Pfad erneut berechnen. Der Schritt "Wand verschieben / Pfad neu berechnen" kommt oft hintereinander vor, daher suche ich nach einem Algorithmus, mit dem der beste Pfad schnell neu berechnet werden kann, ohne dass eine vollständige Iteration von A * ausgeführt werden muss.

Ich suche jedoch nicht unbedingt nach einer Änderung von A * - es könnte sich um einen völlig separaten Algorithmus handeln.

Also überflog ich die Papiere und das schimmerte. Wenn es jemanden gibt, der sich mit dem Thema besser auskennt, korrigieren Sie mich bitte, wenn ich falsch liege (oder fügen Sie Ihre eigene Antwort hinzu, und ich werde sie stattdessen akzeptieren!) .

Links zu den einzelnen Artikeln finden Sie oben im Fragebogen.

• Einfache Neuberechnungen
  • D * (aka Dynamic A * ) (1994): Bei der ersten Ausführung läuft D * sehr ähnlich wie A * und findet den besten Weg vom Anfang bis zum Ende sehr schnell. Wenn sich die Einheit jedoch von Anfang bis Ende bewegt und sich die Grafik ändert, kann D * den besten Weg von der Position der Einheit zum Ziel sehr schnell neu berechnen, viel schneller als A * erneut von der Position der Einheit ausführen zu müssen. D * hat jedoch den Ruf, äußerst komplex zu sein, und wurde durch das viel einfachere D * -Lite komplett überholt.
  • Focused D * (1995): Eine Verbesserung von D *, um es schneller / "Echtzeitfähiger" zu machen. Ich kann keine Vergleiche zu D * -Lite finden, aber da dies älter ist und über D * -Lite viel mehr gesprochen wird, gehe ich davon aus, dass D * -Lite irgendwie besser ist.
  • DynamicSWSF-FP (1996): Speichert die Entfernung von jedem Knoten zum Zielknoten. Hat eine große anfängliche Einrichtung, um alle Entfernungen zu berechnen. Nach Änderungen am Diagramm können nur die Knoten aktualisiert werden, deren Abstände sich geändert haben. Nicht mit A * und D * verwandt. Nützlich, wenn Sie nach jeder Änderung den Abstand zwischen mehreren Knoten und dem Ziel ermitteln möchten. Andernfalls sind LPA * oder D * -Lite in der Regel nützlicher.
  • LPA * / Incremental A * (2001): LPA * (Lifelong Planning A *) , auch als Incremental A * bekannt (und manchmal verwirrend als "LPA", obwohl es keine Beziehung zu dem anderen Algorithmus namens LPA hat) ist a Kombination von DynamicSWSF-FP und A *. Beim ersten Lauf ist es genau das gleiche wie A *. Nach geringfügigen Änderungen an der Grafik können jedoch nachfolgende Suchvorgänge desselben Start / Ziel-Paares die Informationen aus früheren Läufen verwenden, um die Anzahl der zu untersuchenden Knoten im Vergleich zu A * drastisch zu reduzieren. Dies ist genau mein Problem. Es scheint, dass LPA * meine beste Lösung ist. LPA * unterscheidet sich von D * dadurch, dass es immer den besten Weg vom selben Start zum selben Ziel findet; Es wird nicht verwendet, wenn sich der Startpunkt bewegt(z. B. Einheiten, die sich auf dem ursprünglich besten Weg bewegen) . Jedoch...
  • D * -Lite (2002): Dieser Algorithmus verwendet LPA *, um D * nachzuahmen. Das heißt, es verwendet LPA *, um den neuen besten Pfad für eine Einheit zu finden, während es sich entlang des anfänglichen besten Pfades bewegt und sich das Diagramm ändert. D * -Lite gilt als viel einfacher als D *, und da es immer mindestens so schnell läuft wie D *, hat es D * vollständig überholt. Daher gibt es keinen Grund, D * zu verwenden. benutze stattdessen D * -Lite.
• Bewegung in jedem Winkel
  • Feld D * (2007): Eine Variante von D * -Lite, die die Bewegung nicht auf ein Gitter beschränkt. Das heißt, der beste Pfad kann die Einheit entlang eines beliebigen Winkels bewegen, nicht nur 45 (oder 90) Grad zwischen Gitterpunkten. Wurde von der NASA verwendet, um nach den Marsrovern zu suchen.
  • Theta * (2007): Eine Variante von A *, die bessere (kürzere) Wege liefert als Feld D *. Da es jedoch auf A * und nicht auf D * -Lite basiert, verfügt es nicht über die Funktionen zur schnellen Neuplanung, die Field D * bietet. Siehe auch .
  • Incremental Phi * (2009): Das Beste aus beiden Welten. Eine inkrementelle Version von Theta * (auch bekannt als schnelles Nachplanen)
• Zielpunkte verschieben
  • GAA * (2008): GAA * (Generalized Adaptive A *) ist eine Variante von A *, die sich bewegende Zielpunkte handhabt. Es ist eine Verallgemeinerung eines noch früheren Algorithmus namens "Moving Target Adaptive A *".
  • GRFA * (2010): GFRA * (Generalized Fringe-Retrieving A *) scheint (?) Eine Verallgemeinerung von GAA * auf beliebige Graphen zu sein (dh nicht auf 2D beschränkt) , die Techniken eines anderen Algorithmus namens FRA * verwenden.
  • MTD * -Lite (2010): MTD * -Lite (Moving Target D * -Lite) ist eine "Erweiterung von D * Lite, die das Prinzip des Generalized Fringe-Retrieving A *" zur schnellen Neuplanung von Moving-Target-Suchen verwendet.
  • Tree-AA * (2011): (???) Scheint ein Algorithmus für die Suche in unbekanntem Terrain zu sein, basiert jedoch wie alle anderen Algorithmen in diesem Abschnitt auf Adaptive A *. Ich bin mir nicht sicher, wie es mit den anderen in diesem Abschnitt verglichen wird.
• Schnell / Suboptimal
  • Anytime D * (2005): Dies ist eine "Anytime" -Variante von D * -Lite, bei der D * -Lite mit einem Algorithmus namens Anytime Repairing A * kombiniert wird . Ein "Anytime" -Algorithmus ist ein Algorithmus, der unter beliebigen Zeitbeschränkungen ausgeführt werden kann - er findet sehr schnell einen sehr suboptimalen Pfad und verbessert diesen Pfad, je mehr Zeit ihm gegeben wird.
  • HPA * (2004): HPA * (Hierarchical Path-Finding A *) dient zum Auffinden einer großen Anzahl von Einheiten in einem großen Diagramm, z. B. in RTS - Videospielen (Echtzeitstrategie) . Sie haben alle unterschiedliche Startpositionen und möglicherweise unterschiedliche Endpositionen. HPA * unterteilt das Diagramm in eine Hierarchie, um "nahezu optimale" Pfade für alle diese Einheiten schneller zu finden, als A * für jede einzelne Einheit einzeln auszuführen. Siehe auch
  • PRA * (2005): Soweit ich weiß, löst PRA * (Partial Refinement A *) das gleiche Problem wie HPA *, jedoch auf andere Weise. Sie haben beide "ähnliche Leistungsmerkmale".
  • HAA * (2008): HAA * (Hierarchical Annotated A *) ist eine Verallgemeinerung von HPA *, die das eingeschränkte Durchqueren einiger Einheiten über einige Terrains ermöglicht (z. B. ein kleiner Pfad, durch den einige Einheiten gehen können, größere jedoch nicht; oder ein Loch, das nur fliegende Einheiten überqueren können; etc.)
• Andere / Unbekannt
  • LPA (1997): LPA (Loop-free Path Finding Algorithmus) scheint ein Routing-Algorithmus zu sein, der nur unwesentlich mit den Problemen zusammenhängt, die die anderen Algorithmen hier lösen. Ich erwähne es nur, weil dieses Papier an mehreren Stellen im Internet verwirrend (und fälschlicherweise) als das Papier zur Einführung von LPA * bezeichnet wird, was es nicht ist.
  • LEARCH (2009): LEARCH ist eine Kombination von Algorithmen für maschinelles Lernen, mit denen Roboter lernen, wie sie selbst fast optimale Pfade finden. Die Autoren schlagen vor, LEARCH mit Field D * zu kombinieren, um bessere Ergebnisse zu erzielen.
  • BDDD * (2009): ??? Ich kann nicht auf das Papier zugreifen.
  • SetA * (2002): Dies ist anscheinend eine Variante von A *, die das BDD-Modell ( Binary Decision Chart) des Graphen durchsucht . Sie behaupten, dass es in einigen Fällen "mehrere Größenordnungen schneller als A *" läuft . Wenn ich das richtig verstehe, liegen diese Fälle dann vor, wenn jeder Knoten im Diagramm viele Kanten hat?

Angesichts all dessen scheint LPA * für mein Problem am besten geeignet zu sein.

Es gibt eine große Einschränkung bei der Verwendung von D *, D * -Lite oder einem der inkrementellen Algorithmen in dieser Kategorie (und es ist erwähnenswert, dass diese Einschränkung in der Literatur selten erwähnt wird). Diese Arten von Algorithmen verwenden eine umgekehrte Suche. Das heißt, sie berechnen die Kosten vom Zielknoten nach außen, wie eine Welligkeit, die sich nach außen ausbreitet. Wenn sich die Kosten für Kanten ändern (z. B. wenn Sie in Ihrem Beispiel eine Wand hinzufügen oder entfernen), verfügen alle über verschiedene effiziente Strategien, um nur die Teilmenge der untersuchten (auch als "besuchte" bezeichneten) Knoten zu aktualisieren, die von den Änderungen betroffen sind.

Die große Einschränkung besteht darin, dass die Position dieser Änderungen in Bezug auf die Zielposition einen enormen Unterschied für die Effizienz der Algorithmen darstellt. Ich habe in verschiedenen Abhandlungen und meiner These gezeigt, dass es durchaus möglich ist, dass die schlechteste Leistung eines dieser inkrementellen Algorithmen schlechter ist, als alle Informationen wegzuwerfen und mit etwas neuem zu beginnen, das nicht inkrementell ist, wie einfaches altes A *.

Befinden sich die geänderten Kosteninformationen in der Nähe des Umfangs der erweiterten Suche (der "besuchten" Region), müssen nur wenige Pfade geändert werden, und die inkrementellen Aktualisierungen sind schnell. Ein einschlägiges Beispiel ist ein mobiler Roboter, an dessen Körper Sensoren angebracht sind. Die Sensoren sehen nur die Welt in der Nähe des Roboters, und daher sind die Änderungen in dieser Region. Diese Region ist der Startpunkt der Suche, nicht das Ziel, und so funktioniert alles gut und die Algorithmen sind sehr effizient bei der Aktualisierung des optimalen Pfads, um die Änderungen zu korrigieren.

Wenn sich die geänderten Kosteninformationen dem Ziel der Suche nähern (oder in Ihrem Szenario die Zieländerungsorte und nicht nur der Start angezeigt werden), kommt es zu einer katastrophalen Verlangsamung dieser Algorithmen. In diesem Szenario müssen fast alle gespeicherten Informationen aktualisiert werden, da sich der geänderte Bereich so nahe am Ziel befindet, dass fast alle vorberechneten Pfade die Änderungen durchlaufen und neu ausgewertet werden müssen. Aufgrund des Mehraufwands beim Speichern zusätzlicher Informationen und Berechnungen für inkrementelle Aktualisierungen ist eine Neubewertung in dieser Größenordnung langsamer als ein Neustart.

Da in Ihrem Beispielszenario der Benutzer scheinbar jede gewünschte Wand verschieben kann, tritt dieses Problem auf, wenn Sie D *, D * -Lite, LPA * usw. verwenden. Die Zeitleistung Ihres Algorithmus ist je nach Benutzer unterschiedlich Eingang. Im Allgemeinen "das ist eine schlechte Sache" ...

Als Beispiel hatte Alonzo Kellys Gruppe an der CMU ein fantastisches Programm namens PerceptOR, das versuchte, Bodenroboter mit Luftrobotern zu kombinieren, wobei alle Wahrnehmungsinformationen in Echtzeit ausgetauscht wurden. Als sie versuchten, das Planungssystem eines Bodenfahrzeugs mit einem Hubschrauber in Echtzeit auf den neuesten Stand zu bringen, stießen sie auf dieses Problem, da der Hubschrauber dem Bodenfahrzeug vorausfliegen und die Kosten näher am Ziel liegen und sich somit verlangsamen könnte ihre Algorithmen nach unten. Haben sie diese interessante Beobachtung besprochen? Nein. Am Ende gelang es ihnen am besten, den Hubschrauber direkt über dem Bodenfahrzeug fliegen zu lassen - und es damit zum teuersten Sensormast der Welt zu machen. Klar, ich bin kleinlich. Aber es ist ein großes Problem, über das niemand sprechen möchte - und sie sollten,

Es gibt nur eine Handvoll Papiere, die dies diskutieren, hauptsächlich von mir. Von den Arbeiten, die von den Autoren oder Studenten der Autoren der in dieser Frage aufgeführten Originalarbeiten verfasst wurden, fällt mir nur eine ein, die dieses Problem tatsächlich erwähnt. Likhachev und Ferguson schlagen vor, den Umfang der erforderlichen Aktualisierungen abzuschätzen und die gespeicherten Informationen zu löschen, wenn die inkrementelle Aktualisierung voraussichtlich länger dauert als ein Neustart. Dies ist eine vernünftige Lösung, aber es gibt auch andere. Meine Doktorarbeit verallgemeinert einen ähnlichen Ansatz auf ein breites Spektrum von Rechenproblemen und geht über den Rahmen dieser Frage hinaus. Sie finden die Referenzen jedoch möglicherweise nützlich, da sie einen umfassenden Überblick über die meisten dieser Algorithmen und mehr bietet. Siehe http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364 für Details.

Die Hauptidee ist, einen inkrementellen Algorithmus zu verwenden, der in der Lage ist, die vorherigen Berechnungen zu nutzen, wenn die anfänglich berechnete Route blockiert wird. Dies wird häufig im Zusammenhang mit Robotern, Navigation und Planung untersucht.

Koenig & Likkachev, Schnelles Umplanen für die Navigation in unbekanntem Gelände, IEEE Transactions on Robotics, Vol. 3, No. 3, Juni 2005, stellt D * Lite vor. Man kann mit Sicherheit sagen, dass D * in dem Sinne veraltet ist, dass D * Lite immer so schnell ist wie D *. Darüber hinaus ist D * komplex, schwer zu verstehen, zu analysieren und zu erweitern. 9 gibt den Pseudocode für D * Lite an, und Tabelle 1 zeigt experimentelle Ergebnisse mit D * Lite im Vergleich zu BFS, Rückwärts A *, Vorwärts A *, DynamicSWSF-P und D *.

Ich kenne die neueren Algorithmen, die Sie auflisten, nicht (Anytime D *, Field D *, LEARCH). Vor kurzem habe ich einen Roboter gesehen, der D * Lite für die Planung in einer Umgebung mit zufälligen Gehern verwendet hat. In diesem Sinne denke ich nicht, dass D * Lite auf keinen Fall veraltet ist. Für Ihr praktisches Problem gibt es wohl keinen Nachteil, wenn Sie die übliche technische Vorgehensweise ausprobieren: Gehen Sie einen Ansatz vor, und wenn er nicht Ihren Anforderungen entspricht, probieren Sie etwas anderes (komplexeres) aus.

Ich möchte etwas über das schnelle Erkunden von zufälligen Bäumen oder RRTs hinzufügen. Die Grundidee wird im Internet gut diskutiert, aber es ist wahrscheinlich sicher, mit den Links von der Wikipedia-Seite und mit den Originalarbeiten von Kuffner und LaValle zu diesem Thema zu beginnen.

Das wichtigste Merkmal von RRTs ist, dass sie mit realwertigen Räumen von extrem hoher Dimension umgehen können, ohne zu ersticken. Sie können mit Dynamik umgehen, sind nicht optimal, aber wahrscheinlichkeitstheoretisch vollständig (garantiert erfolgreich, wenn die Rechenzeit unendlich ist) und können sich bewegende Ziele handhaben. Es gibt einige Erweiterungen, mit denen sie in nicht statischen Bereichen arbeiten können. Das Beste davon scheint die mehrteilige RRT-Arbeit zu sein, die ich unten verlinkt habe.

• http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree
• http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf

Datenstrukturen, Distanz-Orakel genannt, behandeln solche Probleme. Die meisten Forschungsergebnisse beziehen sich jedoch nur auf statische Diagramme.

Handelt es sich bei den Diagrammen um Raster (und damit um ebene), existieren einige dynamische Datenstrukturen (unklar, ob die Konstanten für die betreffende Anwendung klein genug sind):

Genaue kürzeste Wege:

Jittat Fakcharoenphol, Satish Rao: Planare Graphen, negative Gewichtungskanten, kürzeste Wege und nahezu lineare Zeit. J. Comput. Syst. Sci. 72 (5): 868-889 (2006)

Ungefähre kürzeste Wege:

Philip N. Klein, Sairam Subramanian: Ein vollständig dynamisches Approximationsschema für kürzeste Pfade in planaren Graphen. Algorithmica 22 (3): 235 & ndash; 249 (1998)

Ittai Abraham, Shiri Chechik und Cyril Gavoille: Volldynamische ungefähre Entfernungsangaben für ebene Graphen über verbotene Entfernungsangaben. STOC 2012: 1199-1218

In der Schule habe ich mich mit der Optimierung von Ameisenkolonien beschäftigt . In einigen Texten wurde es als eine Lösung für sich ständig ändernde Grafiken, Routing-Netzwerke usw. angepriesen. Es ist keine technische Lösung, sondern eine Anpassung dessen, wie Ameisen um Hindernisse navigieren, indem sie Pheromone ausbreiten, um gute und schlechte Wege zu markieren. Ich habe keine Ahnung, ob es für Ihr Problem funktioniert, aber ich denke, es ist ein interessanter Standpunkt.