We present the coupling of two constraint-based environments into an on-line support system for fac¸ade-layout configuration in the context of building renovation. The configuration consist on the definition and allocation of a set of rectangular parameterizable panels over a fac¸ade surface. The coupling allows to solve two configuration tasks while gaining efficiency and modularity. First, it allows to configure a set of questions relating the renovation model needed to determine limits for panels' size and panels' weight. Second, it allows to configure a constraint satisfaction model for each of the fac¸ades to renovate. Two constraint-based systems handle the filtering of incompatible values and the generation of layout plans in a web-service setup. The first service performs initial filtering to set panels' limits, based on the questionnaire, using a constraint filtering engine called CoFiADe. The second service uses several fac¸adelayout configuration algorithms, using as underlying engine the constraint solver Choco, to generate compliant layout-plan solutions. We show that by dividing filtering and search, and by coupling the two constraint-based systems, we gain modularity and efficiently as each service focuses on their own strengths. Services executing tasks may be hosted in different network-nodes and thus may be seen as independent communicating agents.
Constraint-base fac¸ade-layout configuration. Product
configuration refers to the task of building a target product using predefined
components, respecting requirements from customers and following
some rules that shape a correct configuration [
A particular scenario on product configuration arises from the
context of building thermal renovation as an effort to reduce current
energetic consumption levels [
Constraint satisfaction problems (CSPs) are conceived to allow the
end-user to state the logic of the computation rather than its flow. For
example, in the context of scheduling, instead stating a set of steps
to avoid tasks overlapping, the user declares “for any pair of tasks
they must not overlap”. The user may do so by stating a) variables
representing elements of the problem, b) a set of potential values
associated to each variable and c) relations over the stated variables
also known as constraints [
It turns out that constraint technology fits neatly in the constrained nature of product configuration and layout synthesis. On one hand, the knowledge (constraints) that restrict possible configuration of elements (variables) is easily modeled under the declarative framework of constraint satisfaction problems. On the other hand, constraintbased configurators are able to presents different solutions to users, often optimal, even when they do not provide all configuration parameters leaving their preferences unknown.
Now, for constraint-based implementations we differentiate
between two related concepts: Solving a problem and filtering (narrow)
possibilities. Whereas solving a problem involves a robust inference
engine and search strategies, filtering algorithms work, in essence, on
how to efficiently remove variable values that are restricted by the
established relations, i.e., the constraints [
Related work. Layout configuration techniques have been used
within different contexts and scenarios. For instance, finding
solutions for room configurations [
Regardless the considerable number of applications on layout configuration, our problem include three characteristics never considered simultaneously: Its deals with the allocation of an unfixed number of rectangular panels that must not overlap, frames (existing windows and doors) must be overlapped by one and only one panel, and fac¸ades have specific areas providing certain load-bearing capabilities that allow to attach panels. Thus, as far as we know, no support system nor design system is well-suited for addressing such particularities. Also, most systems are desktop-oriented and not weboriented, making difficult to adapt new requirements and functionalities as they need new versions to be released.
Contribution and structure. Traditional general purpose
constraint solvers, such as Gecode [
Our goal is two-fold. First, we propose an architecture that divides initial filtering and consequent search for constraint-based product configuration. The architecture allow us to solve two configuration tasks; configure a set of questions relating the renovation model needed in the renovation process and needed to determine limits for panels’ size and panels’ weight and; configure a constraint satisfaction problem for each of the fac¸ades to renovate. In a second time, we present an on-line support system, and formalize its behavior, for the problem of fac¸ade-layout configuration. The architecture, implemented in the on-line system, couples two different constraint-based technological tools to gain efficiency and modularity. We use fac¸adelayout configuration to illustrate our method as it is the goal of the project we are into, but our results can be adapted to deal with different kind of products.
The paper is divided as follows. A brief description of the industrial scenario and elements is presented in Section 2. In section 3, we introduce details of the two configuration tasks performed by the support system. The service oriented architecture, along with details of the constraint-services’ behavior, is presented in Section 4. In Section 5, we discuss the benefits of the tasks division and coupling of the constraint systems. Some conclusions are drawn in Section 6. A bibliography is provided at the end of the document. 2
The problem at hand deals with the configuration of rectangular panels and their arrangement over a fac¸ade surface. In order to start the configuration process, specific information have to be extracted from a set of spatial entities. The renovation is carried out on fac¸ades that are part of a given building, buildings that are part of a given block, and blocks that are part of a given working site. Each of these spatial entities have geometrical and structural properties and may have different environmental conditions that must be taken into account for the layout-plan definition.
Information about spatial entities is acquired by the support system by means of an (JSON) input file describing all geometrical and structural properties, and by means of a web-based questionnaire for each spatial entity in the input file. Thus, if the input file contains information for one working site with two blocks, each block with one building and three fac¸ades in each building, the user answers to eleven questionnaires (one for the working site, two for the blocks, two for the buildings and six for the fac¸ades). After questionnaire completion, the lower bound and upper bound for panels’ size and panel’s weight have been deduced. Also, given that several instances for fac¸ades are need to be solve, at the end of the questioning stage the systems creates a constraint satisfaction model for each fac¸ade using the inputed information and the deduced limits for panels’ size and weight. Here, each constraint satisfaction model instance is parameterized according with the fac¸ade information (e.g. environmental conditions) and the particular deduced panels’ limits.
Lets consider the information flow from the user perspective. Figure 2 presents the representative actions made by the user and the responses by the on-line support system. It also illustrates the fact that to the end-user should be transparent all the configuration process. The complete sequence of the configuration goes as follows. Step 1:- The user uploads a file containing the geometry and structural specification of spatial entities. The support system stores information in a data base.
Step 2:- The filtering service presents a questionnaire for each of the spatial entities in the input file.
Step 3:- The user answers the questions (leaving in blank the questions he does not know the answer).
Step 4:- Using the information about spatial entities (database) and their environmental/user conditions (user answers) the system deduce lower and upper bounds for panels’ size and panels’ weight by using the filtering service.
Step 5:- If a manual configuration is desired, the user draws each panel on the clients GUI. Each panel is assured to be consistent with the problem requirements by sending its information to validate into the solving service (the validator module).
Step 6:- If a semi-automatic configuration is desired, the user draws some panels and then asks the solving service to finish the configuration.
Step 7:- If an automatic configuration is desired, the user asks the solving service to provide compliant layout solutions.
It is worth mentioning the consistency among the different steps: Information at each level is propagated downwards and is never propagated upwards (we will further study this along the document). Also, of major importance is the fact that each fac¸ade may have its own panels’ lower and upper bounds and thus solving a given fac¸ade is done with a particular set of arguments. 3
In this section we present the two configuration tasks within the support system: The configuration of a questionnaire to be filled by the end-user and, the configuration of a constraint satisfaction model for each fac¸ade to renovate used as input for layout-plans generation. 3.1
The renovation includes four spatial entities, namely, working site, block, building and fac¸ade, and some configurable components, namely, panels and fasteners (fasteners are devices to attach panels onto the fac¸ades). A hierarchical view is presented in Figure 3. Once the input file has been read by the support system, it can proceed by configuring a set of questions for each spatial entity in the file. Then, after the user answer the questionnaires, the system configures, i.e., deduces, the limits for panels’ size and panels’ weight for each fac¸ade. The questionnaires ask the following information. Working site. This is the bigger spatial division in the renovation.
It is commonly referred by a name and is well-know by the community. Values provided by the user are:
Target for performance? W:m 2:K 1
Accessibility to the working site? feasy, medium, hardg Panel’s width (wws) and height (hws) lower bound? [0; 1] Panel’s width (wws) and height (hws) upper bound? [0; 1]
Block. Is a set of buildings which are usually attached by a common wall. Values provided by the user are:
wbl 2 [wws; wws] and hbl 2 [hws; hws]
wbl 2 [wws; wws] and hbl 2 [hws; hws]
wbg 2 [wbl; wbl] and hbg 2 [hbl; hbl]
wbg 2 [wbl; wbl] and hbg 2 [hbl; hbl]
Building. Is the actual place where apartment are arranged and is the host of several fac¸ades. Values provided by the user are: layout plan are limited as well as their weight. Thus, the aforementioned inputs have direct impact over configurable components and are defined by their compatibility relations. 3.2
One Fac¸Ade One CSP One critical aspect of the support system is the ability to configure a constraint satisfaction model for each fac¸ade to renovate. This is important because, first, each fac¸ade has (potentially) different size, number of windows, supporting areas etc. Possible positions for panels, for instance, must lie between zero and the fac¸ade width and height. Simply put, each fac¸ade has its own configuration parameters used in the constrain satisfaction model and in the layout generation process. And second, each fac¸ade may have different accessibility conditions, obstacles or even user preferences. Thus, panels’ size limits, as well as their weight, are constrained by the specific conditions of the fac¸ade and not only by the conditions of the working site, block or building.
When configuring these CSP instances it is important to conserve downwards consistency. Downwards consistency refers to the fact that information on higher level of the renovation are is propagated to the inferior levels, i.e., working site ! blocks ! buildings ! fac¸ades, but it can not propagate upwards. As an example consider only accessibility conditions, obstacles presence and panels’ size limits, for the specification in Figure 4.
Fac¸ade. Maybe seen as a big wall, but is in fact a composition of apartment along with its doors, windows and so on. Values provided by the user are:
wfc 2 [wbg; wbg] and hfc 2 [hbg; hbg]
wfc 2 [wbg; wbg] and hfc 2 [hbg; hbg]
Note that inferior entities on the hierarchy inherit values from superior levels. But, it is not the case that information on superior levels should be consistent with information on inferior levels. In Figure 4, for instance, fac¸ade 1 has a hard accessibility condition and thus the upper bound for panels’ size is reduced to a given Z. This upper bound is not propagated upwards to the building 1; it conserves its inherited value X. Consequently, fac¸ade 2 will inherit the value of X as no further reduction is needed for their panels configuration. Naturally, it is the case that Z X U . Using this information a CSP is configured for each fac¸ade to renovate.
This information collection has two specific goals. On the one hand, it will provide details about renovation aspects, such as the targeted performance, that are needed in the configuration process. On the second hand, it provides upper bound for panel’s size and panel’s weight. Indeed, given the manufacturing, environmental, accessibility and even weather conditions, the size of panels composing the 4
In order to divide configuration tasks we divide the support system in two services that may be implemented in different servers. In essence, information about the renovation, entered by means of the input file and the questionnaire, is filtered by means of the first service called Filtering Service. Then, the second service called Solving Service, upon user request, uses its configuration algorithms to provide complaint layout-plans solutions. Figure 5 presents the architecture of the on-line support system.
In order to give a clear understanding on how the services works, let us describe the input and output in a formal way. For each of the services the input is a tuple of the form hSPE C; V; D(V); C(V )i with jVj= jD(V)j and
SPE C = hWS; BK; BG; F ACi; WS variables describing the working site, BK variables describing blocks, BG variables describing buildings and F AC variables describing fac¸ades. V = hP ; F Ai; P variables describing a single panel and F A variables describing a single fastener.
D(V) = hD(P); D(F A); i; domain for each one of the variables in V.
C(V) a set of constraints over variables in V.
Information in SPE C describes only properties of the spatial entities such as the number, sizes, positions, etc. Variables in V and D(V), on the other hand, are manufacturer depended and includes size and position of panels and fasteners, and the initial domains which depends on the manufacturing process. Constraint in C(V) are extracted from the problem domain by an expert and are different in each service. 4.1 4.1.1
Mapping The filtering service is in charge of removing domain values from elements in D(V) that are not allowed by the established constraints. Here, constraints C(V) describe valid combination among different parameters in SPE C and variables in D(V). We denote this set of constraints Cf (V) to distinguish them from the ones used on the solving service. These constraints are formalized as compatibility tables (presented in next section). Formally, the filtering is a mapping M from variables and domains to domains
M(SPE C; V; D(V); Cf (V)) ! D0(V) (1)
The result D0(V) contains the new domain for panels and fasteners, where D0(V) D(V).
As stated previously, the initial filtering has as goal setting
domains for configurable components and takes spatial entities
information and constraints to do so. In our on-line support system we
use the CoFiADe [
Compatibility Knowledge Configurable components of the renovation are panels and fasteners to attach panels.
Panels. Configurable by fixing their width, height, weight and position over the fac¸ade.
Fasteners. Configurable by fixing its length and setting its type fbottom, top, lateralg.
The following compatibility tables, presented from Table 1 to Table 8, show the allowed combination between user’s input values and configurable components values. The second service in the support system is in charge of layout-plans generation. The system uses several algorithms to generate layout plans but, although their behavior are quite different, their semantic remains the same.
Now, while information of SPE C and V are the same as the filtering services, it is not the case for domains and constraints. To differentiate them lest call the input domains Ds(V) and the constraints Cs(V). Intuitively, variable domains Ds(V) are provided by the mapping of the filtering service, i.e.,
M(SPE C; V; D(V); Cf (V)) = D0(V) = Ds(V)
(2)
where D(V) is the initial variable domain of the problem.
Constraints in Cs(V) are expressed as first order formulas and express,
not compatibility among elements but, requirements for valid layout
plans (see next section for a description of these constraints). Both
resolution approaches implemented at the solving service respect all
constraints; the first approach resolving conflicts at positioning each
panel (greedy fashion) whereas the second approach uses the open
constraint programming environment Choco [
The output of the server’s process is a set of layout-plan solutions. Formally, the server’s process is a function of the form
F (SPE C; V; Ds(V); Cs(V); H) = hX ; Y; DX ; DYi (3) where X and Y represent the origin of coordinates for each panel in the solution, and DX and DY the width and height, respectively, for each panel in the solution. Additionally, the function is parameterized by an heuristic H stating the way the solution space is explored.
Available strategies are greedy and depth-first search. Position Fasteners
? ftop,bottomg
bottom
# fasteners
[
Each panel is described by its origin point w.r.t. the fac¸ade origin and its size. For convenience, lets assume that P is the set of panels composing the layout-plan solution. Then, each p 2 P is defined by ho; li where op:d 2 [0; ofac:d] is the origin of panel p in dimension d. lp:d 2 [lbp:d; ubp:d] is the length of panel p in dimension d.
The following six constraints express the relations among panels, and panels and fac¸ade that must respect a layout solution. (a) Manufacturing and transportation limitations constrain panel’s size with a give upper bound ub in one or both dimensions. 8p 2 P lp:d ubd (b) (diffN) For two given panels p and q there is at least one dimension where their projections do not overlap.
8p 2 P; 8q 2 P; p 6= q; 9d 2 [1; 2] j op:d oq:d + lq:d _ oq:d op:d + lp:d (c) A given panel p must either be at the fac¸ade edge or ensure that enough space is left to fix another panel.
8p 2 P op:d + lp:d lfac:d lbk _ op:d + lp:d = lfac:d (d) Each frame over the fac¸ade must be completely overlapped by one and only one panel. Additionally, frames’ borders and panels’ borders must be separated by a minimum distance denoted by .
op:d + of:d ^ of:d + lf:d 8f 2 F; 9p 2 P j op:d + lp:d + (e) The entire fac¸ade surface must be covered with panels.
P i2P
Qd2[1;2](oi:2 + li:2) = Qd2[1;2] lfac:d (f) Panels’ corners must be matched with supporting areas in order to be properly attached onto the fac¸ade. os:d + ls:d In order to efficiently couple two constraint-based systems it is necessary to assign disjoint tasks for them. In our approach, we divide initial filtering and solving in two different services. Benefits for this tasks division are rather simple.
On the one hand we apply the well-known principle Divide and conquer. In our on-line system this principle allow us to add or remove variables, domains and questions in the filtering service, i.e., by means of adding or removing compatibility tables. In addition, as we use CoFiADe, we may mix different variable representation as integer domains, continuous domains and symbolic domains whereas in most constraint systems mixing variable domains is not allowed or is not efficient enough. For instance, given the reduced number of constraints for continuous domains in Choco, the representation have to be changed to integer domains which in consequence involve additional and time consuming efforts.
On the other hand, as a benefit of tasks division, we improve performance by avoiding the use of binary equalities and binary inequalities constraints whose computational time is O(n m), where n and m are the number of values in the domain of the two variables involved in the constraint. Thus, at the moment of finding solutions, the underlying constraint solver, in our case Choco, propagates and applies search using only those constraints defining a layout plan.
Regarding the performance the two configuration tasks must be studied separately. As commented before, applying a given compatibility table in the filtering service is made in constant time. Thus, the time involved in the filtering service depends on the questionnaire that depends on the number of buildings, facades and so on. On the solving service, by contrast, the performance depends on the underlying filtering and search provided by Choco. Execution over fac¸ades with size 40 10 meters, 50 12 meters and 60 15 meters takes between one and two seconds. The use of a dedicated heuristic that exploits the problem structure allows to reach such good performance.
The decoupling of tasks, and coupling of two constraint-based systems, is supported by the underlying declarative model. Indeed, the monotonic properties of constraint-based systems make it possible to add information (constraints) on one system without loosing any solution on the other system. Thus, the declarative view of constraint satisfaction make it possible to handle services as independent communication agents. 6
The aim of this paper has been to introduce an architecture of constraint-based product configuration that couples two constraintbased systems. We have presented an architecture that divided initial variable domain filtering and search space exploration. The method divide and conquer allow us to make straightforward adaptations to each service separately. Our approach have been applied to fac¸adelayout configuration and implemented in an on-line support system. For this particular scenario we have 1. Formalize each service behavior and the relation among them. 2. Presented the constraints, expressed in compatibility tables and carried out by the CoFiADe system, for initial filtering. 3. Presented the constraints, expressed as first order formulae and carried out by Choco constraint programming environment, that are used to generate compliant layout solutions. 4. Show how to solve the configuration tasks by coupling the two constraint-based systems. 5. Show that consistency and integrity of solutions are straightforward modeled and implemented thanks to the monotonic properties of constraint satisfaction problems. 6. Show that the underlying coupling and communication methods are transparent for the user (it only interacts with a friendly webbased interface).
This work is part of a project on buildings thermal renovation
assisted by intelligent systems. A configuration problem arise in this
context: Configuring a specific set of rectangular panels with respect
to create a building envelope. As the industrial scenario evolves the
support system must be able to adapt to new requirements. Thus,
strategic directions for our work are three-fold. On the one hand,
improve each service by adding new constraints. On the second hand,
definition of an API that allow us to replace the underlying processes
in each service without loosing solutions. For instance, the solving
service may be replaced by the same implementation of the model
but using a different constraint solver (e.g., Gecode [
The authors wish to acknowledge the TBC Ge´ne´rateur d’Innovation company, the Millet and SyBois companies and all partners in the CRIBA project, for their contributions on recollecting buildings renovation information. Special thanks to the referees for their comments and to Philippe Chantry from E´ cole des Mines d’Albi for his contribution to the on-line system graphical interface and additional abstractions. 54