Leistungsmetriken heuristischer Suchalgorithmen in Grid-Umgebungen

3 Experimentelle Umgebung und Leistungsmetriken

Heuristische Suchalgorithmen spielen eine wichtige Rolle in Bereichen wie der robotischen Wegfindung, da sie den optimalen Weg bei einer vorgegebenen Start- und Zielposition bestimmen. Gitterbasierte Umgebungen werden häufig zur Darstellung realer Umgebungsszenarien verwendet, in denen diese Algorithmen implementiert werden können, wie etwa bei der autonomen Navigation und Robotik [6]. In dieser Studie analysieren wir umfassend bekannte heuristische Suchalgorithmen, nämlich D*, D* Lite, LPA*, LRTA*, RTAA* und ARA* in verschiedenen Gitterumgebungen. Wir verwenden die euklidische Distanzheuristik, um die Suche der Algorithmen zu steuern und bewerten die Auswirkungen einiger Gittereigenschaften, wie etwa der Hindernisdichte und der Gittergröße, auf die Leistung der Algorithmen.

In unserer Studie verwenden wir gitterbasierte Umgebungen aufgrund ihrer Einfachheit und Bedienbarkeit. Außerdem werden sie in der Forschungsgemeinschaft häufig für Pfadplanungsaufgaben verwendet. Die Gitter bestehen aus weißen Zellen, die durchquerbare Zustände darstellen, während die schwarzen Zellen nicht durchquerbare Hindernisse darstellen. Der Agent in unserer Simulation kann sich in acht Richtungen bewegen, wobei die Kosten für horizontale und vertikale Bewegungen 1 und für diagonale Bewegungen √ 2 betragen. Wir haben zwei Arten von Gitterumgebungen verwendet: zufällig generierte Gitterumgebungen und personalisierte Gitterumgebungen.

Zufällig generierte gitterbasierte Umgebungen: Die Gitter werden durch drei Parameter charakterisiert:

Gittergröße (NxN), Hindernisdichte und Distanz zwischen Start- und Zielzustand. Um die Auswirkungen jedes Parameters auf die Leistung der Suchalgorithmen zu untersuchen, haben wir jeden Parameter unabhängig variiert, während die anderen Parameter konstant blieben. Die Variationen umfassten die Variation der Gittergröße, die Variation der Start-Ziel-Distanz und die Variation der Hindernisdichte. Für jedes Gitter in einer Variation haben wir zehn zufällige Instanzen derselben Gitterparameter generiert (z. B. hat ein Gitter mit 0,25 Hindernisdichte, Größe 300x300 und 140 Start-Ziel-Distanz zehn Instanzen, die zufällig generiert wurden).

Personalisierte Gitterumgebung: Entwickelt für die Simulation spezifischerer Szenarien. Diese Gitter haben eine feste Größe (71 x 31 Einheiten) und eine feste Position sowohl für den Start- als auch für den Zielzustand und wurden basierend auf ihrer Hinderniskonfiguration in zwei Teile unterteilt:

• Horizontale Wandkonfiguration: Für diese Experimente fügen wir alle 10 Einheiten der Rasterlänge horizontale Wände mit halber Rasterbreite hinzu. Wir haben die Wände in zwei Ausrichtungen hinzugefügt: einmal von links nach rechts und einmal von rechts nach links im neu generierten Raster.

• Horizontale Wandlängenkonfiguration: Hier fügen wir alle möglichen Wände hinzu, die innerhalb

die Rasterlänge, und jedes Mal, wenn wir ein neues Raster generieren, erhöhen wir alle Wandlängen um 2 Einheiten.

Wir haben diese beiden unterschiedlichen Umgebungen übernommen, um eine gründliche Analyse zu ermöglichen und differenzierte Einblicke in die Leistung des Suchalgorithmus bei zwei unterschiedlichen Hindernisszenarien zu erhalten. Im ersten Szenario sind die Hindernisse zufällig im Raster verstreut, während im zweiten Szenario die wandähnlichen Strukturen als Masse verbundener Hindernisse erscheinen.

Um die Leistung der verschiedenen in den Experimenten verwendeten Suchalgorithmen zu bewerten, haben wir die folgenden Metriken ausgewählt:

• Pfadkosten: Die Metrik misst die Pfadlänge bzw. die Anzahl der ausgeführten Aktionen vom Start- bis zum Zielzustand. Sie gibt Aufschluss über die Qualität der Lösung.

• Speicherverbrauch: Er misst die Speichermenge, die der Algorithmus benötigt, um eine Lösung zu finden. Er ist relevant, um die Skalierbarkeit des Algorithmus zu prüfen, und wird in (KB) gemessen.

• Lösungszeit: Stellt die Gesamtzeit dar, die ein Algorithmus benötigt, um eine Lösung zu finden (ms), gemessen in Millisekunden (ms).

Wir haben unsere Experimente auf 3,30 GHz 27 Intel i9-Kernen durchgeführt, die mit 250 GB RAM ausgestattet waren und Ubuntu Linux 22.04 ausführten. Dabei haben wir die folgenden Einstellungen verwendet: Alle Algorithmen verwendeten die euklidische Distanz als heuristische Funktion. Für LRTA* und RTAA* haben wir die Anzahl der verbrauchten Knoten für jede Iteration auf 250 gesetzt. Der ARA*-Algorithmus wurde mit einem Gewicht von 2,5 für die Heuristik ausgeführt. Wir haben jeden Algorithmus 100 Mal auf jedem Raster ausgeführt, um die Zufälligkeit zu berücksichtigen und die Zuverlässigkeit der Ergebnisse sicherzustellen.