HMODDD
Contexte
La capacité de raisonner, c’est-à-dire d’inférer de nouvelles connaissances, est un problème central en intelligence artificielle. Parmi les différentes formes de raisonnement, le raisonnement qualitatif (Marquis et al., 2014) vise à raisonner de manière analogue à la cognition humaine. Ainsi, le raisonnement qualitatif permet de raisonner en présence d’informations incertaines et incomplètes, et en l’absence de valeurs numériques. Il permet plus précisément de résoudre les problèmes de nature qualitative de manière efficace et également d’accélérer, dans certains cas, la résolution des problèmes quantitatifs. Il se substitue au raisonnement quantitatif lorsque celui-ci n’est pas applicable. Le raisonnement qualitatif concerne généralement les aspects continus du monde, tels que le temps, l’espace ou encore les quantités. Il permet de raisonner, par exemple, sur des informations telles que « avant de rentrer chez moi, j’étais à la boulangerie », « Alice est plus jeune que Bob » et « L’Italie est au sud-est de la France ». A partir des informations « la séance de cinéma démarre à l’ouverture du restaurant » et « le restaurant ouvre après le spectacle », le raisonnement qualitatif est capable de déduire automatiquement que « la séance de cinéma est après le spectacle ». Le raisonnement qualitatif trouve ses applications dans la résolution de problèmes, la planification et le traitement du langage naturel (Ligozat, 2011).
Comme tout raisonnement, le raisonnement qualitatif se fonde sur un formalisme consistant en un langage de représentation de l’information considéré et en un ensemble de règles de raisonnement permettant de déduire de nouvelles informations à partir d’informations préexistantes. Un formalisme permet donc de raisonner dans un contexte particulier sur certains types d’informations. Par exemple, le formalisme region connection calculus (RCC) permet de raisonner sur la connexion et l’inclusion des régions. Il formalise des raisonnements tels que « puisque Paris est en France et la France est en Europe, Paris est en Europe ».
Une des principales tâches du raisonnement qualitatif est la décision de la cohérence. Celle-ci consiste à déterminer si des informations sont non contradictoires. Par exemple, les informations qualitatives « Bob est dans la voiture », « Alice serre la main de Bob » et « Alice est loin de la voiture » sont contradictoires. Ce problème étant souvent complexe, la littérature s’est en particulier focalisée sur l’identification de fragments du langage, appelés sous classes, sur lesquels la décision de la cohérence est traitable.
La majorité des formalismes qualitatifs de la littérature ne se focalisent que sur un seul aspect du monde : la position, la proximité, l’orientation, le contact … De plus, ces formalismes ne portent que sur des informations de même nature, c’est-à-dire des informations de nature temporelle ou spatiale, ayant le même niveau de précision. Pourtant, la majorité des applications requièrent la prise en compte d’informations hétérogènes. Par exemple, la prise en compte simultanée des informations temporelles et des informations spatiales est essentielle à la résolution de tâches complexes dans un environnement physique et dynamique. Afin de répondre à ces besoins, plusieurs extensions de formalismes qualitatifs ont été proposées dans la littérature. Les séquences temporelles d’informations qualitatives constituent une de ces extensions, qui se situent dans le contexte du raisonnement spatio-temporel.
Formalismes qualitatifs et réseaux de contraintes qualitatives
Dans le cadre de l’intelligence artificielle, on s’intéresse à représenter le monde et à raisonner sur celui-ci. Les représentations du monde sont généralement partielles et constituées d’informations incertaines à propos d’entités caractérisant notre vision du monde. Ces informations décrivent les propriétés des entités et de leurs liens. De nombreux formalismes ont été développés afin d’étudier et d’automatiser le raisonnement. Ces formalismes sont constitués d’un langage pour décrire les entités considérées et de règles de raisonnement pour inférer de nouvelles propriétés et de nouveaux liens, à partir de ceux déjà connus. Les entités de ces formalismes sont de toutes sortes. Dans le cadre du raisonnement sur le temps, il peut s’agir d’intervalles. Dans le cadre du raisonnement sur l’espace, il peut s’agir de régions. Une relation entre deux régions peut décrire, par exemple, leur position relative.
Parmi les formalismes proposés dans la littérature, les formalismes qualitatifs permettent, d’une part, d’exprimer des relations particulières, dites qualitatives, pour décrire les liens entre les entités considérées et, d’autre part, de raisonner sur les descriptions associées. Les relations de ces formalismes sont qualifiées de qualitatives au sens où elles n’expriment aucune donnée numérique. Les relations qualitatives sont omniprésentes dans le langage naturel. Par exemple, dans le langage courant, on ne dira jamais que l’on se trouve au niveau du sol à une latitude de 48.858° nord et à une longitude de 2.2944° est ; on dira à la place que l’on se trouve sous la tour Eiffel. L’information « se trouver sous la tour Eiffel » est moins précise, mais le surplus d’information n’est pas toujours utile. Les relations qualitatives permettent ainsi de se focaliser sur les aspects importants de l’information et d’abstraire le reste. Cette abstraction offre de nombreux avantages, en particulier concernant les aspects computationnels des tâches de raisonnement telles que la décision de la cohérence ou la déduction maximale d’information d’une description. Concernant la représentation, les formalismes qualitatifs permettent de spécifier de façon naturelle des informations partielles à propos d’une configuration d’entités.
Cadre formel des formalismes qualitatifs
Nous commençons par présenter les relations et les schémas de partition, qui sont des ensembles de relations élémentaires sur lesquelles se basent les descriptions du monde, constituant ainsi le vocabulaire des formalismes qualitatifs. Nous exposons ensuite les opérateurs et les propriétés sur lesquels se fonde le raisonnement et qui permettent de mettre en œuvre les tâches du raisonnement. Nous détaillons par la suite la structure algébrique associée aux relations qui induit un calcul sur les relations et ainsi un raisonnement. Enfin, nous présentons les différentes définitions de la notion de formalisme qualitatif qui consiste en un cadre formel permettant de représenter et de raisonner sur un ensemble de relations.
Relations et schémas de partition
Nous nous intéressons tout d’abord aux objets des formalismes qualitatifs, à savoir des relations particulières entre des entités spécifiques. Les entités peuvent être de toute sorte. Dans le cadre du raisonnement sur le temps, les entités considérées peuvent être des points ou des intervalles temporels. Dans le cadre du raisonnement sur l’espace, les entités sont des régions du plan ou de l’espace, des droites ou des courbes, etc. L’ensemble des entités que l’on considère est appelé domaine ou encore univers et est noté U. Par exemple, dans le cadre temporel, le domaine peut être l’ensemble des intervalles de la droite réelle. Il peut être la droite réelle elle-même lorsque l’on raisonne à propos d’instants. Dans le cadre spatial, il peut être l’ensemble des régions du plan ou encore l’ensemble des régions connexes du plan.
Dans le cadre des formalismes qualitatifs, on se fixe un ensemble B = {b1, . . . , bl} de relations dites basiques comme vocabulaire afin de décrire les liens élémentaires entre les entités. Le choix de ces relations définit le niveau d’abstraction, c’est-à-dire de précision, des représentations basées sur celles-ci. Plus précisément, suivant ce choix, certaines configurations d’entités auront la même représentation ou, au contraire, une représentation différente. Ainsi, le choix de B a une influence sur la capacité à effectuer des déductions précises et a un impact sur la complexité du raisonnement. De manière plus concrète, considérons deux points de la droite. Pour décrire les positions relatives entre ces deux points, on peut utiliser les relations <, = et > sur R. Le couple (2, 5) satisfait la même relation que le couple (0, 1), à savoir la relation <. En effet, nous avons 2 < 5 et 0 < 1. Ainsi, (2, 5) et (0, 1) ont la même représentation, qui est x < y avec x, y ∈ U = R. Les relations basiques contiennent généralement une relation particulière : la relation {(x, x) | x ∈ U}, appelée égalité (ou identité) sur U. Celle-ci est notée Id, e, EQ ou encore = en fonction du contexte.
Raisonnement à base de relations
Une fois défini le vocabulaire pour décrire le monde en présence d’incertitude, l’étape suivante consiste à raisonner sur les descriptions basées sur ce vocabulaire. À partir de connaissances, nous voulons inférer de nouvelles connaissances, c’est-à-dire de nouvelles relations. En particulier, l’objectif est de réduire l’incertitude concernant les relations basiques pouvant être satisfaites par les couples d’entités considérées. Par exemple, sachant que x ≤ y, nous voudrions préciser le lien entre x et y, c’est-à-dire déterminer si x < y ou si x = y. Pour ce faire, il faut raisonner conjointement sur les relations des entités considérées, mais ce n’est pas toujours suffisant. En effet, si nous savons uniquement que x ≤ y, nous ne pouvons pas décider si x < y ou si x = y. Par contre, si nous savons également que x ≥ y, alors nous pouvons conclure que x = y. De manière générale, étant données deux entités x et y indéterminées, si nous savons qu’elles satisfont les relations r et r′ , nous pouvons en déduire qu’elles satisfont la relation plus précise r ∩r′ . Pour effectuer ce raisonnement, nous utilisons l’opérateur d’intersection ∩. Plus formellement, nous avons la propriété suivante :
x r y ∧ x r′ y ⇐⇒ x (r ∩ r′) y.
|
Table des matières
1 Introduction
1.1 Contexte
1.2 Problématiques
1.3 Contributions
1.4 Plan
I État de l’art
2 Formalismes qualitatifs et réseaux de contraintes qualitatives
2.1 Introduction
2.2 Cadre formel des formalismes qualitatifs
2.2.1 Relations et schémas de partition
2.2.2 Raisonnement à base de relations
2.2.3 Structure des relations et raisonnement effectif : calcul algébrique des relations
2.2.4 Définitions de formalisme qualitatif
2.3 Formalismes qualitatifs élémentaires
2.3.1 Calcul et algèbre des intervalles d’Allen
2.3.2 Calcul des points cardinaux
2.3.3 RCC8 : un calcul sur la connexion des régions
2.3.4 RCC5
2.4 Réseaux de contraintes qualitatives
2.4.1 Définition d’un réseau de contraintes qualitatives
2.4.2 Cohérence
2.4.3 Clôture algébrique et décision de la cohérence
2.4.4 Quelques classes traitables
2.4.5 Minimalité et redondance
2.5 Conclusion
3 Extensions des formalismes qualitatifs
3.1 Introduction
3.2 Intégrations de formalismes qualitatifs
3.2.1 Les intégrations lâches
3.2.2 Les intégrations étroites
3.2.3 Abstraction et affinement
3.3 Raisonnements spatio-temporels
3.3.1 Interdépendances temporelles
3.3.2 Graphes de voisinage
3.3.3 Graphes de dominance
3.3.4 Formalismes spatio-temporels
3.3.5 Différence entre le raisonnement spatio-temporel et le raisonnement sur le mouvement
3.4 Raisonnement multi-échelle
3.4.1 Échelles temporelles
3.4.2 Formalismes qualitatifs temporels multi-échelles
3.4.3 Formalisme quantitatif temporel multi-échelle
3.4.4 Formalismes qualitatifs spatiaux multi–échelles
3.4.5 Travaux connexes au raisonnement multi-échelle
3.5 Autres combinaisons et extensions
3.5.1 Entités hétérogènes
3.5.2 Informations quantitatives et qualitatives
3.5.3 Clôture propositionnelle
3.6 Conclusion
3.6.1 Bilan
3.6.2 Limites des approches de la littérature
3.6.3 Questions ouvertes
II Contribution
4 Multi-algèbre : structure des réseaux intégrés, séquentiels et multi-échelles
4.1 Introduction
4.2 Le cadre des multi-algèbres : représentation, raisonnement et cohérence
4.2.1 Formalismes qualitatifs symétriques
4.2.2 Projections et multi-algèbres
4.2.3 Raisonner à propos des relations d’une multi-algèbre
4.2.4 Sémantique des relations
4.2.5 Cohérence des relations des multi-algèbres
4.2.6 Réseaux sur des multi-algèbres et clôture algébrique
4.3 Traitabilité de la décision de la cohérence
4.3.1 Sous-classes algébriquement traitables
4.3.2 Cohérence des relations -cohérentes
4.3.3 Héritage de la traitabilité par découpage
4.3.4 Héritage de la traitabilité par affinement vers un sous-ensemble
4.3.5 Conditions plus fortes pour la cohérence et propriétés remarquables
4.3.6 Problème de la clôture par projection et affaiblissement de formalismes
4.3.7 Synthèse des résultats obtenus
4.3.8 Limites du cadre formel proposé et des résultats de traitabilité obtenus
4.3.9 Illustration : combinaison taille-topologie
4.4 Conclusion
4.4.1 Bilan
4.4.2 Perspectives
5 Formalisation du raisonnement qualitatif temporel multi-échelle
5.1 Introduction
5.2 Calcul échelonné : calcul à une échelle
5.2.1 Représentation des entités temporelles à une échelle
5.2.2 Calcul des points et intervalles
5.2.3 Relation échelonnée et calcul échelonné
5.3 Calcul multi-échelle
5.3.1 Conversion ascendante et descendante
5.3.2 Systèmes de discrétisation
5.3.3 Multi-algèbre échelonnée et calcul multi-échelle
5.3.4 Raisonnement avec des échelles qualitatives
5.3.5 Propriétés et avantages du raisonnement multi-échelle
5.4 Conclusion
5.4.1 Bilan
5.4.2 Perspectives
6 Formalisation et étude du raisonnement sur les séquences temporelles
6.1 Introduction
6.2 Interdépendances spatio-temporelles
6.2.1 Définitions de la continuité et de la taille
6.2.2 Caractéristiques et changement de sémantique
6.2.3 Dynamiques des entités
6.2.4 Formalismes qualitatifs topologiques et mesurés
6.2.5 Définition générale des graphes de voisinage et des graphes de dominance
6.2.6 Projections des graphes de transition
6.3 Séquences temporelles simples
6.3.1 Multi-algèbres des séquences temporelles simples
6.3.2 Sémantique des séquences temporelles simples
6.4 Étude du calcul des points temporalisé sans relation intermédiaire et sur intervalles
6.4.1 Résultats de complétude
6.4.2 Cohérence des relations -cohérentes
6.4.3 Discussion à propos de la complexité de la décision de la cohérence
6.5 Séquences temporelles avec relations de caractéristique
6.5.1 Le problème de la taille et l’intégration lâche caractéristique-formalisme
6.5.2 Multi-algèbres des séquences temporelles avec relations de caractéristique
6.5.3 Sémantique et propriétés des relations de caractéristique spatio-temporelles
6.5.4 Sémantique des séquences temporelles avec relations de caractéristique
6.6 Étude de la topologie temporalisée avec préservation de la taille
6.6.1 Complétude du raisonnement pour TRCC8t
6.6.2 Cohérence des relations -cohérentes et affaiblissement arborescent
6.6.3 Complexité et sous-algèbres algébriquement traitables de TRCC8t
6.7 Avantages et applications du cadre des multi-algèbres spatio-temporelles
6.7.1 Avantages computationnels des multi-algèbres
6.7.2 Simulation qualitative
6.7.3 Interpolation de réseaux de contraintes
6.8 Conclusion
6.8.1 Bilan
6.8.2 Perspectives
7 Conclusion
7.1 Bilan
7.2 Perspectives
III Annexes
