ions of several real-world scenarios. The evaluation of our solution on a set of benchmark instances derived from commercial (re)configuration problems shows practical applicability.
Reconfiguration is an important task in the after-sale lifecycle of configurable products and services, because requirements for these products and services are changing in parallel with the customers’ business [6; 2]. In order to keep a product or a service up-to-date a re-engineering organization has to decide which modifications should be introduced to an existing configuration such that the new requirements are satisfied but change costs are minimized.
Following the knowledge based configuration approach, we formulate reconfiguration problem instances as extensions of declaratively defined configuration problem instances where configurations are represented by facts and requirements are expressed by logical descriptions. These requirements may be partitioned into customer requirements and system specific configuration requirements. A configuration is simply defined as a subset of a logical model of the requirements. Informally, a reconfiguration problem instance is generated by an adaption of the requirements resulting in a new set of requirements and therefore a new instance of a configuration problem is formulated. Subsequently, given legacy configurations have to be adapted to configurations for the new requirements. In our approach, the knowledge base
This work has been developed within the scope of the project RECONCILE (reconciling legacy instances with changed ontologies) and was funded by FFG FIT-IT (grant number 825071). comprises two parts, the description of the new configuration problem instance and transformation knowledge regarding reuse and deletion of parts of a legacy configuration. The first part is a usual instance of a configuration problem where all valid configurations are specified by the set of adapted requirements. The second part describes a mapping from the pieces of the legacy configuration to the ontology of the new configuration problem instance. Technically speaking this is a mapping from facts describing the legacy configuration to facts in the ontology of the new configuration problem instance. For generating a reconfiguration the problem solver has to decide which parts of the legacy configuration are either reused or deleted and which new parts have to be created.
We introduce general definitions for (re)configuration problems employing Herbrand-models of logical descriptions. Based on these definitions it is simple to see that configuration and reconfiguration problems fall into the same complexity classes. Because of the remarkable advances of answer set programming (ASP) [8; 5] we base our implementation on this reasoning framework. ASP was first applied to configuration problems by [9]. In particular, we provide modeling patterns for configuration and reconfiguration which allow the generation of optimized reconfigurations exploiting standard ASP solvers. Finally, our evaluation shows that the proposed method solves reconfiguration problem instances which are practically interesting for industrial applications.
In Section 2 we present an introductory example of a configuration problem and some reconfiguration scenarios. Then, configuration problems are defined in Section 3. In Section 4 a review of the basic concepts of ASP is given followed by an exemplification of modeling in Section 5. Section 6 provides the definition of reconfiguration problems. Subsequently, modeling patters and an example of their application are provided in Section 7. Finally, we show the results of an evaluation in Section 8 and conclude in Section 9. 2
Let us exemplify different configuration and reconfiguration scenarios on a problem which is a simple abstraction of several configuration problems occurring in practice, i.e. entities may be contained in other entities but some restrictions must be fulfilled. We employ the ontology comprising the concepts person, thing, cabinet, and room where persons are related to things, things are related to cabinets, cabinets are related to rooms, and rooms are related to persons. These relations are modeled either by roles, associations, or predicate symbols depending on the modeling language (e.g. description logic, UML, or predicate logic).
As input to the configuration problem an ownership relation between persons and things is provided. We call this input a customer requirement since it reflects the individual needs of a customer using a configuration system whereas configuration requirements specify the properties of the system to be configured. Each person can own any number of things but each thing belongs to only one person. The problem is to place these things into cabinets and the cabinets into rooms of a house such that the following configuration requirements are fulfilled: each thing must be stored in a cabinet; a cabinet can contain at most 5 things; every cabinet must be placed in a room; a room can contain at most 4 cabinets; a person can own any number of rooms; each room belongs to a person; and a room may only contain cabinets storing things of the owner of the room.
In order to keep the example simple we only consider configuration of one house and represent all individuals using unique integer identifiers.
Informally, a configuration is every instantiation of the relations which satisfies all requirements.
Let a sample house problem instance include two persons such that the first person owns five things numbered 3 to 7 and the second person owns one thing 8. A solution for this house configuration problem instance is shown in Figure 1.
Reconfiguration is necessary, whenever the customer requirements or configuration requirements are changed. For instance, it becomes necessary to differentiate between long and short things with the following new requirements: a cabinet is either small or high; a long thing can only be put into a high cabinet; a small cabinet occupies 1 and a high cabinet 2 of 4 slots available in a room; all legacy cabinets are small.
The customer requirements, in this case, define for each thing if it is long or short. For instance, the customer provides information that the things 3 and 8 are long; all others are short. Moreover, the first person gets an additional long thing 21. The changes to the legacy configuration are summarized in Figure 2 showing an inconsistent configuration, where thing 21 is not placed in any of the cabinets, and cabinets 9 and 10 are too small for things 3 and 8.
To obtain a solution which is shown in Figure 3 the reconfiguration process changes the size of cabinets 9 and 10 to high and puts the new thing 21 into cabinet 9. A new small cabinet 22 is created for thing 7.
In our reconfiguration process every modification to the existing configuration, i.e. reusing/deleting/creating individuals and their relations, is associated with some cost. Therefore the reconfiguration problem is to find a consistent configuration by removing the inconsistencies and minimizing the costs involved. Different solutions will be found depending on the given modification costs. If, for example, the costs for adding a new high cabinet are less than the cost for changing an existing small cabinet into a high cabinet, then the previous solution should be rejected as its costs are too high. One of the solutions with less reconfiguration costs (see Figure 4) includes two new cabinets 22 and 23, because this is cheaper than converting the existing small cabinets into high cabinets. Also it contains the empty cabinet 10 because it’s cheaper to keep the cabinet than to delete it. Note, this behavior can be controlled by the domain specific costs.
We employ a definition of configuration problems based on logical descriptions [9; 3]. The basic idea is that every finite Herbrand-model contains the description of exactly one configuration.
The description of a configuration is defined by relations expressed by a set of predicates PS. This set of predicates is called the solution schema. For our example the solution schema consists of the four unary predicates thing/1, person/1, cabinet/1 and room/1 representing the individuals and the four binary predicates, namely personTOthing/2, personTOroom/2, roomTOcabinet/2 and cabinetTOthing/2 representing the relations. An instantiation of this solution schema corresponds to a configuration. A fragment of this instantiation is presented below. {person(1), thing(3), room(15), cabinet(9), cabinetTOthing(9,3), personTOthing(1,3), roomTOcabinet(15,9), personTOroom(1,15),...}
Note, this description of a configuration generalizes the component/port models or variable/value based descriptions of a configuration.
We assume that every predicate symbol is unique in a logical theory and has a unique arity. The set of Herbrand-models is specified by a set of logical sentences REQ, which usually comprises the individual customer requirements and the configuration requirements. Configuration requirements reflect the set of all allowed configurations for an artifact, whereas customer requirements may comprise facts and logical sentences specifying the individual needs of customers. The same configuration requirements are a basis for different sets of customer requirements. E.g. the component library of a technical system is stable for some time.
figuration problem instance hREQ; PSi is defined by a set of logical sentences REQ representing requirements and PS a set of predicate symbols representing the solution schema. For optimization purposes an objective function f (S) 7! N maps any set of atoms S to positive integers where S contains only atoms whose predicate symbols are in PS.
Let HM(L) denote the set of Herbrand-models of a set of logical sentences L for a given semantics.
figuration problem instance CPI = hREQ; PSi iff there is a Herbrand-model M 2 HM(REQ) and S is the set of all the elements of M whose predicate symbols are in PS and S is finite, i.e. S = fp(t)jp 2 PS and p(t) 2 M)g. By p(t) we denote a ground instance of p with a term vector t.
S is an optimal configuration for CPI iff S is a configuration for CPI and there is no configuration S0 of CPI s.t. f (S0) < f (S).
configuration problems be defined by hREQ; PSi and objective functions f ( ).
Decision problem: Given a set of atoms S. Decide if S is a configuration for a configuration problem instance. Generation (optimization) problem: Generate a set of atoms S s.t. S is a configuration (an optimal configuration) for a configuration problem instance.
The set of Herbrand-models depends on the semantics of the employed logic. In this paper, we apply answer set programming and a stable model semantics for knowledge representation and reasoning because this approach allows a concise and modular specification, assures decidability, and avoids the inclusion of unjustified atoms (e.g. unjustified components) in configurations [9]. 4
ASP is based on a decidable fragment of first-order logic enhanced with default negation and aggregation. We give a brief summary of the employed ASP variant and language constructs as needed. A detailed discussion of ASP can be found in [5; 4].
We start our introduction with rules without variables and introduce logical variables afterwards. A rule has the structure C0 C1; : : : ; Cn. Elements C1; : : : ; Cn on the righthand-side (the body of a rule) are either literals or weight constraints. A literal is either an atom or a default negated atom. Default negation is expressed by not. C0 (head of the rule) is either an atom or a weight constraint. We do not consider default negation on the left-hand-side and in weight constraints. If all Ci are literals then such a rule is called a normal rule.
To be able to express the requirements of our example domain we introduce a simplified version of weight constraints and their special case – cardinality constraints [9; 8; 4]. Weight constraints are of the form l fa1 = w1; : : : ; an = wmg u where ai are atoms, wj are integers representing weights of corresponding atoms and l; u are integers specifying lower and upper bounds. Given a set of atoms M representing a Herbrand-interpretation, the interpretation of a weight constraints evaluates to true iff the sum of weights of literals a1; : : : ; an which are contained in M is between l and u. E.g. 0 fa = 1; b = 2g 2 is satisfied by ;, fag or fbg but not by fa; bg. Missing lower or upper bounds express the fact that there are no limits. Cardinality constraints are of the form l fa1; : : : ; ang u where each weight is considered to be equal 1. As usually (negated) atoms in the body of the rule are true if they are (not) in M.
The semantics of a set of rules is defined by a stable model semantics. We give a brief informal description of this semantics for the restricted version employed in this paper and refer the reader to [8] for an in-depth exposition. A set of ground atoms M is a stable model for a set of rules RU iff two properties are fullfiled: (1) M satisfies all rules in RU and (2) every atom in M is justified by a reduced rule set RUM. A rule is satisfied by a set of ground atoms M iff M satisfies C0 or there exists a literal C1; : : : ; Cn which is not satisfied by M. An empty body of a rule is always satisfied. A rule with empty head is satisfied iff one literal in the body is not satisfied. The precise semantics of justification is expressed by a reduction of the rule set RU. Given RU and depending on the set of atoms M, the reduct RUM is generated as follows. In our simplified version, default negated atoms are replaced in the rules RU according to their truth value w.r.t. M, i.e. not a is true iff a 2= M. Rules in RU are deleted if the head does not include an atom of M or some of the upper bounds are violated. Note, weight constraints in the head of a rule may comprise several atoms. Roughly speaking an atom where cabinetTOthing(X; Y) : cabinetDomain(X) is a conditional literal, which is expanded to 1fcabinetTOthing(9; 3); cabinetTOthing(10; 3)g1 1fcabinetTOthing(9; 4); cabinetTOthing(10; 4)g1 in M is justified iff it is contained in the head of a rule and all atoms and weight constraints of this rule are justified. True is always and false is never justified. A weight/cardinality constraint in the body of a rule is justified if enough atoms contained in the weight/cardinality constraint are justified s.t. the lower bound is met. Facts are rules with true as body. Justifications must be acyclic. For instance, 0 fa; bg 1 c is satisfied by fag but fag is not justified. However, if we add the fact c to the knowledge base, fcg, fc; ag, and fc; bg are stable models.
In order to allow logical variables and functional symbols but to guarantee decidability the set of allowed rules is restricted. Potassco [4] requires level-restricted programs. The basic idea is that for each variable V in a rule there is an unnegated atom a in the body s.t. the potentially derivable ground instances of a are limited. If such an atom is available the ground terms to which V needs to be instantiated are known a-priori. I.e. every variable in a rule must be bound to a finite set of ground terms via a predicate that is not subject to a positive recursion (recursion over unnegated atoms) through that rule.
For a succinct specification of facts in our example we use so-called intervals, e.g. person(1::2): corresponds to the facts person(1): person(2): To exemplify the application of cardinality constrains, let an ASP program contain the facts: thing(3::4):
cabinetDomain(9::10):
In order to formulate weight constraints concisely, so called conditional literals are supported. The basic idea is that conditional literals serve as a generator for producing a set of atoms. The constraint 1fcabinetTOthing(X; Y): cabinetDomain(X)g1 thing(Y): thing(3): thing(4): expressing that things 3 and 4 must be connected to exactly one of the cabinets 9 and 10. Conditional literals can be used in weight constraints in place of atoms, where the conditional part (e.g. cabinetDomain(X)) is a (conjunction of) domain predicate(s) preceded by the main part. As usual, strings starting with upper case letters are logical variables. The instantiation of domain predicates is defined by non-recursive normal rules and ground facts. For instantiating conditional literals we have to distinguish between local and global variables. A variable is local iff it appears only in a conditional literal, e.g. X is local in our example. All other variables are global, e.g. Y . During grounding of the rules, global variables are instantiated first. Then the main part of the conditional literal is expanded for the instantiations of the local variables where the conditional part is fulfilled.
Note, in Potassco [4] weight constraints are declared by square brackets l [L1 = w1; : : : ; Ln = wn] u, where Li is a literal and wi is a numerical value representing its weight. Literals Li could be equal. Curly brackets are employed to define cardinality constraints where duplicated literals are removed.
Answer set programming solvers like [8; 5; 4] offer optimization services. In particular, the statement #minimize[L1 = w1@p1; : : : ; Ln = wn@pn]: allows minimization. The minimization statement is similar to the weight constraints with a possibility to assign a priority level pi to each weighted literal. Instead of #minimize also #maximize could be used. An answer set is optimal iff the sum of the weights of literals which are satisfied in this answer set is minimal (maximal) among all answer sets of a given program. Optimization is performed in the order of priorities starting from the highest priority value. 5
In [9] various modeling patterns based on weight constraints were introduced. A fixed set of ground facts define the individuals which are employed for a configuration. This fixed set of ground facts in conjunction with the level-restriction place an upper bound on the size of the number of grounded rules and therefore decidability is guaranteed. At the current state of research such an upper bound on the number of individuals is necessary for many applications. In particular, it is well known from database theory that so called tuple generating dependencies lead to undecidability even under rather strict syntactical restrictions [1]. A tuple generating dependency is 8X 8Y (X ; Y ) ! 9Z (X ; Z) where (X ; Y ) and (X ; Z) are conjunctions of atoms and X ; Y ; and Z are representing vectors of logical variables. Unfortunately, such rules may occur in configuration problem instances. E.g. if a condition holds, a specific individual of some type must exist and this individual must be connected to some other individuals.
However, in many cases it is undesirable to consider only a fixed number of individuals employed in a configuration. Guessing the right number is for configuration generation problems or optimization problems quite hard and often impossible. Therefore we apply the following modeling pattern.
Let pLower and pUpper represent the upper and lower number of individuals of type p. Such a type is called bounded. We require each individual of a configuration, represented by its unique identifier, to be a member of exactly one bounded type. To each bounded type a domain pDomain is associated, representing the set of possible individuals of the bounded type. We employ numbers as identifiers, starting from some offset. For every bounded type p we add the following axioms: pDomain(pOffset + 1 :: pOffset + pUpper): The first rule instantiates the maximal required number of unique individuals of p in pDomain. The second rule makes sure that at least pLower, but at most pUpper individuals of p are asserted. The third rule breaks the symmetry of assertions. By these rules the required number of p individuals are asserted, in order to find a configuration within the given upper and lower bounds.
For some bounded types, e.g. person/1 and thing/1 the bounds pLower and pUpper coincide because the exact number of individuals employed in any configuration is known. In this case the fixed set of p facts can be asserted without using the rules presented above.
In our example the customer provides a number of
requirements for a configuration that include definitions of person
and thing individuals as well as their relations.
person(1..2). thing(3..8).
personTOthing(1,3). personTOthing(1,4).
personTOthing(1,5). personTOthing(
For the bounded type cabinet we add the following rules. The upper and lower numbers of cabinets are computed based on the number of things and persons. The rules for rooms are defined accordingly. cabinetDomain(9..14). 2{cabinet(X):cabinetDomain(X)}6. cabinet(X) :- cabinetDomain(X), cabinetDomain(Y), cabinet(Y), X<Y.
Cardinality restrictions given in Section 2 are encoded with cardinality constraints, where one direction of an association is encoded as a generation rule (see Section 4) and the other direction as a constraint. Such encoding corresponds to Guess/Check/Optimize pattern [5]. Note, the cardinality constraints just as the weight constraints require that logical variables appear in domain predicates. Therefore, we have to use pDomain predicates rather than p predicates, e.g. cabinetDomain(X) instead of cabinet(X). However, individuals employed in relations must also be contained in the corresponding types (see the last four rules of the next sequence of rules). By these rules we avoid situations where an individual is used in a relation but not included in the bounded type. In our example, if the program asserts cabinetTOthing(14,1) then cabinet(14) is also asserted. 1{cabinetTOthing(X,Y):cabinetDomain(X)}1 :- thing(Y). :- 6 {cabinetTOthing(X,Y):thing(Y)}, cabinet(X). 1{roomTOcabinet(X,Y):roomDomain(X)}1 :- cabinet(Y). :- 5 {roomTOcabinet(X,Y):cabinetDomain(Y)}, room(X). room(X) :- roomTOcabinet(X,Y). room(Y) :- personTOroom(X,Y). cabinet(X) :- cabinetTOthing(X,Y). cabinet(Y) :- roomTOcabinet(X,Y).
The next rules describe the fact that a room may contain things of its owner only. personTOroom(P,R) :- personTOthing(P,X),
cabinetTOthing(C,X), roomTOcabinet(R,C). :- personTOroom(P1,R), personTOroom(P2,R), P1!=P2.
In addition, optimization can be applied to generate optimal configurations which minimize the overall configuration costs depending on the objective function. We model the objective function by assigning to each atom in S some costs. This can be achieved with the following modeling pattern. By the atom cost(create(a; w)), where a is an element of S and w is an integer, the costs of creating an element a in a configuration are defined. We employ the conjunction of atoms (X; Y; W) to allow case specific determination of costs. For each p 2 PS include axioms of the following form in REQ: cost(create(p(X)); W)
p(X); (X; Y; W): such that for each atom p(t) in S the answer set contains an atom cost(create(p(t); w)) where w is an integer. E.g.: roomCost(5). personTOroomCost(1). cost(create(room(X)),W) :- room(X), roomCost(W). cost(create(personTOroom(X,Y)), W) :
personTOroom(X,Y), personTOroomCost(W).
All other creation costs are expressed in the same way. We minimize the sum of all costs by means of the following optimization statement: #minimize[cost(X,W)=W@1].
For the given example the solver finds the optimal
configuration including two cabinets and two rooms with the overall
cost 40 (depicted in Figure 1).
{cabinet(
We view reconfiguration as a new configuration-generation problem where parts of a legacy configuration are possibly reused. The conditions under which some parts of the legacy configuration can be reused and what the consequences of a reuse are, is expressed by a set of logical sentences T which relate the legacy configuration S and the new configuration problem instance hREQR; PRi.
reconfiguration problem instance hhREQR; PRi; S; Ti is defined by: hREQR; PRi an instance of a configuration problem, S a legacy configuration and T a set of logical sentences representing the transformation constraints regarding the legacy configuration.
For optimization purposes an objective function g(S; R) 7! N maps legacy configurations S and configurations R of hREQR; PRi to positive integers.
Note, the two-placed objective function expresses the fact that the costs of an reconfiguration depend not only on the elements contained in a reconfiguration but also on the reuse or deletion of elements of the legacy configuration.
In order to avoid name conflicts between the entities of the legacy configuration S and instances of new configuration problems hREQR; PRi, we usually formulate PR and REQR using constants not employed in S. In particular, we use different name spaces for terms referencing individuals. Together with the unique name assumption this implies that individuals of the legacy configuration and new individuals introduced by the reconfiguration problem are disjunct.
Reconfigurations are defined analog to configurations as a finite subset of Herbrand-models.
a reconfiguration problem instance RCI = hhREQR; PRi; S; Ti iff there is a Herbrand-model M 2 HM(REQR [ S [ T) and R is the set of all the elements of M whose predicate symbols are in PR and R is finite.
R is an optimal reconfiguration for RCI iff R is a reconfiguration for RCI and there is no reconfiguration R0 of RCI s.t. g(S; R0) < g(S; R).
Reconfiguration problems are formulated analog to configuration problems.
of reconfiguration problems are defined by a tuple hhREQR; PRi; S; Ti and objective functions g( ; ). Decision problem: Given a set of atoms R. Decide if R is a reconfiguration for a reconfiguration problem instance. Generation (optimization) problem: Generate a set of atoms R s.t. R is a reconfiguration (an optimal reconfiguration) for a reconfiguration problem instance.
Because we can reduce configuration problems to reconfiguration problems and vice versa the following property follows trivially.
Property 1 Employing a logical representation language for representing instances of configuration problems and reconfiguration problems whose satisfiability problem is at least NP-complete, generating a(n optimal) reconfiguration is as hard as generating a(n optimal) configuration w.r.t. computational complexity.
In the following we show typical formalization patterns and apply them to our example. The set of atoms flegacyConfig(a)ja 2 Sg describes the atoms of the legacy configuration S. Note, the definition of reconfiguration problems does not employ first-order logic constructs in order to avoid unnecessary restrictions. However, to facilitate a concise description of the problem we introduce the predicate legacyConfig=1 to allow quantification over the elements of the legacy configuration. Note, we could rewrite all shown axioms to propositional logic.
For the transformation sentences T we employ the following general patterns. For reusing parts of the legacy configuration the problem solver has to make the decision either to reuse or to delete. This is expressed by reuse(a) and delete(a) atoms where a is an element of S. For each atom a in S either reuse(a) or delete(a) must hold. Based on these atoms additional configuration constraints can be defined which describe the proper reuse or deletion of a part of the legacy configuration represented by atom a. In our case, reusing an atom a of the legacy configuration implies the assertion of this atom, whereas deletion requires that the atom is not asserted. In addition, costs are associated to each reuse(a) or delete(a) operation. This is expressed by the atom cost(reuse(a); w) or cost(delete(a); w) where a is an element of S and w is an integer specifying the corresponding costs. Furthermore, we require that in each model which contains reuse(a) or delete(a) also cost(reuse(a); w) or cost(delete(a); w) is contained in order to have defined reuse or deletion costs. The conjunctions (X; Y ; W ) and (X; Y ; W ) are employed to define case specific costs.
For each p 2 PS include the following axioms in T: 1freuse(p(X)); delete(p(X))g1 p(X)
reuse(p(X)): p(X); delete(p(X)): legacyConfig(p(X)): cost(reuse(p(X)); W)
reuse(p(X)); (X; Y; W): cost(delete(p(X)); W)
delete(p(X)); (X; Y; W):
Analog to configuration problems, we require each individual contained in a reconfiguration to be a member of exactly one bounded type. Consequently, individuals of the legacy configuration have to be a member of the domain pDomain(X) of a bounded type p of hREQR; PRi, because these individuals can be part of a reconfiguration through reuse. I.e. there are rules of the form pDomain(X)
legacyConfig(q(: : : ; X; : : :)): where q is predicate symbol of the solution schema of the legacy configuration.
As for configuration problems, the number of individuals of a bounded type p is limited. For every bounded type p we add the following axioms: pLowerfp(X) : pDomain(X)gpUpper: However, the two other rules for bounded types are changed. In particular, we have to adapt the symmetry breaking pattern of configurations. The reason is that there are two different types of individuals contained in pDomain, those which are reused and those which are newly generated. Symmetry breaking does not apply to the reused individuals because they may be linked to other reused individuals. Therefore, exchanging these individuals potentially leads to different configurations. However, the newly generated individuals are interchangeable. We describe them by pDomainNew=1 for the bounded type p. We use pNewOffset to generate new identifiers. I.e. the pattern is pDomainNew(pNewOffset + 1 :: pNewOffset + pUpper): pDomain(X)
pDomainNew(X): p(X)
pDomainNew(X); pDomainNew(Y); p(Y); X < Y:
In our example, the reconfiguration problem consists of
additional customer and configuration requirements described
in Section 2. The solution schema for the reconfiguration
problem is an extension of the solution schema of the original
configuration problem by cabinetHigh/1, cabinetSmall/1,
thingLong/1 and thingShort/1 predicates. The additional
requirements of the customer are expressed by:
thingLong(3). thingShort(4). thingShort(5).
thingShort(
To implement the configuration requirements of the modified problem we add rules defining the subtypes of cabinets as well as that long things have to be stored in high cabinets. Note, only some of the usual rules for expressing subtypes are needed. Regarding subtypes of thing, no rules are needed at all because for every thing fact either a thingLong fact or a thingShort fact is contained in the customer requirements and none of these predicates appear in the head of a rule. 1{cabinetHigh(X), cabinetSmall(X)}1 :- cabinet(X). cabinetHigh(C) :- thingLong(X), cabinetTOthing(C,X). Moreover, each high cabinet requires more space in a room. Such a cabinet occupies two of the four available slots in a room, whereas a small cabinet uses only one slot. Note, the last constraint does not allow an answer set where the sum of occupied slots in a room is 5 or more. cabinetSize(X,1) :- cabinet(X), cabinetSmall(X). cabinetSize(X,2) :- cabinet(X), cabinetHigh(X). roomTOcabinetSlot(R,C,S) :- roomTOcabinet(R,C), cabinetSize(C,S). :- 5 [roomTOcabinetSlot(X,Y,S):
cabinetDomain(Y)=S], room(X).
The domains of cabinets and rooms are extended with additional individuals that might be required in a new configuration. The number of new elements in the cabinet and room domains corresponds to the number of things in the modified problem. The upper number pUpper of both cabinet and room individuals is set to 7 because 7 things must be stored in the house. cabinetDomainNew(22..28). cabinetDomain(X) :- cabinetDomainNew(X). 2{cabinet(X):cabinetDomain(X)}7. cabinet(X) :- cabinetDomainNew(X), cabinet(Y), X<Y, cabinetDomainNew(Y).
The modeling of new rooms is done in the same way.
The transformation rules are implemented as described above. E.g. 1{reuse(cabinet(X)), delete(cabinet(X))}1 :legacyConfig(cabinet(X)). cabinetDomain(X) :- legacyConfig(cabinet(X)). However, the transformation rules for legacyConfig(person(X)), legacyConfig(thing(X)) and legacyConfig(personTOthing(X,Y)) could be deleted because facts about persons, things and their relations are given as requirements. Deleting such an atom results in a contradiction.
Given the reconfiguration program the solver identifies a reconfiguration as well as a set of actions required to transform the legacy configuration into a new one.
For generating optimal reconfigurations we formulate a cost model. The minimization statement in the reconfiguration problem is the same as in the configuration. In our reconfiguration example the costs for creation of new high/small cabinets and rooms cost(create(a); w) correspond to the costs definition of the configuration problem. To obtain a reconfiguration scenario with the minimal costs of required actions we extend the costs rules described above with costs for creation of new high/small cabinet and room individuals as well as with costs for newly created relations. E.g. cost(create(cabinetHigh(X)),W) :- cabinetHigh(X), cabinetHighCost(W), cabinetDomainNew(X).
Rules for deducing the costs of reuse and deletion are formulated as described above.
For our example let us assume that the customer sets all deletion costs to 2, whereas reusing has no costs except for cabinets, which could be altered to high in a reconfiguration. The costs of this alteration is set to 3. Creation costs of new high and small cabinets are set to 10 and 5 respectively. Finally, the costs of a new room is set to 5. Creation of relations between individuals is for free. Given these costs assignments the solver is able to find a set of optimal reconfigurations including the one presented in Figure 3.
Modification of the costs results into different optimal reconfigurations. Let us assume the sales-department changes both the costs of deletion of a cabinet and the costs of increasing the height of a cabinet to 10, and decreases the creation costs of new high and small cabinets to 2 and 1 respectively. In this case the solutions returned by a solver will include the one presented in Figure 4. Given their simplicity, the presented optimal solutions were found in milliseconds. 8
The evaluation of our approach was done on a set of test cases derived from four reconfiguration scenarios encountered by us in practice. Each scenario can be represented as an instance of the (re)configuration problem presented in Section 2. In the empty reconfiguration scenario the legacy configuration is empty and the customer requirements contain sets of things and persons owning 5 things each. Every thing is labeled as short. The reconfiguration process should create missing cabinets, rooms as well as all required relations.
The customer requirements of the long scenario specify that each given person owns 15 things. The legacy configuration contains a set of relations that indicate placement of these things into cabinets, s.t. all things of one person are stored in three cabinets that are placed in one room. The customer also requires 5 things of each person to be labeled as long whereas the remaining 10 as short. The goal of the reconfiguration is to find a valid rearrangement of long things to reused or newly created high cabinets.
The next new room scenario models a situation when new rooms have to be created and some of the cabinets reallocated. In this scenario each person owns 12 things. These things are stored in 3 cabinets placed in one room as indicated by the legacy configuration. In the reconfiguration problem the customer requirements declare 6 of the 12 things as long.
The last scenario, swap, describes a situation when the customer requirements include only one person, who owns 35 things. In the legacy configuration the things are placed in 3 cabinets in the first room and in 4 cabinets in the second room. Moreover, one of the things in the second room is labeled as high in the customer requirements. Given the costs schema presented above, the solution corresponds to a rearrangement of the cabinets in the rooms such that a high cabinet can be placed in one of these rooms. All these scenarios can be easily scaled by increasing the number of things. The number of persons in the empty, long and new room scenarios can always be computed given the number of things.
Experiments were performed using Potassco 3.0.3 on Core2 Duo 3Ghz with 4Gb RAM. In our experiments we con0,01 29 empty long newroom swap suboptimal s olutio ns no solutio ns sidered only creation costs for newly generated cabinets and rooms because these are the dominant costs for our application domain. The performance of the reconfiguration process is presented in Figure 5. Potassco was able to find optimal solutions within 600 seconds for all instances of the new room and swap scenarios. Optimal solutions were also found for small and mid-size instances of the empty scenario. For all other instances at least one suboptimal solution was found. The long scenario included the hardest problems. The solver did not find any solutions for one of them in 600 seconds. This was the only unsolved problem instance in the whole experiment. Because the solved instances are comparable to real world applications based on our experiences, we consider the proposed reconfiguration method as feasible for a practically interesting set of reconfiguration problem instances. 9
The existing approaches for reconfiguration can be separated into revision-based [7; 10] and model-based [11]. The revision-based approaches employ a knowledge base describing “fixes”, i.e. reconfiguration operations and configuration invariants [7]. A solution requires that there is a sequence of operations which transform the legacy configuration into a new configuration. The approach of [11] views reconfiguration as a consistency-maintenance (diagnosis) problem, where a solution corresponds to a consistent set of assumptions s.t. requirements are implied. Similarly, our approach can be seen as searching for a consistent (optimal) set of assumptions regarding reuse or deletion of parts of the legacy configuration and creation of new parts. This search is provided by the ASP reasoning system, implementing a correct and complete problem solving method. No additional diagnosis component is required. Regarding the revision-based approach, our domains do not need the computation of sequences of operations, because if a reconfiguration is found, a sequence of real-world change operations can be easily derived. Thus, we can avoid the additional combinatorial explosion introduced by permutations of change operations. However, we can view our approach as a form of the revisionbased method assuming that all change operations are executed simultaneously. The effects of these operations and the combination of allowed operations are described by the transformation knowledge. Thus we can model complex “fix” operations which involve the reuse of several parts of the legacy configuration and which have multiple effects such as creating new parts or deleting existing ones.
To sum up, we have developed a method which allows the modeling of reconfiguration problems based on legacy configurations, transformation knowledge, and a new configuration problem instance. We showed various modeling patterns and implemented the approach based on ASP. Evaluation results show the feasibility for practical applications.