Wegfindung

Für andere Verwendungen siehe Pathfinder (Disambiguierung).
Äquivalente Pfade zwischen A und B in einer 2D -Umgebung

Wegfindung oder Pfad ist die Plotte durch eine Computeranwendung der kürzesten Route zwischen zwei Punkten. Es ist eine praktischere Variante auf Labyrinthe Labyrinthe. Dieser Forschungsbereich basiert stark auf Dijkstra -Algorithmus um den kürzesten Weg auf einem zu finden gewichtete Grafik.

Die Pfadfindung ist eng mit dem verwandt kürzestes Pfadproblem, innerhalb Graphentheorie, in dem untersucht wird, wie man den Weg identifiziert, der einige Kriterien (kürzest, billig, schnellstes usw.) zwischen zwei Punkten in einem großen Netzwerk erfüllt.

Algorithmen

Im Kern sucht eine Pfadfindungsmethode a Graph durch Start bei einem Scheitel und angrenzende Erkundung Knoten Bis der Zielknoten erreicht ist, im Allgemeinen mit der Absicht, den billigsten Weg zu finden. Obwohl Grafik -Suchmethoden wie a Breite-First-Suche Würde eine Route finden, wenn genügend Zeit, andere Methoden, die das Diagramm "erforschen" würden, neigen dazu, das Ziel früher zu erreichen. Eine Analogie wäre eine Person, die durch einen Raum geht; Anstatt jede mögliche Route im Voraus zu untersuchen, ging die Person im Allgemeinen in Richtung des Ziels und abweicht nur vom Pfad ab, um eine Obstruktion zu vermeiden und Abweichungen so gering wie möglich zu machen.

Zwei Hauptprobleme der Pfadfindung sind (1), um einen Pfad zwischen zwei Knoten in a zu finden Graph; und (2) die kürzestes Pfadproblem- um das zu finden Optimaler kürzester Weg. Grundlegende Algorithmen wie z. Breite zuerst und Tiefe-First Suchen Sie die Adresse des ersten Problems durch anstrengend alle Möglichkeiten; Ausgehend vom angegebenen Knoten iterieren sie über alle möglichen Pfade, bis sie den Zielknoten erreichen. Diese Algorithmen laufen in oder lineare Zeit, wo v die Anzahl der Eckpunkte ist und e die Anzahl der Anzahl von Kanten zwischen Scheitelpunkten.

Das kompliziertere Problem ist es, den optimalen Weg zu finden. Der erschöpfende Ansatz in diesem Fall ist als der bekannt als der Bellman -.ford -Algorithmus, was eine zeitliche Komplexität von liefert oder quadratische Zeit. Es ist jedoch nicht erforderlich, alle möglichen Wege zu untersuchen, um die optimale zu finden. Algorithmen wie EIN* und Dijkstra -Algorithmus strategisch weder Wege beseitigen, entweder durch Heuristik oder durch Dynamische Programmierung. Durch die Beseitigung unmöglicher Pfade können diese Algorithmen zeitlich so niedrig erreichen wie .[1]

Die obigen Algorithmen gehören zu den besten allgemeinen Algorithmen, die ohne Vorverarbeitung in einem Diagramm arbeiten. In praktischen Reisungssystemen können jedoch noch bessere Zeitkomplexität durch Algorithmen erreicht werden, die das Diagramm vorbereiten können, um eine bessere Leistung zu erzielen.[2] Ein solcher Algorithmus ist Kontraktion hierarchien.

Dijkstra -Algorithmus

Ein gemeinsames Beispiel für einen auf Diagramm basierenden Pfadfindungsalgorithmus ist Dijkstra -Algorithmus. Dieser Algorithmus beginnt mit einem Startknoten und einem "offenen Satz" von Kandidatenknoten. Bei jedem Schritt wird der Knoten im offenen Satz mit dem niedrigsten Abstand vom Start untersucht. Der Knoten ist als "geschlossen" gekennzeichnet, und alle Knoten neben ihm werden dem offenen Satz hinzugefügt, wenn sie noch nicht untersucht wurden. Dieser Vorgang wiederholt sich, bis ein Weg zum Ziel gefunden wurde. Da zuerst die Niedrigungsknoten untersucht werden, ist das erste Mal, dass das Ziel gefunden wird, der Pfad dazu der kürzeste Weg.[3]

