Caroline Pigeon
email: caroline.pigeon@ifsttar.fr

Claude Marin-Lamellet

Ageing effects on the attentional capacities and working memory of people who are blind

Keywords: Blindness, Ageing, Attention, Working memory, Cognition, Neuropsychological assessment Blindness, Cognition, Neuropsychological assessment

Ageing effects on the attentional capacities and working memory of people who are blind

Caroline Pigeon, Claude Marin-Lamellet

Introduction

There is a consensus that normal ageing leads to the decline of certain cognitive processes, such as selective attention, sustained attention, divided attention, attentional flexibility and working memory [START_REF] Braver | Working Memory, Executive Control, and Aging[END_REF][START_REF] Kramer | Attention[END_REF], involved in most everyday activities. Hence, age-related cognitive decline can lead to difficulties in everyday situations, for example in crossing the street [START_REF] Dommes | Towards an explanation of age-related difficulties in crossing a two-way street[END_REF] and in dual task situations [START_REF] Li | Walking while memorizing: age-related differences in compensatory behavior[END_REF] and can, therefore, result in a reduction in social participation [START_REF] Wilkie | The prevalence of person-perceived participation restriction in community-dwelling older adults[END_REF].

According to a World Health Organization analysis, more than 80 % of blind people in the world are aged 50 and over [START_REF] Pascolini | Global estimates of visual impairment: 2010[END_REF]. Old people therefore make up an important part of the blind population. Consequently, the effects of ageing on the cognitive functioning, the mobility and the social participation of blind people constitute an important issue, since such people experience restrictions which go beyond the consequences of ageing. However, little is known about cognitive ageing in blind people. Nevertheless, cognitive processes are important for the achievement of everyday activities without vision, such as navigation, which involves an important attentional effort [START_REF] Espinosa | Comparing methods for introducing blind and visually impaired people to unfamiliar urban environments[END_REF][START_REF] Geruschat | Estimating the amount of mental effort required for independent mobility: persons with glaucoma[END_REF][START_REF] Kujala | Faster reaction times in the blind than sighted during bimodal divided attention[END_REF][START_REF] Occelli | Auditory, tactile, and audiotactile information processing following visual deprivation[END_REF]. Furthermore, attentional processes (selective, sustained and divided attention) and working memory have shown to be enhanced in young blind people [START_REF] Kujala | Faster reaction times in the blind than sighted during bimodal divided attention[END_REF][START_REF] Collignon | Further evidence that congenitally blind participants react faster to auditory and tactile spatial targets[END_REF][START_REF] Collignon | Improved selective and divided spatial attention in early blind subjects[END_REF][START_REF] Lerens | Does visual experience influence the spatial distribution of auditory attention?[END_REF][START_REF] Pigeon | Evaluation of the attentional capacities and working memory of early and late blind persons[END_REF]. With ageing, a decrease of mobility is observed in blind people [START_REF] Douglas | Evaluating the use of the ICF as a framework for interviewing people with a visual impairment about their mobility and travel[END_REF][START_REF] Cobb | Mobility restriction and comorbidity in vision-impaired individuals living in the community[END_REF][START_REF] Manduchi | Mobility-related accidents experienced by people with visual impairment[END_REF] but it is unknown whether this decrease could be related to a cognitive decline. The issue of age-related cognitive decline in blind people is all the more important as to maintain the cognitive capacities is more crucial for the everyday functioning in old people with a sensory impairment than in old people without sensory impairment [START_REF] Heyl | Managing daily life with age-related sensory loss: cognitive resources gain in importance[END_REF].

On the contrary, the age-related visual impairment has been the focus of a large number of studies. The negative effects of the age-related visual impairment on the cognitive functioning [START_REF] Bertone | The effect of age-related macular degeneration on non-verbal neuropsychological test performance[END_REF][START_REF] Busse | Adaptation of dementia screening for vision-impaired older persons administration of the Mini-Mental State Examination (MMSE)[END_REF][START_REF] Elyashiv | Correlation between visual acuity and cognitive functions[END_REF][START_REF] Rozzini | Cognitive dysfunction and age-related macular degeneration[END_REF][START_REF] Wittich | Sensitivity and specificity of the Montreal Cognitive Assessment modified for individuals who are visually impaired[END_REF] the mobility [START_REF] Sengupta | Evaluation of real-world mobility in age-related macular degeneration[END_REF][START_REF] Black | Vision and falls[END_REF][START_REF] Gallagher | Ageing and the impact of vision loss on independent living and mobility[END_REF] and the social participation [START_REF] Alma | Participation of the elderly after vision loss[END_REF] are well documented.

The paucity of data about the cognitive ageing of blind people may be due to a lack of available neuropsychological tests adapted for use without the visual modality [START_REF] Bylsma | Neuropsychological assessment in individuals with severe visual impairment[END_REF][START_REF] Hill-Briggs | Neuropsychological assessment of persons with physical disability, visual impairment or blindness, and hearing impairment or deafness[END_REF][START_REF] Bauman | Psychological tests used with blind and visually handicapped persons[END_REF]. In the studies conducted on the cognition of people with age-related visual impairment, tests were adapted either by modifying the visual items (magnified or with a reversed contrast [START_REF] Bertone | The effect of age-related macular degeneration on non-verbal neuropsychological test performance[END_REF]) or by removing the visual items (for example in the MMSE-blind [START_REF] Busse | Adaptation of dementia screening for vision-impaired older persons administration of the Mini-Mental State Examination (MMSE)[END_REF][START_REF] Reischies | Age-related cognitive decline and vision impairment affecting the detection of dementia syndrome in old age[END_REF] or in the MoCA-B [START_REF] Wittich | Sensitivity and specificity of the Montreal Cognitive Assessment modified for individuals who are visually impaired[END_REF]) depending on whether the people tested were partially sighted or not. However, the suppression of the visual items might decrease the sensibility and the accuracy of the tests [START_REF] Bertone | The effect of age-related macular degeneration on non-verbal neuropsychological test performance[END_REF], highlighting the need to use tests which do not involve the visual modality.

Furthermore, most of the tests adapted to be used on people with a visual impairment are screening tools, which can efficiently detect a cognitive deficit (such as mild cognitive impairment or dementia) [START_REF] Bertone | The effect of age-related macular degeneration on non-verbal neuropsychological test performance[END_REF], but they are not sensitive enough to provide the cognitive status of people with no pathological cognitive impairment, such as a normal age-related cognitive decline. The objective of this study was to assess the effects of age on performance in tasks assessing selective, sustained and divided attention, attentional flexibility and working memory in blind and sighted people. The hypotheses were that the performances of blind participants would be better than those of sighted participants and that the performances of younger participants would be better than those of older participants.

