Emmanuel Pietriga
email: femmanuel.pietriga@xrce.xerox.com

Jean-Yves Vion-Dury
email: jean-yves.vion-duryg@xrce.xerox.com

VXT: Visual XML Transformer

The ever growing amount of heterogeneous data exchanged through the Internet, combined with the popularity of XML, make structured document transformations an increasingly important application domain. Most of the existing solutions for expressing XML transformations are textual languages, such as XSLT or DOM combined with a general-purpose programming language. Several tools build on top of these languages, providing a graphical environment and debugging facilities. Transformations are however still specified in a textual way using the underlying language (often XSLT), thus requiring users to learn it.

We believe that visual programming techniques are wellsuited to representing XML structures and make the specification of transformations simpler. We propose a visual language for the specification of XML transformations in an interactive environment based on a zoomable user interface toolkit and on two target languages specialised in structure transformations: Circus and XSLT.

Overview

VXT is a visual programming language combined with an interactive environment, written in Java, and specifically designed for programming XML document transformations. It aims at providing high quality visual support for data structure representation and manipulation, so that the user will be freed from maintaining complex mental models of data structures, which play a central role in the transformation specification.

VXT tries to simplify the complexity brought by the different levels of abstraction (transformations rules, document instances, schemas) by unifying them in a single visual representation system (formally studied in [START_REF] Pietriga | A formal study of a visual language for the visualization of document type definition[END_REF]) focused on tree structures and based on a variation of treemaps in partnership with INRIA Rhone-Alpes (Projet OPERA), 655 Av de l'Europe, 38330 Monbonnot Saint-Martin -France [START_REF] Johnson | Treemaps: a space-filling approach to the visualization of hierarchical information structures[END_REF]. XML document instances and Document Type Definitions (DTD) can be visualised as background images which can be smoothly zoomed and panned. Transformations are specified mainly visually and consist of a set of rules which can be cascaded (thus following a model close to the one found in XSLT). The left-hand sides of all transformation rules, in charge of selecting nodes and extracting data, are specified in the same window on a transparent layer 1 which can be navigated and zoomed independently of the background. As opposed to XSLT, in which nodes to select and information to extract w.r.t them are expressed in separate statements, VXT uses the multidimensionality of visual languages to merge them in a single expression, called Visual Pattern-Matching Expression (VPME). A VPME resembles the source structure it is supposed to select and extract information from, thus giving the impression to match "visually". Extracted nodes are filled with a semi-transparent color, conveying the idea of a visual filter, which is close to the mental model associated to the considered transformations.

To improve scalability, each rule's production is specified in its own window, which contains a synchronised copy of the associated VPME on its left-hand side, and the resulttree fragment produced when this rule is fired on the righthand side. Links between the two sides indicate the type of operation applied on extracted nodes.

Transformations can be run from the environment or exported as XSLT or Circus source code (Circus is a language specialised in structure transformations positioned at a level of abstraction between XSLT and a language such as Java associated with DOM). The interactive environment also provides mechanisms to assist the user in specifying transformations, such as the automatic generation of VPMEs from source document fragments and the ability to test them on document instances at any time directly from the environment (progressive evaluation from Green's cognitive dimensions framework).

Example of transformation

Figure 1 shows a transformation that prepares a reply to an e-mail document represented in XML such as the one below:

<mail ref="ep47"> <date>26-01-2001</date> <recipient>vion-dury@xrce.xerox.com</recipient> <sender>pietriga@xrce.xerox.com</sender> <subject>Jazz</subject> <textbody>
Do you know John Coltrane?
</textbody> </mail> This transformation is made of two rules, whose VPMEs are specified in the Source window (the background layer contains a mail document which can be used to progressively evaluate those VPMEs). The two rules are respectively represented in windows t#0 and t#1. Rule t#0 matches mail elements on the condition that they contain recipient, sender and subject children. The textual content of recipient and sender are inverted while transformation rules are applied again on the subject element. The equivalent XSLT template rule is given below: <xsl:template match="mail[recipient and sender and subject]"> <mail> <sender><xsl:copy-of select="recipient"/></sender> <recipient><xsl:copy-of select="sender"/></recipient> <xsl:apply-templates select="subject"/> <textbody>

</textbody> </mail> </xsl:template> Rule t#1 matches subject and appends "Re:" to its content (the dashed octagon indicates that the text node is not required inside subject for the VPME to match, but its content is extracted if present):

Figure 1 .

 1 Figure 1. Preparing a reply to a mail

  <xsl:template match="subject"> <subject> Re: <xsl:value-of select="text()"/> </subject> </xsl:template> Icons attached to links between nodes extracted from source documents and the associated ones in the result-tree represent the type of operation to apply: = copy nodes = apply transformation rules = extract textual content

The legibility problem has been addressed by rendering the background image using shades of grey with minimum contrast while VPMEs are rendered in the foreground with highly-contrasted vivid colours.


Jean-Yves Vion-Dury
email: fjean-yves.vion-dury@xrce.xerox.com

Emmanuel Pietriga
email: emmanuel.pietrigag@xrce.xerox.com

A Formal Study of a Visual Language for the Visualization of Document Type Definition

This formal study proposes a transformational approach to the definition of general purpose visual languages based on hierarchical structures, addressing more specifically DTD visualization as its application area. We show that such visual languages can be constructed through progressive refinement of a syntax based on nested/juxtaposed rectangles. Several transformation stages, which can all be formally characterized, produce a high quality visual representation which expresses the fundamental properties of the original structure. Moreover, this approach opens some perspectives in proving visual properties through standard mathematical tools such as inductive proofs, thus establishing some practical links between visual language theory and classical language theory.

Introduction

Document Type Definitions (DTDs) are used to constrain the structure of XML documents (trees). This paper describes formally a visual language for the graphical representation of DTDs, which is used in VXT, a visual programming language specialized in the specification of XML transformations [START_REF] Pietriga | VXT: Visual XML Transformer[END_REF].

Section 2 presents the basic graphical object model we consider, and a visual syntax V adapted to the representation of hierarchical structures, such as structured documents (SGML, XML, HTML) and DTDs. The required properties of this syntax are identified and captured in a pivotal abstract syntax AS which simplifies formal treatment by abstracting over some spatial issues while still having a visual semantics. The latter is defined through a translation function from the language of AS into the language generated in partnership with INRIA Rhone-Alpes (Projet OPERA), 655 Av de l'Europe, 38330 Monbonnot Saint-Martin -France by V. Section 3 proposes a formal definition of Document Type Definitions and a first visual semantics by the means of a translation that transforms any valid DTD into a sentence of AS. Section 4 describes how such representations can be simplified and made more effective through an additional transformation based on a term rewriting system. This one reduces the number of graphical objects while preserving all the information. A subtle pretty-printing function is then presented in section 5, which enforces the perception of structural information thanks to spatial analogies. The related work section analyses other solutions for the representation of DTDs and more generally tree-based structures, showing how our work differentiates from them. The conclusion synthesizes the paper and discusses global results.

Visual Syntax

Representation model

graphical object model. We first define Gl as an abstract graphical type which does not have any representation. Objects of type Gl have five attributes, namely x y which represent the coordinates of the object's center, z for the depth of the object (this information is used to determine the order in which to paint objects) and w hfor the width and height. Renderable objects can be of type Shfor shapes or T xfor text strings. Both are subtypes of Gl, the first one defining a shape to draw, the second one a text value. Shalso has a subtype Re for a particular kind of shape : rectangles. Type Shalso defines two additional attributes for color and border style (solid or dashed). For objects of type Sh(which are not of type Re), attributes w and h are computed by respectively projecting them on horizontal and vertical axes. Graphical objects being rendered in an infinite virtual space [START_REF] Pietriga | VXT: Visual XML Transformer[END_REF], they can have negative coordinates and their width and height is not limited. CenteredOn Gl Gl (i:x = j:x) ^(i:y = j:y) LeftOf Gl Gl (i:x < j:x) ^(i:y = j:y) Above Gl Gl (i:y > j:y) ^(i:x = j:x) Over Gl Gl (i:z > j:z) Intersects Gl Gl (BB(i j):w < BB(i i):w +BB(j j):w) ^(BB(i j):h < B B (i i):h + BB(j j):h) Contains Gl Gl BB(i j) = BB(i i)

Syntax definition

We can now introduce our visual language, defined by a grammar which is based on a slightly extended version 1 of the Relational Grammar formalism described by Wittenburg et al [START_REF] Wittenburg | Relational grammars: Theory and practice in a visual language interface for process modeling[END_REF].

Definition 1

The grammar is a 5-tuple V =(N , ,S,R,P ) where : P is the following set of productions of the form A ! = =F, where A 2 N , 2 (N j ) + , is a set of relational constraints of the form (r i j ) where r 2 R and i j are integers referencing a member of (the 1 Some relational constraints reference bounding boxes defined on objects belonging to . This liberty, with respect to the formalism, is of no consequence since we are not interested in the properties associated with the fomalism : we rely on it only as a descriptive tool and do not intend to use it for parsing. left-hand-side of a rule is conventionally referenced as 0, the one or more right-hand-side elements are referenced 1::n in the order in which they appear in the definition. F is a set of assignement statements of the form (a 0) = (a i ), i referencing a member of (see [START_REF] Wittenburg | Relational grammars: Theory and practice in a visual language interface for process modeling[END_REF]):

N is the following set of nonterminals : N = fN a N b N c g.
Na ! Gl Sh 1:0 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over 2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1) Na ! Gl Tx 1:1 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over 2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1)

(w 0) = (w 1) (h 0) = (h 1) Na ! Gl Re 1:2 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over 2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1) Na ! Gl Re Na 1:3 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over 2 1 ) (CenteredOn 3 2 ) ( Contains 2 3 ) ( Over 3 2 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1)
Na ! Gl Nb 1:4 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over 2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1)

(w 0) = (w 1) (h 0) = (h 1) Na ! Gl Na Nc 1:5 (Contains 1 BB(2 3)) (Over 2 1 ) ( Above 2 3 ) (CenteredOn BB(2 3) 1) (Over3 1 ) (not Intersect 2 3 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1) Nb ! Gl Na Nb 1:6 (Contains 1 BB(2 3)) (not Intersect 2 3 ) (CenteredOn BB(2 3) 1) (Over3 1 ) (LeftOf 2 3 ) ( Over2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1)
Nb ! Gl Na 1:7 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1)

