Clémentine Adam
email: clementine.adam@univ-tlse2.fr

Marianne Vergez-Couret
email: marianne.vergez@univ-tlse2.fr

Signalling Elaboration: Combining Gerund Clauses with Lexical Cues

Keywords: Elaboration, lexical cues, distributional neighbourhood, SDRT, discourse analysis

In this paper, we aim at automatically identifying Elaboration. This relation is particularly difficult to spot since it does not have prototypical markers. Our approach focuses on an ambiguous syntactic pattern, the gerund clause, combined with lexical cues. This approach allows us to detect few but accurate cases of inner sentence Elaborations in our corpus, validating the fact that lexical cues are relevant for this task.

Introduction

Description and detection of discourse structure is a major topic of ongoing research [START_REF] Moore | Discourse in Computational Linguistics and Artificial Intelligence[END_REF][START_REF] Péry-Woodley | Computational Approaches to Discourse and Document Processing[END_REF]. Many formal and functional approaches attempt to model discourse through relations between segments (typically clauses) [START_REF] Asher | Logics of conversation[END_REF][START_REF] Grosz | Attention, intentions and the structure of discourse[END_REF][START_REF] Hobbs | Literature and cognition[END_REF][START_REF] Mann | Rhetorical Structure Theory : a theory of text organisation[END_REF][START_REF] Wolf | Coherence in Natural Language[END_REF]. Anaphora resolution, temporal order of events identification and others empirical problems require knowledge of discourse structure [START_REF] Grosz | Attention, intentions and the structure of discourse[END_REF][START_REF] Lascarides | Temporal interpretation, discourse, relations and commonsense entailment[END_REF][START_REF] Hobbs | Literature and cognition[END_REF]. Applied approaches [START_REF] Baldridge | Probabilistic Head-Driven Parsing for Discourse Structure[END_REF][START_REF] Lin | Recognizing Implicit Discourse Relations in the Penn Discourse Treebank[END_REF][START_REF] Subba | An effective Discourse Parser that uses Rich Linguistic Information[END_REF] aim to handle and detect elements of this structure studied by formal and functional approaches in order to develop applications like automatic generation [START_REF] Mckeown | Text Generation: Using Discourse Strategies and Focus Constraints to Generate Natural Language Text[END_REF] and automatic summarization [START_REF] Marcu | The rhetorical parsing of unrestricted texts : a surface-based approach[END_REF], among other natural language processing tasks.

In this paper, we focus on the Elaboration relation and on its automated identification, using SDRT's theoretical framework. The Elaboration relation is particularly difficult to spot, since it does not have a prototypical lexical marker according to [START_REF] Knott | A data-driven methodology for motivate a set of coherence relations[END_REF]. According to SDRT, the Elaboration relation can be lexically marked, but this hypothesis has not yet been tested on the basis of corpus data. We investigate this claim using lexical cues to identify Elaboration. This investigation is carried out in the framework of the VOILADIS project 1 , which aims to demonstrate the importance of lexical cues for discourse analysis. More specifically, we discuss the lexical resource that we employ to highlight these lexical cues. A practical experiment of inner sentence Elaboration detection is presented, combining a lexical resource based on the computation of distributional similarity on the one hand, and a weak marker of the Elaboration relation, the gerund clause, on the other hand.

Our first aim is to contribute towards the automated identification of the Elaboration relation. Our second aim, which follows from the first, is to improve the description and formalisation of this rarely studied relation, in order to expand studies on discourse signalling. We offer two contributions towards this goal: first, we extend the study of the devices that are used to mark this relation by showing that it is lexically signalled. Second, we collect examples that could be used to evaluate the adequacy of theoretical frameworks to real-world data.

2 On the Elaboration relation 2.1 Elaboration within the framework of SDRT Segmented Discourse Representation Theory [START_REF] Lascarides | Temporal interpretation, discourse, relations and commonsense entailment[END_REF][START_REF] Asher | Logics of conversation[END_REF]) is a formal theory of discourse. SDRT is an explanatory model making use of semantic information, world knowledge and pragmatic principles in order to explicit the rhetorical link between clauses. Discourse relations are described in two steps: first, they are associated with triggering rules to infer them and second, discourse relations entail semantic effects. SDRT claims that while discourse structure must be sensitive to non-linguistic information like world knowledge, it is conceptually and computationally more efficient to take into account linguistic knowledge to which we have direct access. Triggering rules to infer relations use both linguistic cues like discourse markers, syntactic constructions, verb tense, aspect and mood, argument structure, logical operator, quantifiers ; informations about lexical semantics ; and non-linguistic information about word knowledge and pragmatic principles.

The relation of Elaboration relates two propositions only if the second proposition provides more detail about the eventuality (state or event) described in the first. In the SDRT framework, the triggering rule to infer Elaboration is based on information about lexical semantics and world knowledge. More specifically, Elaboration can be non-monotonically inferred if there is a subsumption relation between the types of the eventualities involved. The Subtype predicate (Subtype D ) means that the type of the second eventuality is a subtype of the first one in the lexical semantics of the predicates or by some piece of shared knowledge dependent on the given discourse (D). For instance, Elaboration is inferred between constituant π a and π b (representing respectively segments (a) and (b)) in the following example :

(1) (a) Martha ate a lovely meal. (b) She devoured lots of salmon. (Asher & Lascarides, 2003, p.282) We can non-monotonically infer that the type of the second event "devour lots of salmon" is a subtype of the first one "eat a lovely meal" thanks to lexical semantics.

Non-monotonically means that this inference can be cancelled if other monotonic inferences are established like in the following example :

(2) (a) Martha ate a lovely meal. (b) And then she devoured lots of salmon.

The discourse markers "And then" monotonically indicates that π b (representing (b)) is attached to π a (representing (a)) by Narration.

In the framework of SDRT, the lexicon is an important (but not exclusive) information source for inferring Subtype D predicate. The lexicon includes information about the semantic type of objects that are denotated by common nouns, verbs and so on. A subtype is related to a supertype by some notion of substituability: the subtype inherits many supertype characteristics and has some specific differences ; the subtype can be substituted by the supertype but the reverse is not necessarily true. The concept of subtype is closely related to the linguistic notion of hyperonymy.

In the example (1), sentences (a) and (b) include words that are semantically linked. First, the type of the event described in e b "devour" is a subtype of the type of the event described in e a "eat". Second, the word meal must be lexically specified to be of type f ood and salmon is also of type f ood but this lexical information is not directly coded in the type hierarchy. More lexical information are needed like, for instance, that the property of the event "meal" is to eat it ; that all words of type "food" have this property ; and that "salmon" is food derived from the animal salmon.

This information at the lexical level between predicates ("eat" and "devour") and arguments ("meal" and "salmon") sharing a same θ-role (here patient) allow us to infer Subtype D between the constituants π a and π b (build from a and b) at the discourse level.

Signalling of Elaboration

( [START_REF] Scott | Getting the message across in RST-based text generation[END_REF][START_REF] Knott | A data-driven methodology for motivate a set of coherence relations[END_REF][START_REF] Knott | Beyond elaboration : the interaction of relations and focus in coherent text[END_REF] observed that Elaboration is a relation for which there are no obvious surface signals, so that automatic identification using prototypical discourse markers is impractical. It is therefore necessary to find different ways (other than traditional markers) to automatically detect this relation. [START_REF] Marcu | The rhetorical parsing of unrestricted texts : a surface-based approach[END_REF] uses algorithms based on discourse markers and word co-occurences, and finds that discourse markers "specifically" signal Elaboration. However, that marker is not frequent and covers few cases of Elaboration. [START_REF] Marcu | The rhetorical parsing of unrestricted texts : a surface-based approach[END_REF] also reports on a non-linguistic marker, based on the number of sentences in a paragraph or the number of paragraphs in a section : If this number is small and no discourse markers are used, the relation between the sentences or paragraphs is generally Elaboration. Elaboration is particularly difficult to spot also because discourse markers are generally ambiguous, as shown by Bras2007 for the french adverbial "d'abord" (first) that requires subordination with a constituent above him in the discourse structure via Elaboration Explanation Result or Flashback relation. In this paper, we investigate the use of lexical cues to detect Elaboration, as suggested by the SDRT model. However, this development is not straightforward; the next section discusses difficulties inherent to the subtype predicate and the requirements for the resource used in this task.

3 Using lexical cues for identification of Elaboration

From Subtype to lexical similarity

At first glance, it may seem that a resource providing information about hypernymy could be the right resource in order to detect automatically Elaboration. However Elaboration exhibits a wider range of lexical relations. The Elaboration relation, at the discourse level, is based on relations at the lexical level; however, those relations are diverse and not restricted to the lexical subtype relation. Since these relations emerge in discourse, the lexical phenomena involved can be different from these found in classical resources. Such relations can be established by discourse, and may be tightly related to a specific enunciation [START_REF] Mortureux | Paradigmes désignationnels[END_REF]. We illustrate this issue in the following examples.

( In example (3), three lexical links allow us to infer Subtype D (π 1 , π 4 ) : "véhicule" (vehicle)/"voiture" (car), "sortie" (exit)/"quitter" (leave) and "route" (road)/"chaussée" (roadway). While the first link, "véhicule" (vehicle)/"voiture" (car), is clearly classified as hyperonymy, the "route" (road)/"chaussée" (roadway) link is in fact meronymy, and the "sortie" (exit)/"quitter" (leave) link is more subtle to categorize, since cross-category relations are generally not listed in typologies.

( ) rests on links between "vocation" (vocation) and words such as "soutien" (support), "accomplir" (to complete), "tâche" (task) or "contribuer" (to contribute). These links are established in discourse, and will most probably not appear in a generic resource, since they do not match a classical lexical relations. Such links are more accurately referred to as lexical similarity relations.

Selecting the appropriate lexical resource: distributional neighbours

We have seen that the Elaboration relation seems indeed lexically marked, but that the links involved are softer than subtype. In order to automatically detect this relation, the resource chosen is crucial: it should contain these links for their automated usage. As stressed in the previous section, a generic resource seems poorly fitted to this task. We have focused on a resource built from corpora, taking into account semantic proximity links, possibly across parts of speech. In particular, we have chosen the Voisins de Wikipédia database, a resource built by distributional analysis. The principle of distributional analysis is to pair words based on their shared contexts, following [START_REF] Harris | Mathematical Structures of Language[END_REF] hypothesis. The paired words share second-order affinities: they do not need to appear together in the corpus, but their environments are similar [START_REF] Grefenstette | Corpus-Derived First, Second and Third-Order Word Affinities[END_REF]. The lexical relations put in evidence are then paradigmatic.

The Voisins de Wikipédia database was build from a full archive of the online encyclopedia Wikipedia, which contains more than 194 millions words. The archive was processed through the Syntex-Upéry chain developed by [START_REF] Bourigault | Upery : un outil d'analyse distributionnelle étendue pour la construction d'ontologies à partir de corpus[END_REF]. First, a syntax analysis is performed. Then, all <governor, relation, dependant> triplets are listed, an example triplet is: <circuler, à bord de, voiture> (<travel, in, car>). The triplets are then transformed in <predicate, ar-gument> couples, where the predicate is a combination of two components: the governor and the relation, in the previous example <circuler_à bord de, voiture> (<travel_in, car>). The similarity between distributions is computed for each predicate couple and each argument couple using Lin's score: Predicates are paired based their shared arguments; reciprocally, the same pairing is performed on arguments, based on their shared predicates. Thus, arguments "véhicule" (vehicle) and "voiture" (car) are paired through predicates such as "circuler_à bord de" (travel_in), "capot_de" (hood_of ), "conduire_obj" (to drive_obj) , etc.

The obtained resource contains 4 million pairs, covering a large panel of relations. An example of neighbourhood links projected on the text sample ( 3) is provided below. Only links between two sentences appear.

Here, aforementioned links relevant for identifying the Elaboration relation are observed: "véhicule" (vehicle) / "voiture" (car), "sortie" (exit) / "quitter" (leave), and "route" (road) / "chaussée" (roadway). Other links participating in global lexical cohesions are observed, but these links are not involved in the Elaboration. Finally, many links are not relevant in this context, for example "route" (road) and "traverser" (to cross).

The plethoric nature of this resource is a strong barrier against its broad usage. Even though relations relevant to our task are put in evidence by projecting neighbours in the text, many other irrelevant neighbourhood links will interfere, making a direct inference to the discourse level impossible. It is therefore necessary to define more restrictive markers, by taking into account more elaborate criteria than the simple presence of neighbourhood links. We choose to experiment on detection based on targeted neighbourhood links combined with the presence of a weak elaboration marker: gerund clauses.

Combining the neighbours with a weak cue: the gerund clause

Since the information provided by the neighbours is too plethoric we propose to combine it with an ambiguous cue of Elaboration. Such a combination should be more reliable than each cue considered separately since the conjunction of two ambiguous cues builds a stronger cue. Gerund clauses are the perfect candidate for this combination: some gerund clauses could be considered as elaborations of the main clause and they are easy to extract with SYNTEX.

The gerund clause establishes a syntactic subordination between two verbs: two processes are linked in this way. The different semantic values expressed by the gerund clause are not conveyed by the gerund itself but depend on the combination of the two linked verbs. The interpretation is done a posteriori and determined by the semantic relationship between the verbs and other elements given by the context [START_REF] Halmoy | Le gérondif. Eléments pour une description syntaxique et sémantique[END_REF].

Our analysis reveals that gerund clauses in French can be linked to the main clause with two main discourse relations. For ( 5) and ( 6), we infer an Elaboration relation:

(5) Les Britanniques réagissent en emprisonnant ou en tuant les derniers chefs.

The British react by imprisoning or killing the last leaders.

In ( 5), the main clause introduces an underspecified event "réagir" to react and the two gerund clauses introduce two events that specify it "emprisonner" to imprison and "tuer les derniers chefs" to kill the last leaders.

(6) Puis on irrigua les alentours en creusant un canal derivé du Zab Supérieur.

Then, the surrounding areas were irrigated by digging a canal leading from the River Zab Supérieur.

In ( 6), the main clause introduces the event "irriguer" (to irrigate) and the gerund clause introduces the event "creuser" (to dig). "Irriguer" and "creuser" are semantically linked. The activity denoted by the type of event "irriguer" can involve the activity denoted by the type of event "creuser". So, we can infer Subtype D between the type of events "irriguer" and "creuser".

However, gerund clauses are not always elaborations of the main clause like in the following example:

(7) Dans la ville de Koriko, Kiki, accompagnée de son chat noir Jiji, va distribuer des colis en volant sur son balai, grâce à ses pouvoirs.

In Koriko town, Kiki, with her black cat Jiji, delivers parcels while flying on her broom, thanks to her magical power.

In ( 7), the gerund clause gives background of the main clause. The Background relation are typically used for setting the stage of an event. In ( 7), the main clause introduces the event "distribuer des colis" (to deliver parcels) and the gerund clause gives background information "voler sur son balai" (to fly on her broom).

Our main idea is that verbs and objects in the main clause and the gerund clause will generally be neighbours in Elaboration cases and not in Background cases. Considering our examples ( 6) and ( 7), it seems to us that "irriguer" (to irrigate) and "creuser" (to dig) could be found as neighbours but not "distribuer" (to deliver) and "voler" (to fly).

With this hypothesis in mind, we set up the experimentation presented in the next section.

4 Experimental validation

Motivations and strategy

The goal of the presented experiment is to reliably identify Elaborations: we aim for the highest precision. This task is challenging: it is sparsely attempted in the literature and the attained reliability is low. Nevertheless, such attempts are required for a better understanding of the Elaboration relation.

While this task is interesting in itself, our experiment will also illustrate the improvement brought by taking into account lexical phenomena for discourse analysis, and show the relevance of lexical neighbourhood for detecting these phenomena. If using lexical neighbours brings a significant performance improvement, we will also validate the fact that Elaboration is a lexically marked relation.

In order to reach these goals, we chose to use the lexical neighbours in combination with a weak clue for Elaboration, the gerund clause. Two combination strategies are tested.

• In a first run, Elaboration is detected if verbs in the main clause and in the gerund clause are neighbours (these candidates are noted by GN in the following), Cf. (8).

• In a second run, Elaboration is detected if verbs in the main clause and in the gerund clause are neighbours, and if the verbs objects are connected by at least one neighbourhood link (GNON in the following), Cf. (9).

(8) ... et les villages contribuaient également à ce grand projet religieux en envoyant des vivres.

(...) and villages also contributed to this great religious project by sending supplies (9) Les Skrulls (...) élargissent leur empire en englobant dans celui-ci les mondes moins avancés qu'ils rencontrent. The Skrulls (...) were expanding their empire by incorporating the less evolved worlds they discovered.

We will compare the results of these two combination strategies to the results obtained by considering only the gerund clause (G in the following). The observed performance differences will allow us to quantify the improvement brought by using lexical neighbours to enhance Elaboration detection.

Extraction of Elaboration candidates

In this experiment, the corpus used is a fraction of the french Wikipedia: 45'823'899 words from 5'106'831 sentences, which amounts to roughly one fifth of the online encyclopedia. This corpus has been pre-processed with SYNTEX. All sentences featuring a [verb clause, gerund clause] pair are extracted (G). Two subsets of these candidates are then produced, by taking into account constraints of lexical neighbourhood on the verbs pairs (GN) and on the verb objects pairs (GNON), as explained in the previous section. The following table gives the number of candidates obtained depending on which markers were used.

G GN GNON 18571 375 193

The number of Elaboration candidates is small considering the corpus size. Nevertheless, in the current state of research on this relation, defining a reliable marker is a significant improvement, even if the number of matches is small.

Annotation of extracted candidates

Each text was independently annotated by two experts in discourse relations2 . We annotated 314 examples, approximatively 100 for each case (G, GN, GNON) presented randomly to the annotators with the question: Is the gerund clause an elaborating segment of the main clause?

The agreement rate between experts is 89% (280 cases of agreement vs 34 cases of disagreement). The kappa score [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF]) is 0.70, which highlights a moderate to good interannotator agreement. This reveals the difficulty of the task. The kappa score is, however, good enough to consider an automatisation of this task.

In a second run, we explored the 34 examples for which we disagreed, in order to make sure the reference annotation was as reliable as possible and to analyze the types of inter-annotator variation. The discussion allowed us to refine the annotation for the vast majority of disagreement cases. Finally, only 9 cases resulted in the experts disagreeing; such cases include texts for which two interpretations are possible. To ensure meaningful results, these 9 marginal cases were discarded from the reference which was subsequently used to evaluate the results of the automated elaboration detection, cf. next section.

Results and perspectives

The table below summarizes the results obtained when testing the three strategies for Elaboration detection. These results confirm that the gerund clause is indeed an ambiguous cue, since only 60.8% of the candidate are Elaboration. The number of annotated candidates is small considering the amount of gerund clauses extracted; this results in a wide confidence interval. However, the performance difference between G and our two strategies is large enough to ensure that these two strategies bring a significant improvement. With the first strategy (gerund clause and main verb are neighbours), 81% of the cases are Elaboration. The second strategy (gerund clause and main verb are neighbours and the verbs objects are linked by neighbourhood) is very reliable, with 95% precision. These results are highly promising.

The cases where our markers failed were analysed. In a few cases, the failure is caused by an irrelevant neighbourhood link. For example, in the context of example (10), the link between "marcher" (march) et "incendier" (burn) is irrelevant. In various cases, a different marker can be observed, which could be used to cancel the Elaboration inference. This is illustrated in example (11), where the strong lexical marker of Contrast relation "mais" (but) appears.

(10) Ils marchent la campagne en incendiant toutes les habitations. They marched the countryside, burning down every dwelling they found.

(11) Le roi d'Espagne lui accorda une décoration qu'il accepta, mais en refusant la pension qui y était attachée.

The king of Spain accorded him a decoration that he accepted while refusing the pension that was attached to it.

These considerations suggest that our good results can still be improved upon, by taking into account other types of markers, signalling an other discourse relation on the one hand, and by a more elaborate filtering for the neighbours on the other hand.

Conclusion and outlook

We have presented a practical experiment dedicated to the detection of Elaboration. While Elaboration is often considered as a relation without prototypical lexical discourse markers, our aim was to find signalling devices for the identification of Elaboration. We combined an ambiguous cue, the gerund clause and information provided by the lexical neighbours resource.

The results of our experiment are encouraging. We validate on a corpus the fact that Elaboration can be lexically marked as suggested in the SDRT framework. With this contribution, we also follow the objectives of ANNODIS project3 , which aim to construct an annotated corpus for the study of discourse organisation in order to improve description and formalisation of discourse relations with real-world data.

The prevalence of lexical cues for discourse structuration is commonly accepted, but they are still neglected in NLP applications because of the difficulty to pick out lexical links in texts. This contribution validates lexical neighbours as a relevant resource to use for this task, in the case of Elaboration detection. In the course of the VOILADIS project, we hope to generalize the usage of lexical cues for all aspects of discourse analysis.

Nevertheless, our approach detects a few cases of Elaboration in the whole corpus. Improvements could be made by detecting Elaborations between sentences. First we will continue to combine neighbours and weak cues of Elaboration such as the adverbial expressions "d'abord" (first), "dans un premier temps" (at first). Second, we will investigate the role of the neighbours by taking into account the density of neighbours between two sentences, the syntactic position of the neighbours, etc.

financed by the Cluster for Higher Education and Research "Université de Toulouse" (PRES)

The authors of this paper.

financed by the French National Research Agency (ANR)

Acknowledgements

We would like to thank Cécile Fabre and Philippe Muller for discussions related to the content of this paper and for the help with english writing and presentation.


Karim Belharet

David Folio

Antoine Ferreira

3D MRI-based Predictive Control of a Ferromagnetic Microrobot Navigating in Blood Vessels

This paper presents an endovascular navigation of a ferromagnetic microdevice using a MRI-based predictive control. The concept was studied for future development of microrobot designed to perform minimally invasive interventions in remote sites accessible through the human cardiovascular system. A system software architecture is presented illustrating the different software modules to allow 3D navigation of a microdevice in blood vessels, namely: (i) vessel path extraction, (ii) magnetic gradient steering, (iii) tracking and (iv) closed-loop navigation control. First, the navigation path of the microrobot into the blood vessel is extracted using Fast Marching Method (FMM) from the pre-operation images (3D MRI imaging) to guide the microrobot from the injection point to the tumor area through the anarchic vessel network. Based on the precomputed path, a Model Predictive Controller (MPC) is proposed for robust time-multiplexed navigation along a 3D path in presence of pulsative flow. The simulation results suggest the validation of the proposed image processing and control algorithms.

I. INTRODUCTION

Microrobots designed to perform targeted therapy by navigating in the cardiovascular system are a prolific research area for minimally invasive surgeries [START_REF] Ishiyama | Magnetic micromachines for medical applications[END_REF][2] and treatments efficiency through early diagnosis of diseases [START_REF] Cavalcanti | Nanorobot for Brain Aneurysm[END_REF]. When microrobots are propelled in the body fluids, especially in the blood circulatory system, a very large number of remote locations in the human body become accessible. Because the method of propulsion should allow such a microrobot to navigate through the cardiovascular system, the use of the normal blood flow itself must be considered only as a complementary means of propulsion when the travel path is in the direction of the blood flow. These untethered microrobots have been mainly developed according to three different designs: magnetic bead pulling [START_REF] Abbott | Robotics in the Small[END_REF], biomimetic flagellated robot [START_REF] Behkam | Design methodology for biomimetic propulsion of miniature swimming robots[END_REF] and magnetotactic bacteria [START_REF] Martel | Flagellated magnetotactic bacteria as controlled MRItrackable propulsion and steering systems for medical nanorobots operating in the human microvasculature[END_REF]. Furthermore, navigation requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct on-line the microrobot's pose error between the planned and the observed trajectory. Recently, magnetic resonance imaging (MRI)-based medical microrobotic platforms are investigated to reach locations deep in the human body while enhancing targeting efficacy using real-time navigational and trajectory control [START_REF] Felfoul | In vivo MRtracking based on magnetic signature selective excitation[END_REF]. For the position recognition of the microrobot in the blood vessels, from the pre-operation images, 3D path planning and route optimization solutions have been proposed. The authors in [START_REF] Sabra | Use of 3D potential field and an enhanced breath-first search algorithms for path-planning of microdevices propelled in the cardiovascular system[END_REF] proposed an endovascular path-planning method based on 3D potential

The authors are with the Institute PRISME EA 4229; ENSI de Bourges, 88 boulevard Lahitolle, 18020 Bourges, FRANCE; {karim.belharet, david.folio, antoine.ferreira} @ensi-bourges.fr fields and enhanced breath-first search algorithms based on MR-imaging. Based on these path-planning techniques, only explorative 2D control strategies have been adopted so far using simple proportional-integral-derivative (PID) controller [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF]. However, stability and robustness are not ensured against important perturbations. First, pulsatile flow whose variations in waveform, amplitude, and frequency exists from one vessel to another. Second, variation of time-multiplexed sequence parameters (duty cycle of the propulsion gradients, and repetition time of the tracking sequence) produce important trajectory errors during real-time navigation. Finally, random imaging signal noise degrades the localization of the microrobot during tracking.

The main objective of this paper is to propose an automated technique based on image processing and control algorithms for path finding, reconstruction and navigation control of a ferromagnetic microrobot using an MRI system. The MRI-based control of a ferromagnetic microcapsule presented here is dedicated to macroscale navigation, which focuses in conveying the device in vessels such as arteries and arterioles. Based on slice images provided by an MRI system, relevant information related to detection of blood vessels is extracted using robust Frangi vesselness filtering from the pre-operation images. Then, a set of minimal trajectory is predefined, using Fast Marching Method (FMM), to guide the ferromagnetic microrobot from the injection point to the tumor area through the anarchic vessel network. Based on the precomputed path, a Model Predictive Controller (MPC) is designed for robust time-multiplexed navigation along a 3D path in presence of pulsative flow. The simulation results suggest the validation of the proposed image processing and control algorithms.

II. MRI-BASED NAVIGATION SYSTEM

A. System Overview

The MRI-based microrobotic system is used here for propulsion and navigation of the micro-device. The propulsion of the ferromagnetic microcapsule in the cardiovascular system is realized through the induction of force from magnetic gradients provided by the MRI. This MRI system will guide the micro-capsule in vivo through vascular networks to a targeted area. The overview of the software system architecture is given in Fig. 1. (i) The graphical user interface module, which comprises input command prompt, 3D-visualization, and process supervision tools. (ii) The control module, which comprises (a) the high-level controller responsible for the microcapsule navigation tasks and for the generation of the magnetic field gradients and (b) the low-level controller (manufacturer MRI controller) responsible for implementing the actuation commands for the generation of the desired field gradients and for the image acquisition tasks. Then, (iii) the controlled hardware, which comprises (a) the MRI hardware and software systems and (b) the microcapsules that have been injected within the vasculature and are navigated by the field gradients. Finally, (iv) the image processing module, which comprises the MRI image reconstruction and the image-processing software that estimates the position and accumulation of the microdevices within the vasculature, the tissues, and the organs of the human.

B. Navigation in blood vessels

In our context, the problem of navigation in blood vessels within the MRI data can be formulated as finding the correct way through the data which follows the vessel of interest between its start and end point. Finding a navigation path within the endovascular network is then an essential, primary, and important step which must be addressed prior to the control procedure. The problem of vessels extraction has received considerable attention in the computer vision and medical imaging communities [START_REF] Kirbas | A review of vessel extraction techniques and algorithms[END_REF]. Hence, several class of methods have been proposed to find a path from a set of medical imaging, such as using tracking methods [START_REF] Reuzé | A 3D moment based approach for blood vessel detection and quantification in MRA[END_REF] [6] [START_REF] Tokuda | Integrated navigation and control software system for mri-guided robotic prostate interventions[END_REF], path extraction methods [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF][13] [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF], and so on. Most works based on in vivo MR-tracking methods usually need many user-defined way points as the input of a controller module for the navigation computation. A major drawback in general remains when the user must define many points (e.g. way or fiducial points) manually. Hence, for a complex structure (e.g. colon, small vessels. . . ) the required interactivity can be very tedious. As consequence, if the path is not correctly build, it can cross an anatomical wall during the in vivo navigation. The path extraction is useful for a range of application domains including medical image analysis, robot navigation, and artificial intelligence. The path extraction technique needs a very simple initialisation and leads to global minimum of a snake-like energy, thus avoiding local minima. Moreover it is fast and accurate. This path finding problem has been studied for ages by mathematicians, and has been solved numerically using graph theory or dynamic programming. Cohen and Kimmel [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF] solved the minimal path problem in 2D with a front propagation equation between the two fixed end points, using the Eikonal equation (that physically models wave-light propagation), with a given initial front. Wink et al. [START_REF] Wink | Minimum cost path determination using a simple heuristic function[END_REF] explored different methods to determine the minimum cost path through a pre-defined cost image, for extraction of vessel centrelines from medical image data. Among them are Dijikstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], the A ⋆ algorithm [START_REF] Pearl | Heuristics: intelligent search strategies for computer problem solving[END_REF], which makes use of additional heuristics to steer the search process, and wave front propagation analysis [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF]. Early, Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] explore the use of Fast Marching Method (FMM) to extract minimal paths. This method relies on the fact that the gradient of the FMM arrival function has only one local minimum, with is guaranteed to be global minimum [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF]. Therefore the minimal path can be extracted by back-propagating from given seeds (e.g. the end point of the desired path) to the starting point implicitly embedded in the arrival function.

In this work the FMM is adopted to design a set of trajectory to guide the micro-device from the injection point to the tumor area through the vessel network. Our aim is to focus on the automation of the path construction, reducing the need of interaction and improving performance, in a robust way.

III. MRI-BASED PREDICTIVE CONTROL

A. Problem formulation

Navigation in blood vessel requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct online the microrobot pose error between the planned and the observed trajectory. To insure a smooth conveyance of the microcapsule to destination, collisions and the risk to be trapped by the endothelium, optimal navigation performance will be affected by external perturbations and MRI technological constraints:

• Nonnegligible pulsatile flow, whose variations in waveform, amplitude, and frequency exist from one vessel to another (such as arteries and arterioles). • Magnetic gradients are used both for observation and control purposes in a time-multiplexed sequence. It requires different trade-offs in terms of refresh rate, duty cycle of the propulsion gradients, and repetition time of the tracking sequence. • MRI overheating avoidance leading to limitations on the MRI duty cycle, tends to increase the disproportional scaling between magnetic forces used for control purpose and perturbation forces (drag forces and net buoyancy forces). • Limitations on the magnetic gradient amplitude in available MRI devices.

• Proper delay in the image processing algorithms that renders the navigation control unstable.

B. Real-Time Sequence Design

Fig. 2. Timeline of acquisition and control prediction.

The overall concept of the in-vivo MRI-tracking system is based on the fact that both tracking and propulsion is possible with the gradient coils of the MRI system. Software based upgrading of a clinical MRI system is the least expensive approach to convert a platform that is used for imaging to an effective interventional platform. At any instant only one of the functions could be applied (i.e. either tracking or propulsion), but both will be executed over the same MRI interface. The MRI interface has therefore to be shared and a time-division-multiple-access scheme for it has to be developed. Fig. 4 shows an overview of the real-time sequence with time-multiplexed positioning and propulsion phases introduced by Martel et al. [START_REF] Felfoul | In vivo MRtracking based on magnetic signature selective excitation[END_REF]. The main aspect relevant to the controller's performance is (i) the duty cycle T Prop /T s that stands for the ratio between the propulsion time and the time between two successive position requests, and (ii) the synchronization event delay T Sync that stands for the minimum time allowed for image processing and real-time control feedback (see Fig. 2). First, the duty cycle should be adapted to apply sufficient magnetic propulsion gradients during a predefined propulsion time T Prop to prevent the microrobot from drifting away from the trajectory. Second, a large time delay T Sync produces oscillations as the microrobot approaches the reference trajectory w leading to position instabilities. Such limitations have been pointed out by Mathieu et al. [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF] when implementing simple proportionalintegral-derivative (PID) controller. We proposed a Model Predictive Controller (MPC) including microrobot's motion and dynamics with estimation of the pulsative blood flow and time-multiplexed positioning. A predictive trajectorytracking control consider a prediction window (cf. Fig. 2). The propulsion phase starts during T Prop seconds at the same initial condition as the prediction phase, recording the performance of the system according to a prediction horizon. After this phase the system ends after a imaging-propulsion sequence at a final position Y which is set as the new initial condition of the next prediction output Y . The proposed navigation based predictive controller offers stability by design and allows the designer to trade-off performance for (computation) speed, stability margins according to the MRI application and technological requirements outlined in section III-A.

C. Model description

The linear model that was used in this work, derived from the nonlinear model developed in a previous study [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF]. In [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF], we used this model to combine the backstepping controller and high gain observer in order to control the trajectory of microrobot inside a vessel using the MRI gradients, as shown on Fig. 4. The different forces acting on the microrobot are (see Fig. 3): drag force -→ F d , apparent weight -→ W a and magnetic force -→ F m . The application of Newton's third law and the projection on the ( -→ x , -→ y , -→ z ) axes leads to:

     m ẍ = - → F dx + - → F mx m ÿ = - → F dy + - → F my mz = - → F dz + - → F mz + - → W a ( 1
)
where m is the mass of the microrobot.

Let - → v = (v f x , v f y , v f z )
denotes the blood flow velocity, and (x, y, z) the robot location in the blood vessel wrt. to a given frame F (O, -→ x , -→ y , -→ z ). Taking the drag coefficient C d = 24 Re , the linear model can be written as follow:

   ẍ = α 1 ẋ -v f x + α 2 u x ÿ = β 1 ẏ -v f y + β 2 u y z = γ 1 ż -v f z + γ 2 u z (2)
with the following parameters α i , β i and γ i , and the magnetic gradients considered as control inputs u x , u y and u z , that is:

             α 1 = -4.5 η cos ϕ cos θ r 2 ρ , u x = - → ∇ B x β 1 = -4.5 η cos ϕ sin θ r 2 ρ , u y = - → ∇ B y γ 1 = -4.5 η sin ϕ r 2 ρ , u z = - → ∇ B z α 1 = β 2 = γ 2 = m ρ ( 3
)
where ρ is the density of the fluid; η is the fluid viscosity; r is the spherical radius of the microrobot; and B = (B x , B y , B z ) T is the magnetic field generate by the MRI system. Finally, the state space representation is deduce from (2): where (v x , v y , v z ) T denote the robot velocity along -→ x -axis, -→ y -axis and -→ z -axis. Assuming that microrobot location (x, y, z) can be measured thanks to the MRI system, we denote by Y = (x, y, z) T the process measure. We can notice that system (S) can be divided into three subsystems (S x ), (S y ) and (S z ), which allow us to define three independents MPC schemes to track the reference trajectory w in 3D MRI data.

(S)                ẋ = v x vx = α 1 v x -α 1 v f x + α 2 u x (S x ) ẏ = v y vy = β 1 v y -β 1 v f y + β 2 u y (S y ) ż = v z vz = γ 1 v z -β 1 v f z + γ 2 u z (S z ) (4)
In this paper we aim to embed the system model ( 4) in high level a MPC scheme in order to follow efficiently a preplaned path extracted with the method proposed in section II-B. Our controller is entended to be above our low level robust controller designed in [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF] (see Fig. 4).

D. Predictive Control

Model Predictive Control (MPC) has become an area of significant research interest over the last twenty years. This interest has been powered by a stream of successful industrial applications [START_REF] Qin | A survey of industrial model predictive control technology[END_REF]. When focusing on linear (and unconstrained) discrete time transfer function models and quadratic cost functions, some of the best known approaches include the Generalized Predictive Control (GPC) introduced by Clarck et al. [START_REF] Clarke | Generalized predictive control -Part I & II[END_REF], the inner loop stabilizing Stable Predictive Control [START_REF] Kouvaritakis | Stable generalised predictive control: an algorithm with guaranteed stability[END_REF], and so on.

MPC refers to a class of computer control algorithms which use an explicit process model to predict the future response of system. One way to design MPC is to use an extended state-space representation, which is given by:

Ẋk+1 = AX k + B∆u k Y k = CX k ( 5
)
where ∆u k = u ku k-1 is the discrete difference operator. The predicted state vector at time k + i is then computed from [START_REF] Camacho | Model predictive control[END_REF]:

X k+i|k = A i X k|k-1 + i-1 ∑ j=0 A j Bu k-j-1 (6)
Then, the future outputs Y k+ j|k can be computed based on the plant for future times starting at time k using a recursion procedure, that is:

Y k+i|k = C A i X k + i ∑ j=1 A i-j-1 Bu k+i-j|k (7)
Design criterion is defined for certain interval of predictions (several steps to future). It includes the part of control error, in which the model of system is covered (insertion of equations of prediction ( 7)) and part of control actions, where the input energy (control actions) is weighted. This part redistributes control errors to individual steps of predictions and provides coupling within interval of predictions. Usual form of the criterion for predictive design is written as follows:

J k = N 2 ∑ j=N 1 +1 Y k+ j W T k+ j Q Y Y k+ j W k+ j + N u ∑ j=1 u T k+ j-1 Q u u k+ j-1 (8)
The criterion is expressed in step k. N = N 2 -N 1 is a horizon of prediction, N u is the control horizon. Q Y and Q u are output and input penalizations. Y k+ j and u k+ j-1 are output and input (full or incremental) values. Finally, let us note how to construct real control actions at incremental algorithm: after computing a vector for whole horizon, only first control u k is used; then to obtain the full control actions the second line of equation ( 5) is applied.

When using MPC in the state-space formulation and generally at the use of whichever stat-space control, it is necessary to solve the question of availability of the state of the system (state vector). If it is not available and only system output from the measurement are known, then some state-space estimation has to be considered. Suitable, wellknown solution of such estimation is the state space observer based on Kalman filter [START_REF] Anderson | Optimal filtering[END_REF].

IV. RESULTS

A. Navigation Path Extraction

The FMM algorithm, introduced by Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] is applied here to extract a targeted navigation path within the vessel network. Hence, from the set of 3D MRI data we have first to compute a speed map (ie. a weighting image map), which must enhance the relevant intravascular network. Choosing an appropriate and efficient image cost function is the most difficult part of the entire process.

We describe in the sequel presented in Fig. 5, the process used to extract navigation path. First, we need a relevant cost function which allow to enhance vessel in the image.

To this aim we use some a priori knowledge about vessel shape and intensity in MRI data (cf. Fig. 5). Vessels are expected to appear as bright tubular structures in a darker environment. One way to account for the varying size of vessels is by multiscale analysis. It allows us to detect structures of different sizes according to the scale at which they give maximal response. In this context, a typical speed image is produced by using a Frangi vesselness filter [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] which uses the eigenvectors of the Hessian matrix at each voxel of the image to compute the likeliness of an image region to vessels. This mapping is selected in such a way that vessels regions will have higher speed (high level in speed image, see Fig. 5). Once the speed map is generated, the user has to select a start and end points (ie. seed points) in the viewer of the input original image. The FFM will then propagate a front from the start seed and traveling to the targeted area, thanks to the speed map. Thus, this approach allow to find a minimal navigation path between the start and targeted seed (cf. Fig. 5).

B. Microdevice Navigation using Predictive Control

Simulations are conducted within the scope of actual commonly spread MRI system abilities. At the moment, MRI systems are able to generate magnetic gradients with an intensity of some tens of mT.m -1 . Let us note that this limitation is additionally affected by the gradient coils duty cycle and by the multiplexing needed both for controlling and observing. In order to make sure that the amplitude of the control inputs remains bounded by physical actuators limits u i,max and to protect the system, we perform a simple time scaling. Thus, the applied control law is given by u i k(t) , with k(t) =max 1, u i u i,max . The set of simulations corresponds to microcapsule's radius of r = 300 µm and a time scaling settled at k(t) = 0.55. Different situations are considered in this section to illustrate and validate the performance and robustness of the proposed MRI-based predictive controller shown on Fig. 4. We validated the proposed control strategy on 3D endovascular navigation path extracted from MRIdata with the method presented previously. Furthermore, to evalute the efficiency of the proposed MRI-based predictive controller, we have performed some tests with a white Gaussian noise on the sytem output measure Y . Fig. 6 present the trajectories followed by the microrobot, and Fig. 7 describe the relative error norm between the current position Y and the reference w, for N = 5. As one can see the system output Y follows perfectly the reference trajectory w. In particular, the microdevice is able to reach quickly the navigation path, in spite of a gap between the initial position Y and the begin of reference w.

Let us notice that that the 3D tracking is not too much affected by the noise, since position standard deviation (std) and root mean square (RMS) error are quite satisfactory. Fig. 8 shows the impact of the time horizon N on the system tracking error. As one can see, for our system, N must be choose between 3 and 10. Moreover, comparing the error statistics, the nature of anticipation of the MPC scheme is illustrate, that is greater is N more is anticipate the path behaviour, increasing the trajectory tracking error. Hence, a great value of N does not necessarily guarantee good performance, and classicaly increase the complexity of the scheme.

V. CONCLUSIONS

The proposed MRI-based ferromagnetic microcapsule steering and navigation strategy has been developed at milliscale and microscale, where endovascular navigation path extraction and predictive controller have been designed. The main drawback of MRI-based navigation stems from the strong limitations on the magnetic gradient amplitude of available MRI devices. As magnetic forces used for propelling are volumetric, whereas the drag force is at best dependent on the microcapsule's area, the smaller the capsule, the higher the required control forces with respect to hydrodynamic perturbations. Consequently, this approach is well conditioned for beads whose radius is up to a few dozen micrometers with actual MRI devices. Targeting aims at focusing these micro-carriers and stopping them through embolization at the arterioles entry close to the occluded blood vessels. Possible releasing mechanisms could rely on biodegradable polymer and techniques used in hyperthermia where aggregates of nanocapsules can be heated to melt polymer. Such a solution is actually under experimentation for validation of the proposed minimally invasive MRI-based microrobotic system.

Fig. 1 .

 1 Fig. 1. Overall sytem overview.

Fig.

  Fig. Forces applied on microrobot navigating in blood vessel.

Fig. 4 .

 4 Fig. 4. MRI-based Predictive Control strategy.

Fig. 5 .

 5 Fig. 5. 3D Navigation path extraction processing: a) Original 3D MRI data; b) Computed cost function using Frangi filter (here displayed in red volume); c) Extracted navigation path between the start and end seeds using FFM.

Fig. 6 .

 6 Fig. 6. 3D MRI-based microrobot endovascular navigation (N = 5, in mm).

  Fig. 7. 3D Tracking error: Yw (N = 5).

Fig. 8 .

 8 Fig. 8. Tracking error statistics for different time horizon N.

VI. ACKNOWLEDGMENTS This work was supported by European Union's 7th Framework Program and its research area ICT-2007.3.6 Micro/nanosystems under the project NANOMA (Nano-Actuactors and Nano-Sensors for Medical Applications). The PhD student K. Belharet is supported by the Nano-IRM project, founded by Region Centre and City of Bourges.


Karim Belharet
email: karim.belharet@ensi-bourges.fr

David Folio
email: david.folio@ensi-bourges.fr

Antoine Ferreira
email: antoine.ferreira@ensi-bourges.fr

Endovascular Navigation of a Ferromagnetic Microrobot Using MRI-based Predictive Control

This paper presents real-time MRI-based control of a ferromagnetic microcapsule for endovascular navigation. The concept was studied for future development of microdevices designed to perform minimally invasive interventions in remote sites accessible through the human cardiovascular system. A system software architecture is presented illustrating the different software modules to allow 3D navigation of a microdevice in blood vessels, namely: (i) vessel path planner, (ii) magnetic gradient steering, (iii) tracking and (iv) closed-loop navigation control. First, the position recognition of the microrobot into the blood vessel is extracted using Frangi vesselness filtering from the pre-operation images (3D MRI imaging). Then, a set of minimal trajectory is predefined, using Fast Marching Method (FMM), to guide the microrobot from the injection point to the tumor area through the anarchic vessel network. Based on the pre-computed path, a Generalized Predictive Controller (GPC) is proposed for robust time-multiplexed navigation along a 2D path in presence of pulsative flow. The simulation results suggest the validation of the proposed image processing and control algorithms. A series of disturbances introduced in the presence and absence of closed-loop control affirms the robustness and effectiveness of this predictive control system.

I. INTRODUCTION

Microrobots designed to perform targeted therapy by navigating in the cardiovascular system are a prolific research area for minimally invasive surgeries [START_REF] Ishiyama | Magnetic micromachines for medical applications[END_REF][2] and treatments efficiency through early diagnosis of diseases [START_REF] Cavalcanti | Nanorobot for Brain Aneurysm[END_REF]. Cardiovascular problems are generally correlated with the obesity, human sedentary lifestyle, or hereditary characteristics. When microrobots are propelled in the body fluids, especially in the blood circulatory system, a very large number of remote locations in the human body become accessible. However, since the diameters of the blood vessels in the human body may vary from approximately 25 mm (aorta) down to 0.010 mm (capillaries), it is obvious that propelling such wireless microdevices in the human cardiovascular system with existing technologies represents a great technical challenge [START_REF] Abbott | How should microrobots swim?[END_REF]. Because the method of propulsion should allow such a microrobot to navigate through the cardiovascular system, the use of the normal blood flow itself must be considered only as a complementary means of propulsion when the travel path is in the direction of the blood flow. These untethered microrobots have been mainly developed according to three different designs: magnetic bead pulling [START_REF] Abbott | Robotics in the Small[END_REF], biomimetic flagellated robot [START_REF] Behkam | Design methodology for biomimetic propulsion of miniature swimming robots[END_REF] and magnetotactic bacteria [START_REF] Martel | Flagellated magnetotactic bacteria as controlled MRItrackable propulsion and steering systems for medical nanorobots operating in the human microvasculature[END_REF]. Furthermore, navigation requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct on-line the microrobot's pose error between the planned and the observed trajectory. Recently, magnetic resonance imaging (MRI)-based medical microrobotic platforms are investigated to reach locations deep in the human body while enhancing targeting efficacy using real-time navigational and trajectory control [START_REF] Felfoul | In vivo MRtracking based on magnetic signature selective excitation[END_REF]. For the position recognition of the microrobot in the blood vessels, from the pre-operation images, 3D path planning and route optimization solutions have been proposed. The authors in [START_REF] Sabra | Use of 3D potential field and an enhanced breath-first search algorithms for path-planning of microdevices propelled in the cardiovascular system[END_REF] proposed an endovascular path-planning method based on 3D potential fields and enhanced breath-first search algorithms based on MR-imaging. In [START_REF] Park | Frontier research program on biomedical robot for intravascular therapy[END_REF], Intra-Vascular Ultra-Sound medical imaging technique coupled to pre-operational images of computerized tomography renders possible 3D navigation in blood vessels. Based on these path-planning techniques, only explorative 2D control strategies have been adopted so far using simple proportional-integral-derivative (PID) controller [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF]. However, stability and robustness are not ensured against important perturbations. First, pulsatile flow whose variations in waveform, amplitude, and frequency exists from one vessel to another. Second, variation of time-multiplexed sequence parameters (duty cycle of the propulsion gradients, and repetition time of the tracking sequence) produce important trajectory errors during real-time navigation. Finally, random imaging signal noise degrades the localization of the microrobot during tracking.

The main objective of this paper is to propose an automated technique based on image processing and control algorithms for path finding, reconstruction and navigation control of a ferromagnetic microrobot using an MRI system. The MRI-based control of a ferromagnetic microcapsule presented here is dedicated to macroscale navigation, which focuses in conveying the device in vessels such as arteries and arterioles. As illustration of the concept, we consider a possible way for the microrobot get into the body through the femoral artery in the leg, which is the normal access point to the circulatory system. One possible application is to locate atherosclerotic lesions in stenosed blood vessels, particularly in vasculary circulation, and treat them either chemically or pharmacologically by targeted drug delivery. Based on slice images provided by an MRI system, relevant information related to detection of blood vessels is extracted using robust Frangi vesselness filtering from the pre-operation images. Then, a set of minimal trajectory is predefined, using Fast Marching Method (FMM), to guide the ferromagnetic microrobot from the injection point to the tumor area through the anarchic vessel network. Based on the precomputed path, a Generalized Predictive Controller (GPC) is designed for robust time-multiplexed navigation along a 2D path in presence of pulsative flow. The simulation results suggest the validation of the proposed image processing and control algorithms. A series of disturbances introduced in the presence and absence of closed-loop control affirms the robustness and effectiveness of this predictive control system.

II. ENDOVASCULAR NAVIGATION

A. Finding Endovascular Navigation Path

In our context, the problem of finding the navigation path within the MRI data can be formulated as finding the correct way through the data which follows the vessel of interest between its start and end point. Finding a navigation path within the vessel network is then an essential, primary, and important step which must be addressed prior to the control procedure. The problem of vessels extraction has received considerable attention in the computer vision and medical imaging communities [START_REF] Kirbas | A review of vessel extraction techniques and algorithms[END_REF]. Hence, several class of methods have been proposed to find a path from a set of medical imaging, such as using tracking methods [START_REF] Reuzé | A 3D moment based approach for blood vessel detection and quantification in MRA[END_REF] [7] [START_REF] Tokuda | Integrated navigation and control software system for mri-guided robotic prostate interventions[END_REF], path extraction methods [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF][15] [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF], and so on. Most works based on in vivo MR-tracking methods usually need many user-defined way points as the input of a controller module for the navigation computation. A major drawback in general remains when the user must define many points (e.g. way or fiducial points) manually. Hence, for a complex structure (e.g. colon, small vessels. . . ) the required interactivity can be very tedious. As consequence, if the path is not correctly build, it can cross an anatomical wall during the in vivo navigation. In opposition, path extraction approaches depend only on the manual definition of the start and end points of the desired vascular path. Therefore, we propose in this work to use path extraction technique to find the desired path to be followed in the vessel network.

1) Endovascular Path Extraction:

The path extraction is useful for a range of application domains including medical image analysis, robot navigation, and artificial intelligence. The path extraction technique needs a very simple initialisation and leads to global minimum of a snake-like energy, thus avoiding local minima. Moreover it is fast and accurate. This path finding problem has been studied for ages by mathematicians, and has been solved numerically using graph theory or dynamic programming. Cohen and Kimmel [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF] solved the minimal path problem in 2D with a front propagation equation between the two fixed end points, using the Eikonal equation (that physically models wave-light propagation), with a given initial front. Wink et al. [START_REF] Wink | Minimum cost path determination using a simple heuristic function[END_REF] explored different methods to determine the minimum cost path through a pre-defined cost image, for extraction of vessel centrelines from medical image data. Among them are Dijikstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], the A ⋆ algorithm [START_REF] Pearl | Heuristics: intelligent search strategies for computer problem solving[END_REF], which makes use of additional heuristics to steer the search process, and wave front propagation analysis [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF]. Early, Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] explore the use of Fast Marching Method (FMM) to extract minimal paths. This method relies on the fact that the gradient of the FMM arrival function has only one local minimum, with is guaranteed to be global minimum [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF]. Therefore the minimal path can be extracted by backpropagating from given seeds (e.g. the end point of the desired path) to the starting point implicitly embedded in the arrival function.

In this work the FMM is adopted to design a set of trajectory to guide the micro-device from the injection point to the tumor area through the vessel network. Our aim is to focus on the automation of the path construction, reducing the need of interaction and improving performance, in a robust way. Finally, as the proposed control strategy, presented in section III-B, is designed for 2D navigation problem, we have limited our path extraction procedure to 2D application.

2

) Applications and Navigation Path Extraction Results:

The FMM algorithm, introduced by Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] is applied here to extract a targeted navigation path within the vessel network. The FMM is very closely related to Dijkstra's method [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], which is a very well-known method from the 1950's for computing the shortest path on a network. Hence, from the set of MRI data we have first to compute a speed map (ie. a weighting image map), which must enhance the relevant intravascular network. Choosing an appropriate and efficient image cost function is the most difficult part of the entire process. The definition of the optimal speed function is case dependent and should be set by the user, along with the start and end points of the path. Hence, an optimal path could be found only if the optimal cost function is provided. In this work, we focus mainly on finding a path allowing reaching the targeted zone. We describe in the sequel presented in Fig. 1, the process used to extract navigation path. First, we need a relevant cost function which allow to enhance vessel in the image.

To this aim we use some a priori knowledge about vessel shape and intensity in MRI data (cf. Fig. 2). Vessels are expected to appear as bright tubular structures in a darker environment. One way to account for the varying size of vessels is by multiscale analysis. It allows us to detect structures of different sizes according to the scale at which they give maximal response. In this context, a typical speed image is produced by using a Frangi vesselness filter [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] which uses the eigenvectors of the Hessian matrix at each voxel of the image to compute the likeliness of an image region to vessels. This mapping is selected in such a way that vessels regions will have higher speed (high level in speed image, see Fig. 2). Once the speed map is generated, the user has to select a start and end points (ie. seed points) in the viewer of the input original image. The FFM will then propagate a front from the start seed and traveling to the targeted area, thanks to the speed map. This step allow to build an image of distance between the start seed and all other pixels. The corresponding shortest path is then traced thanks to the distance map. We have applied the described approach on some representative MRI data which validate our image processing pipeline. The application is to locate atherosclerotic lesions in stenosed blood vessels, particularly in vascular circulation. We consider that the microrobot into the body through the femoral artery in the leg, and treat them pharmacologically, by tageted drug delivery. Let us also notice that the proposed image processing pipeline (cf. Fig. 1) could be applied to 3D MRI data, and then provide 3D navigation path.

III. MRI-BASED CONTROL DESIGN

A. Problem formulation

Endovasular navigation requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct online the microcapsule's pose error between the planned and the observed trajectory. To insure a smooth conveyance of the microrobot to destination, collisions and the risk to be trapped by the endothelium, optimal navigation performance will be affected by external perturbations and MRI technological constraints:

• Nonnegligible pulsatile flow, whose variations in waveform, amplitude, and frequency exist from one vessel to another (such as arteries and arterioles). The overall concept of the in-vivo MRI-tracking system is based on the fact that both tracking and propulsion is possible with the gradient coils of the MRI system. Software based upgrading of a clinical MRI system is the least expensive approach to convert a platform that is used for imaging to an effective interventional platform. At any instant only one of the functions could be applied (i.e. either tracking or propulsion), but both will be executed over the same MRI interface. The MRI interface has therefore to be shared and a timedivision-multiple-access scheme for it has to be developed. Fig. 4 shows an overview of the real-time sequence with timemultiplexed positioning and propulsion phases introduced by Martel et al. [START_REF] Felfoul | In vivo MRtracking based on magnetic signature selective excitation[END_REF]. The main aspect relevant to the controller's performance is (i) the duty cycle T Prop /T s that stands for the ratio between the propulsion time and the time between two successive position requests, and (ii) the synchronization event delay T Sync that stands for the minimum time allowed for image processing and real-time control feedback (see Fig. 4). First, the duty cycle should be adapted to apply sufficient magnetic propulsion gradients during a predefined propulsion time T Prop to prevent the microrobot from drifting away from the trajectory. Second, a large time delay T Sync produces oscillations as the microrobot approaches the reference trajectory leading to position instabilities. Such limitations have been pointed out by Mathieu et al. [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF] when implementing simple proportional-integral-derivative (PID) controller. We proposed a Generalized Predictive Controller (GPC) including microrobot's motion and dynamics with estimation of the pulsative blood flow and time-multiplexed positioning. A predictive trajectory-tracking control consider a prediction window (cf. Fig. 4). The propulsion phase starts during T Prop seconds at the same initial condition as the prediction phase, recording the performance of the system according to a prediction horizon. After this phase the system ends after a imaging-propulsion sequence at a final position q which is set as the new initial condition of the next prediction output q. The proposed navigation based predictive controller offers stability by design and allows the designer to trade-off performance for (computation) speed, stability margins according to the MRI application and technological requirements outlined in section III-A.

C. Model description

The linear model that was used in this work, derived from the nonlinear model developed in a previous study [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF]. In [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF], we used this model to combine the backstepping controller and high gain observer in order to control the trajectory of microrobot inside a vessel using the MRI gradients, as shown on Fig. 3.

The different forces acting on the microrobot are (see figure 5): drag force -→ F d , apparent weight -→ W a and magnetic force -→ F m . The application of Newton's third law and the projection on the -→ x -axis and -→ y -axis leads to:

m ẍ = - → F dx + - → F mx m ÿ = - → F dy + - → F my + - → W a ( 1
)
where m is the mass of the microrobot. Let -→ v = (v f x , v f x ) denotes the blood flow velocity, and (x, y) the robot location in the blood vessel wrt. to a given frame F (O, -→ x , -→ y ). Taking the drag coefficient C d = 24 Re , the linear model can be written as follow:

ẍ = α 1 ẋ -v f x + α 2 u x ÿ = β 1 ẏ -v f y + β 2 u y (2)
with the following parameters α i and β i , and the magnetic gradients considered as control inputs u x and u y , that is:

       α 1 = -4.5 η cos θ r 2 ρ , u x = - → ∇ B x β 1 = -4.5 η sin θ r 2 ρ , u y = - → ∇ B y α 1 = β 2 = m ρ (3)
where ρ is the density of the fluid; η is the fluid viscosity; r is the spherical radius of the microrobot; and B = (B x , B y ) T is the magnetic field generate by the MRI system.

Finally, the state space representation is deduce from (2):

(S)        ẋ = v x vx = α 1 v x -α 1 v f x + α 2 u x (S x ) ẏ = v y vy = β 1 v y -β 1 v f y + β 2 u y (S y ) (4)
where (v x , v y ) T denote the robot velocity along -→ x -axis and -→ y -axis. Assuming that microrobot location (x, y) can be measured thanks to the MRI system, we denote by q = (x, y) T the process measure. We can notice that system (S) can be divided into two subsystems (S x ) and (S y ), which allow us to define two independents GPC schemes to track the reference trajectory in 2D MRI data.

In this paper we aim to embed the system model ( 4) in high level a GPC scheme in order to follow efficiently a preplaned path extracted with the method proposed in section II-A. Our controller is entended to be above our low level robust controller designed in [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF] (see Fig. 3).

D. Generalized Predictive Control (GPC)

Generalized Predictive Control (GPC) belongs to the class of Model Predictive Control (MPC) techniques and was first introduced by Clarck et al. [START_REF] Clarke | Generalized predictive control -Part I & II[END_REF]. GPC approach is a popular control predictive method, experienced on several applications [START_REF] Mahfouf | Generalised predictive control and bioengineering, ser. Systems and Control[END_REF] [25], especially in industrial process [START_REF] Qin | A survey of industrial model predictive control technology[END_REF]. It combines the prediction of future behavior of the system with feedback control (see figure 3). A process model is explicitly used to predict the future behavior of the system over the given time horizon. From this prediction, a control is computed by minimizing a quadratic cost function.

1) GPC Scheme Design: The system is modeled using the model Controlled Auto-Regressive Integrated Moving-Average (CARIMA) with integrator form, that is [START_REF] Clarke | Generalized predictive control -Part I & II[END_REF]:

A(z -1 )q(t) = B(z -1 )u(t -1) +C(z -1 ) ζ (t) ∆(z -1 ) , (5)
where ∆(z -1 ) = 1z -1 define the difference operator; ζ (t) is a zero mean white noise; and A(z -1 ), B(z -1 ) and C(z -1 ) are polynomial matrix in the backward shift operator z -1 .

The GPC is classicaly obtained by minimizing a weighted sum of square predicted future errors and square control signal increments:

J {N 1 ,N 2 ,N u ,λ } = N 2 ∑ j=N 1 ( y(t + j) -w(t + j)) 2 +λ N u ∑ j=1 ∆u 2 (t + j -1) (6)
where y(t + j) is the optimum predicted output of the system at time t + j; w(t + j) is the future reference; N 1 and N 2 are the minimum and the maximum of the prediction horizon; N u is the control horizon; and λ > 0 is the control increment weighting. {N , N 2 , N u , λ } are the design parameters of the GPC scheme.

The optimal predictor built from the measured output data up to time t and any given u(t + j) for j > 1 is:

q = G u + f(z -1 )q(t) + h(z -1 )∆u(t -1) (7)
where f(z -1 ) and h(z -1 ) are the polynomial calculated by solving the Diophantine equations:

A(z -1 )J j (z -1 )∆(z -1 ) + z -1 F j (z -1 ) = 1 B(z -1 )J j (z -1 ) = G j (z -1 ) + z -1 H j (z -1 ) f = F N 1 (z -1 ) . . . F N 2 (z -1 ) T h = H N 1 (z -1 ) . . . H N 2 (z -1 ) T u = [∆u(t) . . . ∆u(t + N u -1)] T q = [ q(t + N 1 ) . . . q(t + N 2 )] T G =       g N 1 N 1 g N 1 N 1 -1 . . . g N 1 +1 N 1 +1 g N 1 +1 N 1 . . . . . . . . . g N 2 N 2 g N 2 N 2 -1 . . . g N 2 N 2 -N u +1       (8)
where G j represents the future; F j and H j define respectively the present and the past; and J j is related to the disturbance. Hence, the optimal control is then defined by:

u = M w -f(z -1 )q(t) -h(z -1 )∆u(t -1) (9)
with w = [w(t + N 1 ) . . . w(t

+ N 2 )]; M = QG T with dimension N u × (N 2 -N 1 + 1); and Q = G T G + λ I N u -1 with dimen- sion N u × N u .
Only the first element of u is applied to the system, that is:

∆u Opt (t) = m T 1 w -f(z -1 )q(t) -h(z -1 )∆u(t -1) (10)
where m T 1 is the first row of M. Classicaly a RST polynomial structure is introduced at the end to determine a relation between the output q(t), the control signal u(t) and the setpoint w(t), according to the scheme of Fig. 3. The advantage of RST polynomial structure is that these modules can be computed off-line, providing a very short real-time loop and on the other hand offers the possibility to analyze the stability of the controlled open loop in the frequency domain. In fact, this off-line operation is a very helpful strategy to determine the stable set of tuning parameters just before applying the control law on the real system.

2) GPC implementation: In order to design the GPC controller the transfer functions of the two subsystems (S x ) and (S y ) of Eq.( 4) are obtained:

H x (s) = 243.8 s 2 + 49.25s (11)
H y (s) = 243.8 s 2 + 79.77s (12)
To ensure good stability, our GPC scheme under RST polynomial form requires tuning of the set parameters N 1 , N 2 , N u , λ x , λ y , where λ x and λ y are the control increment weighting for the two subsystems (S x ) and (S y ) respectively. Some guidelines may be found in the literature [START_REF] Clarke | Generalized predictive control -Part I & II[END_REF] [START_REF] Boucher | ser. Collection Mthodes et Pratiques de l'Ingnieur[END_REF]. Thus, two independants GPC controller have to be designed for the system sampling period T s = 50 ms. For instance, we consider the following tuning parameters, which satisfy stability and robustness features [START_REF] Boucher | ser. Collection Mthodes et Pratiques de l'Ingnieur[END_REF]:

N 1 = 1; N 2 = 4; N u = 1; λ x = 0.77; λ y = 0.34 (13)
According to these parameters, the model of the process using [START_REF] Kirbas | A review of vessel extraction techniques and algorithms[END_REF] and [START_REF] Reuzé | A 3D moment based approach for blood vessel detection and quantification in MRA[END_REF] in CARIMA [START_REF] Behkam | Design methodology for biomimetic propulsion of miniature swimming robots[END_REF] form is given by: and where C x (z -1 ) and C y (z -1 ) are set to 1. The RST form optimal control is:

(S x ) A x (z -1 ) = 1 -1.085z -1 + 0.085z -2 B x (z -1 ) = 0.155 + 0.071z -1 , (14)
(S y ) A y (z -1 ) = 1 -1.018z -1 + 0.018z -2 B y (z -1 ) = 0.115 + 0.034z -1 , (15)
∆u Opt x (t)S x (z -1 ) = T x (z -1 )w x (t) -R x (z -1 )q x (t) (16) ∆u Opt y (t)S y (z -1 ) = T y (z -1 )w y (t) -R y (z -1 )q y (t) (17) with    R x (z -1 ) = 2.855 -2.222z -1 + 0.169z -2 S x (z -1 ) = 1 + 0.140z -1 T x (z -1 ) = 0.123z + 0.273z 2 + 0.405z 3 (18)
   R y (z -1 ) = 4.0.61 -2.906z -1 + 0.052z -2 S y (z -1 ) = 1 + 0.098z -1 T y (z -1 ) = 0.206z + 0.410z 2 + 0.592z 3

E. Results

Simulations are conducted within the scope of actual commonly spread MRI system abilities. At the moment, MRI systems are able to generate magnetic gradients with an intensity of some tens of mT.m -1 . Let us note that this limitation is additionally affected by the gradient coils duty cycle and by the multiplexing needed both for controlling and observing. In order to make sure that the amplitude of the control inputs remains bounded by physical actuators limits u i,max and to protect the system, we perform a simple time scaling. Thus, the applied control law is given by u i k(t) , with k(t) =max 1, u i u i,max . The set of simulations corresponds to microcapsule's radius of r = 300 µm and a time scaling settled at k(t) = 0.55. Different situations are considered in this section to illustrate and validate the performance and robustness of the proposed MRI-based predictive controller shown on Fig. 3. As the considered system is decoupled into two subsystems (S x ) and (S y ) (4), we have first validate the control strategy onto 1D longitudinal path. As illustration, the microrobot has to follow a sinusoidal reference trajectory (cf. Fig. 6 and7) for different time horizons N = N 2 -N 1 (namely N = 3, 10, and 15). Fig. 6 presents the trajectories followed by the microrobot, and the relative error between the current position q and Fig. 7. Longitudinal position microrobot control with white noise. the reference w. As one can see the system output follows correctly the reference trajectory w for each considered prediction horizon N. The output of the closed loop system is dependent on the setting parameters of the GPC. The previous curves show the impact of N on the system. Moreover, comparing the different plots, the nature of anticipation of the GPC scheme is illustrate -greater is N more is anticipate the path behaviour-Hence, a great value of N does not necessarily guarantee good performance, and classicaly increase the complexity of the scheme.

To evalute the efficiency of the proposed MRI-based predictive controller, we added a white Gaussian noise on the sytem output measure q. Fig. 7 shows the system response in the presence of this disturbance on the system. Globally, tracking is not too much affected by the noise, since position standard deviation (std) and root mean square (RMS) error are quite satisfactory (see table I). We validated the proposed control strategy on 2D endovascular navigation path extracted from MRI-data with the method presented in section II-A. As shown in Fig. 8 and 9, the system output q follows perfectly the reference trajectory w, either without or with white Gaussian noise added. In particular, the microrobot are able to reach quickly the navigation path, in spite of a big gap between the initial position q and the begin of reference w (about 50 pixels). Fig. 8(b) and 9(b) describe the error evolution in both cases. Once again the error remains small with low values of std and RMS parameters. Let us notice that these 2D error statistics given in table I take into account the gap between the initial microrobot position and the start of the reference path. Finally, to evaluate the robustness of our strategy, we have performed some tests in which some model parameters (4) are not well identified, and the white noise still added. As illustrated in Fig. 10, the 2D trajecrory tracking error is quite important, but still remains satisfactory.

IV. CONCLUSIONS

The proposed MRI-based ferromagnetic microcapsule steering and navigation strategy has been developed at milliscale and microscale, where endovascular navigation path extraction and predictive controller have been designed. The main drawback of MRI-based navigation stems from the strong limitations on the magnetic gradient amplitude of available MRI devices. As magnetic forces used for propelling are volumetric, whereas the drag force is at best dependent on the microcapsule's area, the smaller the capsule, the higher the required control forces with respect to hydrodynamic perturbations. Consequently, this approach is well conditioned for beads whose radius is up to a few dozen micrometers with actual MRI devices. Targeting aims at focusing these micro-carriers and stopping them through embolization at the arterioles entry close to the occluded blood vessels. Possible releasing mechanisms could rely on biodegradable polymer and techniques used in hyperthermia where aggregates of nanocapsules can be heated to melt polymer. Such a solution is actually under experimentation for validation of the proposed minimally invasive MRI-based microrobotic system.

Fig. 1 .

 1 Fig. 1. Image processing pipeline.

Fig. 2 .

 2 Fig. 2. 2D Navigation path extraction processing of atherosclerotic lesions in the upper right leg: a) Original MRI data; b) Computed cost function using Frangi filter (light pixel have higher weight); c) FFM propagation to build the distance to targeted seed map; d) Extracted navigation path between the start and end seeds.

Fig. 4 .

 4 Fig. 4. Timeline of acquisition and control prediction.

Fig. 3 .

 3 Fig. 3. Navigation based-Generalized Predictive Control (GPC) strategy.

Fig.

  Fig. Forces applied on microrobot navigating in blood vessel.

Fig. 6 .

 6 Fig. 6. Longitudinal position control.

Fig. 9 .

 9 Fig. 8. 2D MRI-based microrobot endovascular navigation (N = 3).

Fig. 10 .

 10 Fig.10. 2D trajectory tracking error qw , with noise and wrong model paramaters (r + 30% and η + 10%)

V. ACKNOWLEDGMENTS

This work was supported by European Union's 7th Framework Program and its research area ICT-2007.3.6 Micro/nanosystems under the project NANOMA (Nano-Actuactors and Nano-Sensors for Medical Applications). The PhD student K. Belharet is supported by the Nano-IRM project, founded by Region Centre and City of Bourges.