Der Algorithmus von Dijkstra schlägt fehl, wenn es negativ ist Kante Gewicht. In der hypothetischen Situation, in der die Knoten A, B und C einen verbundenen undirezierten Graphen mit den Kanten AB = 3, AC = 4 und BC = –2 bilden, kostet der optimale Weg von A bis C 1 und der optimale Weg von a nach B Kosten 2. Dijkstra -Algorithmus ab A wird zuerst B untersuchen, da dies am nächsten ist. Es wird ihm Kosten von 3 zuweisen und es geschlossen markieren, was bedeutet, dass seine Kosten niemals neu bewertet werden. Daher können Dijkstra negative Kantengewichte nicht bewerten. Da es jedoch für viele praktische Zwecke niemals ein negatives Kantengewicht geben wird, ist Dijkstra's Algorithmus zum Zwecke der Pfadfindung weitgehend geeignet.

A* Algorithmus

EIN* ist eine Variante des Dijkstra -Algorithmus, der üblicherweise in Spielen verwendet wird. A* weist jedem offenen Knoten ein Gewicht zu, das dem Gewicht der Kante zu diesem Knoten plus dem ungefähren Abstand zwischen diesem Knoten und dem Finish entspricht. Diese ungefähre Entfernung wird von der gefunden Heuristikund stellt einen minimal möglichen Abstand zwischen diesem Knoten und dem Ende dar. Dies ermöglicht es ihm, längere Pfade zu beseitigen, sobald ein Anfangspfad gefunden wurde. Wenn zwischen Start und Finish einen Pfad der Länge x und der minimale Abstand zwischen einem Knoten und dem Finish größer als X ist, muss dieser Knoten nicht untersucht werden.[4]

A* verwendet diese Heuristik, um das Verhalten im Vergleich zum Algorithmus von Dijkstra zu verbessern. Wenn die Heuristik auf Null bewertet, entspricht A* dem Algorithmus von Dijkstra. Wenn die heuristische Schätzung zunimmt und sich der wahren Entfernung nähert, findet A* weiterhin optimale Pfade, läuft jedoch schneller (aufgrund der Untersuchung weniger Knoten). Wenn der Wert der Heuristik genau die wahre Entfernung ist, untersucht A* die wenigsten Knoten. (Es ist jedoch im Allgemeinen unpraktisch, eine heuristische Funktion zu schreiben, die immer den wahren Abstand berechnet, da das gleiche Vergleichsergebnis häufig unter Verwendung einfacherer Berechnungen erreicht werden kann - zum Beispiel mit Verwendung Manhattan -Entfernung Über Euklidische Entfernung in Zweidimensionaler Raum.) Mit zunehmendem Wert der Heuristik untersucht A* weniger Knoten, garantiert jedoch keinen optimalen Weg mehr. In vielen Anwendungen (wie Videospielen) ist dies akzeptabel und sogar wünschenswert, um den Algorithmus schnell laufen zu lassen.

Probenalgorithmus

Dies ist ein ziemlich einfacher und leicht verständlicher Pfadalgorithmus für Kartenbasis. Zu Beginn haben Sie eine Karte, eine Startkoordinate und eine Zielkoordinate. Die Karte sieht so aus, X Wände sein, S der Start sein, O das Finish sein und _ Die Zahlen an den oberen und rechten Kanten sind die Spalten- und Zeilennummern:

  1 2 3 4 5 6 7 8 X X X X X X X X X X X _ _ _ X X _ X _ X 1 X _ X _ _ X _ _ _ X 2 X S X X _ _ _ X _ X 3 X _ X _ _ X _ _ _ X 4 X _ _ _ X x _ x _ x 5 x _ x _ _ x _ x _ x 6 x _ x _ _ _ x _ x 7 x _ _ _ x _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x 8 x x x x x x x x x

Erstellen Sie zunächst eine Liste von Koordinaten, die wir als Warteschlange verwenden werden. Die Warteschlange wird mit einer Koordinate, der Endkoordinate, initialisiert. Jede Koordinate wird auch eine Gegenvariable angeschlossen (der Zweck wird bald offensichtlich). Somit beginnt die Warteschlange als ((3,8,0)).

Gehen Sie dann jedes Element in der Warteschlange durch, einschließlich neuer Elemente, die am Ende des Algorithmus zum Ende hinzugefügt wurden, und machen Sie für jedes Element Folgendes:

  1. Erstellen Sie eine Liste der vier benachbarten Zellen mit einer Gegenvariablen der Gegenvariablen des Stromelements + 1 (in unserem Beispiel sind die vier Zellen ((2,8,1), (3,7,1), (4, 8,1), (3,9,1)))
  2. Überprüfen Sie alle Zellen in jeder Liste auf die folgenden zwei Bedingungen:
    1. Wenn die Zelle eine Wand ist, entfernen Sie sie aus der Liste
    2. Wenn in der Hauptliste ein Element mit derselben Koordinate vorhanden ist, entfernen Sie es aus der Zellliste
  3. Fügen Sie alle verbleibenden Zellen in der Liste zum Ende der Hauptliste hinzu
  4. Gehen Sie zum nächsten Element in der Liste