Methods

Sample selection and recruitment

A cross-sectional study with 43 blind participants and 42 sighted participants was conducted.

Blind participants were recruited via an advertisement published by associations for people with visual disabilities and by word of mouth. The inclusion criteria were: absence of any neurological or sensory-motor impairment (except for visual impairment in the case of blind participants), habitual, independent mobility outside the home (with a white stick or a guide dog for blind participants), and living independently. The study was approved by the IFSTTAR Research Ethics Committee and participants provided written informed consent prior to participation.

Participants

Eighty-five people participated in the study. Twenty seven of them were blind adults aged under 50 years (50-blind group); 16 participants were blind adults aged over 60 years (60+ blind group); 24 were sighted adults aged under 50 years (50-sighted group) and 18 were sighted adults aged over 60 (60+ sighted group). The etiology of visual impairment in blind participants varied, and blind participants had no useful vision (light perception or less). The verbal portion of the Wechsler Adult Intelligence Scale -Revised (WAIS-R [START_REF] Wechler | Manual for the Wechsler Adult Intelligence Scale-Revised[END_REF]) was used to determine that there was no significant difference in verbal intellectual functioning (verbal IQ) between the groups (F(3, 81) = 0.569, p = 0.637). Table 1 provides a description of the groups.

Insert table 1 about here

Procedure and materials

The experiment was conducted in a quiet room and lasted 90 to 120 min. Sighted participants were blindfolded during testing.

Participants were assessed with the set of computerized auditory tests detailed in our previous publication [START_REF] Pigeon | Evaluation of the attentional capacities and working memory of early and late blind persons[END_REF]. This set of tests consists of a selective attention test, a sustained attention test, a divided attention test, a simple reaction time test, and an auditory version of the Plusminus task [START_REF] Spector | Mental set and mental shift revised[END_REF] to assess attentional switching. Working memory was assessed using an auditory version of the N-back test and the Digit span subtest of the WAIS-R [START_REF] Wechler | Manual for the Wechsler Adult Intelligence Scale-Revised[END_REF]

Results

All statistical analyses were conducted using SPSS (IBM SPSS Statistics 22). Performances (scores and reaction times) were statistically analyzed with two-way analyses of variance (ANOVA) using a design with two between-subject factors: visual status (blind/sighted) and age group (50-/60+). Differences at a level of 0.05 were considered significant. Means and standard deviations for each of the performance measures for the four groups and results of the ANOVAs (mean effects and interaction effects) are shown in table 3.

Insert table 3 about here

Selective attention test.

A two-way ANOVA on the scores obtained in the selective attention test revealed a significant main effect of visual status (F(1, 83) = 4.110, p = 0.046), and a significant main effect of age group (F(1, 83) = 15.295, p = 0.000). However, the analysis did not reveal a significant interaction effect between visual status and age group (F(1, 83) = 1.265, p = 0.264). A two-way ANOVA on the false alarm number did not reveal a significant main effect of visual status (F(1, 83) = 2.464, p = 0.120) but a main age effect emerged (F(1, 83) = 4.544, p = 0.036). The analysis did not show a significant interaction between visual status and age group (F(1, 83) = 0.393, p = 0.532). A two-way ANOVA on the reaction times revealed a significant visual status main effect (F(1, 83) = 11.729, p = 0.001) and an age group main effect (F(1, 83) = 40.420, p = 0.000), but no significant interaction effect between visual status and age group (F(1, 83) = 1.694, p = 0.197).

Sustained attention test.

A two-way ANOVA on the scores demonstrated a significant main effect of visual status (F(1, 83) = 6.912, p = 0.010), but it did not reveal a main effect of age group (F(1, 83) = 3.521, p = 0.064) or an interaction effect between visual status and age group (F(1, 83) = 0.833, p = 0.364). A two-way ANOVA on the reaction times revealed a significant visual status main effect (F(1, 83) = 9.117, p = 0.030) and a significant age group main effect (F(1, 83) = 25.633, p = 0.000). However no significant interaction effect between visual status and age group (F(1, 83) = 0.556, p = 0.458) was found.

Divided attention test.

A two-way ANOVA on the scores obtained in the first task revealed significant main effects of visual status (F(1, 83) = 13.320, p = 0.000) and age group (F(1, 83) = 9.840, p = 0.002), but no interaction effect appeared between visual status and age group (F(1, 83) = 0.920, p = 0.340). A two-way ANOVA on the reaction times obtained in the first task revealed significant main effects of visual status (F(1, 83) = 18.092, p = 0.000) and age group (F(1, 83) = 17.750, p = 0.000) but no interaction effect between visual status and age group (F(1, 83) = 2.559, p = 0.0.114). A two-way ANOVA on the scores obtained in the second task did not reveal a significant main effect of visual status (F(1, 83) = 0.000, p = 0.997), or of age group (F(1, 83) = 0.273, p = 0.603), or any an interaction effect between visual status and age group (F(1, 83) = 1.135, p = 0.290).

N-back test.

A two-way ANOVA on the scores obtained in the 0-back condition did not reveal a significant main effect (F(1, 83) = 0.520, p = 0.473) of either visual status or age group (F(1, 83) = 0.077, p = 0.782). Nor was there any interaction effect between visual status and age group (F(1, 83) = 0.373, p = 0.543). However, a two-way ANOVA on the reaction times obtained in this 0-back condition revealed a significant visual status main effect (F(1, 83) = 4.147, p = 0.045) and a significant main effect of age group (F(1, 83) = 11.213, p = 0.001). No interaction effect between visual status and age group was found (F(1, 83) = 0.372, p = 0.544).

A two-way ANOVA on the scores obtained in the 1-back condition did not reveal a significant main effect of visual status (F(1, 83) = 0.164, p = 0.687). A significant main effect of the age group did, however, emerge (F(1, 83) = 3.949, p = 0.050). The analysis did not reveal a significant interaction between visual status and age group (F(1, 83) = 2.234, p = 0.139). A two-way ANOVA on the 1-back reaction times revealed significant main effects of visual status (F(1, 83) = 9.939, p = 0.002) and age group (F(1, 83) = 23.342, p = 0.000) but no interaction effect between visual status and age group (F(1, 83) = 0.002, p = 0.968).

A two-way ANOVA on the 2-back scores did not reveal a significant visual status main effect (F(1, 83) = 0.108, p = 0.744). However it did reveal a significant main effect of age group (F(1, 83) = 17.302, p = 0.000). The analysis did not reveal a significant interaction effect between visual status and age group (F(1, 83) = 2.387, p = 0.126). A two-way ANOVA on the reaction times obtained in the 2-back condition revealed significant main effects of visual status (F(1, 83) = 8.298, p = 0.005) and of age group (F(1, 83) = 22.197, p = 0.000) but no interaction effect between visual status and age group (F(1, 83) = 0.140, p = 0.709).

A two-way ANOVA on the scores obtained in the 3-back condition did not reveal a significant main effect of visual status (F(1, 83) = 2.760, p = 0.101). However, a significant main effect of age group was observed (F(1, 83) = 13.584, p = 0.000). No interaction effect appeared between visual status and age group (F(1, 83) = 0.268, p = 0.606). A two-way ANOVA on the reaction times obtained in the 3-back condition did not reveal a significant visual status main effect (F(1, 83) = 3.084, p = 0.083), an age group main effect (F(1, 83) = 2.700, p = 0.104), or an interaction effect between visual status and age group (F(1, 83) = 0.843, p = 0.361).

Digit span.

A two-way ANOVA on the forward span did not reveal a significant main effect of visual status (F(1, 83) = 0.067, p = 0.796), but a significant main effect of age group was found (F(1, 83) = 3.976, p = 0.050). No interaction effect between visual status and age group was observed (F(1, 83) = 1.532, p = 0.219). A two-way ANOVA on the backward span revealed significant main effects of visual status (F(1, 83) = 7.425, p = 0.008) and of age group (F(1, 83) = 8.254, p = 0.005), but no interaction effect between visual status and age group (F(1, 83) = 0.304, p = 0.583).

Standard age scores were calculated by adding the scores obtained in the two conditions and converting this obtained score based on the age of the participants. A two-way ANOVA on the standard age scores did not reveal a significant main effect of visual status (F(1, 83) = 1.818, p = 0.181), or of age group (F(1, 83) = 0.329, p = 0.568), or an interaction effect between visual status and age group (F(1, 83) = 2.939, p = 0.090).

Plus-minus task.

A two-way ANOVA on the cost of switching obtained in the plus-minus task did not reveal a significant main effect of visual status (F(1, 83) = 0.171, p = 0.680), of age group (F(1, 83) = 0.294, p = 0.589) or an interaction effect between visual status and age group (F(1, 83) = 0.038, p = 0.845)..

Simple reaction time test.

A two-way ANOVA on the reaction times obtained revealed a significant visual status main effect (F(1, 83) = 4.266, p = 0.042) and a significant age group main effect (F(1, 83) = 47.737, p = 0.000), but no interaction effect between visual status and age group was found (F(1, 83) = 3.175, p = 0.079).

Discussion

The aim of this study was to examine the effects of age on performance in tasks assessing selective, sustained, divided attention, attentional flexibility and working memory in blind and sighted people.

Visual status effects were found: blind participants achieved better performances than sighted participants in many of the measured variables. Blind participants obtained higher scores and had faster reaction times than sighted participants in the selective attention test, in the sustained attention test and in the first task of the divided attention test. These results are consistent with those obtained in previous studies in which blind people achieved better performances than sighted ones in tasks assessing selective, sustained and/or divided attention [START_REF] Kujala | Faster reaction times in the blind than sighted during bimodal divided attention[END_REF][START_REF] Collignon | Further evidence that congenitally blind participants react faster to auditory and tactile spatial targets[END_REF][START_REF] Collignon | Improved selective and divided spatial attention in early blind subjects[END_REF][START_REF] Lerens | Does visual experience influence the spatial distribution of auditory attention?[END_REF][START_REF] Pigeon | Evaluation of the attentional capacities and working memory of early and late blind persons[END_REF]. When working memory was measured, blind participants were faster in the 0-, 1-and 2-back conditions of the n-back task, and their backward spans were greater.

These results confirm those obtained in our previous study [START_REF] Pigeon | Evaluation of the attentional capacities and working memory of early and late blind persons[END_REF] in which blind people achieved better performances than sighted ones in the same tests assessing working memory.

Contrary to our previous study [START_REF] Pigeon | Evaluation of the attentional capacities and working memory of early and late blind persons[END_REF], in which blind participants and sighted participants aged less than 50 years did not exhibit significantly different reaction times in the simple reaction time test, the blind participants in the present study displayed faster reaction times than the sighted ones. However, in the present study, the reaction times obtained by the 50-blind group (270.9 SD 69.1) and the 50-sighted group (275.7 SD 70.7) were comparable with a difference of just 5 ms., although reaction times obtained by the 60+ blind group (358.1 SD 50.9) and those of the 60+ sighted group (423.5 SD 114.0) differed by more than 60 ms. Therefore even if there was no significant interaction, the visual status main effect seems to relate more to the two 60+ groups' reaction times than to the reaction times of the two 50groups. Globally, the results confirmed our hypothesis that the performance of blind participants would be better than that of sighted participants.

Concerning the age effect, the 50-participants obtained better performances than the 60+ participants in most of the measured variables. The 50-participants obtained higher scores and had faster reaction times than the 60+ participants in the selective attention test and in the first task of the divided attention test, and they were faster and tended to have a higher scores in the sustained attention test. In tasks assessing working memory, the 50-participants responded faster and had higher scores than 60+ participants in the 1-and 2-back conditions of the n-back task, responded faster in the 0-back condition and had higher scores in the 3back condition. They also had greater forward and backward spans. In the simple reaction time test, the 50-participants exhibited faster reaction times than the 60+ participants. These results are consistent with the literature on cognitive ageing stating that normal ageing leads to the decline of cognitive processes [START_REF] Braver | Working Memory, Executive Control, and Aging[END_REF][START_REF] Kramer | Attention[END_REF], and confirmed our hypothesis that younger participants would have better performances than older participants. Although the old participants in this study were relatively young (the mean ages of the two 60+ groups were under 66 years), age effects were demonstrated, suggesting that the tests used are sensitive enough to detect a moderate cognitive decline.

The age-related decline of attention seems not more or less marked in blind people, as it is suggested by the absence of interaction between the visual status and age effects. Other studies have shown that people with age-related visual impairment obtained lower performances in cognitive tests than sighted people of the same age, suggesting that cognitive decline is more marked in old people with an age-related visual deficit [START_REF] Wahl | Connections between vision, hearing, and cognitive function in old age[END_REF][START_REF] Lindenberger | Sensory functioning and intelligence in old age: a strong connection[END_REF][START_REF] Lindenberger | The strong connection between sensory and cognitive performance in old age: not due to sensory acuity reductions operating during cognitive assessment[END_REF]. In the present study, the old blind participants obtained higher performances than sighed ones. This suggests that ageing with blindness does not, therefore, have the same effects on cognition as dealing with a visual impairment in the course of ageing. A possible explication could be that the cognitive decline and the visual decline of people with an age-related visual deficit may share common biological causes [START_REF] Salthouse | Interrelations of age, visual acuity, and cognitive functioning[END_REF]. In the contrary, the visual impairment of blind people (who are blind before be old) is not caused by an ageing processes but by ocular illness or injuries. Hence, people with an age-related visual impairment would be a part of the population particularly affected by the age-related cognitive decline.

Otherwise the results obtained from visually impaired people in tests involving visual items may due to visual rather than cognitive aspects [START_REF] Wahl | Connections between vision, hearing, and cognitive function in old age[END_REF]. Indeed, studies conducted on people with a visual impairment [START_REF] Killen | The assessment of cognition in visually impaired older adults[END_REF] and on people with a simulated visual impairment [START_REF] Wood | Simulated visual impairment leads to cognitive slowing in older adults[END_REF][START_REF] Bertone | The impact of blurred vision on cognitive assessment[END_REF] have stressed the importance of using cognitive tests which are not vision dependent to assess people with visual impairments. This issue would be handled with a cognitive assessment in people with an age-related visual impairment with the tests used in the present study. The results of the present study show that blindness leads to an attentional improvement, even in people aged more than 60. The blind participants included in this study were accustomed to being independently mobile outside of the home. As only a third of blind people enjoy autonomous mobility [START_REF] Sander | La population en situation de handicap visuel en France. Importance, caractéristiques, incapacités fonctionnelles et difficultés sociales. Exploitation d'enquêtes HID 1998/99[END_REF], these participants could be considerate as a highlevel sample of the blind population, with over capacities. We can hypothesize that their higher performances compared to the sighted participants may be due to this independence, which can be consider as a cognitive training. Indeed, navigating without vision is an activity cognitive costly. As standard cognitive trainings, navigating without vision is an activity which i) involves cognitive stimulations, ii) includes positive reinforcements (let to have a social participation, the satisfaction to be autonomous), iii) can be performed with gradual difficulty steps, completed when an expertise level is reached (from in a short, simple and known itinerary, accompanied, to in a complex, long and unknown itinerary, independently).

Adaptation to a visual impairment is a dynamic mechanism. People who have been blind for a longer time are, for example, more likely to have adapted from a psychological point of view (i.e. have a greater acceptance of vision loss, be less depressed, enjoy better social support) than people whose visual impairment is more recent [START_REF] Senra | Psychologic adjustment to irreversible vision loss in adults[END_REF][START_REF] Bergeron | Psychological adaptation to visual impairment: The traditional grief process revised[END_REF], even if adaptation to visual impairment can involve several cycles of grieving and acceptance [START_REF] Kaminsky | Supports and barriers as experienced by individuals with vision loss from diabetes[END_REF] and depends on the coping strategies used by people [START_REF] Garnefski | Psychological intervention targets for people with visual impairments: The importance of cognitive coping and goal adjustment[END_REF]. Further investigations using longitudinal studies are required to determine how cognitive adaptation (i.e. the improvement of selective, sustained, divided attention and working memory) occurs over time in people who are blind and how ageing-related changes take place. In addition, longitudinal studies would avoid the generational bias potentially present in the present study [START_REF] Schaie | Handbook of the Psychology of Aging[END_REF].

With ageing, blind people suffer of a decrease of mobility [START_REF] Douglas | Evaluating the use of the ICF as a framework for interviewing people with a visual impairment about their mobility and travel[END_REF][START_REF] Cobb | Mobility restriction and comorbidity in vision-impaired individuals living in the community[END_REF][START_REF] Manduchi | Mobility-related accidents experienced by people with visual impairment[END_REF], which can result in less cognitive stimulations. As cognitive abilities have been found to be related to everyday functioning in ageing [START_REF] Baltes | Everyday competence in old and very old age: Theoretical considerations and empirical findings[END_REF], particularly in people with age-related visual impairment [START_REF] Heyl | Managing daily life with age-related sensory loss: cognitive resources gain in importance[END_REF], a cognitive training intervention could be a promising possibility for the rehabilitation of aged blind people and let them to be autonomous as long as possible. In the field of the mobility, cognitive interventions have been conducted on sighted old people with a view to improving their gait [START_REF] Smith-Ray | Impact of cognitive training on balance and gait in older adults[END_REF][START_REF] Schoene | The effect of interactive cognitivemotor training in reducing fall risk in older people: a systematic[END_REF]. However, only physical interventions seem to have been attempted to improve the gait of people with visual impairments [START_REF] Ray | Review of intrinsic factors related to fall risk in individuals with visual impairments[END_REF].

Other types of intervention can also be considered when dealing with the effects of ageing in blind people. For example, since optimized social participation is related to the preservation of cognitive functioning [START_REF] Kuiper | Social relationships and risk of dementia: A systematic review and meta-analysis of longitudinal cohort studies[END_REF] and functional autonomy [START_REF] Levasseur | Associations between perceived proximity to neighborhood resources, disability, and social participation among community-dwelling older adults: Results from the Voisinuage study[END_REF], improvement of the social participation of people who are blind could be another encouraging approach. Being engaged in social activities is a means of cognitive stimulation and can attenuate age-related cognitive decline [START_REF] James | Late-life social activity and cognitive decline in old age[END_REF] and therefore preserve functional autonomy.

Conclusion

Our study appears to be the first piece of research which assesses cognitive functioning in old blind people. The results suggest that people who are blind follow a similar age-related cognitive trajectory to that of sighted people. The study underlines the need to study cognition and its links with everyday functioning throughout the entire lifespan. It also provides possibilities, such as cognitive intervention, for the rehabilitation for people who are blind.

Implications for rehabilitation

• Blind people show improved attentional capacities compared to sighted people, even in old blind people.

• Old blind people have lower performances than younger blind people in tests assessing selective, sustained and divided attention and working memory.

• Cognitive approaches to rehabilitation may help people who are blind to deal with age-related cognitive decline and its effects on everyday functioning. We would like to thank the editor and the reviewers for their constructive feedback. We carefully revised the manuscript based on the comments, and feel that this considerably improved the manuscript.

In the following, we provide specific response to each comment.

Reviewer #1

Authors' reply 1. The discussion section requires some further work. Many papers cited in the discussion do not engaged with authors' idea, but rather used to show the similarity with previous papers. Moreover, authors have not provided any cognitive adaptation model/hypothesis for discussing the results. They only mentioned that further investigations are required.

