Mariana Neves
email: mariana.lara-neves@bfr.bund.de

Antonio Jimeno Yepes

Aurélie Névéol

Rachel Bawden

Giorgio Maria Di

Roland Roller

Philippe Thomas

Federica Vezzani

Vicente Maika

Navarro

Lana Yeganova

Dina Wiemann

Cristian Grozea

Findings of the WMT 2023 Biomedical Translation Shared Task: Evaluation of ChatGPT 3.5 as a Comparison System

We present an overview of the Biomedical Translation Task that was part of the Eighth Conference on Machine Translation (WMT23). The aim of the task was the automatic translation of biomedical abstracts from the PubMed database. It included twelve language directions, namely, French, Spanish, Portuguese, Italian, German, and Russian, from and into English. We received submissions from 18 systems and for all the test sets that we released. Our comparison system was based on Chat-GPT 3.5 and performed very well in comparison to many of the submissions. * The contribution of the authors are the following: MN prepared the MEDLINE test sets, performed test set validation, manual validation, and organized the shared task; AJY performed test set validation, manual validation, the automatic evaluation and co-organized the shared task; AN compiled information on participants' methods, performed test sets validation, manual validation and annotations of chatGPT outputs on the en2fr test set; RB, GMDN, RR, PT, FV, MVN, LY, DW performed test set validation and/or manual validation; and CG used OpenAI API to create the ChatGPT 3.5 point of comparison;

Introduction

We describe the eighth edition of the Biomedical Translation Task 1 that was part of the Eighth Conference on Machine Translation (WMT23). Similar to previous years, we released multiple test sets based on biomedical abstracts that we retrieved from the PubMed database. 2 April 26, 2023 and searched for articles that contained abstracts in both English and one of the six languages that we consider. We then randomly selected 100 bilingual abstracts for each of the language pairs. For all language pairs, we split the sentences of the abstracts using SciSpacy [START_REF] Neumann | ScispaCy: Fast and robust models for biomedical natural language processing[END_REF] and aligned them with the Geometric Mapping and Alignment (GMA) tool. 4 Native speakers of the languages manually checked the alignment quality in the Appraise tool [START_REF] Federmann | Appraise evaluation framework for machine translation[END_REF]. In this evaluation, we classified the automatically aligned sentences into five categories:

1. "OK": both sentences contain the same information;

2. "Source>Target": the source sentence contains more information than the target one;

3. "Target>Source". the target sentence contains more information than the source one;

4. "Overlap": both source and target sentences have information not contained in the other one;

5. "No Alignment": the sentences refer to completely different contents, or one of hem is missing.

We present the results in Table 1. The highest alignment rates, i.e. the "OK" ones, were for Portuguese (at least 90%, both en2pt and pt2en), and the lowest ones for Russian (only 52% for en2ru). For the latter, we notice that the biggest difference with respect to the other language pairs is that many sentence pairs are not aligned, i.e. the "No Alignment" ones. The percentages for "Source>Target", "Target>Source", and "Overlap" are similar to the other language pairs. An analysis of these errors shows that they are due both to the sentence splitting and the alignment tool.

We released our test sets in two submission systems: (i) our Google form as announced on our shared task's web site; (ii) in OCELoT,5 both in the General and in the Biomedical test sets. model through the OpenAI API. We refer to Chat-GPT as a comparison system rather than a baseline, as it does not satisfy the usual criterion for a baseline as being a transparent, well-understood and reproducible model that provides a good (generally) lower bound against which to compare systems. Notably, the model is closed-sourced and trained on huge amounts of data, of which the details are not openly known.

ChatGPT 4 excels at many tasks [START_REF] Chen | An extensive benchmark study on biomedical text generation and mining with ChatGPT[END_REF][START_REF] Jahan | Evaluation of ChatGPT on biomedical tasks: A zero-shot comparison with finetuned generative transformers[END_REF], including translation. Researchers from Tencent identified in a limited early evaluation done before the API was available ChatGPT 4 as a good translator [START_REF] Jiao | Is ChatGPT a good translator? Yes with GPT-4 as the engine[END_REF]. Please note that we abstained from using the stronger ChatGPT 4 and used instead the faster but expectedly weaker ChatGPT 3.5. More precisely we used the model snapshot "gpt-3.5-turbo-0613", computed on June 13th 2023 but with the training data "up to Sept 2021"6 . This reduces the risk of data contamination with respect to the abstracts used in our test sets, which were published in 2023.

The ChatGPT variants are large and trained on large quantities of data, but are generalist systems. Ideally, systems dedicated to translation or specialized in biomedical translation would be able to outperform them, or at least outperform the faster lower-quality version that we proposed here as a point of comparison. Otherwise, there are fewer reasons remaining for developing and using an alternative machine translation (MT) system: data privacy, self-hosting, usage in low-resources, nonconnected systems.

We used the following prompt to perform the translations and to keep ChatGPT from producing any comments beyond the translation text itself: "You are a helpful assistant specialised in biomedical translation. You will be provided with a sentence in {src}, and your task is to translate it into {trg}." where {src} was the source language and {trg} was the target language (e.g. src = Italian and trg = English).

Using ChatGPT through the API proved to be more challenging than expected and seemed to act as a stress test for the API servers or for the cloudfare content distribution network proxy they use. For example we hit various intentional limitations, such as a rate limit of 90,000 tokens per minute. We then faced multiple other errors: read time out in the object "HTTPSConnectionPool" with host api.openai.com, HTTP 502 (bad gateway), and "internal error". After writing our API calling code in an idempotent way, we were able to interrupt it whenever it was stuck and restart it whenever we stopped it or it stopped with an error. To this end, the script would skip over the existing translations and proceed with sending for translation, one by one, the rest of the entries not yet translated. The overall experience remained positive, as building the ChatGPT 3.5 translations involved 674,470 tokens, resulting in a total API cost of only 1.15 USD. However, we have no information on the CO 2 impact of the computation, which should include the impact of inference for translations as well as a fraction of the impact of training the Chat-GPT 3.5 model. Writing the scripts and executing them took less than three days. The execution itself was fast; as we reported here, at times we exceeded the API limit of 90,000 tokens per minute.

Teams and systems

After the release of the test sets, the teams had around two weeks to process the data and submit their translations. We collected submissions from the two systems (our Google form and OCELoT) belonging to 18 teams (or systems), as listed in Table 2. We allowed up to three runs for each team and language pair. From all submissions, we skipped only one translation from one team, namely the one for fr2en from UPCite-CLILLF, since it was in French (instead of English).

This year, the Google submission form also included questions on material and methods used by participants. The questions were identical to those used in 2022. The response rate was lower than in previous years (2020-2022) when the questionnaire was operated separately from the submission system and teams were asked to complete the survey after submission. In Ocelot submissions, participants were asked to submit a narrative description of their method. None of the teams reported the CO 2 impact of their participation in the task.

Many teams approached the task with transformer-based neural MT (NMT), relying on existing implementations. The use of prompting autoregressive models was also introduced this year. Table 3 presents details of the teams' methods.

Automatic evaluation

We present BLEU scores [START_REF] Papineni | Bleu: a method for automatic evaluation of machine translation[END_REF] for the automatic evaluation in Tables 4 and5. This includes translations received from both submission systems (Google Form and OCELoT).

For both en2de and de2en test sets, the submissions from HuaweiTSC, ZengHuiMT, GPT4-5shot, and PROMT teams obtained higher scores than our comparison system (ChatGPT) according to BLEU. The BLEU scores of the Lan-BridgeMT submissions (which use GPT3 and GPT4) came very close to those of ChatGPT for most language pairs, e.g., en2es, en2it, and were sometimes higher, e.g., fr2en, it2en, and ru2en. Most of the ONLINE system submissions also got higher BLEU scores than ChatGPT. However, it is worth bearing in mind the possibility that the ONLINE systems had previously seen our test sets in the large data on which they were trained, or were used by the authors to assist the production of the abstracts used in the test sets. Although we use the ChatGPT model based on data prior to 2022, meaning that it could not be trained on the parallel abstracts used in the test sets, it is also possible that ChatGPT was used by authors to produce the abstracts that form part of the test set.

Manual evaluation

We carried out a manual validation of the quality of the translations for some language pairs using the "3-way ranking" task in the Appraise tool. It consists of a pairwise comparison with three text spans, for example for en2pt: (i) the source text in English, (ii) translation A in Portuguese, and (iii) translation B also in Portuguese. The text is either a sentence or the whole abstract, i.e., we carried out the validation for each sentence and then for the complete abstract.

The evaluator should choose one of the following four options: (i) A=B, i.e., both translations have similar quality; (ii) A>B, i.e., translation A is better than translation B; (iii) A<B, i.e., translation A is worse than translation B; and (iv) error flag in case one or both of the translations do not refer to the same source text.

For the language pairs that we considered, we randomly selected the abstracts until we had at least 100 sentences. We restricted the abstracts to those in which the rate of well aligned (OK) sentences was at least 80%. We considered all pairwise combinations from the following translations: (i) the reference translation, as originally available in PubMed, (ii) translations from ChatGPT 3.5, and

(iii) translations from systems that directly took part on the Biomedical Translation Task, and not only on the General Task (see Table 2).

We present the results in Tables 6 and7. We compute a significance test (Wilcoxon test) when comparing the systems (or reference translation) and we show in bold and with a star (⊛) those cases in which one system (or the reference translation) was better than the other one.

None of the teams could outperform the reference translation for all of the language pairs. Further, for all language pairs that we checked, the quality of the translations from ChatGPT was similar to the reference translation at the sentence level, i.e., there was no significant difference in the results. However, on the abstract level, the ChatGPT translations were found to be better than the reference translations for some language pairs, namely, en2ru and fr2en.