(w 0) = (w 1) (h 0) = (h 1) Nc ! Gl Na Nc 1:8 (Contains 1 BB(2 3)) (Over 2 1 ) (CenteredOn BB(2 3) 1) (Over3 1 ) (Above 2 3 ) ( not Intersect 2 3 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1) Nc ! Gl Na 1:9 (CenteredOn 2 1 ) ( Contains 1 2 ) ( Over2 1 ) (x 0) = (x 1) (y 0) = (y 1) ((z + 1 ) 0 ) = ( z 1) (w 0) = (w 1) (h 0) = (h 1)

Visual properties of the syntax

The language defined by this grammar is a superset of the sentences that can be generated from the translation of DTDs. Basically, it allows the nesting at an arbitrary level of graphical objects, including text strings, provided that objects containing other objects are of type Re (i.e rectangles). When a rectangle contains a set of objects, elements of this set can be laid out either horizontally or vertically but cannot overlap even partially, and the set is always centered with respect to the parent rectangle, whose size is defined so as to fully contain its children.

Figure 1 shows two examples of visual sentences allowed by the grammar : all objects and sets of objects are centered with respect to their parent and are fully contained 2 illustrates two sentences that do not belong to the language. The left-hand one is incorrect because shapes other than rectangles are not allowed to contain objects and because two sibling shapes partially overlap. In the right-hand one, components of the outmost rectangle are not aligned vertically or horizontally, thus making the sentence incorrect. (fNag )

Example 1 the full derivation path of the leftmost sentence in

(1:3) ;! (fGl1 R e 2 N ag j = R1 f (Contains Gl1 Re2) (CenteredOn Re2 Gl1) (CenteredOn Na Re2) (OverNa Re2) (Contains Re2 Na) (Over Re2 Gl1)g) (1:5) ;! (fGl1 R e 2 G l 3 N a N cg j = R2 f (Above Na Nc) (Contains Gl3 BB(Na N c)) (OverNa Gl3) (not Intersect Na Nc) (Over Na Gl3) (CenteredOn BB(Na N c) Gl3)g) (1:0) ;! (fGl1 R e 2 G l 3 G l 4 S h 5 N cg j = R3 f (OverSh5 Gl4) (CenteredOnSh5 Gl4) (Contains Gl4 Sh5)g) (1:8) ;! (fGl1 R e 2 G l 3 G l 4 S h 5 G l 6 N a N cg j = R4 f (Over Na Gl6) (Contains Gl6 BB(Na N c)) (OverNc Gl6) (CenteredOn BB(Na N c) Gl6) (Above Na Nc) (not Intersect Na Nc)g) (1:2) ;! (fGl1 R e 2 G l 3 G l 4 S h 5 G l 6 G l 7 S h 8 N cg j = R5 f (CenteredOn Sh8 Gl7) (Contains Gl7 Sh8) (OverSh8 Gl7)g) (1:9) ;! (fGl1 R e 2 G l 3 G l 4 S h 5 G l 6 G l 7 S h 8 Gl9 N ag j = R6 f (CenteredOn Na Gl9) (Contains Gl9 Na) (OverNa Gl ; 9)g) (1:1) ;! (fGl1 R e 2 G l 3 G l 4 S h 5 G l 6 G l 7 S h 8 Gl9 G l 10 T x 11g j = R7 f (CenteredOn Tx11 Gl10) (Contains Gl10 Tx 11) (OverTx11 Gl10)g)
2 R i represents the union of R i;1 with the set of relations specified in the previous derivation step. 3 We note S j = R the couple (S R) such that elements in S satisfy all relations in R.

Abstract syntax

We now introduce a formal abstraction which will ease the subsequent formal treatments and transformations (with underlying visual soundness). definition. We propose to capture the previous visual properties into an abstract syntax which is not purely visual but rather structural [START_REF] Erwig | Abstract syntax and semantics of visual languages[END_REF]. The tree grammar formalism [START_REF] Thatcher | Tree Automata: An Informal Survey, chapter 4[END_REF] is a natural extension of CFG grammars allowing the definition of languages as sets of trees instead of sets of strings. This formalism, while powerful in capturing tree-like structures, is also clear and simple enough to understand and supports inductive proof approaches naturally.

Definition 2 (Abstract Syntax AS) G ! Box(G s w h c) container object 2:10 G ! VA(G G d) Ver. alignment 2:11 G ! HA(G G d)
Hor. alignment 2:12 G ! Shp(f s w h c) terminal shape 2:13 G ! Txt(v) terminal text 2:14 where f is a meta-variable for various shapes such as (triangle square

), s denotes style (dashed,solid), w,h, d are positive numerical variables for width, height and spacing) and c represents color. Meta-variable v designates the text value. We note L(AS) the (tree) language generated by AS. The following property states that the visual translation produces visual sentences which belong to the language generated by the visual syntax V. Property 1 (membership of TJASK.) for all tree t belonging to L(AS), TJtK 0 belongs to L(V) We then demonstrate that 8i 1 H1 ^ Ĥi =) Hi+1. We just produce one of the 3 cases (Box):

Visual representation of DTDs

The interested reader will found the precise specification of DTDs in [START_REF] Bray | eXtensible Markup Language (XML) 1.0[END_REF]. For the clarity of our presentation, we use hereafter a simplified version which does not handle attributes even if our implementation does represent them [START_REF] Pietriga | VXT: Visual XML Transformer[END_REF].

Document Type Definitions Definition 4 (Document Type Definition) A DTD D l is a set of rules indexed by a unique name, noted

Dname i = fname1 _ N1 namen _ Nng in which the rule named name i is considered as the root. The structure N of each rule is defined through the following (abstract) syntax RH: R ! R? j R j R + j (R1 ::: Rn) j (R1j:::jRn) j # j EMPTY j ANY j name In order to simplify notations we consider DTDs as mappings, and thus for instance, the functional notation D mail (p) corresponds to (# j cite) .

Translation Semantics

informal description. We propose a recursive function which computes a visual representation of any legal DTD. Possible recursion and cross-references in rule definitions are handled thanks to contextual information. Each element is processed normally the first time it is encountered in the tree, subsequent references to this element being symbolized by a special graphical object with the element's name as a decoration but no content.

The function is defined over DTDs, sets of labels (rule names) and L(AS). Elements of are sets of labels noted = fl 1 : : : l n g, memorizing which rules l i have already been processed (to avoid endless processing of recursive rule definition and to allow the factorization of graphical object translation).

The full signature of the main function is formally defined by: VFJ:K : L(RH) DTD ! L (AS)

and the translation of a DTD D `, noted VFJD `K is recursively defined.

t1 1 = VFJR1KD ` . . . ti i = HA(t 0 i t i+1 2)
and t 0 i i = VFJRiKD ` i;1 Proof 2 We first prove that the function computes a result for every finite DTD (the difficulty is for recursive DTDs), and then we demonstrate that the result belongs to L(AS).

Note that the terms generated by VF are more specific than terms of AS. For instance, no term having the form VA(VA(G 1 G 2 ) G 3 ) is produced. We propose to capture these specific structural properties through a tree grammar DS which is a refinement of AS.

Simplification

overview. A term rewriting system [START_REF] Dershowitz | Handbook of Theoretical computer Science -Rewrite Systems[END_REF], named O, is used to simplify the visual sentences obtained after translation. It consists of a set of unordered orthogonal rewriting rules, which can for instance be applied using a depth-first, innermost-first strategy. Basically, the simplification erases graphical objects representing cardinality and transfers this information to their children by updating attributes such as the border style (solid or dashed).

Pretty-Printing

overview. The principle of the pretty-printing we propose is (i) to establish visual analogies between nodes having the same depth in the tree structure, (ii) to make explicit node types with respect to the DTD semantics (e.g sequences are blue, alternations green). The first point is addressed through a fine tuning of block sizes that avoids pathological cases (e.g too thin rectangles). Figure 6 gives an intuition of the result for the mail DTD. Note that our representation space is based on a camera metaphor, which allows the user to zoom on any part of the observed sentence ( [START_REF] Pietriga | VXT: Visual XML Transformer[END_REF][START_REF] Vion-Dury | A structured workspace for a visual configuration language[END_REF][START_REF] Vion-Dury | Virtual images: Interactive visualization of distributed object-oriented systems[END_REF]).

Definition 9 Pretty-Printing over simplified terms PJ:K : L(AS) Int Int! L (AS) Int Int PJShp(f s w h c)KW H = Shp(f s w h c) max(W w ) max(H h) PJBox(G s w h c)KW H = Box(G 0 s W 0 H 0 c) W 0 H 0 with G 0 w 0 h 0 = PJGK W=1:2 H=1:2

and H 0 = max(h 0 1:2 H ) W 0 = max(w 0 1:2 W H 0 )

Conclusion

Martin Erwig underlined the importance of visual abstract syntaxes [START_REF] Erwig | Abstract syntax and semantics of visual languages[END_REF], and remarked that few papers deal with abstract syntaxes. We add that most of them rely on simplified graph-based syntactic formalisms [START_REF] Reckers | Defining and parsing visual languages with layered graph grammars[END_REF]. In that respect, this paper shows that (i) tree-based visual abstract syntaxes can deal with a general class of visual language syntaxes through well-know proof technics, and (ii) that transformational approaches can help in finding the right abstraction level. The following diagram sums up the transformation architecture developed in this paper. The pivot abstract syntax AS and its associated translation semantics VF is quite general and can be used in other studies. We demonstrated through the simplification transformation O and a prettyprinting transformation P that the proposed approach produces realistic outputs while enabling formal treatments.

DTD T

;! L(DS) ;! L(AS) VF ;! L(V) O # L(DS) ;! L(AS) VF ;! L(V) P # L(DS) ;! L(AS) VF ;! L(V)

This work could be extended by proposing visual soundness properties, establishing relations between structural properties of DTDs and their effective perception by observers of the visual translation. For instance, showing that all element names of a DTD are visible, and that the parent-child relationship is actually translated by a nesting relation. Another soundness property could rely on operational view of DTDs, showing that if a (document) tree conforms to a DTD, its visual translation (to be defined through the pivot syntax AS) conforms in some sense to the visual translation of its DTD. This should reveal that this essential property is captured by the visual language.

  is a set of graphical terminal symbols of type Sh, Re or T x , disjoint from N. S is the start symbol in N : S = N a . R is the set of relation symbols defined above : R = fContains CenteredOn Above LeftOf Intersectg.

  text

Figure 1 .Figure 2 .

 12 Figure 1. Examples of correct visual sentences

Figure

Figure 1 2 3

 3 .

Example 2 (Example 3 ( 4

 234 an element of L(AS)) (captures the structure of the leftmost sentence in Fig. 1) s2 w2 h2 c2 ) VA(Txt(v4) Shp(f5 s5 w5 h5 c5) d3) d1) s0 w0 h0 c0) We now demonstrate the membership of the previous tree by providing a full derivation path in AS. The derivation path of Example 2) the previous tree belongs to L(AS), as shown by the following derivation path The visual semantics of this abstract syntax is defined by a translation function which produces as output a set of indexed visual objects compatible with the representation model introduced in section 2. The function accepts items of L(AS), and returns a set of indexed graphical objects ;. It computes the value of visual attributes associated to each object through an ordered sequence of a basic linear algebra instruction set. Elements of ; are indexed sets of graphical objects noted = fO 1 O n g where the meta-variable O ranges over the syntactic categories fGl Re T xg. The function also propagates a numerical index i which corresponds to the depth of the current node in the source tree. We use the notation G k :attr := ] for the set computed from by applying the operation O k :attr := on every element O k of . For instance, if = fRe 1 R e 2 g then O k :x := O k :x + 10] will compute a new set 0 = fRe 2 R e 3 g where all x coordinates are shifted by 10. We consider also O k :attr := O k :attr := ] as a shorthand for ( O k :attr := ]) O k :attr := ]. Finally, BB( ) denotes the bounding box obtained from all objects in . Definition 3 (T, Visual translation of L(AS)) TJ K : L(AS) N ! ; TJTxt(v)Ki = fTx i G l ig 3:15 such that 2 Tx i:z = i Tx i:x = 0 Tx i:y = 0 Tx i:value = v Gli = BB(Tx i T x i) TJShp(f s w h c)Ki = fShi G l = 0 Shi:y = 0 Shi:w = w Shi:h = h Shi:shape = f Shi:border = s Shi:z = i Shi:color = c Shi:value = v and Gli = BB(Shi S h i) TJBox(G1 s w h c)Ki = 1 f Rei G l = B1:x Rei:y = B1:y Rei:w = max(w B 1:w + 2) Rei:h = max(h B 1 :h + 2) Rei:border = s Rei:color = c Rei:z = i Gli = BB(Rei R e i) TJHA(G1 G 2 d)Ki = 1 :y := B1:y Gk:x := B1:w + B2:w + d] TJVA(G1 G 2 d)Ki = 1 :x := B1:x Gk:x := B1:h + B2:h + d]