The discussion section has been better developed and a cognitive adaptation hypothesis for discussing the results has been more exposed.

2. Table 3 is only showing mean (SD) without the result of statistical analysis, so that it was very hard to understand the results. Moreover, the part of Digit span is not written properly.

The results of statistical analysis have been added in the Table 3 and the part of Digit span in the table 3

has been corrected

3. There is a part incorrectly cited in the discussion. In the results, reaction times obtained in the 3-back condition did not show a significant age group main effect (page8, line 25). However, in the discussion it was mentioned that the 50participants were faster in the 0-and 3-back conditions (page 10, line 28). This is effectively an error in the discussion that we corrected: "In tasks assessing working memory, the 50participants responded faster and had higher scores than 60+ participants in the 1-and 2-back conditions of the n-back task, responded faster in the 0-back condition and had higher scores in the 3-back condition" 4. There are a few careless mistakes in the references.

Errors in the references section have been corrected.

Reviewer #2 1. It is pretty exploratory, which makes it atheoretical. I guess that's not a problem on its own, so long as the authors are up front about it, but I have to say that the introduction did not really tell me where this paper was going at all. When I started reading the methods I needed to go back up to the abstract to have any idea what the point was.question that the authors put forward, which is how blind people develop the ability to walk independently out of home.

We restructured the introduction part and we hope that the introduction is now clearer.

2. What are the dependent variables? It is kind of hard to judge the quality of research without this info. For instance, n-back score of "5.7". Okay? Is that simply hits? Are all of these hits?

The dependent variables have been add in the table 2 which describe the tests used. The scores correspond to the number of correct responses, this has been specified in the Procedure and materials section. In the table 3, for each score, the maximal number of hits have been had. Editor I would also like you to add a fourth bullet point in your section on "implications for rehabilitation" which perhaps elaborates on the third point which focused on the potential benefits of cognitive rehabilitation.

A fourth bullet has been add: "A high level of cognitive stimulation, provided by a cognitive training or a developed social participation, might reduce the age-related effects in people who are blind."

We would like to thank again the reviewers for their careful reading and relevant suggestions and we hope that this revised version will be clearer.

Page 8 of 23 URL

 23 : http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.

Page 11 of 23 URL

 23 : http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.

Page 22 of 23 URL

 23 : http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.

  :/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.ukDisability and Rehabilitation

Table 1 .

 1 General characteristics of the four groups

	Means (SD; range)

Table 2 .

 2 Description of the tests used and the dependent variables

	Page 17 of 23	Disability and Rehabilitation
	Cognitive function assessed	Test	Instructions	Responses of participants (dependent variables)
	Selective attention Sustained attention Sustained attention test Selective attention test	Detect consonants among numbers	Press the space bar (number of correct responses and reaction times)
			First task: detect	First task: press the space bar
			consonants; second task:	(number of correct responses
	Divided attention	Divided attention test	detect the number 6	and reaction times); secondary
			among consonants and	task: verbally (number of correct
			numbers	responses)
			Condition 1: add 3 to	Verbally, written by the
			each number presented	experimenter (cost of switching:
	Attentional switching	Auditory plus-minus task [33] (3 conditions)	Condition 2: subtract 3 to each number presented Condition 3: alternate	difference between the time required to complete the condition 3 and the average
			between addition and	of the times required to complete
			subtraction	the first two conditions)
		N-back test (4 conditions)	Detect when a consonant is the same as the n last consonant	Press the space bar (number of correct responses and reaction times)
			Condition 1: repeat a digit
	Working memory		sequence in the same	Verbally, written by the
		Digit span subtest of	order of presentation	experimenter (forward and
		the WAIS-R [32]	Condition 2: repeat a digit	backward spans and standard
			sequence in the reverse	age scores)
			order of presentation
	Simple reaction	Simple reaction time	Detect the occurrence of	Press the space bar (reaction
	time	test	a sound	times)

URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.uk URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.uk

Table 3 .

 3 Means (standard deviations) for each performance measures of group and results of the ANOVAs (mean effects and their interactions)

	Page 19 of 23			Disability and Rehabilitation
	Test			Mean (SD)		Visual status effect Age group effect	Interaction
		variable	50-blind	60+ blind	50-sighted	60+ sighted
			(n = 27)	(n = 16)	(n = 24)	(n = 18)	F value p value F value p value F value p value
	Selective attention test	Score (/40) False Alarm number	38.8 (1.1) 0.9 (0.9)	35.3 (4.2) 1.6 (1.7)	36.6 (3.2) 0.7 (0.9)	34.6 (4.1) 1.1 (0.6)	4.110 2.464	.046 .120	15.295 4.544	.000 .036	1.265 0.393	.264 .532
		Reaction time (ms)	670.5 (54.9) 768.9 SD 57.4)	731.2 (65.3)	796.2 (51.9)	11.729	.001	40.420	.000	1.694	.197
	Sustained attention test	Score (/120) Reaction time (ms)	112.5 (22.9) 681.4 (69.9)	111.1 (11.4) 765.6 (63.5)	109.5 (10.6) 755.3 (72.4)	107.5 (10.8) 798.5 (57.1)	6.912 9.117	.010 .030	3.521 25.633	.064 .000	0.833 0.556	.364 .458
	Divided attention test	First task score (/40) First task reaction time (ms)	34.3 (7.7) 743.2 (67.7)	31.1 (5.6) 845.0 (62.3)	30.6 (5.7) 846.5 (110.4)	28.1 (5.2) 891.5 (56.0)	13.320 18.092	.000 .000	9.840 17.750	.002 .000	0.920 2.559	.340 ;114
		Second task score (/8)	6.7 (1.1)	7.2 (2.0)	7.4 (1.0)	6.9 (1.0)	0.000	.997	0.273	.603	1.135	.290
	Auditory N-back test	0-back score (/10) 1-back score (/10)	9.9 (0.2) 9.8 (0.5)	10.0 (0.0) 9.8 (0.4)	9.9 (0.2) 9.9 (0.2)	9.9 (0.2) 9.5 (1.0)	0.520 0.164	.473 .687	0.077 3.949	.782 .050	0.373 2.234	.543 .139
		2-back score (/10)	9.1 (1.6)	6.4 (3.0)	8.2 (1.8)	7.0 (2.1)	0.108	.744	17.302	.000	2.387	.126
		3-back score (/10)	5.7 (1.7)	4.6 (1.4)	5.3 (1.4)	3.8 (1.9)	2.760	.101	13.584	.000	0.268	.606
		0-back reaction time (ms)	530.0 (72.7)	621.4 (71.2)	591.0 (137.7)	654.4 (116.2)	4.147	.045	11.213	.001	0.372	.544
		1-back reaction time (ms)	584.0 (81.1)	673.9 (76.7)	642.3 (101.0)	733.8 (73.7)	9.939	.002	23.342	.000	0.002	.968
		2-back reaction time (ms)	713.9 (124.2) 912.9 (281.3)	838.0 (132.7) 1012.8 (193.2)	8.298	.005	22.197	.000	0.140	.709
		3-back reaction time (ms)	893.8 (220.8) 1014.5 (267.5) 1010.1 (135.6) 1051.9 (233.2)	3.084	.083	2.700	.104	0.843	.361
	Digit span	Forward span	7.3 (1.8)	6.3 (1.4)	6.9 (1.2)	6.6 (1.1)	0.067	.796	3.976	.050	1.532	.219
		Backward span	6.0 (1.3)	5.0 (1.6)	5.0 (1.2)	4.4 (0.9)	7.425	.008	8.254	.005	0.304	.583
		Standard age score	14.9 (3.4)	13.4 (3.6)	12.9 (2.1)	13.6 (2.1)	1.818	.181	0.329	.568	2.939	.090
	Auditory plus-minus task Cost of switching	7.43 (12.1)	8.4 (10.6)	8.1 (11.7)	10.3 (19.5)	0.171	.680	0.294	.589	0.038	.845

URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.uk URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.uk

effects on the attentional capacities and working memory of people who are blind

  • A high level of cognitive stimulation, provided by a cognitive training or a developed social participation, might reduce the age-related effects in people who are blind.

	Page 21 of 23	Disability and Rehabilitation
	Manuscript ID: TIDS-02-2016-096
	Title: Ageing Disability and Rehabilitation
	Dear Professor Dave Müller,
	F o
	r
	P
		e e r
		R e v i e w

URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.uk

URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.uk

URL: http:/mc.manuscriptcentral.com/dandr Email: davemuller@suffolk.ac.ukDisability and Rehabilitation

Acknowledgments

We gratefully thank all the volunteers and the Fédération des Aveugles et Handicapés Visuels de France, Association Valentin Haüy de Lyon, Association Valentin Haüy de Marseille, Association Valentin Haüy de Grenoble and Point de Vue sur la Ville for their collaboration.

Declaration of interest

The authors report no declarations of interest. This study has been founded by IFSTTAR.


Tristan Cazenave

Fabien Teytaud

Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows

Keywords: Nested Monte-Carlo, Nested Rollout Policy Adaptation, Traveling Salesman Problem with Time Windows

In this paper, we are interested in the minimization of the travel cost of the traveling salesman problem with time windows. In order to do this minimization we use a Nested Rollout Policy Adaptation (NRPA) algorithm. NRPA has multiple levels and maintains the best tour at each level. It consists in learning a rollout policy at each level. We also show how to improve the original algorithm with a modified rollout policy that helps NRPA to avoid time windows violations.

Introduction

In this paper we are interested in the minimization of the travel cost of the Traveling Salesman Problem with Time Windows. Recently, the use of a Nested Monte-Carlo algorithm (combined with expert knowledge and an evolutionary algorithm) gave good results on a set of state of the art problems [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF]. However, as it has been pointed out by the authors, the effectiveness of the Nested Monte-Carlo algorithm decreases as the number of cities increases. When the number of cities is too large (greater than 30 for this set of problems), the algorithm is not able to find the state of the art solutions.

A natural extension to the work presented in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF], which consists in the application of the Nested Monte-Carlo algorithm on a set of Traveling Salesman Problems with Time Windows, is to study the efficiency of the Nested Rollout Policy Adaptation algorithm on the same set of problems.

In this work we study the use of a Nested Rollout Policy Adaptation algorithm on the Traveling Salesman Problem with Time Windows. The Nested Rollout Policy Adaptation algorithm has recently been introduced in [START_REF] Rosin | Nested rollout policy adaptation for monte carlo tree search[END_REF], and provides good results, including records in Morpion Solitaire and crossword puzzles. We improve this algorithm by replacing the standard random policy used in the rollouts with a domain-specific one, defined as a mixture of heuristics. These domain-specific heuristics are presented in Section 4.2.

The paper is organized as follows. Section 2 describes the Traveling Salesman Problem with Time Windows, Section 3 presents the Nested Monte-Carlo algorithm (Section 3.1) and its application to the Traveling Salesman Problem with Time Windows (Section 3.2). Section 4 presents the Nested Rollout Policy Adaptation algorithm (Section 4.1) and its application to the Traveling Salesman Problem with Time Windows (Section 4.2). Section 5 presents a set of experiments concerning the application of the Nested Rollout Policy Adaptation algorithm on the Traveling Salesman Problem with Time Windows.

The Traveling Salesman Problem with Time Windows

The Traveling Salesman Problem (TSP) is a famous logistic problem. Given a list of cities and their pairwise distances, the goal of the problem is to find the shortest possible path that visits each city only once. The path has to start and finish at a given depot. The TSP problem is NP-hard [START_REF] Johnson | Computational complexity and the traveling salesman problem[END_REF]. In this work, we are interested in a similar problem but more difficult, the Traveling Salesman Problem with Time Windows (TSPTW). In this version, a difficulty is added. Each city has to be visited within a given period of time.

A survey of efficient methods for solving the TSPTW can be found in [START_REF] López-Ibáñez | Beam-ACO for the travelling salesman problem with time windows[END_REF]. Existing methods for solving the TSPTW are numerous. First, branch and bound methods were used [START_REF] Baker | An exact algorithm for the time-constrained traveling salesman problem[END_REF][START_REF] Christofides | State-space relaxation procedures for the computation of bounds to routing problems[END_REF]. Later, dynamic programing based methods [START_REF] Dumas | An optimal algorithm for the traveling salesman problem with time windows[END_REF] and heuristics based algorithms [START_REF] Solomon | Algorithms for the vehicle routing and scheduling problems with time window constraints[END_REF][START_REF] Gendreau | A generalized insertion heuristic for the traveling salesman problem with time windows[END_REF] have been proposed. More recently, methods based on constraint programming have been published [START_REF] Focacci | A hybrid exact algorithm for the tsptw[END_REF][START_REF] Pesant | An exact constraint logic programming algorithm for the traveling salesman problem with time windows[END_REF].

An algorithm based on the Nested Monte-Carlo Search algorithm has been proposed [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF] and is summarized in Section 3.2.

