=Paper=
{{Paper
|id=Vol-2945/33-AF-ConfWS21_paper_12
|storemode=property
|title=Configuring Multiple Instances with Multi-Configuration
|pdfUrl=https://ceur-ws.org/Vol-2945/33-AF-ConfWS21_paper_12.pdf
|volume=Vol-2945
|authors=Alexander Felfernig,Andrei Popescu,Mathias Uta,Viet-Man Le,Seda Polat Erdeniz,Martin Stettinger,Müslüm Atas,Thi Ngoc Trang Tran
|dblpUrl=https://dblp.org/rec/conf/confws/Felfernig0ULESA21
}}
==Configuring Multiple Instances with Multi-Configuration==
https://ceur-ws.org/Vol-2945/33-AF-ConfWS21_paper_12.pdf
Configuring Multiple Instances with Multi-Configuration
Alexander Felfernig1 and Andrei Popescu1 and Mathias Uta2 and Viet-Man Le1 and
Seda Polat-Erdeniz1 and Martin Stettinger1 and Müslüm Atas1 and Thi Ngoc Trang Tran1
Abstract. Configuration is a successful application area of Artifi- student where, for example, each reference should be assigned to not
cial Intelligence. In the majority of the cases, configuration systems more than two students. (2) When planning room assignments for
focus on configuring one solution (configuration) that satisfies the larger user groups (e.g., for a soccer training camp), a configurator
preferences of a single user or a group of users. In this paper, we could collect the preferences of individual group members and then
introduce a new configuration approach – multi-configuration – that generate a room assignment that takes into account as much as possi-
focuses on scenarios where the outcome of a configuration process is ble the preferences of the individual group members. (3) When con-
a set of configurations. Example applications thereof are the config- figuring project teams, a configurator could take care of the optimal
uration of personalized exams for individual students, the configura- configuration of individual teams while keeping in mind the aspect
tion of project teams, reviewer-to-paper assignment, and hotel room of fairness, i.e., none of the team configurations should be ”subop-
assignments including individualized city trips for tourist groups. For timal”. (4) When designing an apartment/house complex, neighbor-
multi-configuration scenarios, we exemplify a constraint satisfaction hood buildings must take into account rules such as the roof type
problem representation in the context of configuring exams. The pa- of all buildings should be the same or neighborhood buildings must
per is concluded with a discussion of open issues for future work. not reduce the amount of direct sunlight below a specific treshold.
Compared to the former ones, the latter scenario can be regarded as a
kind of industrial multi-configuration setting. Finally, the automated
1 Introduction generation of test cases [7], for example, in the context of regression
Configuration is a special case of design activity where a product is testing, can be regarded as a multi-configuration task.
composed of a selection of predefined components that satisfies a set
of constraints [4, 11, 14]. Typical configurator applications are based
on the assumption that a product (or service) is configured for a sin- 2 Multi-Configuration
gle user. Related example applications can be found in product do- In single user and group-based configuration scenarios, one config-
mains such as telecommunications [6], automotive [8], and software uration is determined that supports the requirements of the user (or
systems [12]. In contrast to the configuration for an individual user, a group of users). In multi-configuration scenarios, a set of config-
group-based configuration [2] is based on the idea of configuring a urations is determined for one or a group of users. The following
product or service for a group of users, i.e., the resulting configura- discussions are based on a constraint-based configuration knowledge
tion must take into account as much as possible the individual pref- representation [15]. The following definition of a configuration task
erences of group members. An example of a group-based scenario is (and solution) allows to represent collections of configurations (see
the configuration and also recommendation of software release plans Definition 1 and Definition 2). A multi-configuration task can be de-
where software requirements have to be arranged in such a way that fined as a constraint satisfaction problem (CSP) [15].
the preferences of individual stakeholders are taken into account as Definition 1. A Multi-Configuration
much as possible [1, 3]. STask can be defined by a tu-
ple (V, D, REQ, C) where V = {vij } is a set of finite do-
In this paper, we focus on a scenario where multiple instances of main variables (v ij represents variable j of configuration instance
the same product type are configured for one user or a group of users. S
i), D = S{dom(vij )} is a set of corresponding domain definitions,
In this context, a set of constraints defines restrictions regarding the REQ = {vij = valij } represents a set of user requirements, and
possible combinations of individual instances, i.e., the configured C = {c1 , c2 , .., cm } is a set of constraints that restrict the way in
instances are not completely independent. An application scenario which individual variable values can be combined with each other.
for multi-configuration is the configuration of user-individual exams For simplicity, we assume that user requirements in REQ are rep-
which have to take into account a set of constraints, for example, the resented by simple variable value assignments (vij = valij ). How-
share of complex questions per student must be below 20%. Follow- ever, if needed, this assumption can be replaced by the more general
ing this representation, we define multi-configuration as a specific case of allowing users to specify more complex constraints where
type of configuration task where multiple instances of the same type each of those constraints is regarded as an individual requirement.
are configured for a single user or a group of users. Furthermore, we decided not to differentiate between different con-
There are various example scenarios which can profit from multi- straint types, for example, constraints referring to individual con-
configuration. (1) When assigning presentation topics to students, the figurations and constraints referring to a set of configurations. On
goal could be to identify three different starting paper references per the basis of Definition 1, we can introduce the definition of a multi-
1 Applied Software Engineering & AI, Graz University of Technology, email: configuration (see Definition 2).
{firstname.lastname}@ist.tugraz.at Definition 2. A multi-configuration for a multi-configuration task
2 Siemens Energy AG, email: mathias.uta@siemens.com
(V, D, REQ, C) is a set of variable value assignments CON F =
Copyright 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
S
{vij = valij } s.t. CON F ∪ C ∪ REQ is consistent. k(#examinees) l(#questions)
We now introduce an example multi-exam configuration scenario.3
^ _
c2 : (qij = u ∨ qij = v) (4)
i=1 j=1
3 Example Multi-Configuration Scenario We also assume that the minimum question complexity level is π.
In multi-exam configuration, the overall goal is to determine an exam
c3 : ∀qij ∈ V : qij .level ≥ π (5)
instance for each examinee where a couple of constraints have to be
taken into account. The underlying idea is to provide variability mod- Global Constraints. We require that no question of type δ must be
els for the purpose of being able to generate examinee-individual ex- included in the exam (see Formula 6). A simple reason for formu-
ams and thus save time in exam preparation and also avoid cheating lating such constraints could be that the related topic has not been
due to exam diversity. Furthermore, this approach provides the possi- discussed in detail within the scope of the course.
bility of a deeper integration of examinees into exam-related decision
processes, i.e., students can be allowed to some extend to articulate c4 : |{qij ∈ V : qij .type = δ}| = 0 (6)
their preferences regarding an exam. Following Definition 1, we now We want to assure that at least three questions of type γ must be
show how to represent the task of multi-exam configuration. included in each exam u (see Formula 7).
• V = {q11 ..qkl , q11 .type..qkl .type, q11 .level..qkl .level} where
c5 : ∀u ∈ {1..k} : |{quj ∈ V : quj .type = γ}| ≥ 3 (7)
qij is question j posed to examinee i, qij .type denotes the ques-
tion type (category), qij .level is the question complexity, k the Furthermore, the overall estimated duration of each exam must be
number of examinees, and l the number of questions / examinee. ∆ minutes (constraint formulated for examinee a) (see Formula 8).
• D = {dom(q11 )..dom(qkl ), dom(q11 .type)..dom(qkl .type),
l(#questions)
dom(q11 .level)..dom(qkl .level)}, where dom(qij ) = {1..p}, c6 : Σj=1 (qaj .duration) = ∆ (8)
dom(qij .type) = {1..q}, and dom(qij .level) = {1..r} (p =
We also want to assure that the share of complex questions
number of questions per examinee, q = number of question cate-
(level = φ) per examinee must be between 16% and 18% (example
gories, and r = number of question complexity levels).
formulated for examinee a) (see Formula 9).
• REQ = {r1 ..ru } where rα is a requirement identifier and u the
number of requirements (defined by examinees and instructors). |{qaj ∈ V : qaj .level = φ}|
• C = {c1 ..cv } where v is the number of constraints. c7 : 0.16 ≤ ≤ 0.18 (9)
|{qaj ∈ V }|
In the following, we introduce a couple of example constraints that Further Constraints. In addition to the mentioned examples, there
could be defined in the context of an exam configuration task. are many further relevant constraints, for example, each examinee
Requirements. REQ includes a set of examinee- (and instructor-) should be asked a specific question only once and the question over-
individual constraints – in the context of our example, REQ is a set lap between each pair of students should be more than 90%.
of examinee-specific constraints that have to be taken into account.
The motivation behind this is that we want to make exam generation 4 Conclusions and Future Work
more flexible in terms of being able to include the preferences of
examinees as well as the preferences of instructors. We have introduced the notion of multi-configuration which is a
First, we assume that examinee a prefers to have included ≤ 30% specific approach focusing on scenarios where collections of con-
of questions related to the categories {α, β} (see Formula 1). This figurations are designed for user groups. In order to better under-
way, we want to bring more flexibility into exam configuration, how- stand the discussed concepts, we have introduced a working exam-
ever, students will not always get what they want, i.e., their prefer- ple from the domain of exam configuration. Future work will in-
ences have to be consistent with constraints defined by instructors. clude the analysis of the applicability of the presented concepts in
In many scenarios, students will not be allowed to define such con- the exam configuration domain (e.g., we will identify a complete set
straints, i.e., only instructor requirements are relevant. of typically relevant domain constraints) as well as in further multi-
configuration scenarios. Furthermore, we will analyze new user in-
|{qaj ∈ V : qaj .type ∈ {α, β}}| terfaces and interaction requirements triggered by the application
r1 : ≤ 0.3 (1)
|{qaj ∈ V }| of multi-configuration concepts. The knowledge representation con-
cepts discussed within the context of our exam configuration scenario
Furthermore, we assume that examinee a prefers not to have in-
are currently integrated into the K NOWLEDGE C HECKR elearning en-
cluded questions related to question category γ (see Formula 2).
vironment (www.knowledgecheckr.com) [13]. Our major motivation
is to increase the flexibility of exam generation but also to coun-
r2 : |{qaj ∈ V : qaj .type = γ}| = 0 (2)
teract cheating in online exams through an increased exam variabil-
Question-level Constraints. These constraints define properties re- ity. In cases where individual user requirements induce an inconsis-
lated to the inclusion of specific questions. For example, we assume tency with the exam model constraints, we propose the application of
that a specific question v must not be included in more than x exams model-based diagnosis concepts [5, 9, 10] which can help to deter-
(see Formula 3), i.e., x = 0 would exclude v from any exam. mine minimal conflict resolutions that also take into account aspects
such as fairness and representativeness of the remaining questions.
c1 : |{qij ∈ V : qij = v}| ≤ x (3)
Furthermore, we assume that each exam configuration includes ACKNOWLEDGEMENTS
question u or question v (see Formula 4).
The presented work has been conducted in the PAR XC EL project
3 For exam configuration, we replace the term user with examinee/instructor.
funded by the Austrian Research Promotion Agency (880657).
REFERENCES
[1] A. Felfernig, ‘AI Techniques for Software Requirements Prioritiza-
tion’, in Artificial Intelligence Methods for Software Engineering, eds.,
M. Kalech, R: Abreu, and M. Last, 29–47, World Scientific, (2021).
[2] A. Felfernig, M. Atas, T. Tran, and M. Stettinger, ‘Towards group-based
configuration’, in ConfWS’16, pp. 69–72, Toulouse, France, (2016).
[3] A. Felfernig, L. Boratto, M. Stettinger, and M. Tkalcic, Group Recom-
mender Systems, Springer, 2018.
[4] A. Felfernig, L. Hotz, C. Bagley, and J. Tiihonen, Knowledge-based
Configuration - From Research to Business Cases, Elsevier, 2014.
[5] A. Felfernig, M. Schubert, and C. Zehentner, ‘An Efficient Diagnosis
Algorithm for Inconsistent Constraint Sets’, AI for Engineering Design,
Analysis, and Manufacturing, 26(1), 53–62, (2012).
[6] G. Fleischanderl, G. Friedrich, A. Haselboeck, H. Schreiner, and
M. Stumptner, ‘Configuring large systems using generative constraint
satisfaction’, IEEE Intelligent Systems, 13(4), 59–68, (1998).
[7] A. Gotlieb, B. Botella, and M. Rueher, ‘Automatic Test Data Genera-
tion Using Constraint Solving Techniques’, ACM SIGSOFT Software
Engineering Notes, 23(2), 53–62, (1998).
[8] J. Landahl, D. Bergsjö, and H. Johannesson, ‘Future Alternatives for
Automotive Configuration Management’, Procedia Computer Science,
28, 103–110, (2014).
[9] V.M. Le, A. Felfernig, M. Uta, D. Benavides, J. Galindo, and T.N.T.
Tran, ‘D IRECT D EBUG: Automated Testing and Debugging of Feature
Models’, in 43rd Intl. Conference on Software Engineering (ICSE’21),
pp. 81–85, Virtual, (2021). IEEE.
[10] R. Reiter, ‘A theory of diagnosis from first principles’, Artificial Intel-
ligence, 32(1), 57–95, (1987).
[11] D. Sabin and R. Weigel, ‘Product Configuration Frameworks - A Sur-
vey’, IEEE Intelligent Systems, 13(4), 42–49, (1998).
[12] J. Sincero and W. Schröder-Preikschat, ‘The Linux Kernel Configura-
tor as a Feature Modeling Tool’, in Workshop on Analyses of Software
Product Lines, pp. 257–260, Limerick, Ireland, (2008). ASPL.
[13] M. Stettinger, T.N.T. Tran, I. Pribik, G. Leitner, A. Felfernig, R. Samer,
M. Atas, and M. Wundara, ‘KNOWLEDGECHECKR: Intelligent
Techniques for Counteracting Forgetting’, in 24th European Confer-
ence on Artificial Intelligence (ECAI 2020), eds., G. DeGiacomo,
A. Catala, B. Dilkina, M. Milano, S. Barro, A. Bugarin, and J. Lang,
volume 325 of Frontiers in Artificial Intelligence and Applications, pp.
3034–3039, Santiago de Compostela, Spain, (2020). IOS Press.
[14] M. Stumptner, ‘An overview of knowledge-based configuration’, AI
Communications, 10(2), 111–125, (1997).
[15] E. Tsang, Foundations of Constraint Satisfaction, Academic Press,
1993.