Keywords: Audio-psycho-phonology, Tomatis, listening rehabilitation, auditory integration

Objectives

To determine the quantitative effects of an Tomatis auditory stimulation method using of clinical measures of hearing and cognitive P300 evoked potentials.

Method

Seventeen patients were included in this study. Nine patients received 100 non-consecutive hours of auditory stimulation, in the form of a personalized program. Eight control subjects did not receive any auditory stimulation. The patients were subjected to a listening test and cognitive auditory MMN (Mismatch Negativity) and P300 evoked potentials test before and after stimulation. The control group was subjected to two distant listening tests (without any interim auditory stimulation). The average time between the two tests was quite similar to that of the patient group. The clinical effects of this form of auditory stimulation were ascertained on the basis of a multiple-choice questionnaire.

Results

The listening test shows a significant improvement in the reduction in the difference between bone conduction and air conduction in the left ear. The amplitude of the MMN was reduced during the second session -which goes hand in hand with increased latency -and that the reaction times were shorter. We observe a significant decrease in N1/P2 amplitude at the P300 evoked potential. It was also found that a clear and moderate clinical improvement in patients.

Conclusion

The electrophysiological and hearing measures have been improved significantly in the subjects who received auditory stimulation. To eliminate possible sampling fluctuations or the effect of habituation to the test, they will need to be confirmed on a wider scale. Clinical improvements in patients who received auditory stimulation were observed. However, the correlation between these clinical improvements and the variations in the measuring tests were not examined. Progressive monitoring of the effects of this rehabilitation on the basis of a validated psychometric scale ought to be considered.

Introduction

"Musical training is a more potent instrument than any other, because rhythm and harmony find their way into the inward places of the soul. It enriches the soul, gives it grace and illuminates it. " Plato Alfred Tomatis (1945), ear nose and throat specialist (ENT), dedicated most of his professional life to studying the process that links listening to language. During the 1950s, he presented 3 laws to the French Academy of Sciences.

1) The voice contains as overtones only those frequencies that the ear can hear.

2) When giving the ear the chance to hear frequencies that were previously not or not well perceived correctly again, they instantly and unconsciously reappear in the voice.

3) When repeated over a certain period of time, acoustic stimulation leads to a final change of hearing, and consequently the phonation.

So Audio-Phono-Psychology was born: "Listening is to hearing what sight is to seeing." Accordingly, hearing would be associated with a psychological dimension and not purely with physiological criteria pertaining to sound transmission [START_REF] Mouchnino | La Méthode Tomatis[END_REF]. For Tomatis, "The human ear is made, tailored, designed to hear and listen. The distortions that settle in, the blockages that are created, the deficiencies that appear are only there to stifle motivation, to prevent exchange, to disrupt dialogue, to disturb communication.

Those who never experienced, enjoyed, true listening cannot appreciate what they are losing out on by holding on to their distortions. Listening is life." [START_REF] Mouchnino | La Méthode Tomatis[END_REF][START_REF] Auriol | Considérations sur le test d'écoute[END_REF] Tomatis proposed two ideal listening curves which were based on listening tests of talented musicians, like Enrico Caruso. These bone and air conduction curves correspond to the audibility threshold curve, known as Wegel's "lemon-shaped curve" (figure 1A). The ideal listening Tomatis curves are the inverted Wegel's curves. They reflect maximum sensitivity in voice frequencies between 1000 and 3000 Hz. They follow an ascending curve, from the low to the medium frequencies, and slightly drop again in the high frequencies. The perception threshold is a reference for the method.

Tomatis developed a specific auditory test so-called listening Tomatis test (LTT). Classical audiogram is an examination that pertains to the field of ENT, and which is performed using an audiometer with a standardized calibration (figure 1B). In contrast, LTT is similar to an audiogram but uses the inversed Wegel curve with an adjustment of the minima to end up with linearized curves (figure 1C). LTT was developed with the help of an audiometer, calibrated in accordance with the standards that Tomatis entrusted to the company Inter-acoustics (table I). According to Tomatis, the LTT is more suitable to interpret a patient's audio-psycho-phonology profile and progress under auditory stimulation than an audiogram (3). The table I shows an osseous perception that was deliberately attenuated while the standard audiogram was performed because the audiometer is calibrated differently than the one used for LTT. On the assumption that bone conduction perception is an important factor, the listening test, devoid of attenuation, does indeed seem more relevant.

In the context of our research elaborated hereafter, it seemed logical to record the cognitive evoked potentials, an objective technique to collect non-invasively neurophysiological data during auditory process, and therfore to assess the effects on the brain of a method designed to enhance subjects 'attentional or sensorimotor skills. A number of studies on musical training (4-6), phonological training [START_REF] Tremblay | Central auditory system plasticity: generalization to novel stimuli following listening training[END_REF][START_REF] Tremblay | Auditory training induces asymmetrical changes in cortical neural activity[END_REF][START_REF] Alain | Changes in sensory evoked responses coincide with rapid improvement in speech identification performance[END_REF] or reading/writing training [START_REF] Jucla | Remediation Effects on N170 and P300 in Children with Developmental Dyslexia[END_REF][START_REF] Alvarenga K De | P300 auditory cognitive evoked potential as an indicator of therapeutical evolution in students with developmental dyslexia[END_REF] have already been conducted in the past. They show changes in the components of these auditory potentials that vary with the circumstances.

Cognitive auditory evoked potentials (aCEP) are constituted of a succession of electrical brain waves that occur after 50 ms, associated with the progressive encoding of stimulations, which are highly dependent on attention. The main component is known as the P300 (or P3) wave because of its positive phase and its delay of about 300 ms after stimulation, irrespective of sensory modality. It is preceded by the N100 (or N1), P200 (or P2) and N200 (or N2) waves. To assess the attentional aspect, these waves are recorded on the basis of protocols that require the subject's active attention. P300 is obtained when an unexpected stimulus occurs (oddball paradigm). The amplitude of the P300 is all the greater as the stimulus is not expected. A subject could also be asked to passively listen to the auditory stimulations, which would give rise to a non-concordance wave (MMN for Mismatch Negativity) which occurs between 100 and 200 ms and shows that something new has been detected in the sound environment.

Tomatis's auditory stimulation method (TAS) is a personalized program, tailored to the subject's listening test. TAS generally includes music, filtered to a greater or lesser extent (Mozart, Gregorian chant), the mother's voice filtered at 6000 Hz and the patient's own voice; these sounds are processed in such a way that the high and low frequencies are continuously and irregularly altered, yet. The differences between sound are unpredictable and repeated and catch the subject's attention by surprise. The high frequencies are favored because they trigger the hair (sensory) cells of Corti's organ better than the low frequencies. This means that particular cortical reception and integration zones are stimulated in an unaccustomed way. Until his death in 2001, Tomatis continued to research, experiment and publish to explain that training the listening function aids social interaction, learning, language skills, discourse, voice, singing, posture, coordination, rhythm [START_REF] Mouchnino | La Méthode Tomatis[END_REF][START_REF] Flehmig | Expertise de fond sur la méthode Tomatis[END_REF][START_REF] Vervoort | The Improvement of Severe Psychomotor and Neurological Dysfunctions Treated with the Tomatis Audio-Psycho-Phonology Method Measured with EEG Brain Map and Auditory Evoked Potentials[END_REF]. Nevetheless, the reviews of the available literature are contradictory as to the significance of these Tomatis effects [START_REF] Gerritsen | A review of research done on Tomatis auditory stimulation[END_REF][START_REF] Sinha | Auditory integration training and other sound therapies for autism spectrum disorders (ASD)[END_REF].

In this paper, we aim to determine the quantitative effects of Tomatis, auditory stimulation method using clinical and electrophysiological measures, as listening tests, auditory cognitive evoked potentials.

Our hypothesis is that Tomatis method of auditory stimulation has a marked positive quantitative impact on the objective measures of hearing. These variations are accompanied by psycho-cognitivemotor effects. This would have the consequences such as a) decreasing in the difference between right and left air conduction to bone conduction, b) decreasing in the difference between air conduction and the ideal right curve, c) improvement in the components of cognitive evoked potentials.

Patients and Methods

A) Study design and participants

The study ran from June 2016 until September 2017.

In a first phase, 17 subjects have been included in this study between June 2016 and September 2016 on a completely voluntary basis. Two groups were constituted. The subjects of patient group (n = 9, 5 males, 4 females) presented various problems whether of a physical, psychological or pedagogical nature (table 2). The mean age of our population is 31 years, consisting of 4 adults and 5 children or adolescents. The average time span between the two examinations analyzed (before and after the therapy) was 11.4 months. The control group was constituted by 8 subjects (4 males and 4 females) were on average 28.3 years of age (median: 33.5 years; from 7 to 39 years). All the subjects benefited from 2 LTT: at the beginning and at the end of the study. The patient group benefited of TASM for 5 weeks corresponding to 100 hours of therapy on average. For practical and logistical reasons in this feasibility study, aPEC were recorded in the patient group but not in the control one. Auditory cognitive evoked potentials were performed before and after the therapy.

B) Listening Tomatis Test

LTT was performed on a Interacoustics system (Atlantis Centre in Sint-Truiden, Belgium, model AD226, Tomatis calibration. The LTT was performed in patients before each new week of therapy so as to optimally tailor the musical program and sound modulation to the test trends. The "ideal curve" values of Tomatis suggested was used as reference. (table 1). In LTT, audibility threshold (in dB) was measured for BC and AC with the following frequencies: 125, 250, 500, 750, 1000, 1500, 2000, 3000, 4000, 6000 and 8000 Hz. The values recorded were analyzed via automatic programming in Excel, for listening to the right and to the left side and the results synthetizing data were generated automatically.. The average threshold for all the frequencies was then calculated for BC and AC. Analyzed parameters were: 1) difference between averaged measured threshold for BC and the ideal curve, in absolute values; 2) difference between averaged measured threshold for AC and the ideal curve, in absolute values; 3) averaged BC threshold /averaged AC threshold ratio, in absolute values. In controls, LTT a second test was performed 6 months after the first test in patients the second LTT has been performed at the end of TAS.

C) Tomatis's auditory stimulation

After the first test TAS was performed in patients for 5 non-consecutive weeks. Each patient received 100 hours of sound stimulation, at a rate of 20 hours per week. Listening sessions were performed using the so-called "Tomatis Electronic Ear": More precisely, the patients were given 5 weeks of therapy: 2 consecutive weeks initially, followed by 3 non-consecutive weeks with a 6 to 8 weeks break in between. One week of therapy consisted of 5 consecutive days. One day of therapy was divided into 2 sessions of 2 hours' sound each, one in the morning and one in the afternoon. During the listening sessions, patients were encouraged to make themselves comfortable, to draw or play (jigsaws, cognitive games, games of skill or logic games). They were advised not to read. At the end of the therapy, they were asked to read aloud for 20/30 minutes per session (active phase).

D) Auditory cognitive evoked potentials:

Recordings were performed by means of a Neuro-Mep (Neurosoft) device for three derivations: one frontal and one central median (Fz and Cz), referenced in the linked mastoids, and one vertical oculogram above and under the eye. The bandwidth ranged between 0.1 and 35 Hz and the sampling frequency was 1000 Hz. The artefact rejection threshold was 100 µV. Acquisition times were 500 ms, made up of 50 ms of pre-stimulus for the MMN protocol and 1000 ms with 100 ms of pre-stimulus for the P300 protocol. Recording was stopped when at least 60 responses to deviant stimulations and 50 responses to targeted stimulations had been obtained. The duration of each ranged between 5 and 8 min.

Stimulation to both ears was ensured by means of headphones (TDH 39 headset) with alternating polarity. For the MMN protocol, a total of 600 stimulations at a frequency of 1000 Hz, a rate of 2 Hz and an intensity of 70 dB nHL were given. The standard stimulations consisted of tone bursts of 75 ms while the deviant stimulations lasted 25 ms. The ratio was 1 deviant to 8 standards in a random order. Subjects were advised to think of whatever they liked, without worrying about the sounds, and to keep as still as possible. Some ten standard stimulations were given prior to recording.

In the odd ball P300 protocol 250 tone bursts of 30 ms and 80 dB nHL were given at random intervals ranging between 0.9 and 1.1 s, divided between targeted and non-targeted stimulations. The targeted stimulations were random with a probability of 0.2 and a frequency of 2000 Hz. The non-targeted stimulations had a frequency of 1000 Hz. Subjects were asked to press a button as quickly as possible any time they heard a high-pitched sound and to try not to make any mistakes. Responses that came after 950 ms were rejected. Subjects were given a short training session before recording began.

For the MMN protocol, we measured the latency of waves N1 and P2 on the curves of response to the standard stimulations. The first were the most negative spike before 120 ms and the second the most positive spike between 100 and 170 ms. The N1-P2 amplitude was the difference spike to spike. The non-concordance wave (mismatch negativity) was measured on the differential curve: Its latency was the most negative spike between 120 and 230 ms and its amplitude the difference between the start of the wave and its peak. For the P300 protocol, the N1 and P2 waves were measured on the curves of response to the non-targeted stimulations, for the 80-120 ms and 120-210 ms windows. The N2 and P3 waves were measured on the curves of response to the targeted stimulations, for the 180-240 ms and 250-450 ms windows. The N1/P2 and N2/P3 amplitudes were the spike-to-spike differences of these waves.

Statistical analysis

Recording and the statistical analysis of the evoked potentials was performed by Dr Jacques Grapperon, neurologist. The statistical analysis was performed by the three-way variance analysis for repeated measures. The inter-subject variance came from 9 subjects while the intra-subject variance came from the derivation factor (frontal and central) and from the session factor (before and after the audio-psycho-phonology training sessions). In terms of response time, the percentage of correct responses and the number of errors, the same variance analysis was performed, but without taking the derivation factor into account. To check the significance of the variations in perception of the listening tests, the variances were checked against the variances obtained with the Fisher-Snedecor test. In the case of unequal variances, the bidirectional Mann-Whitney test was used. All the Excel files were compiled by an engineer, who also conducted the macro-based automated analysis.

Results.

As shown in the table 4, the main result is a reduction of mean left BC/AC value (significant, p < 0.05), on LTT , in patients after TAS (Table 4). A slight and not significant reduction can be observed also on the right BC/CA value. In controls, no significant variation in the different values between test 1 and test 2 was observed.

The results for auditory cognitive evoked potentials are presented in figure 2 and table 4. One can observe i) a an increase of of MMN latency after the TAS treatment (F 1/24 = 3.51; p = 0.030) , and ii) a decrease in amplitude of N1/P2 after the TAS treatment (F 1/24 = 9.88; p = 0.004). The amplitude of MMN reduced after the TAS treatment, but this effect is not statistically significant..

Discussion

A) Listening test

In 2009, Gerritsen conducted a review of the literature on the impact of auditory stimulation according to the method of Dr Tomatis [START_REF] Gerritsen | A review of research done on Tomatis auditory stimulation[END_REF]. The analysis of the conclusions of the studies that were discussed in this review show a clear benefit from audio-phono-psychology in learning disorders, pervasive developmental disorders, the learning of foreign languages, pronunciation, vocal production, the length of labour and childbirth, the Apgar score, stammers, mental retardation, anxiety syndrome, depressive syndrome, behavioral disorders associated with a psychotic personality.

During 2011, the Cochrane Collaboration conducted a review of the literature on the technique of auditory stimulation, which it refers to as "auditory integration" [START_REF] Sinha | Auditory integration training and other sound therapies for autism spectrum disorders (ASD)[END_REF]. The authors' objective was to determine its effectiveness in people suffering from autism spectrum disorders (ASD). Six controlled, randomised auditory integration therapy trials were retained as against one Tomatis therapy trial. On the specific issue of ASD, even though numerous studies come to positive conclusions about the effects of the Tomatis method, only one seems to satisfy the trial inclusion criteria for a collaboration like Cochrane, authority on EBM (evidence-based medicine). What conclusions did they come to? Of the 7 studies counted to date, involving a total of 182 participants, only 2 (by the same author), on a cohort of 35 participants, report statistically significant improvements in the group after having received auditory integration therapy, for two evaluation criteria only.

The Collaboration specifies that the lack of conclusive proof about this technique should not be interpreted as proof that it is not effective. What's more, it encourages further research in the field of music therapy, as the current data from various scientific studies suggest that the benefits could be significant: social interaction, communication, social adaptation (autism spectrum disorders, schizophrenia), rhythm, coordination in the case of acquired brain injury, depressive syndrome, anxiety syndrome, blood pressure, respiratory rate (cancers) and sleep disorders. As a consequence, the French Health Authority stated in it last report on "managing autism": music therapy is advised, the Tomatis method not recommended [START_REF] Has | Autism spectrum disorder[END_REF]. Even though the rules of the scientific game are clear and sure, we can see the complexity of furnishing conclusive data, which is inherent to the Tomatis method: a lack of human and financial resources, refusals from research laboratories, internal division, lengthy and face-to-face therapy, a non-standardised protocol, lack of potency of the samples, multiple judging criteria, qualitative studies, unpredictable psycho-cognitive-motor effects.

The trial presented in this article wishes to avoid these stumbling blocks and to stick to quantitative criteria to evaluate the effects of the method. The limited number of subjects included, the disparity in the variances of the groups compared and the diversity in the choice of sound programs make that this research is more akin to a feasibility test or a preclinical study. Of all the distortions that can be interpreted from a listening test, which auditory stimulation purports to modulate (hearing thresholds, air bone gaps, scotoma, spatialization, sound discrimination) (3), only the quantifiable distortions, common to the audiogram, were retained. The possibility of an approximation of the level of perception via air conduction in the right ear with the ideal curve was suggested on the basis of data that pre-date literature. Although not rigorously validated, they agree that right-sided hearing can be lateralized by progressively and predominantly increasing the air conduction-based auditory stimulation to the right and develop the analytical skills of the left hemisphere which is directly linked to it. The assumption of a decrease in the gap between osseous perception and air perception, to the left and to the right, when receiving auditory stimulation which is either mainly bone or air based, depending on the initial test, was also suggested on the basis of experimental data that pre-date the method [START_REF] Auriol | Considérations sur le test d'écoute[END_REF][START_REF] Vervoort | The Improvement of Severe Psychomotor and Neurological Dysfunctions Treated with the Tomatis Audio-Psycho-Phonology Method Measured with EEG Brain Map and Auditory Evoked Potentials[END_REF].

The results obtained in our study (as referred as Tomatis Toulon Group) show a significant reduction in the gap between air conduction, AC, and bone conduction, BC, to the left (p=0.012). The decrease in the right AC/BC gap is not significant, just like the slight reduction in the gap between AC and the ideal curve (p=0.5). It is clear that there is a partially statistically significant improvement in the primary endpoint in terms of the analysis of the listening test.

In spite of a clear significant improvement, the quantitative results of the Toulon Group are considerably lower than the results obtained in the two other centers that use the method.

The Hermione Centre in Annecy was asked to analyse the trends in the listening tests of 10 of its patients before and after the therapy. This group is referred to as the "Tomatis Annecy" Group. The group consisted of 5 females and 5 males, with an average age of 16.3 years (median: 13 years; between the ages of 8 and 47). The average time span between the two analyzed examinations was 10.5 months until 2017. They received 100 hours of therapy on average.

The Atlantis Centre in Sin-Truiden (Belgium) was asked to analyze the trends in the listening tests of 10 of its patients before and after the therapy. This group is referred to as the "Tomatis Sint-Truiden" Group. The group consisted of 2 females and 8 males, with an average age of 8.7 years (median: 8.5 years; between the ages of 5 and 13). The average time span between the two analyzed examinations was 23 months until 2017. They received 250 hours of therapy on average.

The variation in age of the Toulon Group (average age 31 years, median: 15 years) was close to that of the Control Group (average: 28.3 years, median: 33.5 years). These ages were significantly different from the Tomatis Annecy Group (16.3 years, with a median of 13) and the TomatisSint-Truiden Group (8.7 years, with a median of 8.5).

The Toulon and Annecy Groups received 100 hours of therapy on average. The Sint-Truiden Group included patients with severe psychomotor impairment. They received 250 hours of therapy on average. The Control Group did not receive therapy.

The Tomatis Toulon Group was recruited on the basis of an invitation the therapist extended to the patient. At the time of recruitment, the average difference with the ideal was 3 decibels higher than in the Control Group. The Annecy and Sint-Truiden Groups were recruited the other way around, i.e. on the basis of a request the patient or the patient's parents had put to the therapist. At the time of recruitment, the average difference with the ideal was 10 to 11 decibels higher than in the Control Group. Might the young age of the subjects contribute to their greater sensitivity? Does a subject's initial average level of hearing play a role in the responsiveness or resistance to sound stimulation? Does a change in hearing level constitute a risk factor in mental health [START_REF] Amieva | Death, Depression, Disability and Dementia Associated with Self-Reported Hearing Problems: a 25-Year Study[END_REF][START_REF] Granier | Pure-tone auditory thresholds are decreased in depressed people with post-traumatic stress disorder[END_REF][START_REF] Mojs | The possibilities of the improvement language competencies in children with dyslexia. The evaluation of the Tomatis therapy in children aged 6-10 years of age[END_REF] ?

It is currently impossible to answer these questions. The essential point is however that (a) under difficult conditions (non-homogeneous population, hearing thresholds pooled for BC and AC in each side) we have been able to highlight an effect on quantified variables; b) in controls, the results of LTT are stable at several months intervals. It is now necessary to work on homogeneous populations better controlled and to differentiate the effects on the thresholds at low, medium and high frequencies.

B) Auditory cognitive evoked potentials:

The results of the P300 test shows a significant reduction in N1/P2 amplitude. It was also established that the amplitude of the Mismatch wave reduced during the second session, which goes hand in hand with increased latency and a shortening of the response times. On the whole, these results may also reflect a better performance with less active attention. In the absence of a relationship between the clinical and electrophysiological measures, no case can be made for the effect of audio-psychophonology training here. What's more, the studies that incorporate cognitive evoked potentials into cognitive training techniques mentioned in the introduction tend to record increased wave amplitudes. The effect we observed can therefore only be a non-specific habituation effect. Accordingly, it has been suggested that the increase in the amplitude of wave P2 was a non-specific learning marker [START_REF] Tremblay | Is the auditory evoked P2 response a biomarker of learning?[END_REF].

The limitation of our study is due to the small number of subjects and their age heterogeneity. It is also due to the technique we used which is the most straightforward one and most compatible with common function studies in a clinical neurophysiology hospital laboratory. The reduced number of derivations does for instance not take the inter-hemispheric differences in the temporal regions that are sometimes mentioned into account. It contrasts with the more elaborate techniques that have been fine-tuned in research laboratories, but which remain linked to the equipment used. As a result, it has not been possible to test complex stimulations like musical suites or different syllables here.

C) Clinical improvement :

In first instance, this experiment was not designed to establish a formal link between a possible improvement in clinical and electrophysiological measures of hearing and the clinical evolution of patients who receive auditory stimulation. This approach is a complex qualitative one and must be preceded by the scientific validation of the devices that measure electrophysiological variations of the hearing and the significant potential effect of auditory stimulation on these variations. However, this would entail a second judging criterion to question and broaden the research perspectives ensuing from this work. Some of the clinical improvements at least 4 of the patients mentioned at least once as a marked improvement after the final measures are listed here on account of their possible correlation with the significant changes observed in terms of the listening tests and the cognitive evoked potentials. This improvement concerns: concentration, self-esteem, daytime fatigue, mood, motivation/projection, independence, initiative-taking, speaking at home or in public, tonicity.

A number of confounding factors must be mentioned here because, in parallel with the auditory stimulation sessions, some patients also received osteopathic care, physiotherapy, speech therapy, psychotherapy. One of the subjects discontinued his Ritalin therapy. One of the subjects started a therapy for depression with SSRI. The recent conclusions by Inserm Bordeaux (January 2018) on the follow-up of the Paquid cohort merit reiterating here: 3777 participants over the age of 65, over 25 years. They confirm the direct link between the hearing profile of the patients included and the risk of invalidity, dementia and depression [START_REF] Amieva | Death, Depression, Disability and Dementia Associated with Self-Reported Hearing Problems: a 25-Year Study[END_REF]. Another recent publication of the Journal of European Psychiatric Association concluded that Tomatis training significantly improved subjects' cognitive functioning. They demonstrate its efficiency in relation to such parameters as reaction time, localization of sources of sound and over sensitivity to audio stimuli [START_REF] Mojs | The possibilities of the improvement language competencies in children with dyslexia. The evaluation of the Tomatis therapy in children aged 6-10 years of age[END_REF].

Conclusion

In spite of its limitations, the use of cognitive evoked potentials demonstrates its sensitivity in terms of analyzing the changes that are brought about by techniques that act on the attentional processing of sensory stimulations. A neurophysiological analysis of these techniques is needed to tailor the types of recordings to be used to facilitate an analysis of the neurological mechanisms.

The listening test shows a significant reduction in the gap between bone and air conduction to the left. This test has not been scientifically validated. Correlation between the cognitive evoked potentials changes and those of the listening test must be sought [START_REF] Vervoort | The Improvement of Severe Psychomotor and Neurological Dysfunctions Treated with the Tomatis Audio-Psycho-Phonology Method Measured with EEG Brain Map and Auditory Evoked Potentials[END_REF].

If the lack of conclusive proof about a technique must not be interpreted as proof that it is not effective, then the presence of a number of significant results on a small number of samples must, in the context of an essential improvement and the promotion of mental health care, be encouraged and pursued.

Other than a progressive follow-up of the effects of auditory stimulation, we can envisage an improvement in the choice of subjects that are likely to benefit from it (Watson, 1980).

T.R: partly employed by health insurance which is a source of funding for the study. CHITS company JVD : no conflict of interest.

Figure 1 :Figure 2

 12 Figure 1: A) Wegel's graph. The minimum and maximum for pain and hearing threshold curves join at the edges and delineate the normal hearing range in the centre. In abscises, the sound frequencies, on the ordinate the acoustic pression in dB. For listening Tomatis test (LTT) the audibility field curve (arrow) is inverted. B) Graph of a classic audiogram's reference curves, for a 20 year old patient. Air conduction is represented by the solid line, bone conduction by the dotted line Frequency is given in abscissa from 125 Hz to 8000 Hz. The extremities of the curves are linearized. Decibel are in ordinate. In dotted line, bone conduction, in full line, air conduction. C) Graph of the ideal listening curves from the LTT . Air conduction is represented by the solid line, bone conduction by the dotted line. Frequency is given in abscissa from 125 Hz to 8000 Hz. Decibel (dB) are in ordinate . . In dotted line, bone conduction, in full line, air conduction.A)

Table I :

 I Values for the standard audiogram and for the listening Tomatis test (LTT, in grey) audibility thresholds for various frequencies. BC = bone conduction; AC = air conduction.

	Frequencies (Hz)	125	250	500	750	1000	1500	2000	3000	4000	6000	8000
	Standard audiogram:		-9,1	-1,1	-4,9	-5,8	-3,3	0,2	-0,3	-4,8
	BO
	Standard audiogram:	0	1,5	2,5	2,5	1	1.5	0,2	2,1	2,2	0,7	3
	AC
	Ideal listening test curve	20	10	0	-5	-10	-10	-10	-10	-5	0	10
	(dB) of Tomatis (LTT):
	BO and AC threshold are
	considered as similar
	(+/-5dB)

Table 2 .

 2 Characteristics of the patient population studied.

	Patient	age	sex	Symptoms
	1	55	F	Burn out, sleep-wake cycle disorders
	2	14	M	ADHD, school failure
	3	10	M	Dreamy child, school failure
	4	10	M	Dreamy child, school failure
	5	14	F	School failure, inhibition without aggressiveness
	6	70	F	Sleep-wake cycle disorder, concentration disorder, mild depressive disorder
	7	32	F	Daytime hypersomnia in a context of lyme disease, attention disorders
	8	16	M	School failure, inhibition
	9	70	M	Barotrauma in 1971, deafness of transmission (1000 to 8000 hz)

Table 3 :

 3 Average values, (in dB), on right and left sides of audibility thresholds, in patients and controls of i) the difference between AC threshold measured values and the Tomatis ideal curve AC threshold values, ii) the difference between BC measured threshold values and the BC ideal threshold curve values ,iii) the difference between BC threshold /AC threshold ratios. See material and methods for details. *: Significant effect (p<0,05, Mann Whitney test)

			Control group		Patient group
		Test 1	Test 2 (11 months after	Test 1	Test 2 (after TAS, eg
			test 1)		about 10 months)
	AC left	9,4	9,9	11.3	11.3
	AC right	9,1	8,8	14.7	14
	BC left	7,7	7,7	8.4	8.6
	BC right	7,1	6,8	9.3	9.2
	BC/AC left	6,6	7,7	8.8	6.3*
	BC/AC right	6,4	6	9.8	8.4

Table 4 :

 4 evoked potentials performed in the 9 patients of the study.

	**significant effect: p < 0,005
	*significant effect p < 0,05

Conflicts of interest:

J.V: financial interest in the Atlantis MBL company. Study collaborator for loan of equipment and development of auditory remediation programs J.G: partly employed by health insurance which is a source of funding for the study. CHITS company.


Tristan Cazenave
email: cazenave@lamsade.dauphine.fr

Nicolas Jouandeau

Towards deadlock free Sokoban

We present algorithms to compute and match maze specific deadlock tables at Sokoban. They enable to use a greedy search that can solve problems that are not solvable using IDA*.

Introduction

Sokoban is a PSPACE-complete single agent search problem [START_REF] Culberson | Sokoban is PSPACE-complete[END_REF]. The presence of deadlocks makes Sokoban hard to solve even non optimally. Identifying deadlock states is therefore an important step towards solving Sokoban. In this paper we describe algorithms that find maze specific deadlocks as well as efficient algorithms to match the deadlocks during search.

The second section details deadlocks, the third section explains how they can be efficiently matched, the fourth section deals with the retrograde analysis of deadlocks, the fifth section deals with search algorithm using deadlocks, the sixth section gives experimental results.

Maze specific deadlocks

In Rolling Stone [START_REF] Junghanns | Sokoban: improving the search with relevance cuts[END_REF][START_REF] Junghanns | Pushing the limits: New developments in single-agent search[END_REF][START_REF] Junghanns | Sokoban: Enhancing general single-agent search methods using domain knowledge[END_REF] small 5x4 deadlock patterns are used to find simple deadlocks. Moreover a specific search algorithm is used to identifiy conflict among limited subsets of stones and dynamically create penalty patterns.

We use a different approach since we compute maze specific deadlocks containing a predefined number of stones.

Basic one stone and two stones deadlocks can be defined as:

stones in corners, stones on a border between two corners, two adjoining stones along a wall.

More complex deadlocks are computed using retrograde analysis. Retrograde analysis has already been successfully used in two player [START_REF] Thompson | Retrograde analysis of certain endgames[END_REF][START_REF] Lake | Solving large retrograde-analysis problems using a network of workstations[END_REF][START_REF] Thompson | 6-piece endgames[END_REF][START_REF] Cazenave | Automatic Acquisition of Tactical Go Rules[END_REF][START_REF] Cazenave | Generation of Patterns With External Conditions for the Game of Go[END_REF][START_REF] Romein | Solving awari with parallel retrograde analysis[END_REF] and single agent games [START_REF] Korf | Finding optimal solutions to rubik's cube using pattern databases[END_REF][START_REF] Culberson | Pattern Databases[END_REF][START_REF] Korf | Disjoint pattern database heuristics[END_REF][START_REF] Felner | Compressed pattern databases[END_REF].

A deadlock is represented as an ordered set of locations of stones followed by a location of the man. Two deadlocks can have the same locations of stones and a different location for the man.

We represent sets of deadlocks as a different forest for each maze. Each tree of the forest is rooted at a location of the maze, the deadlocks in the tree all contains a stone at that location. The children of the root contain the different second locations of deadlock in the set of deadlocks starting at the root, and so on.

A deadlock can be matched on a screen if a subset of all the stones in the screen corresponds to the set of stones of the deadlock and if the man on the screen can see the man of the deadlock inside the deadlock screen.

In order to verify all deadlocks for a screen, the tree associated to each stone in the screen is verified. The verification consists in checking recursively for each child that the corresponding stone is present in the screen.

The next figures explain how a tree is built for three deadlock with the same first location. The first screen is a two stones deadlock containing locations 16 and 21 and the man at location 0. These two locations and the location of the man are used to build the leftmost tree. Then the second deadlock containing locations 16, 29 and 32 and the man at location 0 is added to the tree, resulting in the tree in the middle. The third deadlock (16, 29, 33 and man at 44) is then added and gives the rightmost tree.

##### ##### ##### #@ # #@ # # # # # # # # # ### ## ### ## ### ## # # # # # # ### #$## # ###### ### #$## # ###### ### #$## # ###### # #$## ##### ..# # # ## ##### ..# # # ## ##### ..# # ..# # $ $ ..# # $ $ ..# ##### ### # ## ..# ##### ### # ## ..# #####@### # ## ..# # ######### # ######### # ######### ####### ####### ####### 16
Nodes contain a stone and possibly several man locations. The pseudo-code for verifying a tree is: A state is a maze containing stones at different locations and a man at a given location, the goal of the tree verification is to find if a subset of the stones of a state, is a deadlock. At each node of the tree, the algorithm verifies that the state contains the stone of the node. If a node contains deadlocks, it contains men locations. If one of the men locations is visible from the man in the state, a deadlock is found. Otherwise the verification continues for all children of the node.

deadlock
All the trees rooted to the locations of the stones of a state are verified.

Retrograde analysis of deadlocks

Retrograde analysis starts with finding all the possible combinations of three stones. In a first pass, for each combination, it verifies that a subset is not already a deadlock. Then it tries all possible moves and verifies that they all lead to a known deadlock. When it is the case the combination is added to the set of deadlocks. In the subsequent passes, it goes through all the found deadlocks, finds all possible previous states. For each previous state, it checks if all moves lead to a known deadlock, and when it is the case the previous state is added to the set of deadlocks.

The pseudo code for the first pass is: Finding all possible combinations in the first pass can be time consuming when the number of stones grows. Many possible combinations do not lead to a deadlock, moreover a first pass deadlock is often a state where a move leads to a smaller deadlock. In order to rapidly compute the first pass, we only consider states where a move leads to a smaller deadlock. These states can be efficiently found by taking a smaller deadlock, finding all previous states, and adding the missing stones in every possible location.

Combinations
The pseudo code for the first pass using the smaller deadlocks is: However the first pass using the smaller deadlock does not find all possible deadlocks. For example a few deadlocks do not have any possible moves and are not found by the smaller deadlock search.

Smaller
Here are some examples of deadlocks that are not found:

############ ######## ######## #..@ # ### #@ # #@ # #.. # # # # ## # # ## #.. # #### # # # # # #.. ## # ##$ # ##$ # #.. # # $$## ######### $$#$### ######### $$# ### ######$##$ $ # #.... ## $ $ # #.... ## $ $ # # $ $ # ##... # ##... $ # # # # #.... ########## #.... ########## ############ ######## ########
Only very few deadlocks have no possible moves. However the algorithm also misses other deadlocks that are based on even smaller deadlocks that the one used.

The retrograde analysis algorithm we have used starts its first passes with all possible combinations of stones until a predefined number of stones (maxS-tonesCombination), and then continues with first passes based on smaller deadlocks:

Global deadlock search process nbStones = 1 while not end of deadlock search if nbStones < maxStonesCombination newStates = combinationsDeadlocksSearch (nbStones) else newStates = smallerDeadlocksSearch (nbStones) while size of newStates is not 0 otherStates = subsequentDeadlocksSearch (nbStones, newStates) newStates = otherStates nbStones++ Another way of looking at Sokoban problems is to start from the goal position and going backward to the start position pulling stones. In this case, the usual deadlocks never appear since the goal position is always reachable by pushing back stones. However other kinds of deadlocks appears which stop the backward search: the pull deadlocks.

Here are example of one stone, two stones and 6 stones pull deadlocks for screens 1 and 13:

##### ##### ######### #@ # # # ## ## ##### # # # # ###@$$ # # ### ### ## ### ## # $ # # # ... # # # #@ $ # # # #$$## # #.#. # ### # ## # ###### ### # ## # ###### # # # # . . # # # ## ##### ..# # $# ## ##### ..# # $ # # #.#. # # ..# # ..# # ## ## . . # ##### ###$# ## ..# ##### ### # ## ..# # # # # #.#. # # ######### # ######### ## ... # ####### ####### # ###### ## # # # ########## ####
In the first one stone pull deadlock, the stone cannot be pulled. In the second two stones pull deadlock pulling the stones reaches a position where no more pulling moves are possible. In the last six stone pull deadlock a more complex retrograde analysis finds that all moves lead to position where no more moves are available, and the man is trapped in a local area.

Searching with deadlocks

In this section, we present the algorithms we use to solve problems. The first algorithm is a greedy search. It consists in developping the state that has the minimal associated heuristic. A greedy search is pointless in Sokoban without deadlock verification since it is trapped in promising deadlock states for a very long time. When deadlocks can be detected a greedy search avoids such states and can find solutions.

The pseudo code for the greedy algorithm with deadlock verification is:

Greedy

child in front of sortedStates [h] if h < currentGreedy currentGreedy = h

The other algorithm we have tested is IDA*. We used a very simple admissible heuristic which consists in summing for all stones the distance to the closest goal location. Moreover we do not place stones inside the goal area and assume they are at their goal location as soon as they enter the area.

The greedy algorithm is very similar for pull deadlocks, except that the heuristic used is a greedy one, the closest pair of stone and start location is chosen, their distance is added to the heuristic, then the start location is removed from the possible locations and the process is repeated until all pairs have been chosen.

Results

In order to compute the deadlock tables, all combinations are tried until 4 stones, then for more stones, a smaller search first pass with P max = 2 is performed, followed by usual passes. Table 1 gives the time used to build deadlock tables and the number of deadlocks found for screen 13. A distinction is made between the first pass and subsequent passes. For 5 stones, the combination search takes 40 minutes and the smaller search takes 10 seconds, the number of deadlock found in the first pass of the smaller search is higher than in the combination search since it the order in which it considers deadlocks is not the same and as it checks a deadlock as soon as it is found. For 10 stones, the smaller search uses 2h14m for the first pass and 1 minute for subsequent passes. Table 2 gives similar information for the deadlocks of screen 14. Table 3 gives the number of nodes required to solve screen 13 and screen 16 with a greedy search and different deadlock tables. Using deadlock tables with only three stones it does not solve the problem 16 in one million nodes. Using four stones deadlock tables, it solves screen 16 in 56941 nodes. The number of nodes decreases with the number of deadlock stones until 8 where it reaches its minimum at 623 nodes. Concerning screen 13, the problem can be solved with the 8 stones deadlock tables, computing more deadlock tables is of little practical interest given the computing times of the deadlock tables greater than 8 stones given in table 1. the number of the screen, the second column is the number of stones of the screen, the third column gives the number of deadlock stones in the tables (-if equals to the number of stones), the fourth column gives the number of nodes used by a greedy search without deadlock tables (search is stopped after 1M nodes, so 1M means the search has failed), the fifth column gives the number of remaining stones for the position in the greedy search that has the minimum such number, the sixth colmun give the number of nodes used by a greedy search with deadlock tables, the seventh column the related number of remaining stones, the seventh column the number of nodes of IDA* without deadlock tables, the eight column the related number of remaining stones, the ninth column the number of nodes of IDA* with deadlock tables and the last column the related number of remaining stones.

Our current greedy search does not manage the placement of the stones in the goal area, as soon as a stone is in the goal area it is removed and considered as placed in the right location of the goal area. For many problems this simplification does not change the solution of the problem, however in some screens there can be interactions between the goal area and the solution or there can be multiple goal areas (for example in screen 18 there are three goal areas so our solution is not valid, in screen 15 there are two stones in the goal areas in the start position and they interact with the solution so our greedy solution is also not valid). Our simplification poses no problem in screens with a simple goal area such as screens 13, 20, 24, 28 and 31 which are solved by greedy search with deadlock tables and not by Rolling Stone.

Deadlock tables were added to Rolling Stone. The IDA* search was stopped as soon as a deadlock was encountered. The results are given in table 5. The first column gives the screen number, the second column gives the number of nodes used by the original Rolling Stone, the third column gives the number of nodes used by Rolling Stone equipped with deadlock tables. Deadlock tables reduce the number of nodes for almost all problems, problem 8 being an exception. A possible explanation is that in this problem some penalty patterns could not be found by Rolling Stone due to deadlock tables cuts and could not be reused in other parts of the search.

Table 6 gives the number of pull deadlocks and their computation times for screen [START_REF] Thompson | Retrograde analysis of certain endgames[END_REF].

A greedy search with pull deadlocks can be trapped in position that are close to the goal position but that are not solvable. Here is an example for screen 1 where the search is one move away from the start but is in a hopeless position, moreover the man cannot move to its start position:

##### ##### # # #@ # #$ # # $ # ### $## ### $## # $ $ # # $ $ # ### # ## # ###### ### # ## # ###### # # ## ##### ..# # # ## ##### ..# # $ $ ..# # $ $ ..# ##### ### #@## ..# ##### ### # ## ..# # ######### # ######### ####### ####### after 495112 nodes

Conclusion

We have presented how to use retrograde analysis to compute maze specific deadlock tables at Sokoban, we have also presented how to use deadlock trees to match the computed deadlocks efficiently as well as a greedy search algorithm. Moreover we have presented a new way to solve Sokoban problems pulling stones out from the goal area towards their start positions as well as the related pull deadlocks.

These algorithms have been tested on many Sokoban screens including difficult ones. Computing maze specific deadlock tables has enabled to successfully use a greedy search at Sokoban and to solve problems that are not solved by IDA*.

In future works, we will improve greedy search so as to cope with the placement of stones in the goal area. We will also try to improve the retrograde analysis efficiency and completeness.

Table 1 .

 1 Time needed and number of deadlocks found with deadlock search.

	screen 13	with combination		with smaller P max = 2
		time nb passes 1st next	time nb passes	1st next
	1	<1s	2 40	0
	2	<1s	4 49	6
	3	1s	5 59 20
	4	40s	6 160 117
	5	40m	7 417 345	10s	6	440	244
	6				43s	8 1576 1057
	7				2m16s	7 4075 3042
	8				9m47s	8 12970 10534
	9				33m31s	10 38775 36838
	10				2h15m	11 154480 132908
	11				8h33m	11 411582 300621
	12				33h20m	17 603892 403528

Table 2 .

 2 Time needed and number of deadlocks found with deadlock search.

	screen 14	with combination		with smaller P max = 2
		time nb passes 1st next	time nb passes	1st	next
	1	<1s	2 36	0
	2	<1s	8 64 38
	3	1s	8 68 38
	4	41s	8 167 49
	5	43m	10 436 248	14s	9	431	113
	6				25s	15	1084	1036
	7				1m31s	18	2999	4548
	8				8m23s	16 14518 14944
	9				32m11s	18 65739 64714
	10				2h44m	17 342553 375699
	11				17h07m	16 1413054 1690141

Table 3 .

 3 Greedy search with different numbers of deadlock tables.

	screen 13
	stones	5	6	7	8	9	10	11	12
	nodes >1M >1M >1M 1414 1407 1372 1371 1371
	screen 16
	stones	3	4	5	6	7	8	9	10
	nodes >1M 56941 7278 1986 1496 623 623 623

Table 4

 4 compares the different search algorithms on different screens. The greedy algorithm with deadlock tables solves most of the problems we have tested. It solves problems 13, 15, 16, 18, 20, 22, 24, 28, 29, 31, 32 and 44 which are not solved by Rolling Stone. The first column of the table is

Table 4 .

 4 Number of nodes evaluated and resulting top level node needed to solve problems.

	Screen MZ	DL	greedy		ida*
				basicDL	DL	basicDL	DL
	1	6	-	643 (0)	400 (0)	1M (1)	1M (1)
	2	10	-	1M (10)	4291 (0)	1M (6)	1M (4)
	3	11	-	1M (10)	490 (0)	1M (3) 723410 (0)
	4	20	-	1M (20)	1981 (0)	1M (20)	1M (5)
	5	12	-	1M (11)	899 (0)	1M (4)	1M (2)
	6	10	-	1M (9)	535 (0)	1M (1)	150 (0)
	7	11	-	1M (8)	378 (0)	1M (2) 40888 (0)
	8	18	11	1M (14)	1489 (0)	1M (12)	1M (10)
	9	14	-	1M (14) 10819 (0)	1M (4)	1M (2)
	11	14	11	1M (14) 62345 (0)	1M (13)	1M (13)
	12	15	13	1M (14)	1440 (0)	1M (10)	1M (10)
	13	16	12	1M (16)	1371 (0)	1M (7)	1M (6)
	14	18	11	1M (13)	1M (14)	1M (14)	1M (9)
	15	15	11	1M (9)	769 (0)	1M (7)	1M (7)
	16	15	14	1M (11)	623 (0)	1M (10)	1M (7)
	18	11	10	1M (7)	443 (0)	1M (4)	1M (4)
	20	18	10	1M (16) 102784 (0)	1M (15)	1M (15)
	22	27	11	1M (25)	2251 (0)	1M (25)	1M (21)
	24	22	10	1M (21)	6967 (0)	1M (17)	1M (17)
	27	20	10	1M (20)	1M (15)	1M (18)	1M (15)
	28	20	12	1M (20)	9691 (0)	1M (15)	1M (8)
	29	16	11	1M (9)	396 (0)	1M (4)	1M (2)
	31	20	10	1M (19)	1800 (0)	1M (20)	1M (11)
	32	15	13	1M (11)	646 (0)	1M (5)	1M (5)
	44	9	-	1M (7) 908532 (0)	1M (6)	1M (5)

Table 5 .

 5 Total nodes searched with Rolling Stone.

	screen without deadlock tables with deadlock tables
	1	1042	384
	2	7530	6366
	3	12902	7181
	4	50369	50369
	5	43294	20483
	6	5118	4028
	7	28460	25954
	8	336495	408123
	9	436801	343591
	11	3091658	2323731
	12	559216	556353
	13	>20M	>20M
	44	>20M	>20M

Table 6 .

 6 Time needed and number of pull deadlocks found with pull deadlock search.

	screen 13	with combination	with smaller P max = 2
		time nb passes 1st next time nb passes 1st next
	1	<1s	1 0 -
	2	<1s	3 35 2
	3	8s	2 78 0
	4	10m51s	2 234 0
	5			16s	10 195 400
	6			76s	10 714 1023


Zhi Yan

Nicolas Jouandeau Arab

Ali Cherif

Sampling-Based Multi-Robot Exploration

This paper presents a new approach for collaborative multi-robot planning issues. The main problem that arises from multi-robot exploration is waiting situations. We consider that such problem involves two or more autonomous robots in an unknown environment. The mission objective is to explore the entire map, while trying to minimize its executing time. Moreover if each robot uses the same topological graph, then it uses the same exploration path that makes waiting situations arising. To solve this problem, we propose a new approach in this paper based on sampling iteratively maps to allow interactive multi-robot exploration. Our approach has been implemented in simulation and the experiments demonstrate that the overall completion time of an exploration task can be significantly reduced by our sampling-based method.

Introduction

The problem of exploring an environment is one of the fundamental problems in mobile robotics. We hope it can also cover the whole exploring space more efficiently by implementing this exploration. Therefore, the key issue is how to move the robot in order to minimize the time needed to completely explore an environment [START_REF] Burgard | Collaborative multi-robot exploration[END_REF]. In relation to a single mobile robot, in some cases, using a collaborative team of mobile robots can accomplish the exploration mission better so as to achieve the purpose of reducing the mission time. For example, looking for an object can be achieved more rapidly as each robot of a team can try different scenario simultaneously with other robots. We also believe that cooperative multi-robot systems have more adaptability than classical single ones. Figure 1 shows an example of a three robots system involved in the same map and both robots are dispatched to different destinations. Unless minimizing the global time of the exploration mission, the collaborative exploration can be smarter than a single robot exploration, if the robots communicate with each other about their position information whenever they sense each other, they could localize themselves much easier [START_REF] Fox | Collaborative multi-robot localization[END_REF].

In this paper, we consider the problem of exploring an unknown indoor environment with a collaborative team of mobile robots that the mission objective is to explore the entire map but the implementation time should be as short as possible.

In order to achieve this goal, we need to focus on examining the following three questions: a) How to identify the potential exploration targets for the map. b) How to assign reasonably the targets calculated in previous question to each individual robot. c) How to plan the path for multiple robots so as to avoid collision, mutual blocking, and all the other problems of waiting situation. For the first question, the common method is using the space partitioning by Voronoi diagram [START_REF] Wu | Voronoibased space partitioning for coordinated multi-robot exploration[END_REF], [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF] and [START_REF] Maneewarn | Sorting objects by multiple robots using Voronoi separation and fuzzy control[END_REF]. The feature of this method is that, the geometry information of map can be well described by using Voronoi diagram, so it allows planning the obstacle-avoiding path effectively for mobile robots. However, in this case, since each robot uses the same topological graph, i.e. the same exploration path, the waiting situation will reasonably likely to occur. In this paper, we introduce a new approach based on sampling iteratively for multi-robot exploration. The core idea is, we sample on the basis of Voronoi Diagram, aim to build a separate topological graph for each robot, i.e. the different exploration paths, so as to avoid the defects mentioned above, and achieve the purpose of reducing the mission time. Through the simulation experiments with a group of robots and compared with others methods, the result show that the overall exploration time is significantly reduced by our method.

This paper is organized as follows. In Section 2, we state the problem, and discuss briefly some related works. Section 3 presents our approach, i.e. sampling-based multirobot exploration. Then we present experimental results in Section 4 and a conclusion is given in last Section 5.

Related Work

In recent years, the question of the collaborative exploration in unknown environments using a team of mobile robots has increasingly been considered. A strategy frontierbased exploration has been presented by B. Yamauchi [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF]. This approach introduced the concept of frontier defined as regions on the boundary between known spaces and unknown spaces. Mobile robots move to the nearest frontier which is the nearest unknown area.

W. Burgard et al. [START_REF] Burgard | Collaborative multi-robot exploration[END_REF] presented a probabilistic approach for the coordination of multiple robots which simultaneously takes the costs of reaching a target point and the utility of target points into account.

An approach using the Hungarian method [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] to compute the assignments that determines which robot should move to which target has been presented by Ko et al. [START_REF] Ko | A practical, decision-theoretic approach to multi-robot mapping and exploration[END_REF].

L. Wu et al. [START_REF] Wu | Voronoibased space partitioning for coordinated multi-robot exploration[END_REF] presented an approach for the coordination of multiple robots which based on Voronoi space partitioning. Through experiments, they presented Voronoibased partitioning performs better than the well-known KMeans-based partitioning. S. A. Wilmarth et al. [START_REF] Wilmarth | MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space[END_REF] presented a new method of sampling on the medial axis of the free space in probabilistic roadmap planners. This algorithm is called MAPRM. Configurations are randomly generated, free or in collision, and are retracted onto the medial axis of the free space. Retracted configurations are used to set a graph that traduces untractable free spaces and that adapts itself to grab narrow passages in free C .

An approach using a segmentation of the environment for the collaborative multi-robot exploration has been presented by K. M. Wurm [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF] that was designed to distribute the robots to different tasks, that means for authors to different rooms in indoor environment, so as to accomplish the exploration mission as soon as possible. This method of distribution takes the structure of the environment into account and partitions the space into segments. However, this method has only considered one topological graph for each map, especially for corridor space. This will lead to that, for a team of mobile robots, there topological graphs of exploration are partially overlapping. Then waiting situations can appear during exploration (Envisage a situation where several homogeneous robots start to move in the same direction at the same time and the same start line).

Others approaches have been developed with various policies [START_REF] Fox | Distributed multi-robot exploration and mapping[END_REF], [START_REF] Stachniss | Efficient exploration of unknown indoor environments using a team of mobile robots[END_REF] and [START_REF] Rekleitis | Multi-robot collaboration for robust exploration[END_REF]. For all, the goal is to coordinate as well as possible for exploration tasks with a team of mobile robots.

In this paper, our approach, in contrast, is especially designed to build a separate topological graph for each robot, i.e. the different exploration path, so as to avoid the waiting situation. The main idea is to build simultaneously different graphs, according to each robot situation, priority according to the whole mission achievement.

Sampling-Based Multi-Robot Exploration

The key issue for exploration with a group of mobile robots is how to make the robots have better collaboration ability. So an important reference criterion for evaluation of effectiveness of collaboration is the time needed to cover the whole environment with the robot's sensors, i.e. the time to accomplish the overall exploration task. In this paper, our focus is, on the one hand, the exploration paths of the individual robots in the team, on the other hand, the strategy for distribution of exploration targets.

Waiting Situation

An important reason for limiting the effectiveness of multi-robot collaboration is the waiting situation. The root cause is that all robots might wholly or partly follow the same exploration path. An effective way to solve this problem, i.e. the waiting situation, is to build for each robot the different exploration path as different as possible, i.e. the overlap in topological graph for each robot as little as possible.

Sampling-Based

The sampling-based approach has dominated the research in recent years and has been applied in fields both in and out of robotics, such as automobile assembly, humanoid robot planning, and conformational analysis in drug design [START_REF] Lavalle | Planning Algorithms, Sampling-Based Motion Planning Chapter 5[END_REF]. Although the completeness guarantees are weaker, this approach has been applied to a wide variety of robot motion planning problems [START_REF] Wilmarth | MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space[END_REF], [START_REF] Jouandeau | Fast Approximation to gaussian random sampling for randomized motion planning[END_REF] and [START_REF] Song | Randomized motion planning for car-like robots with C-PRM[END_REF], because of his efficiency and ease of implementation. The main philosophy of sampling-based approach is to avoid the explicit construction of obs C . There is a large number of possible variant of sampling-based algorithm. Figure 4 illustrates the process of generating a Probabilistic Roadmap based on sampling approach for an example occupancy grid map. The left illustration shows a configuration space in which we will build a Probabilistic Roadmap, the center illustration depicts the random points in free C , and the roadmap constructed by connecting nearby samples can be seen in the right illustration. With the right illustration, we can build the exploration path for mobile robot by connecting the nearest free C in the roadmap.