The TSPTW can be defined as follow. Let G be an undirected complete graph. G = (N, A), where N = 0, 1, . . . , n corresponds to a set of nodes and A = N × N corresponds to the set of edges between the nodes. The node 0 corresponds to the depot. Each city is represented by the n other nodes. A cost function c : A → R is given and represents the distance between two cities. A solution to this problem is a sequence of nodes P = (p 0 , p 1 , . . . , p n ) where p 0 = 0 and (p 1 , . . . , p n ) is a permutation of [1, N ]. Set p n+1 = 0 (the path must finish at the depot), then the goal is to minimize the function defined in Equation 1.

cost(P ) = n k=0 c(a p k , a p k+1 ) (1)
As said previously, the TSPTW version is more difficult because each city i has to be visited in a time interval [e i , l i ]. This means that a city i has to be visited before l i . It is possible to visit a cite before e i , but in that case, the new departure time becomes e i . Consequently, this case may be dangerous as it generates a penalty. Formally, if r p k is the real arrival time at node p k , then the departure time d p k from this node is d p k = max(r p k , e p k ).

In the TSPTW, the function to minimize is the same as for the TSP (Equation 1), but a set of constraint is added and must be satisfied. Let us define Ω(P ) as the number of violated windows constraints by tour (P). Two constraints are defined. The first constraint is to check that the arrival time is lower than the fixed time. Formally,

∀p k , r p k < l p k .
The second constraint is the minimization of the time lost by waiting at a city. Formally,

r p k+1 = max(r p k , e p k ) + c(a p k ,p k+1 ).
With the algorithm used in this work, paths with violated constraints can be generated. As presented in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF] , a new score T cost(p) of a path p can be defined as follow:

T cost(p) = cost(p) + 10 6 * Ω(p),
with, as defined previously, cost(p) the cost of the path p and Ω(p) the number of violated constraints. 10 6 is a constant chosen high enough so that the algorithm first optimizes the constraints. The TSPTW is much harder than the TSP, consequently new algorithms have to be used for solving this problem.

In the next sections, we define two algorithms for solving the TSPTW. The first one, in Section 3, is the Nested Monte-Carlo algorithm from [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF], and the second one, in Section 4, is the Nested Rollout Policy Adaptation algorithm, which is used in this work to solve the TSPTW. We eventually present results in Section 5.

The Nested Monte-Carlo Search algorithm

First, in Section 3.1 we present the Nested Monte-Carlo Search, and then in Section 3.2 the application done in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF] to the Traveling Salesman Problem with Time Windows.

Presentation of the algorithm

The basic idea of Nested Monte-Carlo Search (NMC) is to find a solution path of cities with the particularity that each city choice is based on the results of a lower level of the algorithm [START_REF] Cazenave | Nested Monte-Carlo search[END_REF]. At level 1, the lower level search is simply a playout (i.e. each city is chosen randomly).

Figure 1 illustrates a level 1 Nested Monte-Carlo search. Three selections of cities at level 1 are shown. The leftmost tree shows that, at the root, all possible cities are tried and that for each possible decision a playout follows it. Among the three possible cities at the root, the rightmost city has the best result of 30, therefore this is the first decision played at level 1. This brings us to the middle tree. After this first city choice, playouts are performed again for each possible city following the first choice. One of the cities has result 20 which is the best playout result among his siblings. So the algorithm continues with this decision as shown in the rightmost tree. This algorithm is presented in Algorithm 1. At each choice of a playout of level 1 it chooses the city that gives the best score when followed by a single random playout. Similarly for a playout of level n it chooses the city that gives the best score when followed by a playout of level n -1.

Application to the TSPTW

In [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF], a NMC algorithm is used in order to solve a set of TSPTW. With the intention of having a competitive algorithm they add expert-knowledge to the NMC algorithm. Three heuristics are added and used to bias the Monte-Carlo simulations thanks to a Boltzmann softmax policy. The principle is to define a new policy for the rollout phase. This policy is defined by the probability π θ (p, a) of choosing the action a in a position p:

π θ (p, a) = e φ(p,a) T θ b e φ(p,b) T θ ,
where φ(p, a) is a vector of heuristics and θ is a vector of heuristic weights.

The three heuristics used are the same as the ones defined in [START_REF] Solomon | Algorithms for the vehicle routing and scheduling problems with time window constraints[END_REF], and are summarised as follows:

-The distance to the last city.

-The amount of wasted time because a city is visited too-early.

-The amount of time left until the end of the time window of a city.

For the tuning of the weights of each heuristic, they used an evolution strategy [START_REF] Rechenberg | Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Fromman-Holzboog[END_REF], more precisely a Self-Adaptive Evolution Strategy [START_REF] Rechenberg | Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Fromman-Holzboog[END_REF][START_REF] Schwefel | Adaptive Mechanismen in der biologischen Evolution und ihr Einfluß auf die Evolutionsgeschwindigkeit[END_REF], known for its robutsness.

The Nested Rollout Policy Adaptation algorithm

First, in Section 4.1, we present the Nested Rollout Policy Adaptation algorithm. In Section 4.2 we present some modifications done on this algorithm in order to improve it on the Traveling Salesman Problem with Time Windows.

Presentation of the Algorithm

The Nested Rollout Policy Adaptation algorithm (NRPA) is an algorithm that learns a playout policy. There are different levels in the algorithm. Each level is associated to the best sequence found at that level. The playout policy is a vector of weights that are used to calculate the probability of choosing a city. A city is chosen proportionally to exp(pol[code(node,i)]). pol(x) is the adaptable weight on code x. code(node,i) is a unique domain-specific integer leading from a situation node to its i th child. This is comparable with previous known learning of Monte-Carlo simulations [START_REF] Drake | The last-good-reply policy for monte-carlo go[END_REF][START_REF] Rimmel | Biasing monte-carlo simulations through rave values[END_REF].

Learning the playout policy consists in increasing the weights associated to the best cities and decreasing the weights associated to the other cities. The algorithm is given in algorithm 2.

Application to the TSPTW

As for the NMC algorithm, adding expert-knowledge is possible in order to improve this generic algorithm. Consequently, the generality of the resulting algorithm is lower. We implement a NRPA algorithm with a specific Monte-Carlo policy.

The idea of this algorithm is first to force to visit cities as soon as they go after their window end. The reason is that cities that are after their window end should have been visited earlier and that must be taken into account for the continuation of the playout. If we force to visit them, the algorithm will try more to visit them in time.

The second idea of the algorithm is to avoid visiting a city if it makes another city go after its window end. It considers all the moves that do not make any city go after its window end.

