Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich 55 Solving Object-oriented Configuration Scenarios with ASP ∗ Gottfried Schenner and Andreas Falkner Anna Ryabokon and Gerhard Friedrich Siemens AG Österreich, Vienna, Austria Universität Klagenfurt, Austria gottfried.schenner@siemens.com anna.ryabokon@aau.at andreas.a.falkner@siemens.com gerhard.friedrich@aau.at Abstract technical systems with a long life-span, where parts of exist- ing configurations have to be adapted continuously. The main configuration scenarios occurring in the Reconfiguration is especially challenging if an existing domain of technical products and systems are con- system has to be extended with new functionality that was not sistency checking, completing a partial configura- part of the original system design. In this case, some relations tion, reconfiguration of an inconsistent configura- between new and existing components have to be created or tion and finding the best knowledge base for fu- some of the existing relations have to be changed in order ture reconfigurations. This paper presents OOASP to meet modified configuration requirements. [Falkner and - a framework for the description of object-oriented Haselböck, 2013] discuss typical problems occurring when product configurators using answer set program- configuration requirements are changed. Finding the best de- ming and shows that it is able to solve the differ- sign for future configurations is an important task for the re- ent (re)configuration scenarios occurring in prac- configuration scenario since it allows to reduce costs during tice. Thus, it is a step forward to close the concep- the production process. tual gap between logic-based and object-oriented In the current paper we present a generic configurator approaches for product configuration. which uses an object-oriented approach to encode its knowl- edge base. In order to compute configurations the sys- 1 Introduction tem uses answer set programming (ASP). We illustrate the mapping from an object-oriented formalism (UML) to logi- A configurator is a software system that enables the user cal descriptions using a simplified real-world example from to design complex technical systems or services based on a Siemens. Additionally, the paper provides different insights predefined set of components. In modern configuration sys- on (re)configuration scenarios such as checking and com- tems, domain knowledge - comprising configuration require- pleting a configuration, reconciliation and choosing the best ments (product variability) and customer requirements - is ex- knowledge base for reconciliation. Finally, we discuss chal- pressed in terms of component types and relations between lenges which frequently occur in practice and should be taken them. Each type is characterized by a set of attributes which into account while solving (re)configuration problems. specify the functional and technical properties of real-world The remainder of this paper is organized as follows: In Sec- and abstract components of the configurable product. An at- tion 2 we introduce a sample configuration problem used as tribute takes values from within a predefined domain. Fur- example throughout the paper. After an ASP overview in Sec- thermore, components are related/connected to each other in tion 3, we describe in Section 4 how object-oriented knowl- various ways. Each component type has a number of ports edge bases can be specified using ASP. In Section 5 various which allow to connect a component of that type with other product configuration scenarios are discussed. Section 6 pro- components. A possible connection between two component vides some evaluation details and in Section 7 we conclude. types is modeled as a relation and its cardinality expresses the number of components that can be connected to a port. In most cases, modeling languages used in configuration allow 2 Configuration example to specify relations of the following types: classification (is- Modules example is a simple hardware configuration prob- a), composition (part-of), association (user defined relations). lem. Figure 1 shows the configurable objects of the example For simple customer products, a configuration system aims domain in a UML diagram: hardware frames contain up to at finding a consistent and complete configuration for a given five modules of various types (A, B) and elements of various set of customer requirements and reconfiguration is seldom types are assigned to the modules (one by one). Additionally an issue. Reconfiguration occurs during the maintenance of to the cardinality constraints implied by the UML diagram ∗ there are the following domain-specific constraints: This work has been developed within the scope of the project RECONCILE (reconciling legacy instances with changed ontolo- • Elements of type ElementA require a module of type gies) and was funded by FFG FIT-IT (grant number 825071). ModuleA Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria 56 Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich the literal a is the head of the rule and the conjunction b1 , . . . , bm , not c1 , . . . , not ck is the body. A rule with an empty head, standing for false, is called an integrity constraint, i.e. every interpretation that satisfies the body of the constraint is not an answer set (configuration solution). A rule with an empty body is called a fact. Rule (1) derives that the atom a in the head of the rule is true if all literals of the body are true, i.e. there is a derivation for each positive literal b1 , . . . , bm whereas none of the atoms of the negative literals not c1 , . . . , not ck can be derived. Processing of a general ASP program P , in which atoms can contain variables, is done in two stages [Brewka et al., 2011]. First the program is grounded, i.e. P is re- placed by a possibly small equivalent propositional program grnd(P ) in which all atoms are variable-free. In the sec- ond stage an ASP solver is used to identify answer sets. Following the definition of configuration problems based on logical descriptions, presented in [Soininen et al., 2001; Felfernig et al., 2004], each configuration is a subset of a fi- Figure 1: UML diagram for the modules example nite Herbrand-model. Given the stable model semantics used in ASP, a Herbrand interpretation I is a model of a program P • Elements of type ElementB require a module of type iff (a) it satisfies all the rules in P , (b) for every atom ai ∈ I ModuleB there exists a justification based on given facts and (c) I is minimal under set inclusion among all (consistent) interpre- • The position of the modules of a frame must be unique tations. In a typical configurator scenario for this domain, a user cre- In this paper we use an ASP dialect implemented in ates a partial configuration consisting of elements of different Gringo [Gebser et al., 2011]1 which includes a number of ex- types. Then the configurator extends the configuration by cre- tensions simplifying the presentation of the programs. Thus, ating missing modules for the elements and by creating miss- it allows definition of weight constraints which are defined ing frames and assigning the modules to them. If the user ma- as l[a1 = w1 , . . . , an = wn ]u where ai are atoms, wi are weights nipulates a completed configuration, for instance by adding or of the atoms and l, u are integers specifying lower and upper removing elements, the configurator can restore consistency bounds. Such constraints allow declaration of choices, i.e. through reconfiguration, usually by keeping as much of the such number of atoms from the set {a1 , . . . , an } must be true existing structure of the configured system as possible. that the sum of corresponding weights is between l and u. If the lower or upper bounds are missing, then the ASP grounder 3 Answer set programming overview substitutes l = 0 and u = n, where n is the sum of the weights of all atoms in the set. A special case of the weight con- Answer set programming is an approach to declarative prob- straints are cardinality constraints where each weight wi = 1. lem solving which has its roots in logic programming and Cardinality constraints are denoted by curly brackets. deductive databases. It is a decidable fragment of first-order ASP dialects include operators that are used for generating logic interpreted under stable model semantics and extended sets of atoms: The range operator (“..”) is used to generate a with default negation, aggregation, and optimization. ASP al- set of atoms such that each atom includes one of the integer lows modeling of a variety of (combinatorial) search and op- constants from a given range of integers. The generate oper- timization problems in a declarative way using model-based ator (“:”) is used in weight constraints to create sets of atoms problem specification methodology (see e.g. [Gelfond and used in it. Lifschitz, 1988; Eiter et al., 2009; Brewka et al., 2011] for details). ASP has a long history of being used for product configuration [Soininen and Niemel, 1998]. Example Assume that we want to encode a simple problem An ASP program is a finite set of rules of the form: instance of the modules example including two frames with ids 1 and 2, and six modules with ids ranging from 10 to 15. a :- b1 , . . . , bm , not c1 , . . . , not ck . (1) These customer requirements can be represented as facts: where a, bi , and cj are atoms of the form frame(1..2). module(10..15). predicate(term1 , . . . , termn ). A term is either a variable or a The relation between modules and frames, i.e. that each mod- constant. ule must be placed in exactly one frame, is encoded using a In most of ASP languages, variables are denoted by strings choice rule: starting with uppercase letters and constants as well as pred- icates by strings starting with lower case letters. An atom 1{mod2fr(X,Y) : frame(Y)}1 :- module(X). together with its negation is called literal, e.g. a is a 1 positive and not a is a negative literal. In the rule (1), Potassco ASP suite: http://potassco.sourceforge.net Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich 57 When the rule above is grounded, the grounder generates six • Defines an inheritance hierarchy of classes. Although rules - one for each module. E.g., for module 10 it outputs: other interpretations are possible, in this paper the inher- 1{mod2fr(10,1), mod2fr(10,2)}1 :- module(10). itance hierarchy is assumed to be a tree (single inheri- tance). In order to allow at most five modules to be put in a frame we add the following cardinality constraint to our program: ooasp_assoc(KBID,ASSOCID, CID1,C1MIN,C1MAX,CID2,C2MIN,C2MAX) :- frame(X), 6 {mod2fr(Y,X) : module(Y)}. • Defines the association between classes CID1 and CID2 Due to the cardinality constraint every configuration (answer within given cardinalities, i.e. for every instance of set) containing a frame with more than 5 modules will be CID1 there exist at least C2MIN and at most C2MAX eliminated. instances of CID2 in the association and vice versa. Identification of the preferred configuration solution can be done using the built-in optimization functionality of ASP ooasp_attribute(KBID,CID,ATTRID, solvers. In the ASP dialect used in this paper, the optimiza- {"string","integer","boolean"}) tion is defined on a weighted set of true atoms and indicated • Defines an attribute for the class CID with the given via #minimize or #maximize statements. type. 4 OOASP framework ooasp_attribute_minInclusive(KBID,CID, ATTRID,MINVALUE) OOASP2 is a framework for describing object-oriented knowledge bases in ASP. A knowledge base consists of the • Defines an optional minimum value for integer attributes object model of the configurator and additional constraints ooasp_attribute_maxInclusive(KBID,CID, which a valid configuration must satisfy. It is assumed that ATTRID,MAXVALUE) the object model of the object-oriented configurator can be described by an UML class diagram [Rumbaugh et al., 2005]. • Defines an optional maximum value for integer at- The structure of a knowledge base and configurations are de- tributes scribed by special ASP facts. This fact-based language can ooasp_attribute_enum(KBID,CID, be seen as a domain specific language (DSL) for defining ATTRID,ENUMVALUE) object-oriented knowledge bases and configurations on top • Defines an enum-value (a possible value) for a string at- of ASP. The DSL can represent multiple configurator knowl- tribute. edge bases and solutions in one ASP program. The OOASP framework provides a default implementation for the DSL, The mentioned predicates are sufficient to describe the e.g. the interpretation of the fact-based language, in several object-model of a simple object-oriented configurator. Many program packages (*.lp files). If advanced features (such features which can be additionally found in object-oriented as multiple inheritance, automatic symmetry breaking) are systems such as initial values, constants, multi-valued at- required, the default implementation must be replaced with tributes, ordered associations, etc. are currently missing in the alternative implementations, whereas the OOASP-DSL can framework, but these features are not relevant to the demon- stay the same. The OOASP-DSL is largely independent of stration of the configuration scenarios presented in the paper. special ASP features and can therefore be easily translated to In practice, especially ordered associations and initial values other formalisms (OWL/RDF, UML, etc.). are a convenient feature of object oriented product configura- tors. 4.1 Defining the knowledge base The knowledge base comprises an object-model describing Example The OOASP-DSL representation for the modules types of available components and possible relations between example corresponds to the following set of facts: them. In addition, it can include a number of constraints % modules example kb "v1" on types and relations. To define the object-model of the % classes configurator with the OOASP-DSL, the following predicates ooasp_class("v1","ConfigObject"). are used where all IDs are considered to be unique within a ooasp_class("v1","Frame"). knowledge base. ooasp_class("v1","Module"). ooasp_class(KBID,CID) ooasp_class("v1","ModuleA"). ooasp_class("v1","ModuleB"). • Defines a class in the knowledge base KBID 3 . ooasp_class("v1","Element"). KBID is an id for a knowledge base and CID is an id for ooasp_class("v1","ElementA"). a class within the given knowledge base. ooasp_class("v1","ElementB"). ooasp_subclass(KBID,CID,SUPERCID) % class inheritance ooasp_subclass("v1","Frame","ConfigObject"). 2 The ASP code for OOASP is available upon request from the ooasp_subclass("v1","Module","ConfigObject"). first author ooasp_subclass("v1","Element","ConfigObject"). 3 To allow uppercase names, OOASP identifiers are strings, not ooasp_subclass("v1","ElementA","Element"). constants ooasp_subclass("v1","ElementB","Element"). Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria 58 Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich ooasp_subclass("v1","ModuleA","Module"). 4.3 Defining constraints ooasp_subclass("v1","ModuleB","Module"). There are two different kinds of constraints in OOASP: in- % attributes and associations tegrity constraints and domain-specific constraints. Both are % class Frame implemented as ASP rules which derive an atom ooasp_cv ooasp_assoc("v1","Frame_modules", (head) for each constraint violation expressed in the body. "Frame",1,1, The derived atom can be used for explanations. "Module",0,5). Integrity constraints are generic constraints derived from the object model of the knowledge base. Implementations of % class Module integrity constraints are provided by the OOASP framework ooasp_attribute("v1","Module","position","integer"). in program package ooasp check.lp, e.g. for the constraint ooasp_attribute_minInclusive("v1", which checks the minimal cardinality of associations: "Module","position",1). ooasp_attribute_maxInclusive("v1", % Derive ooasp_cv(CONF,mincardviolated(ID1,ASSOC)) "Module","position",5). % whenever there are less objects associated % with object ID1 than allowed by the cardinality % class Element % restriction of the association ooasp_assoc("v1","Element_module", ooasp_cv(CONF,mincardviolated(ID1,ASSOC)) :- "Element",1,1, { ooasp_associated(CONF,ASSOC,ID1,ID2): "Module",1,1). ooasp_isa(CONF,C2,ID2) } C2MIN-1, C2MIN>0, 4.2 Defining a configuration ooasp_isa(CONF,C1,ID1), A (partial) configuration is an instantiation of the object- ooasp_assoc(KBID,ASSOC, model. A valid configuration is a configuration where no C1,C1MIN,C1MAX,C2,C2MIN,C2MAX), constraint is violated. It represents a buildable artifact of the ooasp_configuration(KBID,CONF). configured system. In addition to the integrity constraints, a knowledge engi- As with knowledge-bases, OOASP allows the representa- neer can define domain-specific constraints for a knowledge tions of multiple configurations within one ASP program. We base. These are constraints that can not be derived automati- use the following predicates to define a (partial) configura- cally from the knowledge base. tion: ooasp_configuration(KBID, CONFIGID) Example The first of the constraints in the modules exam- • Declares that the configuration CONFIGID belongs to ples may be implemented as follows: the knowledge base KBID. Every configuration has a unique ID and belongs to exactly one knowledge base. % ElementA requires ModuleA ooasp_cv(CONF,wrongModuleType(E,M)) :- ooasp_isa(CONFIGID, CID, OBJECTID) ooasp_configuration("v1",CONF), • The object with the id OBJECTID is an instance of the ooasp_associated(CONF,"Element_module",E,M), class CID in the configuration CONFIGID. If an object ooasp_isa(CONF,"ElementA",E), is an instance of a class, it must also be an instance of not ooasp_isa(CONF,"ModuleA",M). one of its leaf classes (i.e. class without subclasses). ooasp_associated(CONFIGID,ASSOCID, 5 Product Configuration Scenarios OBJECTID1,OBJECTID2) This section describes some of the typical scenarios for an • The objects with the OBJECTID1 and OBJECTID2 are object-oriented product configurator. associated in the association ASSOCID in the configu- ration CONFIGID. 5.1 Checking a Configuration ooasp_attribute_value(CONFIGID,ATTRID, Checking a (partial) configuration evaluates the integrity OBJECTID,VALUE) constraints of the knowledge base and the domain-specific • The attribute ATTRID of the object OBJECTID has the constraints for a configuration under closed world assump- value VALUE in the configuration CONFIGID. tion, i.e. during the checking no new objects are instantiated. In an interactive configurator, checking the current config- Example The following configuration consisting of one uration highlights the parts of the configuration that need to frame, one module, and one element is not valid. It would be changed by a user. be valid if the module 10 was a ModuleB. ooasp_configuration("v1","c1"). Example Checking the minimal configuration consisting of ooasp_isa("c1","Frame",1). only one element of type A ooasp_isa("c1","ModuleA",10). ooasp_attribute_value("c1","position",10,5). ooasp_isa("c2","ElementA",10). ooasp_isa("c1","ElementB",20). ooasp_associated("c1","Frame_modules",1,10). will derive a cardinality violation ooasp_associated("c1","Element_module",20,10). ooasp_cv("c2",mincardviolated(10,"Element_module")). Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich 59 • The object with the OBJID can be instantiated to one of the leaf-classes of class CID. The ooasp_domain facts define the available object IDs for a configuration. The object IDs are unique within a con- figuration. Every object ID can represent one instance of a leaf-class. However, the classes used in the ooasp_domain predicates can be non-leaf-classes as well. Therefore, the number of ooasp_domain facts for each class CID is equal to the maximal number of its instances in the configura- tion CONFIGID. From the ooasp_domain facts the possi- ble types of every object ID in a configuration are derived (ooasp_canbe), searching up and down the class hierarchy (see (1) in Figure 4). The ooasp_isa facts (2) are derived upwards only. This approach of controlling instantiation is Figure 2: Checking a configuration similar to the notion of a scope in Alloy [Jackson, 2011]. for the association between element and module, indicating Example ooasp_domain("c3","Module",20) allows that there must be a module for the element with OBJECTID the object with OBJECTID 20 to become either a ModuleA 10. or a ModuleB but not Frame. In a second step it may be The constraint violations derived during checking can also set explicitly to be a ModuleA. Figure 4 shows the derived guide a repair-based solver to repair the current configuration information after the object has been instantiated this way. [Falkner et al., 2011]. If checking does not find any con- straint violation, the current configuration is valid. The pro- cess of checking a configuration within OOASP framework is depicted in Figure 2. 5.2 Completing a Configuration Given a possible empty (partial) configuration, find an ex- tension of the configuration that satisfies all constraints. No fact of the given configuration may be removed. If no such extension can be found, the current configuration is either in- consistent or there is no valid configuration with the given upper bounds for object instances. Completing a configuration can be accomplished by enu- merating all possible extensions of the given configuration until a valid configuration is found. Figure 3 shows the nec- Figure 4: Controlling instantiation essary program packages for completing a configuration. The enumeration of all possible configurations is accom- plished by instantiating objects and setting associations and attributes. The default implementation for instantiating ob- jects is done in program package ooasp config.lp: % instantiate objects 0 { ooasp_isa(CONF,LEAFCLASS,ID) : ooasp_leafclass(V,LEAFCLASS) : ooasp_canbe(CONF,LEAFCLASS,ID) } 1 :- ooasp_domain(CONF,C,ID), ooasp_configuration(V,CONF). This means that every object ID can become an instance of one of its possible leaf-class types. Associations are set in a similar matter. Every instance in the configuration can be associated with all other possible instances in the config- uration. Constraints ensure that only instantiated objects are Figure 3: Completing a configuration associated. % associate objects To enumerate all possible configurations one has to instan- C2MIN { ooasp_associated(CONF,ASSOC,ID1,ID2): tiate objects according to customer requirements. The num- ooasp_canbe(CONF,C2,ID2) } :- ooasp_isa(CONF,C1,ID1), ber of the possible instances is controlled by the predicate ooasp_assoc(V,ASSOC,C1,C1MIN,C1MAX,C2,C2MIN,C2MAX), ooasp_domain(CONFIGID, CID, OBJID) ooasp_configuration(V,CONF). Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria 60 Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich % type check - only use instantiated objects :- ooasp_associated(CONFIG,ASSOC,ID1,ID2), not ooasp_isa(CONFIG,C2,ID2), ooasp_assoc(V,ASSOC,C1,C1MIN,C1MAX,C2,C2MIN,C2MAX), ooasp_configuration(V,CONFIG). Finally, there must be a generating rule for all possible val- ues of the attributes of an object. The following shows the generating rule for integer attributes. % set attribute values for integer attributes 1 { ooasp_attribute_value(CONFIG,N,ID,VALUE): VALUE=MIN..MAX } 1 :- ooasp_attribute(V,C,N,T), ooasp_isa(CONFIG,C,ID), Figure 6: Reconcile a configuration ooasp_attribute_minInclusive(V,C,N,MIN), ooasp_attribute_maxInclusive(V,C,N,MAX), ooasp_configuration(V,CONFIG). link between two objects in the legacy configuration or re- moves it. Reconciliation is controlled by the following pred- Example Figure 5 shows a completed configuration for icates: the partial configuration c3 below. It contains three in- stances of ElementA and two instances of ElementB. Note ooasp_reconcile(LEGACY,RECONCILED) that ooasp_isa is given as customer requirement only for those elements. For modules, only the ooasp_domain is • Activates reconciliation from configuration LEGACY to given and only 5 of the available 10 IDs are used in the com- the configuration RECONCILED pleted configuration. ooasp_cost_instance(KB,CID,ADD,REMOVE) % Partial configuration ooasp_configuration("v1","c3"). • Defines the costs for adding and removing instances of ooasp_domain("c3","Frame",1). class CID ooasp_domain("c3","ElementA",10..12). ooasp_isa("c3","ElementA",10..12). ooasp_cost_assoc(KB,ASSOC,ADD,REMOVE) ooasp_domain("c3","ElementB",13..14). ooasp_isa("c3","ElementB",13..14). • Defines the costs for adding and removing a link to/from ooasp_domain("c3","Module",20..29). the association ASSOC ooasp_cost_attribute(KB,ATTR,COST) • Defines the cost for changing attribute ATTR ooasp_rcost(CHANGEOFLEGACYCONFIGURATION,COST) • For every modification of the legacy configuration an ooasp_rcost atom is derived, defining the COST of the modification. The best reconciliation is the one that min- imizes the overall cost of the ooasp_rcost atoms, i.e. #minimize[ooasp_rcost(CHANGE,COST)=COST]. The following listing shows the implementation of the rules for reconciling associations: Figure 5: Complete configuration for the modules example % either reuse link or remove it: % ooasp_remove_associated is derived, % if a link is removed 5.3 Reconciliation 1 { ooasp_associated(RECONCILED,ASSOC,ID1,ID2), Given a complete legacy configuration and the changed ooasp_remove_associated(RECONCILED,ASSOC, knowledge base which makes the configuration invalid, find ID1,ID2) } 1 :- a new valid configuration that is close to the legacy configu- ooasp_associated(LEGACY,ASSOC,ID1,ID2), ooasp_reconcile(LEGACY,RECONCILED). ration. Reconciliation of a configuration is illustrated in Figure 6. % derive the reconfiguration costs OOASP uses the same cost-based reconciliation approach as % ooasp_rcost contains the overall costs described in [Friedrich et al., 2011]. For every change in the ooasp_rcost(ooasp_remove_assoc(ID1,ID2),REMOVE) :- legacy configuration, a cost can be defined. This allows a fine ooasp_remove_associated(RECONCILED,ASSOC,ID1,ID2), control over the reconfiguration process. The optimal recon- ooasp_cost_assoc(KB,ASSOC,ADD,REMOVE), ciliation is the reconfiguration that minimizes the costs. For ooasp_configuration(KB,RECONCILED), example, the rule for reconciling associations either keeps the ooasp_reconcile(LEGACY,RECONCILED). Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich 61 Example Suppose after the first systems of our example do- main have been built, there is evidence of a previously un- known overheating problem if two modules of type A are put next to each other in a frame. Thus, to prevent overheating we have to add a new constraint to the knowledge base that disallows putting two modules of type A next to each other. % do not put 2 modules of type moduleA % next to each other ooasp_cv(CONF,moduleANextToOther(M1,M2,P1,P2)):- ooasp_configuration("v2",CONF), ooasp_associated(CONF,"Frame_modules",F,M1), ooasp_associated(CONF,"Frame_modules",F,M2), ooasp_attribute_value(CONF,"position",M1,P1), ooasp_attribute_value(CONF,"position",M2,P2), Figure 8: Reconciled configuration with the module of type M1!=M2, ANEW ooasp_isa(CONF,"ModuleA",M1), ooasp_isa(CONF,"ModuleA",M2), Reconcilation in the alternative knowledge base consists in P2=P1+1. replacing modules of type A with modules of type ANEW, but no rearranging is necessary. The result is shown in Fig- ure 8. If modules of type A can be used together with type ANEW then it is sufficient to just replace module A 21 with module ANEW 31. Which technical solution shall be chosen? To answer this question one has to find the affected configurations. With a framework like OOASP, the effected legacy configurations (i.e. deployed systems which must be reconfigured) can be computed by checking the constraint representing the new technical requirement in all available legacy configurations. Note that legacy configurations may use earlier versions of the knowledge base. In this case the legacy configurations must be upgraded to the current version of the knowledge Figure 7: Reconciled configuration for the modules example base or the constraint must be expressed in terms of the legacy knowledge bases. Because of the added constraint the legacy configuration in Using the reconcile scenario one can compute how costly it Figure 5 is no longer valid. Using reconciliation with equal would be to modify the existing legacy configurations to the costs for all changes to the configuration results in the new available technical solutions. configuration shown in Figure 7. The cost for new systems can be estimated by computing the configuration cost of existing legacy systems, i.e. how 5.4 Choosing the best knowledge base for costly it would have been to build these systems from scratch reconciliation with the new knowledge bases. This can be computed by Given a new technical requirement and N knowledge bases a configurator using the initial (partial) configuration, i.e. the satisfying that requirement, choose the knowledge base that customer requirements and completing the configuration with minimizes the costs for reconciling legacy configurations and the new knowledge base. the estimated costs for building a new system and maintaining The costs for future reconciliations are hard to compute in existing systems. general, unless there is some knowledge about the future re- Note that the costs for maintaining systems may also con- quirements. Otherwise, one has to estimate how often the tain the costs for future reconciliations. Often there are many critical constellations will occur. By concentrating on the different technical solutions satisfying new requirements af- most probable reconcile scenarios of a product configurator, fecting existing systems. The choice of a technical solu- one can simulate these reconciliation scenarios using alterna- tion that minimizes the costs for reconciliation of the legacy tive knowledge bases and compare their costs. systems is an important problem to be solved. Given costs for various system modifications, we have to find a solution 6 Evaluation which corresponds to the most cost-effective reconciliation. The main purpose of OOASP is to demonstrate the behavior of an object-oriented configurator within a logical framework. Example A possible technical solution for the overheating Therefore, performance was not the main focus of this paper. modules is to avoid putting the modules next to each other. Since OOASP uses a similar approach as [Friedrich et al., Suppose there is an alternative technical solution replacing 2011], its performance is similar, too. module A with a new module ANEW, which does not have For checking configurations, the framework proved to be the overheating problem. able to handle more than 1000 components for integrity con- Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria 62 Gottfried Schenner, Andreas Falkner, Anna Ryabokon, Gerhard Friedrich straints and simple domain-specific constraints. Of course, [Eiter et al., 2009] Thomas Eiter, Giovambattista Ianni, and one can always come up with complex constraints, like find- Thomas Krennwallner. Answer set programming: A ing all paths in a graph, for which computation of logical primer. In Reasoning Web, pages 40–110, 2009. models is infeasible. [Falkner and Haselböck, 2013] Andreas Falkner and Alois Completing a configuration can be handled for problems Haselböck. Challenges of Knowledge Evolution in Prac- with hundreds of components. The main limiting factor tice. AI Communications, 26:3–14, 2013. here is the grounding size. The grounding explodes since the generic translation of UML to ASP rules of the default [Falkner et al., 2011] Andreas Falkner, Alois Haselböck, OOASP implementation associates every possible object of Gottfried Schenner, and Herwig Schreiner. Modeling and one related type with every other possible object of the other solving technical product configuration problems. Arti- type. The grounding of the module example with 200 objects ficial Intelligence for Engineering Design, Analysis and is already greater than 500 MB. One can reduce the ground- Manufacturing, 25:115–129, 2011. ing size by replacing the rules of the generic translation with [Felfernig et al., 2004] Alexander Felfernig, Gerhard special instantiation rules as follows: Friedrich, Dietmar Jannach, and Markus Stumptner. % associate objects Consistency-based diagnosis of configuration knowledge % special implementation bases. Artificial Intelligence, 152(2):213–234, 2004. % ’create’ a module for every element [Friedrich et al., 2011] Gerhard Friedrich, Anna Ryabokon, % at a fixed object ID Andreas A. Falkner, Alois Haselböck, Gottfried Schenner, 1 {ooasp_associated(CONF, and Herwig Schreiner. (Re)configuration based on model "Element_module", ID1,1000+ID1)} 1:- generation. In Conrad Drescher, Ins Lynce, and Ralf ooasp_isa(CONF,"Element",ID1), Treinen, editors, LoCoCo, volume 65 of EPTCS, pages ooasp_configuration(V,CONF). 26–35, 2011. This is similar to automatically generating subobjects in [Gebser et al., 2011] Martin Gebser, Benjamin Kaufmann, an object-oriented setting. However, these special rules can Roland Kaminski, Max Ostrowski, Torsten Schaub, and no longer be used for reconfiguration, because they assume Marius Thomas Schneider. Potassco: The Potsdam answer that for every element there is a unique module at a fixed ob- set solving collection. AI Communications, 24(2):105– ject ID. Another way to avoid the explosion of grounding size 124, 2011. would be to use a constraint-based model. Additional limit- [Gelfond and Lifschitz, 1988] Michael Gelfond and ing factor is the current lack of ASP to incorporate domain- Vladimir Lifschitz. The stable model semantics for specific heuristics into the solving, which is a topic of active logic programming. In 5th International Conference and research. Symposium on Logic Programming, pages 1070–1080, 1988. 7 Conclusions [Jackson, 2011] D. Jackson. Software Abstractions: Logic, This paper demonstrates the implementation of a small Language and Analysis. Mit Press, 2011. object-oriented product configurator on top of ASP. The [Rumbaugh et al., 2005] James Rumbaugh, Ivar Jacobson, framework contains a domain-specific language for specify- and Grady Booch. The Unified Modeling Language Refer- ing knowledge bases and configurations, that can be easily ence Manual. Addison-Wesley, 2 edition, 2005. translated to other formalisms (OWL/RDF, UML/Java). [Soininen and Niemel, 1998] Timo Soininen and Ilkka Evaluations showed that checking constraints relative to a given configuration can be done effectively. However, finding Niemel. Formalizing configuration knowledge using rules (re)configurations efficiently remains a challenge for large- with choices. In Seventh International Workshop On scale product configuration. The main obstacle for SAT- and Nonmonotonic Reasoning, 1998. ASP-based approaches seems to be the explosion of ground- [Soininen et al., 2001] Timo Soininen, Ilkka Niemelä, Juha ing. In addition, the identification of appropriate domain- Tiihonen, and Reijo Sulonen. Representing configuration specific heuristics is an open problem for all search-based knowledge with weight constraint rules. In 1st Interna- approaches. tional Workshop on Answer Set Programming: Towards By defining typical configuration scenarios we hope to Efficient and Scalable Knowledge, pages 195–201, 2001. raise awareness to often neglected aspects of product config- uration. We demonstrated the handling of these scenarios in ASP and are going to continue this work for other formalisms such as constraint programming, RDF/OWL, etc. References [Brewka et al., 2011] Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. Answer set programming at a glance. Communications of the ACM, 54(12):92–103, 2011. Michel Aldanondo and Andreas Falkner, Editors Proceedings of the 15th International Configuration Workshop August 29-30, 2013, Vienna, Austria