Tests
de benchmark avec les fichiers
Renault "X264.lp" ou "X264.csp" ou "X264.c"
Ce benchmark
contient un problème CSP sur des variables discretes, représentant une gamme
automobile de Renault. Il est fournit en trois formats : csp à tupples
(x264.csp), aralia (x264.lp) et fonctions "c" (x264.c).
Contact: helene.fargier@irit.fr,
laurent.cosserat@renault.com
I
- Les données du problème
Le
but de cette section n'est pas d'expliquer intégralement le sens des
contraintes, mais juste de rendre les fichiers suffisamment
compréhensibles pour le codage de tests. On propose trois formats
differents pour la description des données du problèmes
- les variables de configuration, qui
définissent réellement une solution du CSP et qui font l'objet d'un
choix dans une configuration.
- les variables annexes, qui jouent
un rôle dans la diversité. Celles-ci sont toutes booléennes.
On
distingue deux types de variables :
- les variables de configuration, qui
définissent réellement une solution du CSP et qui font l'objet d'un
choix dans une configuration.
- les variables annexes, qui jouent
un rôle dans la diversité. Celles-ci sont toutes booléennes.
et deux types de contraintes:
- Les contraintes definissant la
diversité : les contraintes de definition des versions, le
contraintes disponibilité d'équipements sur les versions, le
contraintes entre equipements
- Les contraintes de definition des
valeurs sur les vehicules de base (Serie) en fonction de la version
lorque l'on choisit le vehicule de serie
I.1 Variables de
configuration
Les
variables de configuration sont de la forme
v<i> :=
#(1,1,[v<i>_<j1>, ...,
v<i>_<jk>]);
Par exemple : v2 := #(1,1,[v2_0, v2_2, v2_3,
v2_4]);
Un cas
particulier important : la variables v264
correspond à la version du véhicule, et joue un
rôle central dans le contrôle
de cohérence (cf. § II).
Certains
variables de configuration sont "optionnelles". Ceci a été
modélisé par l'ajout d'une valeur "No_Val" dans le domaine de
la
variable, qui est compatible avec toutes les contraintes. Par
exemple, v39 := #(1,1,[v39.3, v39.5,No_Val_v39]); indique que
l'utilisateur peut soit choisir pour la variable v39, l'une
valeurs v39.3 ou v39.5, ou ne pas
lui trouver de valeur, ce qui revient au choix No_Val_v39.
I.2 Variables annexes
S'ajoutent
à ces variables des variables annexes (qui n'ont pas forcement besoin
d'etre affectées). Ce sont les variables suffixées en
.Serie? .Pack? .OptionPack?,
.Option?. Elles sont dde la forme
v<i>.<j>.Pack?, v<i>.<j>.OptionPack?, v<i>.<j>.Option? et son boolennes
Les variables
.Pack?. .OptionPack?,
.Option? permettent de mettre en relation Packs et options avec les
versions. La Variable Vehicle.Serie? permet de decider si l'on veut le
vehicule de serie (et donc fixer les variables à leur valeur par
defaut, quand il y en a )
I.3 Les
contraintes sur la diversité
Deux premiers groupes de contraintes spécifient la compatibilité entre
les versions et les
autres variables de configuration. Elles sont de la forme
v<i>.<j> = = disjonction (v264.i1, ...,
v264.in) (contraintes de definition des versions)
ou de
la forme
v<i>.<j>
=> disjonction (v264.i1, ..., v264.in)
(contraintes de
disponibilité des equipemebt sur les versions)
Elles définissent
l'ensemble des versions sur lesquelles la variable var est
possible, et eventuellement fixent des valeurs de configuration en
fonction de la version.
Par exemple:
(v18.1
=> (v264.281 | v264.290)); la valeur V18.1 (pour
la variable v18) n'est disponible que sur les versions v264.281 et v264.290
(v4.2
== (v264.281 | v264.290)); Les versions v264.281
et v264.290 imposent la valeur v4.2 pour la
variable V4, et
cette valeur n'est disponible que sur ces versions.
S'y
ajoutent des contraintes entre équipements, qui lient
directement entre elles les variables de configurations ; elles font
eventuellement intervenir des variables pack ou option
Exemple
: (-(((((v29.1 & v53.2) & -v50.4) &
v29.1.OptionPack) & v53.2.OptionPack) & v50.4.Option));
I.4 Contraintes
de definition des vehicules de base (Serie)
Elles
définissent les valeurs fixées sur les véhicules de base de
chaque version. Elles sont de la forme: v<i>.<j>
<= SerieVehicle & (disjonction de version)
Exemple: (v18.1 <= SerieVehicle & (v264.281 | v264.290)) , pour les
versions v264.281 et v264.290, la
valeur de serie pour la variable v18 est la valeur v18.1
II
- Simulation d'une session de configuration
On peut suivre le protocole décrit dans (Amilhastre et al. 2002),
en choissisant à chaque pas la prochaine variable à affecter (et une
valeur), puis en propageant ce choix, idealement de manière à ce
que les valeurs laissées dans les domaines des variabls libres soient
globalement consistantes (i.e. appartiennent à une solution compatible
avec l'affectation courante).
Cette simulation portera sur les variables de configuration (on peut omettre les variables annexes).
Une variante de ce protocole consiste à introduire dans la suite d'affectation des desacfectations de variables
III
- Controle de la cohérence du modèle ("cohérence de la documentation")
Il
s'agit de vérifier que le modèle fourni est fortement cohérent, plus
précisément : que chaque version définit une solution, que chaque
tupple autorisé par une contrainte de diversité correspond à une
solution et enfin que le véhicule "de serie" definit pour chaque
version est cohérent.
III.1 Dans le modèle CSP à Tupples
Test
de l'existence des versions: verifier que chaque valeur dans de domaine
de la variable v264 appartient à une solution du problème.
Cohérence
du tableau de diversité: pour chaque contrainte de diversité
(sauf les contraintes entre equipements ?) et chaque tupple de la
contrainte, verifier que ce tupple definit une solution (Cohérence
positive des contraintes, au sens de JFPC'2010).
Terst de
cohérence des véhicules de serie : ayant positioné la variable
"VehiculeSerie?" à la valeur "VehiculeSerie", verifier que chaque valeur dans de domaine de la variable v264 appartient à une solution du problème.
III.2 Dans le modèle Aralia
Dans le modèle aralia, le valeurs des variables discretes ont été transformées en variables booléennes v<i>.j
- il faut y prendre garde lors des tests ci dessus : la coherence
positive des valeurs "faux" des variables booléennes n'a pas à
être testée
Test de l'existence des versions: vérifier, pour toute variable v264.i, que l'affectation v264.i = true conduit à une solution
Cohérence
du tableau de diversité: bien que les contraintes soient aussi
satisfaites par les affectations à faux des variables de
configuration v<i>.j1, la cohérence positive n'a pas à être vérifié pour ces affectations. Par exemple, pour les contraintes de la forme (v<i>.j1& ...
& v<i>.jm) => v264.i1 | ... | v264.in , la
cohérence positive de cette contrainte se limite à vérifier que chaque v<i>.j1& ...
& v<i>.jm) & v264.i1 , ..., v<i>.j1& ...
& v<i>.jm) & v264.in conduit à une solution.
Test de cohérence des véhicules de serie : vérifier, pour toute variable v264.i, que l'affectation v264.i = true & VehiculeSerie = true conduit à une solution
IV
- Bibliographie
Jean-Marc
Astesana, Laurent Cosserat, Hélène Fargier. Modélisation par
contraintes et exploitation d'une gamme automobile : nouveaux
problèmes, nouvelles requêtes, nouveaux besoins en programmation par
contraintes . Actes de JFPC 2010.
http://jfpc2010.greyc.fr/articles/6.pdf
Jean-Marc
Astesana, Laurent Cosserat, Hélène Fargier: Constraint-based Vehicle
Configuration: A Case Study. ICTAI (1) 2010: 68-75
ftp://ftp.irit.fr/IRIT/ADRIA/PapersFargier/ICTAI10.pdf
Jean-Marc
Astesana, Laurent Cosserat, Hélène Fargier: Constraint-based modeling
and exploitation of a vehicle range at
Renault's: requirement analysis and complexity study. ECAI 2010 Configuration
workshop,33-39. ftp://ftp.irit.fr/IRIT/ADRIA/PapersFargier/ECAIWS10.pdf
Jérôme
Amilhastre, Hélène Fargier, Pierre Marquis. Consistency restoration and
explanations in dynamic CSPs-Application to configuration. Artificial
Intelligence 35(1-2): 199-234, feb. 2002. ftp://ftp.irit.fr/IRIT/ADRIA/PapersFargier/AmilhastreFargierMarquisAIJ.pdf
Contact: helene.fargier@irit.fr, laurent.cosserat@renault.com