These moves that avoid some cities can never be moves that force the algorithm into a suboptimal answer. These moves always imply a violation of the time window. Therefore they only change invalid solutions of the problem. An optimal move will not be pruned by our expert knowledge since it does not violate a constraint.

If there are still no possible moves after these two tests, the algorithm considers all the possible moves.

The resulting algorithm is labeled NRPA EK and is given in algorithm 3.

Experiments

First, in Section 5.1, we study the behaviour of the NRPA algorithm. Second, in Section 5.2, we compare it with the version defined in Section 4.2 on two problems among the set of problems from [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF]. Finally, in Section 5.3, we provide a comparison of the two algorithms studied in this work, the NMC algorithm in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF] and the state of the art results found in [START_REF] López-Ibáñez | Beam-ACO for the travelling salesman problem with time windows[END_REF]. In all our experiments we set α = 1 for the NRPA and the NRPA EK algorithms.

The behaviour of the NRPA algorithm

It has been found for the NMC algorithm and the NRPA algorithm (both on Morpion Solitaire) that a plateau is reached for each level of the algorithms, and then consequently, that increasing the level improves the results of the algorithms. In figure 2, similar results are shown for a TSPTW (on the problem rc204.1 from the set of problems from [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF]). We measure the score of a NRPA algorithm as a function of the time T for different levels. The time T represents the number of evaluations done for each level. Formally, T = N level . We recall that N is the number of iterations done for each level (> 0) of the NRPA algorithm. Each point is the average of 30 runs. Plateaus are here well represented.

For the level 1, T = N , and we can note that increasing N beyond 1000 does not improve the algorithm. The level 2 of the NRPA algorithm is quickly better than a level 1. It is better to use the level 3 of the algorithm than the level 2 around T = 30000, this means, approximately for N = 170 for the level 2 and N = 30 for the level 3. The level 4 of the algorithm becomes better than the level 3 around T = 330000, so it corresponds to N = 575 for the level 3 and N = 70 for the level 4.

NRPA against NRPA EK

In this experiment we compare the NRPA algorithm (as defined in Algorithm 2) and the version of NRPA with expert knowledge, presented in Section 4.2. This last algorithm is labeled NRPA EK in all our experiments. We test these two algorithms on two problems from the set of problems from [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF], the problem rc204.3 and the problem rc204.1. This last problem is the hardest one among all the problems of the set, and has 46 cities. In all this experiment, N is fixed at 50. Results are presented in Figure 3 for the problem rc204.3 and in Figure 4 for the problem rc204.1.

Results of the rc204.3 problem (Figure 3) are close, because this problem is simple enough for both algorithms and they are able to quickly find good solutions. However, the NRPA EK is slightly better for both the levels 3 and 4. On the hardest problem (Figure 4), results are much more significant. The level 3 of both the algorithms are not able to find a path with respect to all the time constraints. In average, the NRPA EK version is able to solve one more constraint than the NRPA algorithm. For the level 4 comparison, the NRPA EK is by far better than the classic version of the algorithm and is able to find a path without any violated constraint in all the runs.

State Of The Art problems

We experiment the NRPA algorithm on all the problems from the set of [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF].

Results are presented in Table 1. Problems are sorted according to n (i.e. the number of cities). The state of the art results are found by the ant colony algorithm from [START_REF] López-Ibáñez | Beam-ACO for the travelling salesman problem with time windows[END_REF]. The fourth column represents the best score found in [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF].

[13] uses an evolutionary algorithm for tuning heuristics used to bias the level 0 of a Nested Monte-Carlo algorithm. The NRPA algorithm is somehow close to the NMC algorithm, and a comparison between these two algorithms on a set of TSPTW is interesting. The classic version of the NRPA algorithm does not use any expert knowledge, but is still able to achieve good results on a lot of problems (Table 1, fifth column). We provide the Relative Percentage Deviation (RPD) for both NRPA (column 6) and NRPA EK (column 8). The RPD is 100 × value -record record .

Here again, we show that adding expert knowledge is useful and improves the algorithm. The NRPA EK version is able to find most state of the art results (76.66%), as shown in column 7. For difficult problems, the best results were obtained after 2 to 4 runs of the algorithm.

Conclusion

In this paper we study the generality of a nested rollout policy adaptation algorithm by applying it to traveling salesman problems with time windows. Even with no expert knowledge at all, the NRPA algorithm is able to find state of the art results for problems for which the number of nodes is not too large. We also experiment the addition of expert knowledge in this algorithm. With the good results of the algorithm NRPA EK, we show the feasability of guiding the rollout policy using domain-specific knowledge.

We show that adding expert knowledge significantly improves the results. It has been shown in our experiments that the NRPA EK algorithm (the expert knowledge version of the NRPA algorithm) is able to find most state of the art results (76.66%), and has good results on other problems.

An extension of this work is the use of a pool of policies (instead of just having one), in order to have an algorithm more robust in front of local optima. Adapting the parameters of the NRPA algorithm according to the problem difficulty is also an interesting work. 1. Results on all problems from the set from Potvin and Bengio [START_REF] Potvin | The vehicle routing problem with time windows part II: genetic search[END_REF]. First Column is the problem, second column the number of nodes, third column the best score found in [START_REF] López-Ibáñez | Beam-ACO for the travelling salesman problem with time windows[END_REF], fourth column the best score found by the NMC algorithm with heuristics from [START_REF] Rimmel | Optimization of the nested monte-carlo algorithm on the traveling salesman problem with time windows[END_REF], fifth column is the best score found by the NRPA algorithm and sixth column is its corresponding RPD. Seventh and eighth columns are respectively the score of the NRPA EK algorithm and the corresponding RPD. The problems for which we find the state of the art solutions are in bold.

Fig. 1 .

 1 Fig. 1. This figure explains three steps of a level 1 search. At each step of the playout of level 1 shown here with a bold line, an NMC of level 1 performs a playout (shown with wavy lines) for each available decision and selects the best one.

Fig. 2 .

 2 Fig. 2. Score as a function of T . Average on 30 runs. Plateaus are reached for the first three levels, and increasing the level of the algorithm improves the results.

Fig. 3 .

 3 Fig. 3. Comparison between the NRPA algorithm and the NRPA EK algorithm of the problem rc204.3. For both the algorithms N = 50.

Fig. 4 .

 4 Fig. 4. Comparison between the NRPA algorithm and the NRPA EK algorithm of the problem rc204.1. For both the algorithms N = 50.

Acknowledgement

This work has been supported by French National Research Agency (ANR) through COSINUS program (project EXPLORA ANR-08-COSI-004)