Utilisateur:Léna/Configuration

En informatique théorique, et plus particulièrement en intelligence artificielle, la configuration est un paradigme pouvant aussi bien représenter de la configuration industrielle, telle que la configuration d'un ordinateur ou celle d'une voiture, mais aussi, de manière plus abstraite, des problématiques de bioinformatique ou de design. Configurer un produit, c'est composer un modèle du produit correspondant à des exigences données[1].

Types de configuration

modifier

Modélisation

modifier

Trois niveaux de modélisation co-existent en configuration : celui le plus bas, c'est-à-dire le niveau de l'instanciation, correspond à la description d'un produit en particulier; le second niveau permet de décrire la gamme à laquelle le produit appartient; enfin, le dernier niveau se rapporte aux concepts utilisés pour contruire une gamme de produits[2].

Programmation par contraintes

modifier

La programmation par contraintes, en raison de sa capacité à exprimer des contraintes complexes (telles que la compatibilité entre des valeurs de variables données) et à assurer un certain niveau de cohérence, à l'aide par exemple de la cohérence d'arc, est très utile pour modéliser les problèmes de configuration[3]. Toutefois, les algorithmes associés à la programmation par contrainte cherchent surtout à déterminer l'existence d'une solution et/ou d'un construire une ; le cadre naturel est celui de problèmes fortement contraints (huit dames) alors que, dans le cadre de la configuration, de très nombreuses solutions existent (  possibilités pour un Renault Trafic) et les requêtes associées sont très différentes (détermination du nombre de solutions, recherche de l'origine d'une incohérence)[4].

Logiques de description

modifier

Les logiques de description sont bien adaptées à la description d'un système devant être configuré[5]

Formes compilées

modifier

La forme compilée d'un problème de configuration est une structure de donnée représentant toutes les solutions du problème de manière compact[6].

Diagrammes de décision binaires

modifier

Il est possible de représenter un problème de configuration sous forme de diagramme de décision binaire : chaque variable   sera représentée par un noeud, chaque valeur d'une variable   par une arête du noeud   au noeud   et chaque chemin de la racine au noeud terminal   (respectivement noeud terminal  ) correspond à une affectation valide (respectivement non valide) des variables. Pour respecter la propriété de binarité, c'est-à-dire le fait que chaque noeud ait deux fils, on décompose le domaine   d'une variable en   variables booléennes[6].

Diagrammes de décision multi-valués

modifier

Un diagramme de décision multi-valué est un tuple    est un ensemble de noeuds contenant le noeud terminal   ainsi que la racine   et où   est un ensemble d'arêtes tel que   soit un graphe orienté sans cycle d'origine   et de puit des chemins maximaux  . De plus, on définit   fonction de labellisation des nœuds telle que que  ; chaque arête   est caractérisée par le triplet    est son nœud de départ,   son nœud d'arrivée et   une valeur.

Un diagramme de décision multi-valué associé à un problème de configuration est tel que   correspond au nombre de variables du problème, où chaque nœud   de niveau   correspond à la même variable   et où pour toute arrête  ,   soit dans le domaine de  .

Cartesian Product Tables

modifier

Résolution

modifier

Programmation par contraintes

modifier

Dynamic CSP

modifier

Composite CSP

modifier

Un CSP composite est un CSP où l’activation de variables est conditionné à l'affectation particulière d'autres variables. Plus formellement,

Définition — Un problème de satisfaction de contraintes composite sur des domaines finis (ou DCSP) est défini par un quintuplet   où:

  •   est l'ensemble de variables du problème;
  •   est l'ensemble des domaines des variables, c'est-à-dire que pour tout   on a  ;
  •   l'ensemble des variables initialement activées;
  •   est l'ensemble des contraintes de compatibilité. Une contrainte   est définie par l'ensemble   des variables sur lequel elle porte et la relation   qui définie l'ensemble des valeurs que peuvent prendre simultéanément les variables de  ;
  •   est l'ensemble des contraintes d'activation. Une contrainte d'activation   est définie par l'exemple des tuples   des variables   qui induisent l'activation de la variable  .

On remarquera que, pour les contraintes d'activité, il est possible que  .

Toutefois, Soininen, Gelle et Niemela font remarquer que les CSP composites ne permettent pas d'exprimer l'idée « qu'il puisse y avoir soit un condensateur, soit un refroidisseur », le condensateur et le refroidisseur étant eux-même des variables[7].

CSP à états

modifier

Activity CSP

modifier

Recherche locale

modifier

Configurateurs

modifier

Le rôle d'un configurateur est de rechercher le ou les produits dans la gamme correspondant aux exigences spécifiées par l'utilisateur ; dans le cas où plusieurs solutions existent, le configurateur doit proposer la meilleure (suivant un critère donné, tel que le coût)[8].

Configuration interactive

modifier

Lorsque l'utilisateur d'un configurateur « voit en direct les conséquences de ses choix », on parle alors de configuration interactive. Elle s'oppose à la configuration automatique où l'ensemble des possibilités restantes n'est calculé qu'une fois que l'utilisateur a spécifié tous ses choix[6].

Références

modifier
  1. (en) Timo Asikainen et Tomi Männistö, « A Metamodelling Approach to Configuration Knowledge Representation », dans Proceedings of the International Joint Conference on Artificial Intelligence Workshop on configuration, Pasadena, États-Unis, (lire en ligne), p. 9-16
  2. (en) Lothar Hotz, « Construction of Configuration Models », dans Proceedings of the International Joint Conference on Artificial Intelligence Workshop on configuration, Pasadena, États-Unis, (lire en ligne), p. 23-30
  3. (en) Ulrich Junker et Daniel Mailharro, « The Logic of ILOG (J)Configurator: Combining Constraint Programming with a Description Logic », dans in Proceedings of the International Joint Conference on Artificial Intelligence, Configuration Workshop, (lire en ligne), p. 13-20
  4. (en) Jean Marc Astesana, Yves Bossu, Laurent Cosserat et Hélène Fargier, « Constraint-based modeling and exploitation of a vehicle range at Renault’s: new requests for the CSP formalism », dans in Proceedings of the European Conference on Artificial Intelligence, Configuration Workshop, Lisbonne, Portugal, (lire en ligne), p. 33-39
  5. (en) Junker, U. and Mailharro, D., « The logic of ilog (j) configurator: Combining constraint programming with a description logic », dans proceedings of Workshop on Configuration, IJCAI, vol. 3, Citeseer, , 13--20
  6. a b et c (en) Andreas Hau Nørgaard, Morten Riiskjær Boysen, Rune Møller Jensen et Peter Tiedemann, « Combining Binary Decision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration », dans Proceedings of the International Joint Conference on Artificial Intelligence Workshop on configuration, Pasadena, États-Unis, (lire en ligne), p. 31-38
  7. Soininen, T. and Gelle, E. and Niemela, « A fixpoint definition of dynamic constraint satisfaction », dans Principles and Practice of Constraint Programming--CP’99, Springer, , p. 419-434
  8. Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées evaluation process

Voir aussi

modifier

Liens externes

modifier