Autoren:  (1) Aya Kherrour, Fakultät für Informationstechnik und Informatik der Universität Trient;  (2) Marco Robol, Fakultät für Informationstechnik und Informatik der Universität Trient;  (3) Marco Roveri, Fakultät für Informationstechnik und Informatik der Universität Trient;  (4) Paolo Giorgini, Fakultät für Informationstechnik und Informatik der Universität Trient.  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.    Die Gitter werden durch drei Parameter charakterisiert: Zufällig generierte gitterbasierte Umgebungen:  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).    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: Personalisierte Gitterumgebung:  •   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 Wandkonfiguration:  •   Hier fügen wir alle möglichen Wände hinzu, die innerhalb Horizontale Wandlängenkonfiguration:  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:  •   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. Pfadkosten:  •   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. Speicherverbrauch:  •   Stellt die Gesamtzeit dar, die ein Algorithmus benötigt, um eine Lösung zu finden (ms), gemessen in Millisekunden (ms). Lösungszeit:  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.  Dieses Dokument ist   . auf Arxiv unter der CC 4.0-Lizenz verfügbar

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Zu lang; Lesen

Boost your HackerNoon story @ $159.99! 🚀

Leistungsmetriken heuristischer Suchalgorithmen in Grid-Umgebungen

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

HackerNoon Decoded 2024: Celebrating Our Programming Community!

HackerNoon Decoded 2024: Wir feiern unsere Produktmanagement-Community!

Starting 2025 with New Features: Settings Dashboard, HackerNoon Decoded, Updated Search UI, and More

HackerNoon Decoded 2024: Celebrating Our Writing Community!

HackerNoon Decoded 2024: Celebrating Our Programming Community!

HackerNoon Decoded 2024: Wir feiern unsere Produktmanagement-Community!

Starting 2025 with New Features: Settings Dashboard, HackerNoon Decoded, Updated Search UI, and More

HackerNoon Decoded 2024: Celebrating Our Writing Community!

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps