Decomposing and Distributing Configuration Problems
`
`Diego Magro and Pietro Torasso
`
`Dipartimento di Informatica, Universit`a di Torino
`Corso Svizzera 185; 10149 Torino; Italy
`{magro, torasso}@di.unito.it
`
`Abstract. In the present work the issue of decomposing and distributing a con-
`figuration problem is approached in a framework where the domain knowledge is
`represented in a structured way by using a KL-One like language, where whole-
`part relations play a major role in defining the structure of the configurable objects.
`The representation formalism provides also a constraint language for expressing
`complex relations among components and subcomponents.
`The paper presents a notion of boundness among constraints which specifies when
`two components can be independently configured. Boundness is the basis for
`partitioning constraints and such a partitioning induces a decomposition of the
`configuration problem into independent subproblems that are distributed to a pool
`of configurators to be solved in parallel.
`Preliminary experimental results in the domain of PC configuration showing the
`effectiveness of the decomposition technique in a sequential approach to config-
`uration are also presented.
`
`1
`
`Introduction
`
`In recent years configuration has attracted a significant amount of attention not only from
`the application point of view but also from the methodological one [12]. In particular,
`logical approaches such as [13,4] and approaches based on CSP have emerged [10,3,11,
`14]. In CSP approaches, configuration can exploit powerful constraint problem solvers
`for solving complex problems [5,1]. From the other hand, logical approaches make use
`of a more explicit and structured representation of the entities to be configured (e.g. [9]).
`Logical approaches seem to offer significant benefits when interaction with the user
`(e.g. [7]) and explainability of the result (or failure) are major requirements.
`Configuration, as many other tasks, can be computationally expensive; therefore, the
`idea of problem decomposition looks attractive since, from the early days of AI, problem
`decomposition has emerged as one of the most powerful mechanisms for controlling
`complexity. Ideally, the solution of a complex configuration problem should be easily
`assembled by combining the solutions of the subproblems the initial problem has been
`decomposed into. Moreover, decomposing a configuration problem into a set of mutually
`independent subproblems allows the configuration process to be distributed among a set
`of configurators working in parallel. Unfortunately, in many cases it is not obvious at all
`how to perform such a decomposition.
`In the present work the issue of decomposing a configuration problem is approached
`in a framework where knowledge about the entities is represented in a structured way
`by using a KL-One like language augmented with a constraint language for expressing
`
`D. Scott (Ed.): AIMSA 2002, LNAI 2443, pp. 81–90, 2002.
`c(cid:1) Springer-Verlag Berlin Heidelberg 2002
`
`Page 1 of 10
`
`FORD 1009
`
`

`
`82
`
`D. Magro and P. Torasso
`
`complex inter-role relations (see section 2 for a summary of the representation language).
`Partonomic relations provide the basic knowledge for decomposing the configuration
`problem. In fact, two subparts involved into two partonomic relations can not be inde-
`pendently configured if there is at least a constraint that links them together. For this
`reason we have introduced a notion of boundness among constraints (section 3) which
`assures that two components not involved in a same set of bound constraints can be
`independently configured.
`Section 4 provides a high-level description of the configuration algorithm and of the
`decomposition strategy, while an example of an application of the algorithm is shown in
`section 5. Section 6 reports preliminary experimental results concerning the reduction
`of the computational effort. A discussion of the approach is reported in section 7.
`
`2 The Conceptual Language
`In the last few years we have developped a representation formalism called FPC [6,7]
`(Frames, Parts and Constraints) for modeling configuration problems. Basically, FPC
`is a frame-based KL-One like formalism augmented with a constraint language.
`InFPC, there is a basic distinction between atomic and complex components. Atomic
`components are described by means of a set of features characterizing the component
`itself, while complex components can be viewed as structured entities whose character-
`ization is mainly given in terms of their (sub)components, which can be complex com-
`ponents in their turn or atomic ones. FPC offers the possibility of organizing classes of
`(both atomic and complex) components in taxonomies as well as the facility of building
`partonomies that (recursively) express the whole-part relations between each complex
`component and any one of its (sub)components. Moreover, in any complex component,
`a set of constraints restricts the set of valid combinations of its (sub)components.
`Frames and Parts. InFPC , each frame represents a class of components (either atomic
`or complex) and it has a set of member slots associated with it. Each slot represents a
`property of the components belonging to the class and it can be of type either partonomic
`or (alternatively) descriptive. Any slot p of a class C is described via a value restriction
`D(that can be another class or a set of values of a predefined kind) and a number restriction
`(i.e. an integer interval [m,n] with m ≤ n), as usual in the KL-One like representation
`formalisms. A slot p with value restriction D and number restriction [m,n] captures the
`fact that the property p for any component of type C is expressed by a (multi)set of
`values of type D whose cardinality belongs to the interval [m,n].
`In the following we restrict our attention to partonomic slots since in this framework
`they represent the basic knowledge for problem decomposition.
`Partonomic slots are used for capturing the whole-part relation among compo-
`nents. In FPC this relation is assumed to be asymmetric and transitive. Formally,
`any partonomic slot p of a class C is interpreted as a relation p : C → D such that
`(∀c ∈ C)(m ≤ |p(c)| ≤ n)), being D and [m,n], respectively, its value and its number
`restrictions; the meaning is straightforward: any complex component of type C has from
`a minimum of m up to a maximum of n direct parts of type D via a whole-part relation
`named p.
`It is worth noting that in each configuration a component can neither be a direct part
`of two different complex components nor a direct part of the same complex component
`via two different whole-part relations (exclusiveness assumption on parts).
`
`Page 2 of 10
`
`FORD 1009
`
`

`
`Decomposing and Distributing Configuration Problems
`
`83
`
`C1
`
`C2
`
`p1(1;2)
`
`C
`
`p2(1;2)
`
`p3(1;2)
`
`q5(1;2)
`
`A7
`
`A5
`
`q1(1;2)
`
`A1
`
`q2(1;2)
`q6(1;2)
`
`A2
`
`A6
`
`A11
`
`A12
`
`q3(1;2)
`q4(1;1)
`
`A3
`
`A4
`
`CONSTRAINTS
`Associated with C:
`[co1]({<p1,q1>})(1;1) ==> ({<p2,q5>})(1;1)
`[co2]({<p1,q2>})(1;1) ==> ({<p2,q3>})(1;1)
`[co3]({<p2,q3>})(2;2) ==> ({<p2,q4>})(2;2)
`[co4]true ==> ({<p1,q1>})(in A11 (1;4))
`[co5]({<p3>})(1;1) ==> ({<p3>})(in A71)
`Associated with C1:
`[co6]({<q1>})(1;1) ==> ({<q6>})(in A61)
`
`Fig. 1. A toy conceptual model
`
`Figure 1 contains a toy conceptual model that we use here as a simple example.
`Each rectangle represents a class of complex components, each oval represents a class
`of atomic components and any thin solid arrow corresponds to a partonomic slot. In
`the figure, it is stated, for instance, that C is a class of complex components and the
`partonomic slot p1 specifies that each instance of C has to contain one or two (complex)
`components of type C1; whereas the partonomic slot p3 states that any instance of C
`has to contain one or two (atomic) components of type A7.
`In any conceptual model, a slot chain γ = (cid:9)p1, . . . , pn(cid:10), starting in a class C and
`ending in a class D is interpreted as the relation composition pn ◦ pn−1 ◦ . . . ◦ p1 from
`C to D. The chain represents the subcomponents of a complex component c ∈ C via
`the whole-part relations named p1, . . . , pn. In figure 1, for example, (cid:9)p1, q1(cid:10) denotes
`the subcomponents (of type A1) of each instance of C through the partonomic slots p1
`and q1. Similarly, a set of slot chains R = {γ1, . . . , γm} (where each γi starts in C and
`(cid:1)m
`(cid:1)m
`ends in Di) is interpreted as the relation union
`i=1 γi from C to
`i=1 Di.
`Besides the partonomies, also the taxonomies are useful in the conceptual models.
`In figure 1 the subclass links are represented by thick solid arrows. In that toy domain
`we assume that each class of atomic components Ai is partitioned into two subclasses
`Ai1 and Ai2. Only the partitioning of A1 into A11 and A12 is reported in figure.
`Constraints. A set (possibly empty) of constraints is associated with each class of com-
`plex components. These constraints allow one to express those restrictions on the com-
`ponents and the subcomponents of the complex objects that can’t be expressed by using
`only the frame portion of FPC, in particular the inter-slot constraints that cannot be
`modeled via the number restrictions or the value restrictions.
`Each constraint cc associated with C is of the form α ⇒ β, where α is a conjunction
`of predicates or the boolean constant true and β is a predicate or the boolean constant
`false. The meaning is that for every complex component c ∈ C, ifc satisfies α then it
`must satisfy β. It should be clear that if α = true, then, for each c ∈ C, β must always
`hold, while if β = f alse, then, for each c ∈ C, α can never hold.
`In the following we present only a simplified version of some predicates available
`in FPC. For a more complete description of them see [6].
`
`Page 3 of 10
`
`FORD 1009
`
`

`
`84
`
`D. Magro and P. Torasso
`(cid:10) is a slot chain starting in a
`Let R = {γ1, . . . , γm}, where each γi = (cid:9)pi1, . . . pin
`class of C complex components. For any c ∈ C, R(c) denotes the values of the relation
`R computed for c.
`1) (R)(h; k). c ∈ C satisfies the predicate iff h ≤ |R(c)| ≤k , where h, k are non
`negative integers with h ≤ k.
`2) (R)(inI). c ∈ C satisfies the predicate iff R(c) ⊆ I, where I is a union of classes in
`the conceptual model.
`3) (R)(inI(h; k)). c ∈ C satisfies the predicate iff h ≤ |R(c) ∩ I| ≤k , where h, k are
`non negative integers with h ≤ k and I is a union of classes in the conceptual model.
`For example, the constraint co5 states that if only one component playing the parto-
`nomic role p3 is present in a configuration of an object of type C, then this component
`must be of type A71. It is worth noting that the user’s requirements are automatically
`translated into the FPC constraint language. For example, the (user’s) requirement of
`inserting in a configuration of an object of type C from 1 up to 4 subcomponents of type
`A11 is expressed by the constraint co4.
`
`3 The Role of Partonomic Knowledge in Problem Decomposition
`
`Given this framework, configuring a complex object of type C means to completely
`determine an instance c of C in which all the partonomic slots of C are instantiated
`and each direct component of c is completely configured too. c has to respect both the
`conceptual model (number and value restrictions imposed by the taxonomy and the
`partonomy as well as the constraints associated with the classes of components involved
`in c) and the user’s requirements.
`Configuring a complex component by taking into consideration only its taxo- parto-
`nomic description would be a straightforward activity. In fact, for any well formed model
`expressed in FPC in which no constraints are associated with any class, a configuration
`respecting that model would always exist. A simple algorithm could find it without any
`search and by simply starting from the class of the target object (i.e. the one for which the
`configuration has to be built), considering each slot p of that class and, for it, choosing its
`cardinality, i.e. choosing the number of components playing the partonomic role p to in-
`troduce into the configuration, and the type for each such component. This process must
`be recursively repeated for each complex component introduced in the configuration,
`until all the atomic ones are reached. In this process the algorithm needs only to respect
`the number and the value restrictions of the slots. Unfortunately, this is not realistic. The
`conceptual model usually contains complex constraints that link together different slots.
`In this more realistic situation a solution can’t be generally found by making only a set
`of local choices and without resorting to search in a large space of alternatives.
`Moreover, the requirements usually imposed by the user to the target artifact further
`restrict the set of legal configurations. This means that the search for a configuration is
`not guaranteed to be fruitful any more. In fact, even assuming the consistency of the
`conceptual model, the user’s requirements could be inconsistent w.r.t. it and in such a
`case no configuration respecting the model and satisfying the requirements exists.
`Therefore, in general, the task of solving a configuration problem can be rather
`expensive from a computational point of view. As we have mentioned above, in FPC
`framework this is mainly due to the constraints (both those that are part of the conceptual
`model and those imposed as user’s requirements) that link together different components
`
`Page 4 of 10
`
`FORD 1009
`
`

`
`Decomposing and Distributing Configuration Problems
`
`85
`
`and subcomponents. In these situations a choice made for a component during the con-
`figuration process might restrict the choices actually available for another one, possibly
`preventing the latter to be fully configured. In such cases the configuration process has to
`revise some decision that it previously took and to explore a different path in the search
`space. Usually, in real cases the search space is rather huge and many paths in it don’t
`lead to any solution.
`However, in many cases it does not happen that every constraint interacts with each
`other and the capability of recognizing the sets of (potentially) interacting constraints
`can constitute the basis for decomposing a problem into independent subproblems.
`
`Once a problem has been decomposed into a set of independent subproblems, these
`could be solved concurrently and with a certain degree of parallelism, potentially re-
`ducing the overall computational time. However, also a sequential configuration process
`can take advantage of the decomposition. In fact, if two subproblems are recognized to
`be independent, the configurator is aware that no choice made during the configuration
`process of the first one needs to be revised if it enters a failure path while solving the
`second one.
`To be effective, the task of recognizing the decomposability of a problem (and of
`actually decomposing it) should not take too much time w.r.t. the time requested by the
`whole resolution process.
`In our approach, the partonomic knowledge can be straightforwardly used in recog-
`nizing the interaction among constraints (with an acceptable precision) and in defining a
`way of decomposing a configuration problem into independent subproblems. With this
`aim, we introduce the bound relation among constraints. Intuitively, two constraints are
`bound iff the choices made during the configuration process in order to satisfy one of
`them can interact with those actually available for the satisfaction of the second one.
`If c is a complex component in a (tentative) configuration, the bound relation Bc is
`defined in the set CON ST RS(c) of the constraints that c must satisfy, as follows: let
`u, v, w ∈ CON ST RS(c). If u and v contain both a same partonomic slot p of class(c)
`then uBcv (i.e. if u and v refer to a same part of c, they are bound); if uBcv and vBcw
`then uBcw (transitivity).
`It is easy to see that Bc is an equivalence relation. If U is an equivalence class in
`the quotient set CON ST RS(c)/Bc, every constraint in U might interact with any other
`constraint in the same class during the configuration process of c. On the contrary, given
`the exclusiveness assumption on parts, ifV ∈ CON ST RS(c)/Bc is different from
`U, it means that in c the constraints belonging to V don’t interact in any way with
`those in U. This means that the problem of configuring c by taking into consideration
`CON ST RS(c) can be split into the set of independent subproblems of configuring c
`by considering the set W of constraints, for each W ∈ CON ST RS(c)/Bc.
`
`4 Configuration via Decomposition and Distribution
`
`As said in the section above, bound relation can be used for singling out independent
`subproblems in the configuration process. A sequential algorithm for configuration ex-
`ploiting decomposition is described in [8]. In the present paper we describe a general
`configuration technique which exploits the decomposition mechanism for distributing
`independent subproblems among a set of configurators working in parallel.
`
`Page 5 of 10
`
`FORD 1009
`
`

`
`86
`
`D. Magro and P. Torasso
`Let P be a pool of m configurators (m ≥ 1). In the following we assume that each
`configuration request is sent to P. If no configurator is available, the request is enqueued
`and it is assigned to a configurator as soon as one becomes available.
`Each configuration request is a 4-TUPLE (cid:9)CM, T, c, V (cid:10), where CM is the FPC
`conceptual model describing the domain; T is a tentative configuration "under construc-
`tion"; c is a complex component occurring in T and V is a set of FPC constraints
`holding for c. Such a 4-TUPLE corresponds to the request of extending the tentative
`configuration T (in the domain modeled by CM) by configuring only those direct parts
`of the complex component c involved in the constraints in V .
`Each configurator in P runs the conf igure procedure in figure 2. conf igure pro-
`cedure accepts as input a configuration request (cid:9)CM, T, c, V (cid:10) and it returns either the
`F AILU RE message or a tentative configuration in which the complex component c
`has been successfully extended.
`The problem of extending c by taking into consideration the constraints in V requires
`the introduction in T of a set of direct components of c (first instruction of the procedure
`in fig. 4) and, then, the extension of each complex component introduced in this first step
`(WHILE loop).
`Procedure insertDirectComponents(CM, T, c, V ) tries to introduce in T the di-
`rect components of c that might be critical for the satisfaction of the constraints in V .
`To do this, among the partonomic slots of the most specific class (w.r.t. the taxonomy)
`in CM to which c belongs (let’s call it class(c)), it considers only those occurring in
`some constraint of the set V (in fact, the other partonomic slots possibly associated
`with class(c) are not critical for the satisfaction of the constraints in V ). For each such
`partonomic slot p, this procedure chooses both the number of the components playing
`the partonomic role p that should be inserted into the tentative configuration T and the
`type for each of them. Such choices are done by taking into account both the number
`and value restrictions associated with the partonomic slot p. Since, in general, there are
`more than one alternatives, the configurator records all the open choices. Whenever a
`direct complex component of c is introduced, it is inserted in the queue dirC comps(c).
`
`procedure configure(CM,T,c,V){
` T = insertDirectComponents(CM,T,c,V);
` if(T == FAILURE){return FAILURE;}
` /*T FAILURE*/
`=
` while(dirC_comps(c) <>){
`=
` c‘ = dequeue(dirC_comps(c));
` CONSTRS(c’) = I_Constrs(c’) L_Constrs(c’);
`[
` = CONSTRS(c’)/ ;
`fV ; : : : ; Vng
`Bc
` = send( , );
`fhT; c; Viign
`fT ; : : : ; Tng
`P
` if( ){
`( i)(Ti == F AI LU RE)
` if(no open choice for c){
` return FAILURE;
` }else{BACKTRACK;}
` }else{T = merge( );}
`fT ; : : : ; Tng
` }//while
` return T;
`}//configure
`
`i=
`
`
`
`Fig. 2. High level description of the configuration algorithm
`
`Page 6 of 10
`
`FORD 1009
`
`

`
`Decomposing and Distributing Configuration Problems
`
`87
`
`It can happen that in this phase there is no way to insert these direct components of
`c into T without violating any constraint in V : in this case, the process fails.
`The WHILE loop considers each complex direct component c(cid:3)
`of c that was intro-
`duced (and enqueued in dirC comps(c)) in the previous step. The set of constraints that
`is CON ST RS(c(cid:3)) =I Constrs(c(cid:3)) ∪ L Constrs(c(cid:3)).
`have to be considered for c(cid:3)
`I Constrs(c(cid:3)) is the set of constraints that c(cid:3)
`inherits from c, namely the constraints in V
`in which some partonomic slot associated with class(c(cid:3)) occurs (i.e. those constraints in
`V mentioning some component of c(cid:3)
`); L Constrs(c(cid:3)) is the set of local constraints for c(cid:3)
`,
`namely those ones associated with class(c(cid:3)) in CM, plus the constraints expressing the
`. CON ST RS(c(cid:3)) is then partitioned into the set {V1, . . . , Vn}
`user’s requirements for c(cid:3)
`of equivalence classes w.r.t. the bound relation Bc(cid:1). Each class Vi induces a subprob-
`lem, thus the configuration of the component c(cid:3)
`w.r.t. the constraints CON ST RS(c(cid:3))
`is decomposed into the set of subproblems {(cid:9)T, c(cid:3), Vi(cid:10)}n
`i=1 and this set of configuration
`requests is sent to the pool P of configurators. The results of these configurations is
`collected in {T1, . . . , Tn}. If one (or more) configuration request (cid:9)T, c(cid:3), Vi(cid:10) leaded to a
`failure, it means that, given the tentative configuration T , there is no way to configure
`by respecting the constraints CON ST RS(c(cid:3)). In this case, if there are
`the component c(cid:3)
`some open choices in the configuration of c, a backtracking mechanism is activated, oth-
`erwise a failure occurs.1 In case all the subproblems are successfully solved, the partial
`configurations {T1, . . . , Tn} are merged and a new tentative configuration T , containing
`the configuration of c(cid:3)
`w.r.t. CON ST RS(c(cid:3)), is produced. As shown in the example
`reported below, the merge operation is fairly simple since it only consists in "summing
`up" the partial solutions. In fact, the partition of the constraints induces a partition of the
`partonomic slots associated with class(c).
`The configuration of c w.r.t. the constraints in V is completed when all the direct
`complex components of c in dirC comps(c) are successfully configured.
`It is worth saying that when a configurator Ci ∈ P sends a set of configuration
`requests to P, it becomes immediately available, thus the mechanism is deadlock-free.
`Let us suppose that the user asks for a configuration of a complex object c0 of type
`C and imposes a set of requirements REQS. A main module computes the set of
`constraints CON ST RS(c0) containing the constraints derived from the user’s require-
`ments as well as those associated with C in CM. The main decomposes this problem
`into the requests
`
`{(cid:9)CM, T0, c0, Vi(cid:10)}li=1(l ≥ 1) (where T0 contains only the component c0) and sends
`them to P.
`
`5 An Example
`
`Figure 3 reports eight snapshots of the configuration process of an object of type C w.r.t.
`the constraints co1-co5, where co4 is a user requirement (see figure 1). In figure 3, each
`x 1 identifies a component of type X, while any partonomic slot p is identified by an arc
`labelled p; an arrow indicates the last component that has been expanded or the compo-
`nent that will be expanded next. At the beginning, the partial configuration Ta contains
`only the component c 1 representing the target object. The main module partitions the
`1 The backtracking mechanism is not described here, since it is out of the scope of this paper. A
`description of this mechanism can be found in [8].
`
`Page 7 of 10
`
`FORD 1009
`
`

`
`88
`D. Magro and P. Torasso
`constraints for c 1 into the two classes V1 = {co1, co2, co3, co4} and V2 = {co5}
`and sends the two correspondent configuration requests to the pool of configurators.
`The configuration of c 1 w.r.t. the constraints V2 leads to the partial configuration Tg;
`in parallel, the configuration request relevant to V1 is taken into consideration. Since
`only the partonomic slots p1 and p2 of C occur in the constraints belonging to V1, only
`the complex components c1 1 and c2 1, playing these partonomic roles, are inserted
`into the partial configuration (Tb). To complete the configuration of c 1 w.r.t. V1, its
`direct complex components c1 1 and c2 1 have to be configured too. The constraints
`for c1 1 (those inherited from c 1 and the local one co6) are split into the two classes
`V3 = {co1, co4, co6} and V4 = {co2}; the solutions of the two correspondent sub-
`problems lead to the partial configurations Tc and Td, respectively. These two partial
`configurations are merged and Te is produced. The configuration of the component c2 1
`is decomposed into two subproblems corresponding to the two classes of constraints
`V5 = {co1} and V6 = {co2, co3}; after merging the solutions to these two subprob-
`lems, Tf , representing a partial configuration of c 1 w.r.t. V1 is produced. A final merge
`between Tg and Tf produces a complete configuration of the target object (Th).
`
`6 Preliminary Results
`
`In order to test the impact of the decomposition strategy on the configuration process,
`we have performed an experiment in a real domain of PC configuration. In this domain
`
`{V1, V2}
`c_1
`
`Ta
`
`{V3,V4}
`c1_1
`
`{V1}
`c_1
`
`p1
`
`p2 c2_1
`
`Tb
`
`{V1}
`c_1
`
`{V4}
`c1_1
`
`p1
`
`q2
`
`a21_1
`
`p2 c2_1
`
`Td
`
`c1_1
`
`a11_1
`
`c_1
`
`p1
`
`p2 c2_1
`
`q1
`a61_1
`q6
`q2
`
`a21_1
`
`Tf
`
`q5
`q3
`
`q4
`
`a51_1
`
`a31_1
`
`a41_1
`
`{V2}
`c_1
`
`p3
`
`Tg
`
`a71_1
`
`{V1}
`c_1
`
`{V3}
`c1_1
`
`p1
`
`p2 c2_1
`
`a11_1
`
`q1
`a61_1
`q6
`
`Tc
`
`c_1
`
`Te
`
`c1_1
`
`a11_1
`
`p1
`
`p2 c2_1
`
`q1
`a61_1
`q6
`q2
`
`a21_1
`
`c1_1
`
`a11_1
`
`c_1
`
`p1
`
`p2 c2_1
`
`p3
`
`q1
`a61_1
`q6
`q2
`
`a21_1
`
`Th
`
`a71_1
`
`q5
`q3
`
`q4
`
`a51_1
`
`a31_1
`
`= Merge
`
`= Decompose
`
`a41_1
`
`Fig. 3. A configuration example
`
`Page 8 of 10
`
`FORD 1009
`
`

`
`Decomposing and Distributing Configuration Problems
`
`89
`
`a set of atomic components, such as CPUs, memory slots, monitors, etc., can be used for
`configuring complex objects, such as different kinds of PCs, motherboards etc. according
`to the user requirements. We have generated a test set of 153 configuration problems:
`for each of them we have specified the type of the target object (e.g. a PC for graphical
`applications) and the requirements that it must satisfy (e.g. it must have a CD writer of
`a certain kind, it must be fast enough and so on). In this experiment, we used only one
`configurator, in order to test the impact of the decomposition technique on a sequen-
`tial approach to the resolution of configuration problems. A configuration problem is
`considered solved iff the configurator either provides a configuration or detects that no
`configuration satisfying the user’s requirements can be produced, within the timeout of
`360 sec.
`It came out that the strategy no dec that did not attempt any decomposition was able
`to solve 150 out of the 153 configuration problems (i.e. its competence was of 98.0%);
`whereas the strategy dec making use of decomposition solved all the problems (i.e. its
`competence was of 100%). The average CPU time computed on the 150 problems solved
`by both strategies was 7735.4 msec. for no dec and 2257.4 for dec (i.e. −70.8% w.r.t.
`no dec). Moreover, the average CPU time computed on the 153 problems solved by dec
`was 4502.3 msec. This means that dec was able to solve the 3 difficult problems that
`no dec did not solve with an average cost still less than that relevant to the 150 problems
`solved by no dec 2.
`
`7 Discussion
`
`The present paper addresses the issue of decomposing a configuration problem into sim-
`pler subproblems by exploiting as much as possible the implicit decomposition provided
`by the partonomic relations of complex components. The adoption of a structured frame-
`work for modeling the configuration domains as well as for expressing the configuration
`problems plays a major role since the criterion for singling out the classes of bound con-
`straints is based on an analysis of the partonomic slots mentioned in the constraints. The
`problem decomposition is induced by this partitioning of the constraints into classes.
`Since a set of constraints is associated with each complex component, the configura-
`tion process can try to recursively decompose the problem each time it has to configure
`a component or a subcomponent of the target object. The set of mutually independent
`subproblems the main problem has been decomposed into can be solved in parallel by
`a pool of configurators. Our main motivation for decomposing configuration problems
`is saving in computational effort. However, there are domains in which the configura-
`tion problems are distributed by their nature [2]. This is the case, for example, of those
`domains in which the main components of a complex product are provided by different
`suppliers. In these cases the capability of decomposing at least the main configuration
`problem (i.e. the capability of attempting a decomposition at the target object level)
`can be quite useful, since it would single out the possible interactions among the main
`components.
`
`2 It is worth noting that if we computed the average CPU time spent by no dec on all the 153
`problems (i.e. including the 3 unsolved problems), we would obtain 14642.5 msec.
`
`Page 9 of 10
`
`FORD 1009
`
`

`
`90
`
`D. Magro and P. Torasso
`
`Preliminary experimental results demonstrate the effectiveness of the decomposition
`technique in a sequential approach to configuration. Further experiments are planned in
`order to test the impact of the distribution of the subproblems to a pool of configurators.
`
`References
`
`1. R. Dechter. Enhancement schemes for constraint processing: backjumping, learning, and
`cutset decomposition. Artificial Intelligence, 41:273–312, 1990.
`2. A. Felfernig, G. Friedrich, D. Jannach, and M. Zanker. Distributed configuring. In Proc.
`IJCAI-01 Configuration WS, pages 18–24, 2001.
`3. G. Fleischanderl, G. E. Friedrich, A. Haselb¨ock, H. Schreiner, and M. Stumptner. Configuring
`large systems using generative constraint satisfaction. IEEE Intelligent Systems, (July/August
`1998):59–68, 1998.
`4. G. Friedrich and M. Stumptner. Consistency-based configuration. In AAAI-99, Workshop on
`Configuration, 1999.
`5. G. Gottlob, N. Leone, and F. Scarcello. A comparison of structural csp decomposition meth-
`ods. Artificial Intelligence, 124:243–282, 2000.
`6. D. Magro and P. Torasso. Description and configuration of complex technical products in a
`virtual store. In Proc. ECAI 2000 Configuration WS, pages 50–55, 2000.
`7. D. Magro and P. Torasso. Supporting product configuration in a virtual store. LNAI, 2175:176–
`188, 2001.
`8. D. Magro and P. Torasso. Problem decomposition in configuration. In Proc. ECAI 2002
`Configuration WS (to appear), 2002.
`9. D. L. McGuinness and J. R. Wright. An industrial-strength description logic-based configu-
`rator platform. IEEE Intelligent Systems, (July/August 1998):69–77, 1998.
`10. S. Mittal and B. Falkenhainer. Dynamic constraint satisfaction problems. In Proc. of the
`AAAI 90, pages 25–32, 1990.
`In Proc.
`11. D. Sabin and E.C. Freuder. Configuration as composite constraint satisfaction.
`Artificial Intelligence and Manufacturing. Research Planning Workshop, pages 153–161,
`1996.
`12. D. Sabin and R. Weigel. Product configuration frameworks - a survey.
`Systems, (July/August 1998):42–49, 1998.
`13. T. Soininen, I. Niemel¨a, J. Tiihonen, and R. Sulonen. Unified configuration knowledge
`representation using weight constraint rules. In Proc. ECAI 2000 Configuration WS, pages
`79–84, 2000.
`14. M. Veron and M. Aldanondo. Yet another approach to ccsp for configuration problem. In
`Proc. ECAI 2000 Configuration WS, pages 59–62, 2000.
`
`IEEE Intelligent
`
`Page 10 of 10
`
`FORD 1009