Abdourahim Sylla

Delphine Guillon

Rania Ayachi

Elise Vareilles

Michel Aldanondo

Thierry Coudert

Laurent Geneste

How to deal with Engineering-to-Order Product/System Configuration?

This paper considers the configuration of physical systems in a business to business environment (machine tool, aerospace equipment, cranes …). In this kind of business, knowledge-based configuration software are frequently used when dealing with Assemble/Make-To-Order or (Configure-To-Order (CTO)) situations where the entire customer's requirements can be fulfilled with standard systems. However, in Engineer-To-Order (ETO) situations where non-standard systems must be designed in order to fulfill the entire customers' requirements, existing knowledge-based configuration software cannot be used. In fact, the configuration hypothesis state that all configured systems are assembled from standard sub-systems and components. The aim of this paper is therefore to investigate how the existing products/systems configuration hypothesis, problems' definitions, and models can be modified or adapted in order to allow the use of configuration software in ETO situations. In this purpose, first, the main differences between standard and non-standard systems are analyzed. Then, six cases of systems configuration that differentiate CTO from ETO are identified and discussed. Finally, some Constraint Satisfaction Problems (CSP) based modeling extensions are proposed to allow the use of configuration software in these situations.

INTRODUCTION

The current economic environment is characterized by the increasing demand for personalized systems from the client companies. In addition, the requirements on the performances, costs and delivery times of the systems are increasingly constrained. Therefore, in order to propose relevant systems solutions to the client companies, the supplier companies have to design customized systems in a very short period while optimizing time and resources involved in the design process [START_REF] Krömker | An infrastructure to support concurrent engineering in bid preparation[END_REF], [START_REF] Sylla | Customer / Supplier Relationship : reducing Uncertainties in Commercial Offers thanks to Readiness , Risk and Confidence Considerations[END_REF], [START_REF] Cannon | Buyer-Supplier Relationships and Customer Firm Costs[END_REF]. In this article, a system is considered as a set of sub-systems that are integrated following the system architecture.

The design of a system that fulfils the customer' requirements is carried out using three kind of knowledge: (i) the knowledge about the customer's requirements that are the source of the design problem, (ii) the knowledge about the potential systems solutions relevant to these requirements, and (iii) the knowledge about the design methodology [START_REF] Chandrasekaran | Generic Tasks in Knowledge Based Reasoning: High Level Building Blocks for Expert System Design[END_REF]. Depending on the availability of these three kinds of knowledge, two types of industrial situations are encountered by the suppliers when designing systems solutions relevant to the customer's requirements [START_REF] Chandrasekaran | Generic Tasks in Knowledge Based Reasoning: High Level Building Blocks for Expert System Design[END_REF]: (i) Configure-To-Order (CTO) which gathers both Assemble-To-Order and Make-To-Order industrial situations, and (ii) Engineer-To-Order (ETO).

In Configure-To-Order (CTO) contexts, the relevant knowledge necessary for the design of systems solutions that fulfill the customer's requirements are available. The design of a system in this case, consists in choosing systems solutions that correspond to the requirements [START_REF] Chandrasekaran | Generic Tasks in Knowledge Based Reasoning: High Level Building Blocks for Expert System Design[END_REF], [START_REF] Pitiot | Concurrent product configuration and process planning, towards an approach combining interactivity and optimality[END_REF]. This problem refers to the configuration problem also called customization [START_REF] Sabin | Product configuration frameworks-a survey[END_REF]. In this situation, all possible systems solutions that are relevant to the customer's requirements have been totally designed or predefined. The supplier has just to choose one system solution to propose to the customer. This configuration problem is encountered in many industries, including in the automotive, aeronautics or the micro-informatics sectors [START_REF] Felfernig | Knowledge-based configuration From Research to Business Cases[END_REF], [START_REF] Zhang | Product configuration : a review of the state-of-the-art and future research[END_REF]. In fact, most of the time, the systems or sub-systems solutions must be selected from a huge number of types or variants to meet specific customer' requirements [START_REF] Felfernig | Knowledge-based configuration From Research to Business Cases[END_REF], [START_REF] Zhang | Product configuration : a review of the state-of-the-art and future research[END_REF]. Knowledge-based configuration software is very often used by the suppliers to rapidly configure systems that fulfill the customers' requirements.

In Engineer-To-Order (ETO) situations, some modifications or adaptations must be performed on existing systems solutions in order to design systems that fulfil the entire customer's requirements [START_REF] Sylla | Readiness , feasibility and confidence : how to help bidders to better develop and assess their offers[END_REF]. For example, a customer wants a crane system composed of two sub-systems: a jib of 7 meters long and a tower of 10 meters high. The existing solutions cover the tower sub-system. However, until now, the supplier has only designed jibs of 5 and 9 meters long. Therefore, a jib of 7 meters long must be designed and integrated to the other sub-systems solutions in order to fulfil the entire customer's requirements. Depending on the extent of the design activities necessary to define a system solution that satisfy the entire customer's requirements, some authors and practitioners speak of "light" and "heavy" ETO. In any ETO situations, the existing configuration software cannot be used to configure the entire system. Indeed, the configuration makes the assumption that a system is assembled or defined from sub-systems and components that have been totally designed or predefined. The assembly mode of the sub-systems and components is also predefined [START_REF] Mittal | Towards a generic model of configuration tasks[END_REF], [START_REF] Felfernig | Knowledge-based configuration From Research to Business Cases[END_REF], [START_REF] Zhang | Product configuration : a review of the state-of-the-art and future research[END_REF]. As a consequence, some companies use configuration software to design the predefined parts of the system. The other parts are defined manually or using other tools such as Computer Aided Design (CAD) [START_REF] Haug | Reducing variety in product solution spaces of engineer-to-order companies : The case of Novenco A / S[END_REF], [START_REF] Myrodia | Impact of product configuration systems on product profitability and costing accuracy[END_REF], [START_REF] Sylla | ETO Bid Solutions Definition and Selection Using Configuration Models and a Multi-Criteria Approach[END_REF]. This results in additional time, resources and efforts in the design process.

In [START_REF] Felfernig | Towards Open Configuration[END_REF], the authors introduced the concepts of open configuration. They stressed out that one of the characteristics of open configuration is the ability to integrate components and constraints that are not completely predefined during the configuration process. They presented some example application domains of open configuration. However, the aspects related on how to extend configuration principles towards ETO industrial situations have not been addressed.

The aim of this article is to investigate how the existing configuration hypothesis, problems' definitions, and models can be modified or adapted in order to extend the use of configuration software towards ETO industrial situations. In the section 2, relevant products/systems configuration background, including problems definitions and Constraint Satisfaction Problems (CSP) knowledge modelling, are recalled. In section 3, the main differences between standard and non-standards systems are analyzed. Then, six cases of systems configuration that differentiate CTO from ETO are identified and discussed. Some Constraint Satisfaction Problems (CSP) based modeling extensions that consider the six cases of systems configuration in ETO situations are also proposed.

PRODUCT/SYSTEM CONFIGURATION IN CTO SITUATIONS

Configuration problem definition

Since the first configuration problems defined by Mittal [START_REF] Mittal | Towards a generic model of configuration tasks[END_REF], many products configuration problems have been defined in the scientific literature [START_REF] Felfernig | Knowledge-based configuration From Research to Business Cases[END_REF], [START_REF] Zhang | Product configuration : a review of the state-of-the-art and future research[END_REF], [START_REF] Aldanondo | Configuration for mass customization: How to extend product configuration towards requirements and process configuration[END_REF]. According to the problems, different aspects of a product are considered, especially the physical, descriptive, and functional aspects [START_REF] Felfernig | Knowledge-based configuration From Research to Business Cases[END_REF], [START_REF] Zhang | Product configuration : a review of the state-of-the-art and future research[END_REF], [START_REF] Aldanondo | Configuration for mass customization: How to extend product configuration towards requirements and process configuration[END_REF]. Among all these definitions, we consider the key elements proposed in [START_REF] Mittal | Towards a generic model of configuration tasks[END_REF], [START_REF] Aldanondo | Configuration for mass customization: How to extend product configuration towards requirements and process configuration[END_REF]. They are presented as follows:

Hypothesis: a system is considered as set of sub-systems Given:

 each system or sub-subsystem is characterized with a predefined set of attributes which have predefined domains,  the attributes can be either descriptive (length, power for instance) or key performance indicators such as the cost,  the sub-systems that have the same characteristics constitute a family of sub-systems,  the possible combinations or assembly of sub-systems and/or attributes values are predefined with a set of constraints,  a customer's requirements corresponds to the selection of a sub-system or attributes values. Objectives: The configuration consists in finding at least one set of sub-systems that satisfy all the constraints and customer's requirements.

As you can see in this configuration problem definition, only systems and sub-systems that have totally been designed or predefined are considered. This is the common point between the configuration problems and models encountered in the scientific literature. They all assume the following hypothesis [START_REF] Felfernig | Knowledge-based configuration From Research to Business Cases[END_REF], [START_REF] Zhang | Product configuration : a review of the state-of-the-art and future research[END_REF], [START_REF] Mittal | Towards a generic model of configuration tasks[END_REF], [START_REF] Aldanondo | Configuration for mass customization: How to extend product configuration towards requirements and process configuration[END_REF], [START_REF] Soininen | Towards a general ontology of configuration[END_REF], [START_REF] Günter | Knowledge-Based Configuration -Survey and Future Directions[END_REF]: (i) a configured product or system is assembled from predefined sub-systems or components, and (ii) the assembly mode is also predefined. As a consequence, these definitions and models are not suitable to the ETO situations where some sub-systems are not totally designed or predefined.

In this article, in section 3.1, we propose some adaptations of this definition to the ETO situations. In the section 3.2, we introduce the CSP-based modelling framework that is used to model systems configuration knowledge. We also present an example of system configuration in CTO situations.

CSP based knowledge modelling

In the scientific literature, the CSP (Constraint Satisfaction Problem) is the most commonly formalism used to formalize configuration knowledge. It gathers three elements: (i) a set variables, (ii) a finite domain for each variable, and (iii) a set of constraint that establishes relationships between variables [START_REF] Montanari | Network of Constraints: Fundamental Properties and Applications to Picture Processingr[END_REF].

Referring to the configuration problem previously defined, a CSPbased configuration model is defined as follow [START_REF] Sabin | Product configuration frameworks-a survey[END_REF], [START_REF] Sylla | ETO Bid Solutions Definition and Selection Using Configuration Models and a Multi-Criteria Approach[END_REF], [START_REF] Aldanondo | Configuration for mass customization: How to extend product configuration towards requirements and process configuration[END_REF]: each sub-system family and each attribute is associated to a variable. A specific sub-system or attribute value is then a value in its corresponding variable domain. The constraints are used either to specify acceptable combinations of sub-system solutions and/or attribute values. For example, in the Fig. 1, the sub-system jib is associated to the variable "Jib solution". Its descriptive attributes are associated to the variables "Length" and "Stiffness". The length of the jib has two possible values "5 meters" and "9 meters" which represents its domain. The constraints are represented with the full line. They link the attributes' values to their corresponding subsystems' solutions. Using this model in a configuration software, if the customer' requirements correspond to these solutions; the supplier can configure rapidly at least one solution that cover all the requirements. However, if the customer's requirements exceed these solutions, the supplier cannot exploit this model in a configuration software to configure a crane system solution that covers all the requirements, even if the supplier is able to design, produce or assemble and deliver that solution.

Figure 1: System configuration model in CTO situations

In the next section, we propose some modifications or adaptations to the existing configuration problems' definitions and models in order to allow the use of configuration software in ETO situations.

PROPOSITIONS

In this section, we propose some elements that allow to extend the use of configuration software from CTO towards ETO situations. For this purpose, like Myrodia et al. [START_REF] Myrodia | Impact of product configuration systems on product profitability and costing accuracy[END_REF], Aldanondo et al. [START_REF] Aldanondo | Configuration for mass customization: How to extend product configuration towards requirements and process configuration[END_REF] and other authors, we distinguish : the sub-systems, integrations and systems that have been totally designed or predefined as standard elements, and those that have not been totally designed or predefined as non-standard ones. In the section 3.1, we analysis the main differences between standard and non-standard systems that allow to identify six cases that differentiate the configuration of systems in ETO from CTO situations. In the section 3.2, using a simple example, we show how a configuration model relevant to CTO can be adapted and extended towards ETO situations.

Differences between CTO and ETO

In this section, an analysis of the characteristics of standards and non-standards systems has allowed us to identify the main characteristics which permit to distinguish them. These characteristics rely on: the descriptive attributes of the sub-systems and systems, and the sub-systems that compose the systems. These two elements (descriptive attributes and sub-systems) may: (i) be standard or non-standard, (ii) take standard or non-standard values/instances, and (iii) be the object of standard or non-standard associations/integrations. On this basis, we will talk about standard systems configuration (a configuration in a CTO situation) when all elements, all values or instances, and all associations or integrations are standard. In contrast, for any other case, we will talk about non-standard systems configuration. Thus, the presence of a non-standard feature implies a case of non-standard systems configuration (a configuration in a ETO situation). This analysis has leaded us to identify six cases that differentiate the configuration in CTO from ETO. They represent the different cases of systems configuration in CTO situation. Three cases concern the sub-systems and three relate to the systems. They are presented in Fig. 2 and are described in the following.

The three cases at the sub-system level are:

Case 1: Non-standard association of standard values for the descriptive attributes. This happens when two or more descriptive attributes values that have never been associated together to configure a sub-system have to be associated in order to fulfil customer' requirements. For example, in the Fig. 1, a jib with "5 meters" long and "strong" stiffness is required by a customer. Case 2: Addition of non-standard values for a descriptive attribute. This happens when a non-standard value must be considered for a descriptive attribute in order to fulfill customer's requirements. For example, a customer wants a jib with "11 meters" long. Case 3: Addition of non-standard attribute for a sub-system. In this case, a non-standard attribute must be added to configure a subsystem that fulfills customer's requirements. For example, a customer asks for a jib with a specific "shape".

The three cases at the system level are:

Case 4: Non-standard integration of standard instances or solutions for the sub-systems. This happens when two or more sub-systems solutions that have never been integrated together to configure a system, must be integrated to fulfil customer' requirements. For example, the jib "ji_1" and the tower "To_2" must be integrated to fulfil a customer's requirements in the Fig. 1. Case 5: Addition of a non-standard instance or solution for a subsystem. This happens when a non-standard sub-system solution must be considered for a sub-system in order to fulfill customer's requirements. For example, a customer wants a tower different from "To_1" and "To_2". Case 6: Addition of non-standard sub-system to a system. In this case, a non-standard sub-system that has never been considered in a system must be added to configure a system that fulfills the customer's requirements. For example, a customer wants a control cabin.

In each of these six cases, all the standard solutions that constitute the diversity of systems (options and variants), formalized in a generic model, do not cover the entire customer's requirements. Non-standard systems must be configured. However, as the knowledge related to these non-standard systems is not formalized in a generic model, they cannot be exploited in a configuration software to configure a non-standard system relevant to the customer's requirements.

Therefore, in order to allow the construction of generic models that gather knowledge related to both standard and non-standard systems, a definition of standard and non-standard system configuration problem is proposed in the following. It includes standard and non-standard element.

Figure 2: The six cases of systems configuration in ETO situations

Hypothesis: a system is considered as set of sub-systems; Given:

 each system or sub-subsystem is characterized with a standard or non-standard set of attributes which have standard or non-standards values in their domains,  the attributes can be either descriptive (length, power for instance) or key performance indicators such as the cost,  the sub-systems that have the same characteristics constitute a family, they can be standard or non-standard,  the possible combinations or assemblies of sub-systems and/or attributes values are defined with a set of constraints, the combinations can be standard or nonstandard,  a customer's requirements corresponds to the selection of a sub-system or attributes values. Objectives: The configuration consists in finding at least one set of standard and/or non-standard sub-systems that satisfy all the constraints and customer's requirements.

Based on this definition, in the section 3.2, we propose some modelling approaches that enable to extend existing configuration models relevant to CTO towards ETO situations.

CSP-based Modelling approaches for systems configuration in ETO situations

For each of the six cases of configuration of systems in ETO situations listed in the section 3.1, we have proposed some modifications on the existing configuration models in order to include knowledge related to non-standard elements in the generic models. These modifications include changes to the variables and their domain (the set of possible values), as well as changes to the constraints that bind them. In this article, we only present the extension for the case 1 at the sub-system level and the case 5 at the system level. The same example used for the configuration of system in ETO is used. The model is presented in the Fig. 3. This model is a very simple one. The aim is to show how a configuration model relevant to CTO situation can be modified and extended towards ETO.

At the upper level of the Fig. 3, the sub-system model (case 1) is presented. The same variables as for the configuration model in CTO situation are kept. The main differences are:

 a non-standard sub-system instance or solution "Ji_NS" is added to the domain of the "Jib Solution", this enable the supplier to know that this solution has not been totally designed yet.  a constraint is added for the non-standard association of standard values; it links the values "5 meters" of the attribute "length", the value "strong" of the attribute "stiffness" and the non-standard solution "Ji_NS";

At the lower level of the Fig. 3, the system model (case 5) is presented. The same variables as for the configuration model in ETO situation are also kept. The main differences are:

 a non-standard sub-system instance or solution "Ji_NS" is added to the domain of the "Jib Solution", it results from the modification made at the sub-system level;  a non-standard system instance or solution "Cr_NS" is added to the domain of the "Crane Solution"; as for the sub-system, it enables the supplier to know that this system has not been totally designed yet;  two constraints are added for the non-standard integrations of : "Ji_NS" and "To_1", and "Ji_NS" and "To_2".

For both AMTO and ETO industrial situations, the knowledge necessary to setup the configuration models must be defined by expert teams composed of people from the sales, manufacture, and design departments. The experts must decide on the standard and non-standard systems that can be designed, produced and delivered to a potential customer. This means, with respect to six cases identified in section 3.1, deciding which of the following nonstandard aspects can be accepted: (i) combination of standard attribute values, (ii) attribute values (iii) attributes, (iv) integration of standard sub-system solutions, (v) integration of standard and non-standard sub-system solutions and (vi) sub-system. After identifying and validating the knowledge necessary to setup the configuration models for both AMTO and ETO situations, the proposed modelling approach can be used to build configuration models relevant to configure systems in both AMTO and ETO industrial situations.

CONCLUSION AND FUTURE WORK

In this article, we have studied the configuration of physical systems in the context of business to business environment where a supplier has to propose a system solution to a client company in a very short period while optimizing time, resources and efforts involved. The aim of the article was to propose some solutions in order to extend the use of configuration software from CTO towards ETO situations. For this purpose, first, we have shown why the existing configuration hypothesis, problems' definitions and models are not adapted for systems configuration in CTO situations. Then, we have analyzed the main differences between standard and nonstandard systems. This has allowed us to identify six cases of systems configuration that differentiate the configuration of systems in CTO from ETO situations. The six cases represent the different situations of systems configuration in ETO. This is the main contribution of this article. As far as we know, no scientific work has proposed a formalization of the differences between systems configuration in CTO and ETO situations. Finally, based on these six cases and the configuration background, we have proposed a definition and some CSP (Constraint Satisfaction Problems) modelling approaches for systems configuration problems in CTO and ETO situations. A simple example is used to illustrate the propositions.

As a future research, we intend to test the applicability of our proposals on a larger case of systems configuration. We also intend to extend the configuration of processes relevant to CTO towards ETO.

Figure 3 :

 3 Figure 3: System configuration model in ETO situations

ACKNOWLEDGMENTS

The authors would like to thank all ANR OPERA partners for their implications in our research work.


Insights for Configuration in Natural Language

Andrés F. Barco 1 and Élise Vareilles 2 and César I. Osorio 1 Abstract. Usually, in configuration processes, customers interact with a decision support system, also named configurator, by explicitly selecting components or required functionalities through a written series of questions, until the complete configuration is done and the desired product is defined. The interactions during a configuration process may vary vastly depending on the customers' knowledge about the product and his/her understanding of its potential functionalities. However, configurators are not conceived for making a difference between expert and inexpert customers as interfaces and input information are all expected to be the same for everyone. This paper discusses how natural language can enhance configuration process by making possible for customers to express their desires, needs and preferences in natural language, and for configurators to interpret their words and better help them to find relevant solutions. This kind of configuration process could have as foundations an expert systems that that maps speech into constraints and objectives. We present the artificial intelligence trends motivating our research, an initial architectural design and potential applications of the research.

Introduction

For several decades now, customers want to bring a personal touch to their products to make them special and unique. To meet this growing demand of personalization, companies nowadays no longer offer standard products, but more and more personalizable ones [START_REF] Ardissono | Personalising on-line configuration of products and services[END_REF]. Thanks to the Web technologies and dedicated decision support systems, named configurators, this personalization is done directly and interactively online [START_REF] Ardissono | Personalising on-line configuration of products and services[END_REF]. Customers can play with the wide range of choices and options offered by companies: they can assemble, cut, color, choose, ..., and visualize the result of their desires and ultimately order it, all in few clicks and minutes.

This concept of personalization or configuration of products consists in assembling modules or predefined components, to produce a unique and specific product [START_REF] Felfernig | Knowledge-based Configuration: From Research to Business Cases[END_REF]. For businesses, this is a way to offer personalized products to stand out from the competition and build customers' loyalty through more accurately reflecting their tastes and needs.

Interactions between potential customers and configurators, become now one of the key aspects of configuration problems [START_REF] Tseng | Mass Customization[END_REF]. Nevertheless, often the configuration relies in a long data capturing process. Normally, to configure the product object of desires, any potential customer has to:

1. Face the increasing range of choices and options without being completely able to focus on his/her essential items,

1 Universidad de San Buenaventura Cali. Santiago de Cali, Colombia. email: {anfelbar,ciosoriod}@usbcali.edu.co 2 Université de Toulouse, Mines Albi. Albi, France. email: elise.vareilles@mines-albi.fr 2. answer a predefined series of questions, always in the same order whatever his/her knowledge and needs about the product, 3. express his/her needs and preferences in such a way they fit the predefined set of choices and options proposed online by configurators, and 4. click to select the relevant functions or components meeting the best of his/her needs.

All these facts gathered make the configuration of products more and more a counter-intuitive process. Also, current interaction makes no difference between expert and non-expert user as most of the input mechanism (such of as graphical windows, drawings, text fields) are all expected to be the same for everyone [START_REF] Ardissono | Customising the Interaction with Configuration Systems[END_REF].

This paper discusses how the mature techniques from AI may be used to allow a more natural interaction between customers and configuration systems. In essence, we describe the future of configuration in which natural language interactions could replace the traditional one based on writing, explicit selection of items and rigid series of questions. More precisely, we argue that current AI advances like natural language processing could help customers to express their needs implicitly in speech format (e.g. "I need a cheap laptop with good video card") while an expert system could infer the requirements and set the goals of the configuration (e.g. video card ≥ good). We call this kind of configuration Configuration in Natural Language. We also present an idea of architecture of such an expert system.

The paper is divided as follows. In Section 2, the traditional and future customer-system interactions in configuration are discussed. In section 3, a software architecture based on current advances in AI is introduced. In Section 4, some of the mathematical frameworks from which the configuration in natural language can take advantage are discussed. Finally, in Section 5, some applications of the research and conclusions are presented.

Configuration Interactions: Past and Future

We present in this section the interaction typically made in configuration systems and contrast it with the idea of configuration in natural language proposed in this paper.

Traditional Configuration Interactions

In most of the cases, configuration systems follow a series of iterative steps that guide the customer and help him/her to progressively configure his/her own product. These steps, that we call the standard way of configuration, are as follows:

1. The system shows some sets of components and functionalities to the customer in a predefined way, 2. The customer either selects the most relevant component or functionality which meets his/her needs and desires, or specifies a value for the most important criteria (such as the price he/she is willing to pay for the product), 3. The system removes or assigns the set of remaining components and functionalities according to the set of constraints in the product, 4. The system computes the price of each possible product and valuates their criteria.

In step 2, the selection is usually done manually by clicking on the relevant item via a mouse-click or a touch screen, or by inputting its specific value directly from a keyboard. At the end of the standard way of configuration, the customer selects his/her unique product and orders it.

Future Configuration Interactions

The configuration in natural language changes the interactions between customers and configurators. Customers will be able, whatever their requirements and knowledge about the product, to express better in a more natural way their preferences, desires and needs and configure faster their own products. The significant difference between traditional and forthcoming configuration interactions lies in the way of expressing and capturing customers' needs and goals. The steps for the configuration in natural language are as follows:

1. The system welcomes the customer. 2. The customer writes or says what he/she wants or needs by using his/her own words. 3. The system infers the set of components and functionality the user wants or needs, and the goal of the configuration. 4. The system removes or assigns the set of remaining components and functionalities according to the set of constraints in the product. 5. The system computes the price of each possible product and valuates their criteria.

To exemplify this kind of configuration, limit us to written interactions in natural language via a keyboard or similar device. Three examples of such interactions when configuring a computer, and the respective responses of the inferring engine, are: As expected, inferring components or functionalities and configuration objectives is a major challenge. On the first hand, the universe of words used by humans to express the same thing may be vast. Second, the way to build expressions may vary largely depending on academic background, experience, state of mind and mood, to name a few. Finally, it is difficult to set a difference between components and functionalities, and goals; critical to reach an appropriate configuration solution. For instance, in the first of the two previous examples, both the processor speed and the computer cost may be seen as configuration goals. For tackling this challenge, we propose an expert system architecture built upon AI trends.

AI Trends-based Architecture

The field of AI is generating broad interest. Technological advances using AI techniques, such as the DeepMind GO system developed by Google TM [START_REF] Silver | Mastering the game of go with deep neural networks and tree search[END_REF] and the IBM Watson TM analytic system [START_REF] Ferrucci | Introduction to "This is Watson[END_REF], draw the attention of the academic and non-academic world on the innovative role of mathematical models from computer science and philosophy. Current trends show that the use of AI and other related fields are being widely used sectors such as economy, health, transport industry, aviation and games, among others [START_REF] Stone | Artificial intelligence and life in 2030[END_REF].

The configuration in natural language is motivated by the recent advances in AI and by industrial trends, in particular the growing interest in the construction of machines that understand human emotions and act according to the interaction with human [START_REF] Marsella | Computationally modeling human emotion[END_REF]. It is sought that the machines assist decision-making processes whereas the understanding of human emotions helps to improve the expert systems behavior and interaction [START_REF] Celso | do as i say, not as i do": Challenges in delegating decisions to automated agents[END_REF]. This idea, known as Human Aware AI, is not new in configuration as it has been used as a goal in different configuration systems (see for instance [START_REF] Barker | Expert systems for configuration at digital: Xcon and beyond[END_REF]). Further, the idea of understating or inferring user needs has been widely study in the plan recognition problem [START_REF] Carberry | Techniques for plan recognition[END_REF]. Nonetheless, to the best of our knowledge, current advances in natural language use remain to be adopted in configurators implementations.

Within the human aware AI field, the Natural Language Understating (NLU) [START_REF] Bates | Models of natural language understanding[END_REF] and Natural Language Processing (NLP) [START_REF] Gobinda | Natural language processing[END_REF] draw attention for its capabilities of human computer interaction. In essence, NLU and NLP systems allow the user to ask questions in everyday language and try to understand these questions in order to return appropriated answers. Typically, these systems makes some hypothesis according to the question and a knowledge base, such as Internet, and then process an output. This is akin to the problem of plan recognition, i.e., knowing the user's plans and goals [START_REF] Carberry | Techniques for plan recognition[END_REF]. Further, if these systems are improved with natural language generation (NLG) in order to produce responses, the system then becomes a question answering system (QAS) [START_REF] Hirschman | Natural language question answering: The view from here[END_REF]. These systems were conceived to received provide argued answers to user queries. From these systems, WolframAlpha TM [START_REF] Cassel | Wolfram-Alpha: A Computational Knowledge "Search" Engine[END_REF] and IBM Watson TM [START_REF] Ferrucci | Introduction to "This is Watson[END_REF] present the more innovative results for configuration as these systems are able to recognize some information in form of requirements within informal speech in text format.

To illustrate these capabilities, Figure 1 shows the result when querying "I want a computer of less than 1000 dollars." in the WolframAlpha TM system. To construct a response, the system maps the input into a more elaborated query, encoding the query thus making a syntactic and semantic analysis. Nevertheless, as the system does not focus on inferring mathematical notions, it is easily confused by adding words that add relevant constraints. For instance, no result shown when querying the same computer but Dell TM manufactured; "I want a dell computer of less than 1000 dollars". We consider that this is a major drawback in the system when addressing configuration problems.

The IBM Watson TM system works similarly to the WolframAlpha TM . It encodes a query by applying automated reasoning, machine learning and several other techniques to analyze the speech. One of the more innovative applications of the IBM Watson TM system is the personality characterization from written speech. To do this, in addition to question answering, different techniques of sentiment analysis [START_REF] Taboada | Sentiment analysis: An overview from linguistics[END_REF] are applied. This kind of analysis may be useful to infer expertise level of the user and then behave accordingly.

In spite of the recent advances of NLU, NLP and QAS, these are not well-suited for addressing configuration problems given that they do not focus on constructing the mathematical notions (constraints and objectives) needed in most configuration problems. Besides, question answering systems are too powerful in the sense they are of general purpose having different question types and extensive knowledge bases. At the other end of the spectrum, specific applications using question answering systems technology do not necessarily deal with extensive vocabularies, hypothesis and so on, as these applications are domain-dependent. Ergo, its underlying mechanism may be simpler although more robust and may count with reduced knowledge, question types and small knowledge bases. In consequence, we have devise an architecture, presented in Figure 2, for implementing configurators that exploits the aforementioned natural language elements. The mandatory module is that of NLU whereas NLP and NLG are optional (used if formatted answers are desired). External services may be attached in order to fulfill specific tasks.

The differentiating element in the architecture is the inference engine. This key element is in charge of discriminating among the set of words those referring to components of the product, functionalities and/or configuration objectives. This is in fact a challenge as different conclusions may be reached from a given sentence.

Mathematical Frameworks for Configuration in Natural Language

Unlike NLP and QAS, configuration processes are mapped, generally, into mathematical (optimization) models that unify the customers requirements and problem domain limitations into a single framework. To infer constraints and objectives from informal speech, it is needed an underlying mathematical framework in which such notions are built. In other words, to construct a mathematical formula it is necessary the set of values and operands allowed in the formula.

As an example, if constructing inequalities, the expert system knows that sum, subtract, division and multiplication are allowed as well as inequality symbols. This helps to make the mapping unambiguous. Given that our main innovative application is the configuration in natural language, mathematical frameworks used to tackle configuration problems comes naturally. Here, we briefly describe three of these models.

• The first framework, Constraint Programming (CP), has been identified as a key paradigm in the expansion of applied computer science [START_REF] Rossi | Handbook of Constraint Programming[END_REF]. CP is part and good representative, of the declarative programming frameworks. This is one of the most used framework to address configuration problems as it suits their constrained nature [START_REF] Junker | Configuration[END_REF]. First, the knowledge (constraints) that restricts possible configuration of elements (variables) is easily modeled under the declarative framework of constraint satisfaction problems. And second, constraint-based configurators are able to present different solutions to users, often optimal, even when they do not provide all configuration parameters. • Among the same lines we have integer programming (IP). It is a mathematical optimization in which some or all of the variables are restricted to be integers [START_REF] Sierksma | Linear and Integer Programming: Theory and Practice, Second Edition[END_REF]. Likewise the constraint satisfaction model, it is built from constraints and limitations over variables, although variables do not have a given domain, and objective functions such as minimization and maximization. This model or extensions of it (Mixed IP or Linear IP) have been widely used to reason and solve configuration problems (see for instance [START_REF] Feinerer | Efficient large-scale configuration via integer linear programming[END_REF]). • Finally, another framework that can be used in configuration in natural language is SAT; determining if a given propositional formula is satisfiable by an interpretation [START_REF] Biere | Handbook of Satisfiability[END_REF]. The inclusion or exclusion of a given feature in a product may be seen as boolean assignments. Thus, it would be possible to deduce if a solution exists by constructing a boolean formula using the requirements of the customers and the configuration knowledge (e.g. compatibility among components). The modeling of a configuration problem under SAT is not new (see for instance [14]).

Concluding Remarks

In this paper, we have presented insights on how to enhance the interaction between customers and configuration systems into something called configuration in natural language. In summary, we have discussed the possibility of using AI techniques, namely, human-aware AI to implement an expert system that infers constraints and objectives from a speech input.

We have built out the idea around the concepts of NLU, NLP and QAS. Then, we argue that although current systems have reached a stable development, there is still research to be done when inferring mathematical notions from informal sentences, i.e., everyday language. In addition, we have argued that advanced question answering systems such as IBM Watson TM are not yet well suited for configuration problems as they are not intended to map implicit requirements into mathematical models.

To give a view of the mathematical models that can prove useful to construct the proposed expert system, we have briefly described three techniques from AI and operational research. These, techniques, namely, constraints programming, integer programming and boolean satisfiability, have been used to solve different configuration and optimization problems and are in our point of view interesting models to construct a configurator in natural language.

The main application of inferring constraints and goals from speech is linked to the mathematical modeling of real-world problems. Simply stated, the inference system may be used to build mathematical models to solve linear problems, discrete optimization problems and probabilistic problems, among others. Further, specific properties from each mathematical framework may be exploited, such as the expressivity of declarative approaches like logic and constraint programming. Intuitively, many more applications exists; those in which user requirements, preferences, limitations or objectives are needed. For instance package managers in unix-based operating systems. Typically, a package manager from a Unix-based system must be asked to search or install a specific package. Using a expert systems that maps speech into constraints and objectives, a manager would accept inputs like "I need a powerful UML diagram editor" to present some potential editors to be installed. Further, arguments used by such managers can be replaced by everyday words thus preventing the non-expert user to learn the specifics of the programs.

Figure 1 .

 1 Figure 1. Output example of WolframAlpha TM system.

Figure 2 .

 2 Figure 2. Architectural view of expert system for configuration NL.


Paul Pitiot
email: paul.pitiot@mines-albi.fr

Michel Aldanondo

Élise Vareilles

Thierry Coudert

Paul Gaborit

Elise Vareilles

Improving configuration and planning optimization : towards a two tasks approach

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

This article is about the concurrent optimization of product configuration and production planning. Each problem is considered as a constraint satisfaction problem (CSP) and these two CSP problems are also linked with some constraints. In a previous paper [Pitiot et al., 2013], we have shown that this allows to consider a two-step process: (i) interactive configuration and planning, where nonnegotiable user requirements (product requirements and production process requirements) are first processed thanks to constraint filtering and reduce the solution space (ii) optimization of configuration and planning, where negotiable requirements are then used to support the optimization of both product and production process. Given this problem, product performance, process cycle time and process plus product cost can be optimized, we therefore deal with a multi-criteria problem and our goal is to propose to the user solutions belonging to the Pareto front. For simplicity we only consider cycle time and total cost (product cost plus process cost), consequently the twostep process can be illustrated as shown in figure 1. Some experimental studies, reported last year [START_REF] Pitiot | [END_REF], discusses optimization performance according to problem characteristics (mainly size and constraint level). That last paper proposes to divide the step 2 (Pareto front computation) in two tasks, particularly in the case of large problems: (i) a first rough computation that permit to have a global idea of possible compromises (ii) a second computation on a restricted area that is selected by the user. The goal of this article is to present experimental results that show that this idea allows to significantly reducing optimization duration while improving optimization quality. In this introduction, we clarify with a very simple example what we mean by concurrent configuration and planning problem and relevant optimization needs. Then the second section formalizes the optimization problem, presents the optimization algorithm and describes the experimental study. The third section is dedicated to various experimentations.

Configuration and planning processes.

Many authors, since [Mittal and Frayman, 1989], [Soininen et al., 1998] or [Aldanondo et al., 2008] have defined configuration as the task of deriving the definition of a specific or customized product (through a set of properties, subassemblies or bill of materials, etc…) from a generic product or a product family, while taking into account specific customer requirements. Some authors, like [Schierholt 2001], [Bartak et al., 2010] or [Zhang et al. 2013] have shown that the same kind of reasoning process can be considered for production process planning. They therefore consider that deriving a specific production plan (operations, resources to be used, etc...) from some kind of generic process plan while respecting product characteristics and customer requirements, can define production planning. Many configuration and planning studies (see for example [Junker, 2006] or [Laborie, 2003]) have shown that each problem could be successfully considered as a constraint satisfaction problem (CSP). We proposed to associate them in a single CSP in order to process them concurrently. This concurrent process and the supporting constraint framework present three main interests. First they allow considering constraints that links configuration and planning in both directions (for example: a luxury product finish requires additional manufacturing time or a given assembly duration forbids the use of a particular kind of component). Secondly they allow processing planning requirements even if product configuration is not completely defined, and therefore avoid the traditional sequence: configure product then plan its production. Thirdly, CSP fit very well on one side, interactive process thanks to constraint filtering techniques, and on the other side, optimization thanks to various problem-solving techniques. However, we assume infinite capacity planning and consider that production is launched according to each customer order and production capacity is adapted accordingly. In order to illustrate the problem to solve we recall the very simple example, proposed in [START_REF] Pitiot | [END_REF], dealing with the configuration and planning of a small plane. The constraint model is shown in figure 2. The plane is defined by two product variables: number of seats (Seats, possible values 4 or 6) and flight range (Range, possible values 600 or 900 kms). A configuration constraint Cc1 forbids a plane with 4 seats and a range of 600 kms. The production process contains two operations: sourcing and assembling. (noted Sourc and Assem). Each operation is described by two process variables: resource and duration: for sourcing, the resource (R-Sourc, possible resources "Fast-S" and "Slow-S") and duration (D-Sourc, possible values 2, 3, 4, 6 weeks), for assembling, the resource (R-Assem, possible resources "Quic-A" and "Norm-A") and duration (D-Assem, possible values 4, 5, 6, 7 weeks).

Two process constraints linking product and process variables modulate configuration and planning possibilities: one linking seats with sourcing, Cp1 (Seat, R-Sourc, D-Sourc), and a second one linking range with the assembling, Cp2 (Range, R-Assem, D-Assem). The allowed combinations of each constraint are shown in the 3 tables of figure 2 and lead to 12 solutions for both product and production process.

Optimization needs

With respect to the previous problem, once the customer or the user has provided his non-negotiable requirements, he is frequently interested in knowing what he can get in terms of price and delivery dates (performance is not considered any more). Consequently, the previous model must be updated with some variables and numerical constraints in order to compute the two criteria. The cycle time matches the ending date of the last production operation of the configured product. Cost is the sum of the product cost and process cost.

Optimization problem and techniques

The optimization problem is first defined, and then the optimization algorithm that will be used is described. Finally, the experimental process is introduced.

Optimization problem

The optimization problem can be generalized as the one shown in figure 5. The constrained optimization problem (O-CSP) is defined by the quadruplet <V, D, C, f > where V is the set of decision variables, D the set of domains linked to the variables of V, C the set of constraints on variables of V and f the multi-valued fitness function. The set V gathers: the product variables and the resource process variables (we assume that duration process variables are deduced from product and resource). The set C gathers: only configuration constraints (Cc) and process constraints (Cp). The variables operation durations and cycle time are linked with a numerical constraint that does not impact solution definition and therefore does not belong to V and C. The same applies to the product/process cost variables and total cost, which are linked with cost constraints (Cs) and total cost constraints. The filtering system allows dynamically updating the domain of all these variables with respect to the constraints. The variables belonging to V are all symbolic or at least discrete. Duration and cost variables are numerical and continuous. Therefore, constraints are discrete (Cc), numerical (cycle time and total cost) or mixed (Cp and Cs). Discrete constraints filtering is processed using a conventional arc consistency technique [Bessiere, 2006] while numerical constraints are processed using bound consistency [Lhomme, 1993].

Optimization algorithm

A strong specificity of this kind of optimization problem is that the solution space is large. [Amilhastre et al, 2002] report that a configuration solution space of more than 1.4*10 12 is required for a car-configuration problem. When planning is added, the combinatorial structure can become huge. Another specificity lies in the fact that the shape of the solution space is not continuous and, in most cases, shows many singularities. Furthermore, the multi-criteria problem and the need for Pareto optimal results are also strong problem expectations. These points explain why most of the articles published on this subject, as for example [START_REF] Hong | [END_REF] or [START_REF] Li | [END_REF] consider genetic or evolutionary approaches to deal with this problem. In this article we will use "CFB-EA" (for Constraint Filtering Based Evolutionary Algorithm) a promising algorithm that we have designed specifically for this problem. CFB-EA is based on the SPEA2 method [START_REF] Zitzler | [END_REF] which is one of the most useful Pareto-based methods. It's based on the preservation of a selection of best solutions in a separate archive. It includes a performing evaluation strategy that brings a well-balanced population density on each area of the search space, and it uses an archive truncation process that preserves boundary solution. It ensures both a good convergence speed and a fair preservation of solutions diversity.

To deal with constrained problems, we completed this method with specific evolutionary operators (initialization, uniform mutation and uniform crossover) that preserve feasibility of generated solutions.

This provides the six steps following approach: 1. Initialization of individual set that respect the constraints (thanks to filtering), 2. Fitness assignment (balance of Pareto dominance and solution density) 3. Individuals selection and archive update 4. Stopping criterion test 5. Individuals selection for crossover and mutation operators (binary tournaments) 6. Individuals crossover and mutation that respect the constraints (thanks to filtering) 7. Return to step 2.

For initialization, crossover and mutation operators, each time an individual is created or modified, every gene (decision variable of V) is randomly instantiated into its current domain. To avoid the generation of unfeasible individuals, the domain of every remaining gene is updated by constraint filtering. As filtering is not full proof, inconsistent individuals can be generated. In this case a limited backtrack process is launched to solve the problem. This approach doesn't need any additional parameter tuning for constraint handling. In the following, we will briefly remind the principles and operators used in CFB-EA. Many research studies try to integrate constraints in EA. C. Coello Coello proposes a synthetic overview in [Mezura-Montes and Coello Coello 2011]. The current tendencies in the resolution of constrained optimization problem using EAs are penalty functions, stochastic ranking, ε-constrained, multi-objective concepts, feasibility rules and special operators. CFB-EA belongs to this last family. The special operators class gathers methods that try to deal only with feasible individuals like repairing methods, preservation of feasibility methods or operator that move solutions within a specific region of interest within the search space as for example the boundaries of the feasible region. Generally and has we verified on our last experimentations, these methods are known to be performing on non-over-constrained problems (i.e. a feasible solution can be obtained in a reasonable amount of time to be able to generate a population of solutions). CFB-EA aims at preserving the feasibility of the individuals during their construction or modification. Proposed specific evolutionary operators prune search space using constraint filtering. The main difference between our approach and others is that we do not have any infeasible solution in our population or archive. Each time we modify an individual, the constraints filtering system is used in order to verify consistency preservation of individuals. Previous experimentations [START_REF] Pitiot | [END_REF] allowed us to verify that the exact approaches are limited to problems of limited size and that CFB-EA is completely competitive for the level of constraint of the models which interest us. In this article, we propose a new two sub-step optimization approach that takes advantage of the three following characteristics: (i) EA are anytime algorithms, e.g. they can supply a set of solutions (Pareto Front) at any time after initializa-tion, (ii) we have an user who can possibly refine his criteria requirements with regard to the solutions obtained during optimization process ; (iii) CFB-EA is relevant for the range of concurrent configuration and planning problems required (size and constraints level) and more particularly it can propose, in a reasonable amount of time, a good approximation of the Pareto Front that allows the user to decide about his own cost/cycle time compromise.

Two-task optimization approach.

As explained in the introduction, the goal of this article is to evaluate, for large problem, the interest of replacing the single shot Pareto front computation by two successive tasks: (i) a first rough computation that provides a global idea of possible compromises (ii) a second computation on a restricted area selected by the user. This is shown in the illustration of figure 6. The left part of figure 6 shows a single shot Pareto. The right part of figure 6 shows a rough Pareto quickly obtained (first task), followed by a zoom selected by the user (max cost and max time) and a second Pareto computation only on this restricted area (second task). The restricted area is obtained by constraining the two criteria total cost and cycle time (or interesting area) and filtering these reductions on the whole problem. The second optimization task does not restart from scratch. It benefits from the individuals of the archive that belongs to the restrained area founded during first task. We thus replaced the initialization of our CFB-EA (constitution of the first population) by a selection of a set of the best solutions obtained during the first rough optimization. This provides the following process: 1. Interactive configuration and planning using nonnegotiable requirements of the user (as before), 2.1 -1 st global optimization task on negotiable requirements of the user 2.2 -2 nd optimization on interesting area initialized with individuals of the previous step. The goal of the proposed experiments is to compare these two optimization approaches (single-shot and two-task optimization approaches) in terms of result quality and computation time. In terms of quality we want to compare the two fronts and will use the Hypervolume measurement proposed by [Zitzler and Thiele 1998] which is illustrated in figure 7. It measures the hypervolume of the space dominated by a set of solutions. It thus allows evaluating both convergence and diversity proprieties (the fittest and most diversified set of solutions is the one that maximizes hypervolume). In terms of computation time, we want to evaluate, for a given Hypervolume result the time reduction provided by the second approach. In terms of problem size, we consider a model called "full_ aircraft" that gathers 92 variables (symbolic, integer or float variables) linked by 67 constraints (compatibility tables, equations or inequalities). Among these variables, we find 21 decision variables that will be manipulated by the optimization algorithms (chromosome in EAs): -12 variables (each with 6 possible discrete values) that describe product customization possibilities, -9 variables (each with 9 possible discrete values) that describe production process possibilities. In fact, the nine values aggregate 3 resource types and 3 resource quantities for each of the 9 process operations that compose the production process. Without any constraints, this provides a number of possible combinations around 10 18 (≈ 6 12 x 9 9 ). An average constraint level (around 93% of solutions rejected) allows 7.3*10 16 feasible solutions. Results of experimentation's with other model sizes and other constraint levels can be consulted in [START_REF] Pitiot | [END_REF].

Figure 8 shows the Pareto Fronts obtained with CFB-EA after 3 and 24 hours of computation. The rough Pareto front obtained after 3 hours of computation allows the user to decide in which area he is interested in. In the next subsection, we will study a division of this Pareto front in three restricted area:

-Aircraft_zoom_1: area that correspond to solutions with a cycle time less than 410 (solutions with shortest cycle times), -Aircraft_zoom_2: area that correspond to solutions with a cycle time less than 470 and a total cost less than 535 (compromise solutions), -Aircraft_zoom_3: area that correspond to solutions with a total cost less than 475 (solutions with lowest total costs). These three areas correspond with a division of the final Pareto front obtained after 24h of computation in three equal parts. These areas have been selected in order to evaluate performance of the proposed two-task approach, but it also corresponds with some classical preference of a user who could wish: (i) a less expensive plane, (ii) a short cycle time, (iii) a compromise between total cost and cycle time. We will discuss this aspect in section 3.3. The optimization algorithms were implemented in C++ programming language and interacted with the filtering system coded in Perl language. All tests were done using a laptop computer powered by an Intel core i5 CPU (2.27 Ghz, only one CPU core is used) and using 2.8 Go of ram.

Two-task approach evolutionary settings

For a first experimentation of the two-task approach, we use classical evolutionary settings (e.g. the same evolutionary settings used for the single-shot approach: Population size: 80, Archive size: 100, Individual Mutation Probability: 0.3, Gene Mutation Probability: 0.2, Crossover Probability: 0.8).

The main difference with the single-shot approach is with the backtrack limit (e.g. number of allowed backtrack in mutation or crossover operator). This limit has been set to 100 in the one-shot approach and to 30 in the two-step approach. Indeed in the two-step approach, it could be time consuming to obtain a valid solution. For example with the single-shot optimization, only 2.5% of filtered individuals were unfeasible and none of them were abandoned; while with the twotask approach and a lower backtrack limit, around 7% of filtered individuals were unfeasible and 0.3% of them were abandoned. So a lower backtrack limit reduces the time spend to try to repair unfeasible individuals.

The only other difference between single-shot CFB-EA and two-task CFB-EA is the stopping criterion. While in singleshot approach, we use a fix time limit (24hours), the twotask approach uses a bcondition stopping test that stops either if there is no HV improvement after 2 hours or after 12 hours of computation (that must be added to the three initial hours for getting the rough Pareto Front).

Experimental results

The goal of this section is to evaluate the two-task optimization on the three selected areas of figure 8 (zoom 1, zoom 2 and zoom3) with respect to the single-shot optimization. The Pareto Fronts obtained by the two approaches (singleshot and two-task) are very close when the cycle is greater than 355. For lower cycle times, the proposed two-task approach is a little better. However, these curves correspond with a specific run. In order to derive stronger conclusions, 10 executions of the two approaches have been achieved for each of the three zoom areas.

First result illustrations

Detailed comparisons

Detailed experimental results achieved on the three zoom areas are presented in figure 10 and table 1.

On each graph of figure, the vertical axis corresponds to the hyper volume (average of ten runs) reach and horizontal one is the time spent. At time 0, the single-shot optimization is launched (dotted line). After 3 hours (10800 seconds):

-the single-shot keeps going on (dotted line), -the two-task is launched (solid line).

The table provides numeric results for each zoom area. The columns display the single-shot, two-task and % gap of:

-average final hypervolume, -average % standard deviation of hypervolume -average computation time, -average % standard deviation of computation time, -maximum value of hypervolume. In terms of quality, the new proposed approach (two-task optimization) allows to obtain a similar performance with respect to single-shot one: -0.4% worse on zoom1 -1% worse on zoom2 -4% better on zoom3 but in around half of computing time:

-13 h instead of 24h for on zoom1 -13.5h instead of 24h for on zoom2 -10.5h instead of 24h for on zoom 3. Furthermore, this computing time includes the 2 hours of computation without any hypervolume reduction before stopping (stopping criterion of the two-task approach).

It can be seen on the figure10 that when the single-shot CFB-EA has trouble to obtain a good Pareto Front during the first three hours, the more the two-task CFB-EA is performing. On zoom1 area, single-shot CFB-EA reaches relatively quickly a near-final Pareto Front; while on zoom3 area, it reaches it very slowly.

Conclusions

The goal of this paper was to evaluate a new optimization principle that can handle concurrent configuration and planning. First the background of concurrent configuration and planning has been recalled with associated constrained modeling elements. Then an initial optimization approach (single-shot CFB-EA) was described followed by the twotask approach object of this paper. Instead of computing a Pareto Front on the whole solution space, the key idea is: to compute quickly a rough Pareto Front, to ask the user about an interesting area and, to launch Pareto computation only on this area. According to experimental results, in terms of computation time, the new two-task approach allows a significant time saving around half of the previous time needed by the single-shot optimization approach. In terms of quality, Hypervolume computation are very close or even a little better in some case. Furthermore, these results have been obtained on a rather large problem that contains around 10 16 /10 17 solutions. With smaller problems, the proposed approach should perform much better. We are already working on a more extensive test (different model size and different level of constraints) as we did in [START_REF] Pitiot | [END_REF]. Another key aspect that needs to be study is to find a way to define the rough Pareto computation time.

Figure 1 -

 1 Figure 1 -Two-step process

Figure 2 -

 2 Figure 2 -Concurrent configuration and planning CSP model

Figure 3 -

 3 Figure 3 -CSP model to optimize The model of figure 2 is completed in figure 3. For cost, each product variable and each process operation is associated with a cost parameter and a relevant cost constraint: (C-Seats, Cs1), (C-Range, Cs2), (C-Sourc, Cs3) and (C-Assem, cs4) detailed in the tables of figure 3. The total cost and cycle time are obtained with a numerical constraint as follows: Total cost = C-Seats + C-Range + C-Sourc + C-Assem. Cycle time = D-Sourc + D-Assem

Figure 4 -

 4 Figure 4 -Problem solutions and Pareto front

Figure 5 -

 5 Figure 5 -Constrained optimization problem

Figure 6 -

 6 Figure 6 -Single shot and two-task optimization principles

Figure 7 -

 7 Figure 7 -Hyper volume definition

Figure 8 -

 8 Figure 8 -Pareto-fronts obtained on "full aircraft model" after 3 and 24 hours of computation

Figure 9

 9 Figure 9 illustrates an example of the Pareto fronts that can be obtained on the zoom 1 area : -rough Pareto obtained after 3 hours (fig 9 squares), -two-task, after 3+12 hours (fig 9 triangles), -single-shot, stopped after 24 hours (fig 9 diamonds).

Figure 9 -

 9 Figure 9 -Example of Pareto fronts obtained on zoom1

Figure 10 -

 10 Figure 10 -Evolution of hypervolume

Table 1 .

 1 Comparison of the two approaches

			Singleshot CFBEA	Twotask CFBEA	gap in %
		Average Final HV	5849	5823	0.4
	Zoom1	Average HV RSD Total time	3.8% 86400(24h)	5.1% 47996 (≈13h)	44.6
		Total
		time	0	15%
		RSD
		Max HV	6043	6057	0.2
			Singleshot CFBEA	Twotask CFBEA	gap in %
		Average Final HV	1758	1740	1.
	Zoom2	Average HV RSD Total time	2.1% 86400(24h)	2.3% 48501 (≈13.5h)	44
		Total
		time	0	16%
		RSD
		Max HV	1795	1776	1
			Singleshot CFBEA	Twotask CFBEA	gap in %
		Average Final HV	1765	1844	4.4
	Zoom3	Average HV RSD Total time	3.16% 86400(24h)	0.07% 38185 (≈10.5h)	55.9
		Total
		time	0	26%
		RSD
		Max HV	1831	1845	0,7


É Vareilles
email: elise.vareilles@mines-albi.fr

C Thuesen

M Falcon

M Aldanondo

Interactive Configuration of High Performance Renovation of Apartment Buildings by the use of CSP

This paper is a prospective study which looks at the possibility of configuring high performance renovation of apartment buildings by the use of constraint satisfaction problem (CSP). This study is one part of a project called CRIBA which aims to industrialize high performance thermal renovation of mid-rise (up to seven stories) apartment buildings. The renovation is based on external rectangular panels, always comprising insulation and cladding, and sometimes including, in addition, doors, windows or solar modules. The panels can be fixed directly onto the walls or onto a metal structure around the whole building. With the new thermal envelope and equipment, the building must achieve a really low energy performance of 25 kW h/m 2 /year. A configuration system, based on CSP approaches, will simultaneously enable the interactive definition of the renovation, the associated bill of material (BOM) and the building site assembly process. In Section two, we set out the industrial problem of residential buildings renovation and explain how a configurator can support it. Then, in the third section, the renovation configuration process is described. In the fourth and final section, we present how the renovation configuration can be addressed with constraints, and we introduce relevant CSP approaches. Through out the article, industrial examples illustrate our proposal.

Introduction

The global contribution from buildings (residential and commercial) towards energy consumption has steadily increased. Buildings account for around 20% and 40% of the total final energy consumption in developed countries: 37% in the EU [Perez-Lombard et al., 2008], 36% in the USA [Council, 2013] and 31% in Japan [Center, 2012]. It has now exceeded the other major sectors: industry and transportation. Growth in population, enhancement of building services and comfort levels, together with the rise in time spent inside buildings assure the upward trend in energy demand will continue in the future. Therefore, reducing energy consumption of the building sector is one of our century's challenges. For this reason, it is a prime objective for energy policy at regional, national and international levels.

In several countries, research works are carried out on the efficient measures to take to reduce energy consumption of the building stock. Most states set regulations to improve the energy performance of new buildings. However, the annual rate of construction of new dwellings is only 1.1% in Europe [Poel et al., 2007]. It is therefore very important to renovate the existing buildings to really reduce their energy consumption and to assist the retrofit process by the development of decision support systems [START_REF][END_REF].

This study is one part of a research project called CRIBA, which aims to industrialize high performance thermal renovation of apartment buildings. In this project, a very innovative renovation system based on large timber frame panels will be designed. Moreover, all the tools needed to industrialize the renovation process will be developed:

• a new method for three-dimensional building survey and modelling, • a configuration system for the design of the buildings new thermal envelope (bill of material and assembly process), • a working site planning model with resource constraints. The aim of this paper is to present a prospective study on the development of the interactive configuration system for the renovation of apartment buildings.

Therefore, the remainder of the paper is organized as follows. In Section 2, we present the building renovation problem and how the configurator can support apartment buildings renovation. In Section 3, we put forward some ideas on the generic renovation bill of material. In Section 4, we outline the building renovation configuration process. In Section 5, we identify the different kinds of constraints that are needed in order to make the apartment building renovation model.

Building Renovation Configuration Needs

In this section, we introduce the building renovation problem which is at the origin of our work. Then, we express what the configurator is expected to generate as results.

Building Renovation Problem

The industrialized high performance thermal renovation is based on external rectangular panels, always comprising in-sulation and cladding, and sometimes including, in addition, doors, windows or solar modules. Although the shape of the panels is a major limitation for the architectural creativity, this assumption is the key of renovation industrialization and matches most of apartment buildings.

The building sector is very dependent on hand-made methods which are not always synonymous with quality guarantee [Falcon and Fontanili, 2010]. Therefore, the aim of the CRIBA project is to prefabricate all the panels needed for a renovation, in a correct order, then to deliver them directly to the working site and finally to hang them on the faades. Therefore, the renovation process enables thermal renovations:

• at low cost, considering all the positive elements, fixed cost, logistic, etc, • in a short time,

• of high quality,

• in a good environmental balance,

• without rehousing the inhabitants during the renovation works. Depending on the building strength of materials, the panels can be fixed directly onto the faades or onto a metal skeleton around the whole building. With the new thermal envelope and equipment, the building must achieve a really low energy performance of 25kW h/m 2 /year. In order to reach such a low energy performance, the new thermal envelope has to wrap the whole building. All the faades are covered by nonoverlapping panels and are space-partitioned.

Building Renovation Configuration

The interactive configuration system for the renovation of apartment buildings will simultaneously enable the interactive definition of the renovation thanks to the associated bill of material [Felfernig, 2007] and the building site assembly process.

The bill of material is a list of the components and sub-components, sub-assemblies, and the quantities of each needed to manufacture an end product. It can have multiple options and variants. In our case, we consider:

• the new thermal envelope as the end product;

• the facade new envelopes as the sub-assemblies;

• the complete panels as sub-components;

• the configurable components as leaves of the bill of material (BOM):

the panels, which are placed on the faades, include wood structure, insulation and cladding (three or four types at the moment), as shown in Fig. 1, the angles, which make the junction between two

faades. An angle is a specific type of panel which cannot include other components, the windows, doors, solar modules and balconies, the metal fasteners, which are used to fix either metal profiles or directly the panels onto the faades.

There are several types of metal fastener depending on their type (fasteners to fix metal profiles, to hang There is only one type of metal profile but its length has to fit the facade height.

The assembly process consists in a set of tasks to be carried out in order to assemble the new frame and envelope all around the building. It comprises some tasks that have always to be carried out, such as positioning and fixing metal fasteners, and some that are optional, such as fixing the metal profiles onto the metal fasteners.

At least, the configurator will give an idea of the renovation global cost which includes the costs of raw materials, transportation, labour and lifting devices.

On the first hand, in the configuration community, many authors (among them [START_REF][END_REF]], [Soininen et al., 1998]) have shown that product configuration could be efficiently modelled and aided when considered as a Constraints Satisfaction Problem (CSP) [Montanari, 1974]. On the other hand, in the civil engineering community and in the constraints community, many authors ( [START_REF] Honda | [END_REF], [Junker, 2006], [Medjdoub and Yannou, 2001], [START_REF] Zawidzki | [END_REF] or [Regateiro et al., 2012]) have shown that spatial layout can be solved with CSP. Consequently, we address the building renovation configuration with constraints and filtering algorithms.

Generic BOM Model

In this paper, we focus on the interactive definition of the renovation bill of material. In this section, we highlight the main variables of the configurable components of the renovation BOM. We focus in this paper on the panels and the angles. At the end of the configuration, all the configurable components variables have a single value, given either by the user or deduced by the configurator.

Panels

The panels are rigid 2D rectilinear rectangles. That means that their sides are parallel to the facade reference axis. Let us consider one facade. All the panels covering it belong to a unique vertical plane. They are adjacent (they are at least one side in common) and are not overlapping themselves. By the way, they have all the same orientation. They cover completely the facade and make a partition of it.

The main variables of a panel refer to:

• its width [min w , max w ],

• its length [min l , max l ],

• its coordinates (abscissa and ordinate),

• its insulation thickness [min i , max i ],

• the insulation type (mineral wool or cellulose),

• its weight, which depends on its dimensions, the insulation type, and the components that are included in itself. If the panel includes other components (windows, doors or solar modules), we need to know exactly for each of them:

• its width [min w , max w ],

• its length [min l , max l ],

• its relative position on the panel (x and y),

• its type and reference code.

A minimal distance is required between the sides of the panel and the position of other components: the distance cannot be lower than 90 mm in order to preserve the panel stiffness.

Angles

The prefabricated angles are rigid 3D L-polyomino tetracubes which are placed at the building corners. The corners are at the intersection of two consecutive and perpendicular facade planes. We assume then that the angles are right. Otherwise, a specific design task must be carried out in order to design the relevant angles.

Let us considering a corner. All the angles covering it belong to a unique vertical row. They are adjacent (they are at least one side in common) and are not overlapping themselves. By the way, they have all the same orientation. They covered completely the corner and make a partition of it.

The main variables of an angle refer to:

• its width [min w , max w ],

• its right length [min rl , max rl ],

• its left length [min ll , max ll ],

• its coordinates (abscissa and ordinate),

• its insulation thickness [min i , max i ],

• the insulation type (mineral wool or cellulose),

• its weight, which depends on its dimensions and the insulation type. For the first version of the BOM, the prefabricated angle cannot include other components. The angles dimensions directly depend on the sizes of their adjacent panels, with a minimal length (right and left) equal to 90 mm in order to preserve the angle stiffness.

Building Renovation Configuration Process

The building renovation configuration is a top-down and multi-step process, which progressively converges from the working site to the configurable components. The user has to input some information and data in order to configure the renovation. After each user input, the configurator removes inconsistent values and guides progressively the user to a consistent solution. The user has to follow this process and gives information on:

• the whole working site. The working site description has an impact on the panels dimensions. Let us focus on the working site accessibility and its local atmosphere. Concerning its accessibility, if you can access the working site with special convoys, the panels can be as wide and long as needed. Otherwise, the dimensions of the panels are constrained by the size of the trucks which can access to the working site. Concerning the local atmospheric, if the working site area is very windy, wind speed peaks ≥ 80 km.h -1 , the panels have to be smaller in order to be fixed onto the faades, and the renovation lasts longer because of nonworking periods. • the block of apartment buildings. The block description has directly an impact on the hoisting equipment and indirectly on the panels dimensions. If the block cannot be accessible with a tower crane, the panels have to be smaller in order to be conveying to the faades with an other suitable hoisting equipment, such as a telescopic boom lift.

• the apartment building. The apartment building description has an impact on the panels dimensions. Let us consider only the apartment building height. If the apartment building height is lower than twelve meters (four stories), the height of the panels can be the same as the building one so that the panels are fixed vertically on the faades. • the faades. Let us focus on a facade.

1. First of all, the user has to describe precisely the structure and the geometry of the facade. Considering the structure of the facade, (s)he needs to input where the metal fasteners can be fixed on the facade. A structural study has to be done in order to characterize the load bearing capacity of every area of the facade. Considering the geometry, the positions of windows, doors and balconies have to be known precisely. Only a topographic survey can provide these information. 2. Regarding these areas and their characteristics, the decision of fixing the panels directly on the facade or on the metal profiles can be made. This decision has an impact on the BOM (metal fastener type and optional metal profiles) and on the assembly process (tasks devoted to metal profiles, such as delivery, assembly and adjustment). 3. Having information about the working site, the block, the apartment building and the facade and the impact on the panels dimensions, the drawing of the facade layout can start. The user has now to indicate what the aesthetic effect she/he wants for the facade. For instance, she/he can want continuous vertical joints, which means that the panels are fixed vertically or she/he can want a checkerboard effect with a lot of similar panels. 4. Knowing the facade layout, each panel has to be configured. If the panel is solid, one can decide to add solar modules or to add an exit door. If the panel has to include windows, doors and/or balconies, the suitable reference code has to be selected for each of them. • the angles. The renovation configuration finishes by the configuration of the angles. At this step, only the height of angles has to be determined. At any time in every step of the configuration process, the user can change her/his inputs and see their impact on the configuration solutions.

Building Renovation Configuration and Constraints

Interactive renovation configuration is provided by constraint propagation that prunes bad solutions and progressively guides the way to good ones. In apartment buildings renovation, the range of knowledge to exploit and to model leads us to integrate into a single configurator different constraints types as well as their filtering methods. In this section, we outline the kind of variables and constraints that are necessary to formalize apartment building renovation model.

Classical CSP Approaches

In building renovation configuration, we have to formalize different kinds of knowledge relevant to:

• civil engineering regulations that must be followed absolutely to the letter. For instance, fire barriers have to be installed between two consecutive stories in order to stop the spread of fire, • civil engineering know-how that is the core knowledge of the companies involved in the CRIBA project, • working site assembly process that allows us to define the suitable way of assembling the new frame and envelope all around the building. For instance, we have seen in Section 4, that the working site local atmosphere has an impact on the panels dimensions: if the working site area is very windy, wind speed peaks ≥ 80 km.h -1 several times a year, the panels have to be smaller in order to be fixed onto the faades without stopping the renovation with nonworking periods.

As the range of knowledge to model is wide, we need to use different CSP approaches and their filtering algorithms, such as discrete CSP ( [Montanari, 1974], [Mackworth, 1977], [START_REF] Bessire | [END_REF], [Faltings, 1994]), continuous CSP ( [Lhomme, 1993] or [START_REF] Benhamou | [END_REF]) and mixed CSP ( [Gelle, 1998]) depending on the type of the variables (discrete, continuous, symbolic or numeric) and the type of constraints (compatibility constraints or mathematical formulae).

Groups and Multi-instances of Constraints

In the renovation configuration, we have to cope with several instances of the same configurable components. For instance, in order to cover a facade with its new envelope, we need to configure x times a panel (such as described in Subsection 3.1). We do not know in advance how many panels will be necessary, as it depends on a lot of data (working site description, block description, etc.). Therefore, we need to group variables and constraints into sets or classes, which can be instantiated as much as needed.

Dynamic Constraints

We have seen in the building renovation configuration process, Section 4, that we can decide to fix the panels on a metal envelope, or to create new openings on a facade. These decisions imply firstly the consideration of new components in the BOM and secondly, the insert of their assembly tasks in the assembly process. Therefore, we need to take into account the activation of configurable components as defined by [START_REF] Mittal | [END_REF], [Sabin and Freuder, 1996] and [START_REF] Faltings | [END_REF].

Geometric Constraints

In order to prefabricate the panels, we need to determine precisely the dimensions and the position of each component on the panels. The accuracy of the topographic measures and the precision of the components dimensions and position are the crucial factors for the industrialization of the building renovation and the goals of the CRIBA project. Therefore, in order to do so, we need to integrate to the configurator geometric constraints (for a complete survey, see, [Dohmen, 1995] or [START_REF] Fudos | A graph-constructive approach to solving systems of geometric constraints[END_REF], and for more recent work see [START_REF] Jermann | [END_REF], [START_REF] Zawidzki | [END_REF] or [Regateiro et al., 2012]).

Global Constraints

As we cannot know in advance how many panels are needed to cover a facade, we have to cope with constraints that depend on the number of instances of the same class. For instance, if the height of the facade is covered with more than one panel, the sum of all the panels heights has to be equal to the facade one. Therefore, we need to integrate and filter different kinds of global constraints [START_REF] Van Hoeve | Handbook of Constraint Programming[END_REF].

Conclusion

The aim of this paper has been to present a prospective study on the development of the interactive configuration system for the renovation of apartment buildings.

Firstly, we have presented the apartment buildings renovation problem and what the main objectives of the CRIBA configurator are: the interactive definition of the renovation thanks to the associated bill of material and the building site assembly process as well as a first cost estimation. Then we have focused on two configurable components that are the panels and the angles and highlighted their main characteristics. In the fourth section, we have outlined the top-down and multi-step building renovation configuration process. In the final section we have put forward some ideas on the different kinds of CSP approaches we have to integrate in the configurator in order to support and guide the configuration of buildings renovation.

The apartment buildings renovation configuration is a challenge however you look at it. First of all, we want to industrialize a process that is nowadays traditionally made by craftsmen. This point is quite a revolution for the civil engineering field where only few industrial engineering methods are applied, and in particular in SMEs. Secondly, in order to be able to use a configurator, we need to extract, validate and formalize relevant knowledge. In our application field, the nature and the origin of knowledge are quite various. We have therefore to use different types of variables and constraints. The filtering engine has therefore to integrate different kinds of propagation methods. Thirdly, we need to cope with different variables priorities. For instance, all the variables which describe the whole working site have a strong impact on the dimensions of the panels and cannot be changed: we cannot decide to use a special convoy if the working site is not accessible with such a convoy. If an inconsistent solution is found, we will propose to the user to change her/his choices firstly on the panels and then to progressively zoom out to the whole working site.

As we are still in the very earliest stage of the CRIBA project and as apartment building renovation configuration is quite a complex process, we need to model in details the BOM components and their constraints. When this is done, we have to select, analyse, adapt and integrate constraints approaches and filtering algorithms in our propagation engine CoFiADe. CoFiADe has already been used for supporting heat treatments configuration [Aldanondo et al., 2006], simultaneously product and planning configurations [START_REF] Vareilles | [END_REF] and helicopters maintenance configuration [START_REF] Vareilles | [END_REF]. The development of the graphical user interface in order to allow the user to see the result of her/his configuration is also a challenge. It is not the core of the configuration problem but it is clearly a need for the companies involved in the project.

Figure 1 :

 1 Figure 1: CRIBA Panels

Acknowledgements

The authors wish to acknowledge the TBC Générateur d'Innovation company, the Millet and SyBois companies and all partners in the CRIBA project, for their involvement in the construction of the CSP model.