Ontologie spatiale au coeur du processus de planification

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

Planification classique

Le monde des blocs est l’une des applications de la plani cation classique les plus connues. Il est constitue d’un ensemble de blocs de forme cubique poses sur une table et d’un bras robotique ( gure 1.1(a)). Le but est toujours de construire une ou plusieurs piles de blocs speci ees, en indiquant quels blocs sont au-dessus de quels autres blocs. Un plan solution possible est de ni par deux actions : le bras attrape le bloc C ensuite il le pose sur le bloc B. Nous utilisons cet exemple tout au long de ce chapitre.
Figure 1.1 { Le monde des blocs : la representation graphique des etats initial et but. La gure 1.1(a) decrit l’etat initial : le bloc C est sur le bloc A, le bloc A sur la table et le bloc B sur la table. La gure 1.1(b) decrit l’etat but : le bloc C sur le bloc B.
Pour resoudre un probleme de plani cation, nous avons besoin d’utiliser un algorithme de plani cation (plani cateur). La gure 1.2 decrit les entrees et les sorties d’un plani cateur. En entree, un plani cateur prend l’ensemble des donnees suivant :
{ domaine : le modele du monde est un ensemble d’actions possibles (parfois appeles operateurs) et d’actions. Chaque operateur speci e generalement des preconditions qui doivent ^etre presentes dans l’etat actuel pour qu’il puisse ^etre applique, et des e ets sur l’etat actuel ; { une description de l’etat initial du monde ; { une description d’un but a atteindre.
Ces donnees forment ce qu’on appelle le probleme de plani cation. En sortie, il genere un plan. Ce plan peut prendre di erentes formes, la plus commune etant une sequence d’actions.
Dans la litterature, plusieurs familles de plani cation existent telles que presentees dans [Ghal-lab et al., 2004] et [Regnier et Vidal, 2004]. Nous invitons les lecteurs a les consulter pour plus de details. Dans cette these, nous nous situons dans le cas de la plani cation classique en considerant les hypotheses evoquees dans [Ghallab et al., 2004] a savoir :
1. observabilit totale : tout ce qui peut ^etre connu sur l’environnement est connu. Par exemple, dans le monde de bloc les positions des blocs et l’etat du bras sont connus a tout instant, dans la gure 1.1(a) : le bras est libre, le bloc C sur le bloc A, le bloc B sur la table ;
2. deterministe : lorsqu’on execute une action le resultat est constant. Autrement dit, l’execution se deroule dans un monde parfait ou les actions ne peuvent pas echouer et leurs e ets sont totalement predetermines. Par exemple dans le monde de bloc, si le bras pose le bloc C sur le bloc B, apres execution de cette action l’etat du monde sera comme illustre dans la gure 1.1(b) : le bloc C sur le bloc B, la surface superieure du bloc A est libre ;
3. monde statique : il n’y a pas d’evenements externes qui modi ent l’environnement. Par exemple, dans le monde de bloc, seul l’intervention du bras fait changer l’etat du monde ;
4. plans sequentiels : les plans sont des sequences d’actions ou les actions s’executent l’une a la suite de l’autre. Il n’y a pas d’actions simultanees.
5. discret : les actions n’ont pas de duree, elles sont considerees comme etant instantanees au moment de la plani cation.
Toutes ces hypotheses ne simpli ent pas la complexit du probleme de plani cation mais speci e seulement le cadre. La quantite des travaux dans la litterature en plani cation classique prouve la complexit de ce probleme. En particulier, lors de l’introduction d’une ressource, d’une dimension temporelle ou d’une dimension spatiale, etc.
Dans la litterature, il existe plusieurs manieres pour representer un probleme classique de pla-ni cation. En e et, nous pouvons citer Set-theoric representation [Green et al., 1969] ou encore Classical representation [Fikes et Nilsson, 1971]. Dans la premiere representation (respective-ment, la deuxieme representation), ce sont les propositions qui sont utilisees (respectivement, les predicats du premier ordre et des connecteurs logiques). Ainsi, chaque etat du monde est un ensemble de propositions (respectivement, un ensemble de predicats du premier ordre et des connecteurs logiques) et chaque action est une expression speci ant les propositions (respective-ment, une expression speci ant les predicats du premier ordre et des connecteurs logiques) qui doivent appartenir a l’etat courant pour que l’action soit executable ainsi que les propositions a ajouter ou a supprimer de l’etat suite a son execution (respectivement, une expression speci ant les predicats du premier ordre et des connecteurs logiques).

Planification de t^aches

La plani cation de t^aches consiste en un raisonnement symbolique qui a pour objectif de construire un plan d’actions pour realiser une mission dans laquelle les conditions du but nal sont valides a partir d’une description de l’etat initial, des operateurs et du but a atteindre.
Les plani cateurs necessitent la representation du probleme de plani cation a resoudre ( – gure 1.2), c’est-a-dire la representation des etats, des actions et des buts. Pour cela, il faut trouver un langage su samment expressif pour pouvoir decrire une large variet de problemes, mais aussi su samment restrictif pour l’utiliser d’une maniere e cace. Nous considerons pour l’instant le formalisme de representation classique STRIPS [Fikes et Nilsson, 1971] (details dans la section 3.3.1) qui utilise des notations derivees du premier ordre : un etat est represent sous la forme d’un ensemble d’atomes logiques qui sont vrais lorsque le systeme est dans l’etat consider (notons par S l’ensemble des etats). Les actions sont representees par des operateurs de plani cation qui changent les valeurs de ces atomes (notons par O l’ensemble des operateurs). Formellement, l’ensemble des etats du monde sont representes par un ensemble de predicats de la logique de premier ordre L (de nition 1) decrivant le monde. Nous rappelons les principaux concepts du domaine de la plani cation en utilisant STRIPS.
De nition 1 Le langage L est un langage de premier ordre, base sur des predicats : L = fp1; : : : ; png. Ce langage est utilise pour representer un domaine de plani cation. Le langage L ne contient ni symboles ni fonctions.
De nition 2 Un predicat p est de ni par son symbole et une liste de parametres. Il represente des relations entre les di erents objets du domaine.
Par exemple, le predicat Sur(C,A) signi e que le bloc C se trouve au-dessus du bloc A ( gure 1.1(a)).

Representations des etats

Un etat est une description du monde. Dans la logique du premier ordre, un etat est represent sous la forme d’une conjonction de litteraux positifs. Par exemple, SurTable(A)^ Sur(C,A) ^ SurTable(B) represente l’etat du monde de bloc decrit dans la gure 1.1(a). Aussi, nous considerons les litteraux propositionnels : par exemple, BrasVide pour indiquer que le bras est vide dans la gure 1.1(a). Les variables (par exemple Sur(x,y)) et les fonctions (par exemple Sur(Cube(D),E)) ne sont pas permises dans les litteraux. Formellement, nous avons :
De nition 3 Un etat s est un ensemble d’atomes instancies du langage L.
Propriet 1 Comme L ne contient pas de fonctions, nous avons alors un ensemble ni d’etats.
Propriet 2 S est l’ensemble des etats tel que chaque etat est un sous-ensemble de L, ainsi S 2L.
Nous considerons l’hypothese du monde clos ; tout ce qui n’est pas vrai est suppose faux. Autrement dit, un predicat, qui n’est pas veri dans un etat est consider comme faux dans cet etat. Formellement, cette hypothese se traduit par le fait qu’un predicat p est veri dans un etat s si et seulement si p peut ^etre uni e avec des predicats de s (p 2 s, par exemple).
Un etat but est un etat partiellement speci . Il est de ni par une conjonction de litteraux (sans variable) tel que Sur(C,B) ( gure 1.1(b)). Un etat propositionnel s satisfait un but sg si s contient tous les atomes de sg (et eventuellement d’autres atomes). Par exemple, l’etat SurTable(A)^ Sur(C,B) satisfait le but Sur(C,B) ( gure 1.1(b)).

Representation des operateurs et des actions

Une action est speci ee par des preconditions qui doivent ^etre respectees avant l’execution et les e ets qui resultent de cette execution. Un operateur est un schema d’action representant une operation possible dans un domaine donne. Il represente un ensemble d’actions di erentes que l’on peut deriver en instanciant les parametres avec des constantes di erentes (de nition 4).
De nition 4 Un operateur o est de ni par un quadruplet tel que :
o = (nom(o); params(o); precond(o); ef f ets(o)) :
{ nom(o) : indique le nom de l’operateur,
{ params(o) : liste des parametres de l’operateur sous la forme fparam1; : : : ;paramng,
{ precond(o) : represente les preconditions de l’operateur, c’est-a-dire les proprietes du monde necessaires a son execution,
{ ef f ets(o) : de nit l’ensemble des faits a ajouter et a supprimer de l’etat apres l’execution de o.
Par exemple, le bras pose un bloc sur un autre est de ni par l’operateur PoserSurBloc, comme suit :
PoserSurBloc(b1,b2)
Precond: SurfaceLibre(b2), Attrape(b1)
Effets: Sur(b1,b2), SurfaceLibre(b1), BrasLibre,
: SurfaceLibre(b2), : Attrape(b1)
Code 1.1 – De nition de l’operateur PoserSurBloc.
Pour augmenter la lisibilite, certains travaux (par exemple : [Hioual et Boufaida, 2010]) distinguent entre les e ets positifs et les e ets negatifs, en de nissant une liste d’insertion pour les litteraux positifs (Sur(b1,b2), SurfaceLibre(b1), BrasLibre) et une liste de suppression pour les litteraux negatifs (SurfaceLibre(b2), Attrape(b1)) (code 1.1).
Le principe de la modelisation des actions par des operateurs consiste a speci er a l’aide de predicats, les proprietes du monde necessaires a son application, c’est-a-dire, les preconditions de l’action, ainsi que les e ets engendres par son execution. Les preconditions positives expriment les proprietes qui doivent ^etre veri ees, les preconditions negatives expriment celles qui doivent ^etre absentes de l’etat pour que l’action soit appliquee. Les e ets d’un operateur speci ant les proprietes du monde modi ees par l’execution d’une action. D’un point de vue formel, si une action est de nie par un operateur qui transforme un etat si en un etat si+1, les e ets d’une action sont representes par les predicats ajoutes (e ets positifs) et les predicats enleves (e ets negatifs) a si pour obtenir si+1. Intuitivement, si le modele d’actions (operateurs) est correct et que l’execution se deroule comme prevu, le fait qu’une action ai est applicable a l’etat si signi e qu’elle menera a l’etat si+1 lors de son execution. Une action a est dite applicable a un etat s si toutes ses preconditions sont satisfaites dans l’etat s.
De nition 5 Une action est une instance d’un operateur. Si a est une action et si est un etat tel que precond(a) si alors a est applicable a si et le resultat de cette application est l’etat si+1 = (si ef f ets (a)) [ ef f ets+(a)

Representation d’un probleme de plani cation

La de nition 6 presente d’une maniere formelle un probleme de plani cation. En plani ca-tion, un domaine D decrit le cadre dans lequel va ^etre resolu le probleme. Il est independant de n’importe quel etat initial ou but. Intuitivement, un domaine modelise toutes les actions que peut e ectuer le systeme pour lequel on plani e. Dans l’exemple du monde de blocs, le systeme pour lequel on plani e est le bras robotique. Formellement, le domaine est de ni par l’ensemble des types de variables, l’ensemble des predicats et A l’ensemble des operateurs ins-tancies de O (de nition 7). Une solution a un probleme de plani cation classique est appelee plan (de nition 8).

Table des matières

Introduction
I Etat de l’art
Introduction de la partie I
1 Planication
1.1 Planication en intelligence articielle
1.1.1 Generalites
1.1.2 Planication classique
1.2 Planication de t^aches
1.2.1 Representations des etats
1.2.2 Representation des operateurs et des actions
1.2.3 Representation d’un probleme de planication
1.3 Algorithmes et techniques de planication
1.3.1 Planication dans un espace d’etats
1.3.2 Techniques de planication
1.4 Langages de planication
1.4.1 Historique
1.4.2 Langage PDDL
1.4.3 Utilisation de PDDL
1.5 Integration de la connaissance spatiale dans la planication
1.5.1 Planicateurs de chemins
1.5.2 Couplage de planicateurs
1.5.3 Formalisation de la connaissance spatiale
2 Representation et raisonnement spatial 31
2.1 Connaissance spatiale
2.1.1 Representation spatiale
2.1.2 Raisonnement spatial
2.2 Representation d’une entite spatiale
2.2.1 Representation geometrique
2.2.2 Representation hierarchique
2.3 Representation des relations spatiales
2.3.1 Relations topologiques
2.3.2 Relation de distance
2.3.3 Cadre de reference
2.4 Approches quantitatives pour le raisonnement spatial
2.4.1 Modele raster/Modele vectoriel
2.4.2 Types primitifs
2.5 Approches pour le raisonnement spatial qualitatif
2.5.1 Formalismes inspirees des relations temporelles d’Allen
2.5.2 Formalismes fondes sur d’autres techniques
2.6 Connaissance spatiale en planication
2.6.1 Carte metrique, carte topologique, carte hybride et grille d’occupation
2.6.2 Carte semantique
3 Ontologies
3.1 Qu’est ce qu’une ontologie ?
3.1.1 Reseau semantique
3.1.2 Types d’ontologies
3.1.3 Utilite des ontologies
3.1.4 Construction d’une ontologie
3.2 Logiques de description
3.2.1 Syntaxe des logiques de description
3.2.2 Niveaux de descriptions
3.2.3 Inference dans les logiques de description
3.2.4 Logique minimale AL
3.3 Outils pour les ontologies
3.3.1 Langages
3.3.2 Outils
3.4 Connaissance spatiale dans les ontologies
3.4.1 Ontologies spatiales
3.4.2 Modelisation des entites spatiales
3.4.3 Modelisation des relations spatiales
3.5 Planication et ontologie spatiale
3.5.1 Ontologie spatiale au coeur du processus de planification
3.5.2 Ontologie spatiale et le bon fonctionnement du processus de planication
Conclusion de la partie I
II Contributions 
Introduction de la partie II
4 Connaissance spatiale : SpaceOntology
4.1 Denition d’une ontologie spatiale
4.1.1 Entite spatiale
4.1.2 Relations topologiques
4.1.3 Relations de distances
4.1.4 Relations entre entites spatiales
4.2 Raisonnement avec SpaceOntology
4.2.1 Raisonnement hierarchique
4.2.2 Raisonnement avec les relations de distance
4.2.3 Raisonnement avec les relations topologiques
4.3 Mecanisme de composition
4.3.1 Representation des relations topologiques
4.3.2 Decomposition des relations topologiques
4.3.3 Calcul de la composition
4.3.4 Consistance de la composition
4.3.5 Maintenir la coherence pour les relations topologiques
5 Modele et langage pour la planication spatiale
5.1 Planication spatiale
5.1.1 Approche proposee : Architecture Spoon
5.1.2 Raisonnement dans Spoon
5.1.3 Apercu du processus de planication de Spoon
5.2 Fonctionnement de Spoon
5.2.1 Information spatiale dans le processus de la planication
5.2.2 Operateurs de planication spatiale
5.3 De PDDL a Spatial-PDDL
5.3.1 Denition des objets dans Spatial-PDDL
5.3.2 Denition d’un domaine de planication avec Spatial-PDDL
5.3.3 Denition d’un probleme de planication avec Spatial-PDDL
6 Processus de planication avec des informations spatiales
6.1 Exemple d’application
6.2 Processus de planication : principes
6.3 Description avec Spatial-PDDL
6.4 Planication de t^aches
6.5 Planicateur spatial hierarchique et
6.5.1 Generation du graphe de reseaux de passages
6.5.2 Denition du chemin vers une cible
Conclusion de la partie II
III Experimentations 
7 Performances de Spoon
7.1 Inference de l’adjacence
7.1.1 Principe
7.1.2 Resultats experimentaux
7.1.3 Etude de la complexite
7.2 Coherence de la connaissance spatiale : justication du choix AC-3
7.3 Performances du planicateur de chemins
7.3.1 Performances du principe de la fonction DijkstraMC
7.3.2 Inter^et de la hierarchisation de l’environnement
7.3.3 Recherche de chemins dans un graphe de reseaux de passages
7.4 Planication de t^aches : etude avec HTN
7.5 Performances de Spoon
7.5.1 R^ole de la connaissance spatiale dans la planication
7.5.2 Comparaison avec d’autres planicateurs
7.6 Systeme complet de la planication
Conclusion et perspectives 
Annexes 
Bibliographie 

Télécharger le rapport complet