Contribution à l'utilisation de la programmation par contraintes pour la recherche de modèles finis en intelligence artificielle
Institution:
Aix-Marseille 2Disciplines:
Directors:
Abstract EN:
This thesis aims at using constraint programming, and more precisely finite model search for constraint object models, to achieve symbolic reasoning and address artificial intelligence problems. A the denotational level, we illustrate the expressive power of the chosen formalism through the description of a theoretical and experimental framework addressing a very modern challenge: the automatic composition of semantic web services. This framework, developped during the DIP European project and prototyped using ILOG’s tool JConfigurator, has been integrated in the project’s architecture and tested on industrial use cases. At the operational level, we describe algorithms dealing with the inherent combinatorial explosion of enumerative methods. We propose a pseudo-linear time algorithm that approximates colored directed acyclic graphs canonicity detection, allowing early backtrack when generating isomorphic configurations during the search. The theoretical results are backed by a range of experiments. We also propose a stochastic method based on simulated ant colony behaviour which handles original first-order logic issues. There again we present experimental results.
Abstract FR:
Cette thèse a pour but d’utiliser la programmation par contraintes, et plus précisément la recherche de modèles finis pour les modèles objets contraints, dans le raisonnement symbolique et la résolution de problèmes d’intelligence artificielle. Au niveau dénotationnel, nous illustrons la puissance expressive du formalisme choisi à travers la description d’un cadre théorique et expérimental pour un challenge moderne: la composition automatique de services web sémantiques. Ce cadre, développé durant le projet Européen DIP et prototypé à l’aide de l’outil JConfigurator d’ILOG, a été intégré au sein de l’architecture du projet et testé sur des scénarios industriels. Au niveau opérationnel, nous décrivons des algorithmes traitant l’explosion combinatoire inhérente aux méthodes énumératives. Nous proposons un algorithme pseudo-linéaire en temps pour la détection de canonicité de graphes orientés acycliques colorés, permettant, au cours de la recherche, de “backtracker” sur des configurations isomorphes. Les résultats théoriques sont appuyés par une série d’expérimentations. Nous proposons également une méthode stochastique, basée sur le comportement simulé d’une colonie de fourmi, qui traite des problèmes originaux posés par la logique du premier-ordre. De nouveau nous présentons des résultats expérimentaux.