Figure

Objet

La ville de Paris est au sud-ouest de Bruxelles. Bruxelles est au sud de La Haye, et Cologne à l'est de Bruxelles.

Ce texte est représentatif d'un type de phrases apportant des connaissances qualitatives sur une situation spatiale. Ces connaissances permettent certaines inférences (par exemple, le fait que La Haye se situe au nord-est de Paris). Le domaine du raisonnement spatial qualitatif s'intéresse à la façon de représenter ces connaissances et de formaliser ces inférences. Si cet exemple porte sur des connaissances de type directionnel, les connaissances spatiales peuvent aussi être de type dit topologique(inclusion, recouvrement, de régions), décrire la forme des objets ou leur distance qualitative. Il arrive souvent que l'on ait un ensemble de contraintes à réaliser simultanément (par exemple, aménagement de bureau : on doit placer l'armoire à droite ou à gauche du bureau, la tablette entre les deux plans de travail, etc.). Plus généralement, on considère un nombre fini d'objets, et un ensemble de contraintes sur leurs positions relatives exprimées dans un langage symbolique. Le problème de cohérence consiste à déterminer si cet ensemble de contraintes a une solution.

Description

Nous considérons ici le raisonnement lié aux directions cardinales. Dans ce cas, on peut définir un langage contenant les symboles n(nord), s(sud), e(est), o(ouest), ne(nord-est), se, no, so, ainsi que eg( égalité). On pourra alors décrire la situation de l'exemple de départ en écrivant : (P so  B, B s  L, B e  C). Plus généralement, on pourra avoir des indications de type disjonctif, par exemple (P {se, s, so} L) indiquera que Paris est au sud-ouest, au sud, ou au sud-est de La Haye. Un manque total d'information sera en particulier représenté par l'ensemble des neuf relations. L'ensemble des relations symboliques disjonctives comporte 2⁹ = 512 éléments.

Pour étudier les propriétés du raisonnement qualitatif au moyen des relations cardinales, nous utilisons des techniques analogues à celles du raisonnement temporel. Nos résultats sont les suivants :

- Étant donné un ensemble d'objets et un ensemble de contraintes disjonctives sur leurs relations cardinales, le problème de déterminer s'il existe une disposition de ces objets satisfaisant ces contraintes est un problème NP-complet.

- Il existe un sous-ensemble maximal de relations pour lequel le problème est soluble en temps polynomial ; cette classe possède une caractérisation géométrique simple (relations pré-convexes) ; le problème peut être décidé en appliquant la technique de l'arc-cohérence (essentiellement, on restreint les contraintes de telle sorte que tout triplet d'objets soit cohérent).

Résultats et perspectives

Ces résultats constituent un des rares résultats de complexité connus pour l'instant en matière de raisonnement spatial qualitatif (dans le domaine des relations topologiques, on doit des résultats de même type à Renz et Nebel). Ils illustrent également l'intérêt que peuvent présenter les techniques issues du raisonnement temporel pour le raisonnement spatial. Les problèmes analogues, dans le cas de relations plus complexes, mêlant par exemple la topologie, la direction et la distance, restent ouverts.

Référence

Ligozat, G. : <<Reasoning about Cardinal Directions>>. À paraître dans : Journal of Visual Languages and Computing, 1998.

Gpe Langage et Cognition		Dpt CHM		Sommaire		Présentation