Bon nombre de problèmes issus de l'Intelligence Artificielle et
de la Recherche
Opérationnelle peuvent s'exprimer naturellement sous forme de
contraintes.
Qu'ils soient académiques (problème des n-reines, du
zèbre, etc ...) ou industriels (problèmes
d'ordonnancement, d'allocation de ressources, etc ...), les exemples ne
manquent pas dans la littérature
scientifique.
Un cadre formel appelé CSP (pour ``Constraint Satisfaction
Problem'') a été défini à l'origine par
Montanari, Mackworth puis Freuder.
Le caractère simple et général explique sans doute
l'engouement qu'il a rencontré
dans la communauté « Intelligence Artificielle ».
Au premier abord, un CSP est défini par un ensemble de variables
et un ensemble
de contraintes.
Toute variable représente une inconnue du problème qui
peut
prendre une valeur dans un domaine qui lui est associé.
Toute contrainte porte sur un sous-ensemble de variables du
problème et indique les combinaisons de
valeurs autorisées pour celles-ci. Une solution consiste en
l'affectation d'une valeur à chaque variable du problème
de manière à ce que toutes ses contraintes
soient respectées. Pour trouver une solution (voire l'ensemble
des solutions), il est possible
d'appliquer un algorithme classique de résolution qui consiste
à parcourir l'espace de recherche de ce CSP
(généralement, en profondeur d'abord avec
retours-arrière).
Par ailleurs, de nombreuses méthodes permettent, pendant la
résolution, de réduire l'espace de recherche en utilisant
des techniques déductives basées sur l'emploi des
contraintes. Elles sont communément appelées
méthodes de propagation de contraintes (ou filtrage).
L'équipe de recherche dont je fais partie s'intéresse
aux techniques de filtrage, heuristiques de choix de variables et/ou de
valeurs.
Notre prototype"AbsCon",
développé au laboratoire, permet de tester les
principales techniques existantes mais également nous permet de
développer et tester toutes nouvelles idées à ce
sujet.
Cependant, la résolution (à l'aide d'un algorithme)
classique ne s'avère pas
toujours efficace. En effet, lorsque la taille de l'espace de recherche
est
conséquente et que les contraintes ne permettent pas un filtrage
important, la
résolution ne peut fournir de solution(s) en un temps
raisonnable. De plus,
certains CSPs sont intrinsèquement difficiles (problèmes
NP-complets). Une
alternative à la résolution classique consiste à
utiliser un principe
d'abstraction.
De façon générale, une abstraction de CSPs peut
être considérée comme la donnée
de deux problèmes dont l'un (dit abstrait) est une approximation
de l'autre
(dit concret).
Une telle abstraction peut être utilisée afin
d'améliorer l'efficacité de la
résolution du problème concret. En effet, le
problème abstrait peut être défini à partir
du problème concret en regroupant des variables et/ou des
valeurs ainsi
qu'en modifiant en conséquence l'ensemble des contraintes. La
résolution du problème abstrait permet alors de guider la
résolution du problème concret puisqu'il est possible
d'utiliser les solutions abstraites lors de la recherche des solutions
concrètes. Il suffit de considérer uniquement les
sous-ensembles de l'espace de recherche du problème concret
correspondant aux solutions abstraites.
En règle générale, un problème abstrait
possède moins de variables et/ou des domaines plus petits. C'est
pourquoi la résolution d'un problème concret via une
abstraction peut s'avérer nettement plus efficace que la
résolution classique.
Alors que le principe d'abstraction a été utilisé
avec succès dans de nombreux
domaines (e.g. en planification et en analyse de programmes) depuis
plus de vingt
ans, il n'a été appliqué que plus récemment
au domaine des contraintes.
Durant ma thèse, nous avons
proposé un cadre formel d'abstraction adapté aux CSP qui
permet de définir des formes classiques d'abstractions mais
aussi des formes originales correspondant, pour l'essentiel, à
la notion de
regroupement général de valeurs et de variables.
L'origine de la généralité du
cadre est liée à l'utilisation de relations
d'approximation comme liens
d'abstraction. Ces derniers ont souvent été
formalisés par des applications ou
des connexions de Galois dans d'autres domaines.
Nous travaillons également sur ce cadre d'abstraction afin
d'identifier les propriétés intéressantes qui
permettront
de caractériser l'abstraction et/ou le gain sur la
résolution.
Notre prototype "AbsCon"
permet
également de définir des abstractions et
d'exécuter des résolutions d'instance avec abstractions.
Le cadre CSP même s'il est très intéressant
possède certaines limites.
En particulier, aucune solution (même dégradée) ne
peut être proposée lorsque le
problème est inconsistant. Introduire une certaine
flexibilité permet d'apporter
une réponse à ce type de problème, notamment en
relâchant les contraintes.
Durant ma thèse, nous nous
sommes intéressés à la
définition d'un cadre, appelé "hiérarchie
floue", permettant d'intégrer la notion de
flexibilité aussi bien au niveau
de chaque contrainte qu'au niveau même de l'ensemble des
contraintes.
Dans le premier cas, elle permet de tolérer (et de mesurer) des
combinaisons de
valeurs qui ne respectent pas une contrainte et se traduit sous la
forme de
contraintes avec flexibilité.
Dans le second cas, elle permet d'exprimer l'importance
relative (priorités) de chacune des contraintes et se traduit
sous la forme
d'une hiérarchie.
Nous avons préféré concentrer nos efforts sur
les premiers points ce qui ne nous permet pas d'approfondir ce domaine
particulier.
Vous trouverez l'ensemble de mes publications ici.
Si vous avez des questions sur les activités
développées ou si vous recherchez un document dont je
suis l'auteur ou
co-auteur, n'hésitez pas à me contacter par e-mail.
