CHAPITRE 3
d'optimisation. Le but de ce processus est d'attribuer une
probabilité d'occupation à chaque cellule de la carte. Afin
d'atteindre cet objectif, le robot doit maximiser la surface de la zone
explorée tout en minimisant l'énergie utilisée.
Le rôle des métaheuristiques dans notre
modélisation est au coeur de ce processus. Elles commencent par
générer une population aléatoire de points de destination
à visiter, puis améliorent la position de ces points cibles
à travers une succession d'opérations d'optimi-sation.
Mathématiquement, chaque solution candidate Xk
dans la population représente un ensemble d'emplacements de cellules
cibles Cij, où (i, j) sont les coordonnées
(x, y) à l'in-térieur des limites de la grille.
X = Cij
Par conséquent, la fonction fitness peut être
modélisée comme une maximisation du nombre de cellules qui ont
une valeur d'occupation logarithmique égale à 0 (cellules
inexplorées). L'équation 3.5 définit la formulation
mathématique de cette fonction.
F = max(Observed Cells)
X= min( ä(Cij,0)) (3.5)
i,j
|
Where ä(Cij,0) =
|
?
??
??
|
1 if Occ(Cij) =? 0
0 otherwise
|
Avec la contrainte suivante:
X E(Cij) < current battery
level i,j
Où E(Cij) est l'énergie
nécessaire pour déplacer le robot de la position actuelle
à la cellule Cij.
La figure 3.10 montre un exemple d'application de cette
opération pour sélectionner le meilleur ensemble d'emplacements
cibles à visiter parmi 4 solutions candidates.
Une fois que le meilleur ensemble d'emplacements cibles qui
satisfait la contrainte d'énergie est trouvé, le robot calcule le
chemin le plus court qui relie ces emplacements cibles en utilisant
l'algorithme A* [46], puis il exécute ce chemin
jusqu'à visiter tous les emplacements cibles. Après cela, il
répète l'algorithme d'optimisation pour générer un
nouvel ensemble d'emplacements à visiter et continue le processus
jusqu'à ce que toutes les cellules de la carte aient été
observées (c'est-à-dire que le robot a exploré toute la
zone).
Il est important de rappeler que la trajectoire prévue
n'est pas nécessairement optimale, puisque le robot ne peut pas
détecter les obstacles hors de portée de ses capteurs. De
plus,
Selecting Goals:
Yes
Generate a set of target locations using xBOA (or any other
metaheuristic)
Path Planning:
Plan a path toward the next target
location using A*
Path Execution:
Move toward the target location
Obstacles Detection:
Scan the environment using Lidar sensor
and detect the
surrounding obstacles
J
Mapping:
Update the occupancy probability of the
grid cells
r ~
Path Updating:
Plan an alternative path
avoiding
the obstacle
l J
99
FIGURE 3.11 -- Diagramme du processus
d'exploration d'une zone inconnue
100
| 
