برنامه ریزی و زمانبندی در محیط آموزش الکترونیکی. روش مبتنی بر برنامه نویسی محدودیت

AI planning techniques offer very appealing possibilities for their application to e-learning environments. After all, dealing with course designs, learning routes and tasks keeps a strong resemblance with a planning process and its main components aimed at finding which tasks must be done and when. This paper focuses on planning learning routes under a very expressive constraint programming approach for planning. After presenting the general planning formulation based on constraint programming, we adapt it to an e-learning setting. This requires to model learners profiles, learning concepts, how tasks attain concepts at different competence levels, synchronisation constraints for working-group tasks, capacity resource constraints, multi-criteria optimisation, breaking symmetry problems and designing particular heuristics. Finally, we also present a simple example (modelled by means of an authoring tool that we are currently implementing) which shows the applicability of this model, the use of different optimisation metrics, heuristics and how the resulting learning routes can be easily generated.

Automated planning is an attractive area within AI due to its direct application to real-world problems. Actually, most everyday activities require some type of intuitive planning in terms of determining a set of tasks whose execution allows us to reach some goals under certain constraints. This direct application, the benefits it reports and, finally, the advances on the research in AI planning have facilitated the transfer of planning technology to practical applications, ranging from scientific and engineering scopes to social environments. Particularly, social environments such as education constitute an attractive field of application because of its continuous innovation and use of ICT (Information and Communication Technologies). However, it is generally agreed that education has not yet realised the full potential of the utilisation of this technology. As explained in Manouselis and Sampson (2002), this is mainly due to the fact that the traditional mode of instruction (one-to-many lecturing or one-to-one tutoring), which is adopted in conventional education, cannot fully accommodate the different learning and studying styles, strategies and preferences of diverse learners. But now, conventional education is giving way to e-learning environments, which require learners to take the learning initiatives and control how knowledge is presented during instruction (Atolagbe, 2002), which is not a simple task. Particularly, many European countries signed the Bologna joint declaration of the European space for higher education,1 which entails an important change in the learning process. With this declaration, learner's roles are much more dynamic, active and autonomous. The amount of one-to-many lecturing decreases and significantly increases the amount of self-learning through the construction of coherent learning routes according to a certain instructional course design. Finally, this course design recommends sequence of educational tasks and material, tailored to individual learners needs and profiles. In this paper we address the automated construction of learning routes from the viewpoint of planning based on constraint programming. After all, generating a learning route represents a planning activity with the following elements: learning goals to be attained, profile-adapted tasks with their prerequisites and learning outcomes (i.e. preconditions and effects, respectively), non-fixed durations, resources, ordering and synchronisation constraints, and collaboration/cooperation relations. The underlying idea is to plan a learning route, indicating which tasks must be done, for a learner with a given profile in order to reach some learning goals. The general scheme is shown in Fig. 1. First, an instructional course design is defined by means of a visual authoring tool. This course is extended with the additional, particular constraints of each application context and, all together, is translated into a constraint programming model that is later solved by a CSP solver. Finally, the output solution provides a learning route per learner, that is a profile-adapted plan. Each individual route consists of a sequence of tasks, such as attending an in-person lesson, doing a lab exercise, writing a report, etc. Although intuitively each course-plan is initially created individually for each given learner, there are some particular tasks that need to be done simultaneously by several learners, such as attending a lab for the same practice work. Additionally, these tasks may require some type of synchronisation (for instance, doing a working-group task), where the start and/or end must happen at the same time. Thus, a learning route also requires the time allocation of its tasks according to the temporal+resourcetemporal+resource constraints, i.e. when the tasks will be done (scheduling component), which are encoded as additional constraints. In this context, the planning component is not particularly costly since the plan is usually small; the number of tasks is between 10 and 20 per route, though there may be a lot of different alternatives. On the contrary, the scheduling component is more significant because of the resource availability, the diversity of constraints and their handling and synchronisation among different routes. These features are not easily included in traditional planning as they require artificial mechanisms to be managed, which complicate the planning algorithms. For instance, a very frequent type of constraints in an e-learning scenario such as synchronisation constraints, where several actions need to meet throughout a whole interval, is not easily represented and handled in planners. Our approach for planning learning routes relies on the constraint programming formulation presented in Garrido et al. (2006), previously based on Vidal and Geffner (2006), which encodes all type of constraints derived from both planning and scheduling features. Such a formulation provides a high level of expressiveness to deal with all the elements required in an e-learning setting and it has several advantages: • It is a purely declarative representation and, consequently, it can be solved by any type of CSP solver. Obviously, by any type of CSP solver we mean a solver that supports the expressiveness of our constraint model, which includes binary and non-binary constraints. In any case, a non-binary constraint can be translated into a binary one by creating new variables and constraints ( Bacchus and van Beek, 1998), though this would increase the complexity of the model. • The whole formulation is automatically derived from the course design, without any need of specific hand-coded domain knowledge. This means that no expert users are required to develop our constraint model as it is straightforwardly generated from the tasks and relations provided in the instructional course. Despite this, specific ad hoc control information in the form of hand-coded domain knowledge or domain-dependent heuristics can be easily included in the formulation to find a better plan or make the resolution process more efficient. • Formal properties, such as soundness, completeness and optimality, hold in our constraint model. In particular, optimality is a major issue in this context and so different optimisation multi-criteria can be defined w.r.t. the number of actions of the learning routes, the duration of their tasks or the cost associated to them. In summary, this paper introduces a formulation of planning problems by means of constraint programming and the application of such a formulation to solve a learning-route planning problem. This paper is organised as follows. In the second section we present some basic background on e-learning environments and their relation to AI planning, motivating some needs for using a constraint programming approach. The third section briefly reviews the formulation of a planning problem by means of constraint programming, while in the fourth section this formulation is adapted to fit an e-learning scenario, which imposes some particular requirements. In the fifth section an example of application is analysed, showing part of the formulation, implementation and results. Finally, we present the conclusions of the paper and point some directions for future work.

Constraint programming formulation is a very appropriate approach to tackle planning problems that require the representation and management of a wide range of complex constraints, as it is the case of e-learning environments. Designing a learning route can be seen as generating a plan in a domain where it is necessary to attain learning outcomes (concepts) while handling resources and their capacity, synchronised tasks among learners of different profiles, orderings between tasks, deadlines or other customised and elaborate constraints. In principle, as a planning problem, the design of learning routes could be accomplished by using a current state-of-the-art planner. However, current planners cannot afford complex constraints as task synchronisation or, otherwise, it would be necessary many artificial tricks for representing and handling it. On the other hand, optimality is a major issue in e-learning contexts either from the learner or teaching centre viewpoint, so it is important to guarantee good-quality, and even optimal, plans as this might affect the overall learning route. In an e-learning context, the activity that requires a little bit of effort is the definition of the course design by the instructor. It is necessary to classify the learning tasks, study the prerequisites and outcomes of each task by means of concepts, identify the profiles for which the task is best focus, determine the assessment points, establish the competence level for the concepts, etc. In order to make this task easier we provide a visual authoring tool that allows the instructor to simply drag and drop elements from a tool bar for elaborating such a design in a simple and intuitive way. As an additional advantage, since the course design comprises the specification of a general, flexible learning domain, it can be used for the generation of learning routes in many different contexts (teaching centres) with different time and resource constraints, for different learner profiles and with different optimisation criteria. In other words, it is worth the effort devoted to course design in favour of the reusability degree we can obtain with our approach for planning routes in e-learning environments. We can conclude by saying that the expressiveness of constraint programming makes it very appropriate for modelling learning routes. The adequacy is also given by the fact that designing learning routes is not a very complex planning problem but rather a complex scheduling problem. For this reason, constraint programming approaches seem to be a promising direction for e-learning contexts. As a consequence of this, we are currently working on two aspects. First, we are studying other heuristic functions to make the solving process more efficient in order to face bigger problems and improve the scalability of the approach. Second, we are extending the authoring tool, as presented in Onaindía et al. (2007), to make the definition of the course design even more intuitive by splitting it into three steps: (i) define a conceptual design with the relations among concepts, (ii) define an instructional design with the tasks that achieve the concepts, and (iii) define a planning design with all the elements presented in this paper such as profiles, concepts, tasks, competence levels as percentages and complex constraints.