A set of adaptation patterns for expressing adaptive navigation in Adaptive Hypermedia Nadjet Zemirline1,2 , Yolaine Bourda1 , and Chantal Reynaud2 1 SUPELEC Systems Sciences (E3S) - Computer Science Department, France (Nadjet.Zemirline, Yolaine.Bourda)@supelec.fr 2 University of Paris-Sud XI, CNRS (LRI) & INRIA-Saclay/Projet Leo, France Chantal.Reynaud@lri.fr Abstract. This paper presents a set of 22 adaptation patterns, inde- pendent of any application domain and independent of any adaptation engine. They have been translated to LAG and GLAM adaptation lan- guages in order to plug them on existing adaptation engines. Currently, they are used in the EAP framework, which allows defining complex adaptation strategies in Adaptive Hypermedia. We also propose a typol- ogy for the elementary adaptation patterns in order to facilitate their use and their understanding. 1 Introduction Over the last decade, Adaptive Hypermedia (AH) have been under develop- ment [6], particularly in education [1], where learners get access to particular resources according to their knowledge, preferences and goals. Such access are proposed through the definition of adaptation, which is often considered as the most difficult part to author in AH [4, 2]. The definition of adaptation is made through expressing multiple adaptation strategies. An adaptation strategy specifies which resources have to be proposed and how these resources will be proposed to a set of users who share the same characteristics [9]. For example, users being theorist, textual and sequential, will have access only textual resources related to theory before those related to samples according to a depth-first navigational path on the relation successor. Thereby, authors face numerous challenges when defining their adaptation strategies. The 1st challenge concerns the expression of adaptation strategies. The 2nd challenge concerns the reuse of adaptation strategies from one system to another one, and the expression of adaptation strategies independently of any AH System. To do so, the paradigm ”write once, use many” [8] has been proposed. It endorses expressing adaptation at a high level, independently of any AHS, then translating this adaptation into a particular AHS. The 3rd challenge concerns the granularity in writing adaptation strategies. Its target is to avoid writing the common parts of adaptation strategies several times. As shown in [9], till now, there have been no works concerning building complex adaptation strategies, independent of any AHS by combining simple adaptations. II So, in this paper, we present a set of 22 elementary adaptation patterns (EAP), easy to understand, independent of any application domain and also independent of any adaptation engine. They have been translated to LAG [2] and GLAM [7] in order to plug them to existing adaptation engines. Note that, LAG is already plug on multiple adaptation engines and GLAM proposes its adaptation engine. These EAP are used in the EAP framework [9]. The EAP framework enables authors to define complex adaptation strategies, at a high level and independent of any adaptation engine. It assists authors to instantiate our EAP on their domain model, thus to define elementary adaptations. Each el- ementary adaptation is associated to a user characteristic. As a user has multiple characteristics at a time, the framework proposes a semi-automatic combination process of elementary adaptations to compose complex adaptation strategies3 . 2 Description of an elementary adaptation pattern We propose the following definition for elementary adaptation patterns (EAP), based on the definition of design patterns [5]. Definition 1. An elementary adaptation pattern describes a generic solution for a generic elementary adaptation problem. The solution is independent from any language, and it exploits the characteristics of the domain model. Definition 2. A generic elementary adaptation problem describes a criterion to select resources to be proposed and a criterion to define in which order the selected resources are going to be proposed. In the following, we define fundamental criteria to select resources and to orga- nize the selected resources on which EAP are based. Criteria used to select resources. They are based on the structure of the domain model. We argue that the general description of a domain model includes the following elements: a set of classes, which must contain the class representing all the resources to be proposed, most often known as Resource, and the class representing all the domain concepts, most often known as Concept. A set of relations between classes. Each relation defines a graph on instances of classes on which it is defined. The graph have to be navigated in order to reach user goals. A set of properties. Thereby, we have differentiated between criteria selecting resources and crite- ria defining a navigational path on relations. Our criteria for selecting resources are: (a) their belonging to a class, (b) the values of some properties, or (c) the presence of a relation through the resources or (d) the presence of a relation through the concepts. Furthermore, our criteria currently considered for defining a navigational path are either (a) depth-first, (b) breadth-first. 3 The most difficult part of the combination is done automatically. III Criteria used to order the selected resources. In [9], we have studied over works defining adaptation methods, by giving a particular interest for adap- tive navigation. We have retained four distinct and basic modes to select re- sources in a setting of adaptive navigation, as described below: a - Selection only mode provides a set of resources based on a criterion. Only the selected resources are proposed to users, the other ones are not proposed. For example, we propose only textual resources. b - Recommend selection mode provides multiple sets of resources (at least two) that include knowledge to specify which set should be recommended rather than the others. For example, to recommend definitions rather than examples. Both types of resources are accessible by users with distinct typo- graphic indication to identify which resources are recommended. c - Ordered selection mode provides multiple sets of resources (at least two), accompanied with knowledge to specify the order in which they must be pre- sented. Only one set of resources is proposed at a time, and the resources of a particular set are not proposed until all the resources of all sets of higher priority have been viewed by the user. For example, concepts can be selected and ordered using the successor relation defined between concepts. d - Alternate selection mode provides multiple sets of resources (at least two), accompanied with data that specifies the order in which they must be presented, knowing that only one set is presented to the user. For example, we propose textual resources when they are available, and audio resources in the absence of textual resources. Table 1 presents the characteristics retained from [5] and used to describe EAP. Name: is the name of the elementary adaptation pattern described. Intent: is a short statement about an elementary adaptation problem. It answers what is the elementary adaptation pattern supposed to do? i.e. what is its goal? Indeed, it indicates the way the resources are selected and the way they are presented. Solution: includes two elements: – Expressions: denote a set of resources to be proposed, and the conditions which have to be satisfied. These conditions can be represented in one or more logi- cal expressions. Those to be considered simultaneously are gathered in the same expression, while excluded conditions are expressed in different expressions. – Meta-expressions: a binary relation between two expressions. Indeed, when using multiple expressions, we specify the way they have to be considered using meta- expressions. Let E1 , E2 two expressions, we defined the following meta-expressions E1 ≺ E2 to define an ordered selection mode. E1 ] E2 to define a recommended selection mode. E1 | E2 to define an alternate selection mode. Constituents: describe the elements of the domain model used. Table 1: Description of elementary adaptation patterns IV 3 Organization of elementary adaptation patterns Based on the criteria defined above, we have defined a library of 22 EAP. In order to be able to look easily over them, we have organized them in a tree where each leaf is an EAP (cf. Figure 1). The tree is read from left to right and each EAP is based simultaneously on: 1 - One of the 4 selection modes of resources to be proposed, 2 - One of the 3 elements of the domain model involved in the selection process - When the element is a relation, we consider also one of the 2 types of navigation through the resources or the concepts graph4 . Type of navigation on Selection modes Elements of Classes related Navigational Patterns the domain model the domain model to relations path on instances ..1. Concept P 1.1.1 .1. Relations ..2. Resource P 1.1.2 P 1.2 .2. Classes P 1.3 1. Selection only .3. Properties ...1. Depth-first P 2.1.1.1 ..1. Concept ...2. Breath-first P 2.1.1.2 ...1. Depth-first P 2.1.2.1 .1. Relations ..2. Resource ...2. Breath-first P 2.1.2.2 2. Ordered .2. Classes Selection P 2.2 .3. Properties P 2.3 Adaptive ...1. Depth-first P 3.1.1.1 navigation ..1. Concept ...2. Breath-first P 3.1.1.2 ...1. Depth-first P 3.1.2.1 ..2. Resource .1. Relations ...2. Breath-first P 3.1.2.2 3. Recommended Selection .2. Classes P 3.2 .3. Properties P 3.3 ...1. Depth-first P 4.1.1.1 ..1. Concept ...2. Breath-first P 4.1.1.2 .1. Relations 4. Alternate ..2. Resource ...1. Depth-first P 4.1.2.1 Selection .2. Classes ...2. Breath-first P 4.1.2.2 .3. Properties P 4.2 P 4.3 Fig. 1. Typology of elementary adaptation patterns Just looking to the typology, we can deduce that the previous example of adaptation strategy (cf. Section 1) can be expressed using three separate EAP. Selecting select only textual resources is expressed using P1.3. Proposing ordered resources according to a successor relation is expressed using P2.1.2.1. Proposing resources related to theory before resources related to samples is expressed either 4 The two navigation modes are applied for all the selection modes except for the selection only mode, which proposes a set of resources according to a criterion. V using P2.2 if theory and sample are modeled as two classes in the domain model, or using P2.3 if theory and sample are modeled as an attribute of the Resource class in the domain model. We describe below our library of EAP per selection mode. Table 2 describes EAP using the selection only mode. P1.1.1, P1.1.2, P1.2 and P1.3 in Figure 1. Name: Selection Only - Relation - Concept Intent: It proposes resources that are linked to concepts by abstraction, and where P 1.1.1 each concept can reach the concept named goal directly/indirectly using relationi . Solution: Expression E1 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) E1 means that selected resources are linked to concepts using abstraction. The concepts can reach the goal using relationi . Constituents: See row 1, row 2 in Table 6 Name: Selection Only - Relation - Resource Intent: It proposes resources that can reach the resource named goal directly or P 1.1.2 indirectly using relationi . Solution: Expression E1 : linked-transitive(r, goal, relationi ) E1 means that selected resources are linked to concepts using abstraction and they can reach the goal using relationi . Constituents: See row 1, row 2 in Table 6 Name: Selection only - Classes Intent: It allows to select all resources of a specific type. P 1.2 Solution: Expression E1 : instanceOf (r, Class1 ) E1 means that selected resources are instances of the class Class1 . Constituents: See row 1, row 3 in Table 6 Name: Selection only- particular value of a property Intent: It allows to select resources according to some values of a property. P 1.3 Solution: Expression E1 : characteristicOf(r, propertyi , op, val) E1 means that selected resources must have the property propertyi and their value must satisfy the comparison test. Constituents: See row 1, row 4 in Table 6 Table 2: Elementary adaptation patterns using simple selection mode Table 3 describes EAP using the ordered selection mode. P2.1.1.1, P2.1.1.2, P2.1.2.1, P2.1.2.2, P2.2 and P2.3 in Figure 1. Name: Ordered Selection - Depth first- Relation - Concept Intent: It proposes resources according to a depth first navigational path on con- P 2.1.1.1 cepts. Solution: VI Expression – E1 : linked(currentR, concept’, abstraction) ∧ linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) ∧ linked(concept, concept’, relationi ) – E2 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) According to E1 selected resources are linked to concepts using abstraction. The concepts can reach the goal using relationi and are directly linked to current concept. According to E2 selected resources are linked to concepts using abstraction. The concepts can reach the goal using relationi . Meta-expressions E1 ≺ E2 According to this meta-expression, the set of resources selected by E1 is proposed before the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Ordered Selection - Relation - Concept - breadth first Intent: It proposes resources that are linked to concepts by abstraction, and where P 2.1.1.2 each concept can reach the concept named goal directly or indirectly using relationi according to a depth first navigational path. Solution: Expression – E1 : linked-transitive(concept2, goal, relationi ) ∧ linked(r, concept2, abstraction) ∧ distance(concept2, origin, relationi ) ∧ distance(concept, origin, relationi ) ∧ linked(currentR, concept, abstraction) – E2 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) According to E1 selected resources are linked to concepts using abstraction. The concepts are linked to the goal using relationi and have the same distance of the concept which is an abstraction of current resource from the first selected resource. According to E2 selected resources are linked to concepts using abstraction. The concepts can reach the goal using relationi . Meta-expressions E1 ≺ E2 According to this meta-expression, the set of resources selected by E1 is proposed before the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Ordered Selection - Relation - Resource - Depth-first Intent: It proposes resources that can reach the resource named goal directly or P 2.1.2.1 indirectly using relationi according to a depth first navigational path. Solution: Expression – E1 : linked-transitive(resource, goal, relationi ) ∧ linked(currentR, resource, relationi ) – E2 : linked-transitive(r, goal, relationi ) Meta-expressions E1 ≺ E2 VII According to this meta-expression, the set of resources selected by E1 is proposed before the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Ordered Selection - Relation - Resource - Breadth-first Intent: It proposes resources that can reach the resource named goal directly or P 2.1.2.2 indirectly using relationi according to a breadth first navigational path. Solution: Expression – E1 : linked-transitive(resource, goal, relationi ) ∧ distance(resource, origin, relationi ) ∧ distance(currentR, origin, relationi ) – E2 : linked-transitive(r, goal, relationi ) Meta-expressions E1 ≺ E2 According to this meta-expression, the set of resources selected by E1 is proposed before the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Ordered Selection - Classes Intent: It proposes ordered resources belonging only to subclasses of the class Re- P 2.2 source. Solution: Expression - E1 : instanceOf (r, Class1 ) - .... - En : instanceOf (r, Classn ) Meta-expressions Ei ≺ Ej , i < j, i = 1..n and j = 1..n. According to this meta-expression, the set of resources selected by Ei is proposed before the ones selected by Ej (i < j). Constituents: See row 1, row 3 in Table 6 Name: Ordered Selection - Properties Intent: It proposes ordered resources that satisfy some values of the property P 2.3 propertyi . Solution: Expression - E1 : characteristicOf(r, propertyi , op, val1 ) - .... - En : characteristicOf(r, propertyi , op, valn ) Meta-expressions Ei ≺ Ej , i < j, i = 1..n and j = 1..n. According to this meta-expression, the set of resources selected by Ei is proposed before the ones selected by Ej (i < j). Constituents: See row 1, row 4 in Table 6 Table 3: Elementary adaptation patterns using ordered selection mode Table 4 describes EAP using the recommended selection mode. P3.1.1.1, P3.1.1.2, P3.1.2.1, P3.1.2.2, P3.2 and P3.3 in Figure 1. VIII Name: Recommended Selection - Relation - Concept- Depth first P 3.1.1.1 Intent: It proposes recommended resources that are linked to concepts by abstraction, and where each concept can reach the concept named goal directly or indirectly using relationi according to a depth-first navigational. Solution: Expression – E1 : linked-transitive(concept2, goal, relationi ) ∧ linked(r, concept2, abstraction) ∧ linked(concept, concept2, relationi ) ∧ linked(currentResource, concept, abstraction) – E2 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) Meta-expressions E1 ] E2 According to this meta-expression, the set of resources selected by E1 is recom- mended rather than the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Recommended Selection - Relation - Concept - breadth first Intent: It proposes recommended resources that are linked to concepts by P 3.1.1.2 abstraction, and where each concept can reach the concept named goal directly or indirectly using relationi according to a depth first navigational path. Solution: Expression – E1 : linked-transitive(concept2, goal, relationi ) ∧ linked(r, concept2, abstraction) ∧ distance(concept2, origin, relationi ) ∧ distance(concept, origin, relationi ) ∧ linked(currentResource, concept, abstraction) – E2 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) Meta-expressions E3 ] E2 According to this meta-expression, the set of resources selected by E1 is recom- mended rather than the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Recommended Selection - Relation - Resource - Depth-first Intent: It proposes recommended resources that can reach the resource named goal P 3.1.2.1 directly or indirectly using relationi according to a depth first navigational path. Solution: Expression – E1 : linked-transitive(resource, goal, relationi ) ∧ linked(currentResource, re- source, relationi ) – E2 : linked-transitive(r, goal, relationi ) Meta-expressions E4 ] E5 According to this meta-expression, the set of resources selected by E1 is recom- mended rather than the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Recommended Selection - Relation - Resource - Breadth-first P 3.1.2.2 IX Intent: It proposes recommended resources that can reach the resource named goal directly or indirectly using relationi according to a breadth first navigational path. Solution: Expression – E1 : linked-transitive(resource, goal, relationi ) ∧ distance(resource, origin, relationi ) ∧ distance(currentResource, origin, relationi ) – E2 : linked-transitive(r, goal, relationi ) Meta-expressions E1 ] E2 According to this meta-expression, the set of resources selected by E1 is recom- mended rather than the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Recommended Selection - Classes Intent: It proposes recommended resources according to their type. P 3.2 Solution: Expression – E1 : instanceOf (r, Class1 ) – ... – En : instanceOf (r, Classn ) Meta-expressions Ei ] Ej , i < j, i = 1..n and j = 1..n. According to this meta-expression, the set of resources selected by Ei is recom- mended rather than the ones selected by Ej (i < j). Constituents: See row 1, row 3 in Table 6 Name: Recommended Selection - Properties Intent: It proposes resources that satisfy some values of the property propertyi . P 3.3 Solution: Expression – E1 : characteristicOf(r, propertyi , op, val1 ) – .... – En : characteristicOf(r, propertyi , op, valn ) Meta-expressions Ei ] Ej , i < j, i = 1..n and j = 1..n. According to this meta-expression, the set of resources selected by Ei is recom- mended rather than the ones selected by Ej (i < j). Constituents: See row 1, row 4 in Table 6 Table 4: Elementary adaptation patterns using recommended selection Table 5 describes EAP using the alternate selection mode. P4.1.1.1, P4.1.1.2, P4.1.2.1, P4.1.2.2, P4.2 and P4.3 in Figure 1. Name: Alternate Selection - Relation - Concept- Depth first P 4.1.1.1 X Intent: It proposes alternate resources that are linked to concepts by abstraction, wher each concept can reach the concept named goal directly/indirectly using relationi according to a depth-first navigational. Solution: Expression – E1 : linked-transitive(concept2, goal, relationi ) ∧ linked(r, concept2, abstraction) ∧ linked(concept, concept2, relationi ) ∧ linked(currentResource, concept, abstraction) – E2 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) Meta-expressions E1 | E2 According to this meta-expression, the set of resources selected by E1 is alternate of the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Pattern 4.1.1.2 Name: Alternate Selection - Relation - Concept - breadth first Intent: It proposes alternate resources that are linked to concepts by abstraction, and where each concept can reach the concept named goal directly/indirectly using relationi according to a depth first navigational path. Solution: Expression – E1 : linked-transitive(concept2, goal, relationi ) ∧ linked(r, concept2, abstraction) ∧ distance(concept2, origin, relationi ) ∧ distance(concept, origin, relationi ) ∧ linked(currentResource, concept, abstraction) – E2 : linked-transitive(concept, goal, relationi ) ∧ linked(r, concept, abstraction) Meta-expressions E1 | E2 According to this meta-expression, the set of resources selected by E1 is alternate of the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Pattern 4.1.2.1 Name: Alternate Selection - Relation - Resource - Depth-first Intent: It proposes alternate resources that can reach the resource named goal di- rectly/indirectly using relationi according to a depth first navigational path. Solution: Expression – E1 : linked-transitive(resource, goal, relationi ) ∧ linked(currentResource, re- source, relationi ) – E2 : linked-transitive(r, goal, relationi ) Meta-expressions E1 | E2 According to this meta-expression, the set of resources selected by E1 is alternate of the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Alternate Selection - Relation - Resource - Breadth-first Pattern 4.1.2.2 Intent: It proposes alternate resources that can reach the resource named goal di- rectly/indirectly using relationi according to a breadth first navigational path. XI Solution: Expression – E1 : linked-transitive(resource, goal, relationi ) ∧ distance(resource, origin, relationi ) ∧ distance(currentResource, origin, relationi ) – E2 : linked-transitive(r, goal, relationi ) Meta-expressions E1 | E2 According to this meta-expression, the set of resources selected by E1 is alternate of the ones selected by E2 . Constituents: See row 1, row 2 in Table 6 Name: Alternate Selection - Classes Pattern 4.2 Intent: It proposes alternative resources according to their type. Solution: Expression – E1 : instanceOf (r, Class1 ) – ... – En : instanceOf (r, Classn ) Meta-expressions Ei | Ej , i < j, i = 1..n and j = 1..n. According to this meta-expression, the set of resources selected by Ei is an alter- native of the ones selected by Ej (i < j). Constituents: See row 1, row 3 in Table 6 Name: Alternate Selection - Properties Pattern 4.3 Intent: It proposes alternative resources, where each of them satisfy a value of the property propertyi . Solution: Expression – E1 : characteristicOf(r, propertyi , op, val1 ) – .... – En : characteristicOf(r, propertyi , op, valn ) Meta-expressions Ei | Ej , i < j, i = 1..n and j = 1..n. According to this meta-expression, the set of resources selected by Ei is alternate of the ones selected by Ej (i < j). Constituents: See row 1, row 4 in Table 6 Table 5: Elementary adaptation patterns using alternate selection mode row1 r: represents an instance of the class Resource or of one of its specializations. row2 concept: represents an instance of the Concept class. goal: represents the goal to reach. It is an instance of Concept class. currentResource: represents an instance of the current resource. relationi : represents a relation between instances of the Concept class. origin: represents the first resources proposed to the user. XII abstraction: represents a relation between an instance of the Concept class and instance(s) of the Resource class or of one of its specializations. row3 Classi : represents a subclass of the Resource class. row4 propertyi : represents a property of the Resource class. val: represents a possible value for the property propertyi . Table 6: Constituents used in elementary adaptation patterns 4 Discussion and conclusion Concerning the domain model, we argue that whatever the domain model, it is composed of a set of classes, of properties and relations [7, 4, 2]. Therefore our EAP are independent of any domain model. Concerning the adaptive navigation, we have conducted a study [9] of sup- ported types of adaptive navigation and we have included all of them in our EAP. In case, we didn’t consider a type of adaptive navigation, our EAP are extensible to support missing types of adaptive navigation. We also argue that a user model is always composed of a set of characteristics. For any user model, our framework is generic to consider any user characteristics. The EAP framework enables to associate a value of a user characteristic to an instantiation of EAP. Afterward, it generate complex adaptation strategies basing on combinations of user characteristics. References 1. P. Brusilovsky, J. Eklund, and E. Schwarz, “Web-based education for all: a tool for development adaptive courseware,” Comput. Netw. ISDN Syst., vol. 30, pp. 291–300, April 1998. 2. A. Cristea and L. Calvi, “The three layers of adaptation granularity,” in Proceed- ings of the 9th int. conference on User modeling, ser. UM’03. Berlin, Heidelberg: Springer, 2003, pp. 4–14. 3. P. Brusilovsky, “Adaptive navigation support for open corpus hypermedia systems,” in AH, 2008, pp. 6–8. 4. P. De Bra, D. Smits, and N. Stash, “Creating and delivering adaptive courses with aha!” in 1st Eur. Conf. on Technology Enhanced Learning, ser. 0302-9743, LNCS, Ed. Springer, 2006, pp. 21–33. 5. E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995. 6. E. Knutov, P. De Bra, and M. Pechenizkiy, “Ah 12 years later: a comprehensive survey of adaptive hypermedia methods and techniques,” New Rev. Hypermedia Multimedia, vol. 15, pp. 5–38, April 2009. 7. C. Jacquiot, Y. Bourda, F. Popineau, A. Delteil, and C. Reynaud, “Glam: A generic layered adaptation model for adaptive hypermedia systems,” in AH, 2006, pp. 131– 140. 8. C. Stewart, A. Cristea, T. Brailsford, and H. Ashman, “Authoring once, delivering many: Creating reusable adaptive courseware,” in WBE 2005 Conference, 2005. 9. N. Zemirline, Y. Bourda, and C. Reynaud, “Expressing adaptation strategies using adaptation patterns,” in TLT. Accepted, to appear, 2011.