Aurélie Domnes

Viola Cavallo

Jean Baptiste Dubuisson

Isabelle Tournier

Fabrice Vienne

Crossing a two-way street: comparison of young and old pedestrians

Keywords: Street-crossing, Aging, Virtual environment

come   L'archive ouverte pluridisciplinaire

Introduction

Deciding when it is safe to cross a street in relation to available traffic gaps is a complex everyday task involving several functional abilities known to decline with aging [START_REF] Knoblauch | Field Studies of Pedestrian Walking Speed and Start-up Time[END_REF][START_REF] Salthouse | Executive functioning as a potential mediator of age-related cognitive decline in normal adults[END_REF][START_REF] Snowden | Motion perception in the aging visual system: minimum motion, motion coherence, and speed discrimination thresholds[END_REF]. Age-related declines in perceptual, cognitive, and physical abilities have been shown to result in non-optimal street-crossing decisions and behaviors [START_REF] Dommes | The role of perceptual, cognitive, and motor abilities in street-crossing decisions of young and older pedestrians[END_REF][START_REF] Dommes | Functional declines as predictors of risky street-crossing decisions in older pedestrians[END_REF][START_REF] Dunbar | Older Pedestrians: A Review[END_REF] and may contribute to the high rate of fatal or serious-injury crashes found for old pedestrians (ONISR, 2011).

Since the 90's, an increasing number of studies have been examining the characteristics of pedestrians (such as age) and/or the traffic environment (such as the number of lanes and the speed of approaching cars) likely to raise the risk of a pedestrian being involved in an accident when crossing the street. The pioneer observational study by [START_REF] Oxley | Differences in traffic judgements between young and old adult pedestrians[END_REF] showed that the higher number of unsafe street crossing decisions among pedestrians over 65 years of age occurred mostly in complex traffic situations such as two-way undivided streets, whereas their street-crossing safety improved significantly in less complex situations such as one-way streets. As shown in a French accident study, old pedestrians are more likely to be hit during the second half of the crossing, i.e., on the far side of the road [START_REF] Fontaine | Fatal pedestrian accident in France: a typological analysis[END_REF]. [START_REF] Dunbar | Using epidemiological data to address psychological questions about pedestrian behaviour[END_REF][START_REF] Dunbar | The relative risk of nearside accidents is high for the youngest and oldest pedestrians[END_REF] analyzed road-accident data from Great Britain but obtained different findings by observing an especially high risk of accidents among the oldest pedestrians on the near side of the street.

Although age-specific difficulties handling traffic approaching from several directions are worth investigation in view of making older pedestrian street-crossing safer, only a few papers have studied them experimentally. This is the aim of the present study. To our knowledge, some rare observational studies [START_REF] Oxley | Differences in traffic judgements between young and old adult pedestrians[END_REF][START_REF] Zhuang | Pedestrians' crossing behaviors and safety at unmarked roadway in China[END_REF][START_REF] Dunbar | The relative risk of nearside accidents is high for the youngest and oldest pedestrians[END_REF] and accident analyses [START_REF] Fontaine | Fatal pedestrian accident in France: a typological analysis[END_REF][START_REF] Dunbar | The relative risk of nearside accidents is high for the youngest and oldest pedestrians[END_REF] have been dedicated to old pedestrians in two-way road traffic situations but faced up to difficulties when attempting to specifically examining the role of precise traffic-or pedestrians-related characteristics because they were conducted in real-life situations where these factors could not be experimentally manipulated.

Although laboratory studies are unlikely to give a perfect assessment of the frequency of unsafe choices in the real world [START_REF] Holland | Gender differences in factors predicting unsafe crossing decisions in adult pedestrians across the lifespan: a simulation study[END_REF], they are helpful in controlling factors such as traffic. To our knowledge, there are only two experimental studies about two-way street crossings, but they used judgment tasks where participants indicated their choices by pressing a response button [START_REF] Dommes | Functional declines as predictors of risky street-crossing decisions in older pedestrians[END_REF] or taking one step forward [START_REF] Holland | Gender differences in factors predicting unsafe crossing decisions in adult pedestrians across the lifespan: a simulation study[END_REF]. In these studies, the pedestrians did not carry out a crossing task, so the actual behaviors in each of the two lanes of the street (such as walking speed, acceleration, and safety margin) could not be studied. However, the [START_REF] Holland | Gender differences in factors predicting unsafe crossing decisions in adult pedestrians across the lifespan: a simulation study[END_REF] study revealed an interesting finding which we propose to further examine here using a task that allows for an actual two-way crossing: looking at the far lane immediately before stepping out was associated with safer road-crossing choices, and this behavior was executed the least often by old pedestrians. The authors assumed, in accordance with [START_REF] Oxley | Differences in traffic judgements between young and old adult pedestrians[END_REF] and [START_REF] Fontaine | Fatal pedestrian accident in France: a typological analysis[END_REF], that old adults have trouble taking into account the far side of the road before beginning to cross and are thus more often involved in far-lane collisions than younger pedestrians are. But because the participants were not actually walking, the old pedestrians could not compensate for the selection of incorrect gaps by walking faster. Moreover, participants were watching videos of real approaching cars, so characteristics of the traffic environment like speed could not be studied, even though these characteristics are known to be an important risk factor in aging pedestrians.

Most experimental studies on old pedestrians concern one-way crossings [START_REF] Lobjois | Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task[END_REF][START_REF] Lobjois | The effects of aging on street-crossing behavior: from estimation to actual crossing[END_REF][START_REF] Lobjois | The effects of age and traffic density on street-crossing behavior[END_REF][START_REF] Oxley | Crossing roads safely: An experimental study of age differences in gap selection by pedestrians[END_REF]. As in observational studies, old adults are found to adopt shorter safety margins, especially when the speed of the approaching vehicles is high, with more unsafe decisions at higher speeds than lower speeds in simulated one-way traffic environments. Most likely because of diminished perceptual and cognitive abilities [START_REF] Dommes | The role of perceptual, cognitive, and motor abilities in street-crossing decisions of young and older pedestrians[END_REF], old people appear to use simplifying heuristics based primarily on the distance of the approaching car instead of on the time gap, which young pedestrians appear to use [START_REF] Lobjois | Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task[END_REF][START_REF] Lobjois | The effects of aging on street-crossing behavior: from estimation to actual crossing[END_REF][START_REF] Oxley | Crossing roads safely: An experimental study of age differences in gap selection by pedestrians[END_REF]. Because an approaching vehicle is farther away at a high speed than at a low one for a given available time gap, older people more often decide that it is safe to cross, walk more slowly, and choose to cross in shorter safety margins when the speed of the approaching vehicle is high. The use of distance-based heuristics is related to an overestimation of the available time and thus to very dangerous crossing behaviors. The misperception of time-to-arrival in older adults has even been shown to be a predictor of unsafe crossings in one-way traffic situations [START_REF] Dommes | The role of perceptual, cognitive, and motor abilities in street-crossing decisions of young and older pedestrians[END_REF].

The aim of the present study was to gain a better understanding of the risk factors that heighten the probability that old pedestrians will be involved in a collision when crossing a two-way street. The present study experimentally investigates the effects of age, time gap availability in each lane, and speed of approaching cars, in a safe and controlled simulated environment where participants walk on an experimental two-way road. Differences in the results for the two lanes are of particular interest to the study of looking and crossing behaviors. Because of age-related perceptual, cognitive, and motor limitations, and in line with [START_REF] Oxley | Differences in traffic judgements between young and old adult pedestrians[END_REF] as well as [START_REF] Fontaine | Fatal pedestrian accident in France: a typological analysis[END_REF], old pedestrians are expected to experience more difficulty than young pedestrians in selecting safe gaps in the far lane of traffic and in compensating for risky decisions by increasing their walking pace during crossing. According to earlier works [START_REF] Lobjois | Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task[END_REF][START_REF] Lobjois | The effects of aging on street-crossing behavior: from estimation to actual crossing[END_REF][START_REF] Oxley | Crossing roads safely: An experimental study of age differences in gap selection by pedestrians[END_REF], a higher number of unsafe crossings as speed increases should also be observed in old pedestrians.

Method

Participants

A total of 84 participants took part in the experiment: 18 young adults ranging in age between 19 and 35 years (M = 29.17, SD = 4.73), 28 younger-old adults ranging between 62 and 71 years (M=68.11, SD=2.41), and 38 older-old adults ranging between 72 and 85 years (M = 75.68, SD = 3.31). The younger-old and older-old groups were respectively below and above the median age (72 years old) and the mean age (72.5) of all old participants. The young group was comprised of 8 women and 10 men, the younger-old, of 22 women and 6 men, and the older-old, of 28 women and 10 men.

All participants had normal or corrected-to-normal binocular visual acuity (at least 6/10, Ergovision, Essilor®). Walking speeds were also measured1 . Older-old participants (M=1.21 m/s, SD=0.15) and younger-old participants (M=1.23 m/s, SD=0.14) walked more slowly than young participants (M=1.57 m/s, SD=0.09); these walking speeds are in accordance with several field studies (see e.g., [START_REF] Knoblauch | Field Studies of Pedestrian Walking Speed and Start-up Time[END_REF]. Participants in the older groups specifically took the MMSE test [START_REF] Folstein | Mini-mental state: A practical method for grading the cognitive state of patients for the clinician[END_REF] to ensure the absence of pathological aging symptoms. All were in good health (screened by self-report), were living at home, and went out regularly without help. The study was approved by the institutional ethics committee.

Experimental setup

The street-crossing simulation device included a portion of a real experimental street (5.7 m wide, indicated by continuous grey markings on the floor, used also to demarcate the edge of the flat virtual sidewalks), an image-generation system, a rear-screen projection system, a 3D sound-rendition system, and a movement recording system. The visual scenes were projected on ten screens (2.55 m high and 1.88 m wide) forming a corridor in which the pedestrian could walk up to 7 meters (see Figure 1). The setup provided the pedestrian with a horizontal visual field between 180° (at the starting point of the crossing) and 300° (in the middle of the street and at the sidewalk on the other side), and a vertical visual field of 40°. The pedestrian's initial position was such that s/he could watch the traffic coming from both directions by turning her/his head to the left or right (see Figure 1). S/he was standing at the edge of a sidewalk, facing the experimental street, and had to walk to the other side of the street when s/he thought it was safe to do so. The images (60 frames per second) were calculated and projected at the participant s eye height. Scenes were updated interactively by a movement-tracking system (Vicon®) that recorded the participant s locomotion (submillimeter accuracy) and head motion.

[FIGURE 1]

The visual scenes represented a two-way street 5.70 meters wide sidewalk-to-sidewalk.

Traffic consisted of groups of motorcycles and cars (between 5 and 10 vehicles). The direction of the traffic followed the French traffic rules: on the near-side lane, the flow of vehicles was approaching from the left of the pedestrian standing on the sidewalk. Vehicles in the far lane were approaching from the right.

Procedure and experimental task

Participants were tested individually on the street-crossing simulator. For each trial, they had to judge whether the available gaps in the approaching traffic where suitable for crossing the street. They were instructed to choose traffic gaps in which they could cross the entire two-way street without running and/or stopping in the middle of the street. If they thought it was safe to do so, they were instructed to cross. Otherwise they waited for the next trial. The participants decision to cross or not to cross, and their motion until they reached the opposite sidewalk were recorded.

The experimenter began the session by describing the basic principles of the street-crossing simulator. Then the participant performed a maximum of 18 practice trials. The practice trials were stopped when the participant was comfortable and fully understood the task. The participant then performed the experimental street-crossing task composed of 2 blocks of 18 trials.

Vehicle speed (40 or 60 km/h) and time gap between two target cars in each of the two traffic flows (from 1 to 5 s, in 1-s increments) were varied. Table 1 describes the manipulated time gaps between the two target cars. These gaps were always synchronized and thus simultaneously available in both lanes. The time gaps always appeared 6 s after the onset of the trial, providing a view of the traffic scenes for 6 s before participants could cross (see Figure 1). All other vehicles in the traffic groups were separated by about 1.5 s so that participants could not cross between them. The 17 time-gap combinations (see Table 1) and the 2 speeds of approaching cars resulted in a total of 34 trials. They were presented in random order in 2 blocks, with a break between the blocks. one time gap combination (3 s in each lane) was repeated to make the link between the two blocks, making a total of 36 trials.

The street-crossing task took about 30 minutes to complete.

[TABLE 1]

Data analysis

Six measures were considered. The first was accepted crossings, and the other five were derived from the movement-tracking system and measured head movements and distance travelled.

-Accepted crossings: trials were scored as to whether the participant did or did not accept the available gaps for crossing the street.

-Number of looks: the number of looks in the direction of each lane were counted before the participant began to cross.

-Looking time: the time spent looking at traffic approaching in each lane of the two-way street was measured before the participant crossed the street.

-Collisions: a crossing was scored as a collision when the participant was virtually hit by the approaching car: s/he was in front of the approaching car (within the width of the front end of the car) when it passed the crossing line. This variable was calculated for the near and the far lanes of the two-way street and was expressed as percentage of the total number of crossings accepted by the participant.

-Crossing time: crossing time was calculated for each crossing performed (without leading to a collision) and each lane of the two-way street. Crossing time for the first lane was equal to the time between when the participant started to walk and when s/he had finished crossing that lane (i.e., in the middle of the street); crossing time for the far lane was equal to the time between when the participant was in the middle of the street and when s/he arrived the opposite sidewalk.

-Safety margin: safety margin was calculated for each crossing and each lane of the street.

Safety margin was measured as the time between when the participant had gone past the path of the approaching car (width of the front end of the approaching car) and when the front end of the car reached the crossing line. In other words, safety margin was the time left before a collision.

Accepted crossings were analyzed through logistic regressions. The other five behavioral indicators were entered into a multivariate analysis of variance (MANOVA). MANOVA is a more appropriate analysis than independent ANOVAs for cases where there is a moderately high correlation between the dependent variables [START_REF] Tabachnick | Using multivariate statistics[END_REF]). The significance level was set at .05. Wilks multivariate statistic was used. Wilks lambda ranges from 0 to 1; the lower it is the more the given effect contributes to the model. The partial eta-squared statistic ( 2 p ) was used as an index of the relative effect size. Effects found to be significant in the MANOVA were tested against each of the dependent measures using univariate analyses. Fisher LSD post-hoc tests were performed to determine the source of the significant effects.

Results

Crossing decisions

The participants responses are plotted in Figure 2 as a function of age group and the time gap available in each lane.

[

FIGURE 2]

Based on the raw data, this figure shows different decision-making behavior for young and old participants. Contrary to old participants, young participants considered the available time gaps in both lanes in deciding whether or not to cross the two-way street: when the time gap available in the near lane was long (5 s) but short in the far lane (2 s), most of the young participants refused to cross (on average 14% acceptance). In contrast, both groups of old participants decided to cross much more often (on average 72% acceptance). Both old groups systematically increased the percentage of accepted crossings based on the time gap available in the near lane(Figure 2), while neglecting the one available in the far lane. Their crossing criteria therefore seem to be different, with whole-road choices by young pedestrians and biased near-lane choices by old pedestrians.

To participants did (see Figure 3), they made significantly more decisions that led to collisions with an approaching car (see Table 2). Crossings were slower and less safe than among young participants (see Tables 3 and4). Whereas older-old participants had more collisions than younger-old participants, there were no significant differences between the two groups of old participants in looking time, crossing time or safety margin.

[FIGURE 3]

[TABLES 2, 3 and 4]

The results showed a multivariate main effect of lane, =. in the far lane of the two-way street. Whereas participants made more head movements in the direction of the far lane, they looked longer at the near lane (see Figure 3). Participants had more collisions mostly in the far lane than in the near lane (see Table 2). Participants seemed to have tried to avoid imminent danger in the far lane because crossings were faster and less safe in the far lane than in the near lane (see Tables 3 and4).

The multivariate main effect of speed was also significant, =. 2). Participants did not seem to be aware of the fast arrival of the approaching car, because crossing times were longer and safety margins shorter at 60 km/h than at 40 km/h (see Tables 3 and4).

The multivariate interaction between age group and lane was significant, =.29, revealed greater difficulty in both groups of old participants in considering the far lane of the two-way street. Whereas young participants looked significantly more often and longer at the far lane than the near lane before deciding to cross, old participants looked more often and longer at the near lane (see Figure 3). Both old groups obtained many more collisions on the far lane than on the near lane, whereas the percentage of collisions did not vary significantly by lane among the young group of participants. Indeed, significant age-related differences were observed only in the far lane, where both groups of old participants had more collisions than did young participants, and the older-old had significantly more collisions than the younger-old. Post-hoc tests indicated significant lane differences between the three groups of participants, for both crossing time and safety margin. Interestingly, post-hoc test results indicated that young participants crossed the far lane significantly faster than did younger-old and older-participants, whereas no age-related differences were found in the near lane. By walking faster, maybe young participants tried to avoid potential collisions in the far lane, whereas older ones could not avoid them because of their limited ability to increase their gait.

F
In fact, the age-related differences in safety margin were significant only in the near lane, where both groups of old participants adopted smaller safety margins than young participants did. In the far lane, the young participants had safety margins that were as small as the younger-old and older-old margins (p=.54 and p=.95), but they avoided many more collisions than the older ones did.

The multivariate interaction between age group and speed was also significant, =.77, F(10,154)=2.18, p<.05, 2 p =.12. Univariate analyses yielded a significant interaction only on two of the five measures, i.e., collisions F(2,81)=3.21, p<.05, 2 p =.07; and crossing time F(2,81)=7.12, p<.01, 2 p =.15. Whereas speed differences were not significant in the young group or the younger-old group, older-old participants had more collisions at 60 km/h than at 40 km/h. Age-related differences were significant at 60 km/h only. Regarding crossing time, post-hoc tests yielded no significant speed differences in the young group, whereas both groups of old participants crossed more slowly at 60 km/h than at 40 km.

The multivariate interaction between lane and speed was significant, =.79, F(5,77)=3.97, p<.01, 2 p =.21, as was the multivariate interaction between age group, lane and speed =.79, F(10,154)=1.94, p<.05, 2 p =.04. Regarding the latter interaction, univariate analyses yielded a significant interaction only on one of the five measures, i.e., safety margin F(2,81)=4.87, p<.05, 2 p =.11. Whereas no significant group differences appeared in the far lane, age-related differences were observed in the near lane only at 60km/h, where older-old participants adopted smaller safety margins than younger-old and young participants did. In contrast, group differences were not significant at 40 km/h in the near lane.

Discussion

The present study was aimed at investigating the effects of age, available time gap in each lane, and speed of approaching cars on the way a pedestrian chooses a gap during which to cross on a two-way street. The differences between the results for the two lanes are of particular interest to the study of visual exploration and crossings behavior.

In line with previous research using estimation tasks [START_REF] Dommes | Functional declines as predictors of risky street-crossing decisions in older pedestrians[END_REF][START_REF] Holland | Gender differences in factors predicting unsafe crossing decisions in adult pedestrians across the lifespan: a simulation study[END_REF] or with accident and observational data collected in real-world environments [START_REF] Fontaine | Fatal pedestrian accident in France: a typological analysis[END_REF][START_REF] Oxley | Differences in traffic judgements between young and old adult pedestrians[END_REF], the situation of two-way street crossing proved to be a particularly difficult task for old adults. Older-old pedestrians ages 72 to 85

were found to make street-crossing decisions that led to collisions with approaching cars more often than younger-old (ages 62 71) and young (ages 19 35) participants. This age effect is also in line with the French crash statistics (ONISR, 2011) indicating that people over 75 make up the most vulnerable pedestrian group, accounting for more than 37% of fatalities although representing less than 9% of the population. Younger-old and older-old participant groups were also found to cross more slowly and to use smaller safety margins than young participants. This result corroborates those previously obtained in experimental one-way traffic studies using similar behavioral indicators to assess street crossing [START_REF] Dommes | The role of perceptual, cognitive, and motor abilities in street-crossing decisions of young and older pedestrians[END_REF][START_REF] Lobjois | Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task[END_REF][START_REF] Lobjois | The effects of aging on street-crossing behavior: from estimation to actual crossing[END_REF].

Also in line with real-world observations and accident studies [START_REF] Fontaine | Fatal pedestrian accident in France: a typological analysis[END_REF][START_REF] Oxley | Differences in traffic judgements between young and old adult pedestrians[END_REF] or with analyses conducted on real traffic scenes [START_REF] Holland | Gender differences in factors predicting unsafe crossing decisions in adult pedestrians across the lifespan: a simulation study[END_REF], the results of the present experimental study showed that the old groups' difficulties occurred mostly in the far lane of the two-way street. Biased decision-making favoring the nearer lane was observed: both groups of old participants looked more often and longer at the near lane than at the far lane, and regression analyses showed that they based their crossing decisions much more often on the gap available in the near lane, while neglecting the gap available in the far lane, contrary to the young pedestrians who considered both gaps in both lanes to decide whether or not to cross the two-way street. Old pedestrians tended to step into the street when only the near lane was safe: out of the 3024 decisions made by the 84 participants, 128 led to a collision, 65% of which were made by old participants in situations where the time gap was sufficient for them in the near lane (3, 4, or 5 s) but too short in the far lane (2 s). Because old pedestrians mainly checked traffic approaching in the near lane before starting to cross, they could find out when reaching the middle that cars approaching from the opposite direction were too close. Even if they became aware of this, these non-optimal choices could not be compensated for by walking faster due to the declines in physical abilities (see e.g., [START_REF] Salzman | Gait and balance disorders in older adults[END_REF]. When required to change from walking at preferred speed to walking quickly, old people have been shown to fail to achieve the same increases in speed and stride length relative to the increases achieved by young adults [START_REF] Shkuratova | 85, 582-8. types of cognitive tasks on postural stability in older adults with and without a history of falls[END_REF]). These motor difficulties could have led in the present experiment to collisions on the far side of the street for old pedestrians in particular.

It can be assumed that the observed visual exploration strategies and the ensuing crossing behaviors reflect diminished functional abilities. Because of perceptual and cognitive declines (see e.g., [START_REF] Ball | Visual Attention Problems as a Predictor of Vehicle Crashes among Older Drivers[END_REF][START_REF] Poulter | Errors in motion processing amongst older drivers may increase accident risk[END_REF][START_REF] Salthouse | The processing-speed theory of adult age differences in cognition[END_REF][START_REF] Salthouse | Executive functioning as a potential mediator of age-related cognitive decline in normal adults[END_REF], old pedestrians may not be able to process all information in the visual scene and so may consider only the closer scene when making their decision to cross a two-way street. Given their fear of falling (e.g., Scheffer, Schuurmans, Van Dijk, [START_REF] Scheffer | Fear of falling: measurement strategy, prevalence, risk factors and consequences among older persons[END_REF] and their need to keep their balance during walking [START_REF] Woollacott | Balance control during walking in the older adult: Research and its implications[END_REF], they also seem to allocate more attention to watching their steps as they cross, causing them to at least partly disregard the approaching traffic [START_REF] Avineri | Pedestrians' behaviour in cross walks: The effects of fear of falling and age[END_REF]. At signal-controlled intersections, old pedestrians have even been shown not to look at the traffic at all [START_REF] Job | Pedestrians at traffic light controlled intersections: Crossing behaviour in the elderly and nonelderly[END_REF]. Such an inadequate visual exploration strategy was also partly observed here in the non-signal-controlled crossings of the present experiment. There is evidence that old pedestrians often expect drivers to adapt to them [START_REF] Dunbar | Older Pedestrians: A Review[END_REF].

Some difficulty handling the far lane were also observed in the young pedestrians, although not as numerous or serious as in the old participants because young people can compensate for some rare non-optimal choices by speeding up. Although lane differences were not observed in terms of collisions for young participants, they exhibited safer behaviors in the near lane and difficulty on the far lane in terms of hasty crossings and small safety margins.

The far-lane difficulties of older adults found in the present experiment are inconsistent with [START_REF] Dunbar | Using epidemiological data to address psychological questions about pedestrian behaviour[END_REF][START_REF] Dunbar | The relative risk of nearside accidents is high for the youngest and oldest pedestrians[END_REF] epidemiological analyses. This discrepancy can be explained by important age differences in the pedestrian samples studied, insofar as Dunbar found a high risk of near-side accidents in very old pedestrians over 85 years of age. In line with the idea that cognitive declines increase with age, the decision-making of very old pedestrians (over 85) can no longer be accurate and lead to collisions right from the near side of the street for the oldest pedestrians [START_REF] Dunbar | Using epidemiological data to address psychological questions about pedestrian behaviour[END_REF][START_REF] Dunbar | The relative risk of nearside accidents is high for the youngest and oldest pedestrians[END_REF] or among people with Alzheimer's disease [START_REF] Gorrie | Crash characteristics of older pedestrian fatalities: Dementia pathology may be related to 'at risk' traffic situations[END_REF]. In contrast, the results of the present study suggest that decision-making is only slightly affected in younger-old pedestrians under age 85, with biased decisions favoring the near-side lane and thus collisions and behavioral difficulties mostly in the far lane. The question of near-versus far-side collisions among young and old pedestrians deserves further study in experiments involving a group of pedestrians over 85 years of age.

The old participants in the present experiment were also found to have difficulty safely handling situations where vehicles were approaching at a high speed. As a whole, they made a greater number of decisions that led to collisions when cars were approaching at 60 km/h than at 40 km/h. Risky crossing decisions at the high approach speed were particularly observed in the near lane, most likely because the far lane was not taken into account by old participants.

This effect of vehicle speed has been systematically observed in earlier studies using one-way traffic [START_REF] Lobjois | Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task[END_REF][START_REF] Oxley | Crossing roads safely: An experimental study of age differences in gap selection by pedestrians[END_REF] and interpreted as the use of simplified heuristics based on vehicle distance and a neglect of speed information.

Conclusions

The results of the present study brought out a greater risk of being involved in a collision for old pedestrians than for younger adults when crossing a two-way street. The most notable finding concerned to the high number of non-optimal decisions by old pedestrians with respect to the far lane. The most risky situation was when the near lane provided a safe gap for crossing but the far lane did not, because old pedestrians mainly checked for vehicles approaching in the near lane before crossing and could sometimes reach the middle of the street without looking at the far-side traffic at all.

Together with the use of simplifying speed-neglecting heuristics often reported in the literature [START_REF] Lobjois | Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task[END_REF][START_REF] Lobjois | The effects of aging on street-crossing behavior: from estimation to actual crossing[END_REF][START_REF] Oxley | Crossing roads safely: An experimental study of age differences in gap selection by pedestrians[END_REF] and also observed in the present experiment, the inadequate visual exploration strategies of older adults point to a substantial cognitive overload in the demanding situation of two-way street crossing. According to previous studies, this overload may be mainly related to attention deficits and reduced processing speed, both shown to predict unsafe crossing decisions by old pedestrians in oneway or in two-way situations [START_REF] Dommes | The role of perceptual, cognitive, and motor abilities in street-crossing decisions of young and older pedestrians[END_REF][START_REF] Dommes | Functional declines as predictors of risky street-crossing decisions in older pedestrians[END_REF]. Because sensorimotor performance becomes cognitively more demanding with advancing age [START_REF] Lindenberger | Memorizing while walking: Increase in dual-task costs from young adulthood to old age[END_REF][START_REF] Woollacott | Attention and the control of posture and gait: a review of an emerging area of research[END_REF], the control of posture and gait while walking could also contribute to the too high attentional requirements of the two-way street-crossing task for old pedestrians, who suffer from limited attentional resources.

One of the most interesting results of the present experiment is that old people appear to be unable to compensate for these non-optimal and dangerous choices by speeding up. The higher crash risk of old pedestrians could actually be the result of two parallel difficulties (i) biased decisions (toward the near lane and the distance of approaching cars) and (ii) little possibility of compensation by walking faster. Beyond the well-known motor decrements with aging (see e.g., [START_REF] Shkuratova | 85, 582-8. types of cognitive tasks on postural stability in older adults with and without a history of falls[END_REF], the absence of compensation of decision making difficulties by walking quickly could also be linked to the need of old people to visually control their gait and balance, impeding them therefore to observe the approaching traffic while walking. Several papers clearly show that old people need to watch their steps to avoid a fall while walking (see e.g., [START_REF] Avineri | Pedestrians' behaviour in cross walks: The effects of fear of falling and age[END_REF] and this sensorimotor performance prioritization could be even at the cost of any other performance (see e.g., Shumway-Cook, Woollacott, Kerns, & Baldwin, 1997).

The present findings could contribute to defining specific road-safety measures that could be implemented to counteract the difficulties of old pedestrians. One measure would be to increase the number of marked and/or signaled crossings (e.g., zebra, pelican and puffin crossings) and to make longer crossing-time allowances. Car-free islands in the middle of two-way streets could also considerably help old pedestrians cross the street. Table1. Time gaps simultaneously available between two target cars in the traffic flow (in s.).

Near lane (gap in s) 1 2 3 4 5

Far lane (gap in s) 1 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 [Note: Gaps in the far lane were updated according to the participant's walking speed (as measured previously across multiple trials) so that gaps from 1 s to 5 s were available in the far lane at the moment when the participant would have been in the middle of the street.]

  Islands lower their exposure to potential collisions by decreasing the time spent in the street, while also lightening the cognitive load of the street-crossing task by splitting it into two stages. Such islands mostly provide a safe place to pause in the middle of the street and allow pedestrians to visually explore the far side of the two-way street. Moreover, car-speed reduction measures are clearly important for pedestrian safety and are also recommended. Measures such as lowering speed limits in areas of high pedestrian activity should be considered.The present findings also raise the question whether training programs are a route worth exploring as a supplement to the above safety regulations and pedestrian-friendly infrastructure measures. A possible effective approach could be to offer mixed behavioral and educational training, as already demonstrated for improving the safety of older adults in oneway street-crossing situations(Dommes & Cavallo, 2012;[START_REF] Dommes | Age-related differences in streetcrossing safety before and after training of older pedestrians[END_REF].

Figure captions Figure 1 .

 captions1 Figure captions

Figure 2 .

 2 Figure 2. Percentage of accepted crossings for each age group as a function of the time gap available in each lane.

Figure 3 .

 3 Figure 3. Mean number of looks and mean looking time (in seconds) before crossing as a

  look further into this hypothesis, logistic regressions were computed on each age group's gap acceptance as a function of the time gap available in each lane. Data relative to younger-old and older-old participants were combined into one.The model was significant in the young group of participants, 2(2) = 244.95, p<.001, R²=.42. Both the time gap available in the near lane (Wald statistic = 80.301, p<.001) and the time gap available in the far lane (Wald statistic =101.81, p<.001) were significant predictors of the choices made by young participants. Indeed, the near-lane time gap (odds ratio=2.35) and the far-lane time gap (odds ratio=2.67) were equally powerful in predicting the young participants' decision to cross the two-way street.

	3.2. Crossing behaviors
	The 3 (age groups: young, younger-old, and older-old participants) x 2 (lanes: near and far
	lanes) x 2 (speeds: 40 and 60 km/h) MANOVA revealed a multivariate main effect of age
	group, =.29, F(10,154)=13.31, p<.0001, ²=.46. Univariate analyses indicated that four
	dependent measures contributed to the multivariate main effect, i.e., looking time
	F(2,81)=32.5, p<.001, ² p =.45; collisions F(2,81)=10.69, p<.001, 2	p =.21; crossing time
	F(2,81)=8.71, p<.001, 2

The model was also significant in the old group of participants, 2(2) =1075.62, p <.001, R²=.49. Here again, time gap available in the near lane (Wald statistic = 582.98, p<.001) and the time gap available in the far lane (Wald statistic =44.79, p<.001) were both significant predictors of the choices made by the old participants. But the near-lane time gap played a much more important role (odds ratio=4.23) than the far-lane time gap (odds ratio=1.39) in predicting the old participants' decision to cross the two-way street. p =.18); and safety margin F(2,81)=2.78, p=.067, 2 p =.06. Post-hoc analyses indicated greater difficulty in both groups of old participants. Although before crossing, both groups of old participants looked significantly longer at the traffic than young

Table 2 .

 2 Mean percentage of collisions. Standard deviations are shown in parentheses.

		Young	Younger-old	Older-old
	Near lane -40 km/h	0	1.16	1.75
		(0)	(3.53)	(4.27)
	Near lane -60 km/h	0	0.55	2.74
		(0)	(2.91)	(5.26)
	Far lane -40 km/h	0.69	4.03	5.49
		(2.95)	(7.84)	(9.56)
	Far lane -60 km/h	2.43	6	12.14
		(4.15)	(7.51)	(10.13)
	Age-group comparison	0.78	2.93	5.53
		(1.78)	(5.45)	(7.31)
	Lane comparisons by group				Mean
	Near	0	0.86	2.24	1.03
		(0)	(3.22)	(4.77)	(2.66)
	Far	1.56	5.01	8.82	5.13
		(3.55)	(7.67)	(9.84)	(7.02)
	Speed comparisons by group
	40 km/h	0.35	2.60	3.62	2.19
		(1.47)	(5.68)	(6.92)	(4.69)
	60 km/h	1.22	3.27	7.44	3.98
		(2.08)	(5.21)	(7.7)	(4.99)

Table 3 .

 3 Mean crossing time (in seconds). Standard deviations are shown in parentheses.

		Young	Younger-old	Older-old
	Near lane -40 km/h	2.26	2.25	2.32
		(0.36)	(0.26)	(0.26)
	Near lane -60 km/h	2.18	2.26	2.37
		(0.24)	(0.22)	(0.31)
	Far lane -40 km/h	1.63	1.90	1.94
		(0.11)	(0.15)	(0.22)
	Far lane -60 km/h	1.64	1.95	2.02
		(0.12)	(0.18)	(0.25)
	Age-group comparison	1.93	2.09	2.16
		(0.21)	(0.20)	(0.26)
	Lane comparisons by group				Mean
	Near	2.22	2.25	2.35	2.27
		(0.30)	(0.24)	(0.29)	(0.27)
	Far	1.64	1.93	1.98	1.85
		(0.12)	(0.16)	(0.23)	(0.17)
	Speed comparisons by group
	40 km/h	1.95	2.07	2.13	2.05
		(0.24)	(0.20)	(0.24)	(0.23)
	60 km/h	1.91	2.11	2.20	2.07
		(0.18)	(0.20)	(0.28)	(0.22)

Table 4 .

 4 Mean safety margin (in seconds). Standard deviations are shown in parentheses.

		Young	Younger-old	Older-old
	Near lane -40 km/h	2.27	2.18	2.13
		(0.41)	(0.30)	(0.35)
	Near lane -60 km/h	2.09	1.81	1.72
		(0.30)	(0.22)	(0.31)
	Far lane -40 km/h	1.87	1.83	1.82
		(0.34)	(0.22)	(0.34)
	Far lane -60 km/h	1.55	1.49	1.59
		(0.26)	(0.18)	(0.28)
	Age-group comparisons	1.94	1.83	1.81
		(0.33)	(0.23)	(0.32)
	Lane comparisons by group				Mean
	Near	2.18	1.99	1.92	2.03
		(0.35)	(0.26)	(0.33)	(0.31)
	Far	1.71	1.66	1.70	1.69
		(0.30)	(0.20)	(0.31)	(0.27)
	Speed comparisons by group
	40 km/h	2.07	2.01	1.97	2.02
		(0.37)	(0.26)	(0.35)	(0.33)
	60 km/h	1.82	1.65	1.65	1.71
		(0.28)	(0.20)	(0.29)	(0.26)

Walking speed over a distance equivalent to the width of the simulated street (5.70 meters materialized on the ground by two markers) was measured in the simulator room (but with no virtually approaching cars) on six trials at a normal to fast walking pace.

Acknowledgments

This research was supported by grants from the French Road Safety Foundation (SEPIA Project). The authors are grateful to the young and old participants for their participation, interest, and cooperation. We would also like to thank Sabine Langevin for her help in running the experiment, and Isabelle Aillerie and Jacky Robouant for their help in setting up the simulator scenarios and visual scenes. The authors are grateful to Vivian Waltz for her English editing.


Cyril Gavoille

Pierre Halftermeyer

Connectivity Labeling Scheme for Graphs on Surface

Keywords: connectivity, labeling scheme, forbidden sets, planar graphs, highergenus graphs

Introduction

A natural question in graph theory is to ask whether two vertices u, v are in the same connected component of a graph G. This can trivially be done in linear time. Observe that in linear time one can also assign to each vertex of G a label, so that the subsequent query between u and v can be answered in constant time by inspecting the label of u and the label of v only.

Understanding the evolution of connected components of a graph when some vertices or edges are removed (or forbid) is of great importance for many applications, in particular for Emergency Planning (cf. [START_REF] Pǎtraşcu | Planning for fast connectivity updates[END_REF]). Connectivity with forbidden set of edges has been solved almost optimally by [START_REF] Pǎtraşcu | Planning for fast connectivity updates[END_REF] in general graphs. However, identifying the connected components in a graph G with a forbidden-set X becomes a challenging question whenever X contains more than two vertices, even if we are allowed to preprocess the graph.

In this paper we consider the problem of labeling the vertices of G such that, for every forbidden subset X of vertices of G, and every vertex u in G \ X, one can identify the component of u in G \ X given the labels of u and the label of each vertex of X.

For this problem and for G planar, Courcelle et al. [START_REF] Courcelle | Connectivity check in 3-connected planar graphs with obstacles[END_REF] have proposed a solution using O(log n)-bit labels and O(log n) query time, after preprocessing X in time O(|X| 2 ). We propose an extension of this result to graphs embedded on a surface of Euler genus g (the surface can be orientable or not).

Our contribution

Theorem 1 Every 3-connected n-vertex Euler genus-g map G admits a O(g log n)-bit labeling for forbidden-set connectivity queries. All the labels can be computed in time O(n + g). Given a forbidden-set query X ⊂ V (G), one can preprocess X in time O(Sort(|X|+g, n+g) so that one can subsequently identify in time O(Pred(|X| + g, n + g)) the connected component of u in G \ X, for every vertex u of G \ X.

Here Sort(k, n) stands for the time complexity of sorting k integers ranging in {1, . . . , n}, and Pred(k, n) for the time complexity for predecessor search in a sequence of k sorted integers in {1, . . . , n}. It is known that

Sort(k, n) = O(k √ log log k ) and Pred(k, n) = O(log log (n/k)) in the log n-bit word RAM model.
Our scheme is only based on combinatorial embedding (map) of the graph. For the planar case (g = 0), our scheme is simpler than the one of Courcelle et al. [START_REF] Courcelle | Connectivity check in 3-connected planar graphs with obstacles[END_REF], since it does not require any computational geometry reduction and so avoids the Planar Point Location bottleneck [START_REF] Chan | Transdichotomous results in computational geometry, I: Point location in sublogarithmic time[END_REF]. This result in an exponentional improvement of the query time. These time bounds are comparable to those of the recent work of [START_REF] Borradaile | Connectivity oracles for planar graphs[END_REF]. However, to the best of our knowledge, this latter scheme, restricted to planar graphs, does not convert into a labeling scheme.

Outline of our construction

First, we compute in O(n + g) time a cut-graph C of the surface embedding of the input graph G. Recall that a cut-graph is a subgraph of G such that the surface obtained by cutting along the edges of C is homeomorphic to a disc. We can ensure that the cut-graph C is composed of a spanning tree of bounded degree plus O(g) edges.

By definition of C, cutting along its edges results in a map M whose all the vertices lie on the border of C, i.e., an outerplanar map. Each vertex of G is associated with at most O(g) vertices of M .

We construct a specific forbidden-set connectivity labeling for M and C. For the outerplanar map M we obtain labels of O(log (gn)) = O(log n) bits with a scheme much simpler and efficient than the general planar scheme of [START_REF] Courcelle | Connectivity check in 3-connected planar graphs with obstacles[END_REF]. For the cut-graph C we develop an ad-hoc scheme with O(g log n)-bit labels.

Our construction then uses a meta-scheme that allows us to identify the connected component of any vertex u in G \ X by querying the components of u in M \ X and in C \ X. The preprocessing of X by our meta-scheme costs O(|X| + g) once X has been sorted.

Acutally, our meta-scheme applies to a wider class of graphs, typically the graphs having a k-page embedding (cf. [START_REF] Wood | Degree constrained book embeddings[END_REF] for definition) whose spine is constrained to be covered by a forest of at most k trees of degree bounded by k whose edges belong to only one page of the embedding. Labels are of size O(k log n) bits.

Conclusion

Our solution provides a query time of O(Pred(|X|, n)) (for fixed g), which can be proved optimal even on a path with n vertices by a straightforward reduction to predecessor query. Concerning the label length, our O(g log n)-bit solution can conceivably be improved. In fact, one can show that Ω( √ g + log n)-bit labels are required. In the light of our meta-scheme, we leave open the problem of determining the optimal label length for genus-g graphs.


Dominique Py
email: dominique.py@lium.univ-lemans.fr

Ludovic Auxepaules
email: ludovic.auxepaules@lium.univ-lemans.fr

Mathilde Alonso Lium
email: mathilde.alonso@lium.univ-lemans.fr

Diagram, a Learning Environment for Initiation to Object-Oriented Modeling with UML Class Diagrams

Learning environments for object-oriented modelling in UML which offer a rich interaction usually impose, in return, strong restrictions on the range of exercises they can address. We propose to overcome this limit by including a diagnostic module that compares the student diagram with a reference diagram. This approach enables to combine the advantages of an open environment (in which the teacher can add new exercises without constraints on the vocabulary or the size of the diagram) with a sophisticated interaction that offers methodological help, encourages self-correcting and self-monitoring, and provides the learner with specific graphic tools. These principles have been developed and implemented through a learning environment for UML class diagrams. Experiments have been conducted in ecological context and show that this approach is achievable and quite effective.

INTRODUCTION

Nowadays, modeling is a core topic in most Computer Science and Software Engineering curricula, especially since the object-oriented modeling language UML (Unified Modeling Language) has been accepted as the standard graphical language for specifying software systems. Recent research works have focussed on the design of computer-supported learn-ing environments for modeling, especially for object-oriented modeling [START_REF] Baghaei | A collaborative constraint-based intelligent system for learning object-oriented analysis and design using UML[END_REF][START_REF] Moritz | Generating and Evaluating Object-Oriented Designs in an Intelligent Tutoring System[END_REF] and database modeling [START_REF] Suraweera | An Intelligent Tutoring System for Entity Relationship Modeling[END_REF]. In these environments, the relevance of the feedbacks relies on the system's ability to evaluate the correctness of the student's work. Due to the lack of deterministic methods for checking the consistency of a model, performing this evaluation is still a difficult task. To make it easier, designers can impose different restrictions on the interaction, but this also restricts the learner's ways of expression and the problem range of the environment.

We have tried to overcome these limits by exploring a new approach that aims at designing an open learning environment. This approach relies on a specific interaction model and a diagnostic method that evaluates a diagram and enables the system to provide the learner with textual feedbacks that take into account the correctness of his/her diagram.

In section 2 we describe the context of this work and present the state of the art. Section 3 specifies the objectives and approach adopted in Diagram. The model of interaction is described in section 4, the diagnostic method and its results in section 5 and the pedagogical feedbacks in section 6. Lastly, section 7 describes an experiment of the environment and discusses its results.

LEARNING OBJECT-ORIENTED MODELING

Since the development of OOM languages, many empirical studies, pedagogical tools and books have been devoted to OOM teaching. In this section, we present a brief survey of these studies and the limits of these approaches.

UML

UML is a language standardized in 1997 by the Object Modeling Group (OMG) which facilitates the design of programs (OMG UML, 2010). However, UML does not include a complete methodology for analysing and designing OO programs.

The current version of UML 2.1 consists of thirteen types of diagrams, representing different aspects of a software system. Among these diagrams, the class diagram is the core of the modeling process. It is used during the phases of analysis and design and can represent information at various levels of abstraction and precision. For that reason, it is often the first type of diagram taught in the OOM courses. This is why we chose to focus our study on the class diagram and its main elements: classes, relationships and attributes.

Difficulties of OOM Learning

Empirical research works have studied the difficulties that students face when they learn OOM [START_REF] Moisan | Teaching Object-Oriented Modeling and UML to Various Audiences[END_REF]. These studies show that theoretical knowledge of UML syntax and semantics is not enough: high level skills, like problem analysis and abstraction, are essential and can only be acquired by practice. Thus, [START_REF] Habra | Teaching Object Orientation at the Design Level[END_REF] stress that no universal rule applies for the creation of a model, and note that learners need methodological help to guide their creativity. This point of view is shared by [START_REF] Frosch-Wilke | Using UML in Software Requirements Analysis -Experiences from Practical Student Project Work[END_REF] who estimates that modeling is acquired by practice and recommends to provide learners with processes or steps to build their diagram.

Learning Environments for OOM

Different approaches to computer-supported learning environments for object-oriented modeling have been explored so far, mainly the constraintbased approach, illustrated by Collect-UML [START_REF] Baghaei | Problem-Solving Support in a Constraint-based Tutor for UML Class Diagrams[END_REF], and the curriculum-based approach, used in DesignFirst-ITS [START_REF] Moritz | Generating and Evaluating Object-Oriented Designs in an Intelligent Tutoring System[END_REF].

Constraint-Based Modeling, as defined by [START_REF] Ohlsson | Constraint-Based Student Modeling[END_REF], consists in defining the domain rules in terms of constraints, then checking that the learner's answer satisfies these constraints. This approach was used for databases learning in Kermit [START_REF] Suraweera | An Intelligent Tutoring System for Entity Relationship Modeling[END_REF] and OOM learning in Collect-UML [START_REF] Baghaei | A collaborative constraint-based intelligent system for learning object-oriented analysis and design using UML[END_REF]. In Collect-UML, the learner builds a class diagram starting from a textual description of the problem. He/she selects an expression in the text to model the corresponding object. Collect-UML includes a diagnostic tool, based upon domain-specific constraints, that checks whether the learner's diagram satisfies these requirements. Each constraint is composed of a relevance condition and a satisfaction condition. When the former is satisfied and the latter is not, the constraint is violated and an error message is displayed. Usually, the constraint-based approach is well suited for open domains. However, few general constraints exist in UML, so that the semantic constraints in Collect-UML do not actually express domain constraints, but differences that can be accepted between the learner's diagram and a correct diagram, provided by an expert. For example, a constraint is: "if the ideal solution contains a subclass C, and the learner's solution contains a class C, then C must also be a subclass in the learner's diagram". This has strong consequences on the interaction, because the learner is forced to pick up the class and relation names from the text problem, he/she is not allowed to create elements freely, nor to choose their name. As a consequence, Collect-UML is restricted to problems that do not contain implicit elements. The constraint-based approach, as implemented in Collect-UML, is quite close to the "bug catalogue" approach, because it can only recognize the bugs that have been foreseen by the designers.

The intelligent tutoring system DesignFirst-ITS [START_REF] Moritz | Generating and Evaluating Object-Oriented Designs in an Intelligent Tutoring System[END_REF] is based on a "design-first" curriculum that introduces object-oriented design (using elements of UML) before coding. An author module enables the teacher to create new exercises and automatically generates the solution diagram. An evaluation module compares the learner's diagram to the solution and typical bugs, and a pedagogical agent provides help and explanations. Design-First-ITS is quite sophisticated, but the system is restricted to the very first steps of learning, due to the current limits of the expert module. When the teacher creates a new problem, he has to use declarative sentences with basic syntactic structure and active voice. The problem statement must contain all the details about the classes, attributes and methods. Implicit elements and useless details are proscribed. At last, the diagram should not comprise more than five classes. Consequently, the range of problems that can be solved with DesignFirst-ITS is quite small, and the learners have few ways of expressing their creativity when solving a problem.

DIAGRAM'S GENERAL FRAMEWORK

Before presenting more precisely the Diagram environment, we expose in this section the general approach that we adopted, the base of exercises we used to evaluate the environment, and present an example of problem that will be used throughout the article.

Research Motivation and Objectives

The teachers use a great variety of exercises during the first steps of learning, and this diversity is necessary to organize the course and introduce gradually new concepts. Thus, our first objective was to design an open environment, in which the teacher can add new exercises without constraints on the vocabulary or the size of the diagram. Such constraints strongly limit the expressive power and the range of exercises tackled by environments like Collect-UML or DesignFirst-ITS. In Diagram, the problem statement can include useless details and implicit classes or relations, like problems used in real university courses. The creation of an exercise only requires the teacher to type the statement and to give a correct diagram.

The studies mentioned in section 2 show that two points of interaction design are crucial: first, methodological guidance, in order to mitigate the absence of modeling method, and second, graphic tools for creating the diagram. Our second objective was to design an interface that includes methodological help, encourages self-correcting and self-monitoring, and provides the learner with various and relevant graphic tools. We set up a simple methodological guidance: the learner must follow several steps to create a diagram. We chose to display the statement of the problem on the screen, as the other environments do, but we more largely exploited the possibilities of the graphical interface to reinforce the link between text and diagram (section 4). At last, we provided the learner with contextual assistance to support self-correcting.

Besides these generic helps, some systems also propose specific help messages by comparing the learner's diagram with a solution. DesignFirst-ITS automatically generates this solution, but the constraints that result from this approach (small diagrams, short problem statement, very simple sentences, no implicit elements) do not seem compatible with an open environment. Collect-UML uses a solution provided by the teacher, and so can handle more complex problems, but its constraint-based approach also restricts the learner's creativity. In particular, the names of classes, attributes and methods are imposed, and the problem statement cannot contain implicit elements. Our third objective was to overcome these limits by exploring a new approach, also based on diagram comparison, but without a predefined list of constraints or bugs catalogue. Indeed, we consider that the differences between the learner diagram and the expert diagram are not necessarily mistakes; they sometimes express different modeling choices. The analysis of the differences between diagrams can be performed separately from the interpretation of these differences in a pedagogical objective. We adopted a modular approach, by separately developing a tool that compares the diagrams and enumerates their differences (section 5) and a tool that interprets these differences to provide pedagogical feedbacks (section 6). We make the assumption that this architecture should enable a diagnostic more robust and more relevant than the previous approaches.

Base of Exercises

At the beginning of the project, UML exercises have been collected in order to analyze them and characterize the difficulties encountered by learners. This base includes about thirty exercises. It has been used us to develop Diagram and to carry out the experiments in ecological context. Most of the exercises have been provided by a teacher of the university of Le Mans (France) who took part in the project. He uses these exercises in his OOM courses, with students of second year in computer science. Some exercises found in books or on the Web have also been included. The exercises of the base relate to various fields, the concepts and the vocabulary employed are very diverse. Their size varies from a few sentences to one page. The diagrams comprise four to twenty-seven classes.

This base has been analysed to produce a classification of the exercises according to their difficulty. Several criteria were retained: the length of the text, the simplicity of the vocabulary, the presence of implicit or superfluous information, the presence of clues, the number of information to be modelled. A combination of these criteria provided a scale of difficulty going from one (for "very easy") to five (for "very difficult"). A similar analysis was made to evaluate the degree of difficulty of the diagrams. These two classifications were then used to plan the experiments and propose exercises of increasing complexity.

Example

The functionalities of Diagram are illustrated throughout this paper with an exercise of the base, called "Pen and felt-pen". Figure 1 presents a diagram that will be used thereafter as the expert diagram for this exercise.

"A pen and felt-pen are two concepts with common attributes: color, brand name, etc. A felt-pen has a top. Both pen and felt-pen have a body with some properties. Pen and felt-pen are used by a person and belong to a person. There is a specific felt-pen that is an eraser felt-pen." According to our classification, this exercise is considered as easy (level 2) regarding the statement but difficult (level 4) regarding the diagram because it requires many different UML notions. The statement is short, uses a simple vocabulary and familiar concepts. However, the diagram is not so simple for novices. First, one class is implicit: the word "pencil" does not appear in the text. Some students do not represent this class, but duplicate all the attributes and relations that refer to it. Another difficulty is the presence of two distinct relations between the classes "pencil" and "anybody", which is not common in simple exercises. In addition, this diagram comprises four types of relations: association, composition, aggregation and inheritance. Many novice students cannot make the difference between these relations and often confuse them. At last, classical errors can appear in this exercise, for example an attribute used instead of a class, wrong orientation of relations, or incorrect multiplicities.

This exercise is a classical one, nevertheless it could not be solved with environments like Collect-UML or DesignFirst-ITS, because the concept "pencil" is implicit in the text, so that the corresponding class could not be created in these environments. Figure 2 presents a student diagram that contains typical errors. It will be used throughout the article as an example of learner diagram. In this example, the learner has noticed the presence of an implicit class, that he/she named "writing tool". But he/she duplicated the composition "have" and applied it both to "pen" and "felt-pen", instead of applying it only to "writing tool". He/she represented the concept of "person" as an attribute, instead of a class. The relations between a person and a pencil are thus missing. The direction of certain relations is reversed: the inheritance between "felt-pen" and "eraser", the composition between "felt-pen" and "a top". Lastly, there are some small errors, like the attribute "color, mark, etc" or the insertion of an attribute "properties" into the "body" class.

THE INTERACTION IN DIAGRAM

Introducing some kind of methodological guidance in the environment can contribute to mitigate the lack of formal method for building a class diagram. The starting point is the method used by the teacher who participated in the design of Diagram. He recommends to its students to follow a three steps method: (1) carefully reading the statement, (2) working out the diagram, (3) reading again the statement and checking the correctness of the diagram. This method is simple and consistent with the recommendations that can be found in books about modeling. It has been transposed into Diagram and enriched it with graphic tools. A fourth stage has been added (which will be developed in section 6), in which the system evaluates the diagram and produces feedbacks to help the student to correct it [START_REF] Alonso | Conception de l'interaction dans un EIAH pour la modélisation orientée objet[END_REF].

During the reading step, the student discovers the problem statement. Some students use a pencil or a highlighter to mark the important words. To offer the same functionality in the computer environment, Diagram integrates the possibility of underlining words of the statement. A constraint is imposed before the student can start the modeling step: he/she must have underlined the important concepts of the statement (defined by the teacher when he/she creates the exercise). The second step consists in creating the class diagram (figure 3). Diagram offers two different ways of creating an UML element (class, attribute or relationship): either from a phrase of the text (« assisted mode ») or freely (« free mode »). In the former case, the element and the expression are displayed in the same color, in order to facilitate visual control and reinforce the link between the statement and the diagram. In the free mode, the learner only selects the kind of element that he/she wants to create. The element is displayed in black and the learner chooses its name. This mode enables to create elements that are not explicitly mentioned in the text, and elements without name, like inheritance relationships. Any free element or free expression in the text can later be linked to another expression, and will take on the same color as the expression to which it is linked. The student remains free to modify the name of any element throughout the session. The free mode is an original concept in Diagram that gives a strong expressive power to the interface and allows the learner to be more creative than in the other environments.

During the last step, the student must read again the text problem and compare it to his/her class diagram in order to check the diagram correctness and completeness. At the beginning of this step, the diagram is hidden and the text alone is displayed in black and white on the interface. When the student moves the mouse over an expression linked to an element of the diagram, this expression recovers its color and at the same time, the corre-sponding element in the diagram reappears on the interface. The learner can then turn back to the modelling step, if he/she wants to modify his diagram, or continue and validate the diagram.

THE DIAGNOSTIC METHOD

The assistance provided during the interaction described above is generic: it does not take into account the correctness of the diagram. To produce specific feedbacks, based on the analysis of the individual productions of the student, it is necessary to compare the diagram with a solution, as Collect-UML and DesignFirst-ITS do [START_REF] Baghaei | A collaborative constraint-based intelligent system for learning object-oriented analysis and design using UML[END_REF][START_REF] Moritz | Generating and Evaluating Object-Oriented Designs in an Intelligent Tutoring System[END_REF]. However, the diagnostic methods of these two environments impose strong restrictions on the statements and the diagrams. Another approach, which seemed more compatible with the open character of Diagram, has been explored here. It consists in finding all the differences existing between the two diagrams, by using a tool that compares the diagrams. These differences can then be used to produce feedbacks.

Thus, a specific matching method that takes two class diagrams as inputs and matches them [START_REF] Auxepaules | Analyse des diagrammes de l'apprenant dans un EIAH de la modélisation orientée objet[END_REF] has been defined and implemented. The principles of the algorithm rely on the object-oriented metamodel (OMG MOF, 2010) and on graph matching methods and algorithms [START_REF] Sorlin | A Generic Graph Distance Measure Based on Multivalent Matchings[END_REF]. It proceeds in three steps. First, the diagrams are schematized in characteristic structural patterns. Then, these structures are compared by using similarity functions, and similarity scores are computed for each couple of structures. Finally, the resulting matches are labelled with the differences that they express. This method is detailed in the following sections.

Characteristic Structural Patterns

Characteristic structures, called patterns, are introduced. They correspond to different granularity levels in class diagrams. The simple patterns represent the basic elements of the object-oriented meta-model, they are organized and structured into complex patterns. The patterns have been introduced because of their interesting structural and semantic properties that can be exploited by the matching algorithm in order to match diagram parts at a higher granularity level.

The main patterns for class diagrams are represented on figure 4. The simple patterns of class diagrams are those defined by the Object Management Group (OMG MOF, 2010). The classifiers include classes, interfaces and objects. The relationships include associations (simple associations, aggregations and compositions), generalizations and dependencies. The features include properties (attributes and association ends) and operations. The complex patterns, respectively Association sequence and Generalization hierarchy, are built from several simple patterns and a relationship type, respectively association and generalization.

Comparison and Matching

In order to automate comparison and matching, class diagrams are considered as graphs, where the vertices are classifiers and the edges are relationships. In this way, the problem of diagram matching can be seen as a variant of graph matching, with graphs characterized by specific features. [START_REF] Sorlin | A Generic Graph Distance Measure Based on Multivalent Matchings[END_REF] propose a generic similarity measure for graph matching. This measure is parameterized by similarity functions that express domain dependent similarity knowledge and constraints. The matches are either univalent or multivalent. A match is multivalent when a single vertex in one graph is matched with a set of vertices in the other graph.

The diagnostic algorithm in Diagram relies on the same principles. Similarity functions compute a score for each couple of patterns to be compared. These functions are either general or specific to pattern types. They weight and normalize qualitative and quantitative criteria.

The similarity score is composed of two sub-scores. The simple score weights the criteria that do not depend on the other parts of the diagram, as for example name, visibility, aggregation kind, abstraction, nature, and so on. The complex score weights the scores of the neighbours (parents, children, siblings and linked patterns).

The diagram matching algorithm proceeds top-down. Complex patterns, then simple ones, are compared and the pairs are ordered by decreasing score. A greedy algorithm tries to match complex patterns in an univalent way: if this is unsuccessful, multivalent matches are performed. Once the complex patterns have been matched, univalent or multivalent matches are performed in the same way for each simple pattern of a complex one.

Unlike graph vertices, the basic elements in a diagram (classes, attributes, relationships) are usually given a name. The similarity functions must take this name into account. But, as these names refer to real world objects or concepts, the student may use many synonyms instead of the teacher's names. Moreover, students often mistype words, or make spelling errors. This is why a specific string matcher has been designed and included in the system. It computes a score for each couple of names and selects the pair that matches best. Beforehand, names are filtered by case, gender, number and special characters.

Differences Between the Diagrams

The matching step, described above, produces pairs of fully or partially matched patterns. Then, partial matches are labelled with the kind of difference that they represent. These differences express gaps between structures or characteristics of the two diagrams. They are classified in eight categories:

• Omission of an element: an element of the reference diagram has been omitted by the learner. • Addition of an element: the learner has added an element that does not appear in the reference diagram. In students' diagrams, some differences often go together. For example, a "class omission" usually implies a "relation omission" or a "relation transfer", because the relations supported by the missing class are themselves moved or omitted. When this situation happens, it is better to produce a single feedback covering the group of differences than to produce several feedbacks. Therefore, a set of fifteen compound differences, which can be treated as a whole, has been defined. A compound difference is made of a main difference and a set of secondary differences. For example, the compound difference "relationship duplication and transfer" is composed of a main difference "relationship duplication" and one or several secondary differences amongst "relationship transfer", "direction reversion", "wrong type of relationship" and "wrong multiplicity".

Once all the single differences have been listed in a student's diagram, the compound differences can be searched for. The compound differences have priority on simple differences and lead to specific feedback during the interaction. The simple differences that occur separately will produce the usual feedback.

Example

Table 1 presents the output of the diagnostic algorithm (i.e. the differences between the diagrams) on the example "pen and felt-pen". Among all the differences, three subsets are recognized as compound differences (A, B and C) and the others are simple differences (D, E, F and G).

Implementation and evaluation

The diagnostic algorithm is implemented in Java. UML2 (an Eclipse Tools sub-project) of Eclipse modeling project has been used to represent the diagrams and realize the syntactic validation. An evaluation has been conducted with students' diagrams in order to assess the robustness and speed of the diagnostic method [START_REF] Auxepaules | An Evaluation of Diagnosis in a Learning Environment for Object-Oriented Modeling[END_REF]. The results show that the diagnostic quality is quite good for simple and medium problems, and remains correct on complex problems. On the whole test base (n=82), 90% of the matches are relevant at 85% or more. The calculus time depends on the diagram's size: it varies between 0.2 and 4 seconds (on average: 2 seconds), in function of the diagram complexity. This is fast enough to provide pedagogical feedbacks online.

Table 1

Compound and simple differences

Simple differences Compound differences

Wrong representation of class "Person" by an attribute "person" of class "Writing tool"

(A) Wrong representation of a class and omission of the related elements Omission of relationship "belongs to" between classes "Person" and "Pencil" Omission of relationship "uses" between classes "Person" et "Pencil"

Duplication of relationship "have" between classes "Pencil" et "Body"

(B) Duplication and transfer of a relationship

Transfer of relationship "have" from "Pencil" to "Pen" Transfer of relationship "have" from "Pencil" to "Felt-pen"

Reversion of the direction of the relationship "has" between "Felt-pen" and "Top"

(C) Wrong representation of a relationship and direction reversion

Wrong type of relationship "has" between "Felt-pen" and "Top"

Wrong multiplicity of "has" for "Felt-pen" Wrong multiplicity of "has" for "Top" (D) Reversion of the direction of inheritance between "Felt" and "Felt-pen" (E) Representation of the abstract class "Pencil" by an ordinary class (F) Merging of attributes "color" et "brand name"

(G) Addition of an attribute "properties" into class "Body"

PEDAGOGICAL FEEDBACKS

The output of the diagnostic algorithm is a flat list of differences between the student's diagram and the reference diagram. However, these differences can have quite different meanings, from a pedagogical point of view. Some differences only express a minor variation of the solution while others represent a great mistake. The environment must provide a different response in each situation and the formulation of the feedback messages must vary, according to the degree of certainty about the presence of an error.

Feedbacks formulation

The classification proposed by [START_REF] Lemeunier | L'intentionnalité communicative dans le dialogue hommemachine en langue naturelle[END_REF] identifies three main forms of dialogic intervention: notify, question, and propose. These three categories have been used to design the pedagogical feedbacks in Diagram, in a graded manner. "Notify" draws the student's attention to some part of the diagram, or to the way he has modeled a particular concept. This modality is used for differences that are probably due to a slight variation in the students' diagram. "Question" consists in asking the learner about the diagram's properties. The questions are on a binary mode (the answer is "yes" or "no") and encourage the learner to mentally check whether the diagram satisfies a given property. "Propose", the most direct modality, consists in suggesting how to correct the diagram. This kind of help is provided only when the presence of an error is near-certain.

For each type of difference and each form of intervention, a sentence template can be filled with the name of the elements. For example, the template associated with the "relationship omission" difference and the "notify" intervention is "A relationship is missing between classes C1 and C2". The variables C1 and C2 are simply replaced with the effective names of the classes when the message is displayed.

The appropriate form of intervention only depends on the type of the difference. For example, adding or forgiving an element is not necessarily an error. In this case, the environment only displays the "notify" and "question" messages. By contrast, when the direction of a relationship has been reversed, the "propose" message can be displayed, because the presence of an error is very likely.

During the interaction, feedback messages are graduated from the more general (notify) to the more precise (propose). For each difference, the most general message is displayed first, and the learner can ask for a more precise message if he/she wants to.

Example

For each of the seven differences mentioned in table 1, a feedback message is produced following the modalities described in the previous paragraph. Three examples are given below.

The first compound difference means that the student has represented a class by an attribute, and has omitted the associated relationships. The feedback messages focus on the wrong representation of "person" but do not mention the absence of the relationships, because they relate to a class that is missing. Notify : You have represented person as an attribute of the class Writing tool. Question : Can the attribute person have properties or a behaviour ? Propose : If person has properties or a behaviour, it should be a class

The compound difference C is formed of a type error and an inversion of direction (the errors about multiplicities are considered as minor errors, compared to these errors, and are masked). The feedback message focuses on the inversion.

Notify : You say that a top is composed of felt-pen. Question : Is a top composed of felt-pen ? Propose : I would rather say that felt-pen is composed of a top.

The simple difference G indicates that the student has added an attribute "properties" into the class "body". The feedback is composed of two sentences. As the insertion of an attribute is not necessarily an error, the "propose" sentence is absent.

Notify : Your class body has an attribute properties. Question : Is properties an attribute of body ?

EXPERIMENTS

The experiments of the first versions of Diagram focussed on the contextual helps [START_REF] Alonso | A Learning Environment for Object-Oriented Modeling, Supporting Metacognitive Regulations[END_REF], and the diagnostic module has been evaluated apart [START_REF] Auxepaules | An Evaluation of Diagnosis in a Learning Environment for Object-Oriented Modeling[END_REF]. This article only presents the experiment carried out after the integration of the diagnostic module, which focussed on the relevance of the diagnostic performed in real situations and on the effects of the feedback messages on the students' behaviour.

Sessions

The experiment involved eighteen students in second year of University Diploma for Science and Techniques (DEUST) working with Diagram during four streams of three-hour practice session of UML modeling course. The experiment was conducted in an ecological context, i.e. during the normal schedule of the class. Prior to the session, the students were warned that Diagram's feedbacks are related to one particular solution and that they could ignore some messages if they were convinced that their own solution was a correct alternative. The teacher advised them to read the messages and decide whether a modification was necessary or not. During a session, each student practiced between three and five exercises. For each session, actions on the interface have been recorded.

Results and discussion

All the exercises of the second and the third sessions have been analysed. The first session has not been analyzed because the students were still discovering Diagram. For each exercise, the number of diagnostic calls, the total number of messages and the number of messages read by the learner have been calculated. We consider that a message is read if the student consults at least the first modality of the message (usually, the "notify" feedback).

All in all, 86 exercises were analysed, for a total of 306 calls of the diagnostic, which means that the diagnostic was called 3.56 times per exercise and per student. It results in 1 924 messages, 836 of which (43.45%) have been read. Some students used to read only one or two messages, immediately modify the diagram and call the diagnostic again, which explains this low rate. In some cases, however, the students did not read the messages because they were too many, which probably discouraged them. When the number of messages in a whole session is less than 50, the reading rate is 52.74% whereas if it goes past 50, the rate drops to 31.25%. To address this problem, a degree of priority could be assigned to each message so that, in a first step, only the most important messages would be displayed.

The same message can appear several times during a session (at the maximum, as many times as the diagnostic is called), so that among the 836 read messages, only 565 are distinct. Among these 565 messages, it can be observed, in 11.6% of the cases, that the diagnostic module did not properly match the two diagrams. As a result, the feedback message is inappropriate. This occurs either when the student's diagram is very different from the reference diagram, both in structure and in class/relation names, or when two classes (or more) have very similar names. The diagnostic algorithm relies on structure and names to compare the diagrams, so that its performances deteriorate in these situations, as it was already noticed in the pre-tests of the diagnostic tool [START_REF] Auxepaules | A Diagnosis Method that Matches Class Diagrams in a Learning Environment for Object-Oriented Modeling[END_REF]. However, the disturbance remained acceptable because the resulting messages were clearly irrelevant and the students ignored them most of the time.

The students' reactions after the relevant messages can be classified into three categories:

• Correction: the student modifies the diagram in accordance with the message (49.7%). • Modification: the student modifies the diagram in relation with the message but some difference with the reference diagram remains (3.8%). • No Effect: the student does not take the message into account and does not modify the diagram in relation with the message (46.5%).

The "modification" case is rare, which suggests that the messages are clear: when the students modify their diagram to take into account a piece of advice, this advice is properly understood (49.7%). However, the rate of messages that do not cause any reaction is fairly high (46.49%). Several hypotheses can explain this result. As students were told they could ignore some messages, we can assume that a lot of them did. Moreover, several calls of the diagnostic occurred a few minutes before the end of the sessions. In these cases, even if the students could read the messages, they had not enough time to make all the changes. It can also be assumed that a few messages have not been understood at all by students.

In order to determine what kinds of messages were concerned, the correction rate was analysed more precisely according to the type of difference. Table 2 indicates the percentage of each difference among the messages, and the correction rate for each difference. The results show that Misrepresentation and Wrong Multiplicity are the most frequent differences (respectively 28.46% and 27.65%). The corresponding messages are easy to understand and quite precise about the modification to perform. The correction rate shows that, in half of the cases, the students decided to follow the advice. Messages related to an Omission difference are most of the time suggestive and easy to follow, especially when the missing concept is present in the problem statement: this explains the quite good correction rate. By contrast, the correction rate corresponding to Addition difference is low: as alternative solutions often include additional items, learners usually chose to keep the extra element. The Duplication and Transfer compound difference often happens when elements of a motherclass are duplicated in the children classes. The high correction rate suggests that the messages are efficient and help the student to understand the process of generalization, an important concept of object-oriented modeling. At last, the messages related to Duplication and Merge differences seem to be too general and could be improved.

It sometimes happens that, after having read a message, a student performs several corrections on neighboring objects, as if he/she was checking all similar objects in the diagram. This suggests that the messages efficiently solicit the checking metacognitive function.

Overall, the time spent on Diagram after the first call of the diagnostic tool represents about one third of the total time. The students devoted much time checking and improving their diagrams, by using the feedback messag-es. At the end of a session, the diagrams appeared more complete and more accurate than if students had not benefited from the feedback messages.

CONCLUSION

We have presented a new approach for the design of a learning environment dedicated to class diagrams. The main contribution of this work is to overcome some limits of the existing systems. Diagram is an open environment, which does not impose constraints or restrictions on the problem statement, and allows the learner to express his/her creativity through the graphical interface. As a result, the range and the complexity of the problems that can be solved with Diagram are bigger. Moreover, this flexibility is compatible with accurate feedback messages, as in sophisticated tutoring systems. These improvements were made possible by the integration of an original diagnostic algorithm -a diagram matcher -that produces the list of the differences between the learner's diagram and the solution diagram. Several experiments in ecological context have shown that the interaction in Diagram encourages the learner's regulation activities, by supporting checking and self-correcting.

We have focussed on the first stages of UML learning, and that imposes limits on our work. The complete object-oriented modelling process relies on different types of diagrams, not only the class diagram. A first perspective is to extend this framework to other kinds of UML diagrams (object diagrams, component diagrams, and so on), that are required for more advanced students. The features of Diagram, like the task organization, the graphic tools and the help messages, could be adapted to that end.

The diagnostic module works with only one solution and is not able to recognize a correct alternative solution. To overcome this limit, it would be necessary to adapt the algorithm so that it could take into account different solutions. But this would require describing the relations between diagrams having common elements and then to merge the partial matching results, which is currently regarded as a very complex problem.

Lastly, a limit of the assistance is due to the fact that the feedbacks are produced in the same way, each time the diagnostic is performed. Another perspective is to memorize the successive diagnostic, in order to avoid repeating several times the same message, or, on the contrary, to insist if the learner repeats the same mistake for a long time.

Figure 1 .

 1 Figure 1. Class diagram for the "pelt and felt-pen" problem.

Figure 2 .

 2 Figure 2. A student's class diagram.

Figure 3 .

 3 Figure 3. The interface during the modelling step.

Figure 4 .

 4 Figure 4. Characteristic structural patterns in class diagrams.

•

  Transfer of an element: an element has been transferred to another part of the diagram. For example, a relationship between two classes A and B in the reference diagram is shifted between classes A and C. • Duplication of an element: an element of the reference diagram is replaced by several elements of the same type in the learner's diagram. • Merging elements: several elements of the same type are substituted by a single element. • Misrepresentation: an element of the reference diagram is changed to another one, of a different type. For example, a class is replaced by an attribute or a composition is replaced by an association. • Reversion of the direction of a relationship: an oriented relationship (inheritance, aggregation or composition) has been reversed by the learner. • Wrong multiplicity: multiplicities of a relationship in the learner's diagram are different from those in the reference diagram.

Table 2

 2 Percentages Among Read Messages and Correction Rates

	Difference	% among read messages	Correction rate
	Misrepresentation	28.46	51.41 %
	Wrong multiplicity	27.65	50.72 %
	Omission	15.83	67.09 %
	Addition	10.82	24.07 %
	Duplication	8.42	21.43 %
	Duplication and transfer	4.61	86.96 %
	(compound difference)
	Merging	2.81	21.43 %
	Reversion	1.20	100.00 %
	Transfer	0.20	100.00 %
	Total	100.00