For some of the languages (e.g. en2de), the rankings from the automatic and manual translations appear consistent. The BLEU score from the HuaweiTSC team was much higher than the one from Lan-BrigdeMT (0.43 versus 0.35), and indeed, the quality of the translations from HuaweiTSC was better than the ones from Lan-BrigdeMT. There are however some differences in rankings. For example the manual rankings do not correspond exactly to the automatic rankings for ru2en, fr2en and en2it. Notably, ChatGPT appears to be penalised by BLEU and does better in the manual rankings.

Quality of the translations

We discuss below, for some language pairs, some of the mistakes that we observed during the manual validation of the submissions.

en2de Similarly to the last few years, the quality of the translations into German was very high. Overall, the individual translations were often similar and differed only in nuances, such as the order of the syntactic constituents. Some models seemed to favour compound nouns more often than others (e.g., Lammellentrennung vs Trennung der Lamellen). However, this usually had no impact on the translation quality. Some systems translated idioms, such as "window of opportunity", literally into German. Especially specialist terms were translated differently by the individual models and it was rather challenging to judge which of the translated terms has better quality (see Example 1).

(1) en: The most common surgical fixation options are cerclages and screws, . . . de 1 : Die häufigsten chirurgischen Fixierungsoptionen sind Zerkel und Schrauben, . . . en2es As observed in the last few years, the overall quality of the translations into Spanish was very high. MT systems output was indistinguishable from human translations in many occasions for both systems evaluated: ChatGPT and Lan-Bridge.

The reference translation outperformed Lan-Bridge when evaluating sentences and abstracts. The reference translation was more consistent in the abstracts, had a higher fluency in the translation and a better choice of terminology than Lan-BridgeMT.

For example, "illness recurrence" was translated as "recurrencia' by Lan-Bridge, whereas the reference translation used a more appropriate term "recidiva". Another example in the translation of the term "coronary heart disease", that Lan-Bridge translates literaly as "enfermedad coronaria", while the reference translation uses the medical term "cardiopatía coronaria".

As mentioned, the reference translation was more fluent when compared to Lan-Bridge, oftetimes having a slightly better word order, better concordance subject/verb and using punctuation (commas and full stops) more fluently. Similarly, the reference translation slightly outperformed Chat-GPT when comparing abstracts.

However the baseline translation was better than the reference translation at sentence level, this was due to a more overall fluent and consistent translation of abstracts observed in the reference translation when compared to ChatGPT. It must be noted that ChatGPT performed very well compared to the reference translation in most abstracts evaluated manually.

In the following example ChatGPT used the correct punctuation for numbers above 1,000 in Spanish and the reference translation used the incorrect punctuation and was penalized for this fact.

(2) ChatGPT: Se incluyeron un total de 22,148 pacientes de 40 estudios.

Reference: Se incluyó un total de 22.148 pacientes de 40 estudios.

When compared against each other, ChatGPT outperformed Lan-Bridge both at the abstract level and at the sentence level. As with the reference translation, ChatGPT was more fluent, had a better choice of terminology (domain specific terms) and was more consistent overall at abstract level.

The ChatGPT translation was more fluent in the following example with a better usage of wording. Lan-bridge followed the English source text more closely which made the output less idiomatic.

(3) ChatGPT: IO redujo los niveles de glucosa en sangre, restableció el peso corporal y mejoró la sensibilidad a la insulina, así como la tolerancia a la insulina y a la glucosa en ratones diabéticos.

Lan-bridge: IO redujo los niveles de glucosa en sangre, restableció el peso corporal y mejoró la sensibilidad a la insulina junto con la tolerancia a la insulina y la tolerancia a la glucosa en ratones diabéticos.

While issues are still being observed by the MT systems evaluated manually this year, these are no longer major translation issues as in past years. The issues observed this year for the translations from English to Spanish were minor issues that affect the overall final quality, but can be remediated by editing the MT output to provide better terminology, specially domain specific, more fluent sentences and a better overall consistency in the translation (specially for abstracts).

en2fr Translation quality was somewhat uneven this year. While some translations were very high quality and often similar or identical to reference translations, others exhibited serious issues including inserting erroneous information (see Example 4) or conveying meaning drastically different (see Example 5) or opposite to the original sentence (see Example 6). This type of error can have a severe impact when it results in incorrect medical information (Example 6) or incorrect description of a social group (see Example 5).

(4) en: Analysis (. . . ) showed that. . . * taux sanguin de potassium inférieur à 6,5 mmol/L The translation of numerical values was also unreliable: example 5 illustrates the adequate translation of 6.5 mmol/L into 6,5 mmol/L, however in another abstract the study population of 52 dogs was erroneously translated by 54 chiens.

Issues remain with acronym translation where acronyms are often kept verbatim upon definition (e.g., developmental disabilities (DD) translated as troubles du développement (DD) instead of the reference translation troubles du développement (TD) although consistency seems improved: acronyms, albeit erroneous, are often used throughout a text.

The comparison of translations exhibiting different types of issues also remains difficult. In example 7, although enquête is a better translation for survey in the context, translation fr 1 was preferred to fr 2 because of the correct translation for asking about, which was central to the sentence. Overall, the one-to-one comparisons seemed quite consistent in ranking the systems and reference, and suggest that perhaps the most serious issues identified were concentrated in a few systems.

In addition to the manual evaluation through appraise, a complementary assessment of ChatGPT outputs was conducted, with a focus on Acronyms and Lab Values, which had been studied in our clinical case descriptions last year. We found that overall, 39 out of 50 test documents contained acronyms and only 3 contained lab values. The low frequency of lab values in the test set suggests that this particular source of translation difficulty for automatic system is not present in random scientifc abstracts. Furthermore, we cannot draw conclusions on the performance of ChatGPT on lab value translations. Acronym translations were considered correct when the ChatGPT translation was identical to the reference translation or consisted of an attested acronym use in similar context. Correct acronym translations (74%) included frequent acronyms such as CI (confidence interval), OR (odds ratio) or MRI (magnetic resonance imaging). In other cases, acronyms were either untranslated (16%) or erroneous (10%). These cases included acronyms for terms that were unfrequent or ad-hoc to the documents -albeit often a major topic. It should be noted that they were a source of inconsistent acronym translations in 14 documents -36% of test documents with acronyms.

fr2en Translation quality was good overall and sometimes indistinguishable from reference translations. Aside from a problem with certain words being dropped at the beginning of translations, sometimes mid-word (quite possibly due to a bug by one or several of the systems), the errors made were similar to previous years.

Term and acronym translation (see Example 8) remained a serious problem and one that was highly influential in reranking decisions, i.e. more so than other errors such as those involving grammar, style or naturalness. In addition to acronym translation errors, we also observed that acronym placement was not always coherent (e.g. an acronym not being defined at the first instance and used consistently afterwards), but in practice this did not influence reranking decisions because of the presence of more serious errors.7 (8) fr: La migraine est la maladie neurologique la plus fréquemment rencontrée. . . en 1 : Migraine is the most common neurological disorder. . . en 2 : *Mimine is the most frequently encountered neurological disease. . .

The translation of non-domain-specific terms also posed problem, either those that were ambiguous in context (Example 9), including pronoun translation (for example sa/son 'his/her/its/their' being translated as its rather than 'his/their' or involving some degree of polarity (Example 10). On a similar note, the omission of words, mainly adjectives and adverbs (e.g. relativement 'relatively' and souvent 'often') sometimes made the difference between two translations, as did missing final punctuation (when no other errors were present).

(9) fr: . . . les traitements oraux anciens. . . en 1 : . . . older oral treatments. . . en 2 : *. . . ancient oral treatments. . .

(10) fr: . . . un profil d'effets indésirables peu favorable en 1 : . . . an unfavorable adverse effect profile en 2 : *. . . a slightly favorable side effect profile.

Finally, as in previous years, not all reference translations of were entirely faithful to the French source abstract (paraphrasing, missing or added information). This resulted in some cases in the reference translation being ranked below a system output, including imperfect outputs. Caution should therefore be taken when drawing conclusions about translation quality concerning humans, since intentional paraphrasing by the authors resulted in good abstracts but inferior in terms of our manual evaluation criteria. This partly explains why ChatGPT is "better" than the reference translations for this language pair. en2it The quality of the translation was on average higher than the previous years. Most of the sentences compared was almost identical and fluent in terms of the quality of language. From a terminological viewpoint, it is possible to identify some inaccuracies in the choice of translating terms in the target language. For example, in tumour recurrence, the correct translation of recurrence is recidiva instead of ricorrenza.

Another frequent mistake, which is also a frequent mistake for language learners, is the translation of hair in sentences like "hair cortisol concentration (HCC) in healthy and ill cows". In these cases, hair must be considered as the hair of animals of body parts, therefore peli, and not scalp hair, in Italian capelli.

In some cases, there were better choices made by the reference system. For example, in the case of the phrase "[the author] is an initiate into the topic", ChatGPT used iniziato to translate initiate while a better equivalent would be in this case novizio as proposed by the reference system.

Finally, from a syntactic point of view, the results were very similar and only in a few cases we could find a construction that sounded odd or not easy to read. For example, the sentence "Flowmetry data always showed a more or less sudden disappearance of vasomotion." was translated by the reference system with I dati della flussometria hanno sempre mostrato una più o meno improvvisa scomparsa della vasomotricità while it would be more appropriate the translation of provided by the baselinte I dati di flussometria mostravano sempre una scomparsa più o meno improvvisa della vasomozione.

en2pt The results show that many translations, either from the referenc, ChatGPT, or from the Lan-BridgeMT team, were as good as the reference translation for many sentences (cf. Table 6, "Sentences"). However, there were many cases on which we decide that one passage was better than the other, we discuss some of these differences here.

The most serious mistake that we found was the translation of "back pain" into "pressão arterial" (blood pressure), probably because both of them have the same acronym in English, i.e., "BP".

(11) en: The high incidence and worsening of BP ... pt 1 : A alta incidência e agravamento do PC ... pt 2 : A alta incidência e o agravamento da pressão arterial ... Similar to previous years, we still found cases in which the English (or simply a wrong) acronym was used (cf. exmple below). Some similar errors might only be noticed when checking the complete text (abstract), and not only single sentences, such as when the translation includes an acronym that was not defined previously.

(12) en: ... Creutzfeldt-Jakob disease (CJD) ... pt 1 : ... doença de Creutzfeldt-Jakob (DCJ) ... pt 2 : ... doença de Creutzfeldt-Jakob (CJD) ...

In some cases, even though both passages were correct, we found that the translation was better due to the use or more medical concepts.

(13) en: ... headache attributed to ischemic stroke ... pt 1 : A cefaleia atribuída ao acidente vascular cerebral isquêmico ... pt 2 : ... a dor de cabeça atribuída ao derrame isquêmico ... Sometimes the translation included terms that were not suitable, even thought the meaning was close to the source, and it the might have been understood by many readers.

(14) en:

... which were analyzed fully and individually. pt 1 :

... que foram analisados na íntegra individualmente. pt 2 :

... que foram analisados de forma completa e individual.

We chose translation which better describe the facts, depending of the use active or passive voice. Further, in case of passive voice, we preferred caes in which the subjective is closer to the verb, or even before it. We find that it improves the readability. ru2en While the quality of ru2en translations continues to impress, one recurrent issue centers around the proper handling of abbreviations and acronyms. Often, an acronym is introduced early in the abstract, and holds a clear, defined meaning. Yet, as the text progresses, these acronyms are frequently mishandled by translation systems, failing to link them to their previously established acronym, and frequently transliterating an acronym created in Russian text. This issue manifests itself nearly every time an acronym appears, which makes translations of abstracts that include acronyms not consistently reliable. For example, the term Ischemic Stroke is introduced in the abstract and abbreviated to "ИИ" which corresponds to the Russian term "ишемического инсульта". One of the reference translations correctly uses the acronym IS to refer to Ischemic Stroke, while the other comes up with an unrelated abbreviation AI.

(17) ru: В исследование включили 120 пациентов (57 женщин и 63 мужчины, средний возраст 58,4±6,4 года) в позднем восстановительном периоде ИИ. en 1 : The study included 120 patients in the late recovery period of IS, 57 women and 63 men, average age 58.4±6.4 years. en 2 : The study included 120 patients (57 women and 63 men, median age 58.4±6.4 years) in the late recovery period of AI.

Conclusions

We presented the finding of the edition of the WMT Biomedical Translation Task. We received submission from 18 systems and compared them to translations from ChatGPT 3.5.

In the automatic evaluation, some systems were scored higher than BLEU according to the comparison system (ChatGPT 3.5). In the manual evaluation, none of the systems were systematically better than the reference translation for all of the language pairs that we evaluated. However, in a couple of cases, namely, for fr2en and en2ru, the translations from ChatGPT were preferred over the reference translations. We presented a details discussion of the errors that we found during the manual evaluation.

Limitations

Our test sets comprise 50 abstracts per language pair/directions. Further, due to the time consuming, difficulty of the task, and number of submissions, the manual evaluation was only carried out for a small sample. However, since our task has been running for eight years, the cumulative number of test sets is satisfactory for testing purposes, and maybe even for few-shot training approaches.

We did not carry out manual evaluation for some of the language pairs (directions), e.g., it2en, for which we do not have experts who are native speakers in the target language and have a very good knowledge in the source language. However, we always release the test sets and the submission files from the participants, with which anyone can carry out further experiments or manual evaluations.

Ethics Statement

Our test sets were derived from PubMed, a database of biomedical citations. These publications are often used in many areas of the medicine, including decision about diagnostic and treatment of patients. Automatic translation in this domain should be used as part of a larger framework that should include human experts for the interpretation of the translations and, if necessary, correct and adapt the text accordingly.

de 2 :

 2 Die häufigsten chirurgischen Fixierungsmöglichkeiten sind Zuggurte und Schrauben, . . . de 3 : Die häufigsten operativen Fixationsmöglichkeiten sind Cerclagen und Schrauben, . . .

  fr 1 : L'analyse (. . . ) a montré que. . . fr 2 : * L'analyse (. . . ) a montré que. . . (Traduit par Docteur Serge Messier) (5) en: The criminalization of Black people fr 1 : La criminalisation des Noirs fr 2

( 7 )

 7 en: A survey asking about training fr 1 : Un sondage demandant des informations sur la formation fr 2 : * Une enquête demandant une formation

( 15 )

 15 en: The patients underwent magnetic resonance imaging. pt 1 : Os pacientes realizaram ressonância magnética. (active voice) pt 2 : Os pacientes foram submetidos a ressonância magnética. (passive voice) (16) en: Twelve articles were included in the analysis. pt 1 : Foram incluídos na análise 12 artigos. pt 2 : Doze artigos foram incluídos na análise.

Table 1 :

 1 Statistics (number of sentences and percentages) of the automatic alignment quality of the MEDLINE test sets.

	Language	OK Source>Target Target>Source	Overlap	No Align. Total
	de2en	352 (82.2%)	20 (4.7%)	12 (2.8%)	9 (2.1%)	35 (8.2%)	428
	en2de	471 (87.7%)	28 (5.2%)	9 (1.7%) 11 (2.0%)	18 (3.4%)	537
	es2en	412 (89.5%)	16 (3.5%)	11 (2.4%)	-	21 (4.6%)	460
	en2es	388 (88.4%)	21 (4.8%)	15 (3.4%)	6 (1.4%)	9 (2.0%)	439
	fr2en	215 (85.3%)	17 (6.7%)	10 (4.0%)	7 (2.8%)	3 (1.2%)	252
	en2fr	432 (83.7%)	78 (15.1%)	4 (0.8%)	-	2 (0.4%)	516
	it2en	310 (73.4%)	46 (10.9%)	23 (5.5%)	6 (1.4%)	37 (8.8%)	422
	en2it	298 (67.0%)	33 (7.4%)	29 (6.5%) 12 (2.7%)	73 (16.4%)	445
	pt2en	385 (93.7%)	6 (1.4%)	7 (1.7%)	9 (2.2%)	4 (1.0%)	411
	en2pt	450 (90.6%)	21 (4.2%)	12 (2.4%)	9 (1.8%)	5 (1.0%)	497
	ru2en	233 (70.0%)	30 (9.0%)	16 (4.8%) 10 (3.0%)	44 (13.2%)	333
	en2ru	221 (52.9%)	44 (10.5%)	23 (5.5%) 18 (4.3%) 112 (26.8%)	418

Table 2 :

 2 List of the participating teams and systems. The third column indicates the teams that directly participated on the Biomedical Translation Task.

	Team ID	Language pair MT method	Trained Fine-	BT LM
						Tuned
	AIRC	en/de		Ensemble of Mega transformer	Yes	No	Yes Yes
				models
	GTCOM	en/de		Transformer model	-	-	-	multilingual
								models
	HuaweiTSC	en/de		Transformer model	-	-	-	-
	Lan-BridgeMT	en/de,	en/es,	GPT prompting	No	No	No	GPT3, GPT4
		en/fr,	en/it,
		en/pt, en/ru
	NRPU_FJWU	en/fr		Fairseq NMT	No	Yes	No	No
	PROMT	en/ru		Marian NMT	Yes	No	-	-
	UPCite-CLILLF en/fr		MBart-50	No	Yes	No	No
	USTC	en/fr		Fairseq NMT	Yes	No	No	No
	ZengHuiMT	en/de, en/ru	many-to-many encoder decoder	-	-	-	-
				transformer model

Table 3 :

 3

Overview of methods used by participating teams. Information is self-reported through the Google/Ocelot submission form for each selected "best run". BT indicates if backtranslation is used and LM if language models were used.

Table 4 :

 4 BLEU scores for "OK" aligned test sentences, from English. The submissions without a run number are the ones that were submitted to OCELoT. Primary runs are marked by *.

	Teams	Runs	en2de	en2es	en2fr	en2it	en2pt	en2ru
	AIRC		0.3443
	GPT4-5shot		0.3881					0.3649
	HuaweiTSC	run1* *0.4369
	HuaweiTSC	run2	0.4345
	HuaweiTSC	run3	0.4422
	Lan-BridgeMT		0.3463 0.5098	0.5164 0.4640 0.4832 0.3361
	NLLB_Greedy		0.3663					0.3461
	NLLB_MBR_BLEU		0.3625					0.3504
	ONLINE-A		0.4332					0.4125
	ONLINE-B		0.4298					0.4648
	ONLINE-G		0.4263					0.3939
	ONLINE-M		0.3984					0.3827
	ONLINE-W		0.4451					0.4083
	ONLINE-Y		0.4075					0.4049
	PROMT							0.3872
	UPCite-CLILLF				0.2706
	ustc_ml_group	run1			0.4908
	ustc_ml_group	run2*			*0.4998
	ZengHuiMT		0.3883					0.3775
	ChatGPT		0.3851 0.5097	0.5318 0.4607 0.5098 0.3513
	Teams	Runs	de2en	es2en	fr2en	it2en	pt2en	ru2en
	AIRC		0.3714
	GPT4-5shot		0.4371					0.4774
	GTCOM_Peter		0.4212
	HuaweiTSC		0.4771
	HuaweiTSC	run1* *0.4778
	HuaweiTSC	run2	0.4776
	HuaweiTSC	run3	0.4853
	Lan-BridgeMT		0.4215 0.5769	0.4323 0.5272 0.5569 0.4750
	NLLB_Greedy		0.4040					0.4386
	NLLB_MBR_BLEU		0.3992					0.4437
	NRPU_FJWU	run1*			*0.3350
	NRPU_FJWU(1)	run1			0.3082
	NRPU_FJWU	run2			0.2202
	NRPU_FJWU	run3			0.2395
	NRPU_FJWU(1)	run3			0.3350
	ONLINE-A		0.4606					0.5723
	ONLINE-B		0.4662					0.4648
	ONLINE-G		0.4364					0.5445
	ONLINE-M		0.4465					0.4607
	ONLINE-W		0.4759					0.4919
	ONLINE-Y		0.4075					0.5089
	PROMT							0.5156
	UPCite-CLILLF
	ustc_ml_group	run1*			*0.4124
	ustc_ml_group	run2			0.3854
	ZengHuiMT		0.4316					0.5256
	ChatGPT		0.4360 0.5827	0.4263 0.5067 0.5915 0.4417

Table 5 :

 5 BLEU scores for "OK" aligned test sentences into English. The submissions without a run number are the ones that were submitted to OCELoT. Primary runs are marked by *.

Table 6 :

 6

	Lang. dir. Pair		Abstracts				Sentences
			Total A>B A=B A<B	Total	A>B A=B A<B
	en2de	HuaweiTSC vs. reference	10	0	6	⊛ 4	100	25	57	17
		HuaweiTSC vs. Lan-BridgeMT	10	⊛ 7	2	1	100	⊛ 41	54	5
		HuaweiTSC vs. ChatGPT	10	5	3	2	100	⊛ 29	59	12
		reference vs. Lan-BridgeMT	10	6	3	1	100	⊛ 32	54	3
		reference vs. ChatGPT	10	3	6	1	100	18	64	17
		Lan-BridgeMT vs. ChatGPT	10	0	3	⊛ 7	100	10	61 ⊛ 29
	en2es	ChatGPT vs. Lan-BridgeMT	13	4	6	3	107	21	71	15
		ChatGPT vs. reference	13	3	6	4	107	22	65	20
		Lan-BridgeMT vs. reference	13	1	6	6	107	14	69	24
	en2fr	reference vs. Lan-BridgeMT	10	⊛ 9	0	1	108	⊛ 80	7	21
		reference vs. ChatGPT	10	7	1	2	108	⊛ 71	5	32
		reference vs. UPCite-CLILLF	10 ⊛ 10	0	0	108 ⊛ 107	0	1
		reference vs. ustc_ml_group	10	⊛ 9	0	1	108	⊛ 85	1	21
		Lan-BridgeMT vs. ChatGPT	10	1	5	4	108	24	24 ⊛ 60
		Lan-BridgeMT vs. UPCite-CLILLF	10 ⊛ 10	0	0	108 ⊛ 105	3	0
		Lan-BridgeMT vs. ustc_ml_group	10	⊛ 8	1	1	108	⊛ 54	23	31
		ChatGPT vs. UPCite-CLILLF	10 ⊛ 10	0	0	108 ⊛ 103	3	2
		ChatGPT vs. ustc_ml_group	10	⊛ 9	1	0	108	⊛ 73	14	20
		UPCite-CLILLF vs. ustc_ml_group	10	0	0 ⊛ 10	108	7	4 ⊛ 97
	en2it	Lan-BridgeMT vs. ChatGPT	15	2	1 ⊛ 12	92	16	29 ⊛ 47
		Lan-BridgeMT vs. reference	15	4	1	10	92	25	31	36
		ChatGPT vs. reference	15	9	1	5	92	24	31	37
	en2pt	reference vs. Lan-BridgeMT	11	⊛ 5	6	0	105	35	45	25
		reference vs. ChatGPT	11	4	4	3	105	25	48	32
		Lan-BridgeMT vs. ChatGPT	11	1	5	5	105	18	62	25
	en2ru	reference vs. ChatGPT	13	4	3	6	94	8	60 ⊛ 25
		reference vs. Lan-BridgeMT	13	5	4	4	94	22	47	25
		ChatGPT vs. Lan-BridgeMT	13	7	3	3	94	20	64	10
	Lang. dir. Pair		Abstracts				Sentences
			Total A>B A=B A<B	Total A>B A=B A<B
	fr2en	NRPU_FJWU vs. reference	19	1	0 ⊛ 18	108	18	6 ⊛ 83
		NRPU_FJWU vs. ustc_ml_group	19	1	1 ⊛ 17	108	19	11 ⊛ 78
		NRPU_FJWU vs. ChatGPT	19	0	0 ⊛ 19	108	3	8 ⊛ 97
		NRPU_FJWU vs. Lan-BridgeMT	19	3	3 ⊛ 13	108	25	11 ⊛ 72
		reference vs. ustc_ml_group	19 ⊛ 12	4	3	108	47	26	34
		reference vs. ChatGPT	19	5	7	7	108	30	26 ⊛ 51
		reference vs. Lan-BridgeMT	19 ⊛ 15	1	3	108 ⊛ 60	19	28
		ustc_ml_group vs. ChatGPT	19	0	1 ⊛ 18	108	13	39 ⊛ 56
		ustc_ml_group vs. Lan-BridgeMT	19	9	3	7	108	45	26	37
		ChatGPT vs. Lan-BridgeMT	19 ⊛ 19	0	0	108 ⊛ 69	30	9
	ru2en	ChatGPT vs. reference	13	3	6	4	75	20	41	14
		ChatGPT vs. Lan-BridgeMT	13	⊛ 7	5	1	75 ⊛ 34	37	4
		reference vs. Lan-BridgeMT	13	⊛ 9	4	0	75 ⊛ 42	27	6

Pairwise manual evaluation results for the MEDLINE abstracts test set (from English). We show in bold (and with ⊛) the values which were statistically significant (Wilcoxon test).

Table 7 :

 7 Pairwise manual evaluation results for the MEDLINE abstracts test set (into English). We show in bold (and with ⊛) the values which were statistically significant (Wilcoxon test).

https://ftp.ncbi.nlm.nih.gov/pubmed/ updatefiles/

Comparison system -ChatGPT 3.5Instead of providing a baseline this year, we choose to provide translations from the ChatGPT 3.5

https://nlp.cs.nyu.edu/GMA/

https://ocelot-wmt23.mteval.org/

https://platform.openai.com/docs/models/ gpt-3-5

This could be something to look out for in future years when evaluating whole abstracts, when the translation quality allows such fine-grained observations.

Acknowledgements

Rachel Bawden's participation was funded by her chair position in the PRAIRIE institute funded by the French national agency ANR as part of the "Investissements d'avenir" programme under the reference ANR-19-P3IA-0001 and by the Emergence project, DadaNMT, funded by Sorbonne Université.


B Bouilly

T Sim

R Alami

A Numerical Technique for Planning Motion Strategies of a Mobile Robot in Presence of Uncertainty

This paper addresses the problem of planning the motions of a circular mobile robot moving amidst polygonal obstacles with uncertainty in robot control and sensing. The robot is equipped with sensors which, if properly used, may provide information to overcome the uncertainty accumulated during the motions. The position sensor is based on dead-reckoning, the error then results into a cumulative uncertainty. A proximity sensor may be used to localize the robot with respect to the obstacles of the environment. The robot can also gain information by entering inside landmark areas where the position error is assumed to be bounded. We describe a planner which produces robust motion strategies composed of sensor-based motion commands which guarantee that, given an explicit model of the error accumulated by the motion commands, the robot can reach safely its goal with an error lower than a pre-speci ed value. It is based on a propagation of a numerical potential and on a geometric analysis of the reachability of environmental features. This planner exhibits a set of powerful capabilities: while it allows to consider motion primitives which accumulate uncertainty, it is able, whenever possible, to navigate without relocalizing the robot when the task does not impose it, and also to make a proper use of the sensors. Several examples run with the planner are presented at the end of the paper.

Introduction

Robot motion planning has received a widespread attention over the past decade 12]. Dealing with uncertainties constitutes an important issue of the motion planning problem since robots operating in real world settings, are faced to several sources of uncertainties arising from control errors, limited sensing accuracy and inaccurate models of the environment. Consequently, the use of motion planners which do not take explicitly into account uncertainties is limited to simple situations where the errors remain small with respect to the task tolerances. This cannot be the case neither in assembly planning nor in the context of mobile robot navigation which constitutes a challenging problem for motion planning with uncertainty.

Indeed, mobile robots are not generally equipped with an absolute localization procedure and accumulate position errors (since the error cannot be bounded, a growing of the obstacles is not su cient). To overcome the uncertainty accumulated during the motions, the mobile robot has to be equipped with sensors that can provide additional information by identifying appropriate features of the environment. Among all the collision free paths which may connect two given con gurations of the robot, only some of them may allow, at execution, to acquire enough information from the sensors and reliably guide the robot toward its goal. Dealing with uncertainty in control and sensing may therefore completely change the strategy used to plan the motions and it is preferable to reason in advance on the capacity of the available sensing functions, to generate a robust motion plan composed of sensor-based motion primitives.

In this paper we propose a motion planner for a circular mobile robot moving in a polygonal environment in presence of uncertainty in both sensing and control. Given an explicit model of the error accumulated by a set of motion primitives, the planner produces robust motion strategies composed of a sequence of primitives which guarantee that the robot will reliably reach its goal with an error lower than a pre-speci ed value. The main originality of the approach is to consider a set of motion commands which accumulate uncertainty and to plan the corrective sensor-based motions needed to reduce this uncertainty.

We addressed a similar problem in 1] for a point robot. This planner succeeded in solving a large class of problems. However, it was limited to explore situations where the robot sought systematically the contact with the obstacles to localize and it was also difcult to add new sensor modalities since it involved rather complex geometric computations. The planner proposed here exhibits more powerful capabilities: it is able, whenever possible, to navigate without relocalizing the robot when the task does not impose it, and also to combine several sensor modalities.

The paper is organized as follows. In Section 2, we brie y discuss related work. Section 3 de nes more precisely the problem we propose to tackle and Section 4 describes the construction of the numerical potential which is used by the planner. Finally, some simulation results are presented at the end of the paper.

Related Work

Motion planning with uncertainty has already attracted a lot of interest, especially in the context of automatic assembly. The reader may refer to a very interesting state of the art and discussion in 12,[START_REF] Latombe | Robot Motion Planning[END_REF][START_REF] Fox | Exploiting visual constraints in the synthesis of uncertainty-tolerant motion plans (parts I & II)[END_REF] for a detailed analysis of the relevant literature. Two main approaches have been proposed:

In the two-phase approach, a motion plan is rst generated assuming no uncertainty and then, this plan is analyzed and patched in order to nally produce a robust task plan. The analysis is mainly based on the propagation of uncertainty through the plan and its consequences on plan correctness [START_REF] Takeda | Sensory uncertainty eld for robot navigation[END_REF][START_REF] Lazanas | Landmark-based robot navigation[END_REF]2,[START_REF] Mazon | Representation and propagation of positioning uncertainties through manipulation robot programs[END_REF][START_REF] Taylor | Synthesis of manipulator control programs from task-level speci cations[END_REF][START_REF] Lozano-Perez | Automatic synthesis of ne motion strategies for robots[END_REF]. The plan is then modi ed by inserting complementary actions or sensor readings allowing to reduce uncertainty. The main interest of such an approach is that it can be applied to problems which can be more general than motion planning (e.g. assembly, manipulation) and to robots with a high number of degrees of freedom. However, the a priori decomposition of the planning process and the assumption that the plan can be locally patched, can be too restrictive for the context of mobile robot navigation.

The second approach is the preimage backchaining approach, originally proposed by 16] and analyzed or extended through several contributions 9, 7, 4, 12, 13]. It is based on the geometry of the Con guration Space. The underlying assumption is that it is necessary to take uncertainty explicitly into account in the planning process itself since it can have drastic consequences on the plan structure. Informally, a preimage of a given goal (subset of the C-space), is a set of free con gurations from which a commanded motion is guaranteed to reach and terminate in the goal. Given a goal region and a start region, preimage backchaining consists in nding a sequence of commands such that the inverse sequence allows an iterative construction of preimages starting from the goal and resulting in a preimage containing the initial region.

While this problem, in its general formulation gives a useful computational framework, it raises \discouraging" complexity issues 4]. However this, by no means, a ects its interest. It remains to nd relevant instances of the general problem:

which integrate new sensor modalities (proximity sensors, vision) and control algorithms 3, 10]; which provide sub-classes of the problem with \better" properties 14];

or which allow to implement algorithms of practical use even though they are not complete 1, 6].

The instance of the problem addressed in this paper and the algorithm that we propose fall in these categories. Note that we also need more elaborate models of di erent sensor modalities in order to compute where (in the C-Space) they can be used, and to determine the nature of the measure they can provide together with its (pre-computed) estimated uncertainty. This should of course be done, taking into account the sensor characteristics (position relative to the robot frame, range, specularity. .. ) in a given environment 8, 19, 5].

Problem Statement

The robot and its environment

We consider a circular robot A that can translate freely in the plane among polygonal obstacles. We assume for simplicity that the environment is perfectly known. A con guration q = (x; y) is represented by the cartesian coordinates of the disc center and the Cobstacles simply correspond to the union of the generalized polygons obtained by growing the obstacles by the radius r of the robot. The environment possibly contains polygonal landmarks regions which are supposed to have a null intersection with the obstacles.

The motions of the robot are a ected by control errors: when A is commanded to move in a given direction, the maximal deviation between the actual motion and the desired one is modelled by a control uncertainty cone.

Uncertainty in sensing

We consider that the robot is equipped with the following sensors:

The position sensor is based on dead-reckoning. This technique is known to be quite sensitive to various kinds of errors and it can yield to large and cumulative errors. We model this error by an uncertain position p = (q; (q)) corresponding to a disk centered at the sensed con guration q and having a radius (q) = K:D(q; q I )+ (q I ) which linearly depends on the distance D(q; q I ) crossed by the robot from its initial con guration q I . The constant K is related to the precision of the position sensor.

The proximity sensors (or bumpers) allow to localize the robot with respect to the environment by detecting edges of the obstacles or corners made by two such adjacent edges. The information provided by such sensors is supposed to be perfect. Therefore, when a known edge is detected, the error is reset along the direction orthogonal to the edge. In this case, the uncertain position p = (q; (q)) is a segment of length 2 (q) and aligned with the edge.

The polygonal landmarks represent regions where speci c sensors (eg. vision based) can be used to detect natural or man-made features in the environment. Inside these landmark areas, the uncertainty in the measurement is modelled by a disc of xed radius L centered at the sensed position p = (q; L ).

Model of the motion primitives

The available motion primitives built upon these sensors are modelled by the type of initial situation where they can be applied, the nal situation they can reach and the envelope of possible actual trajectories they can induce.

Motions in free-space

Move(x; y) corresponds to a nominal straight-line motion executed in position-controlled mode. Figure 1 shows the envelope of actual motions which can be executed by the robot due to error accumulation. Note that this primitive can only be used between two uncertain positions such that this envelope grown by the robot radius r completely lies in free-space.

Move to W all( ) also accumulates errors but it terminates when a contact is detected by the proximity sensor (Fig 1). To avoid major localization mistake, this primitive should only be applied from a position which guarantees a correct termination onto the expected edge. The Move Landmark(x; y) primitive can be applied from any position p = (q; (q)) such that the disk robot grown by the uncertainty (q) is included in the landmark (Fig. 2). When this primitive starts, the uncertainty is reset to L and it remains constant while the robot navigates inside the landmark. 3).

The Follow to Corner( left; right]) primitive is similar but it terminates when a corner is detected. Matching the detected corner against the environment model allows to reduce the position uncertainty to zero.

Finally, the Switch Wall() command is used for the case of convex corners, to switch between the two edges by maintaining the contact with the corner.

Follow

Follow to Corner Switch Wall Given an initial position p I = (q I ; I ) of the robot (ie. the robot can be anywhere inside the disk region of radius I and centered at q I ), the problem is to generate a motion plan (eg. a sequence of the available motion primitives) whose execution guarantees that the robot will not collide with the obstacles and will reach a nal position q F with an error less than a pre-speci ed value F . The planner described below solves this problem by propagating a numerical potential over a bitmap superposed to the workspace and by using the polygonal model of the obstacles for a geometric analysis of the reachability of obstacle edges by Move to W all primitives.

Workspace bitmap

The planner rst computes a distance bitmap according to a classical \wavefront expansion algorithm" similar to the one described in 12]: The pixels lying under the edges of the obstacles are rst identied and their distance is set to zero. The distance of their neighbors is then set to 1 and so on until all the free regions of the workspace have been explored. In order to decrease the approximation introduced by the L 1 metric, we alternatively consider the 1-and 2neighborhoods at each step of the propagation. This allows a better approximation of the iso-distance circle by an octagonal shape.

Building the potential

The potential function is de ned over a grid, superposed to the 2-dimensional con guration space of the robot. The potential of a given grid point corresponds to the smallest uncertainty allowing to reach this position from p I . The potential grid is iteratively lled, starting from the initial position, by the propagation algorithm described below. The basic structure used by the algorithm is a node structure which contains the following information: a grid point and the uncertainty accumulated to reach this point from the initial position, the distance crossed by the robot along the motion plan which produced this uncertainty, the parent node from which it was propagated, a label in the set fFree, Landmark, Edge, V ertexg which indicates whether the disk robot grown by its uncertainty completely lies in freespace, in a landmark region or corresponds to a contact with an edge or a vertex of the environment obstacles. The algorithm also maintains in a list OPEN, the nodes that will be possibly considered during the propagation. This list is sorted by increasing value of the node's distance and it is initialized with the node associated to the position p I . At each step of the propagation, the algorithm examines the 2-neighbors of the rst node in the OPEN list and it only retains the neighbors which satisfy the two following conditions:

The uncertain position p = (q; (q)) (a disk or a segment) grown by the radius of the disk robot is collision-free with respect to the obstacles. The distance bitmap provides an e cient way to check this condition.

The potential (q) computed for the neighbor is smaller than the potential currently stored at this position in the potential grid.

The di erent elds of the retained neighbors (distance, label, parent) are updated and these points are inserted in OPEN according to their distance value.

The evaluation of the uncertainty associated to a given neighbor depends on both the uncertainty and the label of the current node. For example, when the node is labelled Free, the value of is incremented by K: (resp. p 2K: ) for its 1-neighbors (resp. 2neighbors) where denotes the size of the grid points.