Daher lautet die Liste der Elemente nach Kurve 1: ((3,8,0), (2,8,1), (4,8,1)).

  • Nach 2 Kurven: ((3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2))
  • Nach 3 Kurven: (... (1,7,3), (4,6,3), (5,7,3))
  • Nach 4 Kurven: (... (1,6,4), (3,6,4), (6,7,4))
  • Nach 5 Kurven: (... (1,5,5), (3,5,5), (6,6,5), (6,8,5))
  • Nach 6 Kurven: (... (1,4,6), (2,5,6), (3,4,6), (6,5,6), (7,8,6))
  • Nach 7 Kurven: (... (1,3,7)) - Problem gelöst, beenden Sie diese Phase des Algorithmus - beachten Der Algorithmus soll dies einfacher machen), Sie können fortgesetzt werden, bis die gesamte Karte aufgenommen wird, alle Einheiten erreicht sind oder eine festgelegte Zählergrenze erreicht ist

Zeichnen Sie nun die Zähler auf die Karte ab und erhalten Sie Folgendes:

  1 2 3 4 5 6 7 8 x x x x x x x x x x x x _ _ _ x x _ x _ x 1 x _ _ _ x _ _ x 2 x s x _ _ _ x _ x 3 x 6 x 6 _ x _ _ _ _ x 4 x 5 6 5 x x 6 x _ x 5 x 4 x 4 3 x 5 x _ x 6 x 3 x 2 3 4 x _ x 7 x 2 1 0 1 x 5 6 _ x 8 x x x x x x x x x x x x x x x X x x x x x 2 x 2 1 x _ x 6 x x x x x x x x x _ x _ x _ x x x x x x x x 5 x 5 x _ x _ x x x x x x x x x _ x x x x x x x x x x x _ x x _)

Beginnen Sie nun bei s (7) und gehen Sie mit der niedrigsten Zahl in die nahe gelegene Zelle (ungeprüfte Zellen können nicht bewegt werden). Der verfolgte Pfad beträgt (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8,0). Für den Fall, dass zwei Zahlen gleich niedrig sind (z. B. wenn S bei (2,5)), wählen Sie eine zufällige Richtung - die Längen sind gleich. Der Algorithmus ist jetzt vollständig.

In Videospielen

Chris Crawford 1982 beschrieb er, wie er "viel Zeit aufgewendet" hat, um ein Problem mit dem Pfadfinding in zu lösen Tanktics, in denen Computertanks an Land in U-förmigen Seen gefangen wurden. "Nach viel verschwendeten Anstrengungen entdeckte ich eine bessere Lösung: U-förmige Seen aus der Karte löschen", sagte er.[5]

Hierarchische Pfadfindung

Quadtrees kann für hierarchische Pfadfindungen verwendet werden

Die Idee wurde zuerst von der beschrieben Videospielbranche, was eine Planung in großen Karten mit geringer Menge an Planung hatte CPU -Zeit. Das Konzept der Verwendung der Abstraktion und Heuristik ist älter und wurde erstmals unter dem Namen Abstrips erwähnt (Abstraktionsbasierte Streifen)[6] Dies wurde verwendet, um die staatlichen Räume von Logikspielen effizient zu durchsuchen.[7] Eine ähnliche Technik sind Navigationsnetz (Navmesh), die für die geometrische Planung in Spielen und multimodal verwendet werden Transportplanung welches in verwendet wird in Probleme mit reisenden Verkäufern mit mehr als einem Transportfahrzeug.

Eine Karte ist in getrennt in Cluster. Auf der hochrangigen Schicht ist der Weg zwischen den Clustern geplant. Nachdem der Plan gefunden wurde, ist innerhalb eines Clusters auf der unteren Ebene ein zweiter Weg geplant.[8] Das heißt, die Planung erfolgt in zwei Schritten, nämlich a Geführte lokale Suche im ursprünglichen Raum. Der Vorteil ist, dass die Anzahl der Anzahl von Knoten ist kleiner und der Algorithmus funktioniert sehr gut. Der Nachteil ist, dass ein hierarchischer Patplaner schwer zu implementieren ist.[9]

Beispiel

A Karte hat eine Größe von 3000x2000 Pixel. Die Planung eines Pfades auf einer Pixelbasis würde sehr lange dauern. Sogar effizient Algorithmus Muss viele mögliche Grafiken berechnen. Der Grund ist, dass eine solche Karte insgesamt 6 Millionen Pixel enthalten würde und die Möglichkeiten, den geometrischen Raum zu untersuchen, äußerst groß sind. Der erste Schritt für einen hierarchischen Pfadplaner besteht darin, die Karte in kleinere Submaps zu unterteilen. Jeder Cluster hat eine Größe von 300x200 Pixel. Die Anzahl der Cluster insgesamt beträgt 10x10 = 100. In der neu erstellten Grafik ist die Anzahl der Knoten gering. Es ist möglich, zwischen den 100 Clustern zu navigieren, jedoch nicht innerhalb der detaillierten Karte. Wenn ein gültiger Pfad im hochrangigen Graf gefunden wurde, besteht der nächste Schritt darin, den Pfad in jedem Cluster zu planen. Der Untermap hat 300x200 Pixel, die von einem Normalen behandelt werden können A* pathplanner leicht.

Algorithmen zur Pfadfindung

  • Dijkstra -Algorithmus
  • Ein* Suchalgorithmus, ein Sonderfall des Dijkstra -Algorithmus
  • D* eine Familie von Inkrementelle heuristische Suche Algorithmen für Probleme, bei denen die Einschränkungen im Laufe der Zeit variieren oder nicht vollständig bekannt sind, wenn der Agent Plant der erste seinen Weg
  • Any-angle path planning Algorithmen, eine Familie von Algorithmen für die Planung von Pfaden, die nicht darauf beschränkt sind, sich an den Kanten im Suchdiagramm zu bewegen, um einen beliebigen Winkel übernehmen zu können und somit kürzere und geradere Pfade zu finden

Multi-Agent-Pfadfinding

Hauptartikel: Multi-Agent-Pfadfinding

Multi-Agent-Pfadfindung besteht darin, die Pfade für mehrere Agenten von ihren aktuellen Standorten zu ihren Zielorten zu finden, ohne miteinander zu kollidieren, während gleichzeitig eine Kostenfunktion optimiert wird, z. B. die Summe der Pfadlängen aller Agenten. Es ist eine Verallgemeinerung der Pfadfindung. Viele Multi-Agent-Pfad-Algorithmen werden von einem*verallgemeinert oder auf der Reduzierung auf andere gut untersuchte Probleme wie die lineare Programmierung der Ganzzahl.[10] Solche Algorithmen sind jedoch typischerweise unvollständig; Mit anderen Worten, nicht nachweislich eine Lösung innerhalb der Polynomzeit zu erzeugen. Eine andere Kategorie von Algorithmen optimiert die Leistung für die Leistung, indem sie bekannte Navigationsmuster (wie Verkehrsfluss) oder die Topologie des Problemraums verwenden.[11]

Siehe auch

Verweise

  1. ^ "7.2.1 Problem mit der kürzesten Pfade für Einzelquellen: Dijkstra -Algorithmus". Archiviert von das Original am 2016-03-04. Abgerufen 2012-05-18.
  2. ^ Delling, D.; Sanders, P.; Schulte, D.; Wagner, D. (2009). "Algorithmen für technische Routenplanung". Algorithmik großer und komplexer Netzwerke: Design, Analyse und Simulation. Vorlesungsnotizen in Informatik. Vol. 5515. Springer. S. 117–139. Citeseerx 10.1.1.164.8916. doi:10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
  3. ^ "5.7.1 Dijkstra -Algorithmus".
  4. ^ "Einführung in eine* Pfadfindung".
  5. ^ Crawford, Chris (Dezember 1982). "Designtechniken und Ideen für Computerspiele". BYTE. p. 96. Abgerufen 19. Oktober 2013.
  6. ^ Sacerdoti, Earl D (1974). "Planung in einer Hierarchie von Abstraktionsräumen" (PDF). Künstliche Intelligenz. 5 (2): 115–135. doi:10.1016/0004-3702 (74) 90026-5.
  7. ^ Holte, Robert C und Perez, MB und Zimmer, RM und MacDonald, AJ (1995). Hierarchische A*. Symposium über Abstraktion, Neuformulierung und Näherung.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  8. ^ Pelechano, Nuria und Fuentes, Carlos (2016). "Hierarchische Pfadfindung für Navigationsnetze (HNA⁎)" (PDF). Computer & Grafiken. 59: 68–78. doi:10.1016/j.cag.2016.05.023. HDL:2117/98738.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  9. ^ Botea, Adi und Müller, Martin und Schaeffer, Jonathan (2004). "Nahe optimale hierarchische Pfadfindung". Journal of Game Development. 1: 7–28. Citeseerx 10.1.1.479.4675.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  10. ^ Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hoenig, T.K. Satish Kumar, Tansel Uras, Hong Xu, Craig Tovey und Guni Sharon. Übersicht: Verallgemeinerungen des Fundwerks mit mehreren Agenten auf reale Szenarien. In der 25. International Joint Conference on Artificial Intelligence (IJCAI) Workshop zum Thema Multi-Agent-Pfad. 2016.
  11. ^ Khorshid, Mokhtar (2011). "Ein Polynom-Zeit-Algorithmus für nicht optimale Multi-Agent-Pfadfindungen". SOCS.

Externe Links