Proof 1 (

 1 by induction on the length of derivation paths) Sketch: the induction hypothesis H i 1 is for all derivation G i ! t there exist j 1 N1 j = j ! j = R and a mapping : ! TJtK0 such that TJtK0 j = R where R denotes the transposition of relations in R through

  0 n t 0 n n = VFJRnKD ` n;1 VFJ(R1j j Rn)KD ` = VA(t t2 2VFJ(R2j j Rn)KD ` 1 VFJ(R)KD ` = VFJRKD ` 6:25 VFJR?KD ` = HA(t Shp(rectangle dashed 10 10 white) 2) 1 with t = Box(t1 solid 10 10 white) 6:26 and t1 1 = VFJRKD ` VFJR KD ` = HA(t Shp(rectangle dashed 10 10 c) 2) 1 with t = Box(t1 dashed 10 10 white) 6:27 and t1 1 = VFJRKD ` VFJR + KD ` = HA(t Shp(rectangle dashed 10 10 white) 2) 1 with t = Box(t1 solid 10 10 white) with t1 = Shp(rectangle solid 10 10 grey) and t2 = Box(t solid 10 10 white) and t 1 = VFJD`(name)K D ` fnameg Property 2 8d m 2 DTD VFJd m K 2 L (AS)

Proof 3 Example 4 (

 34 Figure 3 for VF(D mail ) and Figure 4 for TJVF(D mail )K.

Definition 8 Figure 3 .Figure 4 .Property 5 (Proof 5 Example 5 Figure 5 .

 8345555 Figure 3. the translation VF(D mail ) (simplified leaves, with d = dashed)

Figure 6 .

 6 Figure 6. The final pretty-printed mail DTD

  where r is a name for the relation, i and j being objects of type Gl or one of its subtypes :

	which returns the smallest rectangle bounding two objects :
	BB : Gl Gl ! Re
	and which is defined as follows :
	BB(A1 A 2) = R R:x = ( minX + maxX)=2 R:y = ( minY + maxY )=2 R:w = maxX ; minX R:h = maxY ; minY where maxX = max(A1:x + A1:w=2 A 2:x + A2:w=2) with maxY = max(A1:y + A1:h=2 A 2:y + A2:h=2) minX = min(A1:x ; A1:w=2 A 2:x ; A2:w=2) minY = min(A1:y ; A1:h=2 A 2:y ; A2:h=2)
	spatial relations. Using this relation, we introduce the
	following relational constraints, all defined by a 3-tuple (r i j ) Relation Arg. types Definition

bounding box function. We then define function BB,

PJVA(Box(G1 s1 w1 h1 c1) Box(G2 s2 w2 h2 c2 ) d)KW H = VA(G 00 1 G 0 2 0) w h with G 0 1 w 0 1 h 0 1 = PJBox(G1 s1 w1 h1 c1 )KW H and G 0 2 w 0 2 h 0 2 = PJBox(G2 s2 w2 h2 c2)K w 0

The pretty-printing of all term in L(DS) is a term in L(DS)

Proof 6 By induction on derivation paths D i ! t implementation. The representation obtained thanks to the pretty-printing function is not completely satisfactory. The layout algorithm implemented in VXT [START_REF] Pietriga | VXT: Visual XML Transformer[END_REF] is based on another function, too complex to be formally described in this paper. This function further enhances the user's perception of the structure, by assigning the same height to all nodes at the same absolute depth in the DTD tree, without taking into account the choice and sequence nodes, considered as constructors rather than true nodes of the DTD. Choice and sequence nodes are simply assigned a width and a height slightly bigger than their content. The result of this enhanced pretty-printing function is illustrated in Figure 6.

Related works

The representation of tree structures as nested graphical elements has been explored by Schneiderman with treemaps [START_REF] Johnson | Treemaps: a space-filling approach to the visualization of hierarchical information structures[END_REF], which represents all nodes as rectangles, the children being nested inside their parent. Treemaps have been used to visualize large hierarchies, such as file systems and other complex tree structures.

Several visual representations of DTDs have been proposed, both in industrial products and research prototypes, but none of these proposals seems to have been specified or studied using formal methods. Near and Far [START_REF] Opentext | Near & far designer[END_REF], an XML modeling and authoring tool, represents DTDs graphically as an editable node-link diagram. Elements, text nodes and cardinality information are all mapped to different graphical nodes, while sequence and choice are respectively mapped to straight and curved edges, making the structure representation complex and hard to understand, especially when sequences or choices directly contain other sequences and choices. Furthermore, the tree-layout method, combined with very basic navigation and zooming capabilities, makes in our opinion this representation less intuitive and less scalable than the one proposed here. XML-GL [START_REF] Ceri | XML-GL: a graphical language for querying and restructuring XML documents[END_REF], a visual language for querying and restructuring XML data, proposes another visual representation


Sylvie Picol
email: sylvie.picol@ens.insa-rennes.fr

Gheorghe Zaharia

Dominique Houzet

Ghaïs El

DESIGN OF THE DIGITAL BLOCK OF A HARDWARE SIMULATOR FOR MIMO RADIO CHANNELS

The aim of the regional research project SIMPAA2, which continues the former national research SIMPAA project, is the realization of a hardware simulator of MIMO propagation channels for UMTS and WLAN applications. The simulator must reproduce the behavior of the radio propagation channel, thus making it possible to test "on table" the mobile radio equipments. The advantages are: low cost, short test duration, possibility to ensure the same test conditions in order to compare the performance of various equipments.

I. INTRODUCTION

During last years, the development of wireless technologies offers many prospects and new applications. This trend will be accentuated in the future, the systems still having to improve their data rate and mobility. UMTS (Universal Mobile Telecommunications System) and WLAN (Wireless Local Area Networks) constitute the mobile and wireless telecommunications systems of third generation and beyond able to offer to general public the high-rate multi-media services. MIMO (Multiple-Input Multiple-Output) systems make use of antenna arrays at both the transmit and the receive sides of a radio link to drastically improve the capacity over more traditional systems.

However, the transmitted electromagnetic waves interact with the propagation environment (indoor/outdoor). It is thus necessary to take into account the main propagation parameters during the design of the future communication systems. The optimal choice of the modulation, coding, etc. for these communication systems is based on a reliable model of the radio propagation channel. Moreover, after the realization of a communication system, its experimental performance can be evaluated by using a hardware radio channel simulator. A hardware simulator can also be used to compare the performance of various radio communication systems in a time-variant propagation channel in the same test conditions.

On the market, there are some hardware channel simulators (Propsim, Smart System, Spirent), but they are very expensive and therefore prohibitive for a communication laboratory.

This paper presents the design of the digital block of a hardware simulator for indoor/outdoor MIMO radio channels. Section 2 of the paper deals with the architecture of the digital block of the hardware simulator. This section is divided into three parts: RF blocks, Channel model block and Digital block describing their respective architecture and several parameters useful to design the hardware simulator. Lastly, Section 3 shows the beginning of the realization of the hardware digital block. The prototyping platform is described and simulations carried out give first results. The trade-off between results accuracy, complexity and cost represents an important choice during the design of the digital block of the hardware simulator.

II. HARDWARE SIMULATOR: PRINCIPLE, ARCHITECTURE AND OPERATION

The simulator must reproduce the behavior of a MIMO propagation channel for a specific environment, indoor or outdoor. This makes it possible to check the correct operation of the new radio communication systems and to compare their performances under the same test conditions.

The simulator must operate with RF signals (2 GHz for UMTS and 5 GHz for WLAN). In order to make adjacent channels interference tests for UMTS systems, it is useful to consider three successive channels, thus to have a 3x5 MHz bandwidth. Therefore, the frequency bandwidths B are 15 MHz for UMTS and 20 MHz for WLAN.

Moreover, UMTS uses two operating modes: the TDD mode (Time Division Duplex) having the same frequency band for both uplink and downlink and the FDD mode (Frequency Division Duplex) having different frequency bands. In addition, depending on the strength of the transmitted signals, the simulator must be able to accept input signals with wide power range, between -50 and 33 dBm, which implies a power control for the simulator inputs.

The design and realization of the RF block for UMTS systems were completed in the previous SIMPAA (SImulateur Matériel de Propagation pour Antennes Adaptatives) project [1]. The RF block will need some modifications required by WLAN specifications. The objectives of the actual regional project SIMPAA2 mainly concern the channel model block and the digital block of the MIMO simulator, as shown in Fig. 1 by the gray blocks.

A. RF Blocks

The number of radio frequency blocks is determined by the number of the transmitting and receiving antennas. For a transmitter with N T antennas and a receiver using N R antennas, the MIMO simulator must have N T N R fullduplex SISO channels, thus 2 N T N R one-way SISO channels. The actual choice of 18 one-way SISO channels seems to be a suitable trade-off between utility, complexity and cost, assuming 2 ≤ N T , 2 ≤ N R and N T + N R ≤ 6.

As shown in Fig. 2, for RF receiver and transmitter, the "Attenuator" and "Amplifier" blocks are controlled respectively via "Control bus" and "Gain control bus" in order to adjust the reception and transmission power by the automatic gain control (AGC). In the reception RF unit, local oscillators LO TDD or LO FDD allow the RF to IF 1 conversion by taking into account the TDD and FDD modes which use different frequency bandwidths. Then, the third local oscillator LO 1 allows the IF 1 to IF 2 conversion. The IF 2 band-pass filter must perform a good rejection of the out-of-band frequencies to avoid aliasing problems. The local oscillator LO 2 and the low-pass filter (LPF) give a lowfrequency real signal (its Fourier transform keeps the hermitian symmetry). After the digital block, the transmission RF unit converts, with the equivalent steps, the low-pass version of the y j (t,τ) signal into a RF signal.

Moreover, when the impulse response or frequency response of the propagation channel presents fadings, their samples must be "amplified" before A/D conversion, in order to obtain a convenient utilisation of the full-scale. This allows a reduction of the computing errors of the digital blocks. Thus, the final RF amplifier restores the correct level of the signal y j (t,τ) received by the j th Rx antenna by taking into account the attenuation introduced by AGC block and the amplification of the impulse or frequency response of the channel.

Fig. 3 shows the realization of the RF reception (high part) and transmission (low part) units, as well as the connection unit (left part) which allows the link between antenna and the RF reception and transmission units. This RF block was realized in printed technology during the previous SIMPAA project.

B. Channel Model Block

A MIMO channel is composed of several randomly timevariant correlated SISO channels. Fig. 4 illustrates a MIMO channel with N T = 2 transmit antennas and N R = 2 receive antennas. For this MIMO channel, the signal y j (t,τ) received by the j th receive antenna can by easily obtained:

y j (t,τ) = x 1 (t,τ) * h 1j (t,τ) + x 2 (t,τ) * h 2j (t,τ), j = 1,2 (1)
For a hardware implementation, it is easier to use the Fourier transform to replace the convolution by an algebraic product:

Y j (t,f) = X 1 (t,f).H 1j (t,f) + X 2 (t,f).H 2j (t,f), j = 1,2 (2)
As it was shown in [START_REF] Picol | Further Steps Towards the Development of a Hardware Simulator for MIMO Radio Channels[END_REF], this solution is possible to implement but its disadvantage is the generated latency. For indoor environments, we will consider the first relation because a FIR (Finite Impulse Response) filter has, in spite of its relative complexity, a much lower latency. For outdoor environments, the effective duration W t of the impulse response of the channel is wider. Therefore, in order to reduce the complexity and the cost of the digital block, the second relation is used. Therefore, both approaches can be used according to the considered propagation environment.

The channel models used by the simulator will be obtained from measurements by using a time domain MIMO channel sounder designed and realized at the IETR [START_REF] Cosquer | Conception d'un sondeur de canal MIMO -Caractérisation du canal de propagation d'un point de vue directionnel et doublement directionnel[END_REF], as shown in Fig. 5. This MIMO channel sounder is based on the correlation technique [START_REF] Rappaport | Wireless Communications Principles & Practice[END_REF]. For each SISO channel, the sounder gives the measured complex envelope of its impulse response. During the measurement of all SISO channels, the MIMO channel must be practically invariant. This limits the mobile speed and therefore the maximal value of the Doppler shift. A simple way to use these measurement results is to compute, for each location of the mobile transmitter, the frequency responses H i,j (t,f) as Fourier transforms of the impulse responses h i,j (t,τ) of the MIMO propagation channel. These frequency responses can be used to supply the "Channel model" block of each SISO channel, as shown in Fig. 1. Periodically, the frequency responses must be actualized, in order to simulate the channel timeevolution. The "refreshing" period of the frequency responses is determined by the channel coherence time, thus by the mobile speed and the propagation environment. As the number of the recorded files is finite, it will be necessary to periodically replay the whole set of frequency responses.

C. Digital Block

For outdoor environments, the impulse responses are longer, thus more points are necessary to describe them. Moreover, the impulse responses are more often refreshed, thus the number of profiles to be stored and treated is more significant. Thus, computations are carried out in the frequency domain because FFT modules need less resources than FIR filters. On the other hand, for indoor environments, the FFT modules would generate too much latency, therefore it is more judicious to use FIR filters.

In order to have a suitable trade-off between complexity and latency, two solutions are necessary: a time domain approach with FIR filters for the indoor environment and a frequency domain approach with FFT modules for the outdoor environment.

The FIR filter carries out convolutions. Several multipliers are used, their number depends on the length of the channel impulse response. The frequency domain approach uses only one multiplication but needs, for each SISO channel, one FFT module and one IFT module, which increases the latency of the digital block. For an outdoor environment, the digital block operates in the frequency domain. The Fourier transform of the input signal, obtained at the output of the FFT block, is multiplied by the channel frequency response H i,j (t,f), which includes the correction of errors introduced by the filters of the reception unit. Then, the sum must be realized N R times, to add each SISO Y i,j (t,f) signal coming from each simulator input. This signal is truncated depending on the number of data bits of the D/A converter. Finally, from the resulting MIMO signal Y j (t,f) representing the sum of the SISO Y i,j (t,f) signals, the IFT block gives the low-frequency output signal y j (t,τ) which represents the input of the transmission RF unit.

For an indoor environment, the digital block operates in the time domain. The FIR filter block computes the convolution product between the sampled input signal and the channel impulse response h i,j (t,τ). As for the frequency domain, the sum must be realized N R times to add the SISO y i,j (t,τ) signals coming from each simulator input. Then, each sum must be truncated according to the number of data bits of the D/A converter.

By using the Shannon theorem and the expected performances of the RF/IF filters, the sampling frequency f s is 40 MHz for UMTS systems and 50 MHz for WLAN systems. This choice allows a reasonable low sampling rate and avoids the aliasing problems.

According to the considered propagation environments, Table 1 summarizes some useful parameters. For these various environments, the size of the FFT blocks is estimated by:

N = = W t f s T s W t (3)
where W t represents the width of the effective time window of the impulse response of the propagation channel, i.e. the width of the time-interval where the impulse response can be considered not null. The final value N is the closest 2 n value (for FFT only). The resulting W t is also given in Table 1.

If the latency of the "Digital block" is lower than the absolute delay of the first path τ 0 , no error will occur.

III. IMPLEMENTATION

In order to implement the hardware simulator, several solutions of prototyping platforms were studied. The adopted solution uses a prototyping platform based on 3 development boards (XtremeDSP Development Kit-IV for Virtex-4) from Xilinx [6], shown in Fig. 8.

A. Description

The XtremeDSP Development Kit provides a complete platform for high-performance signal processing applications. This kit features dual-channel highperformance ADCs (AD6645) and DACs (AD9772A) with 14-bit resolution, a user programmable Virtex-4 FPGA, support for external clock, programmable clocks, two banks of ZBT-SRAM, host interfacing via PCI or USB, and JTAG interfaces.

This development kit is built with a module containing the Virtex-4 SX35 component selected to correspond to the complexity constraints. It contains a number of arithmetic blocks (DSP blocks) which makes it possible to implement many functions occupying most of the component.

In addition, the digital block must operate with relatively high frequencies, in order to share the limited resources on several clock cycles.

This device enables us to implement not only the FIR filter for the time domain but also the FFT module for the frequency domain and thus to reprogram the component according to the selected (indoor or outdoor) environment.

B. Implementation and results

According to Table 1, the worst case for indoor environments uses a FIR filter with a length of 64. So, for the time domain, we have developed our own FIR filter with a length of 64, instead of using Xilinx MAC FIR filter because this filter does not make it possible to reload the FIR filter coefficients. According to the resolution of the A/D and D/A converters, our own filter has a 14 bits resolution for input and output data. It has also a 16 bits resolution for the coefficients of the impulse response of the channel. The coefficients have a power of two resolution to optimize the memory size. In addition, each intermediate product of the FIR is truncated on 20 bits.

Before each FIR operation, the 64 coefficients of each FIR are stored first in 14 shift registers of length 64 via USB ports of each board. Then, they are stored in the FPGA dual-port RAM. So, it is possible to prepare the loading of the next coefficients in the register. Those coefficients are read at 100 MHz and the input data at 50 MHz. Thus, the same FIR multipliers are used during two cycles. A binary arborescent structure of adders makes it possible to build a 4-stages pipeline.

Several simulations and synthesis was made with Xilinx ISE and Modelsim software. The FIR filter block has 4 stages, so 4 clock cycles (2 cycles of 32 multiplications and 2 addition cycles). Then, an addition cycle is necessary to add the results of each FIR. Thus, we have 5 cycles at 100 MHz, therefore 50 ns of latency for the FIR. It is necessary to add approximately 38 ns of the ADC latency, and 17 ns of the DAC latency, according to their respective datasheet.

The FFT block latency is measured between the time when the data enter in the FFT block and the time when the result is provided, which is roughly a latency of 5 µs.

Moreover, for a MIMO configuration, we have to use several boards connected together with point-to-point links. Thus, synchronization differences between boards also add a latency of several ns. So, it is necessary to add one clock cycle for communication between boards for both frequency and time domains.

In summary, the digital block and the converters have a latency of 5 µs for the frequency domain and 115 ns for the time domain.

IV. CONCLUSION SIMPAA2 project has two main objectives. The first objective concerns the design and the realization of the digital block of the hardware simulator by using a prototyping platform containing programmable circuits.

The second objective concerns the reliable MIMO channel models which must supply the digital block.

After a comparative study, in order to reduce the complexity and the latency of the digital block, the output signal of the MIMO simulator will be computed in the frequency domain for outdoor environments and in time domain for indoor environments. This work will be continued to complete the design of the architecture of the hardware simulator by minimization of the latency of the digital block and maximization of its precision.

Nowadays, we work with a configuration which requires 3 XtremeDSP Development Kit-IV but we are studying a 200 MHz optimized FIR filter solution allowing to reduce the latency from 115 ns to 90 ns. Synchronization effects on latency will be precisely measured with these three boards.

More measurement campaigns will be carried out with the MIMO channel sounder, realized by IETR, for various types of environments (indoor, outdoor, penetration) and for both UMTS and WLAN frequency bands. The final objective of these measurements is to obtain realistic and reliable impulse responses of the MIMO channel in order to supply the digital block of the hardware simulator.

Lastly, the digital block of the MIMO hardware simulator will be implemented as an electronic module. A Graphical User Interface (GUI) will be also developed to allow the user to configure the channel parameters: environment type, channel model, time window, mobile speed, etc.

Fig. 1 .

 1 Fig. 1. Block diagram of a one-way SISO channel.

Fig. 2 .

 2 Fig. 2. Reception and transmission RF unitsfor a one-way SISO channel.

Fig. 3 .

 3 Fig. 3. UMTS receiver and transmitter of a SISO RF block.

Fig. 4 .

 4 Fig. 4. MIMO channel (2 x 2 SISO channels).

Fig. 5 .

 5 Fig. 5. MIMO channel sounder.

Fig. 6

 6 Fig.6shows the Uniform Linear Array (ULA) used for outdoor measurements with 4 active elements[START_REF] Zein | Characterization and Modeling of the MIMO Propagation Channel: An Overview[END_REF].

Fig. 6 .

 6 Fig. 6. ULA Tx Antenna.

Fig. 7 Fig. 7 .

 77 Fig. 7. Digital block.

Fig. 8 .

 8 Fig. 8. XtremeDSP Development Kit-IV for Virtex-4.

Table 1 .

 1 Simulator parameters.

		Type	Cell Size	Wt eff(µs)	N	Wt(µs)
	UMTS	Rural	2-20 km	20	512	12.8
	(B = 15 MHz)	Urban	0.4-2 km	3.7	128	3.2
	(fs = 40 MHz)	Indoor	20-400 m	0.7	28	0.7
	WLAN	Office	40 m	0.39	20	0.4
	(B = 20 MHz)	Indoor	50-150 m	0.73	37	0.74
	(fs = 50 MHz)	Outdoor	50-150 m	1.16	64	1.28

Table 2 .

 2 Table 2 shows the device utilization for 4 FIR 64 in one V4-SX35 after synthesis, mapping and place & route. For example, 128 DSPs are used and DSPs occupy 66 % of available DSPs. Virtex-4 SX35 utilization for 4 FIR 64: For the frequency domain, the Fourier transform is realized with the FFT module from Xilinx. As the development kit has 2 ADC and 2 DAC, it can be connected to only 2 antennas, so we have to use 2 FFT and 2 IFT per FPGA. The V4-SX35 utilization summary is given in the Table 3 for one FFT with a length of 512, which is the worst case for outdoor environments according to Table 1.

	Number of Slices	10015 out of 15360	65%
	Number of logic LUTs 7586 out of 30,720	24%
	Number of RAM LUTs 4096 out of 30,720	14%
	Number of Flip Flops	9,680 out of 30,720	31%
	Number of DSP48s	128 out of 192	66%
	Clock period	9,92 ns

Table 3 .

 3 Virtex-4 SX35 utilization for 1 FFT 512:

	Number of Slices	2,638 out of 15,360 17%
	Number of logic LUTs	2,716 out of 30,720 8%
	Number of RAM LUTs	1,132 out of 30,720	3%
	Number of Flip Flops	3,253 out of 30,720 10%
	Number of DSP48s	16 out of 192	8%
	Clock period	6,8 ns
	To determine the digital block latency, the used FIR
	filter and FFT block latency are measured.

ACKNOWLEDGMENTS

The authors would like to thank the "Conseil régional de Bretagne" for its financial support of the SIMPAA2 project. Also, they would like to thank José Manuel Aguilar Bruno and Antonio Hernández Hernández from Escuela Técnica Superior de Ingeniería de Telecomunicación de Cartagena (Spain) for their helpful assistance.


Jeremy Seyssaud

Julien Favrichon

Kevin Giraud-Esclasse

Philippe Girones

Najib Mahjoubi

Sven Bock

Philippe Capdepuy

Cyril Moitrier

An humanoid robot for inspections and cleaning tasks in nuclear glove box

An humanoid robot for inspections and cleaning tasks in nuclear glove box

Jeremy SEYSSAUD 1 , Julien FAVRICHON 1 , Kevin GIRAUD-ESCLASSE 1 , Philippe GIRONES 1 , Najib MAHJOUBI 1 Sven BOCK 2 , Philippe CAPDEPUY 2 and Cyril MOITRIER 1 .

Abstract-This article presents an opportunity evaluation of the use of humanoid robots in a nuclear environment. The project worked on the DaRwIn-OP platform to assess and carry out the modifications the robot needed to enable it to perform as an intervention operator in a nuclear location. The study had two main lines, based on equipping the humanoid with a radiological measurement capture system and with an arm command system using a depth camera. The tests performed showed the robot's ability to make radiological measurements with the built in detector and to collect swipe samples to assess the contamination of an object.

I. INTRODUCTION

This article describes the results of work intended to prepare a humanoid robot for work in a nuclear environment where the irradiation and contamination mean human intervention must be severely limited. The use of anthropomorphic robotics arises from the theory that a biped humanoid with gripping hands has the ability to replace humans for work in an extreme or hostile environment. Such a robot's means of movement should offer the advantage of being well-adapted to surfaces inaccessible by more classic robot locomotion systems based on wheels or tracks [START_REF] Bruzzone | Review article : locomotion systems for ground mobile robots in unstructured environments[END_REF]. Its humanlike ability to grip and handle objects with its hands appears to represent a real opportunity, as does the control of this sort of robot by having it imitate the movements of an operator located outside the hazardous zone [START_REF] Do | Imitation of human motion on a humanoid robot using non-linear optimization[END_REF]. Given these factors, work was undertaken on a humanoid platform in order to evaluate the opportunity of making it into a robotized assistance operator for nuclear environment investigations. This project followed up on analyses of the possibilities offered by a link between the D&D industry and the opensource robotic community [START_REF] Seyssaud | Robotic d&d : Smart robots-15093[END_REF]. The humanoid robot was called H@RI, a French acronym for Robotized Assistance Humanoid for Investigation. This article first describes the pre-existing technological bricks used in the trials, i.e. the DaRwIn-Op [START_REF] Ha | Development of open humanoid platform DARwIn-OP[END_REF] humanoid robot and the radiological detector used (II). Next, the work carried out on the platform software part, the integration of a nuclearized instrumentation and the robot control are explained (Section III). Finally, different tests are presented concerning the irradiation of the on-board electronics, the on-board radiological detector validation and the remotely-handled control capacity for taking a swipe sample (Section IV).

II. THE EXISTING EQUIPMENT

A robot can be considered as a match between hardware and middleware systems, on which a set of tools and detectors has been installed. This view is the basis of the following presentation of the platform used, and of the tools added on. In this section, the humanoid robot platform (Section II-A) the software system structuring all the developments carried out (Section II-B) and then the radiological detector which was built onto the humanoid (Section II-C) are described. The H@RI robot's tools made it a suitable intervention operator for hostile environments, able to take measurements which provide further useful data in the radiological characterization of a nuclear environment.

A. Hardware

On order to avoid the cost of designing a completely new humanoid robot, it was decided to use an existing platform. The well-known DARwIn-OP (Dynamic Anthropomorphic Robot with Intelligence -Open Platform) marketed by ROBOTIS [START_REF]Robotis[END_REF] was chosen. This robot is 45.5 cm tall and weighs 2.8 kg. Its size and weight features mean that each of the joints is controlled by a single servomotor. The MX-28 servomotors were developed specifically for this robot in order to have the best possible resolution and communication speed compared to RX-28 type servomotors, in particular by using PID type control methods [START_REF] Ha | Development of open humanoid platform darwin-op[END_REF]. The DARwIn-OP robot is available off the shelf with an Intel Atom Z530 @ 1.6 GHz main controller with 1 GB RAM and 4 GB of memory. Communication is via HDMI, USB, flash memory, Ethernet or even Wi-fi type external ports. The robot is powered by lithium batteries.

B. Firmware

The platform is delivered with a Linux Ubuntu 9.10 operating system. The open-DARwIn-SDK framework, in C++ programming language, was specifically created for this platform. The development team wished to make it a modular architecture [START_REF]Framework[END_REF] grouping all the necessary functions : communication, walking, vision, etc. The framework was modified to avoid the developments carried out during this project being not just for this particular robot, as will be discussed in Section III-A.

C. Tools

H@RI had to be able to contribute to characterizing the radiological state of its operation zones. Among the different possible analysis techniques, it was decided to retain gamma spectrometry, as it enables the identification and quantification of gamma emitting radionuclides. H@RI was equipped with a gamma spectrometry detector whose hardware and software had to be built in. The small size of the humanoid platform meant a small-scale, lightweight gamma spectrometry line had to be used. These precautions are important to enable easy integration onto the robot's structure without disturbing its dynamic model. The GR1 detector, marketed by KROMEK, with dimensions of 62 × 25 × 25 mm and weighing 60 g, was installed. It uses a CdZnTe (Cadmium Zinc Telluride) detector which is sensitive to γ radioactivity ranging from 30 keV to 3 MeV [START_REF] Goaller | In-situ nuclear measurement for decommissioning : Recent trends and needs[END_REF], and can be used at normal room temperature. The set-up of the device on the robot is explained in Section III-B.

III. DEVELOPMENTS CARRIED OUT

This section describes the work carried out on H@RI to make it into a robot-operator able to intervene in a nuclear environment. Firstly, the motherboard and the operating system were modified in order to manage all the developments which were to be made to the robot (Section III-A). Next, the gamma spectrometry detector set-up is briefly explained (Section III-B). Control of the platform was organized in three ways : H@RI's walking is controlled via a video game joystick (Section III-C.1) whereas its arms reproduce the movements of a remote-handling operator who uses a deep field camera (Section III-C.3), and the grips at the end of the robot's arms are commanded via an instrumented glove (Figure 1).

A. OS, hardware et middleware

The original motherboard's memory limited the amount of data which could be stored on it. One of the first jobs was to replace it with a Odroid XU3, a central processing unit Samsung Exynos5422 with 2 GB of RAM. The memory Fig. 2: GR1 detector attached to H@RI's head can be adjusted with 16, 32 or 64 GB sizes. Maintenance of the Ubuntu 9.10 version of the operating system stopped in April 2011. This limits the possibility of software updates and therefore motivated the move to a Lubuntu 14.04 type Linux version, for which maintenance is planned to continue through to April 2019. Moreover, its light operating environment is well-adapted to this project, particularly as concerns the energy consumption and a RAM mobilization lower than the classic Ubuntu version. The framework offered with the DARwIn-OP robot is specifically linked to this humanoid platform, making it difficult to transpose developments between different platforms. Today there are a large number of proprietary or open-source middleware, for example ROS, MOOS, OROCOS, etc. The Robot Operating System middleware (ROS), based on an open-source sharing mode, is currently widely used in the robotics field, and enables external developers' contributions to be shared [START_REF] Woodall | ROS Topics : Capabilities[END_REF]. ROS can be viewed as a set of interconnected programs or nodes, making up a robot operating system. It also offers a standard communication between the different programs and associated programming languages. Deciding on this middleware for our project thus made fast, flexible integration of developments possible on different platforms [START_REF] Quigley | ROS : an open-source Robot Operating System[END_REF]. During the change of the open-DARwIn-SDK framework to ROS, it was necessary to create ROS kinematics control nodes for H@RI. Instead of creating the node from the open-DARwIn-SDK framework, an equivalent node developed by the Institut de Robòtica i Informàtica Industrials (Barcelona University), was able to be used [START_REF]Institut de robòtica i informàtica industrial[END_REF].

B. Nuclear instrumentation

H@RI had to be able to carry out gamma spectrometry measurements in order to determine the radionuclides present during operations in a nuclear environment. Given that the robot is only « baby-size », the dimensions of the detectors used had to be in proportion. It was decided to attach the detector onto H@RI's head to avoid any disturbance of the robot's overall kinematics, like its walking or arm movements. The GR1 detector was held on the humanoid's head by a support created via a 3D printing technique (Figure 2). Section IV-B gives an example of acquisition using this detector.

C. H@RI robot control

Remotely-handled control of H@Ri takes place in two steps, either through piloting the robot's legs to position the humanoid (Section III-C.1), or by piloting its arms (Section III-C.3) and grippers to carry out a task (Section III-C.1).

1) Walking control: A video game controller is used for this. It has two joysticks, one controlling forward and backward movement, and the other the robot's rotation on the spot. The control device is also used to switch between control of the legs and of the arms. Though walking could also be controlled via a computer keyboard, the game controller approach was preferred here, given that the operator must be facing the deep field camera used to control the arms (Section III-C.3).

2) Arm control: A motion capture method using an ASUS depth camera was suggested as the means to control the humanoid's arms. The objective was to be able to handle H@RI remotely, without having to set up an operator with instruments. In this case, the operator's movements are the equivalent of a man-machine interface. This contact-free piloting method is an intuitive way for an operator to control H@RI's arms.

3) Gripper control: Controlling the robot's arm by deep field camera makes the simultaneous use of a joystick impossible. This is why H@ri's grippers are piloted via instrumented gloves. The gloves enable an intuitive control of gripper opening and closing, proportional to the curve of the operator's fingers.

IV. TESTS

This section illustrates the different tests carried out with the H@RI robot in its condition as delivered by ROBOTIS. Section IV-A describes the irradiation tests performed on the robot's sensitive components. Next, the validation tests for the GR1 detector setup using calibration radioactive sources are presented (Section IV-B). Lastly, tests were made to validate the use of a depth camera to remotely control H@RI's arms (Section IV-C).

A. Tests in irradiator

A key point which had to be checked regarding the use of a robot in a radioactive environment is the on-board electronic components' resistance to ionizing irradiation. Because of the damage which can be caused by irradiation, it is necessary to estimate the maximum admissible dose for these electronic components. Knowing this maximum value is important in order to be able to estimate the reliability and the performances to be expected from the system in irradiating environments. The ionizing γ radiation emitted by radioactive elements is the subject of special attention. In this particular situation, penetrating-type radiation cannot be stopped by heavy, bulky shielding. This meant the consequences of the interaction of this irradiation on the electronic components had to be evaluated. This impact can be assessed by measuring the total absorbed dose, representing the energy deposited in the material. This total absorbed dose represents the effect of the irradiation, the most important property for robotic systems working in irradiating environments. The hardening of electronic components depends on the technologies used, the manufacturing process or the complexity of the electronic board's sub-systems. A distinction can be made between components specially hardened during their manufacturing and off the shelf components (non-hardened). Nevertheless, the irradiation resistance capability properties of certain commercial components equivalent to especially hardened components could be noted. To our knowledge, there were no data concerning the DARwIn-OP robot's electronics behavior under γ irradiation. It was therefore decided to carry out tests in a Cobalt-60 irradiator in order to forecast this behavior and estimate the vulnerability of the on-board electronics. In this type of test, the energy deposit simulation is done in a panoramic irradiator equipped with a Cobalt-60 source. The position within the bunker enabling the desired dose rate to be reached was evaluated by simulation with the RayXpert software (Figure 3). The H@RI robot's electronics components tested were :

• PC2i adaptor,

• CM-730 controller,

• Interface board,

• Power supply board,

• Head board. As well as these electronic components, the on-board detectors also have to function well. For the H@RI robot, the consequences of γ radiation were analyzed on the following items :

• Loudspeaker,

• HD 2MPx camera,

• Two ventilators,

• Accelerometer,

• Gyroscope,

• MX-28T servomotor. The MX-28T servomotors are used as actuators and have a digital memory whose functioning under irradiation had to be checked. The behavior of metallic or insulating materials was not considered in this case, as the energies under which alterations to their properties have been observed are in the several thousand Gray dose range. The component irradiation was carried out in order to simulate a total accumulated dose Fig. I. The components were polarized during their irradiation, in a similar way to their normal use in the humanoid platform. A methodology was then implemented to test different functions of the H@RI robot PC2i adaptor, such as the USB port, the video output, disk writing, the Ethernet port, and the Wifi. The tests were repeated at each irradiation level, as shown on Table I, until a failure was observed. When a failure was detected on one of the components, it was replaced in order to continue the irradiation of the other components. A test procedure was implemented to evaluate the condition of the components at each irradiation level. These tests were :

1) Camera : A photo was taken within the bunker in light, and a second photo after positioning an opaque screen in front of the lens. 2) Ventilators : These were started up to be able to visually check their functioning. 3) Microphone, loudspeaker, USB, disk writing, network access (Ethernet, Wifi) : Ubuntu operating system test procedures were launched to check that each sub-system was functioning correctly. 4) Accelerometer and gyroscope : A writing procedure for the data sent by the detectors was launched. The test involved checking whether the detectors were able to send back the values.

The accumulated doses observed at failure for all the subsystems tested are summarized in Table II. The accelerometer as well as the gyroscope was tested via the CM-730 controller. As the servomotors continued to function up to a dose of 1024 Gy, the irradiations went on until failure, which TABLE II: Accumulated dose measured at sub-system failure occurred at a dose of 1400 Gy. Based on this work, it is estimated that H@RI can function up to a total accumulated dose of 200 Gy (failure of the PC2i adaptor and of the HD camera).On nuclear facilities undergoing dismantling, particularly in high level cells, the reference dose for the development of complex systems is 0.1 Gy.h -1 [START_REF] Girones | First report from an advanced radiological inventory for a spent fuel reprocessing plant[END_REF], i.e. 2000 hours of work for the H@ri robot. As a comparison, this dose would represent 10 years of work for a human operator under the terms of French regulations. This limit has been qualified for an environment where only gamma radiation is present. As previously indicated, the components in question were not designed to be irradiation-resistant. For statistical purposes, it would therefore be necessary to carry out a sufficiently large number of tests to determine the level of irradiation resistance and the associated confidence level.

B. GR1 Detector Test

Tests were carried out in order to validate the GR1 detector set-up on the H@RI robot. Standard radioactive Cesium-137 and Europium-152 sources were used for these experiments. This type of source is commonly used in laboratories to test the functionalities of measurement detectors. For these trials, the H@RI robot was equipped with a GR1 detector and placed facing the standard sources (Figure 5).

TABLE III: Acquisition characteristics

The spectra from each of the sources were analyzed to qualify the integration of the gamma spectrometry line (Figure 6). The characteristic lines for the radioactive elements used are clearly found : 662 keV for Cesium-137 and (121 keV, 244 keV and 3444 keV) for Europium-152. This experiment validated the installation of the GR1 gamma spectrometry detector on the H@RI robot. The analysis result shows that the gamma spectrometry line set up in the robot's architecture did not lead to any deterioration in the quality of the spectra : resolution and yield.

C. H@ri robot control test

A final test consisted in simulating an operation where the H@RI robot had to move to position itself facing a surface from which it had to collect a swipe sample. This test was representative of missions which can be needed in contaminated environments, to check the loose (nonfixed) surface contamination. A swipe sample is an efficient, easy way to collect samples from radioactively-contaminated surfaces. During any intervention in an irradiating contaminating environment, the personnel must wear full appropriate P.P.E. Radioactive contamination involves a process leading to a radioactive product being deposited on an object or a living being. Contamination is a phenomenon which is distinct from that of irradiation (see Section IV-A). Thus in order to be able to handle a swipe sampling disk, a device was attached to one of robot's grippers, onto which the swipe was attached. When a contamination risk has been identified, the regulations impose vinyl coveralls to equip any intervening personnel. This approach was kept in mind and Fig. 6: Gamma spectra -GR1 detector on board H@RI the H@RI robot was suitably equipped to prevent any possible contamination (Figure 7). The humanoid's movement within the work zone was managed using the joystick via a WiFi communication. The addition of the GR1 detector on H@RI's head seemed to disturb the center of gravity of the platform, which led to a posture error and thus to instability in walking. To prevent any tipping forward during a movement, the robot's feet were simply lifted in order to compensate for this imbalance. Obviously, it will be necessary to set up a stabilizer which will take into account the data from the gyroscope, accelerometer and other force detectors. This stabilization algorithm will enable the robot to compensate for the impact of the addition of an additional weight. The second phase of this experiment was to carry out the swipe sampling on a tank representative of the equipment found in a nuclear facility. The H@RI robot arm piloting in the work zone was managed by a remotely-located operator. This operator mimed the movements needed to carry out the swipe sampling and the body movements were scanned using an ASUS depth camera, then reproduced by H@RI. Figure 7 illustrates how this sampling was carried out. As can be seen, the operator is separated from the intervention site by a vinyl air lock (Figure 7c) commonly used in the nuclear field to ensure containment of any contamination. This experiment is a good illustration of the robot's ability to replace a human for an intervention in an extreme environment. As this test case did not require the use of grippers, tests of the instrumented glove were carried out separately and proved to be satisfactory. It was shown that controlling a humanoid robot can be a solution for a large number of tasks without needing a specific design for each of the missions it will need to perform. In other words, the humanoid robot appears to be a good alternative to the development of specialized robot, as has been the case in the nuclear field. The use of a small-size humanoid, DARWINOp, as an assistant in a nuclear environment to carry out different tasks (investigation, cleanup) [START_REF] Seyssaud | Robotic d&d : Smart robots-15093[END_REF], has been demonstrated. The result was obtained firstly by including a gamma spectrometry line in the robot for the radiological characterization of its environment by direct readings or by sampling. Secondly, motion capture was used on the body movements of a remotely-located operator for arm control and the development of a containment suit for the robot and irradiation trials (resistance : 200Gy) all contributed. The combination of the innovative controls offered here, very operatorfriendly, improves the remote handling aspects, in particular for cleanup operations which require delicate manipulations. The integration of the system and the development of new functions in the ROS ecosystem were also a success, proven by the general nature of the tasks carried out. At this stage, the applications of this work can be imagined extended to more complex conditions of use, in particular in zones where the floor is cluttered. In this perspective, the robot's stability problems when moving need to be taken into account, as they can interfere with the H@ri robot's approach to the intervention zone where it has been shown to excel. Thus the utilization of anthropomorphic systems for D&D is a support for work on improving the reliability of humanoid movement in extreme environments. Moreover, other lines of study are appearing to meet the need to adapt robots to such environments. In particular, these include dealing with aspects like robot contamination or of improving the humanoid's dose resistance to better withstand extreme conditions.

Fig. 1 :

 1 Fig. 1: Functional architecture

Fig. 4 :

 4 Fig. 4: Electronic component kit (left) and MX-28T servomotor (right)

Fig. 5 :

 5 Fig. 5: H@RI facing a Cesium-137 source during the acquisition

  Fig. 7: H@RI robot dressed in vinyl coveralls

Fig. 7 :

 7 Fig. 7: H@RI robot controlled by operator movement capture to carry out a swipe sample collection

  3: Cobalt-60 irradiator : dose rate simulations by Rayxpert (left) and view inside the bunker (right)

	Accumulated dose level (Gy)	0	5	10	15	20	33	44	53	67	82	87	101	121	136	232	330	428	525	623	720	832	916	1024
	Bunker
	temperature	19	19	19	20	20	20	19	20	20	20	19	20	21	21	21	21	22	22	22	22	22	22	22
	( o C)
	Dose rates (Gy.h -1 )							0.21											0.6

TABLE I :

 I

Irradiation levels

of 1024 Gy at a temperature set at 20 • C. The irradiations were performed with a dose rate of 0.21 Gy.h -1 up to 136 Gy, then 0.6 Gy.h -1 up to 1024 Gy. The irradiation profiles are summarized in Table


Aneel Tanwani

Sylviane Gentil

Suzanne Lesecq

Jean-Marc Thiriet
email: jean-marc.thiriet@inpg.frtanwani2@uiuc.edu

J-M Thiriet

Distributed FDI of a networked embedded microdrone

Keywords: Fault Diagnosis, Embedded system, Generalized Observer Scheme Residual Generation, Distributed computer control system, Network Topology, Drones

teaching and research institutions in France or abroad, or from public or private research centers.

INTRODUCTION

Drones constitute a category of embedded systems whose safety is critical. The system must still be able to exhibit given properties, such as stability or precision, even in the presence of faults. Compared to aircrafts, they constitute low cost systems whose sensors and actuators are often subject to faults (offsets, drifts). Consequently, their maintenance is essential and difficult. Hardware redundancy is not conceivable, not only due to cost but also to constraints on weight, energy and operating space.

Fault Detection and Isolation (FDI) real time constraints are particularly important for these systems. Early detection is necessary but embedded algorithms must be as simpler as possible. Thus computations may be distributed between the embedded system and a more powerful distant computer sharing information through a network. Control, state estimation, fault detection, fault isolation and controller accommodation or reconfiguration must be considered as cooperative functions distributed on the network architecture. Splitting of algorithms is an open problem.

NCS emerged recently with the rapid development of wire or wireless network technology. It is now reasonable to design at the same time the network and the control and FDI algorithms [START_REF] Nilsson | Stochastic analysis and control of real-time systems with random time delays[END_REF][START_REF] Otanez | Using Deadbands to Reduce Communication in Network Control Systems[END_REF]. Evidently, from the FDI point of view the design of residuals and their evaluation is more difficult [START_REF] Fang | Fault diagnosis of networked control systems[END_REF]. Some faults are induced by the network, such as packet losses comparable to an intermittent sensor failure. Delays are induced by the network and should be taken into account by the algorithms [START_REF] Zhang | Observer-based monitoring of distributed networked control systems In[END_REF]. This paper deals with a particular application. This preliminary work is completed in simulation. Section 2 presents the studied prototype: a 4 rotors mini drone equipped with an attitude central for system positioning, made of 3 gyroscopes, 3 accelerometers and 3 magnetometers. The system is controlled in closed loop through a state observer. Several kinds of realistic faults can be hypothesized on this system, whose study is proposed in (Tanwani et al., submitted). The following sections focus on the case of sensor and actuator faults. In section 3, a modelbased diagnostic approach is adopted. A model of the system has been designed for the control synthesis, simulated with SIMULINK and extended to fault analysis. An FDI algorithm based on a generalized observer scheme is proposed and results are commented. Section 4 proposes a network architecture to embed or remotely distribute control and FDI algorithms.

PRESENTATION OF THE SYSTEM

A drone with 4 rotors is regarded as a composition of two PVTOL (Planar Vertical Take off Landing) problems whose axes are orthogonal allowing a movement of six degrees of freedom.

Mechanical model

, p v = (1) . 1 R z B z v ge TR e m = - (2)
.

1 1 ( ) 2 2 q q q ϖ = ⊗Ω= Ω (3)
.

f f a I I G a ϖ ϖ ϖ τ = -× -+ (4)
. , {1,2,3,4

i r i i I Q i ω τ = - ∈ }
(5) where m indicates the mass of the drone, g is acceleration due to gravity, e z = (0, 0, 1) T is an unit vector in reference frame R, the vector p = (x, y, z) T indicates the position of the origin of frame B relative to frame R, the vector v = (v x , v y , v z ) T is the linear velocity of the origin of B measured in the reference frame R. The orientation of the drone is given by the orthogonal rotation matrix .

(3) R B R SO ∈ 3 3 f I × ∈ ℜ is a
symmetric positive definite constant inertia matrix of the drone with respect to the frame R whose origin is at the centre of mass. The speed and the moment of inertia of rotor i are indicated, respectively, by ω i and I r . The reactive torque generated by rotor i is given by:

2 i i Q kω = (6)
and the total thrust generated by four rotors is given by:

4 4 2 1 1 i i i i T f b ω = = = = ∑ ∑ (7)
k > 0 and b > 0 are two parameters depending on the air density, the radius, the shape, the pitch angle of the blade and other factors. The gyroscopic torques, due to the combination of the rotation of the drone and the four rotors, are modelled as: The drone torques generated by rotors are given by:

1 2 2 2 4 2 2 2 1 3 3 2 2 2 1 3 2 2 ( ) ( ) ( )
where d represents the distance from the rotors to the centre of mass of the drone, and τ i represents the torque produced by rotor i.

In equation ( 3), the attitude dynamics are represented by ( ) 0 , T q q q = r which is a rotational quaternion [START_REF] Chou | Quaternion kinematics and dynamic differential equations[END_REF][START_REF] Guerrero Castellanos | A low-cost air data attitude heading reference system for the tourism airplane applications[END_REF] ) that gives the orientation of the drone.

( )

0, T ϖ Ω =
is a quaternion with ϖ the angular velocity of the drone measured by the gyrometers in the frame B. indicates quaternion multiplication which leads to the following definition of

⊗ ( ) ϖ Ω : 0 ( ) T ϖ ϖ ϖ ϖ × ⎛ ⎞ - ⎜ Ω = ⎜ ⎟ ⎟ ⎡ ⎤ -⎣ ⎦ ⎝ ⎠ ( 10
)
where ϖ × ⎡ ⎤ ⎣ ⎦ is the self cross product.

Sensors

The estimation of attitude (or orientation), position and speed is the pre requisite for flight control. For this purpose, a central navigation unit is used that consists of a tri-axis accelerometer (a 1 , a 2 , a 3 ) a triaxis magnetometer (m 1 , m 2 , m 3 ) and a tri-axis rate gyroscope (g 1 , g 2 , g 3 ). These sensors use MEMS (Micro Electronic and Mechanical Systems) technology to reduce the weight, dimension and cost.

1) Rate Gyros: The angular velocity ϖ is measured by tri-axis rate gyros that are usually affected by various errors, such as fixed bias, drift bias, fixed scale or asymmetric scale factor error, and noise. Theoretically, the integral of ϖ gives the relative orientation but the presence of bias at low frequencies generates errors which accumulate over time. The sensor measurements are modelled as:

. 1 1 ,

g 2 ϖ ϖ ν η ν ν η τ = -- = - + (11)
where g ϖ is the sensor value, ν is the bias, 100 τ = s is the time constant obtained from an Allan Variance chart, and η i are assumed to be Gaussian white noises.

2) Accelerometers: The 3-axis accelerometer senses inertial forces and gravity in the aircraft body coordinate system B. The transformation of force and gravity from inertial frame R to body frame is given by: ( )( )

acc z acc b C q a ge η = - + r r (12)
where is the value measured by sensors. The motion is supposed quasi static: linear accelerations are negligible. In this way, accelerometers are only sensible to earth's gravitational pull.

acc b r

The rotation matrix is the Rodrigues matrix, defined as:

( ) C q 2 ( ) ( ) 2( ) T T o C q q q q I qq q q × ⎡ ⎤ = - + -⎣ ⎦ r r rr o (13)
3) Magnetometers: the information provided by a 3axis magnetometer is added to the inertial measurements. The magnetic field vector is transformed to the mobile frame attached to the aircraft and is defined by: ( )

mag m mag b C q h η = + r r (14)
where ( )

0 T m m x m z h h h = r r r
and mag b r are the components of the magnetic field vector in R and B, respectively.

STATE OBSERVER AND CLOSED LOOP CONTROL

The measurements provided by the above mentioned accelerometers, magnetometers and rate gyros are used to feed an observer. The speed and quaternion estimation are used in a feedback loop. The reference corresponds to a quaternion (Fig. 2). For simplification, q=(1 0 0 0) T is chosen as reference for the following simulations. Several state observers have been tested. An extended Kalman filter (Fig. 3) has provided good results. In this filter, the prediction part of the algorithm uses only the gyros measurements while the accelerometers and magnetometers outputs are used for correction [START_REF] Tanwani | Stratégies de diagnostic pour un système embarqué: application à un mini drone 4 rotors[END_REF].

FDI ALGORITHM

