La satisfaction de contraintes (Constraint Satisfaction) est un paradigme fondamental de l’intelligence artificielle et de l’informatique, qui se concentre sur l’identification d’un état ou d’une configuration satisfaisant un ensemble de conditions ou de limitations prédéfinies. Plus formellement, il s’agit du processus de recherche d’une solution à un problème de satisfaction de contraintes (CSP), où une solution est une assignation de valeurs à un ensemble de variables de telle manière que toutes les contraintes imposées sur ces variables soient respectées.
Les concepts fondamentaux de la satisfaction de contraintes reposent sur trois composantes principales. Premièrement, les variables : ce sont les inconnues du problème, auxquelles des valeurs doivent être attribuées. Deuxièmement, les domaines : chaque variable est associée à un domaine, qui est l’ensemble des valeurs possibles que cette variable peut prendre. Ces domaines peuvent être finis ou infinis, discrets ou continus. Troisièmement, les contraintes : ce sont les relations logiques ou numériques qui limitent les combinaisons de valeurs que les variables peuvent prendre simultanément. Une contrainte peut être unaire (impliquant une seule variable), binaire (impliquant deux variables), ou n-aire (impliquant un nombre quelconque de variables). Un Problème de Satisfaction de Contraintes (CSP) est typiquement défini par un triplet (X, D, C), où X est l’ensemble des variables, D est l’ensemble des domaines des variables, et C est l’ensemble des contraintes. Une assignation est dite complète si chaque variable a reçu une valeur, et partielle dans le cas contraire. Une solution à un CSP est une assignation complète qui satisfait toutes les contraintes.
La satisfaction de contraintes est d’une importance capitale car elle fournit un cadre général et puissant pour modéliser et résoudre une très vaste gamme de problèmes combinatoires issus de divers domaines. Sa pertinence réside dans sa capacité à exprimer de manière déclarative les conditions d’un problème, séparant ainsi la description du problème de l’algorithme utilisé pour le résoudre. Cet aspect facilite la formulation de problèmes complexes et permet l’application d’algorithmes de résolution génériques. L’impact de la satisfaction de contraintes se mesure par son rôle central dans le développement de la programmation par contraintes et par sa contribution significative à la résolution de problèmes réputés difficiles en recherche opérationnelle, en planification, en conception et dans de nombreux autres champs d’application de l’intelligence artificielle. Elle permet souvent d’explorer de manière structurée des espaces de recherche immenses, en élaguant les branches qui ne peuvent mener à une solution.
Les applications pratiques de la satisfaction de contraintes sont nombreuses et variées. Dans le domaine de la planification, elle est utilisée pour l’élaboration d’horaires (emplois du temps scolaires, plannings du personnel, horaires de production industrielle) afin d’assurer que toutes les ressources sont correctement allouées et que toutes les conditions (disponibilités, prérequis, capacités) sont respectées. La configuration de produits complexes, comme des ordinateurs ou des voitures, où le client choisit parmi de nombreuses options interdépendantes, est une autre application courante. D’autres exemples incluent l’allocation de ressources (fréquences radio, portes d’embarquement dans un aéroport), le diagnostic de pannes (identifier la cause d’un dysfonctionnement à partir d’observations et de contraintes sur le fonctionnement normal du système), la vision par ordinateur (interprétation de scènes par l’assignation d’étiquettes à des régions d’images tout en respectant des relations spatiales), la bio-informatique (alignement de séquences d’ADN, prédiction de la structure tridimensionnelle des protéines), la vérification de circuits électroniques, ou encore la résolution de puzzles logiques comme le Sudoku, le problème des N reines ou les cryptarithmétiques.
Le concept de satisfaction de contraintes englobe plusieurs nuances et variations. Les CSP les plus couramment étudiés sont les CSP discrets, où les domaines des variables sont finis. Il existe aussi des CSP continus, où les variables peuvent prendre des valeurs dans des intervalles réels et les contraintes sont souvent des inéquations numériques. Lorsque toutes les contraintes ne peuvent être satisfaites simultanément, on parle de CSP sur-contraints. Plusieurs formalismes permettent de gérer ces situations, tels que Max-CSP, qui vise à maximiser le nombre de contraintes satisfaites, ou les CSP pondérés (Weighted CSP), où chaque contrainte a un poids et l’objectif est de minimiser la somme des poids des contraintes violées. Les CSP dynamiques (Dynamic CSP) considèrent des problèmes où les variables ou les contraintes peuvent changer au fil du temps, nécessitant une révision ou une adaptation de la solution. Les CSP distribués (Distributed CSP ou DisCSP) impliquent des variables et des contraintes réparties entre plusieurs agents autonomes qui doivent coopérer pour trouver une solution globale. Enfin, les CSP temporels (Temporal CSP ou TCSP) se spécialisent dans la gestion des contraintes de temps entre événements.
Plusieurs concepts sont étroitement liés à la satisfaction de contraintes. La Programmation par Contraintes (CP) est un paradigme de programmation qui émerge directement de la recherche sur les CSP, intégrant des mécanismes de résolution de contraintes au sein d’un langage de programmation. Les Problèmes d’Optimisation sous Contraintes (COP) étendent les CSP en ajoutant une fonction objectif à optimiser (minimiser ou maximiser) parmi les solutions qui satisfont toutes les contraintes. La Satisfiabilité Booléenne (SAT) est un cas particulier de CSP où toutes les variables sont booléennes et les contraintes sont exprimées sous forme de clauses logiques. La Programmation Logique avec Contraintes (CLP) intègre la résolution de contraintes dans le cadre de la programmation logique. La recherche opérationnelle partage également de nombreux problèmes et techniques avec la satisfaction de contraintes, notamment pour les problèmes d’optimisation combinatoire. Le terme « Problème de Satisfaction de Contraintes » (PSC), ou « Constraint Satisfaction Problem » (CSP) en anglais, est souvent utilisé pour désigner le problème formel à résoudre, tandis que « Constraint Satisfaction » peut faire référence au domaine d’étude ou à l’ensemble des techniques. Il n’existe pas d’antonyme direct, mais les problèmes non contraints ou l’optimisation sans contraintes représentent des classes de problèmes distinctes où l’aspect de restriction par des contraintes est absent ou trivial.
L’origine de la satisfaction de contraintes remonte aux premières recherches en intelligence artificielle dans les années 1960 et 1970. Des travaux pionniers, comme ceux de David Waltz sur l’étiquetage de lignes dans l’interprétation de scènes visuelles ou ceux d’Ugo Montanari sur les réseaux de contraintes, ont jeté les bases du domaine. La formalisation des CSP en tant que tels s’est précisée dans les années 1970 et 1980, notamment grâce aux contributions d’Alan Mackworth, qui a introduit les concepts de consistance d’arc et de chemin, et d’Eugene Freuder. Cette période a vu le développement d’algorithmes fondamentaux pour la résolution des CSP, tels que le backtracking simple, le forward checking, et les algorithmes de maintien de la consistance d’arc (comme MAC). L’essor de la Programmation par Contraintes dans les années 1990, avec l’apparition de langages dédiés tels que Prolog III, CHIP (Constraint Handling In Prolog) et plus tard OPL (Optimization Programming Language), a marqué une étape importante dans la diffusion et l’application industrielle de ces techniques. La recherche continue activement sur des algorithmes de résolution plus performants, des techniques de modélisation plus expressives, et l’exploration de nouvelles classes d’applications.
La satisfaction de contraintes offre plusieurs avantages significatifs. Sa nature déclarative permet aux utilisateurs de se concentrer sur la description du problème (le « quoi ») plutôt que sur la manière de le résoudre (le « comment »), ce qui simplifie la modélisation. Elle assure une séparation claire entre le modèle du problème et l’algorithme de résolution, favorisant la réutilisabilité des solveurs. Sa généralité et son expressivité permettent de modéliser une très grande variété de problèmes combinatoires. La modularité est également un atout, car il est relativement aisé d’ajouter, de supprimer ou de modifier des contraintes dans un modèle existant.
Cependant, la satisfaction de contraintes présente aussi des inconvénients, des défis et des limitations. La plupart des CSP généraux sont NP-difficiles, ce qui signifie que le temps de résolution peut croître exponentiellement avec la taille du problème dans le pire des cas. L’efficacité de la résolution dépend de manière cruciale de la qualité de la formulation du problème (choix des variables, des domaines, des contraintes) et des heuristiques de recherche utilisées (ordre de sélection des variables, ordre de test des valeurs). La propagation de contraintes, bien qu’utile pour réduire l’espace de recherche, peut elle-même être coûteuse en temps de calcul. Modéliser certaines contraintes globales très complexes de manière efficace peut s’avérer difficile. La mise à l’échelle pour des problèmes de très grande taille reste un défi constant. De plus, le débogage des modèles de contraintes peut être ardu, car il est parfois difficile de comprendre pourquoi un ensemble de contraintes n’admet aucune solution ou pourquoi le solveur prend beaucoup de temps. Le choix du bon niveau de consistance à maintenir (par exemple, consistance d’arc versus consistance de chemin) représente un compromis entre la réduction de l’espace de recherche et le coût de l’inférence. Enfin, la gestion des CSP sur-contraints ou l’intégration de préférences utilisateur de manière flexible et efficace pose des défis supplémentaires par rapport aux CSP classiques.