When the propagation reaches a point p = (q; ) such that the disk of radius r + (q) is included in a landmark region, the uncertainty is reset to the value L of the landmark and it remains constant for all the neighbors such that the disk of radius r + L lies inside the landmark. Obstacle relocalizations are taken into account in the following way: each time the algorithm detects a neighbor that does not verify the collision-free condition because of a too large uncertainty (ie. the current node lies on the boundary of the Free nodes), a visibility test is performed to determine the edges that can be reliably reached from this position by a Move to Wall primitive (Fig. 4). When this test succeeds1 for a given edge, a node is created at a position deduced from the intersection between the edge and the visibility cone associated to the Move to Wall primitive. This node is labelled Edge and its parent is set to the node which was currently propagated. Finally, when the propagation of such Edge nodes reaches a vertex, the uncertainty is reset to zero for the corresponding neighbor. Elsewhere, the uncertainty is incremented as for the nodes having a Free label.

The algorithm terminates when the goal point is reached with an admissible uncertainty (success) or when the list OPEN is empty (failure).

Computing the motion plan

When the propagation algorithm succeeds, the motion plan can be computed as follows: a \bitmap path" is rst deduced by following the parents from the goal node, back to the initial one. The motion primitive used between two adjacent points along this path is determined from the labels of the nodes (cf. The sequence of wall-following primitives along the same edge can be easily fused into a single motion primitive (Follow or Follow to Corner) followed by a Switch W all or a Move command. The path portions associated to free-space motions (Move or Move Landmark) are replaced by a smaller sequence of longer straight-line motions. The algorithm used for this \smoothing" of the path guarantees that the produced motion primitives remain collision-free with the obstacles according to the model of the error accumulated by the primitives.

Remarks on the algorithm

Complexity: As previously mentioned, a given node is possibly propagated (ie. inserted in OPEN) only when it allows to decrease the uncertainty of the associated point in the potential grid. Therefore, in the absence of landmark or obstacle relocalization, each point is guaranteed to be propagated only once, since in this case, the uncertainty increases at each iteration of the algorithm.

Each of the l landmarks (resp. s obstacle vertices) can possibly create a local minimum of the potential when it is used for a relocalization, by reseting to L (resp. 0) the uncertainty of a grid region (resp. point). Each relocalization can generate only once a new wave of propagation which stops when it cannot decrease anymore the uncertainty of any neighbor. In the presence of relocalizations, a given point of the grid potential can be therefore propagated in the worst case l+s+1 times and the algorithm is guaranteed to terminate. In practice, this number averaged over the propagated points, is much lower (see Table 2).

Properties: Each iteration of the propagation algorithm rst develops the nodes having the smallest distance. Therefore, when the algorithm succeeds (ie. the propagation reaches the goal with an uncertainty lower than F ), the solution corresponds to the nearoptimal motion with respect to the distance crossed by the robot along the nominal path.

In the other case, the propagation stops when the list OPEN is empty and all the possible localizations have been tried. Hence, if the solution was not found because the goal position was attained with a too large uncertainty, the associated goal node can be used to get the motion plan which minimizes the uncertainty.

Finally, when the problem is too constrained for connecting both initial and nal positions by a robust motion plan, the regions of the potential grid attained by the propagation correspond to the workspace regions that can be reliably reached by the robot.

Simulation Results

The above method was implemented in C on a Silicon Graphics Indy workstation. We ran the planner on several examples with workspaces containing both polygonal obstacles/landmarks and using di erent types of motion strategies. The size of the bitmap grid was chosen equal to 256 256 in the examples presented in Figure 5 which illustrates some of the results obtained. For each example, the right gure shows the workspace and the nominal motion plan produced by the planner (the disk robot is displayed at the goal position). The regions reached by the propagation of the potential are displayed on the left gures which also show the robot grown by the uncertainty accumulated along the free-space portions of the motion plan. Computation times and other simulation results are given in Table 2. Sensorless motion strategies: In the rst example, the planner is given a large value for the bounded nal uncertainty. The workspace contains no landmark region and the obstacle edges are too small to be reliably reached by Move to Wall commands. Hence, the obstacles cannot be used to localize the robot. Despite the error accumulation induced by the Move primitives, the motion plan found by the planner is simply composed by a sequence of seven such primitives. This plan is guaranteed to be collision-free and it allows to reach the goal with a su cient precision.

In uence of landmarks: The second example illustrates the in uence of landmark areas (the three grey rectangles). Starting from a position in the topright corner of the workspace, the plan should allow to reach the room of the lower-right corner with an uncertainty su ciently small to reliably pass the small doorway. The strategy rst leads the robot to cross a rst landmark region and then to reach the two others (each being accessible only from the previous one), which nally makes the goal accessible. The motion primitives used to execute this path are Move(x; y) to enter landmark areas and Move Landmark(x; y) when moving inside these areas.

In uence of obstacle relocalizations: The two last examples show the e ect of the relocalizations obtained by the wall following primitives in the motion plans produced by the planner. Both examples were run with the same workspace and between the same robot positions. In the rst case, the strategy is aimed at minimizingthe length of the nominal path. Relocalizations only occur when the uncertainty accumulated during the Move commands becomes too important. The other example was run by minimizing the uncertainty instead of the distance crossed by the robot.

Conclusion

This paper described a motion planner for mobile robot navigation in presence of uncertainty. A numerical potential allows to propagate the error accumulated during free-space motions and also to take into account the e ect of possible relocalizations by using external sensors. A geometric analysis of the reachability of environmental features determines where these sensors can be used to guarantee that they will not be confused at execution by other similar features, which may be a source of major localization mistakes. The planner has been tested on several examples and the simulation results demonstrate its ability to nd rather complex motion plans in a very reasonable amount of time.

Despite its relative simplicity, the planner exhibits a set of powerful capabilities not provided by earlier similar planners: it considers sequences of motion primitives which accumulate uncertainty and it combines several sensor modalities. A nice property of the approach is also that, whenever possible, it leads to navigate without relocalizing the robot when the task does not impose it (free-space motions may be faster than wall-following and seeking for contact). Finally, another advantage of this technique compared to more complex geometrical methods may be its potential ability to take into account more easily additional sensor modalities in a single framework. We are working on such extensions and on relaxing some assumptions currently made by the planner. In particular, it would be interesting to replace the circular model of the position error in free space by a directional uncertainty in order to precisely model the e ects of the obstacle relocalizations through the motion plan. We also plan to implement the sensor-based primitives used by the planner in order to conduct experiments in real world settings and to establish the e ectiveness of the approach in producing robust motion plans that can be reliably executed by a real robot.

  this work is supported by the CEC Esprit 3 Project 6546 PROMotion

Figure 1 :

 1 Figure 1: Error accumulated during free-space motions

Figure 2 :

 2 Figure 2: Localization with the Move Landmark command

Figure 3 :

 3 Figure 3: Localization with the wall following primitives

Figure 4 :

 4 Figure 4: Edge visibility

Figure

  Figure 1 2 3 4 Uncertainty rate 8 % 4 % 13 % 13 % Relocalization none landmark obst obst Total distance 29.5m 89.8m 37.5m 56.9m Uncertainty max 2.4m 1.2m 1.7m 0.9m Averaged (Max) 1 2.1 1.7 1.1 propagation/point (1) (4) (5) (3) CPU time 2.5s 6.5s 19.8s 12.5s

Figure 5 :

 5 Figure 5: Paths generated by the planner

Table 1 :

 1 Table 1). Label transitions This solution is then transformed into a motion plan containing a reasonable number of primitives.

	Initial label Final label Motion primitive Landmark Landmark Move Landmark Free Edge Move to Wall Edge V ertex Follow to Corner Edge Edge Follow V ertex Edge Follow V ertex V ertex Switch Wall Other transitions Move

Table 2 :

 2 Simulation results

if not, the neighbor is eliminated


Fabien Gravot

Rachid Alami

Thierry Simeon

Thierry Siméon

Playing with several roadmaps to solve manipulation problems

. Indeed, we are convinced that a higher level of problems complexity, and particularly those involving multiple robots and multiple objects, will be accessible thanks to the introduction of a symbolic reasoning level.

The resolution scheme relies on Probabilistic Roadmap Methods (PRMs) and on a reasoning level that adaptatively controls the construction and extension of a number of roadmaps.

We consider this symbolic level as a step towards a systematic approach to integrate task planning and geometric planning in better conditions than trough a gross, and somewhat, artificial hierarchical decomposition.

This paper describes the main ingredients of the proposed framework, and its first results.

Introduction

The Problem. We address the manipulation planning problem [START_REF] Alami | A geometrical Approach to planning Manipulation Tasks. The case of discrete placements and grasps[END_REF]. We have developed a resolution scheme that is able to build plans for a wide range of manipulation problems and that is aimed to be the basis for future work on multi-robot manipulation. The current implementation is already able to deal with manipulation problems involving one robot (holonomic or not) with one movable object and continuous grasps and placements [START_REF] Siméon | A Manipulation Planner for Pick and Place Operations under Continious Grasps and Placements[END_REF][START_REF] Sahbani | A Probabilistic Algorithm for Manipulation Planning under Continuous Grasps and Placements[END_REF]. The presence of objects that can only be moved by the robot leads to complex instances of the motion planning problem. Indeed, the robot may be forced because of kinematic constraints or because of collision avoidance to find intermediate positions and re-grasping steps for the movable object.