As a state observer has been designed for the control synthesis, it seems quite natural to investigate if this observer is useful for diagnosis. The use of a bank of observer to design structured residuals is well known [START_REF] Isermann | Fault Diagnosis Systems: An introduction from fault detection to fault tolerance[END_REF].

Diagnosis of Sensors

To isolate a fault concerning one of the output sensors, under the hypothesis that actuators are faultfree, a Generalized Observer Scheme (GOS) is used.

Based on this principle, an observer that takes 8 out of 9 system outputs is used to generate structured residuals. The basic idea is to estimate a quaternion using these 8 sensor values and compare this to the quaternion calculated via the drone mechanical model (Fig. 4). The residual is thus insensitive to the faults in the sensor that is not used and the signature table strongly isolable. Table 1 is the fault signature table obtained in case of faults in the three rate gyros. It shows that the estimator gyro1 is sensitive to faults in all the sensors (f ai , f mi , f gi , i∈1,2,3) except f g1 , which indicates the fault in rate gyro 1 (along x -axis). The same definition applies to all other symbols. Thus, it is possible to isolate the fault in rate gyros by looking at the residuals generated by the three observers mentioned in the first column of Table 1.

f a1 f a2 f a3 f m1 f m2 f m3 f g1 f g2 f g3 gyro1 1 1 1 1 1 1 0 1 1 gyro2 1 1 1 1 1 1 1 0 1 gyro3 1 1 1 1 1 1 1 1 0
The same technique is applied for the surveillance of accelerometers and magnetometers but the values of these sensors are a nonlinear function of quaternion.

The technique was modified and the observer was replaced by an optimisation algorithm to find an optimal quaternion qopt (Fig. 3). The technique of optimization would generate an optimal quaternion using five out of six measurements of accelerometers and magnetometers. Thus the idea of generalized observers is conserved but the observer is replaced by an estimator which uses optimization algorithm.

f a1 f a2 f a3 f m1 f m2 f m3 f g1 f g2 f g3 acc1 0 1 1 1 1 1 0 0 0 acc2 1 0 1 1 1 1 0 0 0 acc3 1 1 0 1 1 1 0 0 0 mag1 1 1 1 0 1 1 0 0 0 mag2 1 1 1 1 0 1 0 0 0 mag3 1 1 1 1 1 0 0 0 0
Table 2 shows that the estimator acc1 is insensitive to faults in accelerometer along x-axis (f a1 ). The '1's in the first row show that a non zero residual is generated by acc1 if there appears a fault in any other accelerometer or magnetometer. Note that all these six estimators are insensitive to faults in rate gyros.

Algorithm

The observers that estimate the quaternion using 3 accelerometers, 3 magnetometers and 3 rate gyros already exist [START_REF] Guerrero Castellanos | A low-cost air data attitude heading reference system for the tourism airplane applications[END_REF]. The problem that confronts us is the quaternion estimation while neglecting one of the sensor values. In the formulation mentioned for rate gyros, it must be noted that 8 sensor measurements are used and the last one is modelled mathematically. The classical Kalman filter is further used to get . Residuals are generated following the scheme in Fig. 4. The first step is to find quaternion of error (qe) using:

q 1 - ⊗ = model estim e q q q
( 1 5 ) Since this is a quaternion of rotation, it has the following form:

0 cos sin 2 2 T T e e e
e e e q q q u φ φ

⎡ ⎤ ⎛ ⎞ ⎛ ⎞ ⎡ ⎤ = = ⎢ ⎥ ⎜ ⎟ ⎜ ⎟ ⎣ ⎦ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦ uur ( 16
)
and finally the residual e φ is computed in degrees, The residual e φ actually has some physical meaning:

it is the difference between the original orientation and the estimated orientation of the drone.

The above results have also been verified using a non linear observer for which the algorithm is given in the appendix.

While discarding one of the accelerometers or magnetometers measurements, these observers cannot be used to estimate the quaternion. Hence an optimization algorithm is proposed to calculate an optimal quaternion q opt . The criterion to be minimized is:

6 2 1 ( ) ( ( ) ( )) mes j f q C q r v j = = - ∑ r ( 18
)
where

6 1 T m r g h × ⎡ ⎤ = ∈ℜ ⎣ ⎦ r r r
. Once q opt is calculated from this equation, the residuals can be computed in exactly the same way as mentioned in equations 15 through 17.

Diagnosis of Actuators

The 4 actuators are independent. The model of each electrical motor has been used for their surveillance.

Due to the constraint imposed by the availability of a single sensor that measures the rotor speed, the principle shown in Fig. 5 is used for fault diagnosis of each rotor: Hence, the fault signature is given by Table 3. Rotor1 1 0 0 0

Rotor2 0 1 0 0 Rotor3 0 0 1 0 Rotor4 0 0 0 1
There are several limitations to this technique. A fault in speed sensor or in motor cannot be differentiated. Also, the form of residual is strictly dependent upon the difference of speed which may not always be suitable for boolean decision making. This limitation could be removed by additional sensors to measure other variables such as current or voltage but it is contrary to the weight constraint.

Simulation results

The closed loop system in Fig. 2 is simulated with Matlab Simulink and various faults have been injected into the system. The FDI performance is now discussed.

In the first experiment (Fig. 6), the information delivered by the rate gyro along y-axis is assumed to be lost at t=5 (f g2 fault, Table 1 and2). The residuals generated by acc1, acc2, acc3 (first row of Fig. 6) and mag1, mag2, mag3 (second row) remain null even after the fault has occurred. Residuals generated by gyro1 and gyro3 are non zero after t=5 and gyro2 is insensitive to f g2 (third row). This is consistent with Tables 1 and2. In the second experiment, a failure of the magnetometer along x-axis is considered. The fault is simulated at t=4. In Fig. 7, the residuals generated by the six estimators of Table 2 are shown and once again the results are consistent with the theoretical formulation. Only estimator mag1 is insensitive to the faults in the magnetometer along x-axis (f m1 ). 2 for total breakdown in magnetometer along xaxis (f m1 ).

For actuators, Fig. 8 shows the case of a fault winding in rotor 1. The fault is simulated at t=5 and the residual increases immediately.

Figure 8. Fault winding in rotor 1.

NETWORK ARCHITECTURE

The benchmark presently in development will be equipped with two networks (Fig. 9).

The first network is an embedded network on the drone-helicopter itself. The control loop is closed through the embedded network that must be designed taking into account the fact that the system has fast dynamics and strong real-time constraints. The problems induced by the network are studied in (Tanwani et al., submitted).

Fig. 9. The two networks.

The second network is a wireless network which aims at ensuring the communication between the dronehelicopter (a mobile vehicle) and the ground. It is evident that calculations related to the 9 observers and the 4 actuators fault detection algorithms can be really time-consuming. It is thus not reasonable to implement them on the embedded microcontroller.

The FDI and FTC algorithms will be deported in the ground station. Evidently, the duration of the transmission will be longer, and the real-time constraints will not be met as easily as in the case of the wired network, so some strategies of Networked Fault-Tolerant Control and decentralised Diagnosis will be tested.

DISCUSSION

This paper has discussed the design of a benchmark embedded system: a drone, with state estimation and closed loop control. The original point of the presented approach is the use of a quaternion vector to represent the mobile position instead of the Euler angles. The quaternion is observed thanks to nine sensors. Some of these sensors can be related to the dynamic model while others represent static relations verified by the quaternion. Thus the observer equations are twofold: a least squares estimation algorithm for the static relations and an extended Kalman filter for the dynamic relations.

This observer needs to be modified to allow fault detection and isolation through a Generalized Observer Scheme. A strongly isolable signature table is obtained. Future work concerns the study of other types of observers that have been proposed in the literature for FDI. As a first principle reliable model of the process is available, approaches based on behavioural models such as neural networks do not seem, at a first glance, to be relevant [START_REF] Koscielny | Fault diagnosis: models, artificial intelligence, applications[END_REF]. But approaches based on non linear observers require a lot of attention [START_REF] Kinnaert | Robust fault detection based on observers for bilinear systems[END_REF][START_REF] De Persis | A geometric approach to non linear fault detection and isolation[END_REF] .

The residual generation and decision making process are time consuming. As time constraints are a crucial aspect in this application, attention must be paid to the way algorithms can be implemented. It is hardly imaginable that the bank of observers can be executed in the embedded system. It is rather envisaged that the FDI algorithms will be deported on a ground station related to the drone by a wireless network. The embedded network will be in charge only of the closed loop control. The network effect on the residual evaluation will need a careful study. The idea for future research is to examine specific problems such as the network induced delays, the loss of messages (or packets) due to the worse Quality of Service between the drone and the ground station and the management of the roaming (between several ground stations).

[ ]

B. Non Linear Observer

A nonlinear observer is implemented jointly with the previous algorithm in order to estimate a reliable attitude quaternion:

[ ] ε ϖ 1 ) ( 2 1 ) ( ˆK b q t q g + - Ξ = & ε 2 1 ˆK b T b - - = - &
where T is a diagonal matrix of time constants and K i , i =1, 2 are chosen to be positive definite matrices.

is predicted attitude at time t, obtained by propagating the kinematics equation using the measured angular velocity, the bias estimate and ε which depends on the discrepancy q ) ( ˆt q e between and q ) ( ˆt q ms (t).

[

] T e e ms e q q t q t q q r 0 1 ) ( ) ( ˆ= ⊗ = -) sgn( 0 e e q q r = ε

Fig. 1 .

 1 Fig. 1. Coordinate frames assigned to the drone The four electric motors, driving the four blades, provide the thrust for the movement of the drone (Tayebi and Mc Gilvray, 2004), Fig. 1. To develop the dynamic equations, consider R, an inertial frame of reference and B, a frame attached to the drone. The dynamic model is described by the following equations:.

Fig. 2 .

 2 Fig. 2. The control loop.

Fig. 3 .

 3 Fig. 3. The observer principle.

  Fig. 4. Residuals generation using observers

  Fig. 5. Residual generation for actuators

Fig. 6 .

 6 Fig. 6. Residuals generated by the 9 estimators for the total breakdown in rate gyro along y-axis (f g2 ).

Fig. 7 .

 7 Fig. 7. Residuals generated by the 6 estimators of Table2for total breakdown in magnetometer along xaxis (f m1 ).

  magnetic field vectors in the inertial coordinate system R.

Table 1 .

 1 Fault signature for diagnosis of rate gyros

Table 3

 3 Fault signature for diagnosis of actuators f rotor 1 f rotor 2 f rotor 3 rotor 4

Appendix

A. Linear Attitude Estimation

, i = 1 : n are the corresponding vectors expressed in inertial frame R. Then, the measurement equation 12 and 14 at time t k can be modeled as: