No CrossRef data available.
Configuration knowledge representations for Semantic Web applications
Published online by Cambridge University Press: 07 August 2003
Abstract
Today's economy exhibits a growing trend toward highly specialized solution providers cooperatively offering configurable products and services to their customers. This paradigm shift requires the extension of current standalone configuration technology with capabilities of knowledge sharing and distributed problem solving. In this context a standardized configuration knowledge representation language with formal semantics is needed in order to support knowledge interchange between different configuration environments. Languages such as Ontology Inference Layer (OIL) and DARPA Agent Markup Language (DAML+OIL) are based on such formal semantics (description logic) and are very popular for knowledge representation in the Semantic Web. In this paper we analyze the applicability of those languages with respect to configuration knowledge representation and discuss additional demands on expressivity. For joint configuration problem solving it is necessary to agree on a common problem definition. Therefore, we give a description logic based definition of a configuration problem and show its equivalence with existing consistency-based definitions, thus joining the two major streams in knowledge-based configuration (description logics and predicate logic/constraint based configuration).
Information
- Type
- Research Article
- Information
- Copyright
- © 2003 Cambridge University Press
1. INTRODUCTION
Knowledge-based configuration has a long history as a successful AI application area (e.g., Barker et al., 1989; Mittal & Frayman, 1989; Heinrich & Jüngst, 1991; Wright et al., 1993; Fleischanderl et al., 1998; Mailharro, 1998). Starting with rule-based systems such as R1/XCON (Barker et al., 1989), various higher level representation formalisms have been developed since the late 1980s to exploit the advantages of more concise representation, faster application development, higher maintainability, and more flexible reasoning. Although these representations have proven their applicability in various real-world applications, the heterogeneity of configuration knowledge representation is the major obstacle to incorporating configuration technology in E-commerce environments. The trend toward highly specialized solution providers results in a situation where different configurators of complex products and services must be integrated in order to transparently support distributed configuration problem solving. In such integration scenarios, configurators must share a clear and common understanding of the problem definition and the semantics of the exchanged knowledge. Consequently, it is necessary to agree on the definition of a configuration problem and its solution. Of the two current main streams in representing and solving configuration problems, the first approach is based on predicate logic or various simplified variants thereof, specifically constraint-based systems (including their dynamic and generative variants, e.g., Mittal & Falkenhainer, 1990; Fleischanderl et al., 1998; Mailharro, 1998) and resource balancing methods (e.g., Heinrich & Jüngst, 1991). The second approach uses description logics as knowledge representation and reasoning mechanism (e.g., Wright et al., 1993; McGuinness & Wright, 1998). Clearly, an integration of these approaches is a major milestone for the integration of configuration systems.
In order to map the predicate logic based representations into description logic based representations and vice versa, the definition of a common view of a configuration task is needed. A solution for the exchange of knowledge is the provision of a standardized configuration knowledge representation language, which is based on state of the art web technologies that allow easy integration of existing proprietary configuration environments if this common view can be obtained. Languages such as Ontology Inference Layer (OIL; Fensel et al., 2001b) or DARPA Agent Markup Language (DAML+OIL; VanHarmelen et al., 2001), which were developed in the context of the Semantic Web (Berners–Lee, 2000), are intended for designing and sharing ontologies. These languages are strongly influenced by description logics and therefore possess clear declarative semantics, an important precondition for the exchange of knowledge. A commonly accepted problem definition with formal semantics on this basis will offer a well-defined interface between configurator implementations and allow a joint provisioning of configuration services, a major step toward the integration goal identified above. Proprietary configuration systems can then be independently implemented following different approaches and still be able to interoperate. We only require that cooperating configurators deliver valid solutions with respect to the common definition of the problem and its solution.
In this paper we give a description logics based definition of a configuration task and show the equivalence of this definition with a consistency-based definition given in Felfernig et al. (2000b). The major result of this equivalence is that configuration tasks defined in terms of description logics and predicate logic can be easily transformed into each other and can consequently be represented in ontology representation languages such as OIL or DAML+OIL. Using concepts of OIL,1
For presentation purposes we employ OIL text throughout the paper, but this representation can be easily transformed into a corresponding DAML+OIL representation.
Note that these differ from the configuration ontology that was described for demonstration purposes in Gruber et al. (1996).
The rest of the paper is organized as follows. In Section 2 we introduce an example that provides an overview of representative modeling concepts required for building configuration knowledge bases. In Section 3 we give a description logic based definition of a configuration task and show its equivalence to the consistency-based definition given in Felfernig et al. (2000b). In Section 4 we describe an OIL-based as well as a corresponding predicate logic based formalization of the modeling concepts presented in Section 2. In Section 5 we summarize the results and analyze the expressiveness of available Semantic Web ontology representation languages with respect to their capability for configuration knowledge representation. In Section 6 the CAWICOMS3
CAWICOMS is the acronym for Customer-Adaptive Web Interface for the Configuration of Products and Services with Multiple Suppliers.
2. EXAMPLE CONFIGURATION KNOWLEDGE BASE
The Unified Modeling Language (UML; Rumbaugh et al., 1998) is the result of an integration of the object-oriented approaches of Rumbaugh et al. (1991), Jacobson et al. (1992), and Booch (1994), which is well established in industrial software development. UML is applicable throughout the whole software development process from the requirements analysis phase to the implementation phase. In order to allow the extension of the basic metamodel with domain-specific modeling concepts, UML provides the concept of profiles; the configuration domain–specific modeling concepts presented in the following are the constituting elements of a UML configuration profile. UML profiles can be compared with ontologies discussed in the artificial intelligence literature (e.g., Chandrasekaran et al., 1999, defines an ontology as a theory about the sorts of objects, properties of objects, and relationships between objects that are possible in a specified domain of knowledge).
For the following discussions, the simple UML configuration model shown in Figure 1 will serve as a working example. This model represents the generic product structure, that is, all possible variants of a configurable Computer. The basic structure of the product is modeled using classes, generalization, and aggregation. The set of possible products is restricted through a set of constraints that are related to technical restrictions, economic factors, and restrictions according to the production process. The concepts used stem from connection-based (Mittal & Frayman, 1989), resource-based (Heinrich & Jüngst, 1991), and structure-based (Stumptner, 1997) configuration approaches. These configuration domain-specific concepts represent a basic set useful for building configuration knowledge bases and mainly correspond to those defined in de facto standard configuration ontologies (Soininen et al., 1998; Felfernig et al., 2000a):
- Component types: Component types represent the basic building blocks of which a final product can be built and they are characterized by attributes (e.g., in Fig. 1 the component type CPU is characterized by the attribute clockrate).
- Generalization hierarchies: Component types with a similar structure are arranged in a generalization hierarchy (e.g., in Fig. 1 the component type CPU1 is a special kind of CPU).
- Part–whole relationships: Part–whole relationships between component types state a range of how many subparts an aggregate can consist of [e.g., a Computer contains at least one and at most two motherboards (MB)].
- Incompatibilities and requirements: Some types of components must not be used together within the same configuration because they are incompatible (e.g., a SCSIUnit is incompatible with a MB1). In other cases, the existence of one component of a specific type requires the existence of another special component within the configuration (e.g., an IDEUnit requires a MB1).
- Resource constraints: Parts of a configuration task can be seen as a resource balancing task, where some of the component types produce some resources and others are consumers (e.g., the consumed hard-disk capacity must not exceed the provided hard-disk capacity). Dependencies are introduced for representing the producer/consumer relationships between different component types.
- Port connections: In addition to the amount of components
and their type specifications, the product topology (i.e., exactly how
the components are interconnected) is often of interest as well in the
final configuration. The concept of a port is used for this purpose
(e.g., see the connection between Videocard and
Screen which is based on the ports videoport and
screenport). Note that in our example we do not apply
generalization hierarchies for ports and resources. Such a
generalization hierarchy could be defined depending on the application
domain and the capabilities of the underlying reasoning system. Our
definitions are general enough to allow these generalization
hierarchies.4
Note that UML interfaces can be used as an alternative representation for ports, although in our configuration profile we decided to use specialized classes for this purpose.
An example of a configuration model.
In the following we give a description logics based definition of a configuration problem and show its equivalence with the consistency-based definition given in Felfernig et al. (2000b). Furthermore, we describe OIL5
In the following we assume that the reader is familiar with the concepts of OIL. See Fensel et al. (2001b) for an introductory text.
3. DEFINING CONFIGURATION TASKS IN DESCRIPTION LOGIC AND PREDICATE LOGIC
3.1. Description logic based configuration task
For the description of a configuration task we employ a description logic language (e.g., OIL) starting from a schema
of disjoint sets of names for concepts, roles, and individuals (Borgida, 1996). Concepts can be seen as unary predicates defining classes (component types). Roles are used to express relationships between different elements of a domain. Finally, individuals are specific named elements of the domain.
Definition 1 (configuration problem in description logic). In general we assume a configuration problem is described by a triple (DDDL, SRSDL, CLANGDL), where DL is description logic, DDDL represents the domain description of the configurable product, and SRSDL specifies the particular system requirements defining an individual configuration problem instance. CLANGDL comprises a set of concepts
and a set of roles
that serve as a configuration language for the description of actual configurations (solutions).█
One can think of additional restrictions on SRSDL, DDDL, for example, that SRSDL may only contain concepts and roles that also occur in DDDL. However, we leave this decision to designers of domain-specific solutions.
In the following we will describe solutions to configuration problems based on the interpretation of concepts and roles. In order to make sure that roles in CLANGDL describe relationships only between concepts of CLANGDL, we require that roles in CLANGDL are defined over the domains given in Cconfig; that is, we add for each Ri ∈ Rconfig the role descriptions range(Ri) = CDom and dom(Ri) = CDom for CDom [esdot ] Ci∈CconfigCi to DDDL, if such descriptions are not subsumed by other descriptions already contained in the knowledge base. Note that DDDL may contain auxiliary concepts or roles that are not actually in CLANGDL.
Example 1: In this example we use a part of our computer ontology (see Fig. 1) that comprises CPUs and MBs as component types. On each MB at least one, but at most two, CPUs are mounted (constraint c1 in DDDL). A CPU must always be mounted on a MB (constraint c2 in DDDL). A CPU of type CPU2 must be mounted on a MB of type MB2 (constraint c3 in DDDL).
The domain description DDDL is defined as follows. Note that subclass-of and disjoint are used to express the completeness and disjointness of the generalization hierarchy where each individual must be instantiated to exactly one of the leaf nodes. Note also that to avoid introducing a separate operator we use subclass-of in reverse in one case, when writing CPU subclass-of (CPU1 or CPU2) to specify that the coverage of the subclasses is complete. These requirements together with the assumption that there is a fixed set of component types corresponds to assumptions in other description logic based papers such as Klein et al. (1994) and Weida (1996). We will discuss the implications in Section 5.
The customer requirement that there must be (at least) “two CPUs of type CPU1 and one CPU of type CPU2” is expressed by SRSDL = {(instance-of c1 CPU1), (instance-of c2 CPU1), (instance-of c3 CPU2)}.
The configuration language CLANGDL is defined by Cconfig = {CPU1, CPU2, MB1, MB2} and Rconfig = {mb-of-cpu}.
In our example we do not include the concepts CPU and MB and the role cpu-of-mb in CLANGDL because we are only interested in the leaf concepts of a generalization hierarchy and specific relationships (e.g., to manufacture the final system we only need to know the most specific type for each component and its connections). The semantics of description terms are usually given denotationally using an interpretation
is a domain (nonempty universe) of values and
is a mapping from concept descriptions to subsets of the domain and from role descriptions to sets of 2-tuples over the domain. The mapping also associates with every individual name in
some distinct value in
. The reason for this distinctness is the unique name assumption (UNA) we employ in our formalism. We require the UNA for concepts and roles that describe configurations in order to make sure that different identifiers for individuals (e.g., modules of a system) refer to different individuals. The UNA can be lifted, if necessary, for those concepts and roles that are not used to describe configurations. In the following we give a description logic based definition of a valid configuration and show its equivalence with consistency-based definitions given in the literature (Felfernig et al., 2000b). This definition serves as a joint foundation of configuration knowledge representation in the Semantic Web.
We use the extensions of concepts and roles that correspond to a logical model to specify valid configurations. Note that, depending on the domain, only specific concepts and roles are considered relevant for describing configurations (i.e., those roles and concepts defined in CLANGDL).
Our definition of a valid configuration does not make use of extraneous requirements such as minimality. Following our definitions, the domain description joined with the system requirements specification (describing the expectations of a customer) must enforce configuration solutions (described by the configuration language) such that these solutions deliver services which match the expectations of the customer. In practice (Fleischanderl et al., 1998) we have to allow solutions that may even include components that are unnecessary with respect to the current system requirements because some of these components might be needed in later extensions (reconfigurations). Accepting solutions that are satisfactory with respect to costs or to the number of components used is common practice in real-world applications. Although the optimality of such solutions is not shown, these solutions are appreciated because they are as good as or even better than good quality solutions provided by human experts.
Definition 2 (valid configuration in description logic). Given a configuration problem C = (DDDL, SRSDL, CLANGDL), let
be a model of DDDL ∪ SRSDL. CLANGDL = Cconfig ∪ Rconfig is the configuration language of the problem. Let COMPS be a set of tuples 〈Ci, INDIVSCi〉 for every Ci ∈ Cconfig, where
is the set of individuals of concept Ci in
. These individuals identify components in an actual configuration. Let
be the set of tuples of role Rj, then we define ROLES = {〈Rj, TUPLESRj〉|Rj ∈ Rconfig}.
We call CONFDL = COMPS ∪ ROLES a valid configuration for C.█
Example 2. A valid configuration for our example configuration problem is CONFDL = {〈CPU1, {c1, c2}〉, 〈CPU2, {c3}〉, 〈MB1, {m1}〉, 〈MB2, {m2}〉, 〈mb-of-cpu, {〈m1, c1〉, 〈m1, c2〉 〈m2, c3〉}〉}.█
We also have to describe component parameter settings in addition to components and their connections. Using description logics, such parameter settings of components are modeled by special functional roles (also called features) expressing the relation between the component and the data value assigned to a particular attribute. Therefore, component structure and parameter settings can be treated in a uniform manner except that the parameter values come from some data value domain dom(D) (Sattler, 2000), which is disjunct from the individuals in COMPS.
In addition to the definition of a valid configuration given above, we can provide an equivalent characterization based on checking the consistency of a set of axioms.
Remark 1. Let DDDL, SRSDL, CLANGDL = Cconfig ∪ Rconfig be a configuration problem, and CONFDL = COMPS ∪ ROLES be a description of a configuration.
The concepts Ci are defined by the component axioms
The roles Rj are defined by the role axioms
Note that we use the above notation for defining the complete extension of roles in order to apply the translation function from description logics to predicate logic defined in Borgida (1996). An alternative to the product constructor would be a constructor that (similar to the one-of constructor for concepts) permits the enumeration of permissible entries for a role. However, computation of the product requires only constant effort because we only apply product to singleton arguments.
Example 3. In order to verify that a given configuration is valid with respect to our example configuration problem (defined by DDDL and SRSDL), we need to add the axioms CPU1 [esdot ] one-of[c1, c2], CPU2 [esdot ] one-of[c3] , MB1 [esdot ] one-of[m1] , MB2 [esdot ] one-of[m2] , mb-of-cpu [esdot ] product[one-of[m1] , one-of[c1]] [sqcup ] product [one-of[m1] , one-of[c2]] [sqcup ] product[one-of[m2] , one-of[c3]].█
We now give a consistency-based definition of a configuration problem using predicate logic6
We employ a notation where variables are all quantified if not explicitly mentioned.
3.2. Predicate logic based configuration task
Definition 3 (configuration problem in predicate logic). In general we assume a configuration problem is described by a triple (DDLOG, SRSLOG, CLANGLOG) where DDLOG and SRSLOG are sets of logical sentences and CLANGLOG is a set of predicate symbols. DDLOG represents the domain description and SRSLOG specifies the particular system requirements. A configuration CONFLOG is described by a set of positive ground literals whose predicate symbols are in the set of CLANGLOG.█
Example 4. For our example, DDLOG can be expressed by using monadic and dyadic predicates and numerical quantifiers, that is:
Definition 4 (consistent configuration in predicate logic). Given a configuration problem (DDLOG, SRSLOG, CLANGLOG), a configuration CONFLOG is consistent iff DDLOG ∪ SRSLOG ∪ CONFLOG is satisfiable.█
This definition allows determining the consistency of partial configurations but does not guarantee the completeness of configurations (Felfernig et al., 2000b). It is necessary that a configuration explicitly includes all needed components (and their connections and attribute values) in order to assemble a correctly functioning system. We need to introduce an explicit formula for each predicate symbol in CLANGLOG to enforce its completeness property. In order to stay within first order logic, we model the property by first order formulae. For our example we have to add the completeness axiom
for the predicate CPU1 and similar axioms for CPU2 and mb-of-cpu. Note that
serves as a macro, which is expanded into a set of formulas by substituting the elements of CONFLOG for Z. Also note that if there are no parts of a particular type, the consequent of this rule degenerates to the empty clause (preventing spurious parts of that type from appearing in the configuration). We refer to CONFLOG extended by completeness axioms as
Note that the empty configuration can be a valid configuration. This is in keeping with the standard approach to specifying configuration problems, where it is a problem-dependent explicit specification expressed through key components (Mittal & Frayman, 1989; Heinrich & Jüngst, 1991; Fleischanderl et al., 1998) or some sort of functionality (which can only be satisfied by including components in the configuration, e.g., because of the existence of resource constraints) that prevents empty configurations from being consistent.
Example 5. CONFLOG = {CPU1(c1). CPU1(c2). CPU2(c3). MB1(m1). MB2(m2). mb-of-cpu(m1, c1). mb-of-cpu(m1, c2). mb-of-cpu(m2, c3).}
The completeness axiom for CPU1 is
where unsatisfiable literals are deleted.█
Definition 5 (valid configuration in predicate logic). Let (DDLOG, SRSLOG, CLANGLOG) be a configuration problem. A configuration CONFLOG is valid
is satisfiable.█
Note that CONFLOG in Example 5 is a valid configuration.
3.3. Equivalence
In order to show the equivalence of valid configurations for description logic and predicate logic, we apply a translation function
that maps description logics to predicate logic, that is, axioms to formulas with no free variables, concepts to formulas with one free variable, and roles to formulas with two free variables.
Borgida (1996, Theorem 1 and subsequent corollaries) provides such a translation function
such that concepts, roles, terms, and axioms of a description language
without transitive closure
7This description language contains a comprehensive list of operators based on an analysis of a set of corresponding survey papers.
. This language
allows only monadic and dyadic predicates, counting quantifiers and subformulas with at most three free variables. The UNA is assumed from the outset. For a concept C in
for a role r in
produces a predicate r(X,Y). Following this approach, C [sqsube ] D can be translated as
and [C, D] can be translated as
or [C, D] can be translated as
one-of [b1, b2,…, bm] can be translated as X = b1 ∨ X = b2 ∨ ··· ∨ X = bm, and product[C, D] can be translated as
Similar to the above-mentioned translation function (Borgida, 1996, Theorem 2 and subsequent corollaries) defines a translation function that maps sentences of
Given function
holds for all DDDL and SRSDL, and DDLOG ∪ SRSLOG is satisfiable iff DDDL ∪ SRSDL is satisfiable.
Remark 2 (equivalence of configuration problems). Let CLANGLOG = CLANGDL where each concept is interpreted as monadic and each role is interpreted as dyadic predicate. DDDL and SRSDL are sets of sentences in the description logic language
without transitive closure. DDLOG and SRSLOG are sets of sentences in
. CONFLOG describes the actual configuration by two sets of facts CONFLOG = COMP-facts ∪ ROLE-facts. The construction of CONFLOG is based on CONFDL = COMPS ∪ ROLES where COMP-facts = {Ci(ci)|ci ∈ INDIVSCi,Ci ∈ Cconfig} and ROLE-facts = {Rj(rj, sj)|〈rj, sj〉 ∈ TUPLESRj, Rj ∈ Rconfig}.
CONFLOG is a valid configuration for (DDLOG,SRSLOG, CLANGLOG) iff CONFDL is a valid configuration for (DDDL,SRSDL,CLANGDL).█
Remark 2 follows from Remark 1 and the equivalence property of the translation function. Note that CLANGLOG is restricted to exactly the monadic and dyadic predicates that correspond to the concept and role definitions of CLANGDL and no others. The equivalence result stated in the last sentence of the remark is made specifically for languages restricted in this manner (i.e.,
without transitive closure and
), and in this case the equivalence holds. Note also that the completeness axioms correspond exactly to the translation of the axioms AXCOMPS and AXROLES by applying the translation function proposed in Borgida (1996). For example, by employing the translation function, a Ci in AXCOMPS is translated to Ci(X) [harr ] X = ci1 ∨ ··· ∨ X = cini for INDIVSCi = ci1,…, cini, which is equivalent to our completeness axioms (predicate logic) for Ci. Note that in the formulation of the completeness axioms only one direction of the implication needs to be expressed because the Ci(ci) facts about the individuals ci are asserted by definition (they are contained in CONFLOG). The [esdot ] corresponds to identity and [sqcup ] corresponds to a disjunction. The equivalence for AXROLES follows immediately by using the translation rules for the terms one-of and product.
Note that there is a one to one relationship between CONFLOG and CONFDL. Applying Remarks 1 and 2, every valid configuration in the corresponding restricted predicate logic (i.e.,
) corresponds to a valid configuration in description logic. In addition, every valid configuration in description logic corresponds to a valid configuration in predicate logic. It follows that no configuration is missed using either of the two representations.
From the equivalence of configuration problems follow two important consequences. First, the two main streams in solving configuration problems based on description logics on the one hand, and predicate or propositional logic on the other hand can be easily transformed to each other. Second, because description logics without transitive closure are equally expressive to dyadic predicate logic with counting quantifiers and at most three free variables in each subformula (Borgida, 1996), it follows that the predicate logic based approach is strictly more expressive than the description logics based approach, implying that some logic constructions have to be simulated by more complex description logic constructions, and also that certain complex structural restrictions (Immerman, 1982; Cai et al., 1989; Schröder et al., 1996) are not expressible in the language directly but have to be incorporated using a more expressive assertional language.
4. STANDARDIZED KNOWLEDGE REPRESENTATION
UML (Rumbaugh et al., 1998) is a well-established modeling language in industrial software development processes. Felfernig et al. (2000a) demonstrated the applicability of UML for configuration knowledge representation. In order to bridge the gap between research and development organizations, we think it is indispensable to relate the knowledge representation concepts to UML. In the following, we employ UML as a basis for showing the representation of configuration knowledge in OIL and in predicate logic. For the modeling concepts discussed in Section 2, we present a set of rules for translating those concepts into an OIL based representation, as well as into an equivalent predicate logic based representation. The equivalence of the description logic and the predicate logic based representations is founded in the translation function
proposed in Borgida (1996).
UML is based on a graphical notation; therefore, our translation starts from such a graphical description of a configuration domain. In the following, GREP denotes the graphical representation of the UML configuration model. For the model elements of GREP (i.e., component types, generalization hierarchies, part–whole relationships, requirement constraints, incompatibility constraints), we propose rules for translating those concepts into a description logic based and into a predicate logic based representation. Note that we do not discuss the translation of resource constraints in this section because resource constraints cannot be represented using standard predicate logic or standard description logic (i.e., OIL, DAML+OIL). Semantics for resource constraints are presented in Section 5.
Rule 1a (component types). Let c be a component type in GREP, then
For all attributes a of c in GREP, and d the domain of a in GREP,
Rule 1b (component types). For those component types ci, cj ∈ {c1,…, cm} (ci ≠ cj), which do not have any supertypes in GREP,
Example 6a (component type CPU).
Example 6b (component type CPU).
Subtyping in the configuration domain means that attributes and roles of a given component type are inherited by its subtypes. In most configuration environments, a disjunctive and complete semantics is assumed for generalization hierarchies, where the disjunctive semantics can be expressed using the disjoint axiom and the completeness can be expressed by forcing the superclass to conform to one of the given subclasses as follows.
Rule 2 (generalization hierarchies). Let u and d1,…, dn be classes (component types) in GREP, where u is the superclass of d1,…, dn, then
Example 7a (CPU1, CPU2 subclasses of CPU).
Example 7b (CPU1, CPU2 subclasses of CPU).
Part–whole relationships are important model properties in the configuration domain. Artale et al. (1996), Soininen et al. (1998), and Sattler (2000) pointed out that part–whole relationships have quite variable semantics depending on the application domain. In most configuration environments, a part–whole relationship is described by the two basic roles partof and haspart. Depending on the intended semantics, different additional restrictions can be placed on the usage of those roles. Note that we do not require acyclicity because particular domains such as software configuration allow cycles on the type level. In the following we discuss two facets of part–whole relationships that are widely used for configuration knowledge representation (Soininen et al., 1998) and are also provided by UML, namely composite and shared part–whole relationships. In UML the composite part–whole relationships are denoted by a black diamond and shared part–whole relationships are denoted by a white diamond.8
Note that in our Computer configuration example we only use composite part–whole relationships. As mentioned in Soininen et al. (1998), composite part–whole relationships are often used when modeling physical products, whereas shared part–whole relationships are used to describe abstract entities such as services.
The part–whole relationship (p, part; w, whole).
Rule 3 (part–whole relationships). Let w and p be component types in GREP, where p is a part of w, ubp is the upper bound and lbp is the lower bound of the multiplicity of the part, and ubw is the upper bound and lbw is the lower bound of the multiplicity of the whole. Furthermore, let w-of-p and p-of-w denote the names of the roles of the part–whole relationship between w and p, where w-of-p denotes the role connecting the part with the whole and p-of-w denotes the role connecting the whole with the part, that is, p-of-w [sqsube ] haspart, w-of-p [sqsube ] Partofmode, where Partofmode ∈ {partofcomposite,partofshared}. A part p can be either a shared part (concept partshared) or a composite part (concept partcomposite). Given a part–whole relationship between p and w in GREP, then
Remark 3. The following properties have to hold for shared and composite part–whole relationships.
Example 8a (MB partof Computer)
Example 8b (MB partof Computer):
4.1. Necessary part-of structure properties
In the following we show how the constraints contained in a product configuration model (e.g., an IDEUnit requires an MB1) can be translated into a corresponding OIL representation. For a consistent application of the translation rules, it must be ensured that the components involved are parts of the same subconfiguration, that is, the involved components must be connected to the same instance of the component type that represents the common root9
In Figure 3 the component type Computer is the unique common root of IDEUnit and CPU1.
The navigation paths from Computer to CPU1 and IDEUnit.
For the derivation of constraints on the product model, we introduce the macro navpath as an abbreviation for a navigation expression over roles. For the definition of navpath the UML configuration model can be interpreted as a directed graph, where component types are represented by vertices and part–whole relationships are represented by edges.
Definition 6 (navigation expression). Let path(c1, cn) be a path from a component type c1 to a component type cn in GREP represented through a sequence of expressions of the form haspart(Ci,Cj, NameCi) denoting a direct partof relationship between the component types Ci and Cj. Furthermore, NameCi represents the name of the corresponding haspart role. Such a path in GREP is represented as
Based on the definition of path(c1, cn) we can define the macro navpath(c1, cn) as
For the translation into DDLOG the macro navpath(c1, cn) is defined as
where X is a free variable quantified outside the scope of this expression and represents an instance of concept c1. █
Example 9a (navpath(Computer,CPU1)).
Example 9b (navpath(Computer,CPU1)).
The concept of a nearest common root is based on the definition of navpath as follows.
Definition 7 (nearest common root). A component type r is denoted as the nearest common root of the component types c1 and c2 in GREP, iff there exist paths path(r, c1), path(r, c2) and there does not exist a component type r′, where r′ is a part10
In this context partof is assumed to be transitive.
When regarding the example configuration model of Figure 1, MB is the nearest common root of CPU and Videocard. Note that the component type Computer is not a nearest common root of CPU and Videocard but it is the nearest common root of CPU1 and IDEUnit (see Fig. 3).
4.2. Requirement constraints
A requires constraint between two component types, c1 and c2, in GREP denotes the fact that the existence of an instance of component type c1 requires an instance of component type c2 in the same (sub)configuration.
Rule 4 (requirement constraints). Given the relationship c1 requires c2 between the component types c1 and c2 in GREP with r as the nearest common root of c1 and c2, then
The condition part of the inner implication is a path from the nearest common root to the component c1; the consequent is a path to the required component c2.
Example 10a (IDEUnit requires MB1).
Example 10b (IDEUnit requires MB1).
4.3. Incompatibility constraints
An incompatibility constraint between a set of component types c = {c1, c2,…, cn} in GREP denotes the fact that the existence of a tuple of instances corresponding to the types in c is not allowed in a final configuration (result).
Rule 5 (incompatibility constraints). Given an incompatibility constraint between a set of component types c = {c1, c2,…, cn} in GREP with r as the nearest common root of {c1, c2,…, cn}, then
Example 11a (SCSIUnit incompatible with MB1).
Example 11b (SCSIUnit incompatible with MB1).
4.4. Resource constraints
In order to introduce resource constraints, additional expressivity requirements must be fulfilled. This issue will be discussed in Section 5.
4.5. Port connections
Ports in the UML configuration model (see Fig. 4) represent physical connection points between components (e.g., a Videocard can be connected to a Screen using the port combination videoport1 and screenport2). In UML we introduce ports using classes with stereotype Port; these ports are connected to component types using relationships.
The ports in the configuration model.
In order to represent port connections in OIL, we introduce them via a separate concept Port.11
Note that in OIL there are only predicates with arity 1 or 2 available. Therefore, the representation of port connections must be realized by the definition of additional concepts.
Rule 6 (port connections). Let {a, b} be component types in GREP, {pa, pb} be the corresponding connected port types, {ma, mb} be the multiplicities of the port types with respect to {a, b},12
In this context no differentiation between lower and upper bound is needed because the number of ports of a component is exactly known beforehand.
Example 12a (Videocard connected to Screen)
Example 12b (Videocard connected to Screen)
Using the port connection structure defined above, the constraint “a Videocard must be connected via videoport1 with a Screen via screenport1” can be written as follows.
Example 13a.
Example 13b.
5. ANALYSIS
Although the basic frame structure and formal basis of description logics based languages makes them one of the natural choices for configuration representation, certain demands on expressiveness must be met. This section deals with the functions that are not currently expressible in OIL and therefore require extensions to the language: aggregation functions and built-in predicates, representation of resources, structural properties and n-ary relationships, and the possible incorporation of specific assertional languages. These will be considered in the following subsections.
5.1. Aggregation functions and built-in predicates
The current versions of OIL (Fensel et al., 2001b) and DAML+OIL (VanHarmelen et al., 2001) do not support aggregation functions (e.g., sum or avg) which are fundamental representation concepts frequently used in the configuration domain. Baader and Sattler (1998) provided concrete domains and aggregation functions over them as extensions to the basic description logic
In addition to aggregation functions, built-in predicates must be allowed in order to support comparisons on the results of aggregation functions as well as on local features. In configuration knowledge representation aggregation functions are used for designing resource constraints enforcing the balance between produced and consumed resources.
Resource constraints can be modeled in UML using stereotyped classes representing types of resources and stereotyped dependencies with a corresponding tagged value indicating resource production and consumption (see Fig. 1). Resource balancing tasks (Heinrich & Jüngst, 1991) are defined within a (sub)tree (context) of the configuration model. To map a resource balancing task into DD, additional attributes (resp and resc in the following) have to be defined for the component types acting as producers and consumers. In addition, we have to introduce aggregation functions as representation concepts, which are currently supported neither in OIL nor DAML+OIL. However, proposals exist (Baader & Sattler, 1998) to extend description logics by concepts that allow the modeling of such resource constructs. The following representation of aggregation functions is based on the formalism presented in Baader and Sattler (1998), where a set of predicates P associated with binary relations (e.g., ≤, ≥, <, >) over a value domain dom(D) and a set of aggregation functions agg(D) (e.g., count,min,max,sum) are defined. Let φ be the path leading from the nearest common root to the concept whose features are aggregated. Then the definitions of Baader and Sattler (1998) require that all but the last one of the roles in φ must be features, that is, functional relations (see Section 3). Note that for our navpath expressions functional restrictions are also required.
Rule 7 (resource constraints). Let p = {p1, p2,…, pn} be producing component types and c = {c1, c2,…, cm} be consuming component types of resource res in GREP. Furthermore, let resp be a feature common to all component types in p, and resc be a feature common to the types in c, where the values of resp and resc are defined by the tagged values of the consumes and produces dependencies in GREP.
Using the notation of Baader and Sattler (1998), a resource constraint for DDDL can be expressed as
where r represents the nearest common root of the elements in c and p, P is a binary relation, and < r11, r21,…, rn1 > , < r12, r22,…, rm2 > represent navigation paths from r to the elements of p and c.
A resource constraint for DDLOG can be expressed as
where P is set to ≤ in this case.
The predicates allconsumers and allproducers define sets of all objects that appear as role fillers at the end of a navigation path and are (respectively) either consumers or producers. We use normal set notation (Hella et al., 2001) to express the grouping.
In the context of resources we define the macro navpath′ (X1, Xn, c1, cn) as c1(X1) ∧ namec1(X2, X1) ∧ namec2(X3, X2) ∧ … ∧ namecn−1(Xn, Xn−1) ∧ cn(Xn), where nameci represents a haspart role in the path from the component type c1 to component type cn.█
Example 14a (capacity needed by Software ≤ capacity provided by HDUnit).
Example 14b (needed Software capacity ≤ HDUnit capacity).
5.2. Complex structural properties
Because trivial structural conditions lead to definitional overhead in DAML+OIL (e.g., when defining restrictions on port connections), additional concepts must be provided allowing the definition of roles with arity greater than 2. In effect, this would result in the definition of a separate constraint language or a relational language permitting arbitrary n-ary relations and disjuncts of positive literals, (e.g., to express alternative ports). Also, the description of more complex structural properties would be supported by permitting the usage of variables (Immerman, 1982; Cai et al., 1989; Schröder et al., 1996).
The utility of knowledge-based configurators in some domains crucially depends on the ability to configure structural (topological) properties such as the connecting of components by cables (see Fig. 5 for an example). In fact, the configuration of the cable connections is one of the most difficult parts in a configuration process (e.g., when configuring telecommunication switches; Fleischanderl et al., 1998). It is exactly at this stage that successful knowledge-based configuration has to show its advantage over traditional procedural configuration systems. In order to truly gain advantage over conventional approaches in domains where structural knowledge must be expressed, knowledge representation must support the formulation of these properties.
The cable connections of a Siemens EWSD telecommunication system.
5.3. Decidability
Happily, most of the required means of expression are already available in the description logic designer's toolbox; however, the degree of expressivity required also leads to problems with respect to decidability of basic properties such as satisfiability or subsumption (Baader & Sattler, 1998). State of the art configurators achieve decidability by putting a predefined limit on the number of individuals and allowing only finite domains of values for features (constraint variables). Furthermore, only fixed concept hierarchies are allowed (as part catalogs are typically considered unchangeable), which reduces the importance of subsumption versus that of A-Box (assertion box, i.e., instance level) reasoning.
From a practical point of view, the systems occurring in configuration domains (such as telecom systems, railway safety systems, etc.) are designed to be understood (and, theoretically, configured) by human experts. The language these human experts use to describe the configuration constraints and to exchange knowledge is far more expressive than decidability considerations would allow. In the configuration process, simple heuristics are used to guide the construction process of a configuration. It is interesting that the configuration knowledge allows a quick conclusion as to whether a customer request can be fulfilled. In the rare cases where it is not easily decidable, organizations tend toward default decisions (e.g., if we are not sure that a valid configuration is possible, we just refuse the customer request). COCOS (Fleischanderl et al., 1998) and almost any practical applications of configurators crucially depend on the application of search heuristics. Relating this to our concepts, it must be possible to guide the model search process and even to stop this process if certain thresholds are exceeded. Such heuristics include orderings about the types of individuals (e.g., which type a newly generated individual should take) or about assignments of values to features and filling of roles. These types of heuristics have proved quite sufficient and highly effective in the configuration of such large-scale systems as the EWSD (a digital switching system, Siemens), which can comprise more than 100 racks, 1,000 frames, 30,000 modules, and 10,000 cables.
6. THE CAWICOMS ENVIRONMENT
When selling complex products and services over the web, the shortcomings of current configuration technology become obvious. Web-based commerce places additional requirements on the interaction with configuration systems: customers with different needs, skill levels, or organizational backgrounds interact with the system. Therefore, interfaces must be provided that dynamically adapt to the needs of the customers (i.e., a personalized presentation of the configurable product is needed). Another shortcoming of current configuration technology concerns the cooperation between separate configurators. There is no central point of knowledge, and therefore a single-configurator approach is not appropriate (see the application scenario in Section 6.3). In addition to the distribution of configuration knowledge, distributed problem solving processes have to be supported in order to allow the calculation of solutions for distributed configuration tasks. In order to address the shortcomings of current configuration systems, we have developed an infrastructure for the creation of web-based, user-adaptive configuration systems that can perform distributed configuration of products and services by interacting with remote suppliers. This infrastructure is a result of the IST research project CAWICOMS. The concepts presented in this paper are the basis for the CAWICOMS Knowledge Acquisition Component (see Section 6.2). OIL representations can be generated from a UML configuration model and be used for configuration knowledge interchange. The knowledge acquisition component has been successfully tested using the scenario of distributed virtual private network (VPN) configuration (see Section 6.3).
6.1. Architecture
The overall architecture of the CAWICOMS (Ardissono et al., 2001) environment is shown in Figure 6. The central component of this architecture is the CAWICOMS Configuration Server, which is responsible for the integration of remote configuration systems (also product catalogs), the coordination of a distributed configuration process, and the personalized presentation of the configuration results to the customer. In this context the CAWICOMS Frontend provides personalization functionality and the CAWICOMS Backend provides distributed problem solving functionality. The configuration server has an interface to underlying B2B/ERP Platforms, which allows it to forward the result of a configuration session to subsequent processes (e.g., procurement transactions).
The overall CAWICOMS architecture.
6.2. Knowledge acquisition
The concepts presented in this paper are implemented in the CAWICOMS Knowledge Acquisition Component. This workbench enables distributed configuration processes by supporting standardized configuration knowledge base development and interchange between different configuration environments; knowledge interchange is supported in UML/Extensible Markup Language (UML/XML; OMG, 1999) and OIL (Fensel et al., 2001b) using the OilEd ontology editor presented in Bechhofer et al. (2001). Constraints on the product structure can be modeled by directly annotating the UML configuration model; this functionality is provided by a Configuration Add-in for the CASE tool Rational Rose.14
See www.rational.com.
See www.ilog.com.
6.3. Application scenario
One of the guiding application scenarios for the CAWICOMS project is the distributed configuration of VPNs. A VPN is an extension of an enterprise's private network that provides network services based on a public network infrastructure such as the Internet. A secure communication environment can be provided for defined communities of interest. The major advantage of such networks is that no expensive maintenance for company-wide area networks is necessary. The infrastructure for VPNs is provided by specialized solution providers who offer different subcomponents (services) for the VPN (e.g., telephony services, leased lines, firewalls, or computers). These subcomponents are integrated by resellers (integrated solution providers), who subsequently offer complete VPN solutions to their customers. In many cases the subcomponents from specialized solutions providers are configurable (i.e., the integration of such a set of components into a complete VPN solution can be interpreted as a distributed configuration task). Using the CAWICOMS Knowledge Acquisition Component, resellers can integrate functional product descriptions (functional architectures, Mittal & Frayman, 1989) into an integrated configuration model. This integrated model is the basis for the CAWICOMS Configuration Server, which starts a distributed configuration process and tries to calculate a solution for the given distributed configuration task.
7. RELATED WORK
7.1. Description logic based approaches
In the past, a number of authors have suggested general description logic based frameworks for configuration. First among these was the work by Owsnicki–Klewe (1988), which used a KL-ONE like language for automatically determining the most specific concept for each entity in a (fixed) configuration structure. The result of a configuration corresponds to a deductive closure starting from object instances and reaching a fix point. These deductions compute facts about objects such as concept membership or role fillers. The configuration result does not describe a complete configuration in case of disjunctions or existential quantification. As pointed out by Schröder et al. (1996), unlike other description logic approaches, this required defining concepts in terms of both necessary and sufficient terms. No new objects could be created. Compared to our definitions the approach of Owsnicki–Klewe (1988) computes consistent configurations, but (depending on the formulation of the knowledge base) it is not guaranteed that these configurations are valid because they may be incomplete.
The best known description logic based configuration system is the PROSE system used by AT&T (McGuinness & Wright, 1998). PROSE used a knowledge management and reasoning system based on the tractable description logic CLASSIC for checking the consistency of configuration solutions and to perform deductions. Configurations were computed (expanded) using a forward chaining production rule interpreter as also described by Weida (1996). From the view of our definitional framework, PROSE searches for consistent solutions where a completeness check can be achieved by closing roles. Note that CLASSIC does not apply the closed world assumption.
When configuring, many deductions are drawn which are not relevant for describing configurations. This was solved in PROSE by filters which restrict the output of the configuration process to the relevant deductions. This filter mechanism is achieved in our approach by defining the relevant concepts and roles needed to describe solutions to a configuration problem. An approach similar to PROSE was followed in the system developed by Weida (1996), which directly incorporated the so-called closed terminology assumption (CTA). As in PROSE, the description logic reasoner was used for consistency checking, with problem specific reasoning components producing the actual configuration. The CTA means that, as in CPS (see below) or most non-description logic configuration systems, the set of concepts and the subsumption hierarchy were assumed to be fixed; the parts in a final solution have to belong to the leaves in the concept hierarchy, which represent concrete types. The CTA limits the concepts an individual can instantiate. Roughly speaking, an individual (e.g., a particular component of a configuration) is only accepted to be part of a configuration if it can be monotonically extended to match an explicitly defined (concrete) concept. For example, if we learn from a component that its color is red but our domain knowledge base is ignorant about colors, then this component cannot be part of any configuration. The closed terminology assumption adds implicit additional constraints to a knowledge base. In order to achieve the same effect, we need additional constraints in our framework to exclude such components from valid configurations. We argue that both approaches (open vs. closed terminologies) have their advantages, depending on the application domain. Note that this is closely related to the distinction made in the diagnosis community between the consistency-based and the abductive-based approaches; that is, one has to decide whether diagnoses that do not explain all observations should be ruled out or not. A further aspect of such assumptions concerns the exchange of knowledge bases. The content of the knowledge base depends on the semantics and assumptions of the underlying reasoning system. Consequently, the exchange of knowledge bases eventually needs a transformation, if we submit a knowledge base written under the closed terminology assumption to a reasoning system employing open terminologies.
Generally, the most formally refined of the description logic approaches was the CPS approach that used a sorted feature logic to provide a formal model for configuration tasks (Klein et al., 1994; Buchheit et al., 1995). Configuration is defined as an abductive task using a domain-specific implication operator that provides a model
based on C [vdash ]D ∃.S,C [vdash ]D I, where D is the definitional knowledge; C is the configuration, ∃.S is the existential closure of the specification S; I is a set of integrity constraints; and S and I hold in the extension
of C, which is defined by D. As most logic-based configuration approaches (e.g., systems based on constraint satisfaction formalisms) and all configuration solvers in industrial use known to the authors use a consistency-based approach, we have taken that route instead.
Finally, Schröder et al. (1996) used a description logic based approach for a theoretical analysis of the the well-known PLAKON/KONWERK configurator (Cunis et al., 1989; Günther & Cunis, 1992; Günther, 1995) and its expressive means. The language defined for this study was designed to possess as many properties as possible of the original heterogeneous PLAKON/KONWERK representation (including explicit cover axioms that fixed the concept hierarchy and guaranteed disjunction between concepts). We found that a large amount of the expressiveness could be captured, although not all (PLAKON/KONWERK did, for example, support arbitrary n-ary constraints). Our view of the configuration problem and its solution is compatible with this approach.
7.2. Other approaches
In parallel to the description logic based work, a number of other approaches were recently developed to provide broad coverage of configuration domains with different properties.
The approach of Simons et al. (2002) is based on stable model semantics. As a consequence, unjustified components in a configuration solution are excluded. More formally speaking, some of the logical models of a set of sentences are not accepted if the stable model property is not fulfilled. Compared to our approach, such an approach of restricting the set of allowed models (one can also think of minimal model semantics) rejects configurations that would be valid in our case. The reason why we are more liberal is based on practical observations. For example, in the telecommunications domain it is common practice to add components to a configuration that are not necessary in the current situation but might be necessary in a next expansion step. Such configurations would not be accepted under stable model semantics because of the unjustified components, and explicit justifications would have to be entered into the knowledge base.
One of the most prominent methods to solve configuration problems is to apply constraint-based reasoning and its variants, such as dynamic and generative constraint satisfaction (e.g., Mittal & Frayman, 1989; Mittal & Falkenhainer, 1990; Heinrich & Jüngst, 1991; Fleischanderl et al., 1998; Mailharro, 1998) just to name some examples of the vast number of applications. In constraint satisfaction we are searching for an assignment to all variables in order to satisfy all constraints. This corresponds to our consistency-based definition of a configuration problem, where the configuration result is described by the set of variables and their assignments. Completeness of the configuration is automatically achieved in the case where the set of all variables is known to be static because all variables receive a value assignment. Note that dynamic CSPs can be transformed to static ones. Generative constraint satisfaction is different insofar that the number of variables is not known initially. However, the solution described in Stumptner et al. (1998) assures that the configuration is valid by checking that all attributes are assigned and no additional components and connections exist. Likewise, the resource-based (Heinrich & Jüngst, 1991) approach fits our definitions nicely because in this paradigm we are searching for a set of resources such that all resource constraints are satisfied.
The goal of Aldanondo et al. (2000) is to propose a set of modeling concepts enabling a noncomputer specialist to describe generic configuration models. Based on a set of requirements stemming from different classes of configuration problems a set of modeling concepts is presented which is based on the dynamic CSP approach (Mittal & Falkenhainer, 1990). This approach to configuration knowledge representation has its advantages when modeling configuration problems for dynamic CSP solving. Compared to the approach presented in this paper, the problem of representing configuration knowledge on a more abstract level is solved by providing graphical representations for problem variables. In Ramachandran and Gil (1999) the EXPECT (Swartout & Gil, 1995) approach for knowledge acquisition is applied to the configuration domain. The EXPECT configuration knowledge acquisition approach is based on a proprietary representation, whereas the approach presented in this paper supports knowledge acquisition and knowledge interchange on the basis of a common foundation for configuration knowledge representation; the use of UML as the configuration knowledge representation language permits the integration of configuration technology into industrial software development processes. Smith et al. (1988) present an approach based on the idea of configuration knowledge representation using dependency diagrams. These diagrams depict the dependencies between different parameters of the configurable product. The graphical notation is used as the communication basis between the domain expert and the knowledge engineer but does not allow the automated derivation of configuration knowledge bases.
The definition of a common representation language to support knowledge interchange between and integration of different knowledge-based systems is an important issue in the configuration domain. In Soininen et al. (1998) one approach to collect relevant concepts for modeling configuration knowledge bases is presented. The defined ontology is based on Ontolingua (Gruber, 1992) and represents a synthesis of resource-based, function-based, connection-based, and structure-based configuration approaches. This ontology is a kind of metaontology that is similar to the UML profile for configuration models presented in this paper. Conforming to the definition of Chandrasekaran et al. (1999), a UML configuration model is an ontology, that is, it restricts the sort of objects relevant for the domain and defines the possible properties of objects and the relationships between objects. Felfernig et al. (2000a) present an approach to automatically translate UML configuration models into a corresponding consistency-based definition of a configuration problem. The work presented in this paper is an extension of the work of Felfernig et al. (2000a) in the sense that a joint foundation for the representation of configuration problems is established by giving a description logic based definition of a configuration problem and showing the equivalence to existing consistency-based definitions (Felfernig et al., 2000b).
The work of Cranefield (2001) shows some similarities to the work presented in this paper. Starting with a UML ontology (which is basically represented as a class diagram) corresponding Java classes and RDF documents are generated. The work presented in this paper goes one step further by providing a UML profile for the configuration domain and a set of translation rules allowing the automatic derivation of executable configuration knowledge bases. We show the correspondence between Semantic Web ontology languages and UML on the object level, as well as on the constraint level, where a set of domain-specific constraints (e.g., requires) are introduced as stereotypes in the configuration profile. For these constraints we present the corresponding representation in OIL.
Most of the required means for expressing configuration knowledge are already provided by current versions of semantic web knowledge representation languages. However, in order to provide full-fledged configuration knowledge representation, certain additional means of expression must be provided in terms of new operators or relaxed restrictions on the language, as discussed in Section 5. Finally, we assumed the unique name assumption from the start, as this is a necessity in each problem domain that exhibits repetitive subcomponents (i.e., tasks where the same type of component can occur repeatedly but the topology of the connections plays a role).
Within the Semantic Web community there are ongoing efforts to increase the expressiveness of web ontology languages. DAML-L (McIlraith et al., 2001) is a language that builds on the basic concepts of DAML. XML Rules (Grosof, 2001) and CIF (i.e., Constraint Interchange Format; Gray et al., 2001) are similar approaches with the goal to provide rule languages for the Semantic Web.
Solutions already exist for the integration of product catalogs within marketplace environments (Fensel et al., 2001a). The basic approach is to provide a standard representation language and to provide a set of transformation concepts for integrating proprietary product representations. However, standard representation languages for simple products do not consider the basic properties of configurable products; exactly these properties were discussed in this paper and corresponding solutions for the integration of configurable products and services have been developed in the CAWICOMS project (Ardissono et al., 2001).
8. CONCLUSION
In this paper we have shown how to apply Semantic Web ontology languages for configuration knowledge representation. We have given a description logic based definition of a configuration problem and shown its equivalence with corresponding consistency-based definitions. A consequence of this equivalence is that configuration problems represented in standard description logics (OIL or DAML+OIL or Borgida, 1996) can be transformed into configuration problems represented in predicate logic (dyadic predicate logic with counting quantifiers and at most three free variables in each subformula) and vice versa. Consequently, we provide a common foundation that enables joint research activities and exploration of results. With respect to ongoing efforts to extend DAML+OIL, our paper contributes a set of criteria that must be fulfilled in order to use such a language for full-fledged configuration knowledge representation. It follows that DAML+OIL and OIL must be extended in order to cover requirements imposed by de facto standard configuration ontologies. By using UML for configuration knowledge representation, we support effective sharing and integration of configuration knowledge on a graphical level, which has become one of the major issues in the context of distributed configuration problem solving.
ACKNOWLEDGMENTS
We thank the reviewers for their suggestions that certainly improved this paper.
References
REFERENCES
Aldanondo, M.,
Moynard, G., &
Hamou, K.
(2000).
General configurator requirements and modeling elements.
Proc. Workshop on Configuration, ECAI 2000, pp.
1–6.
Ardissono, L.,
Felfernig, A.,
Friedrich, G.,
Jannach, D.,
Zanker, M., &
Schäfer, R.
(2001).
Customer-adaptive and distributed online product configuration in
the CAWICOMS Project.
Proc. Workshop on Configuration, in Conjunction with the 17th
International Conf. Artificial Intelligence (IJCAI-2001), pp.
8–14.
Artale, A.,
Franconi, E.,
Guarino, N., &
Pazzi, L.
(1996).
Part–whole relations in object-centered systems: An overview.
Data & Knowledge Engineering
20(3),
347–383.Google Scholar
Baader, F. &
Sattler, U.
(1998).
Description logics with concrete domains and aggregation.
Proc. 13th European Conf. Artificial Intelligence (ECAI '98), pp.
336–340.
Barker, V.,
O'Connor, D.,
Bachant, J., &
Soloway, E.
(1989).
Expert systems for configuration at Digital: XCON and beyond.
Communications of the ACM
32(3),
298–318.Google Scholar
Bechhofer, S.,
Horrocks, I.,
Goble, C., &
Stevens, R.
(2001).
OilEd: A reasonable ontology editor for the Semantic Web.
Proc. Joint German/Austrian Conf. on AI, pp.
396–408.
Burners–Lee, T.
(2000).
Weaving the Web.
New York:
Harper Business.
Booch, G.
(1994).
Object-Oriented Analysis and Design with Applications. Object
Technology Series.
Reading, MA:
Addison–Wesley.
Borgida, A.
(1996).
On the relative expressive power of description logics and
predicate calculus.
Artificial Intelligence 82,
353–367.
Buchheit, M.,
Klein, R., &
Nutt, W.
(1995).
Constructive Problem Solving: A Model Construction Approach Towards
Configuration.
Technical Report TM-95-01. Saarbrücken, Germany:
DFKI.
Cai, J.,
Fürer, M., &
Immerman, N.
(1989).
An optimal lower bond on the number of variables for graph
identification.
Proc. 30th IEEE Symposium on FOCS, pp.
612–617.
Chandrasekaran, B.,
Josephson, J., &
Benjamins, R.
(1999).
What are ontologies, and why do we need them?
IEEE Intelligent Systems
14(1),
20–26.Google Scholar
Cranefield, S.
(2001).
UML and the Semantic Web.
Semantic Web Working Symposium.
Cunis, R.,
Günter, A.,
Syska, I.,
Peters, H., &
Bode, H.
(1989).
PLAKON—An approach to domain independent construction.
Proc. Int. Conf. Industrial and Engineering Applications of
Artificial Intelligence and Expert Systems, pp.
298–318.
Felfernig, A.,
Friedrich, G., &
Jannach, D.
(2000a).
UML as domain specific language for the construction of
knowledge-based configuration systems.
International Journal of Software Engineering and Knowledge
Engineering
10(4),
449–469.Google Scholar
Felfernig, A.,
Friedrich, G.,
Jannach, D., &
Stumptner, M.
(2000b).
Consistency-based diagnosis of configuration knowledge bases.
Proc. 14th European Conf. Artificial Intelligence (ECAI 2000), pp.
146–150.
Fensel, D.,
Ding, Y.,
Omelayenko, B.,
Schulten, E.,
Botquin, G.,
Brown, M., &
Fett, A.
(2001a).
Product data integration in B2B E-commerce.
IEEE Intelligent Systems
16(4),
54–59.Google Scholar
Fensel, D.,
VanHarmelen, F.,
Horrocks, I.,
McGuinness, D., &
Patel–Schneider, P.
(2001b).
OIL: An ontology infrastructure for the semantic web.
IEEE Intelligent Systems
16(2),
38–45.Google Scholar
Fleischanderl, G.,
Friedrich, G.,
Haselböck, A.,
Schreiner, H., &
Stumptner, M.
(1998).
Configuring large systems using generative constraint satisfaction.
IEEE Intelligent Systems
13(4),
59–68.Google Scholar
Gray, P.,
Hui, K., &
Preece, A.
(2001).
An expressive constraint language for Semantic Web applications.
Proc. IJCAI 2001 Workshop on E-Business and the Intelligent Web, pp.
46–53.
Grosof, B.
(2001).
Standardizing XML rules.
Proc. IJCAI 2001 Workshop on E-Business and the Intelligent Web, pp.
2–3.
Gruber, T.
(1992).
Ontolingua: A Mechanism to Support Portable Ontologies.
Technical Report KSL 91-66. Stanford, CA:
KSL.
Gruber, T.,
Olsen, R., &
Runkel, J.
(1996).
The configuration design ontologies and the VT elevator domain
theory.
International Journal of Human–Computer Studies 44(3/4),
569–598.
Günther, A. &
Cunis, R.
(1992).
Flexible control in expert systems for construction tasks.
Journal of Applied Intelligence
2(4),
369–385.Google Scholar
Günther, A.
(1995).
Wissensbasiertes Konfigurieren: Ergebnisse aus dem Projekt PROKON.
Sankt Augustin, Germany:
Infix.
Heinrich, M. &
Jüngst, E.
(1991).
A resource-based paradigm for the configuring of technical systems
from modular components.
Proc. 7th IEEE Conf. AI Applications (CAIA), pp.
257–264.
Hella, L.,
Libkin, L.,
Nurmonen, J., &
Wong, L.
(2001).
Logics with aggregate operators.
Journal ACM
48(4),
880–907.Google Scholar
Immerman, N.
(1982).
Upper and lower bounds for first-order expressibility.
Journal of Computer and System Sciences 25,
76–98.
Jacobson, I.,
Christerson, M., &
Övergaard, G.
(1992).
Object-oriented Software Engineering—A Use-Case Driven
Approach.
Reading, MA:
Addison–Wesley.
Klein, R.,
Buchheit, M., &
Nutt, W.
(1994).
Configuration as model construction: The constructive problem
solving approach.
Proc. 3rd Int. Conf. Artificial Intelligence in Design, AID'94, pp.
201–218.
Mailharro, D.
(1998).
A classification and constraint-based framework for configuration.
Artificial Intelligence for Engineering Design, Analysis and
Manufacturing
12(4),
383–397.Google Scholar
McGuinness, D. &
Wright, J.
(1998).
Conceptual modeling for configuration: A description logic-based
approach.
Artificial Intelligence for Engineering Design, Analysis and
Manufacturing
12(4),
333–344.Google Scholar
McIlraith, S.,
Son, T., &
Zeng, H.
(2001).
Mobilizing the Semantic Web with DAML-enabled web services.
Proc. IJCAI 2001 Workshop on E-Business and the Intelligent Web, pp.
29–39.
Mittal, S. &
Falkenhainer, B.
(1990).
Dynamic constraint satisfaction problems.
Proc. National Conf. Artificial Intelligence (AAAI 90), pp.
25–32.
Mittal, S. &
Frayman, F.
(1989).
Towards a generic model of configuration tasks.
Proc. 11th Int. Joint Conf. Artificial Intelligence, pp.
1395–1401.
OMG.
(1999).
XMI Specification.
Available on-line at www.omg.org.
Owsnicki–Klewe, B.
(1988).
Configuration as a consistency maintenance task.
Proc. GWAI-88—The 12th German Workshop on Artificial
Intelligence, pp.
77–87.
Ramachandran, S. &
Gil, Y.
(1999).
Knowledge acquisition for configuration tasks: The EXPECT
approach.
Proc. AAAI Workshop on Configuration,
Technical Report WS-99-05, pp.
29–34.
Rumbaugh, J.,
Blaha, M.,
Premerlani, W.,
Eddy, F., &
Lorensen, W.
(1991).
Object-Oriented Modeling and Design.
Englewood Cliffs, NJ:
Prentice–Hall.
Rumbaugh, J.,
Jacobson, I., &
Booch, G.
(1998).
The Unified Modeling Language Reference Manual.
Reading, MA:
Addison–Wesley.
Sattler, U.
(2000).
Description logics for the representation of aggregated objects.
Proc. 14th Eur. Conf. Artificial Intelligence (ECAI 2000), pp.
239–243.
Schröder, C.,
Möller, R., &
Lutz, C.
(1996).
A partial logical reconstruction of PLAKON/KONWERK.
Proc. Workshop on Knowledge Representation and Configuration,
DFKI Memo D-96-04, pp.
55–64.
Silaghi, M.,
Sam–Haroud, D., &
Faltings, B.
(2000).
Asynchronous search with aggregations.
Proc. 17th National Conf. Artificial Intelligence (AAAI), pp.
917–922.
Simons, P.,
Niemelä, I., &
Soininen, T.
(2002).
Extending and implementing the stable model semantics.
Artificial Intelligence 138(1–2).
181–234.
Smith, C.,
Inder, R., &
Chung, P.
(1988).
Knowledge acquisition and representation for product
configuration.
Proc. 1st Int. Conf. Industrial and Engineering Applications of AI
and Expert Systems (IEA/AIE'88), pp.
805–811.
Soininen, T.,
Tiihonen, J.,
Männistö, T., &
Sulonen, R.
(1998).
Towards a general ontology of configuration.
Artificial Intelligence for Engineering Design, Analysis and
Manufacturing
12(4),
357–372.Google Scholar
Stumptner, M.
(1997).
An overview of knowledge-based configuration.
AI Communications
10(2),
111–125.Google Scholar
Stumptner, M.,
Friedrich, G., &
Haselböck, A.
(1998).
Generative constraint-based configuration of large technical
systems.
Artificial Intelligence for Engineering Design, Analysis and
Manufacturing
12(4),
307–320.Google Scholar
Swartout, B. &
Gil, Y.
(1995).
EXPECT: Explicit representation for flexible acquisition.
Proc. 9th Knowledge Acquisition for Knowledge-Based Systems
Workshop (KAW-95).
VanHarmelen, F.,
Patel–Schneider, P., &
Horrocks, I.
(2001).
A Model–Theoretic Semantics for DAML+OIL.
Available on-line at www.daml.org.
Weida, R.
(1996).
Closed terminologies in description logics.
AAAI Fall Symposium 1996, pp.
11–18.
Wright, J.,
Weixelbaum, E.,
Vesonder, G.,
Brown, K.,
Palmer, S.,
Berman, J., &
Moore, H.
(1993).
A knowledge-based configurator that supports sales, engineering,
and manufacturing at AT&T Network Systems.
AI Magazine
14(3),
69–80.Google Scholar
Yokoo, M.,
Durfee, E.,
Ishida, T., &
Kuwabara, K.
(1998).
The distributed constraint satisfaction problem.
IEEE Transactions on Knowledge and Data Engineering
10(5),
673–685.Google Scholar
An example of a configuration model.
The part–whole relationship (p, part; w, whole).
The navigation paths from Computer to CPU1 and IDEUnit.
The ports in the configuration model.
The cable connections of a Siemens EWSD telecommunication system.
The overall CAWICOMS architecture.
You have
Access
- 53
- Cited by