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

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.

Environnements basés sur des grilles générés aléatoirement : les grilles sont caractérisées par trois paramètres :

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).

Environnement de grille personnalisé : 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 :

• Configuration de murs horizontaux : 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 la longueur du mur horizontal : ici, nous ajoutons tous les murs possibles pouvant être placés à l'intérieur.

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 :

• Coût du chemin : 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.

• Consommation de mémoire : 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).

• Temps de résolution : représente le temps total nécessaire à un algorithme pour trouver une solution en (ms), mesuré en millisecondes (ms).

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.