tous. UE conseillée pour les parcours ACR et CODA.
Pré-Requis
UMINM111 (Algorithmique), UMINM112 (Complexité et calculabilité), UMINM203 (Introduction à l'intelligence articielle), UMINM207
(Résolution de problèmes NP-difficiles).
Controle connaissances
3
Description de l'UE :
Semestre
Code
Intitulé
Cours
TD
TP
TER
S3
UMINR302
Contraintes
15h
-
-
Detail du programme
Objectifs : Contenu :
Objectif
Le raisonnement par contraintes est aujourd'hui connu pour sa capacité à résoudre de nombreux problèmes combinatoires (emplois
du temps, affectation de personnel, etc.). Ce module s'attachera dans un premier temps à décrire le modèle de base du raisonnement
par contraintes, à savoir le problème de satisfaction de contraintes (ou CSP pour son sigle anglais). Intuitivement, la question
de base que l'on se pose est celle de l'existence d'une affectation de valeurs à des variables soumises à des restrictions
(= contraintes) sur les combinaisons de valeurs qu'elles peuvent prendre. Une fois le modèle posé, les principales approches
pour résoudre un CSP seront présentées.
Dans un deuxième temps, nous présenterons les différentes extensions qui peuvent être apportées au modèle de base dès que
la question que l'on pose ne se limite pas à obtenir une solution. On traitera notamment le cas où le but est d'obtenir une
``bonne'' ou la ``meilleure'' solution selon certains critères.
Enfin, au cours de l'avancée du module, nous aborderons en parallèle le problème de la modélisation de problèmes complexes
en réseaux de contraintes. Nous ferons cela sous la forme d'exemples que l'on modélisera de différentes façons pour ensuite
ananlyser les savoir-faire nécessaires.
Plan
? définition du problème de satisfaction de contraintes
? technique de résolution de base : le backtrack
? différents types d'amélioration possibles de cette méthode :
retours-arrière ``intelligents''
heuristiques d'ordonnancement des variables, des valeurs
propagation de contraintes (appelée aussi filtrages, suppression d'incohérences locales)
? méthodes de décomposition du problème
? parcours ``exotiques'' de l'arbre de recherche
? phénomène de seuil dans les problèmes aléatoires, problèmes exceptionnellement difficiles
? contraintes non binaires, contraintes globales
? la question de la modélisation d'un problème donné en CSP.
? extensions au modèle de base : maxCSP, CSP dynamiques, CSP valués, etc.
Bibliographie
Consistency in Networks of Relations, A.K. Mackworth, Artificial Intelligence Vol 8, 1977.
Constraint Satisfaction Problems: An Overview, P. Meseguer, AICOM Vol 2, March 1989.
Constraint Processing, Rina Dechter, Morgan Kaufmann, 2003
