Lise Hobeika

Séverine Samson

Why do music-based interventions benefit persons with neurodegenerative disease?

Keywords: Alzheimer disease, music intervention, non-verbal communication, interpersonal coordination, rhythmic entrainment, social engagement

Alzheimer disease (AD) is a neurodegenerative disease impacting cognitive, emotional, and social functioning. Given the limited effectiveness of the pharmacological approach in overcoming these difficulties, the development of non-drug treatment and particularly music-based interventions appear to be an efficient tool to overcome those difficulties. However, the factors that explain their efficacy are not clarified yet. Music is a fundamental human activity that can have a strong emotional and cognitive impact. Moreover, musical interventions promote social interactions during which participants coordinate their movements to a common rhythm. In this chapter, we will discuss the idea that interpersonal coordination supported by music can improve social functioning and non-verbal communication in patients with AD. We will also propose methods to study the benefits of music interventions on aged persons in clinical context and in particular in patients with AD.

Introduction

For a long time, musical practices with a therapeutic vocation have existed and its use in this context has considerably amplified during the last decades [START_REF] Sihvonen | Music-based interventions in neurological rehabilitation[END_REF][START_REF] Van Der Steen | Music-based therapeutic interventions for people with dementia ( Review )[END_REF]. Widely relayed by the media, music-based interventions have shown growing success in persons with neurodegenerative disease and their caregivers. An important field of application of these methods concerns the management of the different stages of cortical neurodegenerative pathologies such as Alzheimer's disease (AD). Considering the limited impact of pharmacological treatments with the iatrogenic effects of medication in these patients, several health institutions recommended in parallel the development of non-pharmacological approaches to alleviate some symptoms (National Institute for Health and Care Excellence, 2018).

