The area of product configuration has witnessed a growing demand for systems that can efectively guide users through the configuration process. These systems facilitate interactivity during configuration by combining user actions with automatic solving. In this paper, we present an API that fulfills the basic requirements of interactive configuration. Our implementation is based on the OOASP framework for object-oriented configuration in Answer Set Programming (ASP), leveraging multiple features of the ASP system clingo to dynamically introduce components.
applications of Answer Set Programming (ASP [
Industrial product configuration deals with large
problems. For example, even small infrastructure projects may
contain thousands of components and hundreds of
component types. Such configurations are typically solved
step-by-step by combining interactive actions with
automatic solving of sub-problems [
Using a grounding-based formalism like ASP in this
context introduces the risk of a grounding bottleneck
[
In this work, we present an Application Programming
Interface (API) to satisfy basic requirements for
interactive configuration [
After covering background on ASP, product configuration and OOASP, and on our running example in Section 2, we introduce our approach in detail in Section 3. The paper concludes with a discussion in Section 4.
A logic program consists of rules of the form a1;...;a :- a+1,...,a,
not a+1,..., not a. where each a is an atom of form p(t1,...,t) and all t are terms, composed of function symbols and variables. For 1 ≤ ≤ ≤ , atoms a1 to a are often called head atoms, while a+1 to a and not a+1 to not a are also referred to as positive and negative body literals, respectively. An expression is said to be ground, if it contains no variables. As usual, not denotes (default) negation. A rule is called a fact if = = = 1, normal if = 1, and an integrity constraint if = 0. In what follows, we deal with normal logic programs only, for which is either 0 or 1. Semantically, a logic program induces a set of stable models, being distinguished models of the program determined by the stable models semantics [8].
To ease the use of ASP in practice, several extensions
have been developed. First of all, rules with variables
are viewed as shorthands for the set of their ground
instances. Further language constructs include conditional
literals and cardinality constraints [9]. The former are
1https://potassco.org/clingo
of the form2 a:b1,...,b, the latter can be written as3 configuration problems, a dynamic number of
compos {d1;...;d} t, where a and b are possibly negated nents plays an important role [12].
(regular) literals and each d is a conditional literal; s OOASP4 [
A particular convenience feature are anonymous vari- coding of models, and Table 2 shows the OOASP-DDL ables, denoted uniformly by an underscore ‘_’. Each predicates for the encoding of instantiations.5 underscore in a rule is interpreted as a fresh variable. OOASP constraints are defined using the predicate In turn, atoms with anonymous variables are replaced ooasp_cv (“cv” stands for “constraint violation”). Rules by new atoms dropping these variables; the new atoms with head atoms of this predicate are used instead of are then linked to the original ones by rules expressing ASP constraints to enable configurations to be checked, projections. i.e., to derive which constraints are violated in a given
Multi-shot solving allows for solving continuously configuration (Listing 4). To enforce a configuration to be changing logic programs in an operative way. In clingo, consistent, a simple ASP constraint forbidding ooasp_cv this can be controlled via an API for implementing reac- to be true can be added. An ooasp_cv atom contains tive procedures that loop on grounding and solving while four terms: a unique constraint identifier, the identifier of reacting, for instance, to outside changes or previous solv- the faulty object, a string containing a message describing ing results. This is supported by two directives. First, a the issue, and a list of additional explanatory terms. program can be partitioned into several subprograms by OOASP distinguishes integrity constraints from means of the directive #program; it comes with a name domain-specific constraints. The former are defined in and an optional list of parameters. Such subprograms can the OOASP framework itself and refer to issues such as then be grounded upon demand and added to the solver. invalid values and violations of association cardinalities. Second, #external directives allow for declaring atoms Domain-specific constraints can be defined by a user of whose truth value can be set via the API and/or rules that OOASP in the same format. may be added later on. This allows us to continuously An instantiation (configuration) defined by the predassemble ground rules evolving at diferent stages of a icates from Table 2 is complete if every object is an inreasoning process and to change program behavior by stance of an instantiable class, and it is correct if no manipulating the truth values of external atoms via the constraint violations can be derived from it. We follow API. the convention that only leaf classes (i.e., classes that
Full details on the input language of clingo along have no subclasses) are instantiable, so every object must
with various examples can be found in the Potassco User be an instance of a leaf class in a complete configuration.
Guide [10]. Configuration is usually an interactive task, iteratively
involving user interactions (decisions) and automatic
rea2.2. Product Configuration and OOASP soning by a solver, e.g., an ASP solver [
3More elaborate forms of aggregates are obtained by explicitly
using function (e.g. #count) and relation symbols (e.g. <=) [10].
4https://github.com/siemens/OOASP
5We here present a version of OOASP-DDL that has already
evolved from the original definition [
Additionally to the constraints implied by the UML diagram, the following constraints hold for the domain:
Python, relying heavily on multiple features provided by clingo’s Python API, as well as the systems clorm6 and clingraph. Clorm is a Python library providing an Object • An ElementA/B/C/D requires exactly 1/2/3/4 ob- Relational Mapping (ORM) interface to clingo, which we jects of type ModuleI/II/III/IV use to map the OOASP predicates defining the knowledge • Instances of ModuleI/II/III/IV must be required base and the configuration into Python classes. These by exactly one Element elements are then visualized as graphs (resembling UML • A SingleRack/DoubleRack has exactly 4/8 Frames diagrams) using clingraph. For interactive configuration, • A Frame containing a ModuleII must also contain we created a scientific prototype User Interface (UI) using exactly one ModuleV ipywidgets that employed our CAPI functionalities.
The running example captures the essence of a typical The basic idea behind our approach is to modularize configuration knowledge base in an industrial setting. the encodings so that the program can be built increOf course, real life industrial knowledge bases are much mentally as the number of instantiated objects in the larger (>100 classes, associations, attributes). And the configuration increases based on user interaction. To constraints of the domain will vary considerable depend- that end, we use the multi-shot capabilities of clingo ing on additional requirements imposed by the customer, to solve these continuously changing logic programs. regulations, geographic location, etc. Notice that the This approach avoids re-grounding and benefits from knowledge base does not contain any restrictions on the learned constraints by grounding and solving on demand. number of objects in a configuration or on the order in More specifically, we defined subprograms that depend which objects must be created. on the identifier of each newly introduced object, namely
Another property of these knowledge bases is that the new_object. Therefore, whenever the domain size is number of objects required for a solution is not known extended by a new object, all the rules referring to this beforehand. For example, suppose the user interactively object are grounded. In this sense, our implementation created 5 objects of type ModuleI. The user could assign those modules to the same frame and assign the frame to 6https://github.com/potassco/clorm difers from the previous work [ 15], in which subprograms were subject to domain-specific actions.
from [
T3. Setting and un-setting values for attributes. 1 #program domain(new_object). 2 #external user(ooasp_attr_value(A,new_object,V)): 3 ooasp_attr_enum(_,A,V). 4 ooasp_attr_value(A,new_object,V) :5 user(ooasp_attr_value(A,new_object,V)).
object will not have a type; its type will be set explicitly by the user with T1 or by the system with T5.
Finally, we identified three reasoning tasks in which solving is necessary.
T5. Using the current objects to generate from
via choice rules.7 T6. Checking if is complete or if it violates any
constraints.
T7. Obtaining the list of available edit-options for the user via brave reasoning.
Such tasks are done using external atoms in clingo, so that no re-grounding is required. Due to lack of space, we will focus only on the encoding of task T3. Tasks T1 and T2 are encoded in a similar way. We show in Listing 1 how the user input is handled for task T3. Line 1 corresponds to clingo’s program directive indicating that the subprogram depends on new_object. Thus, all the following rules will be grounded on demand when a new object is introduced. Lines 2 and 3 define an external atom user(ooasp_attr_value(A,new_object,V)) for each attribute A and value V of the new_object. Notice that we need to generate all possible combinations since the object can be assigned to any class. The truth value of these externals will be set based on the user’s selection. Finally, the rule in Lines 4 and 5 makes sure that if the user selected a value for an attribute it will be considered in the encoding.
These tasks are distinguished within the encoding via externals. The truth values of these externals is controlled internally depending on the task selected by the user. In this case, one external atom guess states that the guessing of objects’ types, associations and values is active. Two additional externals check_permanent_cv and check_potential_cv activate the integrity constraints for the two types of constraints. Constraints are divided in this way, since we need to take into consideration that we are building in an interactive and incremental way, therefore some of these constraints might be violated on but fixed once is reached.
The intuition for this decision can be taken from the ifelds of Runtime Verification and Monitoring, where a constraint is either satisfied , potentially violated (might or T4. Extending the configuration with a new object. might not remain a violation in the future) or permanently violated (a violation in all possible futures). Potential con
As mentioned before, the grounding of subprograms straint violations are those that can potentially be fixed by will exclusively occur when the user performs task T4. adding more information in a later stage of the process. Consequently, in the rest of the tasks the number of objects will remain fixed. Note that the newly introduced 7A choice rule is a rule with a cardinality constraint in the head. 1 1 { ooasp_attr_value(A,new_object,V): 2 ooasp_attr_enum(C,A,V) } 1 :3 ooasp_isa(C,new_object), 4 ooasp_attr(C,A,T), 5 ooasp_attr_enum(C,A,_), 6 guess. 1 ooasp_potential_cv(no_val). 2 ooasp_cv(no_val,new_object,"Missing value for {}",(A,)) :3 ooasp_attr(C,A,T), 4 ooasp_attr_enum(C,A,_), 5 ooasp_isa(C,new_object), 6 not ooasp_attr_value(A,new_object,_).
1 :- ooasp_cv(CV,_,_,_), 2 not ooasp_potential_cv(CV), 3 check_permanent_cv. 4 :- ooasp_cv(CV,_,_,_), 5 ooasp_potential_cv(CV), 6 check_potential_cv. straints of this type to be violated in while still getting a satisfiable answer. However, the permanent constraints should remain active since we want to discard anything that can’t be fixed by further interaction with the system.
Listing 3: Integrity constraints enforcing constraint With this set, we use the brave reasoning capabilities of violations clingo to obtain the union of all stable models, and thus, all the possible options for types, values of attributes, and associations.
For instance, a lower bound of an association that has As before, we use the attribute values to exemplify not been reached, or a value that is missing. These con- the use of task T7 in Listing 4. The rule in Lines 2 to straints are identified in the encoding with the predicate 6 derives the constraint violation no_val of having no ooasp_potential_cv. On the other hand, permanent value set for an attribute. As expected, this is a potential constraint violations refer to violations that can no longer constraint (expressed in Line 1) since the user can later on be fixed, such as upper bounds of an association or an select the missing value. The constraint violation is then attribute value of a wrong type. derived for any attribute of the new_object that has no
For task T5, guess, check_permanent_cv and corresponding value assigned via ooasp_attr_value. check_potential_cv are set to true in order to find a Some other checks might depend on values that have complete and valid configuration . This is achieved by to be recomputed on every grounding step, such as using choice rules to generate possible values, types and the arity of an association. In other words, if an agassociations for the objects, which are activated by the gregate #count is used to compute the objects assoexternal guess. If no can be found with the current ciated to new_object , it will only count the objects number of objects the result of the task will be UNSATIS- that are already grounded at that time. This means FIABLE. To illustrate this, Listing 2 shows the choice rule that the arity computed in previous steps must be disto select a value for an attribute. The rule can be read as regarded. Therefore, we need an additional external follows: if the new object is of type C (Line 3), where type active(new_object) that indicates the current step C has an attribute A (Line 4) with some elements in the to know if the aggregate’s value is older and thus expired. domain (Line 5), and the guessing is active (Line 6), then Notice that the current step corresponds to the object out of all the possible values for A choose a single value identifier that is being grounded at that time. V. Notice that this rule is also grounded incrementally and uses the corresponding new_object. T8. Extend incrementally to generate
For task T6, we set the externals Given all these functionalities, finding the smallest check_permanent_cv and check_potential_cv to that extends can be encapsulated into the combined false so that all the ooasp_cv atoms are part of the task T8. The program for task T8 will proceed following computed stable model, thus deriving the issues with an incremental approach: is extended with a new . In Listing 3 we show the integrity constraints object (T4) and then tries to generate (T5), these steps handling the constraint violations, which are also are repeated until a is found. grounded incrementally. Lines 1 to 3 make sure that no constraint violation is derived if the external 3.2. Performance check_permanent_cv is true and the constraint violation CV is not a potential but a permanent one. Knowing about the huge solution space, we improved efSimilarly, the second constraint (Lines 4 to 6) enforces ifciency right from the beginning by including symmetry potential constraints when check_potential_cv is breaking constraints which get rid of multiple symmetric true. configurations. The two symmetries identified can be
For task T7, we want to provide the user with valid found in Listing 5. Both symmetries correspond to actions from T1, T2 and T3. To achieve this, po- permutations of the classes assigned to objects. The tential constraints are ignored by setting the external constraint in Lines 1 to 6 ensures that the classes check_potential_cv to false so that we allow con- assigned to objects smaller than the new_object answer in a single call, comparable to the solving time taken for domain size 23 in Figure 2b. 3.3. User Interface Prototype 1 :- ooasp_isa_leaf(C1,new_object), 2 ooasp_isa_leaf(C2,ID), 3 ID<new_object, 4 C1<C2, 5 not user(ooasp_isa_leaf(C1,new_object)), 6 not user(ooasp_isa_leaf(C2,ID)). 8 :- ooasp_isa_leaf(_,new_object), 9 not ooasp_isa_leaf(_,ID), 10 ooasp_isa(_,ID), 11 ID<new_object.
screenshots (Figures 3,4) of the UI rendered in a Jupyter notebook for the racks examples from Section 2.3. This Listing 5: Symmetry breaking constraints UI has 6 sections. The section on the upper left corner shows the current using clingraph. To the right, the history of actions taken by the user is rendered as a list are also smaller. Notice that this is only applied to in the History section. In our example, the user started decisions made by the solver, excluding assignments with the first two actions being the extension of the domade by the user (Lines 5 and 6). Otherwise the user main by two new objects. This is done via the button setting the class of an object (via T1) could lead to in the Extend section below, corresponding to task T4. unsatisfiability. The constraint in Lines 8 to 11 makes Then, in steps 3 and 4, the user assigned classes to obsure that any objects left out from the configuration (with jects 1 and 2, respectively, using the Edit section. This no class assigned) are always those with larger ids. For section employs T7 to generate a dropdown for each obinstance, the assignment {(1, 1), (2, undef), (3, 2)} ject with the list of possible options (T1, T2, T3). Step 5 would be removed by the second constraint in corresponds to T6, triggered by clicking the button in the favor of {(1, 1), (2, 2), (3, undef)}. Similarly, Check section. This action prints in red the constraint {(1, 1), (2, 2), (3, 1)} would not be valid due to violations found for each object. In this case, Object 2 (the the first constraint, keeping the symmetric assignment frame) violates the missing value constraint from List{(1, 1), (2, 1), (3, 2)}. ing 4 and the lower-bound constraint, since it should be
We performed some empirical tests in the system to associated with one rack. Similarly, Object 1 (the instance check the performance based on the running example of RackSingle) is violating the lower-bound constraint, from Section 2.3. The aim of the first test was to gen- as well as a domain-specific constraint enforcing it to be erate a of size 41 with one RackSingle associated to associated to exactly 4 frames. For the last task, namely four Frames, each Frame with four associated Modules T5, the user must work on the Browse section of the UI. with one corresponding Element. First, we extended By clicking the button labeled “Next solution”, the system with 41 objects via T4 where 18 of those objects were would perform task T5. However, since there is no selected to be of the Element class. Then we used task with the current number of objects it would get an error. T5 to find our expected . Overall, these steps took As mentioned before, this is overcome by extending 7 seconds of grounding time and 3 seconds of solving. incrementally, which is done by task T8 in step 6 when At this point, any of the tasks T1, T2, T3, and T6 can the user clicks on “Find incrementally” (Figure 4). As be done without delay. However, obtaining the list of a consequence, the system will internally find and options with task T7 didn’t finish within 5 minutes. This render it in the bottom right. In this clingraph image, happened since the number of valid options is quite large the values from will appear in green. As a next step, when a user has 23 objects without an associated class. the user could either browse through all the possible In practice we expect this to decrease with a more tightly of the same size, or select the current as the new defined during the interaction. As a second test, we to be to be further edited. Notice that while browsing, analyzed task T8 by creating Element instances and no options are shown in the Edit section. This happens ifnding incrementally the corresponding . The results since we have a single clingo control object which is curcan be found in Figure 2a for ∈ {8, 9, 10}. When we rently in the middle of solving, thus, it can’t generate the increased to 11, the task didn’t finish within a 5 minute brave consequences of T7. time out. Looking closely at the performance for = 9 in Figure 2b, we can see that the issue lies on having to 4. Discussion prove unsatisfiability for domain sizes 9 to 22. Proving unsatisfiability implies going trough all the search space to make sure there is no answer, which is quite costly as the domain increases. In our test, this is the case when trying to find a non-existing with a domain size of 22 objects. This was not the case in our previous test where we have all the required objects to obtain a satisfiable
urator that enables engineers and salespeople, among other configurator users, to incrementally build configurations. Our contribution involves the development of an API built upon the OOASP framework and the clingo system. The OOASP framework provided us with a domain (a) Times starting from 8, 9 and 10 Elements. (b) The times for each call to task T5 for the given domain size, starting from 9 Elements. description language to encode models, instances, and solutions, while clingo’s multi-shot capabilities allowed us to dynamically extend the configuration by adding components on demand. The integration of this multi-shot approach to interactive configuration distinguishes our approach from previous work.
uration, we identified and implemented eight distinct tasks, which we described in detail. To demonstrate the functionality of our API, we developed a prototype user interface and showcased the step-by-step creation of a configuration using our running example. As the UI is currently in a prototypical stage, gathering real user feedback remains a future goal for subsequent versions of the system. To assess the performance of the system, we conducted empirical tests and identified the need for further improvements. In particular, we boosted eficiency by incorporating symmetry-breaking constraints.
However, we also encountered performance issues with our incremental approach when dealing with larger instances, which warrants future research. More specifically, we plan to explore alternative methods for extending the configuration beyond the one-by-one incremental process. For instance, we are interested in investigating scheduling techniques [16] and pre-computing the minimal number of required objects [17]. Additionally, we aim to enhance usability by incorporating additional advanced features, such as linear domains, which enable more sophisticated reasoning in the configuration process. gence, Springer-Verlag, 2015, pp. 332–345. doi:10. [17] M. Aschinger, C. Drescher, G. Gottlob, H. Vollmer, 1007/978-3-319-23264-5_28. Loco – A logic for configuration problems, ACM [7] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Trans. Comput. Log. 15 (2014) 20:1–20:25. doi:10.
Multi-shot ASP solving with clingo, Theory and 1145/2629454.
Practice of Logic Programming 19 (2019) 27–82.
doi:10.1017/S1471068418000054. [8] M. Gelfond, V. Lifschitz, Logic programs with classical negation, in: D. Warren, P. Szeredi (Eds.), Proceedings of the Seventh International Conference on Logic Programming (ICLP’90), MIT Press, 1990, pp. 579–597. [9] P. Simons, I. Niemelä, T. Soininen, Extending and implementing the stable model semantics, Artificial
Intelligence 138 (2002) 181–234. [10] M. Gebser, R. Kaminski, B. Kaufmann, M. Lindauer, M. Ostrowski, J. Romero, T. Schaub, S. Thiele, Potassco User Guide, 2 ed., University of Potsdam, 2015. URL: http://potassco.org. [11] A. Felfernig, L. Hotz, C. Bagley, J. Tiihonen (Eds.),
Knowledge-Based Configuration – From Research to Business Cases, Morgan Kaufmann, Boston, 2014. doi:10.1016/B978-0-12-415817-7.
00029-3. [12] A. A. Falkner, G. Friedrich, A. Haselböck, G. Schenner, H. Schreiner, Twenty-five years of successful application of constraint technologies at siemens, AI Mag. 37 (2016) 67–80. doi:10.1609/aimag.
v37i4.2688. [13] A. Falkner, G. Friedrich, K. Schekotihin, R. Taupe,
E. Teppan, Industrial applications of answer set programming, Künstliche Intelligenz 32 (2018) 165– 176. doi:10.1007/s13218-018-0548-6. [14] S. Hahn, O. Sabuncu, T. Schaub, T. Stolzmann, clingraph: ASP-based visualization, in: G. Gottlob, D. Inclezan, M. Maratea (Eds.), Proceedings of the Sixteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’22), volume 13416 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 2022, pp. 401–414.
doi:10.1007/978-3-031-15707-3_31. [15] R. Comploi-Taupe, G. Francescutto, G. Schenner,
Applying incremental answer set solving to product configuration, in: Proceedings of the 26th ACM International Systems and Software Product Line Conference – Volume B, Association for Computing Machinery, New York, NY, USA, 2022, pp. 150–155.
doi:10.1145/3503229.3547069. [16] Y. Dimopoulos, M. Gebser, P. Lühne, J. Romero,
T. Schaub, plasp 3: Towards efective ASP planning, in: M. Balduccini, T. Janhunen (Eds.), Proceedings of the Fourteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’17), volume 10377 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 2017, pp. 286–300. doi:10.1007/978-3-319-61660-5_26.