Styles

mercredi 4 juin 2008

Problèmes de Satisfaction de Contraintes

Le rêve de tout développeur : que la machine fasse tout à sa place. Quoi de plus idéal que de pouvoir décrire son problème à un ordinateur et qu’il trouve la ou les solutions tout seul. Plus une ligne de code à développer ! Ce qui est paradoxal en informatique, c’est que le développeur véritablement paresseux est celui qui sera le plus productif. Le paresseux s’entoure d’outils les plus utiles pour avoir le moins de ligne de code à écrire. Un logiciel sans bug, c’est un logiciel sans ligne de code !

Un des outils les plus performants mais encore trop peu utilisé par les paresseux que nous sommes est l’utilisation de systèmes de résolutions de problèmes de satisfaction de contraintes (en anglais : « Constraints Satisfaction Problems solvers »)

Le domaine du traitement des contraintes s’articule autour d’une définition très simple :

- Soit X un ensemble de variables

- Soit D l’ensemble des domaines pour chaque variable de X

- Soit C l’ensemble des contraintes exprimées sur les variables X

Définir l’ensemble des solutions (affectation à chaque variable X d’une valeur de son domaine D) satisfaisant l’ensemble des contraintes C.

Ou alors, montrer qu’il n’y a pas de solution.

Ou alors, montrer quelle est la solution partielle la plus grande (le plus de variable de X affecté à une valeur et respectant l’ensemble des contraintes C)

Ou alors, montrer quelle est la solution complète ou partielle la plus satisfaisante d’après une fonction d’évaluation des solutions (une fonction de coût).

Autour d’une définition aussi simple, s’est construite toute une discipline de l’Intelligence Artificielle avec nombre d’algorithmes à la clé pour trouver toutes ces solutions. De nombreuses applications (comme par exemple la reconnaissance d'objet 3D à partir d'une scène 2D) et de "solvers" ont déjà vu le jour, mais l’usage d’outils de résolution de CSP (Constraint Satisfaction Problem) n’est pas encore aussi généralisé qu’on pourrait l’espérer.

En tant que développeur, on pourrait imaginer plusieurs applications de ces techniques :

- l’optimisation de l’administration des serveurs, notamment des serveurs de base de données (à ce propos, à partir de la version 10g d’Oracle Server, le système détermine par lui-même les meilleurs valeurs à appliquer aux variables de configuration, sans parler du CBO)

- la génération d’interfaces utilisateurs d’après une charge graphique exprimée sous la forme de contraintes.

- Un outil de gestion de projet de type MS Project mais où l’utilisateur ne fait qu’exprimer des contraintes et l’outil en déduit une ou des planifications (MS Project n’est pas très riche pour l’expression de contraintes réalistes).

On peut trouver des implémentations pour ce type d’application, mais on ne sent pas une généralisation de ceux-ci (on peut tout de même s’amuser à utiliser le solveur Excel pour faire de la résolution de contraintes…). Cela est surement du en partie à la difficulter pour le développeur moyen à entrer dans un domaine comme le traitement des contraintes.

Un livre complet sur le sujet et donnant une vue d'ensemble est "Constraint Processing" de Rina Dechter. On peut dire que ce livre est plus du côté de la science que du côté de l'informatique pratique qu'on rencontre en entreprise, mais qui peut s'attendre à un traitement correct du domaine sans passer par des définitions non ambigües et donc, mathématiques ?

Le traitement des contraintes est une technique qui a permi de prouver un théorème sans passer par une démonstration mais en explorant toutes les solutions possibles. Il s'agit du théorème des quatres couleurs
Dans les années 1960 et 1970, Heinrich Heesch s'intéresse à la possibilité de prouver informatiquement le théorème des quatre couleurs. Finalement, en , deux Américains Kenneth Appel et Wolfgang Haken affirment avoir démontré le théorème des quatre couleurs. Leur démonstration partage la communauté scientifique : pour la première fois, en effet, la démonstration exige l'usage de l'ordinateur pour étudier les 1478 cas critiques (plus de 1200 heures de calcul). Le problème de la validation du théorème se trouve alors déplacé vers le problème de la validation :
  • d'une part de l'algorithme d'exploration ;
  • d'autre part de sa réalisation sous forme de programme.
Utilisez-vous des systèmes de résolution de contraintes dans vos tâches quotidiennes ? Etes-vous prêt à essayer d'inclure un solveur dans un de vos prochains projets de développement ?

Aucun commentaire: