Soutenance mémoire
Projet RNTL CO2
Le projet RNTL CO2 (Réseau National des Technologies Logicielles : projet Conception par Contraintes) qui s’est achevé en juillet 2004, avait pour objectif de développer un environnement de calculs et d’aide à la décision en conception. Ce projet regroupait six laboratoires français : quatre entités académiques (LINA, LIPSI-ESTIA, LIP VI, TREFLE) et deux entités industrielles (DASSAULT-Aviation, CRIL Technology). Ce projet a trouvé sa concrétisation dans le développement d’une librairie au sein du LINA et d’un solveur de Problèmes par Satisfaction de Contraintes numériques Constraint Explorer au sein de la société Dassault Aviation [Zim04]. L’équipe du TREFLE a développé de son côté une démarche d’analyse préalable, d’aide à la recherche de caractéristiques structurantes d’un problème de conception en ingénierie mécanique et énergétique [Sca04a, Sca04b] et d’aide à l’expression des contraintes de conception [Ver04]. Ce projet a aussi permis de tester ces méthodes et ces outils sur des problèmes de conception réels , comme, par exemple, la conception d’un double réducteur ou d’un joint labyrinthique. Les algorithmes de résolution utilisés au sein de Constraint Explorer sont aussi présents dans la librairie Elisa et le solveur realpaver [Gra06]. Ils sont tous les deux publiés sous une licence libre, ce qui permet d’avoir accès à leur code.
Outils et travaux existants autour de la conception par contraintes
Les CSP permettent de modéliser de manière assez naturelle les problèmes de conception préliminaire. Les paramètres de conception sont représentés par des variables, alors que les spécifications d’un problème de conception sont exprimées au travers des contraintes d’un CSP [Jan90]. Par exemple, CADRE [Hua96] et IDIOM [Lot98, Smi96] utilisent les techniques de résolution de CSP sur des contraintes décrivant des paramètres géométriques pour améliorer des plans décrivant la disposition d’un plancher d’appartement. De plus, les CSP ont été utilisés très tôt dans le cadre de la conception collaborative [Ser91, Dar94, Lot99]. Ils permettent de propager les changements effectués entre les différents partenaires d’un même projet. La prise en compte de catalogues et de restrictions de domaines remplacent alors la proposition de valeurs uniques par les collaborateurs d’un même projet. Les CSP sont aussi utilisés pour résoudre des problèmes de conflits et d’aide à la négociation [Bow93, Khe94, Bah95, Kle97]. Quelques années plus tard, les CSP ont été utilisés dans le contexte de la phase de recherche de concepts [OSu01]. Cette utilisation est à rapprocher de celle faite en configuration [Stu97, Far02]. Les concepts ou composants sont décrits principalement à l’aide de variables discrètes. Le concepteur dispose de catalogues, dans lesquels il doit choisir des composants. Le reste du modèle décrit les contraintes liées à l’arrangement des composants et la satisfaction de contraintes liées aux performances globales du produit. La structure des solutions obtenue change en fonction des choix des composants, c’est pourquoi plusieurs dérivations du paradigme CSP sont généralement utilisées : les CSP dynamiques [Mit90] et les CSP composites [Sab96]. Dans le premier cas, les variables et les contraintes ont un état actif/inactif, qui est défini en fonction de contraintes d’activation. Dans le second cas, les variables peuvent avoir pour domaines des sous-problèmes, ce qui permet de hiérarchiser les variables et leur domaine en fonction des composants d’un produit. La configuration d’un produit est un processus interactif, qui prend souvent en compte des composants ou des caractéristiques optionnels ou à choisir dans un catalogue [Jun06]. Lors d’une résolution interactive, c’est l’utilisateur et non la machine qui fait des choix pour restreindre l’espace de recherche du problème [Gel96, Oui02, Van06]. L’utilisateur ajoute ou retire des contraintes pour exprimer ses choix ou ses critères. La cohérence des valeurs des domaines doit alors être calculée rapidement à chaque changement effectué par l’utilisateur [Ami02, Far04]. Cependant, l’utilisation de variables sur les domaines continus a rapidement été nécessaire [Sam96, Ben01, Gel03]. Les problèmes définis sont alors continus ou mixtes : les variables discrètes représentent certains choix de valeurs normalisées ou de composants et les variables continues expriment certaines dimensions ou certaines propriétés des phénomènes physiques. Ces problèmes prennent alors en compte de nouvelles connaissances liées au produit, comme la description de phénomènes physiques [Mul02, Hao05, Mer05, Vu05]. Cependant, le choix de composants et leur arrangement restent l’un des principaux objectifs. La gestion de l’incertitude [Ben00] pendant la phase de recherche de concepts est alors traitée en se basant soit sur les CSP valués [Sch97], soit sur les CSP mixtes au sens de Fargier [Far96]. D’autres travaux en conception architecturale ont permis de montrer l’intérêt de l’utilisation des CSP [Tho94, Fis00, Saw01, Zim01, Had02, Fis04, Sca04a, Ver04, Var05, Arb06, HoK06, Mes06]. Les problèmes de conception traités sont alors plus complexes et les variables liées au produit sont en grande partie définies sur des domaines de valeurs continues, contrairement à la configuration ou à la phase de recherche de concepts. L’espace de recherche lié au produit est alors nettement plus grand et le processus de résolution s’avère peu performant. L’élaboration des modèles et la connaissance qu’ils représentent est alors un travail important pour obtenir des solutions pertinentes [Ver04, Sca04a].
Le processus de conception d’un système mécanique
Le processus de conception est jalonné de plusieurs phases [Pah96] que l’on peut généralement séquencer ainsi (voir figure 1) : expression du besoin, recherche de concepts, conception architecturale (pré-dimensionnement : choix d’architecture, de structure et de topologie du produit), conception détaillée. Résoudre un problème de conception peut alors être considéré comme [Jan90,Sca04a] : partir des spécifications fonctionnelles d’un produit et en construire une représentation respectant :
– des lois physiques,
– des données impératives provenant de la phase de réalisation ou de fabrication du produit : matériaux ou ressources disponibles par exemple, limitations de coûts, de temps, etc.,
– la prise en compte de critères portant sur le produit (robustesse, coût, simplicité) ou sur sa réalisation (coût de fabrication, gestes métiers, etc.). La conception détaillée (calculs et simulation, plans détaillés, dimensionnement complet, etc.) est souvent bien plus longue et coûteuse que les phases précédentes. Beaucoup d’efforts y sont souvent consacrés aux dépens de la conception préliminaire. Ainsi, peu d’outils d’exploration de concepts ou d’architectures d’un produit existent, contrairement aux logiciels de CAO qui sont très utilisés dans les bureaux d’études. Les logiciels de CAO permettent surtout de définir une représentation géométrique détaillée d’un produit et de ses composants, et offrent la possibilité de faire de la simulation numérique en se basant sur cette géométrie. De son côté, la conception préliminaire est composée de deux phases : la recherche de concepts et la conception architecturale. Ces phases se basent toutes les deux sur le cahier des charges fonctionnel établi lors de la phase d’analyse du besoin.
Les principes de base sur les CSP numériques
Les CSP numériques sont basés sur des contraintes exprimées en intention comme des relations sur des variables définies sur les nombres réels. Le traitement des domaines continus peut se faire suivant deux approches [Ben06] : une discrétisation des domaines continus sur l’ensemble des nombres flottants suivi de calculs algébriques ou une approche basé sur du calcul ensembliste. C’est cette approche que nous développerons par la suite. Elle fait appel à l’analyse par intervalles et à l’algorithmique qui en découle [Moo66]. Cependant, les domaines continus sont représentés par des intervalles dont les bornes sont des nombres réels, ce qui pose de nombreux problèmes quant à leur représentation informatique et leur utilisation dans les calculs [Ric68, Wan74]. Les nombres réels ne peuvent être tous définis à l’aide d’une représentation basée sur un nombre fini de bits en mémoire. La principale conséquence de cette représentation est l’erreur d’arrondi. A partir de là, le but principal des techniques basées sur les intervalles est de résoudre des problèmes définis comme des relaxations de problèmes continus. Un autre problème important est de prouver l’existence de solutions dans une boîte intervalle, pour garantir les solutions calculées.
Les heuristiques de recherche
La génération de nouveaux noeuds dans l’arbre de recherche fait aussi appel à différentes heuristiques liées au choix des variables et à la manière dont leur domaine est découpé ou énuméré. Le choix de la prochaine variable à découper est souvent crucial pour l’efficacité de l’algorithme de résolution. Une stratégie de tourniquet (ou Round-Robin) peut être appliquée : les variables sont choisies tour à tour de manière équitable, tant que leur domaine peut être découpé. Cette heuristique est simple à mettre en oeuvre et souvent la plus robuste, mais elle n’exploite pas la structure du problème ou d’autres informations liées aux variables ou à leur domaine. Ainsi, d’autres heuristiques assez simples à mettre en oeuvre peuvent être utilisées :
− fail-first : la variable de plus petit domaine est choisie. Cette heuristique est connue pour être mieux adaptée aux domaines discrets.
− reduce-first : la variable de plus grand domaine est choisie. Cette heuristique est connue pour être mieux adaptée aux domaines continus.
− most-constrained variable : la variable la plus contrainte du problème est choisie. C’est celle qui apparaît dans le plus de contraintes et qui possède donc le plus d’opérateurs de réduction.
D’autres heuristiques plus complexes tiennent compte de la structure du problème et du réseau de contraintes. Le graphe de contraintes associé à un CSP peut être décomposé en blocs, formant un graphe orienté acyclique (DAG) [Red96,Bli98,Nev06]. Ce DAG définit alors un ordre partiel entre les blocs et donc entre les variables à choisir. Cette approche s’avère très performante pour les problèmes continus bien contraints (autant de variables que de contraintes) et ne comportant pas de trop grands ensembles de variables couplées.
L’exploration des domaines des variables
Différentes stratégies peuvent être définies suivant le type des domaines. Les domaines continus sont généralement découpés en utilisant la bissection, c’est-à-dire qu’un intervalle est découpé en son milieu afin d’obtenir deux intervalles de taille équivalente. On peut aussi énumérer des petits intervalles, dont la taille correspond à la précision des variables, ce qui s’apparente à l’énumération des valeurs généralement faites sur les domaines discrets. Des valeurs particulières peuvent aussi être choisies au sein des domaines des variables, comme par exemple lors de l’utilisation d’inéquations [Sil99], ou des minima ou maxima de fonctions correspondant aux contraintes. Les domaines discrets sont généralement énumérés, bien qu’il soit tout à fait possible de les découper à la manière des domaines continus. Lors de l’énumération, la première valeur du domaine est en général choisie, mais on peut aussi choisir la plus grande, la plus petite ou celle se trouvant au milieu
Modélisation et aide à la décision en conception architecturale
La notion de modèle et son élaboration sont fondamentales en conception architecturale. En effet, les modèles considérés pendant cette phase permettent de prendre des décisions importantes par rapport au processus de développement d’un produit (cf. chapitre 1). Ils doivent être définis pour aider à prendre des décisions qui concernent l’architecture principale d’un produit. Ces modèles n’ont pas besoin d’être trop exhaustifs quant aux caractéristiques du produit. L’objectif n’est pas de faire de la simulation intensive du comportement du produit, d’autant plus qu’assez peu de choix sont généralement déjà faitsconcernant le produit et ses composants. Ces modèles doivent tenir compte des compromis nécessaires pour prendre de bonnes décisions en accord avec le contexte de la conception préliminaire. La plupart des composants ne sont pas encore déterminés et certaines caractéristiques sont encore incertaines, afin, entre autre, de ne pas restreindre trop tôt le champ d’investigation lié à l’utilisation du produit. Résolution par satisfaction de contraintes pour l’aide à la décision en conception architecturale diagrammes ou de graphes. Il permettent de structurer globalement les concepts les uns par rapport aux autres. Les modèles mathématiques sont issus de l’analyse menée pendant la phase de conception architecturale, lors de l’analyse des concepts et des phénomènes physiques identifiés précédemment. Ces modèles décrivent généralement la géométrie et le comportement physique du produit, de ses composants et de leurs interactions. Chaque modèle mathématique peut décrire un point de vue particulier sur le produit ou un de ses composants. Nous considérons qu’un point de vue correspond au contexte d’exploitation d’un modèle. Chaque point de vue peut être lié à l’expression d’une connaissance métier : fonctionnel, tolérancement, thermique, électrique, etc. Deux modèles différents peuvent décrire le même concept, mais avec un point de vue différent, traduisant une connaissance métier spécifique.
|
Table des matières
CHAPITRE I – Introduction générale
I.1 – Positionnement de la thèse
I.2 – Contexte de la thèse et travaux précédents
I.2.1 – Projet RNTL CO2
I.2.2 – Outils et travaux existants autour de la conception par contraintes
I.3 – Organisation du document
CHAPITRE II – État de l’art
II.1 – La conception préliminaire
II.1.1 – Le processus de conception d’un système mécanique
II.1.2 – La phase de recherche de concepts
II.1.3 – La phase de conception architecturale
II.1.3.1 – Aide à la décision en conception architecturale
II.1.3.2 – Modèle en conception architecturale
II.2 – La programmation par contraintes
II.2.1 – Les principes de base sur les domaines continus
II.2.1.1 – Les erreurs d’arrondis
II.2.1.2 – Le calcul par intervalles
II.2.2 – La propagation de contraintes
II.2.2.1 – Les techniques de consistance locale
II.2.3 – Les algorithmes de recherche
II.2.3.1 – Les heuristiques de recherche
II.2.3.2 – L’exploration des domaines des variables
CHAPITRE III – Élaboration et exploitation d’un modèle pendant la phase de conception architecturale
III.1 – Introduction
III.1.1 – Objectifs et contexte de ce type de modèle
III.2 Modélisation et aide à la décision en conception architecturale
III.2.1 – Adaptation de modèles
III.3 – Connaissance formalisée pendant la phase de recherche de concepts
III.3.1 – Connaissance formalisée à l’aide du cahier des charges fonctionnel
III.4 – Connaissance formalisée pendant la phase de conception architecturale
III.5 – Exploitation du modèle et des solutions
III.6 – Pourquoi utiliser le paradigme des CSP?
III.7 – Points importants pour la réalisation d’un outil d’aide à la décision en conception architecturale
III.7.1 – Types des variables en conception
III.7.2 – Importance des variables de conception architecturale
III.7.3 – Variable explicite ou alias
III.7.4 – Précision des variables
III.7.5 – Représentation des phénomènes physiques
III.7.6 – Gestion des situations de vie
III.8 – Bilan
CHAPITRE IV – Concepts et apports en programmation par contraintes
IV.1 – Etude de l’existant
IV.2 – Nouveaux concepts
IV.2.1 – Gestion de la précision
IV.2.2 – Heuristiques de recherche
IV.2.2.1 – Variables de conception
IV.2.2.2 – Solution de conception
IV.2.2.3 – Apprentissage de la sensibilité
IV.2.3 – Contraintes par morceaux
IV.3 – Benchmarking
IV.4 – Bilan
CHAPITRE V – Étude de problèmes de conception
V.1 – Introduction
V.2 Problèmes de conception
V.1.1 – Circuit d’une pompe et de réservoirs
V.2.2 – Système de refroidissement d’apéritif
V.2.3 – Système de conditionnement d’air sans ailette
V.2.4 – Système de conditionnement d’air avec ailettes
V.3 – Analyse des performances de résolution
V.3.1 – Gestion de la précision des variables auxiliaires
V.3.2 – Analyse du ratio de l’heuristique sur les variables de conception
V.3.3 – Comparaison globale des performances des heuristiques de recherche
V.4 – Bilan
CHAPITRE VI – Conclusion et perspectives
VI.1 – Contribution apportée
VI.2 – Perspectives et futures évolutions
Références bibliographiques
Annexes
Télécharger le rapport complet
