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.