Inkrementelle heuristische Suche ist eine Familie von Algorithmen in der künstlichen Intelligenz, die sich mit dem Problem befasst, einen Pfad in einem Graphen zu finden, wenn sich der Graph im Laufe der Zeit ändert. Im Gegensatz zu klassischen heuristischen Suchmethoden wie A*, die bei jeder Änderung der Umgebung eine vollständige Lösung von Grund auf neu berechnen, nutzen inkrementelle heuristische Suchalgorithmen so viele Informationen wie möglich aus früheren Suchbemühungen wieder. Diese Wiederverwendung kann die Rechenkosten in dynamischen oder teilweise bekannten Umgebungen drastisch reduzieren, was sie besonders wertvoll für Anwendungen wie Roboternavigation, Wegfindung in Videospielen und Routenplanung autonomer Fahrzeuge macht.
Die Kernidee besteht darin, eine heuristische Funktion und einen Suchbaum zu pflegen, die inkrementell aktualisiert werden, wenn sich Kantenkosten ändern oder neue Hindernisse entdeckt werden. Wenn eine Änderung auftritt, identifiziert der Algorithmus, welche Teile der vorherigen Suche noch gültig sind und welche überarbeitet werden müssen, und propagiert dann die notwendigen Aktualisierungen. Dieser Ansatz steht im Gegensatz sowohl zur klassischen heuristischen Suche (die einen statischen Graphen annimmt) als auch zur inkrementellen Suche ohne Heuristiken (die Pfade wiederverwenden kann, aber die Führung durch eine Heuristik vermissen lässt).
Historische Entwicklung
Die Grundlagen der inkrementellen heuristischen Suche wurden Ende der 1990er und Anfang der 2000er Jahre gelegt. Der einflussreichste Algorithmus, D Lite, wurde 2002 von Sven Koenig und Maxim Likhachev eingeführt. D Lite basiert auf dem früheren D-Algorithmus, der 1994 von Anthony Stentz entwickelt wurde und für die Navigation mobiler Roboter konzipiert war. D Lite vereinfacht das ursprüngliche D*, während es dessen Effizienz beibehält, und ist zu einem Standardreferenzpunkt in diesem Bereich geworden.
Ein weiterer wichtiger Algorithmus ist Lifelong Planning A (LPA), ebenfalls von Koenig und Likhachev im Jahr 2001 eingeführt. LPA behandelt Änderungen der Kantenkosten, während die Heuristik konsistent bleibt, und bildet die Grundlage für D Lite. Das Feld hat sich seitdem mit Varianten wie Generalized Adaptive A (GAA) und Anytime D* erweitert, die Lösungsqualität gegen Rechenzeit abwägen.
Algorithmische Prinzipien
Inkrementelle heuristische Suchalgorithmen pflegen typischerweise zwei Arten von Werten für jeden Knoten: einen g-Wert (die Kosten des besten bekannten Pfads vom Start) und einen h-Wert (die heuristische Schätzung zum Ziel). Sie verfolgen auch, ob ein Knoten konsistent ist, was bedeutet, dass sein g-Wert dem Minimum über seine Vorgänger entspricht. Wenn sich Kantenkosten ändern, aktualisiert der Algorithmus die g-Werte betroffener Knoten und propagiert Änderungen durch den Suchbaum mithilfe einer Prioritätswarteschlange, die nach f = g + h geordnet ist.
Die wichtigste Neuerung ist die Verwendung eines "rhs-Werts" (rechtsseitiger Wert) in LPA und D Lite, der das Minimum der g-Werte der Vorgänger plus der Kantenkosten darstellt. Ein Knoten ist lokal konsistent, wenn sein g-Wert seinem rhs-Wert entspricht. Der Algorithmus pflegt eine Liste lokal inkonsistenter Knoten und verarbeitet sie in der Reihenfolge ihres Schlüssels, der ein Paar (min(g, rhs) + h, min(g, rhs)) ist. Dies stellt sicher, dass nur die notwendigen Teile der Suche neu berechnet werden.
Anwendungen in Robotik und KI
Inkrementelle heuristische Suche wird in der Robotik häufig für die Pfadplanung in unbekannten oder sich ändernden Umgebungen eingesetzt. Beispielsweise kann ein Roboter, der ein Gebäude erkundet, zunächst einen Pfad basierend auf einer Karte planen, aber wenn er neue Hindernisse entdeckt (z. B. geschlossene Türen), kann er seinen Plan inkrementell aktualisieren, ohne neu zu starten. Dies ist entscheidend für die Echtzeitnavigation, bei der die Rechenzeit begrenzt ist.
In Videospielen müssen Nicht-Spieler-Charaktere (NPCs) oft durch dynamische Gelände mit sich bewegenden Hindernissen oder sich ändernden Zielen navigieren. Inkrementelle heuristische Suche ermöglicht effiziente Neuplanung und verbessert die Reaktionsfähigkeit des Spiels. Die Technik wird auch in der Logistik angewendet, wo Lieferrouten sich an Verkehrsbedingungen anpassen müssen, sowie in der Netzwerk-Routing, wo Verbindungskosten schwanken.
Vergleich mit anderen Suchmethoden
Die klassische A-Suche ist optimal und vollständig für statische Graphen, aber sie ist in dynamischen Umgebungen ineffizient, weil sie alle früheren Arbeiten verwirft, wenn sich der Graph ändert. Inkrementelle heuristische Suche behält die Optimalitätsgarantien von A bei, während sie frühere Berechnungen wiederverwendet. Sie erfordert jedoch zusätzlichen Speicher, um den Suchbaum und Konsistenzinformationen zu speichern.
Ein weiterer verwandter Ansatz ist die Anytime-Suche, die darauf abzielt, schnell eine gute Lösung zu finden und sie dann mit mehr Zeit zu verbessern. Einige inkrementelle Algorithmen, wie Anytime D*, kombinieren beide Eigenschaften: Sie können schnell eine suboptimale Lösung zurückgeben und sie verfeinern, wenn Zeit verfügbar ist. Dies ist besonders nützlich in zeitkritischen Anwendungen.
Aktuelle Forschung und zukünftige Richtungen
Die aktuelle Forschung zur inkrementellen heuristischen Suche konzentriert sich auf die Skalierung auf sehr große Graphen, die Behandlung kontinuierlicher Zustandsräume und die Integration mit maschinellem Lernen. Beispielsweise können lernbasierte Heuristiken verwendet werden, um die anfänglichen h-Werte zu verbessern und die Anzahl der Expansionen zu reduzieren. Es gibt auch Arbeiten zur Parallelisierung der inkrementellen Suche für Mehrkernprozessoren und zur Kombination mit sampling-basierten Planern wie RRT* für hochdimensionale Probleme.
Im Kontext moderner Systeme der künstlichen Intelligenz bleibt die inkrementelle heuristische Suche für verkörperte Agenten relevant, wie etwa in Waymo-Fahrzeugen oder Tesla-Autopilot-Systemen, wo Echtzeit-Neuplanung unerlässlich ist. Die Prinzipien beeinflussen auch die Forschung im Bereich maschinelles Lernen und tiefes Lernen für das Lernen zu suchen, obwohl die klassischen Algorithmen weiterhin der Standard für garantierte Optimalität sind.
Siehe auch
Referenzen
- Koenig, S., & Likhachev, M. (2002). D* Lite. Proceedings of the National Conference on Artificial Intelligence.
- Koenig, S., & Likhachev, M. (2001). Lifelong Planning A*. Artificial Intelligence.
- Stentz, A. (1994). Optimal and Efficient Path Planning for Partially-Known Environments. IEEE International Conference on Robotics and Automation.