dernière modification : décembre 2003
L'équipe InCA est active autour des projets suivants :
- SIG : raisonnement en information géographique (R. Jeansoulin, C. Campioni, Y, Lassoued, E. Wurbel, O. Papini*)
- configuration à base de contraintes (L. Henocque, B. Benhamou, S. Grandcolas, P. Jégou, P. Siegel)
- hybridations algorithmiques pour SAT et CSP (P. Jégou, L. Keddar, S. Grandcolas, L. Oxusoff, N. Prcovic, C. Terrioux)
- planification et actions (G. Audemard, B. Benhamou, C. Pain-Barre, A. Isli*)
- les logiques de l'argumentation (V. Risch, P. Basso, JM. Lorenzi, L. Oxusoff, P. Siegel, R. Mercer*)
SIG : raisonnement en information géographique
La représentation et le raisonnement dans les systèmes d'information géographique est un thème de recherche en pleine croissance au niveau international. Il se développe au sein de l'équipe suivant deux axes : - Raisonnement spatial et information géographique imparfaite : Il s'agit de représenter des contraintes spatiales en utilisant un langage propositionnel et en se basant sur un formalisme de treillis de relations. L'objectif principal est d'utiliser ce formalisme pour un mieux traiter des informations imparfaites (incomplètes, imprécises et incertaines). Ce type d'information se trouve fréquemment dans les systèmes d'information géographique (SIG). - Représentation et interopérabilité des données géographiques : Un modèle orienté objet est élaboré pour la représentation des relations spatiales et de leurs hiérarchies. Ces travaux ont pour principal objectif l'amélioration des capacités d'interopérabilité des données géographiques (grand thème de réflexion de la recherche et de l'industrie dans le domaine de l'information géographique). La logique fournit un formalisme adapté à bien des égards au traitement de divers problèmes de représentation de connaissances. Elle offre des modèles formels de raisonnement bien définis et dont les mécanismes de déduction et les sémantiques associées sont bien étudiées. Les points d'intérêt de l'équipe portent sur les raisonnements non-standards avec des travaux notamment sur les logiques conditionnelles, les logiques non-monotones, la calculabilité, et la construction de formalismes à base de séquents.
Configuration à base de contraintes :
La configuration consiste à construire un produit complexe à partir de composants. Les types, les relations existant entre les types des composants sont connus mais pas le nombre et l'organisation des composants participant à un produit à construire. La configuration d'un produit peut être simulée par un programme disposant d'un modèle des données et de stratégies de construction appropriées. Les applications potentielles des technologies émergentes de la configuration sont immenses, par exemple dans la CAO, le commerce électronique, le traitement automatique des langues, la représentation et l'exploitation de connaissances. Les problèmes de configuration sont des problèmes du premier ordre, ne pouvant pas être traités par des algorithmes à espace prévisible où des isomorphismes nombreux conduisent à des espaces de recherche très redondants. Les problèmes de configuration constituent le lieu naturel d'aboutissement de nombreuses recherches développées et en cours au sein de l'équipe InCA : heuristiques, détection des symétries, classes polynomiales, recherche de modèles finis aux théories équationnelles notamment. Ce projet de quatre ans vise notamment l'étude des symétries et des heuristiques pour l'optimisation des configurations sous une fonction de coût.
Hybridations algorithmiques pour SAT et CSP :
Les stratégies algorithmiques généralement mises en oeuvre sur SAT ou CSP reposent sur les notions d'énumération, de recherche locale, de propagation ou de décomposition. D'un point de vue expérimental, les méthodes les plus efficaces sont fondés sur le principe d'énumération (complète) ou de recherche locale (incomplète). Celles-ci intègrent systématiquement des méthodes de propagation. En termes de complexité, l'énumération a un coût théorique exponentiel, indépendamment des propriétés des instances traitées alors que les méthodes recherche locale sont en général stoppées en un temps fixé a priori. A contrario, les méthodes fondées sur la décomposition fournissent des bornes de complexité de l'ordre de 2k où k par exemple représente la tree-width du réseau de contraintes traité. Ces méthodes sont basées sur l'existence, la reconnaissance et l'exploitation de classes d'instances polynomiales. Elles n'ont cependant montré leur intérêt pratique que sur des classes d'instances trop limitées. Enfin, il ressort que l'ensemble des algorithmes recèle un comportement tel que sur certaines instances, une approche sera préférable, au contraire d'autres où seule une stratégie différente obtiendra des résultats acceptables. Ce projet, sur deux ans, a pour objectif de fournir des solutions à ces problèmes par la mise en oeuvre d'approches hybrides. Deux axes principaux seront étudiés, le premier concernant la mise en synergie des notions d'énumération/propagation et des techniques de décomposition. La voie consiste a bâtir des méthodes énumératives ainsi que des techniques de propagations en les guidant par l'analyse structurelle des instances. Les résultats envisageables à moyen terme sont l'obtention de meilleures bornes de complexité pour les méthodes énumératives et l'élaboration de techniques de propagation plus efficaces car fondées sur l'exploitation des structures de problèmes. Enfin, elles devraient permettre de rendre véritablement opérationnelles les méthodes de décomposition structurelle. Enfin, ces résultats devraient aussi servir à construire des schémas de mises en oeuvres parallèles ou concurrentes, par exemple quand les paramètres de décomposition de problèmes induisent des collections de sous problèmes indépendants. Le second axe de l'étude concerne l'hybridation des algorithmes de recherche arborescente avec les algorithmes de recherche locale. L'objectif à moyen terme est de fournir une généralisation de ces deux méthodes de recherche. La voie étudiée ici consiste dans un premier temps à construire une seule méthode globale dépendant de certains paramètres à réglage fin. Dans un second temps il s'agira de déterminer comment régler automatiquement ces paramètres pour obtenir des algorithmes optimaux suivant le contexte d'utilisation. Le cadre applicatif au niveau de l'équipe INCA se retrouve naturellement sur plusieurs thèmes dont ceux liés au raisonnement spatial ou temporel, mais aussi dans les projets, en premier lieu, celui traitant des problèmes de configuration.
Planification et actions :
Dans le cas général, la planification est un problème très difficile (PSPACE-complet). L'approche classiquement retenue consiste à produire un plan se limitant à une séquence d'actions permettant d'atteindre les buts fixés dans la pratique. En outre, l'utilisation d'un planificateur nécessite une phase de modélisation complexe et fastidieuse afin de fournir au planificateur les actions utilisables pour un problème donné, en particulier lorsque ces actions sont représentées avec des opérateurs de type STRIPS. Cette difficulté est à l'heure actuelle une entrave à l'exploitation effective de la planification dans l'industrie.
Objectifs :
- Réalisation d'un outil d'aide à la modélisation des opérateurs en utilisant une théorie de l'action.
- Réalisation d'un système de planification efficace, basé sur la génération de modèles finis et l'exploitation des symétries en logique du premier ordre.
- Résolution des problèmes de planification temporelle prenant en compte des contraintes temporelles et des actions parallelisables.
Calendrier :
Les deux premières années seront consacrées à la réalisation des deux premiers objectifs. Les deux années suivantes concerneront le dernier objectif.
Description des travaux envisagés :
Ce projet se veut à la fois théorique et pratique. Les objectifs évoqués ci-dessus montrent son ambition d'aller de la modélisation du problème à sa résolution en se basant sur les lignes directrices suivantes :
- Outil d'aide à la modélisation d'opérateurs :
Il s'agit de réaliser un compilateur d'une théorie de l'action qui produit les opérateurs nécessaires à la résolution d'un problème de planification. Les opérateurs produits sont ceux requis par les planificateurs actuels (opérateurs STRIPS ou ADL). Ils décrivent explicitement leurs effets. Ils sont difficiles à produire à la main car ils nécessitent de prévoir les effets de chaque action dans chaque état. Ceci n'est pas nécessaire dans une théorie de l'action, où les actions ne décrivent que leurs effets principaux. Les effets secondaires à partir d'un état sont déductibles de la théorie. Un compilateur d'une théorie de l'action exprimée en logique propositionnelle est déjà opérationnel. Il produit des opérateurs STRIPS propositionnels. Nous voulons étendre ce compilateur afin qu'il produise des opérateurs paramétrables avec des effets universalement quantifiés. Pour cela, nous devons étendre les principes développés dans ce compilateur pour compiler une théorie exprimée en logique du premier ordre.
- Résolution d'un problème de planification exprimé en logique du premier ordre :
Il s'agit d'étendre les travaux de Kautz et Selman sur la résolution d'un problème de planification par satisfaisabilité d'un ensemble de formules propositionnelles. Cette approche a montré de très bons résultats mais se heurte à une explosion combinateoire due à la nature propositionnelle des formules considérées. Nous pensons que l'expression de ces problèmes en logique du premier ordre et l'utilisation des méthodes de recherche de modèles finis exploitant les propriétés de symétries pour les résoudre serait une meilleure solution. Cependant, les générateurs de modèles finis existants (e.g., Falcon, Sem, Fmset) nécessitent une forme clausale du premier ordre ou une une forme simplifiée de celle-ci. Pour traiter les problèmes de planification dont l'expression nécessite une forme plus générale, nous pensons étendre le langage d'entrée de ces méthodes à des formules quelconques de la logique du premier ordre (en intégrant une énumération partielle.
- Prise en compte de contraintes temporelles :
Certains problèmes de planification (planification des vols, problèmes liés à l'ordonnancement) nécessitent l'exécution d'actions en parallèle, et la représentation explicite du temps en général. Nous pensons représenter ces problèmes sous forme de contraintes temporelles et utiliser des fomalismes qualitatifs et/ou quantitatifs (e.g., algèbre des intervalles de Allen, formalisme de Dechter et Pearl) pour exprimer ces contraintes. Pour résoudre des problèmes dans ce formalisme, nous envisageons d'exploiter les symétries dans les CSP temporels. Des symétries dans le cadre des CSP temporels qualitatifs ont été étudiées en collaboration avec Amar Isli (Université de Leeds, Université de Hambourg). Leur exploitation améliore la résolution de problèmes exprimés dans l'agèbre des intervalles d'Allen. Nous pensons étendre ces travaux dans le cadre des CSP temporels quantitatifs ce qui permettra de traiter notamment les problèmes liés à l'ordonnancement de tâches (type Job shop) et ceux de la planification temporelle en général.
Les logiques de l'argumentation :
L'étude des phénomènes argumentatifs dans les langues naturelles permet de mettre en évidence des mécanismes de raisonnement dont les liens avec l'approche logique non-monotone sont indéniables. Par ailleurs, des tentatives prometteuses ont récemment vu le jour concernant la constitution d'une théorie de la preuve pour les formalismes non-monotones d'une part et l'appréhension des opérations logiques régissant l'agrégation de connaissances d'autres part.
A partir des travaux formels amorcés dans ces deux directions, ce projet sur quatre ans a pour objet l'étude, l'amélioration, et l'utilisation d'outils logiques qui permettraient de réaliser à terme un système automatisé d'aide à la simulation de stratégies argumentatives. L'idée de base est d'utiliser un moteur d'inférence non-monotone pour délimiter précisément le processus d'échange (modèle de locuteurs, finalité de l'argumentation), traduire le réseau des exceptions et des usages courants sous formes de règles de défauts, caractériser les saillances et la stratégie argumentatives. Un tel moteur devrait permettre dans une certaine mesure de tester la validité des arguments et d'en signaler les faiblesses. Il devrait permettre en outre d'exhiber les liens inférentiels entre arguments et de signaler les modifications de contexte.
Des applications délimitées sont à envisager d'une part au sein du logiciel de communication homme-machine ILLICO (en collaboration avec l'équipe Langage Naturel), d'autre part dans le cadre de la modélisation des échanges stratégiques entre deux agents formels en contexte (pour un descriptif complet, consulter l'URL http://www.lim.univ-mrs.fr/~risch/projetfre/projetfre.html).
Une partie de ces projets s'appuie sur des travaux antérieurs menés entre autres au sein de l'ancienne équipe RTLC du LIM. Le lecteur intéressé trouvera un descriptif détaillé des travaux de l'équipe RTLC dans le rapport scientifique 1995-1999 du Laboratoire d'Informatique de Marseille.