AD is a neurodegenerative disorder that is associated with several cognitive and emotional deficits. Symptoms usually include memory [START_REF] Hodges | Memory in the dementias[END_REF], and mood dysfunction [START_REF] Christensen | A quantitative review of cognitive deficits in depression and Alzheimer-type dementia[END_REF] and, in particular, depression and anxiety [START_REF] Chu | The Impact of Group Music Therapy on Depression and Cognition in Elderly Persons With Dementia: A Randomized Controlled Study[END_REF]. These deficits have been associated with behavioral disorders such as agitation, and sometimes aggressiveness, which are the main causes of patients' institutionalization [START_REF] Luppa | Prediction of institutionalisation in dementia: A systematic review[END_REF][START_REF] Toot | Causes of nursing home placement for older people with dementia : a systematic review and metaanalysis[END_REF] and are also at the root of caregivers' suffering [START_REF] Black | A systematic review of the association between the Behavioral and Psychological Symptoms of Dementia and burden of care[END_REF]. All together, these difficulties lead to a progressive social deterioration, including a loss of sense of self and identity [START_REF] Caddell | The impact of dementia on self and identity: A systematic review[END_REF], and weakening of interpersonal relationships that may stem from a decline in emotional comprehension [START_REF] Shimokawa | Influence of deteriorating ability of emotional comprehension on interpersonal behavior in Alzheimer-type dementia[END_REF], and communication difficulties [START_REF] Feyereisen | Pragmatic skills in the early stages of Alzheimer ' s disease : an analysis by means of a referential communication task[END_REF][START_REF] Potkins | Language impairment in dementia: Impact on symptoms and care needs in residential homes[END_REF]. Such social dysfunctions might be aggravated by patients' decline of verbal function, and may impact as well organization of units and staff. The most common language deficits are lexical access, as well as speech disfluencies such as aposiopesis (sentences left unfinished), logorrhea (excessive wordiness with incoherent talkativeness), palilalia (repetition of syllables, words or phrases; [START_REF] Hier | Language disintegration in dementia: Effects of etiology and severity[END_REF], abnormal turn-taking [START_REF] Perkins | Conversing in dementia: A conversation analytic approach[END_REF][START_REF] Ripich | Comparing the effects of different individualized music interventions for elderly individuals with severe dementia[END_REF], and empty discourse [START_REF] Nicholas | Empty speech in alzheimers disease and fluent aphasia[END_REF]. In more severely detoriated patients, language can be totally absent [START_REF] Caramelli | Language and Communication Disorders in Dementia of the Alzheimer Type[END_REF]. Thus, AD patients' attempts to share their thoughts or engage in dialogue for social purposes may go unnoticed because of their verbal communication deficits [START_REF] Potkins | Language impairment in dementia: Impact on symptoms and care needs in residential homes[END_REF][START_REF] Small | The discourse of self in dementia[END_REF]. The combination of memory, mood and communication disorders increases social isolation reducing therefore the quality of life of patients with neurodegenerative diseases [START_REF] Klimova | Alzheimer's disease and language impairments: social intervention and medical treatment[END_REF]. However, while verbal communication is impaired, non-verbal communication appears to be relatively spared at least in these cases reports [START_REF] Tzortzis | Absence of amusia and preserved naming of musical instruments in an aphasic composer[END_REF][START_REF] Warren | Nothing to Say, Something to Sing: Primary Progressive Dynamic Aphasia[END_REF]. It has therefore been proposed that non-verbal skills might compensate verbal difficulties in these patients [START_REF] Schiaratura | Expression verbale et gestualité dans la maladie d ' Alzheimer : une étude en situation d ' interaction sociale[END_REF].

Musical interventions are thought to improve mood regulation, social functioning and cognition of patients with AD, as well as the well-being of their caregivers. However, the factors that explain their therapeutic efficacy are not yet clarified. In our chapter, we want to shed light on the intervention elements that appear to benefit patients with different stages of the AD, and will discuss the idea that synchronization to music, which is relatively spared even in advanced stages of the disease, can enhance inter-personal coordination, and thus can improve social functioning and sustain non-verbal communication skills. For this purpose, we will also review the evidence from psychology, neuroscience and embodied music cognition that may have important implications to understand and to improve the efficacy of music-based interventions in patients with AD.

Music-based interventions in patients with Alzheimer's disease

Several reasons justify the use of music as a privileged support for therapy. Appreciated by patients of all ages, backgrounds and socio-cultural levels, music is widely accessible, easy to utilize, enjoyed by the majority of people and thus a potentially playful and motivating tool for rehabilitation. Indeed, music naturally conveys strong emotions [START_REF] Koelsch | Brain correlates of music-evoked emotions[END_REF] and induces extremely pleasurable experiences such as chill [START_REF] Blood | Intensely pleasurable responses to music correlate with activity in brain regions implicated in reward and emotion[END_REF][START_REF] Pankseep | The Emotional Sources of " Chills " Induced by Music[END_REF]. It seems that patients with Alzheimer's disease retain an intriguing sensitivity to music, even at advanced stages [START_REF] Baird | Music and dementia[END_REF][START_REF] Cuddy | Music, memory, and Alzheimer's disease: Is music recognition spared in dementia, and how can it be assessed?[END_REF][START_REF] Johnson | Music recognition in frontotemporal lobar degeneration and Alzheimer disease[END_REF]. Music can trigger souvenirs, such as autobiographical memory [START_REF] Baird | Music evoked autobiographical memory after severe acquired brain injury: Preliminary findings from a case series[END_REF][START_REF] Cuddy | Music-evoked autobiographical memories (MEAMs) in alzheimer disease: Evidence for a positivity effect[END_REF][START_REF] El Haj | Music Enhances Autobiographical Memory in Mild Alzheimer's Disease[END_REF]. As demonstrated by neuroimaging and pharmacological studies in healthy participants, music can modulate emotional state and motivation [START_REF] Ferreri | Dopamine modulates the reward experiences elicited by music[END_REF][START_REF] Mas-Herrero | Modulating musical reward sensitivity up and down with transcranial magnetic stimulation[END_REF][START_REF] Salimpoor | Interactions between the nucleus accumbens and auditory cortices predict music reward value[END_REF][START_REF] Salimpoor | Predictions and the brain: How musical sounds become rewarding[END_REF]. Its unique ability to elicit both emotions and memories means that it can potentially provide a link to the person's past. Furthermore, music can be a social activity. It is commonly used for communication [START_REF] Mehr | Form and Function in Human Song[END_REF] thus may promote feelings of interconnectedness among patients and between patients their caregivers. Overall, music appears as an ideal media to present to persons with potential memory and mood disorders and diminished social interactions. [START_REF] Ripich | Comparing the effects of different individualized music interventions for elderly individuals with severe dementia[END_REF][START_REF] Särkämö | Cognitive, emotional, and social benefits of regular musical activities in early dementia: Randomized controlled study[END_REF]. In a study in which short-and long-term effects of such interventions were assessed, Sakamoto and colleagues (2013) showed that the active interventions requiring patients to sing and to dance on music led to the greatest improvement in emotional state and better long-term reduction of behavioral problems. In another study, Särkämo and colleagues also demonstrated that both types of music interventions improved mood and remote episodic memory. However, only the active interventions enhanced short-term and working memory, and caregiver well-being [START_REF] Särkämö | Cognitive, emotional, and social benefits of regular musical activities in early dementia: Randomized controlled study[END_REF]. Taken together, these findings support the idea that involving patients with AD at the motor level in the musical interventions may provide most important benefits. An potential explanation of the advantage of active intervention is first the emotional content. We know that moving to the rhythm of music provides pleasure [START_REF] Janata | Sensorimotor coupling in music and the psychology of the groove[END_REF]. The audiomotor coupling and the temporal expectations produced by the perception of the musical beat would stimulate the reward brain network, inducing therefore pleasure [START_REF] Salimpoor | Anatomically distinct dopamine release during anticipation and experience of peak emotion to music[END_REF]. Moreover, an important component of those interventions is the social aspect. Some studies suggest that the social context modify music perception. Thus, the presence of a singerwhich is often the case in active interventions -can improve the engagement of patients in the musical task compared to a music recording [START_REF] Holmes | Keep music live: music and the alleviation of apathy in dementia subjects[END_REF][START_REF] Lesaffre | Dementia treatment strategies[END_REF][START_REF] Sherratt | Music interventions for people with dementia: A review of the literature[END_REF]. Moreover, sharing a musical rhythm with others may be a way to connect with them and share positive emotions [START_REF] Tarr | Music and social bonding : " self-other " merging and neurohormonal mechanisms[END_REF]. Therefore, we propose that the therapeutic benefits of music lie in its hedonic and emotional component coupled with its role in communication and in the creation of social bonds (social bonding), which patients are often lacking. However, the mechanisms underlying the beneficial impacts of music in these patients and the extent to which the efficacy of music seems to surpass that of other pleasant activities need to be further explored.

Music

Interpersonal coordination in music to improve social functioning

Motor behaviors and social bonding

When verbal communication is impaired, patients with AD may rely on non-verbal communication to connect with others [START_REF] Schiaratura | Expression verbale et gestualité dans la maladie d ' Alzheimer : une étude en situation d ' interaction sociale[END_REF]. Non-verbal communication describes conscious or unconscious behaviors that share information about our mental state to others without the use of language. Non-verbal communication can take various forms such as facial expressions, body posture, interpersonal distances or eye gaze contact. All these behaviors can be used to communicate to others information about our intentions, our emotional state or our willingness to bond with them.

Other non-verbal communication behaviors rely on the coordination of movements with others in time and space, i.e. interpersonal coordination. Interpersonal coordination is at the core of social life, as it is necessary for most social interactions to succeed: such as doing collective sports, moving a piece of furniture with a friend or even having a conversation. In the musical domain, interpersonal coordination such as singing, dancing or music playing in group are activities that allow communicating to others the willingness to bond. Anthropologists suggest that those musical activities, found in churches, in armies or in sport teams, create a feeling of cohesion between individuals by weakening the boundaries between the self and the group [START_REF] Ehrenreich | Dancing in the streets: A history of collective joy[END_REF][START_REF] Radcliffe-Brown | Structure and function in primitive society[END_REF]. It has also been shown that individuals singing in unison, or moving together on musical beats have a higher tendency to cooperate with each others [START_REF] Hove | It's All in the Timing: Interpersonal Synchrony Increases Affiliation[END_REF][START_REF] Mogan | To be in synchrony or not? A meta-analysis of synchrony's effects on behavior, perception, cognition and affect[END_REF]. This effect is not specific to musical interaction. Moving together by simply walking in step, rocking chairs synchronously or tapping to a metronome beat with others can promote social cohesion [START_REF] Demos | Rocking to the beat: effects of music and partner's movements on spontaneous interpersonal coordination[END_REF][START_REF] Reddish | Let ' s Dance Together : Synchrony , Shared Intentionality and Cooperation[END_REF][START_REF] Wiltermuth | Synchrony and cooperation[END_REF]. Thus, singing or music making can be a form of non-verbal communication between individuals, promoting cohesion and cooperation between individuals.

At the physiological level, the social effect of interpersonal coordination seems to be associated with the release of oxytocin. As reported by several authors, this neurohormone is known for its role in social behaviors, as it induces increase in trust [START_REF] Kosfeld | Oxytocin increases trust in humans[END_REF], cooperation [START_REF] Zhang | Oxytocin promotes synchronized out-group attack during intergroup conflict in humans[END_REF] and empathy [START_REF] Domes | Oxytocin Improves "Mind-Reading" in Humans[END_REF]. Synchronized behaviors could also stimulate the endogenous opioid system and particularly endorphins, which are neurohormones associated with pleasure and well-being, and have a role in social bonding in human and non-human primate [START_REF] Cohen | Rowers' high: behavioural synchrony is correlated with elevated pain thresholds[END_REF][START_REF] Martel | Effects of opioid receptor blockade on the social behavior of rhesus monkeys living in large family groups[END_REF][START_REF] Schino | Opiate receptor blockade in juvenile macaques: effect on affiliative interactions with their mothers and group companions[END_REF][START_REF] Tarr | Music and social bonding : " self-other " merging and neurohormonal mechanisms[END_REF]. We can therefore suggest that physiological responses resulting from interpersonal coordination activities could, at least in part, mediate the impact of musical interventions on social interactions.

In active musical interventions, patients with AD spontaneously sing or move with the musical rhythm with others (i.e. therapist, other patients or caregivers). We hypothesize that the success of those interventions may in part rely on their benefits on social behaviors. Moving on music with others could induce patients with AD to interact positively with others, to feel included in a group, and thus to improve social functioning. It could also increase trust and collaboration with the surroundings and with the caregivers. This interpretation, based on hypotheses raised by the study of healthy young adults, deserves to be tested in aged populations. Although it seems in coherence with the fact that participatory musical interventions have greater efficacy than receptive ones on patients with AD well-being (see section 1), further research is still needed to better understand the social cognitive functioning of these patients, and their communication behaviors.

Social cognition abilities

The few studies investigating social cognitive abilities in patients with AD found a decreased in theory of mind (Fernandez-Duque, [START_REF] Fernandez-Duque | Falsebelief understanding in frontotemporal dementia and Alzheimer's disease[END_REF][START_REF] Gregory | Theory of mind in patients with frontal variant frontotemporal dementia and Alzheimer's disease: theoretical and practical implications[END_REF], emotion recognition [START_REF] Albert | Perception of Affect in Patients With Dementia of the Alzheimer Type[END_REF][START_REF] Bediou | Impaired social cognition in mild alzheimer disease[END_REF] and empathy (Fernandez-Duque, [START_REF] Fernandez-Duque | Empathy in frontotemporal dementia and Alzheimer's disease[END_REF]. These high-order social cognitive functions allow the understanding of others and support non-verbal communication. By using active music interventions in pathological as well as in physiological aging, we can expect to stimulate social cognitive abilities and to maintain these skills as long as possible. Since no study has addressed the relationship between interpersonal coordination and social cognitive abilities in AD, we will report evidence obtained in individuals with typical and atypical development. We are aware that the explanatory factors are very different in neurodevelopmental and degenerative pathology. However, even if the pathological contexts are different, we may treat similar social symptoms with the same procedure. These results may be used as a basis for finding methods to stimulate social capacities in AD, whose implementation will require adaptation.

According to a large literature, the development of social cognition skills is partially linked to interpersonal coordination, synchronization and imitation [START_REF] Asendorpf | Self-Awareness and Other-Awareness: Mirror Self-Recognition and Synchronic Imitation Among Unfamiliar Peers[END_REF]Feldman, 2007bFeldman, , 2007a;;[START_REF] Harrist | Dyadic synchrony: Its structure and function in children's development[END_REF]. In a longitudinal study testing the development of empathy on children, Feldman (2007a) found an association between mother-infant synchrony at 3 months and empathy capacities of adolescents at 13 years (Feldman, 2007a). Engaging in interpersonal coordination may be a way to restore social cognition skills. Some evidence to support this idea is provided in a recent study on individuals with autism spectrum disorder. In this study a training program based on dance and movements (focusing on interpersonal synchronization and imitation) improved their social abilities [START_REF] Koehne | Fostering Social Cognition through an Imitation-and Synchronization-Based Dance/Movement Intervention in Adults with Autism Spectrum Disorder: A Controlled Proof-of-Concept Study[END_REF].

The link between interpersonal synchronization and social cognition abilities reported in these studies is usually explained by the fact that the understanding of others' actions may be based on motor resonance, i.e. the mapping of others' action in our own motor repertoire [START_REF] Panasiti | The bright and the dark sides of motor simulation[END_REF]. The so-called mirror system is activated during both the observation and the realization of the same action [START_REF] Aglioti | Action anticipation and motor resonance in elite basketball players[END_REF][START_REF] Calvo-Merino | Action observation and acquired motor skills: an FMRI study with expert dancers[END_REF]. Engaging individuals in interpersonal synchronization may be an appropriate way to stimulate this association between observation and motor resonance, boosting therefore the ability to understand others' action.

Interestingly, music interventions appear as perfect situations to engage in interpersonal synchronization.

In participatory musical interventions, individuals can easily synchronize their movements thanks to the presence of musical rhythm. It would also be interesting to test if the success of those interventions can be linked to an improvement in social cognitive functioning of patients with AD, and particularly to an amelioration of empathy, emotions recognition and theory of mind. However, to provide support to these findings or interpretations, appropriate evaluating tools and methods to measure synchronization to music and to others should be designed.

Methodological aspects related to the impact of musical intervention in patients with AD

A large number of studies claim positive effects of music-based interventions on emotions, well-being, social functioning, and even sometimes on cognition in patients with AD, as well as on caregivers well-being [START_REF] Choi | Effects of group music intervention on behavioral and psychological symptoms in patients with dementia: A pilot-controlled trial[END_REF][START_REF] Raglio | Music, music therapy and dementia: A review of literature and the recommendations of the Italian Psychogeriatric Association[END_REF][START_REF] Svansdottir | Music therapy in moderate and severe dementia of Alzheimer's type: A case-control study[END_REF][START_REF] Ueda | Effects of music therapy on behavioral and psychological symptoms of dementia: A systematic review and metaanalysis[END_REF]). Yet, those conclusions need to be interpreted with caution. The results of a recent meta-analysis questions the validity of such positive effects [START_REF] Van Der Steen | Music-based therapeutic interventions for people with dementia ( Review )[END_REF].

Indeed, many studies still have methodological biases that weakened the conclusions: small sample sizes, lack of blind assessors, lack of randomization, the absence of a control group with no intervention (i.e. with treatment as usual) and of a group with a control (non-musical) intervention. This latter group is necessary to control for social stimulation and hedonic factors, to determine whether or not any pleasant social activity could have similar effects. Moreover, the potency of the treatment vary considerably between individuals. More studies need to be conducted to document the efficacy of music on patients with AD.. As already mentioned, the proposed musical activities in those prior studies cover a large variety of skills from music listening individually to music playing in groups. Therefore, it is not surprising that the reported studies lead to inconsistent results. Two main characteristics of those interventions can impact their potential effects: the social context (alone or in social presence) and as mentioned above, the type of intervention (passive or active intervention) (see Figure 1). These characteristics can change patients' engagement during the interventions, the pleasure felt but also the impact of such interventions on the social, emotional and cognitive functioning. To disentangle the influence of those factors and to understand the mechanisms underlying the positive impact of musical interventions, wellcontrolled studies using multimodal data , such as cognitive, emotional, social or psychophysiological recordings, are necessary.

Usually, the evaluation of musical interventions' impact includes the assessment of patients' mood and behavior as well as caregivers' quality of life. These evaluations are often performed using questionnaires filled by the patient (selfreported evaluation) or by a family or medical caregiver (hetero evaluation), depending on the disease progression. Frequently used questionnaires are the Behavior Pathology in Alzheimer's Disease Ratings Scale (BEHAVE-AD) that rates behavioral problems of dementia [START_REF] Reisberg | Behavioral pathology in Alzheimer's disease (BEHAVE-AD) rating scale[END_REF], the Cohen-Mansfield Inventory (CMAI) which rates agitated behaviors [START_REF] Cohen-Mansfield | A description of agitation in a nursing home[END_REF], the State-Trait Anxiety Inventory for Adults (STAI-A) that assesses mood and anxiety [START_REF] Spielberger | Manual for the State-Trait Anxiety Inventory[END_REF]) and the NeuroPsychiatric Inventory (NPI) which evaluates the severity and frequency of several behavioral functioning (e.g. delusions, hallucinations, agitation, disinhibition, sleep abnormalities) as well as caregivers distress [START_REF] Sisco | Les troubles du comportement chez le sujet dément en institution: évaluation à partir de l'inventaire neuropsychiatrique pour les équipes soignantes (NPI/ES)[END_REF].

The questionnaires can be completed by objective measures such as the evaluation of physiological changes induced by musical intervention. Indeed, measures of cortisol level can be a marker of patients stress levels [START_REF] Kirschbaum | Salivary cortisol in psychoneuroendocrine research: recent developments and applications[END_REF]. Heart rate and blood pressure can also constitute an interesting marker of patients' affective state (de Witte, Spruit, [START_REF] De Witte | Effects of Music Interventions on Stress-Related Outcomes: A Systematic Review and Two Meta-Analyses[END_REF][START_REF] Ripich | Comparing the effects of different individualized music interventions for elderly individuals with severe dementia[END_REF]. However, we still need additional studies to confirm their relevance to examine the effect of music-based interventions on psychophysiological responses in patients with AD. Quantitative measures of patients' engagement should also be considered to study the benefits of music-based interventions. Engagement in the musical activity can be analyzed at the motor, the emotional or the social level. Motor engagement is evaluated by the spontaneous motor reaction with music. Music is built on a strong regular rhythm that elicits spontaneous motor responses in listeners [START_REF] Fraisse | Rhythm and Tempo[END_REF]: people have the tendency to move in synchrony with musical beats [START_REF] Leman | The empowering effects of being locked into the beat of the music[END_REF][START_REF] Repp | Sensorimotor synchronization : A review of the tapping literature[END_REF]. The production of behaviors like singing, clapping, or the global quantity of body movements can provide measures of patients rhythmic entrainment with the music (Ghilain et al., in prep.;[START_REF] Holmes | Keep music live: music and the alleviation of apathy in dementia subjects[END_REF][START_REF] Lesaffre | Dementia treatment strategies[END_REF][START_REF] Sherratt | Music interventions for people with dementia: A review of the literature[END_REF]. The emotional engagement can be evaluated using methods from social psychology [START_REF] Schiaratura | Non-verbal communication in Alzheimer's disease[END_REF]. The production of non-verbal behaviors in patients with dementia have already been successfully measured in studies that have found benefits of music interventions [START_REF] Narme | Efficacy of Musical Interventions in Dementia: Evidence from a Randomized Controlled Trial[END_REF]. The measurements of the production of emotional facial or vocal expressions, or of body postures and gestures seem to be very promising markers of patients' emotional state. They can be decoded from video recordings of the participants, providing information related to the quality of nonverbal behaviors produced in response to music listening or practicing.

Music-based interventions in groups can be analyzed as a joint action supported by the presence of music. The degree of synchronization between participants' behaviors reflects social engagement. As already mentioned, individuals tend to synchronize their behaviors with others', and especially rhythmic movements when they are in a group. This spontaneous interpersonal synchronization, called motor entrainment or alignment, has been observed in laboratory studies, in which dyads of participants unconsciously or voluntarily synchronized their finger tapping [START_REF] Oullier | Social coordination dynamics : Measuring human bonding[END_REF], their steps while walking side by side (van Ulzen, Lamoth, [START_REF] Van Ulzen | Characteristics of instructed and uninstructed interpersonal coordination while walking side-by-side[END_REF] or the rhythm of rocked chairs sways [START_REF] Richardson | Rocking together : Dynamics of intentional and unintentional interpersonal coordination[END_REF]. We can therefore propose that interpersonal synchronization of rhythmic movements might provide relevant indexes to measure patients' engagement with others in a musical context [START_REF] Ghilain | Is music special for people with dementia[END_REF]. In addition, the synchronization of individuals' posture, gestures, facial expression and eye gaze, which have long been regarded as the regulators of social interaction, are notably important for the development of rapport and personal relationships [START_REF] Lakin | The chameleon effect as social glue: evidence for the evolutionary significance of nonconscious mimicry[END_REF]. Rigorous measures to quantify the production of rhythmic joint actions in musical activities should be developed to examine their relationships with social cognitive abilities.

Finally, patients' rhythmic abilities can also be measured by asking participants to tap along with the musical beat. Sensorimotor precision in tapping tasks gives a measure of individuals' prediction and adaptative abilities [START_REF] Keller | Rhythm in joint action : psychological and neurophysiological mechanisms for real-time interpersonal coordination[END_REF]. The variability of the tapping can be provided by assessing the sensorimotor consistency [START_REF] Dalla Bella | BAASTA : Battery for the Assessment of Auditory Sensorimotor and Timing Abilities[END_REF]. Usually, such rhythmic behaviors are measured in tasks involving finger or hand tapping with music or metronome beats. Very few studies examined this type of rhythmic abilities in patients with AD or mild cognitive impairment [START_REF] Kluger | Motor/Psychomotor Dysfunction in Normal Aging, Mild Cognitive Decline, and Early Alzheimer's Disease: Diagnostic and Differential Diagnostic Features[END_REF][START_REF] Suzumura | Assessment of finger motor skills in individuals with mild cognitive impairment and patients with Alzheimer's disease: Relationship between finger-tothumb tapping and cognitive function[END_REF]. Even if gross motor skills appear clinically normal at the early stage of AD, motor control deficits may be associated with disease progression [START_REF] Bangert | Keep up the pace: Declines in simple repetitive timing differentiate healthy aging from the earliest stages of Alzheimer's disease[END_REF][START_REF] Kluger | Motor/Psychomotor Dysfunction in Normal Aging, Mild Cognitive Decline, and Early Alzheimer's Disease: Diagnostic and Differential Diagnostic Features[END_REF][START_REF] Suzumura | Assessment of finger motor skills in individuals with mild cognitive impairment and patients with Alzheimer's disease: Relationship between finger-tothumb tapping and cognitive function[END_REF]). Yet, they often pass undetected in comparison to cognitive impairments and to decline in daily living activities [START_REF] De Paula | Impairment of fine motor dexterity in mild cognitive impairment and Alzheimer's disease dementia: Association with activities of daily living[END_REF][START_REF] Yan | Alzheimer's disease and mild cognitive impairment deteriorate fine movement control[END_REF]. A careful examination of the accuracy and the variability of sensorimotor synchronization with musical rhythms might offer additional and relevant behavioral markers of interpersonal coordination and deserve to be examined in patients with AD disease.

Conclusion

Music is a universal human activity that can play a key role in communication, social interaction, and mood regulation. The richness of music on the emotional, motor and social stimulations might explain the success of music-based interventions as a non-pharmacological treatment for patients with AD. Among the different musical activities responsible to their effectiveness, the synchronization of movements to the musical rhythm, which is relatively spared even in advanced stages of AD, is largely used. It seems to induce a lot of pleasure, improve emotion regulation, stimulate motor control as well as social functioning. However, more specific and control studies with appropriate and innovative tools need to be developed to assess and to train elderly persons. Such technical and scientific progresses that combine methods from psychology, neuroscience and embodied music cognition will allow a better understanding of the factors that contribute to the positive effect of music-based interventions in patients with AD. This knowledge will help to design rhythmic training programs. By adapting the musical activities to the patients' needs, personalized training sessions will be proposed to reduce social isolation and to improve the quality of life of elderly people and of their family and medical caregivers.

Figure 1 :

 1 Figure 1 : Musical-based interventions can be classified according to the social context (alone or in social presence) and the motor engagement (passive or active)

  However, the few studies examining active and passive music-based interventions as compared to a control group with usual care suggest that participatory activities bring greater benefits than passive listening to music

		-based interventions involve a large
	variety of activities that can be divided in two types:
	passive (or receptive) or active (or participatory)
	interventions. In receptive interventions, patients
	listen to music or songs performed by musicians,
	caregivers or from audio or video recordings. In
	participatory interventions, patients are encouraged
	to join the music-making by singing, playing simple
	instruments, dancing or simply moving with the
	beats. Those musical activities can be performed
	individually or more frequently in groups with the
	presence of another person (caregiver or therapist) or
	other persons (i.e. patients' group). Since it remains
	difficult to induce passive listening without any
	active processes, passive and active sessions are
	generally	combined	during	music-based
	interventions.

Acknowledgements

Grant support was provided by the Institut Universitaire de France and the French Foundation France Alzheimer to Séverine Samson.


Hadrien Cambazard

Fabien Demazeau
email: demazeau@isoft.fr

Narendra Jussien

Philippe David
email: pdavid@emn.fr

Interactively solving school timetabling problems using extensions of constraint programming

Timetabling problems have been frequently studied due to their wide range of applications. However, they are often solved manually because of the lack of appropriate computer tools. Although many approaches mainly based on local search or constraint programming seem to have been quite successful in recent years, they are often highly dedicated to specific problems and encounter difficulties to take the dynamic and over-constrained nature of such problems. We were confronted with such an over-constrained and dynamic problem in our institution. This paper deals with a timetabling system based on constraint programming with the use of explanations to offer a dynamic behaviour and to allow automatic relaxations of constraints. Our tool has successfully answered the needs of the current planner by providing solutions in a few minutes instead of a week of manual design. We present in this paper the techniques used, the results obtained and a discussion on the effects of the automation of the timetabling process.

Introduction

Timetabling problems have been frequently studied because of their wide range of applications. Scheduling activities occur in any human organisation and become quickly critical for large administrations. However, timetabling problems are often solved manually because of the lack of appropriate computer tools. Although many approaches mainly based on local search or constraint programming seem to have been quite successful in recent years, they are often highly dedicated to specific problems. This is due to the wide variety of problems which differ for example for education timetabling between schools, universities, engineering schools and more specific educational institutions. Among those problems, two main difficulties are encountered: first, timetabling problems are often over-constrained and optimization criterias are hard to define. The optimization objective is often hard to express for the scheduling office itself because of the confusion induced by the manual process of resolution. Second, they are intrinsically dynamic: activities, resources or constraints are sometimes unknown or can often change at the last moment.

We were confronted with such an over-constrained and dynamic problem in our institution. We took the opportunity to experiment with PaLM [START_REF] Jussien | e-constraints: explanation-based constraint programming[END_REF], our explanation based constraint solver, in a real world situation. The system is based on constraint programming with the use of explanations [START_REF] Jussien | Best-first search for property maintenance in reactive constraints systems[END_REF] to offer a dynamic behaviour (the problem is not solved again from scratch when constraints are added or removed) and to allow an automatic relaxation of constraints in case of over-constrained problems. The tool has already been introduced for solving dynamic RCPSP (Ressource Constrained Project Scheduling Problems) in [START_REF] Elkhyari | Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools[END_REF]. Experiments on academic problems such as the RCPSP encouraged us to apply the technique in a real world situation. Our tool has successfully answered the needs of the planner by providing solutions in a few minutes instead of a week of manual computation. This paper is organized as follows: Section 2 introduces the timetabling problem we solved. Formal models are then presented in Section 3: a linear and a constraint formulation are given. Section 4 presents the basics of explanationbased constraint programming and our results are discussed in Section 5.

Problem description

The problem was met in a French engineering school: the École des Mines de Nantes (EMN). EMN offers a 4-year program which consists of a 2-year common core followed by 2 specialized years. There are 9 possible specializations in various areas of study like computer science, production and logistics, environment or management (a complete list is provided in table 1). EMN tries to offer as much choice as possible to its students.

In this paper, we report our work on the third year timetabling problem. All students are supposed to choose a major and a minor (among the nine possible specializations) and a set of open courses. The idea is to let them finalize their choices for their final year where either the major or the minor becomes the only set of courses that they follow. Notice that the choice of a specialization implies a fixed set of required courses. The task is to design a weekly timetable which will be in use for a complete semester. Each course available for the studied semester is to be assigned to a half-day slot during the week. The main problem is to determine which courses will happen simultaneously. The aim is to allow as many students as possible to attend all the required courses of their two choices and as many as possible of their free choices. Each option 3 is defined by two sets of required courses (depending if the topic is a major or a minor). 3 An option is a topic or an area of study chosen by a student to specialize in during his last year.

Static part of the problem

The built timetable must verify a given set of constraints. Both hard and soft constraints can be defined. Hard constraints are as follows:

topic availability: required courses of each topic have to be assigned non overlapping slots ; pre-requisite: some courses are pre-requisite for others and must therefore take place in different slots ; room availability: a maximum number of courses is allowed simultaneously because of room limitations

The provided timetable must meet all these hard constraints. Moreover, soft constraints are highly desirable for a useable timetable:

teachers' availability: teachers can specify their availability on given slots during the week major/minor selection: for each student, the major and minor required courses should be scheduled in non overlapping slots. free course selection: additional courses chosen by a given student must fall in different slots.

Although no precise preference function is defined, the person in charge first tries to satisfy teachers as much as possible (many teachers come from other schools or universities) and to leave students free to attend their major/minor choice. Secondly, the objective is to fulfill the other students' requests in order to provide each of them with a conflict-free schedule. The main problem consist in optimizing both objectives:

1. minimize the number of violated pairs of options (major/minor); 2. minimize the number of violated pairs of courses 4 .

For the first semester, the priority is given to the number of pairs of options available and for the second semester, it consists in minimizing the number of conflicts between courses 5 .

Typical instances for the first semester of the third year in EMN involve 120 students, 30 different courses, 9 main topics and 7 courses per student. The 30 courses have to be assigned in 7 timeslots. Notice that, even if the number of courses and students is quite small compared to typical universities, the student schedule is complete. 72 pairs of options are possible, 3 courses are required for a major and 2 for a minor. Around 30 pairs among the 72 are effectively chosen by students and the distribution of option over the pairs is varied. We cannot predict a priori that any two options will never be together. For example, environment and computer science options are not incompatible (a particular instance can be seen on table 1). Therefore, the problem is often over-constrained only considering the soft constraints concerning major/minor selection.

The student scheduling problem [START_REF] Cheng | Flow formulation for the student scheduling problem[END_REF] (SSP) has the same objective: providing conflict-free schedules. Students need to be assigned to courses in the classical SSP (the timetable is already done) whereas our problem consists in assigning courses to timeslots (the timetable is built according to student's requests). A similar problem is solved in [START_REF] Santiago-Mozos | A two-phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a spanish university[END_REF] where a feasible and personalized weekly timetable is assigned to every student of a Spanish Engineering School. But in this case again, several groups have been already done for every subject, every group has a fixed timetable and is already scheduled to lecturers. Actually, our problem can be seen as a specific demand driven timetabling problem [START_REF] Cheng | Flow formulation for the student scheduling problem[END_REF] where the number of satisfied course requests is to be maximized.

2 0 0 EG 1 0 - 0 2 0 0 3 5 CSAD 0 6 2 - 0 1 1 0 0 QRS 0 0 0 0 - 7 0 0 1 OMPL 2 0 4 0 13 - 2 0 1 ACC 4 3 1 0 2 9 - 1 3 NT 1 0 4 0 0 0 0 - 2 ESE 0 0 4 0 0 0 0 1 - Table 1.
The allocation of minor and major choices in a particular instance (the pair (ACC,QRS) has been chosen by two students for instance). Options are the following: Computer systems engineering (CSE), Computer science as an aid to decision-making (CSAD), Organisation and management of information technologies (OMIT), Automatic control and industrial computation (ACC), Operations management in production and logistics (OMPL), Quality and reliability of systems (QRS), Environmental engineering (EG), Energetic system engineering (ESE), Nuclear and associated technologies (NT).

Dynamic part of the problem

One of the main requirements from the scheduling office was the possibility to quickly change a previous solution in order to take unexpected events into account. Constraints concerning the students are supposed to be quite static, even if the timetabling can be computed whereas some student choices are still missing. The dynamic part of the schedule is more related to logistic problems and unexpected events concerning:

-The link with timetabling of other years (the four years share common resources: rooms, equipment for practical sessions but also teachers)

-The requirement of the teachers (insiders and specially outsiders)

It is for instance usual that the availability of an outside contributor to a course remains unknown until the last moment. Moreover, as teachers are involved in courses for different years whose timetables are not scheduled at the same period, unexpected constraints concerning teachers occur frequently. The dynamic changes considered here focus on addition of constraints (teachers availability or logistic needs). Literature on dynamic timetabling is not very rich. However, our dynamic changes are related to the minimal perturbation problem which consists in incorporating the changes, along with the initial solution, as a new problem whose solution must be as close as possible to the previous one. [START_REF] Müller | Minimal perturbation problem in course timetabling[END_REF] proposes a local search method on partial feasible assignments guided by conflicts statistics to solve the minimal perturbation problem. Our approach is quite different but also pragmatic (see 4.3). However, recent dedicated complete methods can also be found in [START_REF] Barták | A new approach to modeling and solving minimal perturbation problems[END_REF].

Formal Models

The input data for a given timetable are the following:

-Courses = {1, 2, ..., n}; -Options = {1, 2, ..., o}; -Students = {1, 2, ..., m}; -∀i ∈ Options, Requisite1 i ⊂ Courses; -∀i ∈ Options, Requisite2 i ⊂ Courses; -∀s ∈ Students, Choices s ⊂ Courses -R
is the maximum number of free rooms in a each timeslot; -NP is the number of time periods in a week; w i1i2 denotes the conflicts associated to a pair of courses (i 1 , i 2 ) (for example, the number of students that took the pair (i 1 , i 2 )).

Let Courses be the set of courses, Options be the set of options, Requisite1 i be the first set of required courses for option i and Requisite2 i , the second set of required courses for the same option i. For each student s, the inputs are his major and minor O1 s ,O2 s and his free choice of courses F reeCourses s ⊂ Courses. Therefore, the complete set of courses, Choices s , corresponding to a student s is equal to Requisite1 O1s ∪ Requisite2 O2s ∪ F reeCourses s .

A Linear Programming model

A linear model can be expressed using boolean variables x ij which take the value 1 if the course i is placed in the timeslot j and 0 otherwise.

∀i ∈ {1..n}, ∀j ∈ {1..NP } x ij = {0, 1}
Integrity constraints: Each course must be placed exactly once: ∀i ∈ {1..n},

j x ij = 1
Hard constraints:

Option validity: ∀o ∈ Options, ∀j ∈ {1..NP } i∈Requisite1o x ij ≤ 1 Linked courses: ∀i 1 , i 2 pre-requisite, ∀j ∈ {1..NP } x i1j + x i2j ≤ 1 Room availability: ∀j ∈ {1..NP } i∈Courses x ij ≤ R

Soft constraints:

Teachers' availability: teacher of course i is absent at period p,

x ip = 0 Option choice: ∀s ∈ Students, ∀j ∈ {1..NP }, i∈    Requisite1 O1s ∪Requisite2 O2s    x ij ≤ 1 Course choice: 6 ∀s ∈ Students, ∀j ∈ {1..NP }, i∈Choices x ij ≤ 1
This model corresponds to the problem as it was first expressed by the scheduling office. Theses requirements were modified to consider an optimization model which minimizes the number of conflicts once the problem has been proved to be over-constrained. An optimization function could be added using y i1,i2 boolean variables to express the fact that the courses i 1 and i 2 are placed in the same timeslot. An optimization function could be written (with appropriate channelling constraints to link x and y variables):

M in (i1,i2)∈Courses×Courses y i1j2 × w i1,i2

A constraint programming model

Constraint programming (CP) techniques have been widely used to solve scheduling problems. A constraint satisfaction problem (CSP) consists of a set V of variables defined by a corresponding set of possible values (the domain D) and a set C of constraints. A solution for the problem is an assignment of a value to each variable such that all the constraints are simultaneously satisfied. The constraints are handled through a propagation mechanism which allows the reduction of the domains of variables and the pruning of the search space. The propagation mechanism coupled with a backtracking scheme allows the search space to be explored in a complete way. CP seems a good approach to our problem as almost all the constraints described here fall within difference constraints (except room availability) i.e. courses that cannot be scheduled into the same period. We can therefore enforce our model by using global constraints like the alldifferent [START_REF] Régin | A filtering algorithm for constraints of difference in CSPs[END_REF] or global cardinality7 [START_REF] Régin | Generalized arc consistency for global cardinality constraint[END_REF] constraints. Such constraints constitutes an efficient way to handle recurrent patterns or sub-problems, they contain complex algorithms able to efficiently prune large portions of the search space.

The constraint model proposed uses n integer variables x i denoting the timeslots in which courses i are scheduled.

∀i ∈ {1..n}, domain(x i ) = [1..NP ]
Hard constraints can be simply written as follows:

Option One can first notice that the problem is highly symmetrical. In fact, disregarding the teachers' availability constraints, two timeslots are interchangeable. A partial assignment of at least two timeslots is equivalent by exchanging the slots. When the search algorithm has proven that one assignment is inconsistent, it is a waste of effort to try the equivalent permuted assignment. The problem can be seen as a generalized assignment problem (GAP). It is a well-known NP-complete combinatorial optimization problem which consists of assigning a set of tasks (courses) to a set of resources (half-day timeslots). But it can also be considered as a weighted CSP which minimizes the weighted sum of unsatisfied constraints (by considering a weight for each soft constraint). The weight w i1,i2 can be associated to each elementary difference x i1 = x i2 . Coefficients can be added to distinguish minor choice and free courses choices. However, our goal was firstly to provide a solution to hard constraints and, as requested by the planner, to quickly re-compute a solution in case of changes (often concerning teachers) or to simulate different scenarii with unknown data. The dynamic and over-constrained aspect of the problem led us to consider constraint programming with specific enhancements: explanations.

Solving dynamic constraint problems has led to different approaches. Two main classes of methods can be distinguished: proactive and reactive methods. On one hand, proactive methods propose to build robust solutions that remain solutions even if changes occur. On the other hand, reactive methods try to reuse as much as possible previous reasonings and solutions found in the past. Reactive methods avoid restarting from scratch and can be seen as a form of learning. One of the main methods currently used to perform such learning in dynamic constraint solving is a justification technique that keeps trace of inferences made by the solver during the search. Such an extension of classical constraint programming has been recently introduced. It is called explanation-based constraint programming (e-constraints) and it has already proved its interest in many applications [START_REF] Jussien | e-constraints: explanation-based constraint programming[END_REF] including dynamic constraint solving. One can refer to [START_REF] Elkhyari | Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools[END_REF] to find an example of using explanations to solve timetabling problems. We recall in this section what explanation-based constraint programming is and how it can be used.

Definition

An explanation records information to justify a decision of the solver as a reduction of domain or a contradiction. It is made of a set of constraints C (a subset of the original constraints of the problem) and a set of decisions, dc 1 , dc 2 , ..., dc n , taken during search (eg the branching part of a branch and bound algorithm such as x = a or x < y). An explanation of the removal of value a from variable v will be written as follows:

C ∧ dc 1 ∧ dc 2 ∧ • • • ∧ dc n ⇒ v = a
An explanation e 1 is said to be more precise than e 2 if and only if e 1 ⊂ e 2 . The more precise the explanation, the more relevant the learning about the inference is. When a domain is emptied, a contradiction is identified. An explanation for this contradiction is computed by uniting each explanation of each removal of value of the variable concerned. At this point, intelligent backtracking algorithms that question a relevant decision appearing in the conflict are conceivable [START_REF] De | Intelligent backtracking for CLP languages: An application to CLP(R)[END_REF]. By keeping in memory a relevant part of the explanations involved in conflicts, a learning mechanism can be implemented [START_REF] Jussien | Local search with constraint propagation and conflict-based heuristics[END_REF]. Notice that a nogood is associated to any explanation:

dc 1 ∧ dc 2 ∧ • • • ∧ dc n ∧ v = a.

Computing explanations

During propagation, constraints are awaken (like agents or daemons) each time a variable domain is reduced (this is an event) possibly generating new events (value removals). A constraint is fully characterized by its behaviour regarding the basic events such as value removal from the domain of the variables and domain bound updates. Explanations for events are computed when the events are generated.

Explanations for basic constraints. It is easy to provide explanations for basic constraints. The following example shows how to compute them.

Example 1. Let us consider a two-variable toy problem: x and y with the same set of possible values [START_REF] Barták | A new approach to modeling and solving minimal perturbation problems[END_REF][START_REF] Berlandier | Arc-consistency for dynamic constraint problems: A RMS free approach[END_REF][START_REF] Bessière | Arc consistency in dynamic constraint satisfaction problems[END_REF]. Let us state the constraint x > y. The resulting sets of possible values are [START_REF] Berlandier | Arc-consistency for dynamic constraint problems: A RMS free approach[END_REF][START_REF] Bessière | Arc consistency in dynamic constraint satisfaction problems[END_REF] for x and [1, 2] for y. An explanation for this situation is the constraint x > y. Now, let us suppose that we choose to add the constraint x = 2. The only resulting possible value for x is 2. The explanation of the modification is the constraint x = 2. The other consequence is that the remaining value for y is 1. The explanation for this situation is twofold: a direct consequence of the constraint x > y and also an indirect consequence of constraint x = 2.

Precise explanations for global constraints. Computing a precise explanation for global constraints may not be easy because it is necessary to study the algorithms used for propagation. However, there always exists a generic explanation: the current state of the domains of each variable of the constraints. [START_REF] Rochart | Challenging explanations for global constraints[END_REF] describes how to provide precise explanations for the all-different constraint involved in our timetabling problem.

Explanations for handling dynamic problems

Incremental constraint addition to a problem is a well-known issue in classical constraint programming solvers: it is often the usual way constraints are added to the constraint system. However, incremental constraint retraction is not so easy. Several extensions have been proposed to handle dynamic retraction of constraints: some of them [START_REF] Berlandier | Arc-consistency for dynamic constraint problems: A RMS free approach[END_REF][START_REF] Georget | Constraint retraction in clp(fd): Formal framework and performance results[END_REF] analyze the reduction operators to be able to determine the past effects of a constraint and so incrementally retract it; others, following [START_REF] Bessière | Arc consistency in dynamic constraint satisfaction problems[END_REF], store information to achieve that determination.

Explanations (or simplifications) may be used as past effect determination tools [START_REF] Debruyne | Arc-consistency in dynamic csps is no more prohibitive[END_REF][START_REF] Jussien | Best-first search for property maintenance in reactive constraints systems[END_REF]. Dynamic constraint retraction. Dynamic constraint retraction of a constraint c can be achieved through the following steps in an explanation-based system:

1. Disconnecting The first step is to remove the retracted constraint c from the constraint network (no further propagation).

Setting back values

The second step is to undo the past effects of the constraints, both the direct (each time the constraint operators have been applied) and indirect (further consequences of the constraint through operators of other constraints) effects of that constraint. We can easily put back in its domain, each value whose explanation contains the constraint. Past events are recorded in explanations. 3. Re-propagate It is finally necessary to re-propagate in order to reach a consistent state. As our explanations are neither minimal nor unique, many ways exist to deduce the removal of a value and only one of those ways is stored in the current explanation. Therefore a new propagation is necessary.

Re-propagation of constraints. Although determining the past effects of a constraint c is quite easily done by referring to the explanations that do contain reference to c, efficient re-propagation is not provided in classical constraint solvers. Indeed, another event needs to be handled: value restoration (or bound restoration). Instead of calling a general local consistency operator for handling this new event, it is possible to design new operators dedicated to this re-propagation phase. One can refer to [START_REF] Debruyne | Correctness of constraint retraction algorithms[END_REF] for more details.

Solving over-constrained problems

Computing explanations for conflicts and for incrementally removing a constraint from a constraint system leads to over-constrained problems.

Consider the classical enumeration process used to solve CSP as a dynamic sequence of constraint additions (assigning variables) and retractions (backtracks). We can apply a simple strategy [START_REF] Jussien | Best-first search for property maintenance in reactive constraints systems[END_REF]: solve the complete constraint system as usual and, if necessary (i.e. once the problem has been proven over-constrained), use the conflict explanation to identify the next constraint system to consider (using a comparator [START_REF] Wilson | Hierarchical constraint logic programming[END_REF] that takes into account the user's preferences) and perform the constraint modification (retraction(s) and/or addition(s)) incrementally still using explanations. This process is iterated as long as no suitable solution is found. The use of the comparator guarantees the optimality of the solution. Section 5.3 explains in more details how this process leads to an optimization with respect to soft constraints.

Notice that search is made in the space of possible relaxations in opposition to the space of possible assignments in more classical approaches. We can carry this idea further and imagine a local search process in the space of possible relaxations (see Section 5.3).

Solving dynamic timetabling problems

An interactive tool

Our system has been implemented using PaLM [START_REF] Jussien | e-constraints: explanation-based constraint programming[END_REF] and the Java Swing API to design the graphical interface. PaLM is launched as a background process and waits for dynamic events: addition, retraction of constraints or asking of a new solution (during search, the graphical user interface is locked). As the success of the tool was largely depended on a user-friendly interface as well as the ability to solve the problem, we paid a particular attention to the planner's needs and her manual process.

A screenshot of the implemented system can be seen on picture 1. One can see a classic timetable representation with 7 timeslots and 30 courses. Each line corresponds to a timeslot. Boxes on the left column give information on the complete timeslot (number of conflicts and number of involved students). Inside a timeslot, courses are ordered according to the number of involved students (from warm to cold colours, dark to light on the picture). Each course corresponds to a box with the following information: conflicts with every other courses in the same slot, number of involved students, reference to the course and the kind of dynamic constraint added on it. Tool Tip texts help to know the purpose of each number by simply pausing with the cursor over it. Constraints can be added using a mouse left click on the course or the concerned timeslot. A new window allows the constraint and other courses or timeslots involved to be selected. The current state of dynamic constraints added since the beginning is also maintained, allowing easy removals. The automated timetabling system implemented met the requirements of the scheduling office by proposing the following features:

-A dynamic behaviour. 3 kinds of constraints can be added or removed: equality, difference and alldifferent, either between courses or courses with timeslot. By dynamically adding, retracting constraints or changing their weight, the planner is able to perform simulations on the solution, to evaluate its robustness and to manually build (in interaction with the tool) good solutions. -A complete visualization of conflicts in each timeslot and for each course with its neighbours offers the possibility to make judicious dynamic changes to a solution. Previous indicators used by the planner in the manual process, such as the number of inactive students in a timeslot, have been included. Additional statistics on a solution are accessible through a menu to evaluate the results in more details.

Results

The first results were of great interest for the planner:

-The tool is able to provide better solutions quickly. A solution was found manually in a week when 10 solutions are now obtained in about 10 minutes. Moreover, solutions have a better quality than those found by hand even if no optimization is done. Nevertheless, the planner is forced to pre-allocate some courses to allow a quick computation of a solution. It is a simple way to reduce the symmetries of the problem. A good way of doing it consists in setting the required courses of the most chosen option in different slots, as they will not be found together in any conceivable good solution.

We compared the result during the start-up year of the tool and noticed that conflicts have been reduced by around 20 % on both semesters. Moreover, the number of students able to follow their minor choice has been increased by 3 % (it corresponds to a reduction of 10 % of the number of unsatisfied students concerning their minor). The tool was good enough to be accepted by the scheduling office and since then, six semesters have been scheduled with it. -Unexpected events, or unknown data can be taken into account quickly before the start of the courses without changing the original solution too much.

The system doesn't provide any guarantee on the perturbation. It doesn't ensure to get the minimal perturbation. However, the stability of a solution has been analysed for scheduling problems in [START_REF] Elkhyari | Outils d'aide à la décision pour les problèmes d'ordonnancement dynamique[END_REF][START_REF] Elkhyari | Constraint programming for dynamic scheduling problems[END_REF][START_REF] Elkhyari | Stable solutions for dynamic project scheduling problems[END_REF] using the same technique and proved to be quite effective. -A simulation tool: The tool has been quickly used by the planner to simulate different situations. Common sense assumptions were made to make the manual scheduling process easier and are now questioned and simulated with the tool. For example, Human social science courses were often put together in the last timeslot considering that each student is forced to choose one course in this field. However, best solutions do not necessary respect such assumptions. Dynamic abilities intend here to take advantage of the knowhow of the planner as much as possible because she remains a central element in the process of resolution.

Post optimization processing

When solving an instance by hand, the planner focused on the satisfaction of hard constraints and teacher wishes. As hard constraints have been successfully taken into account with the current system, the planner can focus more on student wishes. Once she was experienced with the tool, the time gained has been used to optimize the solution through a simulation process. We noticed how she brought her know-how into play to interact with the tool using its dynamic abilities and to focus on the optimization objective. It was a new aspect of her work since she was more focused on hard constraints in the past. It was therefore for us a second step of resolution. Her manual process can be seen as a manual local search around the first solution given by the system and we came naturally to the point of automating the technique as a local search.

User preferences. Preferences are taken into account during the relaxation of constraints. When the problem has been proved over-constrained, we use the current contradiction explanation and the user preferences to identify the constraint to be relaxed. The use of a simple comparator8 [START_REF] Wilson | Hierarchical constraint logic programming[END_REF] that considers the constraint with the minimal weight ensures that the heaviest weight among the relaxed constraints is minimal in any solution. It guarantees the optimality of the solution according to this comparator. A configuration is defined by two sets of constraints (A, R) where A is the set of active constraints and R the set of relaxed constraints. A configuration C is said to be preferred to C according to a given comparator. In the previous case, two configurations are compared on Fig. 1. A timetable with 7 timeslots and 30 courses. Light boxes on the left give information on the complete timeslot (number of conflicts and number of students concerned). In a timeslot, courses are ordered according to the number of students concerned (from warm to cold colours). Each course corresponds to a box with the following information: conflicts with every neighbours, number of involved student and the kind of added manual constraints. Tool Tip Texts help to know the purpose of each number.

Number of conflicts between Cryptography and its three neighbours. Number of involved students in the course

the heaviest weight of their constraints. The solutions provided in this way are close to the planner's objective and first solutions have shown to be good solutions. However, a more precise objective could be the minimization of the weighted sum of relaxed constraints. Such a comparator needs all the contradiction explanations computed during the search to determine (each time a new contradiction occurs) the new set (of constraints) of minimal weight that covers every contradiction explanation. It leads to two main problems:

-The number of contradiction explanations can be exponential; -Finding the set of minimal weight covering the whole set of explanations is an NP hard problem (set covering problem).

To overcome those problems and try to provide better solutions, we decided to perform local search techniques. This choice was directed by the well-known ability of local search techniques to efficiently improve an initial solution generated using an heuristic method. However, a very different approach for performing the search has been tried using the dynamic abilities of our system.

Local search in the space of configurations. Local search techniques can be seen as methods which iteratively apply simple moves to a solution. Among the wide variety of techniques, tabu search is a local metaheuristic which avoid entrapment in local minima. It has already proved its interest in solving timetabling problems [START_REF] Hertz | Tabu search for large scale timetabling problems[END_REF]. We use here one of the simplest forms of Tabu search without achieving an effective balance of intensification and diversification. But instead of performing the search on complete or partial assignments as usual, we perform the search in the space of configurations using the dynamic abilities of an explanation-based constraint solver.

Let (A, R) be the configuration reached at the end of the first step of the search. As the use of a simple comparator gives good results, we start from this point a local search in a second step of resolution. The tabu search is performed by trying to add a constraint from R to A. The neighbour function (a move) consists therefore in adding a relaxed constraint to the set of active constraints. To avoid cycling, the weight of the constraint is dynamically changed to an infinite value (in our case, 100). Adding a constraint with an infinite weight to A can lead to very difficult sub-problems. Therefore, to reduce the computational effort of each move, we limited the number of extensions (or backtracks, or repairs) allowed to find a new solution. Once the constraint of R leading to the best solution has been added to A, we store it in a tabu list with its original weight. As long as the constraint appears in the list, its weight stays infinite in the problem, forbidding its relaxation. When the constraint leaves the list, it takes back its original weight and becomes relaxable.

Local search methods traditionally encounter difficulties in taking hard constraints into account. Notice that the solution provided here after each move satisfies hard-constraints because arc-consistency is maintained after each retraction Tabu search: input: a configuration (A, R) and the constraint problem pb, (1) begin (2) while time limit not reached do [START_REF] Bessière | Arc consistency in dynamic constraint satisfaction problems[END_REF] for each ct in R do [START_REF] Cheng | Flow formulation for the student scheduling problem[END_REF] add ct to A and changes its weight to 100 [START_REF] De | Intelligent backtracking for CLP languages: An application to CLP(R)[END_REF] (A , R ) ← searchOneSolution(pb) in less than N new decisions [START_REF] Debruyne | Arc-consistency in dynamic csps is no more prohibitive[END_REF] if (conflict(A , R ) < conflict(A, R)) then [START_REF] Debruyne | Correctness of constraint retraction algorithms[END_REF] bestMove ← ct [START_REF] Elkhyari | Outils d'aide à la décision pour les problèmes d'ordonnancement dynamique[END_REF] endif [START_REF] Elkhyari | Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools[END_REF] restore previous configuration (A, R ) by: [START_REF] Elkhyari | Constraint programming for dynamic scheduling problems[END_REF] removing ct from A [START_REF] Elkhyari | Stable solutions for dynamic project scheduling problems[END_REF] adding all c ∈ A\A [START_REF] Georget | Constraint retraction in clp(fd): Formal framework and performance results[END_REF] endfor [START_REF] Hertz | Tabu search for large scale timetabling problems[END_REF] update tabu list: [START_REF] Jussien | e-constraints: explanation-based constraint programming[END_REF] store bestMove and its weight in the list and if the size is exceeded: [START_REF] Jussien | Best-first search for property maintenance in reactive constraints systems[END_REF] remove from the list the first constraint and restore its weight [START_REF] Jussien | Local search with constraint propagation and conflict-based heuristics[END_REF] add bestMove to A with a weight of 100 [START_REF] Jussien | User-friendly explanations for constraint programming[END_REF] (A, R ) ← searchOneSolution(pb) [START_REF] Müller | Minimal perturbation problem in course timetabling[END_REF] endwhile [START_REF] Régin | A filtering algorithm for constraints of difference in CSPs[END_REF] end Fig. 2. Tabu search in configurations space or addition of constraint. When no solutions are found for every constraint of R, we can decide to increase the number of extensions allowed or to stop the search.

The neighborhood of a configuration (A, R) is defined by transferring a constraint from R to A, the computation of a consistent state with this move leads to relax some constraints from A to R. Therefore the configuration reached (A , R ) can be far from the original one. The limitation of the number of extensions to re-compute a solution from the previous one ensures remaining in a close neighborhood of (A, R) and limiting the time needed to compute a move. Moreover, after proving that a move is not reachable in the limit of time allowed, it can be removed from the neighborhood until the current configuration has been changed enough. It is a waste of time of proving at each step that a move doesn't not belong to the current neighborhood.

Results on optimization.

The tabu is able to improve the first solutions by around 10 % on both semesters. It compensates one main problem of the simple comparator used by the solver to relax constraints: All the constraints of one level can be relaxed whereas only one constraint of a higher level needs to be relaxed to get a solution (it is called a flooding phenomenon). Table 2 summarizes the conflict on major/minor choices (option choices for the first semesters in column Opt), the free choices in column Conflicts and the value of the optimization function considered to perform optimization.

Discussion

The tool can successfully solve the problem even if optimization is still an open question. Of course, as mentioned before, it is still necessary to pre-affect some courses by hand to reduce symmetries and to obtain an efficient resolution. We would like to insist on the fact that the tool is unable to replace the planner's work. On the contrary, although a lot of progress has been made in this research field, timetabling problems remain very difficult and specific. Computer tools still need to be open and interactive to take advantage of the know-how of the planner. In our case, the tool has significantly changed her work and opened new perspectives. Common sense assumptions, needed when the problem is solved by hand (to reduce its complexity) can now be questioned and others evaluated. By executing thankless work, the tool gives freedom to the planner who can analyse the problem without any reductionist assumptions. Therefore, her understanding and way of doing it have considerably changed with the tool which gives efficient and relevant information about the problem. Only the planner knows what makes a good solution, has in mind the complete problem with its human dimension and is used to students and teachers' behaviour. That is why an objective function is so hard to define clearly and the know-how of the planner so critical. We have tried to develop an efficient tool based on recent technologies in order to answer precise needs, which is a quite different objective compared to the resolution of very hard and academic problems.

Conclusion and further work

We have presented in this paper a practical application of an explanation based system to solve a school timetabling problem. The system has proved its efficiency when it was accepted by the scheduling office. First, our intention was to show the interest of using explanation techniques to solve dynamic and overconstrained timetabling problem. Second, we presented a different local search technique that tries to take advantages both of constraint programming for satisfying hard constraints and local search for its performance in an optimization context. We plan in the future to keep working on the problem itself as well as the tool:

-Our next step would be to improve the system with user-friendly explanations [START_REF] Jussien | User-friendly explanations for constraint programming[END_REF] to answer to legitimate questions of the planner such as: Why is the problem over-constrained ? Contradictions could be explained to the user by providing the explanation computed for the contradiction in a high level representation.

-Further experiments have to be done concerning the optimization process.

After the local search phase, we intend to restart the search with the new upper bound. Efficient lower bounds and branching scheme will therefore be needed. A more precise study on the problem has to be carried out to evaluate the quality of the first solution found.

Even if work remains to understand the problem, these first results show that explanation constraint programming can be successfully integrated in a real-world situation.

Table 2 .

 2 Results obtained on three years. Instances X1 corresponds to a first semester problem and instances X2 to a second semester.

	Instances		First Solution			Tabu (5min)
		Opt Conflicts Obj. Fct Opt Conflicts Obj. Fct
	A1	6	162	282	5	138	238
	B1	11	151	391 13	140	380
	C1	7	160	320	5	133	273
	Improvement:			10,3 %
	A2	-	54	54	-	49	49
	B2	-	97	97	-	90	90
	C2	-	117	117	-	103	103
	Improvement:			9,7 %

Violated pairs of options and courses will be denoted as conflicts in the latter.

Optimization was not required at the beginning by the planner and became possible once the satisfaction of hard constraints had been successfully taken into account.

This constraint includes the previous one but the distinction will be made for relaxation.

It is denoted by gcc(X, lb, ub) where X is a set of variables, lb and ub, two sets of integers where lbi and ubi gives the minimal and maximal number of times the value i must appear in X.

A comparator is a partial order on configurations.

Acknowledgments

The authors would like to thank Valérie Kirion, in charge of timetabling of the third year students, for her help and collaboration.