Motion planning [START_REF] Latombe | Robot Motion Planning[END_REF] is a challenging problem that involves dealing with elaborate physical constraints and high-dimensional configuration spaces. The fastest existing deterministic planner has a complexity exponential in the number of degrees of freedom of the robot. On the other hand, a class of randomized planners, in particular, Probabilistic Roadmap Methods (PRMs) [START_REF] Kavraki | Ramdomized preprocessing of configuration space for fast path planning[END_REF][START_REF] Nissoux | Visibility based probabilistic roadmaps[END_REF], have been used successfully in high-dimensional configuration spaces. More recently, the use of several roadmaps to solve motion planning with kinematic constraints [START_REF] Han | A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems[END_REF][START_REF] Valle | A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains[END_REF] or manipulation tasks [START_REF] Siméon | A Manipulation Planner for Pick and Place Operations under Continious Grasps and Placements[END_REF][START_REF] Sahbani | A Probabilistic Algorithm for Manipulation Planning under Continuous Grasps and Placements[END_REF], have been proposed. In our approach, we develop a resolution scheme based on a number of methods for reasoning on roadmaps construction and handling.

The Key Ideas. The planner will be based on an "adaptative" search on various roadmaps. Each roadmap type is built with specific random and local path functions.

Planning generally involves several distinct elementary tasks. In the manipulation context, performing an object transfer or a transit motion between two grasps, are two distinct task types that must be treated separately and combined in a precise way [START_REF] Alami | A geometrical Approach to planning Manipulation Tasks. The case of discrete placements and grasps[END_REF][START_REF] Siméon | A Manipulation Planner for Pick and Place Operations under Continious Grasps and Placements[END_REF][START_REF] Sahbani | A Probabilistic Algorithm for Manipulation Planning under Continuous Grasps and Placements[END_REF]. To deal with such types of tasks, we propose to associate a roadmap to each one.

When dealing with closed kinematic chains, it has been shown that it could be useful to deal separately with different operations. For instance, closing a kinematic chain and moving in the environment can be done in two steps [START_REF] Han | A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems[END_REF][START_REF] Valle | A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains[END_REF]. Therefore, we also allocate a specific roadmap to each operation.

The last type of roadmaps that we propose to define are purely heuristic ones. They will be used to perform search in relaxed instances of problems. For instance, one may decide to search for a certain type of path that may be invalid, but that will serve as a good basis for further refinement.

The planner is guided by a set of heuristics rules that will allow it to choose which roadmap should be extended and how to do so. These rules exploit the specificities of the different roadmaps.

The roadmaps are not necessarily built to catch directly the topology of the configuration space of all environment parameters but only of subsets of it. The key idea is to work on several roadmaps of kinematics subset in order to be able to deal with their composition without explicitly computing it.

In order to limit the size of the search space, the search process will tend to give priority to the most constrained roadmaps or to sub-manifolds involving a small number of mobile objects.

To find a valid solution, we use a multi-roadmap solver that can handle several roadmaps to ensure the validity of all of the environment configurations.

Configurations Definition

A roadmap are specific to one robot, or more precisely to a sub-set of elementary kinematic chains (noted EKC), associated with configuration definition.

Classically, a configuration is a set of parameters which allows to specify the state of all objects in the environment. With kinematic constraints [START_REF] Valle | A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains[END_REF][START_REF] Han | A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems[END_REF][START_REF] Cortès | A Random Loop Generator for Planning the motions of closed kinematic chains with PRM methods[END_REF] the number of configuration parameters may be greater than needed. Indeed, through the kinematic constraints, several degrees of freedom must be recomputed. Likewise, we have chosen, in our application, to not to have a minimal representation. Let us consider a manipulation environment with a mobile manipulator and a movable object (besides fixed obstacles). As shown in Figure 1, we consider a set of EKC that define the state of all objects. In our representation we split a configuration into a placement part (6 degrees of freedom) and an actuator part (degrees of freedom controlled by robots). For example the arm configuration has 14 degrees of freedom: 6 for the placement part, 6 for a classical arm configuration and 2 for the gripper.

Given a set of EKC, one can combine them in order to describe more complex robots. For instance a mobile arm (M-A) can be modeled with a mobile base (M), an arm (A) and a fixed attachment between them. The model will then be completed by a configuration which groups the two elementary con-figuration sets and no other degree of freedom because of the fixed attachment: ((6, 3), [START_REF] Han | A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems[END_REF][START_REF] Kavraki | Ramdomized preprocessing of configuration space for fast path planning[END_REF], 0). This allows to take advantage of specific methods associated to each EKC in order, for instance to combine their local-path methods. We have defined a set of methods that allow this combination, like using Reed and Sheep local-path for the mobile base and straight-lines in the C-space for the arm.

In the same way, we define a chain (M-A-O) where the robot holds the object. The resulting configuration includes all the EKC configurations and 3 additional degrees of freedom for the continuous set of grasps: (((6, 3), (6, 8), 0), (6, 0)3). For a parallel jaw gripper, this attachment depends on 3 parameters: two translations parallel to the grasped face and one rotation around the axis perpendicular to the faces [START_REF] Siméon | A Manipulation Planner for Pick and Place Operations under Continious Grasps and Placements[END_REF][START_REF] Sahbani | A Probabilistic Algorithm for Manipulation Planning under Continuous Grasps and Placements[END_REF]. Using such combinations, the arm forward kinematics can be used in order to generate a transfer configuration (the robot holds the object), and its inverse kinematics to obtain a grasp configuration (the robot grasps the object on a specific placement).

In the next section we will show how these combinations of EKC will be used to build roadmaps for manipulation problems.

Roadmap Definition

As already mentioned, our approach is based on the construction of a number of roadmaps. Each roadmap is associated with a task and is used according to it. It corresponds to one of the previously defined combinations of EKC. In our representation, the link between a roadmap and its semantics is done through 4 attributes:

Roadmap type: see §3.1. Edge method: defines the local-path used to connect two nodes in the roadmap Roadmap links: see §3.2. Random sampling method: see §4.1.

This attributes allow to extend the roadmaps definitions used in the manipulation problems, or in kinematics roadmap [START_REF] Han | A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems[END_REF][START_REF] Valle | A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains[END_REF]. They have been devised not only to solve the class of problems presented here, but also to model and solve multiple robots, multiple objects manipulation problems.

Roadmap Type

A type is associated to each roadmap in order to describe how to use it. Up to now, we have defined four roadmap types: Cross, Refine, Heuristic, Relative.

The first two types are used to extract the solution.

Cross: defines a roadmap where all the nodes and edges are valid subset of configurations and movements. The solution plan must be expressed with paths from such roadmaps.

Refine: defines a roadmap where all the nodes are valid, but where the edges do not represent a valid motion but satisfy the reduction property [START_REF] Alami | Two manipulation planning algorithms[END_REF]. This property allows to systematically transform an edge of this graph into a finite number of valid movement operations. Therefore, a solution plan to a manipulation problem can include those elementary paths. The final plan will be obtained after the refinement of such paths into valid action sequences.

The last two roadmap types are used for the sake of increasing the speed of the planner. While a solution cannot include edges borrowed from such graphs, they can provide paths that can guide the search.

Heuristic: defines a roadmap where several constraints has been relaxed. They will generally be domain specific.

Relative: defines a roadmap where the EKC configuration is expressed relatively to a joint. Such a roadmap does not take into account the static environment. It allows the computation of complex local configurations and motions. This processing can be useful when the kinematic chain becomes complex and/or when the autocollision checking or the kinematic computations are time consuming [START_REF] Han | A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems[END_REF][START_REF] Valle | A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains[END_REF].

-A-O Grasp G " Relative M-A-O Attachment A none Heuristic
In our example, we have defined the set of roadmaps presented in Table 1. The objet alone has two roadmaps. The first R(P o) represents the valid configurations of the objet when it is not grasped (stable positions globally named Placement). In this case, no movement is allowed, so the roadmap contains only unlinked nodes. In the second roadmap, the configuration space is the same but movements are allowed, resulting in links between nodes. As the object cannot move by itself, this graph is a heuristic one. It is aimed to catch the topology of the valid stable object positions. This will be useful when it will be necessary to find intermediate objects positions (see §4.3). The roadmaps R(T i) and R(T a) represent respectively the "standard" transit and transfer paths.

As already mentioned, R(T i) does not involve all the EKC; hence, any valid path extracted from it should be tested to be free of any collision with the object. The Graspb ∩ P lacement roadmap R(GP ) satisfies (by construction) the reduction property [START_REF] Alami | Two manipulation planning algorithms[END_REF]. So, any path included in this graph can be transformed into a finite set of alternate valid transit and transfer paths. It is the most constrained roadmap with a closed kinematic chain induced by the fact that any configuration corresponds to a stable object placement as well as a grasp/ungrasp robot configuration [START_REF] Siméon | A Manipulation Planner for Pick and Place Operations under Continious Grasps and Placements[END_REF][START_REF] Sahbani | A Probabilistic Algorithm for Manipulation Planning under Continuous Grasps and Placements[END_REF].

Note that R(G) can be used to store valid closed kinematic chain relative configurations of the robot and the object, and to reuse them in R(GP ).

Another heuristic roadmap, R(A), is intended to store the gripper/object grasp transforms used. The planner will try to re-use as much as possible the same grasp transforms. This is done in order to simplify the search for new transfer motions.

After this description of the various roadmaps that can be used, we will now see the links between them and how they allow to search for a plan through a set of roadmaps.

Roadmap links

In order to be able to build a plan as a result of a search through several roadmaps, the planner will incrementally build, explore and switch between them. We define two types of links between those roadmaps:

Inheritance : This link connects a constrained roadmap R 1 to a less constrained roadmap R 2 .

All valid configurations in R 1 are valid in R 2 .

Compose : Such a link connects one or more roadmaps to a more complex roadmap to make new configurations that are a composition of the nodes of these roadmaps. These links are based on the inheritance links.

Inheritance. As said before, the inheritance links connects a constrained roadmap R 1 to a less constrained roadmap R 2 . This link also defines a filter used to derive a a valid sub-node in R 2 from a node in R 1 . Each time a node is added to R 1 , it is linked to its sub-node in R 2 .

There are two conditions for the existence of such a link. First, it cannot connect a Relative roadmap to a not Relative one. Second, the EKC of R 2 must be included in R 1 . When R 2 is Relative, a change of reference frame is applied.

For example (Figure 2), R(GP ) is the most constrained roadmap, so all its nodes are linked to the other roadmaps. Whenever a node N is created in R(GP ), a corresponding node is added to R(T a). Such a node may serve as beginning or end of a transfer path. Likewise, a node is created in R(T i). Besides, a closed kinematic chain and a relative grasp transform are extracted from N and respectively stored in R(G) and R(A).

Roadmap Construction

The last roadmap attribute to consider is the random sampling method. Now we study the not so classical random sampling method.

Random Sampling

For random sampling we mainly use two methods (and their combination): the Random Loop Generator (RLG) [START_REF] Cortès | A Random Loop Generator for Planning the motions of closed kinematic chains with PRM methods[END_REF] and the creation of nodes based on compose links between roadmaps.

The RLG allows to choose a new node with short generation time. In fact the random space is reduced to only allow configurations with the possibility to be updated to satisfy a set of kinematic constraints.

The other possibility is the use of composed links. A set of nodes in sub-roadmaps are chosen at random (or not) to make a new node N c . In fact this link does not necessary define completely a configuration of N c . So, there is often a combination of node composition and RLG.

Let us recall that there is a third way to obtain nodes in a roadmap through link inheritance.

Each roadmap can have several ways to make a new node. We use a set of heuristic rules to determine what are the nodes needed, and in which roadmap the search should be performed.

Heuristic Rules

Recent progresses in task planning [START_REF] Bacchus | Using Temporal Logic to Control Search in a Forward Chaining Planner[END_REF][START_REF] Erol | HTN Planning: Formalization, Analysis, and Implementation[END_REF][START_REF] Hoffmann | The FF Planning System: Fast Plan Generation Through Heuristic Search[END_REF] have been based on the development of new heuristics. The manipulation problem is both a geometrical and a task problem. So it seems natural to borrow techniques from these domains.

The heuristic rules are, for us, the first level of symbolic control of the purely geometrical PRMs search methods.

Rules Precondition. Rules preconditions enable to compute the probability to select a rule. While in task planning the best rule is always selected, with PRMs, if we want to keep the property of probabilistic completion, we must allow a non-null probability to all applicable rules.

The preconditions are based on roadmaps analysis. Several parameters can be used: the roadmaps nodes number, the number of connected components, the current mean computation time,. . .

For instance, it is interesting to increase the size of R(GP ) and of R(T i) at the beginning to avoid to link not useful nodes of R(GP ) with transit or transfer paths. Indeed, it is better to invest until we have "sufficiently" captured the topology of R(GP ).

The preconditions can also be based on a more detailed analysis of the roadmaps. For example:

∃N 1 ∈ C(GP ) 1 , N 2 ∈ C(GP ) 2 , N o ∈ R(P o) ∃N s ∈ R(T i), N e ∈ R(T i)/ N o ⊂ N 1 and N o ⊂ N 2 and N s ⊂ N 1 and N e ⊂ N 2 (1)
This precondition is used in a rule that tries to link two connected components C(GP ) 1 and C(GP ) 2 of R(GP ) with a transit path. The precondition tests if a common object position exists in the two components. The right part of the rule is discussed in the next subsection.

Rules Specification

We have two levels of rules. The high level allows to select a rules subset. For instance, the following rule selects the set of rules that require to perform an extension of GP roadmap.

Increase R(GP )

The low level rules specify (1) the roadmap that must be increased (2) how it will extended (by choosing a new node randomly or by trying to link two nodes with a specific-search) and (3) the associated method.

In R(GP ), random(), with RLG In R(GP ), random(), with Compose(P o, G)

The first rule draws a new node in R(GP ) with the Random Loop Generator method [START_REF] Cortès | A Random Loop Generator for Planning the motions of closed kinematic chains with PRM methods[END_REF]. The second uses the compose link (Figure 2) from the Grasp roadmap and the Object position roadmap to build a new random node, The interest of such a rule is that all the closed kinematic and the auto-collision computations have been already done; it is sufficient to test only collision with the static environment to validate the node.

Rules can also specify more specific actions. For example, if two nodes N s and N e satisfy the precondition 1, then we can try to link them:

In R(T i), specif ic search(N s , N e ), with RRT

Problem Solving

The heuristic rules explain how to build the roadmaps, and now we must explain how to search for a solution in the set of roadmaps.

Kinematic-Component

We define a topological structure across the different roadmaps that will serve as a search space for the planner. We call them the kinematic-components (noted KC()).

A kinematic-component does not link roadmap nodes but connected components of two different roadmaps or of other kinematic-components.

They are defined on Cross and Refine roadmaps and the edges are derived from roadmaps inheritance links. Besides, each kinematic-component is defined on a subset of elementary kinematic chains (EKC).

In our example, we have three types of kinematiccomponents: the robot kinematic-component (KC(M -A)) that stores C(T i) components, the object kinematic-component (KC(O)) that stores C(P o) components, the grasp kinematic-component (KC(M -A-O)) that stores C(T a), C(GP ) and the pairs of kinematic-components (KC(M -A), KC(O)) previously defined.

This hierarchical structure will be mainly used in multiple robots problems.

To solve the problem, the planner must find a solution in a kinematic-component in which all the EKC are defined. In our case we need to link the kinematic-components KC(M -A-O) of the initial and goal configurations.

Validity of edges

To find a solution, the planner must incrementally increase the roadmaps, under the control of the heuristic rules until it is able to link the kinematiccomponents of the initial and the goal configurations. But even if a path is found, it may be not valid. The edges of some roadmaps have not yet be fully tested.

With the mono-robot, mono-object manipulation problem, the solution is found into the robot crossable roadmaps (R(T a), (R(T i), R(P o)), R(GP )). All these roadmaps are valid but not the robot movement roadmap R(T i). The roadmap has been built without the object, so the robot may collide the object during its movement. The selected trajectories must be checked with the current object position (given by C(P o) coupled with C(T i)). Like [START_REF] Siméon | A Manipulation Planner for Pick and Place Operations under Continious Grasps and Placements[END_REF][START_REF] Sahbani | A Probabilistic Algorithm for Manipulation Planning under Continuous Grasps and Placements[END_REF], we use RRT [START_REF] Kuffner | RRT-Connect: an efficient approach to single-query path planning[END_REF] to find a valid path based on non-valid trajectory. If no valid path is found, we invalidate the link between those kinematic-components and search for another path in the set of components. This can lead to re-grasping operations.

With multi-robot or with multi-object manipulation, finding a path through valid edges could be much more challenging. To solve this problem we foresee the use of another level of symbolic methods much closer to task planning.

First results

The manipulation planner has been implemented within the software platform Move3D1 currently developed at LAAS-CNRS. Even if the preliminary version of our implementation is not yet fully functional, the first result (Figure 3) shows the roadmaps construction for a simple manipulation task, and its solution with a mean time of 1 minute with a SunBlade 100. In this example we have a non holonomic robot with an arm which can grasp a bar under continuous grasps and placements.

The problem is to change the position of the object. The planner re-uses as much as possible other roadmaps (Figure 3) . The Grasp∩Placement roadmap has nodes composed on the initial and goal position of the object. In the same way the transfer roadmap is very close to the transit one.

Conclusion

We have presented a new approach to manipulation planning that deals with a set of roadmaps and introduces new heuristics with more symbolic specifications. This approach has been tested on mono manipulation problems but is intended to deal with a much wider class of problems, even the multi-robot and multi-object manipulation.

The first results are encouraging, but many improvement could be done in order to have a fully functional planner. The most important part will be the realization of the multi-robot solver that could have good performances for searching valid edges through the set of roadmap and possibly take into account other non-purely manipulation tasks . This new solver must be a link between PRMs and tasks planning.

Figure 1 :

 1 Figure 1: Configuration definition through kinematic chains

Figure 2 :

 2 Figure 2: Roadmap links Compose Links. These links define how to make a node in a complex roadmap R c from nodes belonging to other roadmaps R 1 . . . R n that inherit from R c . The node composition is based on the inverse functions of the original inheritance link.

Figure 3 :

 3 Figure 3: Example of a manipulation problem with a non-holonomic mobile maniptlator: (a) the problem consists in tranferring the bar from one table to another; (b) and (c) represent two different roadmaps that have been incrementally built during the search (d) illustrates one solution

Table 1 :

 1 Roadmap Definition

	Kin.	Roadmap	Edge method	Type
	O	Placement P o	none	Cross
	O	Movement M o	linear	Heuristic
	M-A	Movement T i	local-path	Cross
		(Transit)	holonomic or not
	M-A-O Transfer T a	linear composition	Cross
			fixed attachment
	M-A-O Grasp ∩	linear composition	Refine
		Placement GP	with constraints
	M

See http://www.laas.fr/ nic and for a commercial version of this prototype distributed by the spin-off Kineo, see http://www.kineocam.com

Acknowledgments

We are very grateful to Anis Sahbani and Juan Cortès who have contributed to many ideas in this paper and developed several algorithms that are used in this planner.