CHAPITRE 4
*Les résultats présentent les valeurs
moyennes de 10 exécutions
FIGURE 4.4 - Résultats de la simulation de la mission
d'exploration en utilisant la stratégie à court terme
115
Exploration rate -- Empty Map
20 40 60 80 100 120 140 160
Step number
Exploration rate -- House Map
80 -
60 -
ABC
t BOA CMAES GA
- 1- GWO
- c- PS
t XBOA
20 -
200 250
1E:D 150
Step number
*Les résultats présentent les valeurs
moyennes de 10 exécutions
FIGURE 4.5 -- Résultats de la simulation
de la mission d'exploration en utilisant la stratégie à long
terme
116
CHAPITRE 4
Nous remarquons dans les résultats
présentés par ces figures la présence de plusieurs pics
sur l'axe du temps de calcul. Ces pics correspondent au temps requis par le
robot pour calculer les prochains points à visiter en utilisant l'une
des métaheuristiques, sachant que le robot est figé pendant ce
temps puisqu'il n'a pas encore de point de destination pour pouvoir planifier
un chemin de déplacement. Nous remarquons aussi que le temps de calcul
pendant le déplacement du robot est relativement négligeable,
ceci s'explique par le fait que le robot ne nécessite pas d'effectuer
des opérations de calculs compliquées pendant le
déplacement puisque cette phase se limite à mesurer la distance
avec l'obstacle le plus proche pour éviter les collisions ainsi que la
mise à jour des probabilités d'occupation dans la carte.
Bien que les méthodes xBOA, GA et ABC donnent de
meilleurs résultats en termes de taux d'exploration comparés
à BOA, elles nécessitent un temps de calcul plus long. Ceci
s'explique par la simplicité des opérations de l'algorithme BOA
et sa complexité réduite comparée aux autres
méthodes. Les résultats présentés dans la Figure
4.8 renforcent cette explication; nous observons clairement que le temps de
calcul de la méthode BOA est inférieur à celui de xBOA, GA
et ABC, et que le nombre d'appels à la fonction de fitness (fitness
evaluations) est inférieur.
Nous observons aussi que la méthode ABC requiert un
temps de calcul considérable dans toutes les expériences, qui est
supérieur au double du temps requis par les autres méthodes. Ceci
est causé par la nature de l'algorithme ABC qui est divisé en 3
phases dont chacune nécessite la réévaluation des
individus, ce qui conduit à un grand nombre d'exécu-tions de la
fonction objectif. Cette lenteur le rend inadapté aux scénarios
en situation réelle, car les robots ne doivent pas rester
immobilisés pendant une longue période.
Par ailleurs, nous remarquons que la méthode CMAES
domine les autres méthodes sur le critère du temps de calcul,
mais elle est parfois dominée par la méthode BOA en termes de
taux d'exploration, alors que cette dernière est elle-même
dominée par xBOA dans tous les scénarios sur ce même
critère. La méthode GWO est elle aussi dominée par xBOA
sur ce critère, mais elle enregistre un temps de calcul plus rapide.
Il est important de noter à partir de la figure 4.8 que
le temps de calcul moyen pour sélectionner le prochain point de
destination est relativement long; moyennant 150 à 450 secondes durant
lesquelles le robot est à l'arrêt en attendant le résultat
du processus d'opti-misation. Ceci n'est pas recommandé pour des
scénarios où le temps est un facteur critique tel que les
missions de sauvetage par exemple. Deux potentielles solutions sont possibles
dans ce cas. La première consiste à profiter des
fonctionnalités de parallélisme offertes par les processeurs
modernes pour évaluer plusieurs individus de la population en même
temps. Des résultats préliminaires nous ont permis de
réduire de moitié le temps d'exécution en utilisant cette
technique.
La deuxième stratégie consiste à
réduire la taille de la population, ce qui revient donc à
réduire le nombre de solutions candidates évaluées par la
fonction objectif. Dans la série d'expériences suivante, nous
allons analyser l'impact de cette deuxième stratégie sur la
qualité des solutions générées.
117
Execution time -- Empty Map
1000 -
A
4000 -
3000 -
V
N
0
2000 -
·
·
·
·
·
·
·
·
· t
·
·
·
0
·
·
tt~+ir
-ç
· t
· ABC
t BOA t CMAES t GA
-
· - GWO -X- PSO
t XBOA
0 20 40 60 80
Exploration rate
Execution time -- House Map
·
·
· ABC
- 0- BOA CMAES GA
-
·- GWO -~ Pso
t XBOA
4000 -
3000 -
2000 -
1000 -
0 10 20 30 40 50 60 70 80
Exploration rate
*Les résultats présentent les valeurs
moyennes de 3 exécutions
FIGURE 4.6 -- Comparaison de la durée
totale de la mission d'exploration pour la stratégie à court
terme
118
| 