Our algorithm [START_REF] Jouandeau | Algorithmique de la planification de mouvement probabiliste pour un robot mobile[END_REF] is designed to compute the medial axis of the free space by random sampling, and is given in Algorithm 1.

Algorithm 1 Probabilistic Medial Axis Sampling 1:

← T empty; 2: while T is not efficient 3:

← 0 q random in free C ; 4: ← 1 q nearest ( 0 q , δ ) in obs C ; 5: 1 0 2 * 2 q q q - ← ; 6: while 2 q in C and 2 q in free C 7: 2 / ) ( 2 0 0 q q q + ← ; 8: 1 0 2 * 2 q q q - ← ; 9:
end while 10: if 2 q in obs C

11:

← T add( 0 q ); 12:

end if 13:

end while 14:

return T ;
T is defined as the graph that tries to represent as well as possible the median axis. It is based on the sampling of free C and computing the approximation of the clearance between obstacles. For each random configuration, a near configuration of obs C is chosen with a precision of δ .

When this first configuration is defined, a last configuration is set to fix the first random at the center of the two last. While the last configuration is free, the last is pushed far from the others and the random configuration is replaced in their center. It produces self adaptive medial axis synthesis, fitted to the clearance of each local free space.

Our experiments proved that, with our sampling-based algorithm, we can effectively build a separate topological graph for each individual robot of the team.

Target assignment

In indoor environment, there are three types of structure in general, room, doorway and corridor. We consider each room like a potential exploration target. So the distribution of target means that the assignment of room to individual robots.

H.W. Kuhn [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] presented the Hungarian method for the assignment problem in 1955. It is a classical algorithm for solver the maximum matching problem in a bipartite graph. In our research, we use this method to find the best distribution of exploration target to robots. The implementation can be summarized as follows: With this method, each exploration target will not be assigned to the same robot unless the count of robot is more than the count of unexplored target. In that case, we clone the target in accordance with the count of robots.

Planning

In our approach, we assign the room like a potential exploration target to different robots by taking into account both the critical points of DVG and free C based on sampling. When all room is explored signifies that the overall exploration mission has been completed. Assign the target rooms to each robot using the Hungarian method. 5: end while Our planning algorithm is summarized in Algorithm 2. First of all, in a configuration space, we use DVG to build an exploration path for one robot, and we find the so-called critical points [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF], [START_REF] Thrun | Learning metric-topological maps for indoor mobile robot navigation[END_REF], so as indentify room, doorway and especially corridor. Second, we sample in corridor based on DVG by taking into account the critical points. After sampling, so we can build a separate topological graph for each individual robot. Then we use the Hungarian method to assign the individual robots to potential exploration targets. During the explorations, we apply dynamic planning to robots by taking into account both the critical points of DVG and free C based on sampling.

Experimental Results

Our approach described has been implemented in a 2.5D multiple-robot simulator called Stage [START_REF] Kranz | A Player/Stage System for Context-Aware Intelligent Environments[END_REF] which is a part of the Open-source software the Player Project. The simulation experiments were conducted using the Activmedia Robotics PIONEER 2 DX robot equipped with a laser range finder with 180 degrees field of view. And all our experiments were carried out on the notebook Compaq nx6125.

In our experiments, we have studied three types of skeletonizations, Voronoi diagram, straight skeleton (by library CGAL [START_REF] Cacciola | A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes[END_REF]), sampling-based graph, to extract information from the map. For this two first, skeleton have to be transformed to a topological graph for each robot that allows target locations assignment to each autonomous robot using the Hungarian method. To decentralize this last phase, we have tried to assign target locations to the individual robots using iteratively the Hungarian method at each step of each robot in the topological map. This additional phase decreases mission time needed and produces plans where each robot is following individually its plan to full-fill the mission.

Figure 5 and Figure 6 show two experimental maps used for the simulation. The left part show the map extracted by Voronoi diagram. The center part show the geometry in-formation generated by straight skeleton, the red lines depict the free path which mobile robots can follow to reach the target rooms. And the right part shows the result by using our sampling-based method. Notice that we sample just for corridor, our experimental results prove that it is sufficient for solving the waiting situation for multiple robot exploration.

After identify these two experimental maps, we have tested with several robots by using different methods. The average mapping times and average planning time for all approaches corresponding to two occupancy grid maps and three or four different counts of robots are displayed in table 1, table 2 andtable 2 given the results by using straight skeleton. The same problem like table 1, i.e. waiting situation.

Table 3 given the results by using sampling-based method. We can find that, although the mapping time required has been increased, the completion time of an exploration task has been significantly reduced by our method.

Each time is an average time computed over 10 executions. When using more than 1 robot, each executing time is followed by its standard deviation. Over all tables, the standard deviation is less than 2sec when average times vary between 100sec and 400sec. In brief, first of all, the three tables show that, in contrast a single robot, a collaborative robots team can implement the exploration more efficiently, i.e. the time required to accomplish overall exploration task has been reduced.

Secondly, by comparing the results of these three methods above, we show that sampling-based is the most effective one to eliminate the problem of waiting time. The reason is by sampling-based, we can build a separate topological graph for each robot, and each topological graph will take the other robots' topological graph into account, so that every robot has its own exploration path, and there will not be any blocks between any two of them. By this means the waiting situation problem will get resolved.

Conclusion

The experiments proved that the time needed to accomplish the exploration mission has been significantly reduced by our sampling-based method which reduces waiting situations possible occurrences. Because, in contrast with only use Voronoi diagram, adding the sampling-based graph that could be computed online, incrementally and synchronized to robot's configurations.

Figure 1

 1 Figure 1 Example of collaborative exploration of multiple mobile robots.

  Figure 2 depicts two types of waiting situation. The left half part of the figure shows a waiting situation when four robots move simultaneously to the same free C , and the right half part shows the same problem when four robots pass to the same free C in proper sequence. Figure 3 shows the two free C to pass for the four robots.

Figure 2

 2 Figure 2 Two types of waiting situation.

Figure 3

 3 Figure 3 Two free C to pass for robots.

Figure 4

 4 Figure 4 Generation of the Probabilistic Roadmap based on sampling approach.

  a) Construct a cost matrix n n × , n corresponds with the count of robots. The entry in matrix corresponds with the exploration path length from robot's current position to exploration target. b) Apply the Hungarian method on the cost matrix to find the maximum matching. c) In terms of the above maximum matching obtain, assign the individual robots to exploration targets.

Algorithm 2 2 :

 22 Sampling-Based Exploration Planning 1: Build an exploration path for one robot with DVG. Build the separate exploration paths for the other robots with sampling-based algorithm. 3: while all target rooms not yet explored do 4:

Figure 5 Figure 6

 56 Figure 5 Map A. Left: Voronoi Diagram. Center: Straight Skeleton. Right: Sampling-Based

Table 1

 1 3. Voronoi DiagramTable1given the results by using Voronoi diagram. The waiting situation does not exist in a signal robot. However, from two robots, the waiting problem appears. The robots have to pass free C one by one because of the same explo-

			Map A	Map B
	Nodes		24	34
	Links		23	33
	Mapping time	< 1s	< 1s
	Planning	1 robot 200.0s	410.0s
	time	2 robots 130.2s (1.662) 267.5s (1.104)
		3 robots 102.0s (1.789) 193.5s (1.225)
		4 robots 98.6s (1.910) 151.0s (1.400)
	ration path.
			Map A	Map B
	Nodes		21	32
	Links		20	31
	Mapping time	< 1s	< 1s
	Planning	1 robot 201.0s	398.0s
	time	2 robots 128.6s (1.496) 262.1s (1.101)
		3 robots 97.3s (1.552) 191.7s (1.134)
		4 robots 92.2s (1.661) 148.4s (1.281)

Table 2

 2 Straight SkeletonTable

Table 3

 3 Sampling-Based Method

6

Literature