We develop a principled approach to configuration that targets Answer Set Programming by integrating established concepts in a uniform setting. We begin by defining an abstract specification of configuration problems, drawing on concepts from the literature. We define both, user requirements and configuration solutions, as (partial) instantiations of a configuration model, and require the latter to be an extension of the former. The core of our configuration models comprise a partonomic structure which is adorned with constraints over atomic and aggregated attributes. Driven by this principled approach, we then develop a domain-independent ASP encoding for configuration.
the latter is required to be an extension of the former. The core of our configuration models comprise a partonomic Configuration has been a central topic in AI since several structure which is adorned with constraints over atomic decades [1, 2, 3]. Early on already, non-monotonic for- and aggregated attributes. malisms emerged as a promising alternative for modeling Driven by this principled approach, we then develop a configuration problems [ 4]. Nowadays, this role is filled domain-independent ASP encoding for configuration. by Answer Set Programming (ASP) [5], a non-monotonic The paper is structured as follows. In section 2 we problem solving paradigm, combining an easy, rule-based formally define a configuration problem and its solutions. modeling language with high performance solving ca- Section 3 discusses how constraints and aggregation of pacities [6, 7]. Over the years, this has led to several values are handled. In section 4 we present the ASP fact applications of ASP to configuration problems, among format and encoding and show how to solve configurathem [8, 9, 10] and notably the ASP-based configuration tion problems using the ASP solver clingo. Section 5 gives systems WeCoTin [11] and VariSales [12]. an overview of related work and section 6 concludes the
Our objective is to develop a principled ASP-oriented paper. approach to configuration, which integrates established concepts from configuration in a uniform setting. However, while ASP usually strives for generality, aiming at 2. Configuration problem and problem encodings covering the greatest possible class of solutions problems, many approaches to configuration appear to be more down-to-earth, targeting more specific classes of configuration problems. Hence, as an intermediate step, we begin by defining an abstract specification of configuration problems, drawing on concepts borrowed from [13, 2, 14]. More precisely, we describe configuration problems in terms of a configuration model, user requirements and resulting configuration solutions [ 15].
Both user requirements and solutions are defined as (partial) instantiations of the configuration model [ 13], where
models along with one of their (partial) instantiations. Formally, both are expressed in terms of (directed) multigraphs;1 the model’s graph delineates the ones capturing partial instantiations. User requirements and solutions are both represented by instantiations.
A configuration problem is a pair (, ). A simple example is given in Figure 1. The (configuration) model is a tuple ( , , , , , , , , de, at , co), where 1. ( , , , ) is a multigraph, where a) is a set of types, b) = ∪ is a partition of ports, where i. is a set of partonomic ports, ii. is a set of connection ports, frame p1 p3 rearWheel
p2 frontWheel
bag p4 p5 bag Bag bike a1 a2 wheel2
to ( , , , ) as the partonomy (graph); its root represents the configured object.
An example of a model graph is given on the For simplicity, we sometimes drop the subscripts of left in Figure 1. It consists of four types, = and and simply write , when clear from the type {Bike, Frame, Wheel , Bag }, linked by five partonomic of argument. ports, viz. = {1, 2, 3, 4, 5} with source An example instantiation of the configuration model (1) = (2) = (3) = Bike, (4) = Frame, in Figure 1 is given on its right. It includes ob(5) = Wheel and target (1) = Frame, (2) = jects = {bike, wheel1 , wheel2 , bag1 , bag2 } whose (3) = Wheel and (4) = (5) = Bag . The cor- relationships are fixed via the associations = responding descriptors are (1) = frame, (2) = {1, 2, 3, 4} with source (1) = (2) = frontWheel , (3) = rearWheel and (4) = bike and (3) = (4) = wheel1 , and target (5) = bag . Note that two ports can have the same (1) = wheel1 , (2) = wheel2 , (3) = descriptor as long as their source type is diferent. In bag1 , and (4) = bag2 . The actual instantiusual graph terminology, this amounts to two edges ation of the configuration model is warranted by (Bike, Wheel ) labeled with frontWheel and rearWheel , functions and . The object mappings are (bike) = Bike, (wheel1 ) = (wheel2 ) = Wheel , and (bag1 ) = (bag2 ) = Bag . The association mappings are (1) = 2 and (2) = 3, and (3) = (4) = 5. There are no corresponding objects and associations for type Frame and partonomic port frame, respectively. This shows that partial instantiations are fully admissible.
The other components of instantiations are detailed in Section 3.
Finally, a valid instantiation of satisfies the following conditions: of ′. That means all components of are also subsets of and thus ≺ . It follows that ∈ (, ).
The objects in a valid instantiation must satisfy all associated constraints in the underlying configuration model. 1. All constraints in co(()) are satisfied for all Apart from the structural constraints imposed by the ∈ , and model graph, additional constraints can be imposed on 2. the subgraph (, , , ), where = { ∈ objects (in the instantiation) via their types. | () ∈ } is the set of all parto- As an example, consider Figure 2 showing the model nomic associations, is a tree with root ∈ graph from Figure 1 but with attributes and constraints. such that () is the (partonomic) root of The model is extended by a set of constraints = ( , , , ). {1, 2, 3, 4, 5, 6}, assigned to their corresponding The satisfaction of constraints is detailed in Section 3. types, viz. (Bike) = {1, 2, 3}, (Wheel ) = The first condition ensures consistency of the instan- {4, 5}, and (Bag ) = {6}. tiation while the second guarantees that it is indeed a The attributes are assigned to their types as follows configuration of the object in focus where every non-root (Bike) = {(maxWeight , ⊤), (minStowage, ⊤), object is a part of exactly one other object. (totalWeight , 1), (stowage, 2)},
For comparing instantiations in terms of partiality, we view all components as sets (i.e., functions as relations) (Wheel ) = {(size, ⊤), (weight , ⊤)}, and and compare them with set inclusion. Accordingly, we (Bag ) = {(volume, ⊤), (weight , ⊤)}. say that an instantiation ′ is an extension of another , written ≺ ′, if all components of are subsets of the ones of ′. In this way, we may pose a configuration problem (, ) as a configuration model along with user requirements expressed as a (partial) instantiation of . We define the set of solutions to (, ) as Here ⊤, 1, 2 ∈ are evaluators whose function is explained later in this section. While constraint 1 guarantees that the front and rear wheel of a bicycle have the same size, constraints 2 and 3 assure that the values of the total weight and stowage of the bike lie within some (possibly user-requested) range. Constraints 4 and 5 specify possible combinations of the attributes of the (, ) = { | is a valid instantiation of wheels and bags. Lastly, constraint 6 expresses that only and ⪯ } . small bags can be attached to a wheel.
We represent constraints in their canonical form as This assures the user requirements are included in any tables. For illustration of how table constraints work, solution; invalid user requirements or ones which cannot consider the instantiation in Figure 3 and constraint be extended to a valid instantiation may lack solutions. 1 ∈ ((bike)) from Figure 2. This constraint is ex
A minimal solution of some user requirements is pressed as an equality but can easily be rewritten as a a valid extension ≺ such that there is no valid table containing all combinations which satisfy the given instantiation ′ with ≺ ′ ≺ . relation. The constraint describes compatible values of
One might wonder why a rigourous specification of the attribute size of Wheel at paths frontWheel and rearconfiguration problems as shown above is necessary. Wheel of Bike.
Such a specification allows us to show properties of our To make this relation precise, we rely on path expresformalism. For example, there is a simple proof that the sions leading from the type at hand to the attributes in solution space behaves monotonically for a fixed model. focus. In our example, they are given in the header of Proposition 1. Let be a fixed configuration model. the table constraint. Notably, given that this structure is Then for any user requirements and ′ it holds that mirrored in corresponding instantiations, the path expres ≺ ′ implies (, ′) ⊆ (, ). sions also allow us to access the values of these attributes from each object of the type at hand.
Proof. Take any ∈ (, ′). Per definition is valid More precisely, a path expression is a finite sequence and ′ ≺ , that is, all components of ′ are subsets of . of descriptors. We distinguish path expressions only inWe also have ≺ ′ so all components of are subsets cluding port descriptors in , and the ones consisting c1 (frontWheel,size) == (rearWheel,size) c2 (totalWeight) <= (maxWeight) c3 (stowage) >= (minStowage)
Bike totalWeight = sum((*,weight)) stowage = sum((*,volume)) maxWeight minStowage Frame 1
frame bag
{0,1,2} 100 250 600 1200 c6 (volume) (weight) 10 20 50 100 bike rearWheel
1 frontWheel {0,2} bag 1 Wheel size weight Bag volume weight c4 (size) (weight) 22 24 27 29 1800 1900 2100 2200 c5 (bag,volume) 10 20 {(′, +1) ∈ | ′ ∈ sel ((1, . . . , ))} if +1 ∈ and ∈ for 1 ≤ ≤ .
In our example, for constraint 1 ∈ ((bike)) we
get
sel bike ((frontWheel )) = {wheel1 }
sel bike ((rearWheel )) = {wheel2 }
sel bike ((frontWheel , size)) = {(wheel1 , size)}
sel bike ((rearWheel , size)) = {(wheel2 , size)} . (
With this, a table constraint is a pair ((⃗1, . . . , ⃗), ) tinue the illustration of constraint 1 ∈ ((bike)) where each ⃗ is an attribute path expression for given by 1 ≤ ≤ and ⊆ is an -ary relation over .
We use path expressions to select objects as well as at- (((frontWheel , size), (rearWheel , size)), tribute variables. For an object ∈ and ≥ 0, we {(22, 22), (24, 24), (27, 27), (29, 29)}) define sel ( ) = {} for the empty path sequence . sel ((1, . . . , , +1)) = {′ ∈ | ∈ , () = ′, () ∈ sel ((1, . . . , )), de(()) = +1} if +1 ∈ and ∈ for 1 ≤ ≤ .
(
(
(
The constraint illustrated above imposed a relation on constraint and auxiliary attribute, we often denote this attributes with atomic values. In addition, we want to by just adding “{0, 2}” to the correponding arrow. Note account for attributes taking aggregated values. For ex- that unlike above, the aggregator relies on a port path ample, the weight of a wheel is (usually) explicitly given, expression, yielding the bags bag1, bag2 for wheel1 and while that of an entire bike must be calculated from the no objects for wheel2. Accordingly, the value of attribute weights of its components. Also, we can use calculated #bags of wheel1 (resp. wheel2) is 2 (resp. 0). This is among attributes for enforcing port multiplicities, as we show the admissible values of the constraint imposed by Wheel. below. To this end, we allow for attributes whose value is either assigned or calculated via aggregate functions, like addition or maximum. We address this via the evaluators 4. An ASP-based solution to in along with a refinement of the valuation function . configuration problems As above, we rely on path expressions for selecting the values subject to aggregation. For brevity, we refrain from giving an introduction to
Accordingly, an evaluator ∈ is either ⊤, in- ASP. Full details on the input language of clingo along dicating that an atomic value is assigned, or a pair with various examples can be found in the Potassco User ((⃗1, . . . , ⃗), ) where each ⃗ is a path expression for Guide [16]. 1 ≤ ≤ and is an aggregate function. Aggregate functions are defined on sets and yield an element 4.1. Configuration model fact format from . When the input is the empty set, this is their neutral element, e.g., 0 for the function sum. 1 type((bike;wheel;frame;bag)).
Given ∈ , we define for (, ) ∈ at (()) ((, )) = {︃ ∈ ︁( ⋃︀ =1 sel (⃗)︁) if = ⊤ if = ((⃗)=1, )
For simplicity, we often write = (⃗1, . . . , ⃗)
whenever (, ((⃗1, . . . , ⃗), )) ∈ at () for some type
∈ . For example, in Figure 2 consider the
attribute calculating the total weight of a bike indicated by
totalWeight = sum((*,weight)). In the above notation, this
corresponds to attribute (totalWeight , 1) ∈ (Bike),
with evaluator 1 = ((* , weight ), sum). The expression
(*,weight) is syntactic sugar for all attribute path
expressions pointing to an attribute weight, here expanding to
the sequence
Listings 1-4 display a snippet of the encoding
representing the bike example from Figure 2. A part of the
model graph is encoded in Listing 1. Types are
declared via a type/1 atom where the argument is the
name of the type. Parts are declared via a part/3 atom
with source and target type and port descriptor as
arguments. The corresponding multiplicites are encoded
via a multiplicity/4 atom with the same structure as
the part/3 atom plus all possible multiplicities as fourth
argument.
1 attr(wheel,size). 1 constraint((wheel,0)).
2 dom(wheel,size,(22;24;27;29)). 2 column((wheel,0),0,(size,())).
3 attr(wheel,weight). 3 column((wheel,0),1,(weight,())).
4 dom(wheel,weight,(1800;1900;2100;2200)). 4 entry((wheel,0),(0,0),22).
Listing 2: Facts representing the Wheel attributes of the 5 entry((wheel,0),(
Listing 2 contains the encoding of attributes size and 8 entry((wheel,0),(
Listing 4: Facts representing a table constraint of the bike
example from Figure 2 4.2. General problem encoding 1 attr(bike,totalWeight,"sum"). 2 path(bike,totalWeight, 3 ((weight,(frontWheel,())); 4 (weight,(rearWheel,()))); 5 (weight,(bag,(frontWheel,()))); 6 (weight,(bag,(rearWheel,()))); 7 (weight,(bag,(frame,())))).
Listing 5. In Lines 1-6 it is checked that the configuration model graph is indeed acyclic and rooted. Further, the type of the root object is determined which is created Listing 3: Facts representing a calculated attribute of the in Line 8 (with the correct type as second argument). In bike example from Figure 2 Lines 10-12 objects for each part relation are generated Listing 3 contains the encoding of the calculated at- while making sure that the indices of the objects are astribute totalWeight from type Bike. Calculated attributes signed incrementally. Satisfaction of the multiplicites of are declared via an attr/3 atom. The structure is the those part relations are assured in Lines 14-15. In Lines 17same as attr/2 atoms plus the aggregate function as 19 values are assigned to attribute values according to third argument (currently sum, count, min and max are their domain making sure that each object has exactly one supported). The corresponding path expressions which value assigned for all its attributes. All possible port and are used to gather all values are declared via path/3 attribute selectors are created in Lines 22-24. Using seatoms. The first two arguments have to be the same lectors, the correct values for aggregates are determined as the attr/3 atoms and the third argument is a path and assigned. In Lines 26-27, we show the encoding for expression. Path expressions follow a nested tuple struc- one such aggregate function sum. Our full implementature in ASP with the first element of the sequence being tion which can be found under https://github.com/ the innermost. Consider for example the path expres- potassco/configuration-encoding also contains sion (1, 2, 3) in the formalism. We express this in the aggregate functions count, min and max. Lastly, in ASP as (d3,(d2,(d1,()))). While this is not easily Lines 29-42 table constraint satisfaction is checked for readable for humans, it enables one to work dynamically each object. First, all possible tuples of the cross product with tuples of any size in ASP. In the future, we plan are created (encoded again as nested tuples). Then the to implement an input and output language which is tuples are unpacked step-by-step while traversing the human-readable and leave the nested tuple structure for columns of the constraint. Only if all tuples satisfy at internal representation. least one complete row, the constraint is satisfied.
Constraints are declared via a constraint/1 atom Due to space limitations, we are not showing the full where the argument is a constraint identifier . In Listing 4 implementation of our formalization. As mentioned an example of a table constraint is shown. The identifier above, we are only showing the aggregate function sum. is a tuple consisting of the type the constraint is attached Additionally, we left out connection ports and comparito and an index. The columns of the table are declared via son constraints (e.g., ==, ≤ , etc.) in Listing 5. In our full column/3 atoms containing the constraint identifier, the encoding we also distinguish between mandatory objects index of the column and the path expression. The actual (encoded by normal rules) and optional objects encoded entries are declared via entry/3 atoms containing the by choice rules by which we hope to achieve a better constraint identifier, a tuple with the index of the column performance. In addition to that, several examples and and row, and the value of the entry. ifles to visualize configuration models and instantiations using clingraph [17] can be found in the repository linked earlier. 1 partonomic_path(X,Y) :- part(X,Y,_). 2 partonomic_path(X,Z) :- partonomic_path(X,Y), partonomic_path(Y,Z). 3 :- partonomic_path(X,X). 5 root(T) :- type(T), not partonomic_path(_,T). 6 :- {root(T)} > 1. 8 object((),T) :- root(T). 10 { object((D,(O,I)),T) : I = 0..Max-1 } :11 object(O,S), part(S,T,D), Max = #max { N : multiplicity(S,T,D,N)}. 12 :- object((D,(O,I)),_), not object((D,(O,I-1)),_), I > 0. 14 :- part(S,T,D), object(O,S), not multiplicity(S,T,D,X), 15 X = #count { I : object((D,(O,I)),T) }. 17 { val((O,D),V) : dom(T,D,V) } :- object(O,T), attr(T,D). 18 :- attr(T,D), object(O,T), not val((O,D),_). 19 :- val(X,V1), val(X,V2), V1 < V2. 21 attr(T,D,"atomic") :- attr(T,D). 22 selector(O,(),O) :- object(O,_). 23 selector(O,(D,P),(D,(O’,I))):- selector(O,P,O’), object((D,(O’,I)),_). 24 selector(O,(D,P),(O’,D)) :- selector(O,P,O’), object(O’,T), attr(T,D,_). 26 val((O,D),V) :- object(O,T), attr(T,D,"sum"), 27 V = #sum { V’,X,P : path(T,D,P), val(X,V’), selector(O,P,X) }. 29 max_col_idx(C,N) :- constraint(C), N = #max{ Col : column(C,Col,_)}. 30 tuple((O,C),N,((),X)) :- object(O,T), max_col_idx((T,C),N), 31 selector(O,P,X), column((T,C),N,P). 32 tuple((O,C),N,(VT,X)) :- object(O,T), tuple((O,C),N+1,VT), 33 selector(O,P,X), column((T,C),N,P), N>=0. 35 sat_row((O,C),VT,(0,Row),VT’) :36 object(O,T), tuple((O,C),0,VT), VT = (VT’,X), 37 val(X,V), entry((T,C),(0,Row),V). 38 sat_row((O,C),VT,(Col,Row),VT’’) :39 object(O,T), sat_row((O,C),VT,(Col-1,Row),VT’), 40 VT’ = (VT’’,X), val(X,V), entry((T,C),(Col,Row),V). 42 :- tuple(C,0,VT), not sat_row(C,VT,_,()).
Listing 5: ASP encoding for solving configuration problems. 4.3. Instantiation fact format and object((bag,((frontWheel,((),0)),1)),bag). obtaining solutions This correponds to the second bag of the first (and only) wheel with descriptor frontWheel of the root object On the instantiation level, there are two important (which has type Bike). The root is always encoded as an atoms object/2 and val/2. They represent objects empty tuple (). Note that this way of encoding objects and the valuations of attribute variables, respec- directly assures that the set of partonomic associations tively. The object/2 atom takes as arguments the is a tree as required for valid instantiations. name of the object encoded as a nested tuple and The val/2 atom takes as first argument an attribute its type. The nested tuple structure is similar as variable encoded as a tuple. The tuple contains the object for path expressions above (see Section 4.1). The name and the attribute descriptor. The second argument names are constructed from the partonomic port of the atom is the actual value of the variable. For exdescriptors and indices. Take for example the atom ample, we have the atom val(((),minStowage),30) which expresses that attribute minStowage of the root configuration solution knowledge and requirements knowlobject bike has value 30. edge. However, the paper argues that the latter can be
We can run the encoding together with the file of a expressed in terms of the other two. In the model knowlmodel to obtain one or multiple stable models. The sta- edge there are product specific classes called types and a ble models correspond to valid instantiations as defined configuration of a product w.r.t. to a configuration model in Section 2. This is easy to verify, as (table) constraints is defined as a set of instances of the types occurring in are encoded as integrity constraints in ASP, thus have the model. These instances are called individuals. Conto be satisfied in every stable model. Further, as men- straints are specified inside the model and a correct contioned above our object structure directly assures that figuration must satisfy these. However, the definition of the set of partonomic associations is a tree and that the constraints is left to an unspecified constraint language. root object has the type of the partonomic root of the A configuration also contains configuration specific relamodel graph. We can also specify user requirements by tions called properties. Unlike our approach, [13] includes providing, e.g. another input file instantiation.lp. the concepts of taxonomy and inheritance. Every instantiation obtained in form of a stable model Another formal approach to configuration in the conthen extends the user requirements and is therefore a text of constraint programming has been given by [2]. solution to (, ). Here, a structural configuration model lays out the possi
In Listing 6 we run our full encoding with the model ble variations of the entity to be configured. This model from Figure 2. The user requirements are empty, i.e., contains types and attributes, as well as partonomic and omitted, and the solution we obtain corresponds to the connection ports. Types can be functional or technical one from Figure 3. and this restricts the possible kinds of (taxonomic) sub$ clingo encoding.lp examples/bike/model.lp types they are allowed to have. Technical types can only clingo version 5.6.2 have concrete types as subtypes which can be seen as Reading from encoding.lp ... "complete" parts ready to be ordered from a catalog. A Solving... configuration can be obtained from a structural model by Answer: 1 instantiating types. Instances inherit the attributes and oobbjjeecctt((((f),rboinkteW)heel,((),0)),wheel) ports from their type and all its supertypes. As to what reobject((rearWheel,((),0)),wheel) gards constraints, three kinds are defined: compatibility, object((frame,((),0)),frame) requirement and resource constraints. object((bag,((frontWheel,((),0)),0)),bag) Lastly, [14] follows a somewhat less formal, objectobject((bag,((frontWheel,((),0)),1)),bag) oriented approach at modelling configuration problems vvaall(((((()),,mmianxSWteoiwgahgt)e,),503000)) where concepts are directly defined in ASP. Again, there val(((frontWheel,((),0)),size),27) is a distinction between a model and an instantiation. val(((rearWheel,((),0)),size),27) The model contains a taxonomy of classes and a general val(((frontWheel,((),0)),weight),2100) association relation (with no distinction between part and val(((rearWheel,((),0)),weight),2100) connection relations). It is noteworthy, that associations val(((,b2a0g),((frontWheel,((),0)),0)),volume) in general have multiplicities in both directions. Further, val(((bag,((frontWheel,((),0)),0)),weight) attributes are limited to be over the domain of strings, ,250) integers or booleans. In an instantiation of a model, each val(((bag,((frontWheel,((),0)),1)),volume) object is defined through a global index. An "is-a" relation ,10) ties it to a class. Two objects are connected through val(((,b1a0g0,)((frontWheel,((),0)),1)),weight) an "associated" relation which has to correpond to an val(((),stowage),30) association relation from the model. Attribute values val(((),totalWeight),4550) assign values to attributes of objects. Constraints are SATISFIABLE not specified directly but left open to general integrity constraints in ASP.
clingo
5. Related work We presented an approach to model and solve configuration problems and a corresponding encoding for ASP.
Our formalism borrows concepts from various other ap- A model and its instantiation are expressed through diproaches in the literature. A general ontology of configu- rected multigraphs where the former specifies the posration has been introduced in [13]. Here, a configuration sible graphs of the latter. Similar to [2], the partonomy problem is divided into configuration model knowledge , of the model graph has to be acyclic. We view this as favorably for object generation. what other properties our formalism possesses.
Apart from the structural constraints imposed by the Partly due to this abstractness, we decided to start with model graph, each type in the model may impose con- a simpler approach exluding a taxonomy and thus a form straints on itself and its parts. For this we use table of inheritance. However, we view both these concepts constraints as a canonical representation which spec- as vital for eficiently modelling configuration problems ify possible combinations of attributes. In our view, table and we plan to extend our formalism to contain them. constraints are the most general form of constraints and This would probably require the following steps: other kinds can be expressed through them. Constraints attached to a type are checked independently for each 1. Itnytpreo"drueclaettiaoxno. nFoomlloicwpionrgts[r2e]p,roeusrenactiyncgliaci"tysucpoenr-object of that type. This guarantees that they are only dition would be extended to consider these ports applied in the correct context. as well.
Attributes can be atomic, i.e., a value needs to be assigned, or calculated. For the latter we make use of ag- 2. Adapt the definition of a valid instantiation. Now gregate functions. We also formalized the concepts of the root object of the model graph does not necpath expressions and selectors. The former can be com- essarily represent the object to be configured but posed of port or attribute descriptors and the latter return could be specialized to a subtype. There might not sets of attribute variables or objects. While port multi- even be a partonomic root anymore. In general, plicites are unbounded in general, we can use aggregate it should be possible to start the configuration functions and port path expressions to restrict them. at any node of the model graph which could be
In contrast to many other approaches, we cannot target expressed through user requirements and a dedispecific objects in the instantiation with our constraints. cated "root object" in the instantiation. For example, in Figure 3 it would not be possible to attach 3. Types would inherit attributes and other types a constraint to the type Wheel targeting only bag1. This is of ports from their supertypes, i.e., constraint because there is no selector starting at wheel1 containing satisfaction would have to be checked not only this bag only. Note that sel wheel1 ((bag )) returns the set for the type an object is mapped to but also for {bag1 , bag2 } with both bags. This was done on purpose all its supertypes. to evade symmetries. Our understanding is that if dis- 4. A more dificult question is how to treat attributes tinctions between objects are desirable, this information and (non-taxonomic) ports which appear more should be included in the model, e.g., by having separate than once for a set of supertypes or if this should ports as for the front and rear wheel. be prohibited.
In many scenarios it is desirable to configure multiple Lastly, we note that in many examples a taxonomy only instances of the same type simultaneously. Since we appears in form of "specializations" (such as concrete require every configuration to be rooted, this might not types and catalogs in [2]). This feature can be represented appear possible within our approach. However, one could in our formalism by adding table constraints (see for always add a new root type to the model, for example a example constraint 4 in Figure 2 describing the possible Fleet of bikes. wheels).
A shortcoming of our formalization is that we require Further, we plan to further study connection ports by the attribute valuation function to be total, i.e., every working out examples. They are part of the literature [2] instantiated attribute variable needs to have a value as- and we view them as an important complement to partosigned. In user requirements, though, it might be desir- nomic ports since they convey additional information able to leave certain attributes undefined. and allow to form cycles in the model graph. Consider
Further, there are user requirements which cannot be the configuration of a computer network. Here, a configexpressed through an instantiation. For example, con- uration might have identical parts like switches which sider Figure 2 and a user who wants all bags to be of a can be connected in numerous ways. We also intend to certain color but does not care about the number of bags. investigate symmetry conditions for connection ports This would require adding a new constraint to the model. which currently do not seem to be expressible within our Anyhow, we consider this to be more of a knowledge formalization of constraints. engineering problem as any such option should only be On the implementation level, our full encoding curavailable if included in the model. rently supports table and comparison constraints. In the
Compared to many other approaches that are tuned literature other kinds such as requirement and incomfor practical applications, our approach is more abstract. patibility constraints often occur. We plan to study how This allows us to formally prove properties as we have these can be represented in our formalism and to add demonstrated with the monotonicity of the solution them to our implementation. space. Experience has shown that this is important when working with ASP. In the future, we intend to investigate