Auteurs:  (1) Aya Kherrour, Département d'ingénierie de l'information et d'informatique de l'Université de Trente ;  (2) Marco Robol, Département d'ingénierie de l'information et d'informatique de l'Université de Trente ;  (3) Marco Roveri, Département d'ingénierie de l'information et d'informatique de l'Université de Trente ;  (4) Paolo Giorgini, Département d'ingénierie de l'information et d'informatique de l'Université de Trente.  3 Environnement expérimental et mesures de performance  Les algorithmes de recherche heuristique jouent un rôle important dans des domaines tels que la recherche de chemin robotique, car ils déterminent le chemin optimal en fonction d'une position de départ et d'une position cible. Les environnements basés sur une grille sont couramment utilisés pour représenter des scénarios d'environnement réels, dans lesquels ces algorithmes peuvent être implémentés, comme dans la navigation autonome et la robotique [6]. Dans cette étude, nous analysons de manière approfondie des algorithmes de recherche heuristiques bien connus, à savoir D*, D* Lite, LPA*, LRTA*, RTAA* et ARA* dans différents environnements de grille. Nous utilisons l'heuristique de distance euclidienne pour guider la recherche des algorithmes et évaluer l'impact de quelques caractéristiques de la grille, telles que la densité d'obstacles et la taille de la grille, sur les performances des algorithmes.  Dans notre étude, nous utilisons des environnements basés sur une grille en raison de leur simplicité et de leur facilité de contrôle, en plus d'être couramment utilisés dans les tâches de planification de chemin dans la communauté de recherche. Les grilles sont composées de cellules blanches, représentant des états traversables, tandis que les noires représentent des obstacles non franchissables. L'agent de notre simulation peut se déplacer dans huit directions, avec un coût égal à 1 pour les mouvements horizontaux et verticaux, et à √ 2 pour les mouvements diagonaux. Nous avons utilisé deux types d'environnements de grille : des environnements de grille générés aléatoirement et des environnements de grille personnalisés.    les grilles sont caractérisées par trois paramètres : Environnements basés sur des grilles générés aléatoirement :  la taille de la grille (NxN), la densité des obstacles et la distance entre le départ et l'objectif. Pour étudier l'impact de chaque paramètre sur les performances des algorithmes de recherche, nous avons fait varier chaque paramètre indépendamment tout en gardant les autres paramètres constants. Les variations comprenaient la variation de la taille de la grille, la variation de la distance du début au but et la variation de la densité des obstacles. Pour chaque grille d'une variante, nous avons généré dix instances aléatoires des mêmes paramètres de grille (par exemple, une grille avec 0,25 de densité d'obstacles, une taille de 300 x 300 et 140 de distance du début à l'objectif, a dix instances générées de manière aléatoire).    conçu pour simuler des scénarios plus spécifiques. Ces grilles ont une taille fixe (71x31 unités) et une position fixe pour les états de départ et d'objectif, et elles ont été divisées en deux parties en fonction de leur configuration d'obstacles : Environnement de grille personnalisé :  •   Pour ces expériences, nous ajoutons des murs horizontaux d'une demi-largeur de grille toutes les 10 unités de longueur de grille. Nous avons ajouté les murs dans deux orientations : une fois de gauche à droite et une fois de droite à gauche dans la grille nouvellement générée. Configuration de murs horizontaux :  •   ici, nous ajoutons tous les murs possibles pouvant être placés à l'intérieur. Configuration de la longueur du mur horizontal :  la longueur de la grille, et chaque fois que nous générons une nouvelle grille, nous augmentons toutes les longueurs des murs de 2 unités.  Nous avons adopté ces deux environnements distincts pour fournir une analyse approfondie, cherchant à révéler des informations nuancées sur les performances de l'algorithme de recherche en présence de deux scénarios gênants différents. Dans le premier, les obstacles sont dispersés de manière aléatoire dans la grille, tandis que dans le second, les structures en forme de murs apparaissent comme une masse d'obstacles connectés.  Pour évaluer les performances des différents algorithmes de recherche utilisés dans les expériences, nous avons sélectionné les métriques suivantes :  •   la métrique mesure la longueur du chemin ou le nombre d'actions exécutées depuis le début jusqu'à l'état objectif. Il indique la qualité de la solution. Coût du chemin :  •   Elle mesure la quantité de mémoire requise pour que l'algorithme trouve une solution. Il est pertinent de vérifier la scalabilité de l’algorithme, et elle se mesure en (Ko). Consommation de mémoire :  •   représente le temps total nécessaire à un algorithme pour trouver une solution en (ms), mesuré en millisecondes (ms). Temps de résolution :  Nous avons réalisé nos expérimentations sur 27 cœurs Intel i9 cadencés à 3,30 GHz, équipés de 250 Go de RAM et exécutant Ubuntu Linux 22.04. Utilisation des paramètres suivants : Tous les algorithmes utilisaient la distance euclidienne comme fonction heuristique. Pour LRTA* et RTAA*, nous fixons le nombre de nœuds dépensés à 250 pour chaque itération. L'algorithme ARA* a été exécuté avec un poids de 2,5 pour l'heuristique. Nous avons exécuté chaque algorithme 100 fois sur chaque grille pour tenir compte du caractère aléatoire et garantir la fiabilité des résultats.  Cet article est   sous licence CC 4.0. disponible sur arxiv

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

EScholar Technologies

EScholar

Cet audio est produit dans la langue originale de l'histoire !

Trop long; Pour lire

Boost your HackerNoon story @ $159.99! 🚀

Mesures de performance des algorithmes de recherche heuristiques dans les environnements de grille

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Valhalla de Floki se joint en tant que sponsor associé de la tournée indienne au Sri Lanka

La fuite de l'invite du système Claude Sonnet 3.5 : une analyse médico-légale

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Valhalla de Floki se joint en tant que sponsor associé de la tournée indienne au Sri Lanka

La fuite de l'invite du système Claude Sonnet 3.5 : une analyse médico-légale

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps