Diagnostic de la violation de la structure du plan et de l’´echec des actions

Télécharger le fichier pdf d’un mémoire de fin d’études

Repr´esentation classique du domaine de la planification

Dans la litt´erature, il y a trois fa¸cons diff´erentes de repr´esenter un probl`eme classique de planification. Elles sont ´equivalentes en pouvoir d’expression dans le sens o`u chaque domaine de planification repr´esent´ dans l’une d’entre elles peut ˆetre repr´esent´ dans les deux autres, avec au plus une augmentation lin´eaire de la taille [Nebel, 1998].
1. la repr´esentation dans la th´eorie des ensembles (Set-theoretic represenation) [Green, 1969] : chaque ´etat du monde est un ensemble de propositions et chaque action est une expression sp´ecifiant les propositions qui doivent appartenir a` l’´etat courant pour que l’action soit ex´ecutable, ainsi que les propositions a` ajouter ou a` supprimer de l’´etat suite a` l’ex´ecution de l’action ;
2. la repr´esentation classique (Classical representation) [Fikes et Nilsson, 1971] : les ´etats et les actions sont semblables a` ceux d´ecrits pour la repr´esentation dans la th´eorie des ensembles. Des pr´edicats du premier ordre et des connecteurs logiques sont utilis´es a` la place des propositions ;
3. la repr´esentation par des variables d’´etats (state variable representation) : chaque ´etat est repr´esent´ par un tuple de n variables d’´etats valu´ees {x1, …, xn} et chaque action est repr´esent´ee par une fonction partielle pour passer entre deux variables d’´etats instanci´es.
Un avantage de la repr´esentation dans la th´eorie des ensembles est qu’elle offre une repr´esentation plus lisible du syst`eme de transition d’´etats. Par contre, cette repr´esentation peut prendre plus d’espace m´emoire que les deux autres. Au del`a des consid´erations th´eoriques, il peut y avoir des raisons pratiques pour lesquelles une repr´esentation est pr´ef´erable a` l’autre. Par exemple, pour exprimer un concept qui est essentiellement une fonction d’une valeur, il est plus commode d’utiliser la repr´esentation par des variables d’´etats que la repr´esentation classique. Dans la suite du chapitre, nous introduisons les principaux concepts du domaine de planifi-cation en utilisant le formalisme de la repr´esentation classique STRIPS qui utilise des notations d´eriv´ees de la logique du premier ordre [Fikes et Nilsson, 1971]. Nous avons choisi de d´etailler cette repr´esentation car nous allons l’´etendre afin de pouvoir l’utiliser dans notre approche de composition de services dans un domaine dynamique (Web services par exemple).
Nous illustrons les d´efinitions de la repr´esentation classique du domaine de planification par un exemple du domaine de Web services d´efini dans [Falou et al., 2008]. Consid´erons le domaine ESW (Figure 1.1) qui contient :
– quatre effecteurs destin´es `a traiter des fichiers textes :
1. f r2en traduit un texte du fran¸cais vers l’anglais ;
2. en2ar traduit un texte de l’anglais vers l’arabe ;
3. lat2doc transforme le format de fichier de latex en doc ;
4. doc2pdf transforme le format de fichier de doc en pdf .
– deux fichiers textes F 1 et F 2 o`u :
1. F 1 est en format doc r´edig´ en anglais ;
2. F 2 est en format latex et en fran¸cais.
D´efinition 1 Un langage logique L constitu´e d’un ensemble de pr´edicats du premier ordre L = {p1, …, pn} est utilis´e pour repr´esenter un domaine de planification. Ce langage est bas´e sur le pr´edicat d´efini par son symbole et une liste d’arguments. Il est utilis´e pour repr´esenter les relations fixes et dynamiques entre les diff´erentes variables du domaine.
Remarque 1 Dans ce qui suit, nous utilisons les lettres x, y, z pour d´esigner les variables et les lettres c, p, v pour d´esigner les constantes.
Plusieurs notions attach´ees a` la d´efinition de l’atome sont d´efinies :
– expression compl`etement instanti´ee (Ground expression) : expression qui ne contient pas de symboles de variables e.g., in(c1,p3) ;
– expression partiellement instanti´ee (Unground expression) : expression qui contient au moins un symbole de variable e.g. in(c1,x) ;
– substitution : une substitution σ = {x1 ← v1, x2 ← v2, . . . , xn ← vn} dans une expression logique consiste a` remplacer chaque occurrence d’une variable xi dans la proposition, partout o`u elle intervient, par un objet vi ;
– instance de e : une instance d’expression logique e est le r´esultat de l’application d’une substitution σ a` e.
Exemple 1 Dans ESW, un sous-ensemble des atomes utilis´e pour d´ecrire le domaine est : (en f ) pour designer que le fichier f est r´edig´ en anglais ; (lat f ) pour designer que le format du fichier f est latex ; etc.
´ L D´efinition 2 Etat : un ´etat est un ensemble d’atomes instanci´es du langage .
Un pr´edicat p est v´erifi´ dans un ´etat q si et seulement si p ∈ q. Dans le cas contraire, p est faux du fait de l’hypoth`ese du monde clos : un pr´edicat qui n’est pas explicitement sp´ecifi´ dans un ´etat, est consid´er´ comme faux dans celui-ci.
Exemple 2 L’´etat du domaine d´ecrit dans la Figure 1.1 est donn´e par :
(doc F 1), (en F 1)
q0 = (lat F 2), (f r F 2)
D´efinition 3 Op´erateur : Un op´erateur est d´efini par
o = (nom(o), precond(o), ef f et+(o), ef f et−(o))
avec :
– nom(o) est le nom de l’op´erateur. Il est d´efini par une expression de la forme n(x1, …, xn) o`u n est un symbole d’op´erateur et x1, …, xk repr´esentent les param`etres de l’op´erateur ;
– precond(o) est l’ensemble de pr´econditions de l’op´erateur o, c’est- a`-dire les propri´et´es du monde n´ecessaires a` son ex´ecution ;
– ef f et+(o) et ef f et−(o) d´efinissent respectivement l’ensemble de propri´et´es d´ecrivant les propri´et´es a` ajouter et a` supprimer de l’´etat du monde apr`es l’ex´ecution de o.
Exemple 3 L’op´erateur en2ar(f ) peut ˆetre d´efini de la fa¸con suivante :
en2ar(f )
precond : (en f )
ef f et+ : (ar f )
ef f et− : (en f )
D´efinition 4 Action : Une action est une instance d’un op´erateur.
Si a est une action et qi un ´etat tel que precond(a) ⊆ qi alors a est applicable dans qi, et le r´esultat de cette application est l’´etat :
qi+1 = (qi − ef f ets−(a)) ∪ ef f ets+(a)
Exemple 4 L’´etat r´esultant de l’application de l’action en2ar[F 1] dans l’´etat q0 est :
(doc F 1), (ar F 1)
q1 =
(lat F 2), (f r F 2)
D´efinition 5 Un domaine de planification D est d´efini par : l’ensemble des types des variables, les atomes (pr´edicats), les ´etats du domaine Q = 2ATOMES INSTANCI´ES DE L et l’ensemble A des op´erateurs instanci´es de O.
Un exemple d’une partie de description du domaine de planification ESW (Figure 1.1) est donn´e ci-dessous en utilisant le langage PDDL [McDermott et al., 1998]. PDDL (Planning Domain Definition Language) est un langage standard destin´ a` d´ecrire l’´etat physique d’un domaine de planification, a` savoir ses pr´edicats (atomes), ses actions, les effets des actions et la structure des plans.
Exemple 5
( define (domain(file-transformation-domain)
(:types file)
(:predicates
(en ?f -file)(fr ?f -file)(ar ?f -file)
(lat ?f -file)(doc ?f -file)(pdf ?f -file)
(:action en2ar
(:parameters (?f -file)
(:precondition (en ?f))
(:effet (ar ?f) )
(:action fr2en
…
)
etc..
Dans l’exemple ci-dessus, le nom du domaine de planifcation est d´efini dans la premi`ere ligne, l’ensemble des types des variables est donn´e dans la deuxi`eme ligne, les diff´erents types de pr´edicats sont d´efinis dans la troisi`eme ligne et les actions du domaine sont d´efinis apr`es. Le sysmbole « ? » est utilis´e pour d´esigner les variables du domaine.
D´efinition 6 Un probl`eme de planification P pour un domaine de planification D est d´efini par
P = (O, init, but) o`u :
– init : est l’´etat initial ;
– but : est l’´etat but devant ˆetre atteint ;
– O : est l’ensemble des op´erateurs.
Exemple 6 Un exemple d’un probl`eme de planification peut ˆetre d´efini par P = (O, q0, q2) o`u : O est l’ensemble des op´erateurs du domaine ESW, l’´etat q0 (exemple 2) est l’´etat initial init, et q2 est l’´etat but d´efini comme suit :
(doc F 1), (ar F 1)
q2 =
(pdf F 2), (f r F 2)
D´efinition 7 Un plan est d´efini par toute s´equence d’actions Π = a1, a2, …, an o`u chaque action ai est une instance d’un op´erateur de O.
Soit P = (O, init, but) un probl`eme de planification. Un plan Π est un plan solution si but ⊂
γ (init, Π) o`u γ(init, Π) = γ(qn−1, …γ(γ(init, a1), a2)…an) et γ(q, a) est le r´esultat d’application de l’action a dans l’´etat q.
Exemple 7 Un plan solution du probl`eme de planification introduit dans l’exemple 6 est
π = en2ar[F 1], lat2pdf [F 2]
La repr´esentation classique du domaine de planification introduite ci-dessus est tr`es res-treinte. Par cons´equence, des extensions sont n´ecessaires non seulement pour pouvoir d´ecrire des domaines complexes mais aussi pour faciliter leur description. Ces principales extensions sont le typage des variables, les op´erateurs de planification conditionnelle (Forall , Exists, . . .), les expressions de quantification, etc. Le langage de planification PDDL permet d’exprimer ces extensions. Ces derni`eres permettent d’am´eliorer l’expressivit´e des expressions du domaine de planification tout en r´eduisant leur taille.
Dans la section suivante, nous introduisons les algorithmes de planification pour la r´esolution d’un probl`eme de planification.

Algorithmes de planification

Les algorithmes de planification peuvent ˆetre regroup´es en deux grandes familles : les al-gorithmes de planification dans un espace d’´etats (state space planning ) [Fikes et Nilsson, 1971, Zhang, 1999] et les algorithmes de planification dans un espace de plans (plan space planning ) [Sacerdoti, 1990].

Planification dans l’espace d’´etats

Les algorithmes classiques les plus simples sont les algorithmes de recherche dans un espace d’´etats. Ce sont des algorithmes de recherche dans lesquels l’espace de recherche est un sous en-semble de l’espace d’´etats. Chaque nœud correspond a` un ´etat du monde, chaque arc correspond a` une transition d’´etat, et le plan correspond a` un chemin dans l’espace d’´etats.
Les principaux algorithmes de planification dans un espace d’´etat sont : la recherche par chaˆınage avant, la recherche par chaˆınage arri`ere, la recherche mixte et l’algorithme STRIPS [Fikes et Nilsson, 1971]. Dans les sections suivantes, nous d´etaillons ces algorithmes de recherche.
Recherche par chaˆınage avant
L’algorithme par chaˆınage avant prend en entr´ee un probl`eme de planification P = (O, init, but) et retourne un plan solution π (s’il existe) ou ´echec (dans le cas contraire) [Hoffmann et Nebel, 2001a]. L’algorithme est illustr´e dans l’algorithme 1. Partant de l’´etat initial init (ligne 2), et d’un plan vide π (ligne 3), pour chaque it´eration, l’algorithme teste si l’´etat courant q satisfait l’´etat but (ligne 5), alors le plan r´esultat est retourn´ (5). Si non, il choisit une action a parmi les actions applicables dans q d’une mani`ere non d´eterministe (ligne 8). Il applique cette action pour obtenir un nouvel ´etat q (9) et il ajoute l’action au plan π (ligne 10).
Le choix non d´eterministe est incorpor´e dans une boucle ou dans un appel r´ecursif, de sorte que l’algorithme donne une s´equence de choix non d´eterministe. L’ensemble des traces d’ex´ecutions peut ˆetre repr´esent´ comme un arbre d’ex´ecution o`u chaque nœud est repr´esent´ par une it´eration ou une invocation r´ecursive de l’algorithme. Si une ou plusieurs traces d’ex´ecution r´eussissent a` trouver la solution, alors l’algorithme se termine imm´ediatement et retourne une solution. Autrement, la proc´edure ´echoue.
Algorithme 1 : Algorithme de recherche par chaˆınage avant
1 Chaˆınage-avant(O, init, but)
2 q ← init
3 π ← ∅ le plan vide
4 tant que vrai faire
si q satisfait but alors retourne π
E ← {a|a est une instance d’un op´erateur dans O et precond(a) est vraie dans q} si E = ⊘ alors retourne ´echec
Choisir une action a ∈ E d’une mani`ere non d´eterministe
q ← γ(q, a)
π ← π.a
L’algorithme de recherche par chaˆınage avant est :
– non d´eterministe : si une solution du probl`eme de planification existe, l’algorithme peut r´eussir ou ´echouer `a trouver cette solution ;
– consistant : chaque fois qu’il est invoqu´e sur un probl`eme de planification P et retourne un plan r´esultat Π, Π est guaranti d’ˆetre une solution pour P.
Exemple 8 Dans la figure 1.2, une trace d’ex´ecution de l’algorithme par chaˆınage avant pour le probl`eme de planification d´efini dans l’exemple 6 est illustr´ee. Le plan solution obtenu est le mˆeme plan que dans l’exemple 7.
Une extension pour rendre l’algorithme de recherche par chaˆınage avant d´eterministe consiste a` appliquer, a` partir d’un ´etat, non seulement une action par it´eration, mais aussi tous les op´erateurs ex´ecutables (actions). Par cons´equent, d´evelopper un ´etat conduit a` l’obtention d’un ensemble de nouveaux ´etats. Sur la base de la strat´egie de parcours de l’arbre de recherche, un des ´etats non d´evelopp´ est choisi pour le d´evelopper. L’algorithme continue le d´eveloppement des ´etats afin d’atteindre l’´etat but (solution trouv´ee) ou jusqu’`a ce qu’aucun ´etat n’est d´eveloppable (´echec). Lorsque l’algorithme trouve l’´etat but, il extrait le plan solution qui est le chemin entre l’´etat initial et l’´etat but.
Plusieurs strat´egies de recherche peuvent ˆetre utilis´ees pour choisir, dans chaque it´eration, l’´etat a` d´evelopper dans l’arbre de recherche, parmi elles :
– non-d´eterministe : l’´etat est choisi d’une mani`ere non d´eterministe ;
– profondeur : l’´etat choisi est le premier ´etat voisin jusqu’`a ce qu’un ´etat n’ait plus de voisins, alors l’algorithme revient `a l’´etat p`ere ;
– largueur : l’algorithme liste d’abord les voisins de l’´etat `a d´evelopper s pour ensuite les d´evelopper un par un. Par exemple, dans la figure 1.3, le nœud qui contient l’´etat intial est d´evelopp´ en largeur ;
– heuristique : l’´etat ayant la meilleure heuristique est d´evelopp´ afin de trouver la solution le plus vite possible. Selon le type du probl`eme, cette heuristique est d´efinie par la distance
`a l’´etat but ; dans ce cas l’algorithme choisit l’´etat le plus proche du but ;

Table des matières

Introduction 
I ´Etat de l’art en intelligence artificielle 
1 Planification classique
1.1 Repr´esentation classique du domaine de la planification
1.2 Algorithmes de planification
1.2.1 Planification dans l’espace d’´etats
1.2.2 Planification dans l’espace de plans
1.3 Techniques de planification graphique
1.3.1 Construction du graphe
1.3.2 Conditions de l’accessibilit´e
1.3.3 Planificateur Graphplan
1.4 Techniques de planification hi´erarchique
1.4.1 De STRIPS `a HTN
1.4.2 Algorithme de r´esolution de HTN
1.5 Extensions des caract´eristiques du domaine de planifcation
1.6 Conclusion
2 Planification distribu´ee et syst`emes multi-agents
2.1 D´efinition de l’agent
2.1.1 Propri´et´es d’agents
2.1.2 Type d’environnement
2.2 Des agents vers les syst`emes multi-agents
2.3 Planification distribu´ee
2.4 Planification multi-agents par cycles de conjecture/r´efutation
2.4.1 Exemple introductif
2.4.2 Mod`ele formel
2.4.3 Dynamique de l’interaction
2.5 Conclusion
3 Diagnostic et r´eparation 41
3.1 Diagnostic des plans
3.1.1 Diagnostic de la violation de la structure du plan et de l’´echec des actions
3.1.2 Diagnostic du plan
3.2 Diagnostic et r´eparation des plans multi-agents
3.2.1 Structure du plan multi-agents
3.2.2 R´eparation automatique des plans multi-agents par une strat´egie locale
3.3 Diagnostic actif
3.4 Conclusion
II ´Etat de l’art dans le domaine applicatif des Web services 
4 Introduction aux Web services
4.1 Web services, Web s´emantique et ontologies
4.2 Utilit´e des Web services
4.3 Architecture des Web services
4.4 Probl`eme de composition des Web services
4.5 D´efis de composition de Web services
4.6 Conclusion
5 Composition de Web services fond´ees sur la planification centralis´ee
5.1 Composition des Web services utilisant le planificateur SHOP2
5.2 Utilisation du planificateur MBP (Model Based Planner)
5.3 Utilisation des techniques de grilles
5.4 Travaux de composition dans le projet CASCOM
5.4.1 Agent de composition
5.4.2 Planificateur OWLS-XPlan
5.4.3 Filtres pour la composition de Web services
5.5 Approche de composition bas´ee sur les liens s´emantiques
5.5.1 Web s´emantique et description logique
5.5.2 Planification et matrice de liens causaux
5.6 Conclusion
6 Composition de Web services fond´ees sur la planification d´ecentralis´ee
6.1 Chor´egraphie dynamique de services bas´ee sur la coordination d’agents introspectifs
6.1.1 Complexit´e de communication et compl´etude
6.1.2 Exp´erimentation
6.2 Un mod`ele de composition automatique et distribu´ee de services web par planification
6.3 Conclusion
III Contribution 
7 Approche centralis´ee de composition automatique et dynamique de Web services
7.1 Exemple introductif
7.2 Limites de la repr´esentation classique du probl`eme de composition
7.3 Cadre formel
7.4 Algorithmes de planification centralis´es
7.4.1 Algorithme de composition de Web services Tree-search
7.4.2 Algorithme de composition de WS fond´e sur la m´ethode Graphplan
7.5 Impl´ementation
7.5.1 Exemple de sp´ecification de service et de requˆete en PDDL
7.5.2 Exp´erimentation de Tree-search et analyse des r´esultats
7.5.3 Impl´ementation de Graph Plan
7.6 Conclusion et perspectives
8 Approche de composition d´ecentralis´ee multi-agents avec une heuristique locale
8.1 Id´ee basique
8.2 Mod`ele formel
8.3 Op´eration de fusion des plans
8.3.1 Plans compl`etement fusionnables
8.3.2 Plans partiellement fusionnables
8.3.3 Plans non-fusionnables
8.4 Extraction du plan
8.4.1 Extraction du sous-graphe ex´ecutable
8.4.2 Extraction du meilleur plan local
8.5 Coordination multi-agents
8.5.1 Strat´egie de coordination fond´e sur le parcours en chaˆınage avant
8.5.2 Strat´egie de coordination fond´ee sur le parcours en chaˆınage arri`ere
8.5.3 Strat´egie de coordination mixte
8.5.4 Exemple d’application de la strat´egie mixte
8.6 ´Etude des complexit´es des algorithmes
8.6.1 ´Etude de la complexit´e des algorithmes centralis´es
8.6.2 ´Etude de la complexit´e de l’algorithme d´ecentralis´e
8.7 ´Etude de la compl´etude des algorithmes
8.8 Tests exp´erimentaux
8.9 Discussion
8.9.1 Comparaison avec l’´etat de l’art
8.9.2 L’utilit´e de l’approche d´ecentralis´ee
8.9.3 Passage `a l’´echelle de l’approche d´ecentralis´ee
8.10 Conclusion
9 Approche de composition d´ecentralis´ee multi-agents avec l’heuristique globale
9.1 Exemple
9.2 Id´ee basique
9.3 Algorithme de calcul de l’heuristique globale
9.4 Extraction du meilleur plan local
9.5 Coordination multi-agents
9.5.1 Exemple
9.5.2 Utilisation de l’heuristique locale
9.5.3 Exemple
9.5.4 Complexit´e de l’algorithme complet
9.6 Compl´etude de l’algorithme
9.7 Impl´ementation
9.8 Conclusion
10 Diagnostic et r´eparation de l’ex´ecution d’un plan de composition
10.1 R´eseaux de P´etri
10.2 Mod`ele formel
10.3 Architecture d’agent autogu´erissant
10.4 Le planificateur
10.5 Le diagnostiqueur
10.5.1 Rˆole du diagnostiqueur
10.5.2 Notions pr´eliminaires
10.5.3 Construction du diagnostiqueur
10.6 R´eparateur
10.6.1 Rˆole du r´eparateur
10.6.2 M´ecanisme de r´eparation
10.7 G´en´eralisation et maximisation du nombre d’´etats de croyance couverts
10.8 Conclusion et perspectives
Conclusion et Perspectives 
Bibliographie 

Télécharger le rapport complet