160
Recherche de plus court chemin sur une carte
puis à éxécuter pendant quelques pas de temps le plan partiel trouvé par cette recherche,
puis à replanifier de nouveau à profondeur fixée.
8.4.4 Recherche temps-réél
La recherche temps-réé! permet de faire face au problème de l ' observation partielle
de l 'environnement. Elle consiste à intercaler la planification et l ' action. Real Time A*
(RTA *), Learning Real Time A * (LRTA *) [54] et Moving Target Search [46] sont des
algorithmes de recherche temps réél.
RTA * consiste à évaluer heuristiquement tous les voisins et à se déplacer vers le voisin
qui a la meilleure évaluation.
Une amélioration de RTA * est Learning Real Time A* qui met à jour l 'évaluation
heuristique de chaque état lorsque les déplacements amènent à se rendre compte que
l ' heuristique admissible était trop optimiste. Ainsi si un état a une évaluation de 3 et que
le meilleur déplacement coute l et se déplace vers un état qui a une évaluation de 3, on
peut augmenter ! 'évaluation du premier état de 3 à 4. LRTA * est sûr de trouver le but dans
un espace d'états fini.
Algorithm 8 Recherche d' un chemin sur une carte avec l ' algorithme LRTA *
nouvellePosition (prevPos, pos)
if prevPos -:/:- pos then
best +--- heuristique [pos] + 1
for tous les voisins de prevPos do
if heuristique [voisin] + 1 < best then
best +--- heuristique [voisin] + 1
end if
end for
heuristique [prevPos] +--- best
end if
retourner le voisin qui a la plus petite valeur pour heuristique[ voisin]
LRTA * (pas)
for tous les points de la carte do
heuristique [point] +--- h(point)
end for
prev +--- pos
white pos -:/:- arrivee do
p +--- pos
pos +--- nouvellePosition (prev, pos)
prev +--- p
end white
Une preuve de complétude de LRTA * [45] utilise la fonction h* (x) qui donne pour
l 'état x le coût du plus court chemin vers le but. On a toujours h( x) < h * ( x) puisque h est