استفاده از برنامه ریزی خطی برای حل مسائل برنامه ریزی اشتراک بیش از حد خوشه ای برای طراحی دروس الکترونیکی

The automatic generation of individualized plans in specific domains is an open problem that combines aspects related to automated planning, machine learning or recommendation systems technology. In this paper, we focus on a specific instance of that task; that of generating e-learning courses adapted to students’ profiles, within the automated planning paradigm. One of the open problems in this type of automated planning application relates to what is known as oversubscription: given a set of goals, each one with a utility, obtain a plan that achieves some (or all) the goals, maximizing the utility, as well as minimizing the cost of achieving those goals. In the generation of e-learning designs there is only one goal: generating a course design for a given student. However, in order to achieve the goal, the course design can include many different kinds of activities, each one with a utility (that depend on the student profile) and cost. Furthermore, these activities are usually grouped into clusters, so that at least one of the activities in each cluster is needed, though many more can be used. Finally, there is also an overall cost threshold (usually in terms of student time). In this paper, we present our work on building an individualized e-learning design. We pose each course design as a variation of the oversubscription problem, that we call the clustered-oversubscription problem, and we use linear programming for assisting a planner to generate the design that better adapts to the student.

Automated planning is the branch of artificial intelligence that studies the computational synthesis of ordered sets of actions that perform a given task (Ghallab, Nau, & Traverso, 2004). A planner receives as input a collection of actions (that indicate how to modify the current state), a collection of goals to achieve, and a state. It then outputs a sequence of actions that achieve the goals from the initial state. Given that each action transforms the current state, planners may be viewed as searching for paths through the state space defined by the given actions. However, the search spaces can quickly become intractably large, such that the general problem of automated planning is PSpace-complete (Bylander, 1994). The evolution of automated planning can be seen from three different interrelated perspectives: planning techniques, expressiveness of planning languages, and applications. In relation to the first one, it is one of the most active areas, since very powerful domain-independent techniques have been devised in the last two decades. However, we can see that there is no such counterpart in the other two. The International Planning Competition (IPC1) has been one of the major drivers of this advancement, and the standard language, PDDL (Gerevini & Long, 2005), one of its bases. Although, PDDL is gaining in expressiveness, very few planners can handle the full set of features that it defines. This is due mainly to the competition: if competition does not focus on specific aspects of the planning task, then it is hard to see which technique is better for solving each aspect. Unfortunately, most real world applications require the use of some features of PDDL that are not handled by most planners, as well as the use of some representation features that are not present in PDDL. So, in relation to the third perspective, when trying to solve different real world applications, then one is very restricted to the planners that can be used. Another relation between current planners and their ability to directly be used in applications is that most planners are still in an advanced prototype status. So, as we will see later, they either crash or fail on solving problems in domains that do not belong to the competition. This is probably due to small implementation errors, but this makes it unfeasible to use them “as is” in current applications. Thus, there is still a gap between state of the art planners and their direct application. This can be easily explained given the two different emphasis on both communities: either generating powerful search techniques that can handle some expressiveness, and the need of polished implementations to be used as “off-the-shelf” components for applications. Despite these problems, the application of planning techniques to real problems sometimes requires solving interesting associated problems that can be useful in more general contexts. This is the case of the work presented in this paper. The application area is the generation of learning designs adapted to students’ profiles. And, the associated problem is a variation of the oversubscription problem (OSP) that we have called clustered oversubscription. OSP was first introduced by Smith (2004) and the objective of the planning process in the presence of goals oversubscription is not to find a feasible plan accomplishing all the goals, but to find a plan which reaches some of them, maximizing the sum of utilities of achieved goals. As Smith pointed out, many NASA planning problems are over-subscription problems. For example, space and airborne telescopes, such as Hubble, SIRTF, and SOFIA, receive many more observation requests than can be accommodated. As a result, only a small subset of the desirable requests can be accomplished during any given planning horizon. For a Mars rover mission, there are many science targets that the planetary geologists would like to visit. However, the rover can only visit a few such targets in any given command cycle because of time and energy limitations, and limitations on the rover’s ability to track targets. In this paper, we describe our work on a task that also presents a kind of oversubscription: automatic generation of e-learning courses. An e-learning task can be posed as: given a specific student, and a course defined by a pool of diverse learning activities, automatically generate a learning design for that student using the given learning activities that better suit the student profile. This domain has some interesting characteristics that resembles OSP: (1) each activity has a utility, and a time (cost) that it takes to complete it; (2) the utility that a given learning activity will provide a student depends on some student features; (3) as a hard constraint, the time to execute all learning activities in the final plan must be bound by a threshold (the total amount a student can dedicate to that course); (4) and, as with usual planning tasks, the activities present causal relationships among them (the student should follow some learning activities before others). Besides, it has an extra characteristic that comes up with the clustered oversubscription problem: (5) each learning activity belongs to a given cluster, and the final design should have at least one activity of each cluster, potentially more. In clustered oversubscription, we perform some analysis before planning that selects a subset of the learning activities that is worth pursuing, given that they maximize utility (or have a high utility), and fulfill the constraint that the sum of their cost (time) is less than the cost limit (time threshold). The approach for performing this selection consists of posing the problem as a clustered-knapsack problem and using linear programming. Then, we translate this subset in two different ways, as preferences or as a metric. Our work is based on previous pedagogical research where they have tested a valid way for measuring the utility each learning activity reports to the students (Baldiris et al., 2008). So, we focus on the problem of sequencing learning activities in a course adapted to every student’s profile by trying to maximize the total utility. Other relevant work concerning the use of AI planning and scheduling techniques for sequencing learning activities, according to different student’s profiles and pedagogical theories, is reported in Castillo et al., 2009 and Ullrich and Melis, 2009. But, they did not focus on the goal of finding a feasible plan that maximizes some measure of utility by reaching a subset of the goals. Our aim is that the proposed solution would be general enough so it can be extrapolated to other domains. An example of domain that have similar clustered-oversubscription problems is a variation of the Rovers domain. The rovers need to take several samples, each sample of a specific kind (cluster) of rock, and there are several rocks of each kind. Also, taking those samples takes some time, and they have a specific time threshold to perform the activities. Other examples are earth observing satellites (clusters are areas with the same information, as big forests, mountains, or oceans) or the planning and optimization of resources in bus transportation networks (clusters are the different lines that compose the transportation network and the goal is optimizing their resources and minimizing costs). The contribution of the current paper is twofold: modelling e-learning tasks as clustered-oversubscription planning problems; and providing a generic approach for solving the resulting problems, applicable in other contexts than e-learning applications, as well. The remainder of the paper proceeds as follows. Next section introduces automated planning and its representation language PDDL. Section 3 describes how we have modelled the e-learning application in PDDL. Section 4 explains the approach that we have devised for solving the clustered-oversubscription problem by performing an action selection pre-processing to help the planning task using linear programming. Section 5 reports the experiments performed to test the validity of the approach. Section 6 describes the related work. Finally, last section draws the conclusions and our future work.

