Configuration is a successful application area of Artificial Intelligence. In the majority of the cases, configuration systems focus on configuring one solution (configuration) that satisfies the preferences of a single user or a group of users. In this paper, we introduce a new configuration approach - multi-configuration - that focuses on scenarios where the outcome of a configuration process is a set of configurations. Example applications thereof are the configuration of personalized exams for individual students, the configuration of project teams, reviewer-to-paper assignment, and hotel room assignments including individualized city trips for tourist groups. For multi-configuration scenarios, we exemplify a constraint satisfaction problem representation in the context of configuring exams. The paper is concluded with a discussion of open issues for future work.
Configuration is a special case of design activity where a product is
composed of a selection of predefined components that satisfies a set
of constraints [
In this paper, we focus on a scenario where multiple instances of the same product type are configured for one user or a group of users. In this context, a set of constraints defines restrictions regarding the possible combinations of individual instances, i.e., the configured instances are not completely independent. An application scenario for multi-configuration is the configuration of user-individual exams which have to take into account a set of constraints, for example, the share of complex questions per student must be below 20%. Following this representation, we define multi-configuration as a specific type of configuration task where multiple instances of the same type are configured for a single user or a group of users.
There are various example scenarios which can profit from
multiconfiguration. (1) When assigning presentation topics to students, the
goal could be to identify three different starting paper references per
student where, for example, each reference should be assigned to not
more than two students. (2) When planning room assignments for
larger user groups (e.g., for a soccer training camp), a configurator
could collect the preferences of individual group members and then
generate a room assignment that takes into account as much as
possible the preferences of the individual group members. (3) When
configuring project teams, a configurator could take care of the optimal
configuration of individual teams while keeping in mind the aspect
of fairness, i.e., none of the team configurations should be
”suboptimal”. (4) When designing an apartment/house complex,
neighborhood buildings must take into account rules such as the roof type
of all buildings should be the same or neighborhood buildings must
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
generation of test cases [
In single user and group-based configuration scenarios, one
configuration is determined that supports the requirements of the user (or
a group of users). In multi-configuration scenarios, a set of
configurations is determined for one or a group of users. The following
discussions are based on a constraint-based configuration knowledge
representation [
Definition 1. A Multi-Configuration Task can be defined by a tuple (V; D; REQ; C) where V = Sfvij g is a set of finite domain variables (vij represents variable j of configuration instance i), D = Sfdom(vij )g is a set of corresponding domain definitions, REQ = Sfvij = valij g represents a set of user requirements, and C = fc1; c2; ::; cmg is a set of constraints that restrict the way in which individual variable values can be combined with each other.
For simplicity, we assume that user requirements in REQ are represented by simple variable value assignments (vij = valij ). However, if needed, this assumption can be replaced by the more general case of allowing users to specify more complex constraints where each of those constraints is regarded as an individual requirement. Furthermore, we decided not to differentiate between different constraint types, for example, constraints referring to individual configurations and constraints referring to a set of configurations. On the basis of Definition 1, we can introduce the definition of a multiconfiguration (see Definition 2).
Definition 2. A multi-configuration for a multi-configuration task (V; D; REQ; C) is a set of variable value assignments CON F = Sfvij = valij g s.t. CON F [ C [ REQ is consistent.
We now introduce an example multi-exam configuration scenario.3 3
In multi-exam configuration, the overall goal is to determine an exam instance for each examinee where a couple of constraints have to be taken into account. The underlying idea is to provide variability models for the purpose of being able to generate examinee-individual exams and thus save time in exam preparation and also avoid cheating due to exam diversity. Furthermore, this approach provides the possibility of a deeper integration of examinees into exam-related decision processes, i.e., students can be allowed to some extend to articulate their preferences regarding an exam. Following Definition 1, we now show how to represent the task of multi-exam configuration.
V = fq11::qkl; q11:type::qkl:type; q11:level::qkl:levelg where qij is question j posed to examinee i, qij :type denotes the question type (category), qij :level is the question complexity, k the number of examinees, and l the number of questions / examinee. D = fdom(q11)::dom(qkl); dom(q11:type)::dom(qkl:type); dom(q11:level)::dom(qkl:level)g, where dom(qij ) = f1::pg, dom(qij :type) = f1::qg, and dom(qij :level) = f1::rg (p = number of questions per examinee, q = number of question categories, and r = number of question complexity levels).
REQ = fr1::rug where r is a requirement identifier and u the number of requirements (defined by examinees and instructors). C = fc1::cvg where v is the number of constraints.
In the following, we introduce a couple of example constraints that could be defined in the context of an exam configuration task.
Requirements. REQ includes a set of examinee- (and instructor-) individual constraints – in the context of our example, REQ is a set of examinee-specific constraints that have to be taken into account. The motivation behind this is that we want to make exam generation more flexible in terms of being able to include the preferences of examinees as well as the preferences of instructors.
First, we assume that examinee a prefers to have included 30% of questions related to the categories f ; g (see Formula 1). This way, we want to bring more flexibility into exam configuration, however, students will not always get what they want, i.e., their preferences have to be consistent with constraints defined by instructors. In many scenarios, students will not be allowed to define such constraints, i.e., only instructor requirements are relevant.
r1 : jfqaj 2 V : qaj :type 2 f ; ggj jfqaj 2 V gj 0:3
Furthermore, we assume that examinee a prefers not to have included questions related to question category (see Formula 2). r2 : jfqaj 2 V : qaj :type = gj = 0
Question-level Constraints. These constraints define properties related to the inclusion of specific questions. For example, we assume that a specific question v must not be included in more than x exams (see Formula 3), i.e., x = 0 would exclude v from any exam. c1 : jfqij 2 V : qij = vgj x
Furthermore, we assume that each exam configuration includes question u or question v (see Formula 4). 3 For exam configuration, we replace the term user with examinee/instructor. (1) (2) (3) c2 : k(#examinees) l(#questions) ^ _ i=1 j=1 (qij = u _ qij = v) We also assume that the minimum question complexity level is .
c3 : 8qij 2 V : qij :level
Global Constraints. We require that no question of type must be included in the exam (see Formula 6). A simple reason for formulating such constraints could be that the related topic has not been discussed in detail within the scope of the course.
c4 : jfqij 2 V : qij :type = gj = 0
We want to assure that at least three questions of type included in each exam u (see Formula 7). must be c5 : 8u 2 f1::kg : jfquj 2 V : quj :type = gj 3 Furthermore, the overall estimated duration of each exam must be minutes (constraint formulated for examinee a) (see Formula 8). c6 : l(#questions)(qaj :duration) = j=1
We also want to assure that the share of complex questions (level = ) per examinee must be between 16% and 18% (example formulated for examinee a) (see Formula 9).
c7 : 0:16 jfqaj 2 V : qaj :level =
gj jfqaj 2 V gj 0:18 (9)
Further Constraints. In addition to the mentioned examples, there are many further relevant constraints, for example, each examinee should be asked a specific question only once and the question overlap between each pair of students should be more than 90%. (4) (5) (6) (7) (8) 4
We have introduced the notion of multi-configuration which is a
specific approach focusing on scenarios where collections of
configurations are designed for user groups. In order to better
understand the discussed concepts, we have introduced a working
example from the domain of exam configuration. Future work will
include the analysis of the applicability of the presented concepts in
the exam configuration domain (e.g., we will identify a complete set
of typically relevant domain constraints) as well as in further
multiconfiguration scenarios. Furthermore, we will analyze new user
interfaces and interaction requirements triggered by the application
of multi-configuration concepts. The knowledge representation
concepts discussed within the context of our exam configuration scenario
are currently integrated into the KNOWLEDGECHECKR elearning
environment (www.knowledgecheckr.com) [
The presented work has been conducted in the PARXCEL project funded by the Austrian Research Promotion Agency (880657).