I.2.3. Recherche d'une solution (calcul d'un plan)
Pour déterminer la suite d'opérateurs (le plan)
qui permet de passer de la description de l'état initial à un
état qui satisfait le but, le planificateur peut utiliser, selon sa
conception, différentes stratégies (algorithmes) de recherche :
la recherche dans un espace d'états et la recherche dans un espace de
plans.
appliqués pour passer d'un état à un
autre. Le travail effectué par le planificateur pour dresser le plan
peut être représenté par un graphe de recherche qui est un
sous graphe du graphe d'états représentant le problème
à résoudre. Pour parcourir l'espace d'états, le
planificateur peut utiliser différentes méthodes : la recherche
par chaînage avant, par chaînage arrière ou
bidirectionnelle.
La recherche par chaînage avant
(Forward) : Cette approche est
appelée planification progressive puisqu'elle se déplace
vers l'avant. Elle consiste, en partant de l'état initial, à
trouver par essais successifs une suite d'actions qui permette d'arriver
à un état but. Le plan-solution est la suite des
opérateurs étiquetant les arcs du chemin-solution, chemin qui
mène de l'état initial à l'état-but. L'approche
peut être élaboré par l'algorithme ci-dessous [10]. L'appel
Forward(s0, Sg, nil) retourne un chemin de G (graphe d'états)
de s0 à un état de Sg, s'il existe un tel chemin. L'étape
de choix est non-déterministe, elle correspond à un
retour arrière en cas d'échec.
Forward (s, Sg, path)
si sE Sg alors retourner(path)
sinon soit applicables - {a? A| s ??
pré(a)} si applicables = 0 retourner (échec) sinon
Choix a E applicables
retourner (Forward(a(s), Sg, path.a))
|
|
Algorithme1.2: algorithme de planification
par chaînage avant
La recherche par chaînage arrière
(Backward) : Cette approche est
appelée planification régressive puisqu'elle se
déplace vers l'arrière. Elle consiste à parcourir le
graphe de recherche du problème, non pas en partant de l'état
initial, mais en partant du but (qui doit donc être explicitement connu)
et en appliquant l'inverse des opérateurs de planification pour produire
des sous-buts jusqu'à arriver à l'état initial. Si
l'algorithme permet de remonter à cet état initial, alors il
retourne le plan solution trouvé.
L'approche peut être élaborée par
l'algorithme ci-après [10]. L'algorithme choisit une proposition but
particulière << g >> parmi les buts courants
<< y >> et une action pertinente pour ce
but. Une action est dite pertinente pour un objectif conjonctif si
elle accomplit un des conjoints de l'objectif.
La fonction <<
Regression(a, y) >> est définie
comme suit : Ayant un ensemble y de propositions décrivant les
buts, la régression de a relativement à y
cherche un ensemble y' de propositions telles que tout état s
qui les comporte soit dans le domaine de définition de a et
conduise à un état où y est satisfaite :
Regression(a, ?) = y' tel que y' ?=
pré(a) et sE M(y'): a(s) ?? ?
Backward(s0, y , path)
si s0 |= y alors retourner(path)
sinon Choix de g E 7
soit pertinentes -- {a E A | eff(a) |= g}
si pertinentes = 0 alors retourner (échec) sinon
Choix de a E pertinentes
soit y' - Regression(a, ?)
retourner (Backward(s0, y', a.path))
|
|
Algorithme1.3: algorithme de planification
par chaînage arrière
La recherche bidirectionnelle : consiste
à utiliser simultanément les techniques de recherche avant et
arrière jusqu'à rencontrer un état commun aux deux
processus. Le plan-solution est alors la suite des opérateurs qui
permettent de passer de l'état initial à l'état commun
plus l'inverse de la suite des opérateurs qui mènent du but
à l'état commun. Cette méthode nécessite la
connaissance explicite du but.
I.2.3.2. Recherche dans un espace de plans :
Dans l'approche de la planification dans un espace de plans, l'espace
de recherche n'est plus un ensemble d'états du monde mais un espace de
plans partiels dont les noeuds représentent des plans partiellement
spécifiés et les arcs sont des opérations de raffinement
de plans, i.e., qui permettent de réaliser un but ouvert ou d'enlever
une inconsistance potentielle (par exemple lorsque deux actions sont en
conflit) [1]. Cette approche obéit au paradigme de la
décomposition de but, i.e, le problème initial (but à
atteindre) est décomposé en sous-problèmes plus simples
(grâce à l'utilisation de règles de décomposition);
ceux-ci sont à nouveau décomposés, et ainsi de suite
jusqu'à l'obtention de problèmes terminaux (tous solubles par des
actions élémentaires) [9].
| 