This paper presents our work on building an e-learning planning application for generating learning designs adapted to different students’ profiles. An e-learning course is defined by a set of different learning activities, that use learning objects. Learning activities, with their duration, student profile’s dependence and the relations defined in their metadata, keep a strong resemblance with actions as traditionally used in AI planning domains. In particular, each learning activity can be simply modelled as an action, its dependency relations as preconditions, and its outcomes as effects. This way P&S techniques can be very powerful to automatically generate sequences of learning activities fully adapted to the students. However, current planners are good for sequencing actions, but they are not so good for optimizing. Optimizing requires to use fluents and plan metrics, and it notably increases planning complexity. We are interested in finding the sequence that maximizes the student’s net benefit. Therefore, we have modelled the problem as a clustered-oversubscription problem performing an action selection pre-processing to help the planning task. We have proposed an action-selection schemes based on linear programing, that partially solves the optimization problem, and whose output is compiled into the planning task. It turns out that for this task, LP provides optimal solutions in a more than reasonable time. PDDL provides expressive power to model the problem, and to include the optimization knowledge in two different formats. The resulting PDDL domain is apparently simple, because there are no delete effects, but the complexity arises from the number of actions, the conditional effects, and the plan metric. Only the SGPlan and CBP planners were able to solve the problem, but SGPlan gave unfeasible solutions because it violated the threshold time constraint. Results show that the learning designs obtained with our approach report greater benefits to the students with regards to the overall utility of the proposed learning activities. The benefits are specially relevant when the threshold time is high and the course size is big. A base planner, without the information reported by our clustered oversubscription pre-processing, stops the search when the plan includes one activity per cluster although there was enough time for adding more learning activities that could reinforce the student knowledge. Our approach, however, continues including activities in the design until the reward threshold is exceeded. On the other hand, when the time limit is small, a base planner has difficulties finding a solution that our pre-processing can overcome. Another alternative would have been modelling the action preconditions as linear equality and inequality constraints. However, this is still an open issue and it is not trivial how to do it, due to the disjunction relations among some preconditions. Therefore, a complete formulation of the whole problem as LP or CSP tasks is difficult. Here, we opt for a hybrid approach in that LP solves the LP component of the task, and planning solves the causality-related component of the task. In the future, we would like to test our approach in other domains as the clustered Rovers and Satellite ones, as well as, in other application areas. For example, the planning and optimization of resources in bus transportation networks.