Raisonnement qualitatif sur le temps et l'espace

Gérard Ligozat

Description

Le raisonnement qualitatif sur le temps et l'espace est un domaine de l'intelligence artificielle qui connaît un développement important, notamment en raison de ses liens avec de nombreuses applications comme la planification, la robotique et les systèmes d'information géographique.
Cet ouvrage traite de la représentation et de la manipulation de connaissances qualitatives sur le temps, comme par exemple ces deux événements ont débuté simultanément ou sur l'espace, comme la parcelle A est adjacente à la parcelle B. Les questions d'expressivité, de complexité, et d'existence de modèles sont étudiées de façon systématique, en privilégiant les techniques algébriques et géométriques.
L'ouvrage Le raisonnement qualitatif sur le temps et l'espace s'intéresse également aux extensions floues des formalismes, à l'étude de la complexité au moyen de notions d'algèbre universelle et contient des pointeurs vers les applications, ainsi qu'une description de logiciels qui permettent d'utiliser les formalismes.
Le raisonnement qualitatif. Chapitre 1. Le formalisme d'Allen. Chapitre 2. Sous-classes polynomiales. Chapitre 3. Intervalles généralisés. Chapitre 4. Formalismes qualitatifs binaires. Chapitre 5. Formalismes qualitatifs de valence supérieure à 2. Chapitre 6. Formalismes quantitatifs, hybrides, et granularité. Chapitre 7. Raisonnement flou. Chapitre 8. Espaces conceptuels. Chapitre 9. Représentations faibles. Chapitre 10. Modèles de RCC-8. Chapitre 11. Approche catégorique. Chapitre 12. Complexité des langages de contraintes. Chapitre 13. Raisonnement spatial et logique modale. Chapitre 14. Applications et outils logiciels. Chapitre 15. Conclusion et perspectives. Annexes. Bibliographie. Index.

Sujets

• Informatique
• Mathématiques

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 06 décembre 2010
• Nombre de lectures: 30
• EAN13: 9782746241480
• Langue: Français
• Poids de l'ouvrage: 6 Mo

Extrait

Raisonnement qualitatif sur le temps et l’espace

© LAVOISIER, Paris, 2011 LAVOISIER 11, rue Lavoisier 75008 Paris www.hermes-science.com www.lavoisier.fr ISBN 978-2-7462-3117-7 Le Code de la propriété intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une part, que les "copies ou reproductions strictement réservées à l’usage privé du copiste et non destinées à une utilisation collective" et, d’autre part, que les analyses et les courtes citations dans un but d’exemple et d’illustration, "toute représentation ou reproduction intégrale, ou partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété intellectuelle. Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins d’identification et sont des marques de leurs détenteurs respectifs. Printed and bound in England by Antony Rowe Ltd, Chippenham, January 2011.

Raisonnement qualitatif sur le temps et l’espace Gérard Ligozat

D IRECTION EDITORIALE J EAN -C HARLES P OMEROL Collection Ingénierie des langues sous la direction de Patrick Paroubek

Le raisonnement qualitatif

Table des matières

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 1. Le formalisme d'Allen. . . . . . . . . . . . . . . . . . . . . . . . 1.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1. « Le mystère de la chambre obscure » . . . . . . . . . . . . . . 1.1.2. Apports du formalisme d'Allen . . . . . . . . . . . . . . . . . . 1.2. Les relations d'Allen . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1. Relations de base . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2. Relations disjonctives . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Réseaux de contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2. Expressivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3. Cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Propagation de contraintes . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1. Opérations : inversion et composition . . . . . . . . . . . . . . . 1.4.2. Table de composition . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3. L'algèbre d'Allen . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.4. Clôture algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.5. Imposition de la clôture algébrique . . . . . . . . . . . . . . . . 1.5. Tests de cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1. Le cas des réseaux atomiques . . . . . . . . . . . . . . . . . . . 1.5.2. Réseaux arbitraires . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3. Recherche de sous-ensembles polynomiaux . . . . . . . . . . .

Chapitre 2. Sous-classes polynomiales. . . . . . . . . . . . . . . . . . . . . . 2.1. « Dessine-moi une relation traitable » . . . . . . . . . . . . . . . . . . 2.2. Sous-classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Représentation géométrique . . . . . . . . . . . . . . . . . . . .

17

33 33 33 3 7 3 8 38 39 40 40 41 45 50 50 51 52 52 55 59 59 61 61

63 63 64 64

6

Raisonnement qualitatif sur le temps et l'espace

2.2.2. Interprétation en termes de granularité . . . . . . . . . . . . . . 2.2.3. Relations convexes et pré-convexes . . . . . . . . . . . . . . . . 2.2.4. Le treillis des relations d'Allen . . . . . . . . . . . . . . . . . . 2.2.5. Polynomialité des relations convexes . . . . . . . . . . . . . . . 2.2.6. Relations pré-convexes . . . . . . . . . . . . . . . . . . . . . . . 2.2.7. Polynomialité des relations pré-convexes . . . . . . . . . . . . . 2.2.8. Relations de ORD-Horn . . . . . . . . . . . . . . . . . . . . . . 2.3. Sous-classes traitables maximales . . . . . . . . . . . . . . . . . . . . 2.3.1. Une caractérisation alternative des relations pré-convexes . . . 2.3.2. Les autres sous-classes polynomiales maximales . . . . . . . . 2.4. Utilisation des sous-classes polynomiales . . . . . . . . . . . . . . . . 2.4.1. Algorithme de Ladkin et Reinefeld . . . . . . . . . . . . . . . . 2.4.2. Etude empirique du problème de cohérence . . . . . . . . . . . 2.5. Modèles du langage d'Allen . . . . . . . . . . . . . . . . . . . . . . . 2.5.1. Représentations de l'algèbre d'Allen . . . . . . . . . . . . . . . 2.5.2. Représentations de l'algèbre des instants . . . . . . . . . . . . . 2.5.3.ℵ 0 -catégoricité de l'algèbre d'Allen . . . . . . . . . . . . . . . . 2.6. Note historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 3. Intervalles généralisés. . . . . . . . . . . . . . . . . . . . . . . . 3.1. « La construction du pont » . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Vers les intervalles généralisés . . . . . . . . . . . . . . . . . . . 3.2. Entités et relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Le treillis des(p, q)-relations de base . . . . . . . . . . . . . . . . . . 3.4. Régions associées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1. Polytopes associés . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2. M-convexité des relations de base . . . . . . . . . . . . . . . . . 3.5. Opérations : inversion et composition . . . . . . . . . . . . . . . . . . 3.5.1. Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2. Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3. Les algèbres d'intervalles généralisés . . . . . . . . . . . . . . . 3.6. Relations convexes et pré-convexes . . . . . . . . . . . . . . . . . . . 3.6.1.(p, q)-relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2. Relations convexes . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.3. Relations pré-convexes . . . . . . . . . . . . . . . . . . . . . . . 3.7. Réseaux de contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8. Traitabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8.1. Relations de ORD-Horn . . . . . . . . . . . . . . . . . . . . . . 3.9. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10. Note historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67 70 72 78 80 82 86 87 87 89 92 92 95 9 5 95 96 96 97

99 99 100 102 104 105 107 109 110 110 111 114 115 116 116 117 119 120 121 121 122

Table des matières

Chapitre 4. Formalismes qualitatifs binaires. . . . . . . . . . . . . . . . . . 4.1. « Conduite de nuit » . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1. Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2. Un panorama des formalismes présentés . . . . . . . . . . . . . 4.2. Points orientés en dimension 1 . . . . . . . . . . . . . . . . . . . . . . 4.2.1. Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2. Réseaux de contraintes . . . . . . . . . . . . . . . . . . . . . . . 4.2.3. Réseaux réductibles à des réseaux d'instants . . . . . . . . . . . 4.2.4. Cas des réseaux quelconques . . . . . . . . . . . . . . . . . . . . 4.3. Intervalles orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1. Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2. Réseaux de contraintes et complexité . . . . . . . . . . . . . . . 4.4. Les calculs d'orientationOP RA. . . . . . . . . . . . . . . . . . . . 4.5. Les calculs de dipôles . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6. Le calcul des relations cardinales . . . . . . . . . . . . . . . . . . . . 4.6.1. Relations convexes et pré-convexes . . . . . . . . . . . . . . . . 4.6.2. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7. Le calcul des rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7.1. Relations convexes et pré-convexes . . . . . . . . . . . . . . . . 4.7.2. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8. Le calcul desn-points . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8.1. Convexité et pré-convexité . . . . . . . . . . . . . . . . . . . . . 4.9. Le calcul desn-pavés . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9.1. Convexité et pré-convexité . . . . . . . . . . . . . . . . . . . . . 4.10. Relations cardinales entre régions . . . . . . . . . . . . . . . . . . . . 4.10.1. Relations de base . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10.2. Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10.3. Cohérence des réseaux basiques . . . . . . . . . . . . . . . . . . 4.10.4. Applications de l'algorithme . . . . . . . . . . . . . . . . . . . . 4.11. Le formalisme INDU . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11.1. Inverse et composition . . . . . . . . . . . . . . . . . . . . . . . 4.11.2. Le treillis des relations de INDU . . . . . . . . . . . . . . . . . 4.11.3. Régions associées aux relations de INDU . . . . . . . . . . . . 4.11.4. Une algèbre non associative . . . . . . . . . . . . . . . . . . . . 4.12. Les calculs2n-étoile . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12.1. Inverse et composition . . . . . . . . . . . . . . . . . . . . . . . 4.13. Intervalles circulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.13.1. Relations convexes et pré-convexes . . . . . . . . . . . . . . . . 4.13.2. Complexité du problème de cohérence . . . . . . . . . . . . . . 4.14. Le formalismeRCC−8. . . . . . . . . . . . . . . . . . . . . . . . . . 4.14.1. Relations de base . . . . . . . . . . . . . . . . . . . . . . . . . . 4.14.2. Relations d'Allen et relationsRCC−8. . . . . . . . . . . . . . 4.14.3. Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

123 123 125 125 128 129 130 130 133 133 134 135 136 136 138 139 140 140 141 142 143 143 144 144 145 145 147 148 158 159 159 160 160 162 163 164 165 167 168 168 168 169 170

8

Raisonnement qualitatif sur le temps et l'espace

4.14.4. Classes polynomiales maximales deRCC−8. . . . . . . . . . . 4.15. Une théorieRCC. . . . . . . . . . . . . . . . . . . . . . . .discrète . 4.15.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.15.2. Entités et relations . . . . . . . . . . . . . . . . . . . . . . . . . . 4.15.3. Méréologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.15.4. Notion de contact et relationsRCC−8. . . . . . . . . . . . . . 4.15.5. Clôture, intérieur, et frontière . . . . . . . . . . . . . . . . . . . 4.15.6. Notion de connexité . . . . . . . . . . . . . . . . . . . . . . . . . 4.15.7. Chemins et distance entre cellules . . . . . . . . . . . . . . . . . 4.15.8. Distance entre régions . . . . . . . . . . . . . . . . . . . . . . . 4.15.9. Voisinages conceptuels . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 5. Formalismes qualitatifs de valence supérieure à 2. . . . . . . . 5.1. « Le bar à sushis » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Formalismes ternaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1. Notions générales . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2. Le formalisme des points cycliques . . . . . . . . . . . . . . . . 5.2.3. Calcul de la « Croix de Lorraine » . . . . . . . . . . . . . . . . . 5.2.4. Calcul va-et-vient et calculLR. . . . . . . . . . . . . . . . . . 5.2.5. Calculs pratiques et naturels . . . . . . . . . . . . . . . . . . . . 5.2.6. Détermination de la cohérence . . . . . . . . . . . . . . . . . . . 5.3. Relations d'alignement entre régions . . . . . . . . . . . . . . . . . . 5.3.1. Alignement entre régions du plan : calcul de 5-intersection . . 5.3.2. Relations ternaires entre solides dans l'espace . . . . . . . . . . 5.3.3. Relations ternaires sur la sphère . . . . . . . . . . . . . . . . . . 5.4. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 6. Formalismes quantitatifs, hybrides, et granularité. . . . . . . 6.1. « Est-ce que Jean a croisé Frédérique ce matin ? » . . . . . . . . . . . 6.1.1. Contenu du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Réseaux TCSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1. Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2. Problème de cohérence . . . . . . . . . . . . . . . . . . . . . . . 6.3. Réseaux hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1. Le formalisme de Kautz et Ladkin . . . . . . . . . . . . . . . . . 6.4. Le formalisme de Meiri . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1. Entités temporelles et relations . . . . . . . . . . . . . . . . . . . 6.4.2. Réseaux de contraintes . . . . . . . . . . . . . . . . . . . . . . . 6.4.3. Propagation des contraintes . . . . . . . . . . . . . . . . . . . . 6.4.4. Résultats de traitabilité . . . . . . . . . . . . . . . . . . . . . . . 6.5. Relations linéaires disjonctives (DLR) . . . . . . . . . . . . . . . . . 6.5.1. Un formalisme unificateur . . . . . . . . . . . . . . . . . . . . . 6.5.2. L'algèbre d'Allen avec contraintes sur les durées . . . . . . . .

172 174 174 174 175 175 176 178 178 179 181

183 183 184 184 185 186 190 190 191 194 194 195 196 197

199 199 200 200 201 202 204 204 209 209 210 211 212 214 214 215