Lisa Serir
email: lisa.serir@femto-st.fr

Emmanuel Ramasso
email: emmanuel.ramasso@femto-st.fr

Noureddine Zerhouni
email: noureddine.zerhouni@femto-st.fr

Time-Sliced Temporal Evidential Networks: the case of Evidential HMM with application to dynamical system analysis

Diagnostics and prognostics of health states are important activities in the maintenance process strategy of dynamical systems. Many approaches have been developed for this purpose and we particularly focus on data-driven methods which are increasingly applied due to the availability of various cheap sensors. Most data-driven methods proposed in the literature rely on probability density estimation. However, when the training data are limited, the estimated parameters are no longer reliable. This is particularly true for data in faulty states which are generally expensive and difficult to obtain. In order to solve this problem, we propose to use the theory of belief functions as described by Dempster, Shafer (Theory of Evidence) and Smets (Transferable Belief Model). A few methods based on belief functions have been proposed for diagnostics and prognostics of dynamical systems. Among these methods, Evidential Hidden Markov Models (EvHMM) seems promising and extends usual HMM to belief functions. Inference tools in EvHMM have already been developed, but parameter training has not fully been considered until now or only with strong assumptions. In this paper, we propose to complete the generalization of HMM to belief functions with a method for automatic parameter training. The generalization of this training procedure to more general Time-Sliced Temporal Evidential Network (TSTEN) is discussed paving the way for a further generalization of Dynamic Bayesian Network to belief functions with potential applications to diagnostics and prognostics. An application to time series classification is proposed.

I. INTRODUCTION

Fault diagnosis and prognosis are two key elements of effective Condition-Based Maintenance. Today's concept of machine diagnosis comprises the automated detection and classification of faults, whereas machine prognosis is the automated estimation of how soon and likely a failure will occur [START_REF] Heng | Rotating machinery prognostics: State of the art, challenges and opportunities[END_REF]. One approach to prognosis is to use a physicsbased model of the system. Another approach is the expert system approach. A third approach, on which we focus our interest, is the data-driven approach, which uses historical data to automatically learn a model of the system's behavior. Algorithms that use the data-driven approach to prognosis learn models directly from the data, rather than using a model based on human expertise. Artificial intelligence techniques, such as expert system, neural network, fuzzy logic and genetic algorithm, have been employed to assist the diagnostic task to correctly interpret the fault data. Neural network technique has gained popularity over other techniques as it is efficient in discovering similarities among large bodies of data.

Another common solution is to use state sequence representation, learning and inference algorithms. A state generally represents a stationarity or a functioning mode in the data and describes the dynamical system at a given time, while transitions represent its dynamics. In practical applications, states are hidden and only features are observable. An additional modelling step is thus required to relate features to states. To manage imperfections, the modelling should cope with uncertainty using probability theory, possibility theory or evidence theory [START_REF] Klir | Uncertainty-based information[END_REF], the latter being more general.

Hidden Markov model (HMM) [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF] is one commonly used method for state sequence representation and recognition. They represent an appropriate model for analyzing event and condition monitoring data together. An HMM consists of two stochastic processes: a Markov chain with a finite number of states describing an underlying mechanism and an observation process depending on the hidden state. Early applications of HMM in fault classification and diagnostics treated the real machine faulty states and the machine normal state as the hidden states of the HMM. The use of HMM in bearing fault prognosis was investigated by Zhang et al. [START_REF] Zhang | An integrated approach to bearing fault diagnostics and prognostics[END_REF] where one HMM was trained to recognise one type of cone-andcup bearing faults based on the corresponding vibration data. The HMMs were also trained to estimate the fault states. The similarity between current state and failure state was used as the bearing degradation index, which was then extrapolated to estimate the time of exceeding a predetermined failure threshold. Dong and He [START_REF] Donga | A segmental hidden semi-markov model (hsmm)based diagnostics and prognostics framework and methodology[END_REF] have proposed a segmental Hidden Semi-Markov Model (HsMM) which generates a segment of observations where durations are estimated from training data.

For the problem of state sequence modelling and recognition, we propose here to use the theory of belief functions as described by Dempster and Shafer's Theory of Evidence [START_REF] Dempster | Upper and lower probabilities induced by multiple valued mappings[END_REF], [START_REF] Shafer | A mathematical theory of Evidence[END_REF] and Smets' Transferable Belief Model [START_REF] Smets | Advances in the dempster-shafer theory of evidence -what is dempster-shafer's model ?[END_REF], [START_REF] Smets | The transferable belief model[END_REF]. Belief functions cope with some limitations of usual HMMs [START_REF] Bilmes | What HMM can do[END_REF]:

• The use of belief functions allows the modelling of information on states without priors. Vacuous belief functions are used when no prior knowledge is available. • HMMs requires probability density estimation, which can be no longer reliable when the training data are limited. This is particularly true for data in faulty states which are expensive and difficult to obtain. Belief functions takes this lack of information into account. • In some cases, observations provided by sensors are reliable only in some context and for some specific subset of states. The theory of belief functions allows modelling of this case easily. • Emission models used in HMM are based only on probability. However, there are some cases where some knowledge can be generated using fuzzy or belief functions formalisms. The use of belief functions provides tools to combine information in a common framework, using specific operators for information fusion with non-distinct sources [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. Although inference tools in EvHMM have been developed [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF], parameter training has not been considered without the use of strong assumptions [START_REF] Mohamed | Generalized HMM -part 1: Theoretical frameworks[END_REF], [START_REF] Pieczynski | Multisensor triplet markov chains and theory of evidence[END_REF]. In this paper, we first propose to complete the generalization of HMM to belief functions with a method for automatic parameter training. The generalization of this training procedure to more general Time-Sliced Temporal Evidential Network (TSTEN) is discussed, paving the way for a further generalization of Dynamic Bayesian Network (a generalization of HMM) to belief functions with potential applications to diagnostics and prognostics.

The paper is organized as follows: Section II describes HMM basics and is followed by a brief description of belief functions in Section III. EvHMM inference mechanisms are then presented. Compared to [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF] where canonical weights are used, we here present the procedures using the communality function to fulfill the requirements described in [START_REF] Shenoy | Valuation-based systems: A framework for managing uncertainty in expert systems[END_REF], [START_REF] Shenoy | Axioms for probability and belief function propagation[END_REF] for belief propagations. Section IV and parameter training are finally presented in Section V.

II. PROBABILISTIC HMM BACKGROUND

The notations and basic mechanisms of HMMs described in the tutorial of Rabiner [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF] are presented in this section.

A sequence is defined by a set of N states in the set Ω t called the frame of discernment with:

Ω t = {s 1 , s 2 , . . . s N } (1)
and s i ∈ Ω t is the i-th state at time t. States are said hidden because only -continuous -observations

O t = [O 1 O 2 . . . O F ],
t ∈ {1..T } (F is the dimension) are actually measured on the dynamical system. Each observation O t generates a degree of confidence on each state s i that is generally represented by a likelihood P (O t |s i ), denoted by b i (O t ). The latter are assessed by a modelling technique B such as a mixture of Gaussians [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. At each time, the transition from a state s i (at t -1) to a state s j (at t) has a probability a ij = P (s j |s i ).

The

N × N stochastic matrix A = [a ij ], i ∈ {1 . . . N }, j ∈ {1 . . . N } such as j a ij = 1 is called the transition matrix.
At time t = 1, the a priori on states is represented by the initial distribution on states π i , i ∈ {1 . . . N }. An HMM λ = {A, B, Π} is thus characterized by three elements: the transition matrix A, the observation models B (generating likelihoods b i (O t )) and the initial distributions π i .

The forward and backward propagations are the basic mechanims of the HMM that ensure the temporal coherence and compute useful quantities for inference and learning:

• Forward / filtered estimate: α t (s j |λ) = P (O 1 , O 2 . . . O t , s j |λ) = ∀si∈Ωt-1 α t-1 (s i ) • a ij • b j (O t )
, used in particular for classification since the log-likelihood of a sequence of observations given a HMM λ r is:

L p (λ r ) = 1 T T t=1 log   sj ∈Ωt α t (s j |λ r )   (2)
and the best model is

λ * = argmax r L p (λ r ). • Backward: β t (s i ) = P (O T , O T -1 . . . O t+1 |s i , λ) = ∀sj ∈Ωt+1 a ij • b j (O t+1 ) • β t+1 (s j ), • γ-variable / smooth estimate: γ t (s j ) = P (s j |O 1:T , λ) ∝ α t (s j ) • β t (s j )
, used in particular to determine both the most probable state at t and model's parameters B,

• ξ-variable: ξ t (s i , s j ) = P (s i , s j | O 1:T , λ) ∝ α t (s i ) • a ij • b j (O t+1 ) • β t+1 (s j
) used to estimate the expected probabilities of a transition by:

a ij ∝ T -1 t=1 ξ t (s i , s j ) (3)
• Viterbi metric δ: computed similarly as α but replacing the sum a maximum (max-product algorithm).

III. TBM BACKGROUND

The Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model[END_REF] is a general framework for uncertainty representation and combination of various pieces of information without additional priors. In particular, doubt and conflict are explicitly emphasized. Typically, the former represents ignorance and the latter emphasizes the contradiction within a fusion process. This section reviews some basic notions.

A. Belief mass

The belief of an agent in subsets of the frame of discernment Ω t can be represented by a basic belief assignment (BBA), also called belief mass assignment:

m Ωt : 2 Ωt → [0, 1], A → m Ωt (A) A⊆Ωt m Ωt (A) = 1 (4)
A belief mass can not only be assigned to a single state (|A| = 1), but also to a subset (|A| > 1) of states without assumption concerning additivity. This property permits the explicit modelling of doubt between states (composing A) and constitutes a fundamental difference with probability theory. Elements A for which m Ωt (A) > 0 are called focal sets.

A normalised BBA is such as the degree of conflict is nil:

   m Ωt * (A) = m Ωt (A) 1 -m Ωt (∅) m Ωt * (∅) = 0 (5)
This process is called Dempster normalisation. Other sound redistribution rules for conflict normalisation exist [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF].

B. Other belief functions

Several functions -in one-to-one correspondance [START_REF] Smets | The transferable belief model[END_REF] -can be computed from a BBA. Depending on the context of application, these functions are used to represent the knowledge and to make the combination rules easier to compute.

In the following, the communality q will be used and is defined by:

q Ωt (B) = C⊇B m Ωt (C) (6)
The plausibility is also an important function:

pl Ωt (B) = C∩B =∅ m Ωt (C) (7)
In particular pl Ωt (Ω t ) = 1 -m Ωt (∅) links the plausibility of "everything" (considered in the frame Ω t ) to the opposite of the belief mass of "nothing". This relation is actually a bridge from likelihood maximization principle to minimum of conflict principle, also called unlikelihood [START_REF] Ramasso | State filtering and change detection using TBM conflict[END_REF].

C. Combination

The combinations of several sources of belief can be computed by four main rules [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. In the sequel we will mainly used the conjunctive rule of combination (CRC, ∩ ):

q Ωt 1 ∩ 2 (B) = q Ωt 1 (B) • q Ωt 2 (B) (8)
The CRC is a simple product in the q-space while it implies several summations and products in the m-space:

m Ωt 1 ∩ 2 (B) = C∩D=B m Ωt 1 (C) • m Ωt 2 (D) (9)
If the CRC is used and if the obtained belief mass (using the inverse transform from q to m) is normalised (Eq. 5) then we obtain Dempster rule of combination [START_REF] Dempster | A generalization of bayesian inference[END_REF].

D. Conditional BBA

A conditional BBA can be used to represent the state of knowledge. For example m Ωt|Ωt-1 (•|S i ) is a BBA defined on Ω t conditionally to subset S i ⊆ Ω t-1 . Conditioning is also a process which consists in combining conjunctively (using the CRC, Eq. 9) a BBA m Ωt with a categorical BBA defined by m Ωt 2 (A) = 1, i.e. the latter has the particularity to be nil except for one single element A ⊂ Ω t ("A" is the condition).

Therefore, after conditioning, the focal sets -elements for which the mass is greater than zero -have a non-empty intersection with A which becomes the restricted frame of discernment. The key point is that the mass on the empty set increases and is given by the following defintion.

Definition 1: After conditioning of a BBA m Ωt by a subset A, the mass on the empty set is equal to:

1 -m Ωt (∅|A) = pl Ωt (A) (10)
and:

• when |A| = 1, only two focal sets remain: ∅ and A,

• when |A| > 1, there may be more than two focal sets, including ∅.

E. Generalized Bayes theorem

The Generalized Bayesian Theorem (GBT) is an extension of Bayesian Theorem in the TBM framework [START_REF] Smets | Beliefs functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF]. The GBT alleviates the problem of priors, since belief functions make the representation of total ignorance possible. Expression of the GBT varies according to the type of belief functions. For example, in the sequel we will use the q -pl form:

q Ωt|Ωt+1 a (S i |S j ) = si∈Si pl Ωt+1|Ωt a (S j |s i ) (11)

F. Law of total plausibility

The law of total plausibility will be used for projection and is given by:

pl Ωt+1 (S j ) = Si⊆Ωt pl Ωt+1|Ωt (S j |S i ) • m Ωt (S i ) (12)
This equation remains valid with m or q instead of pl [START_REF] Smets | Beliefs functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF].

G. Decision making

After combination of multiple sources of belief, a resulting BBA m Ωt is obtained. Decision making in the TBM framework consists in the choice of the best hypothesis from the pignistic probability distribution [START_REF] Smets | The transferable belief model[END_REF] or the plausibility transform [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF].

IV. EVIDENTIAL HMM

Compared to [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF] where canonical weights are used, we here present the procedures using the communality function in order to fulfill the required axioms described in [START_REF] Shenoy | Valuation-based systems: A framework for managing uncertainty in expert systems[END_REF], [START_REF] Shenoy | Axioms for probability and belief function propagation[END_REF] for belief propagations [START_REF] Pichon | Belief functions: canonical decompositions and combination rules[END_REF]. Canonical weights can be used but only with the product operator which is equivalent to use the communalities.

A. Classification in EvHMM

Given an observation sequence O 1:T (length T ) and a set of EvHMMs λ 1...R , the goal of the classification process is to choose the EvHMM that best fits observations. The classification criterion is given by [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF]:

L e (λ r ) = 1 T T t=1 log pl Ωt α (Ω t |λ r ) (13a) λ * = argmax r L e (λ r ) (13b)
and is a generalization of HMM criterion to belief functions. This criterion relies on the opposite of the conflict value (which is a plausibility) computed in the forward propagation. Therefore, it has a natural interpretation: the less the conflict, the more likely is the model λ. The EvHMM classification process is presented in Algorithm 1.

The computation of the evidential forward variable at t satisfies a "prediction -update" mechanism. The prediction of proposition S j is first computed using the law of total plausibility (Eq. 12). The prediction is then combined with observations in order to update belief on states:

q Ωt α (S j ) = Si⊆Ωt-1 m Ωt-1 α (S i ) • q Ωt a (S j |S i ) • q Ωt b (S j ) (14)
The prior on states at t = 1 can be "vacuous" and this state of knowledge is easily represented by q Ω1 α (S i ) = 1, ∀S i ⊆ Ω 1 meaning total ignorance. This equation generalizes the probabilistic forward variable when transitions, observations, and prior are all Bayesian (i.e. the belief mass is nil except for singleton hypotheses) and with Dempster normalisation (Section III-C). In the worst case, the evidential version has a complexity is equal to T • N • 2 N , with N the number of states and T the sequence length (vs T • N 2 in HMM). In this equation, q Ωt a (•|S i ) are the conditional communalities defined on Ω t conditionally to subsets S i ⊆ Ω t-1 and representing transitions between subsets at t-1 and t, and q Ωt b ≡ q Ωt b (•|O t ) are communalities obtained from current observations.

Remark 1: The conflict resulting from the conjunctive combination between observations and prediction must be cancelled out (by normalisation) at each iteration because it is absorptive by the conjunctive rule (embedded within the forward propagation). As in probabilistic HMM, where the normalisation process consists in redistributing uniformly 1j α t (j) to each state at t, belief function framework also provides a similar process (Eq. 5) [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF] [β γ ξ] = Backward propagation {Eq. 15 and 16. If ξ is required then use Eq. 22 of [START_REF] Ramasso | Forward-backward-viterbi procedures in TBM for state sequence analysis using belief functions[END_REF] or see Section V-B for an approximation} 8: end for

B. Hidden state sequence recognition using smoothing

As in probabilistic HMM, one can use the γ-variable (posterior probability of states given observations) for state recognition. In EvHMM, a similar process can be used. For that, the evidential backward variable has to be computed:

q Ωt β (S i ) = Sj ⊆Ωt+1 m Ωt+1 β ∩ b (S j ) • q Ωt a (S i |S j ) (15)
which follows also a prediction-fusion scheme. The BBA m Ωt+1 β

is the backward variable defined on subsets of states at t + 1, pl ). Then a projection towards Ω t is carried out. For this, given transitions in the pl-space, the posterior conditional communalities q Ωt a (•|S j ) are obtained from these plausibilities by applying the GBT (Eq. 11). Note that unknown prior at T is modelled by a vacuous BBA (q Ω T β (S i ) = 1, ∀S i ⊆ Ω T ) and Eq. 15 reduces to the probabilistic case if all BBAs are Bayesian and if Dempster rule is used.

The evidential γ variable is then computed by the conjunctive combination of both forward and backward variables:

q Ωt γ (S j ) = q Ωt α (S j ) • q Ωt β (S j ) (16)
The γ-variable is then used for the detection of the best state s * t at a given time t. This state can be found by maximizing the pignistic probability [START_REF] Smets | The transferable belief model[END_REF] or the plausibility [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF]. The γvariable is not always well-suited for state recognition because the decision is too "local". In [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF], a Viterbi-like procedure was proposed to find the best sequence of hidden states. This procedure is not optimal but draw benefits of belief functions. In this paper, we propose an optimal version.

C. Hidden state sequence recognition using a Viterbi procedure

The problem is to find the best sequence of states. A solution is to maximize the state sequence plausibility. For that, let consider a sequence of singletons states {s 1 , s 2 , . . . s T } with |s t | = 1. At t = 1, the available information are: the prior m Ω1 π and observations m Ω1 b . They have to be combined by the CRC rule and then conditioned on s 1 . Since conditioning is made by a singleton, the BBA has two focal sets: ∅ and s 1 . Therefore, at t = 1, the combination leads to pl δ (s 1 ) = pl π (s 1 ) • pl b (s 1 ).

Then at time t = 2, one observes that the true state is

s 2 . Given the transition BBA m Ω2|Ω1 a [s 1 ], conditioning by s 2 gives m Ω2|Ω1 a [s 1 , s 2 ](∅) and m Ω2|Ω1 a [s 1 , s 2 ](s 2 )
, where the latter is equal to pl Ω2|Ω1 a [s 1 ](s 2 ) (after conditioning since s 2 is a singleton). Observations are also conditioned by s 2 and the combination of all these information provides:

pl δ (s 1 , s 2 ) = pl π (s 1 ) • pl b (s 1 ) • pl Ω2|Ω1 a [s 1 ](s 2 ) • pl b (s 2 ).
Applying the same reasoning for the whole sequence, we have the following definition.

Definition 2: In EvHMM, the plausibility of a sequence of singleton states S = {s 1 , s 2 , . . . s T }, |s t | = 1 is given by:

pl δ (S) = pl π (s 1 ) • T t=2 pl Ωt|Ωt-1 a [s t-1 ](s t ) • T t=1 pl b (s t ) (17)
Proposition 1: Eq. 17 remains valid for subsets (which are not considered in this paragraph). To show this property, it is sufficient to consider the mass on the empty set after conditionning which is equal to the opposite of the plausibility of the conditioning subset.

Given all possible state sequences, one can apply Eq. 17 and then choose the best sequence S * by:

S * = argmax S={s 1 ,s 2 ,...s T } pl δ (S) (18)
which is intractable because the number of possible sequences is N T , which leads to the following proposition. Proposition 2: The Viterbi algorithm defined in probabilistic HMM can be applied using as imputs the plausibilities on singletons: pl π (s i ),

s i ∈ Ω 1 (prior), pl Ωt|Ωt-1 a [s t-1 ](s t ), s t-1 ∈ Ω t-1 , s t ∈ Ω t (transitions)
and pl b (s t ), s t ∈ Ω t (observations). Finding the best sequence is then performed in N • T . If no prior information is available at t = 1, then pl π (s i ) = 1, ∀s i ∈ Ω 1 (i.e. the related BBA is vacuous). The Viterbi metric is thus a plausibility.

Proposition 3: In the maximization, it is not relevant to consider all possible sequences of subsets S t ⊆ Ω t (even though Eq. 17 remains valid) because the plausibility increases as the cardinality of the subsets increases and therefore the resulting optimal sequence would be S * = {Ω 1 , Ω 2 , . . . Ω T } which brings no information.

D. The case of Evidential Markov Chains (EMC)

In Markov chains, the state s t ∈ Ω t is observed. In Evidential Markov Chains (EMC), the originality is that the state can be a subset S t ⊆ Ω t . In signal and image processing, observations of subsets can be useful in transitions where the state is naturally imprecise.

Thus, in EMC, we have a sequence S = {S 1 , S 2 , . . . S T }, S t ⊆ Ω t , and one is interested in assessing the plausibility of this sequence. Reasoning similarly as in the previous Viterbi procedure but conditioning by the subsets in the sequence S and considering that the true subset is perfectly known (pl b (S t ) = 1), we have the following definition.

Definition 3: In an EMC, the plausibility of a sequence S = {S 1 , S 2 , . . . S T }, S t ⊆ Ω t is

pl δ (S) = pl π (S 1 ) • T t=2 pl Ωt|Ωt-1 a [S t-1 ](S t ) (19)
EMC were first proposed in [START_REF] Pieczynski | Multisensor triplet markov chains and theory of evidence[END_REF]. However, the authors propose to use the BBA (cf. Definition 4.1 in [START_REF] Pieczynski | Multisensor triplet markov chains and theory of evidence[END_REF]) in order to assess the support given to a sequence. We here justify theoretically the use of plausibilities instead. In particular, if one uses only belief masses on subsets then pieces of information are lost.

V. TRAINING IN EVHMM

The problem is to learn transitions (m a ) and models (B) in EvHMM. As underlined in [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF], applying an iterative procedure as in EM-based HMM training is not relevant. Indeed, successive forward and backward propagations imply conjunctive combinations which has a tendancy to generate specific BBAs focused on singletons, therefore loosing the interest of using belief functions. We rather propose two distinct processes: one for observation models (called RCGI) and one for transitions (called ITS).

A. RCGI: Observations models training

The proposed training process of observation models can be decomposed in two steps: Clustering data into M clusters (called components in the sequel) and Regrouping the M components into N states. The main features of this algorithm (Alg. 3) are represented in Figure 1.

Components found in the Clustering phase Prototypes Regrouping of components into states

1)

Step 1 -Clustering: The first step consists in paving the feature space by first finding M × N components in the data (see filled circles in Fig. 1):

Ω 0 ← find M × N components using a clusterer (20)
This phase can be performed by any clustering approach.

If there are enough data, an EM algorithm can be used by estimating, for example, the parameters of a mixture of M × N Gaussian components. In the presence of imperfect data, a Gustafson-Kessel Fuzzy-C-Means [START_REF] Gustafson | Fuzzy clustering with a fuzzy covariance matrix[END_REF], an Evidential C-Means (ECM) [START_REF] Masson | ECM: An evidential version of the fuzzy c-means algorithm[END_REF] or an evidential EM algorithm [START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF] can be used. One can also use online clustering such as [START_REF] Serir | Evidential evolving gustafssonkessel algorithm for data streams partitioning using belief functions[END_REF].

2)

Step 2 -Regrouping: In probabalistic HMM, a set of states (N ) and a number of components for each state (M ) has to be chosen. Then Baum-Welch algorithm finds the parameters of each component in each state: B ← Baum-Welch algo. (data, M comp., N states) [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF] Regrouping of components into states is made automatically by maximizing likelihood, and a relevant regrouping implies a better recognition of states.

We propose to adapt this algorithm for EvHMM as follows: let M ×N components found by the Clustering phase (Eq. 20), we then need to find N states, each one composed of M components. For that, we propose a procedure called RCGI (Regrouping Components with Geometrial Interaction) described in Algorithm 3. Note that the optimal way is intractable because it requires to consider all possible permutations between components.

We denote Ω 0 the set of M × N components provided by the Clustering phase. The N sets of states are denoted Ω i , i = 1 . . . N such as:

∩ i Ω i = ∅ and ∪ i Ω i = Ω 0 ( 22
)
The cardinality |Ω i | can be different for each state but, for the sake of simplicity, we consider here the same cardinality. RCGI thus fills a M × N association matrix A with:

A(i, j) = 1 if component j is assigned to state i 0 otherwise (23)
a) Initialisation: RCGI first requires one component for each state. This step is critical since components will be added gradually based on this initialisation. We propose the following procedure (Alg. 2):

1) First, compute distances between all components. The result Z = [D(i, j)] is a N ×M triangular square matrix where elements are the distances between components i and j (we here use the Euclidean distance).

D(i, j) ← Distance between comp. i and j (24)

2) Then, find the farthest component from all others:

C 1 = argmax j i D(i, j) (25)
3) The third step consists in finding the farthest component from C 1 :

C 2 = argmax j,j =C1 D(comp. C 1 , j) (26)
4) At this stage, we have two states, each with one component. In order to find the first component for the remaining N -2 states, we consider the distance between C 1 and C 2 and divide it into N -1 segments of equallength. Let denote Ĉi the estimated component for state i = 3 . . . N . Therefore, C i is given by the closest component to Ĉi : In Fig. 1, the result of the initialisation step is represented by the stars on the chosen components.

C i = argmin j,j =C k ,k>i D(comp. Ĉi , j), i = 3 . . . N (
b) Association: A component j in Ω 0 is associated to a state i if the latter is the closest state to j.

A representation of this assignment is depicted by dotted circles in Fig. 1. Since a state can be composed of several components, it is necessary to adapt the distance measure D in to compare a single component (j) to a set of components (composing state i):

j * = argmin j D (component j, state i) A(i, j * ) = 1 (28)
For distribution-based clusterers (such as Gaussian mixtures models), we propose to use the Kullback-Leibler (KL) divergence between both the distribution p j ≡ p(y|j) of data points y in component j and the distribution p i ≡ p(y|i) of data points y in the mixture of components composing state i:

D (j, i) = KL p i || p j (29)
For mixtures of continuous densities, the KL divergence does not have a closed-form but can be estimated by Monte-Carlo sampling. Samples are thus drawn from the mixture associated to p i and given a set of i.i.d. sampled points y 1 . . . y n . . . y Ns , we can approximate the KL by its Monte-Carlo estimate:

KL = 1 N s n log p(y n |i) p(y n |j) -----→ Ns→∞ KL(p i ||p j ) (30)
where we used N s = 1e5 samples.

Algorithm 2 ONE STATE RCGI

Require: Set of components Ω 0 Require: Number of states N {assume the same number of components for each state} Ensure: Find N prototypes: A(i, j * ) = 1 with j * = argmin j D (i, j) {Assign a component to state i} 8:

A(j) = 1, j = 1 . . . |Ω 0 | if component j is a prototype 1: Compute distances between all components ([D(i, j)]) 2: Find the farthest component: C 1 ⇒ A(C 1 ) = 1 3: Find the farthest component from C 1 : C 2 ⇒ A(C 2 ) =
Ω 0 ← Ω 0 -{j * } {Update remaining components} 9:
end while 10: end for and the obtained segmentation is given on Figure 4 after reordering of states according to their norm over components.

Compared to probabilistic HMM, RCGI is deterministic (if the number of samples is sufficient to compute the KL) and thus allows to obtain a stable result while HMM are sensitive to initialisation. Note that RCGI can also be applied on clustering results obtained in HMM.

In signal processing, we believe that RCGI can be useful since the coherence obtained has a real meaning on the signal (for temporal data).

B. Transition estimation

The problem is to estimate belief concerning transitions between states. As in Baum-Welch algorithm, we propose an iterative process described in Algorithm 4 and called ITS (Iterative Transition Specialization).

ITS algorithm starts after RCGI and requires a first estimation of the transition matrix. When there is no prior information on transitions, we use [START_REF] Ramasso | Forward-backward-viterbi procedures in TBM for state sequence analysis using belief functions[END_REF]:

m Ωt×Ωt+1 â0 ∝ T -1 t=1 m Ωt↑Ωt×Ωt+1 b ∩ m Ωt+1↑Ωt×Ωt+1 b (31)
m Ωt↑Ωt×Ωt+1 b (B) = m Ωt b (C) if C × Ω t+1 = B (32)
and 0 otherwise. Eq. 31 is a generalization of HMM transition estimate to belief functions when there is no prior information on transitions. It is also a simplification of Eq. 22 in [START_REF] Ramasso | Forward-backward-viterbi procedures in TBM for state sequence analysis using belief functions[END_REF].

Once the first estimate m â0 has been estimated, the evidential forward algorithm is applied. The resulting α variable is then used in Eq. 31 (instead of m b ) to compute transitions m â1 used in the second iteration. In iteration k, the evidential forward produces the α variable used again in Eq. 31 to compute transitions m âk . This process iterates and ITS stops when the conflict (unlikelihood) converged. The final transition matrix is denoted m â * . As expected [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF], consecutive applications of the forward algorithm provides an evidential transition matrix with high values on singletons and low values on doubt. This effect is due to conjunctive operations embedded in propagations and is increased if we use the smoothed estimate (γ) instead of the filtered estimate (α). In order to solve this problem, we simply take the value of (m â * + m â0 )/2 as the final transition matrix. This provides a consensus between the two transitions.

C. Towards RIL in TSTEN

Previous sections introduced Evidential HMMs. We now consider more complex models that we call TSTEN, standing for Time-Sliced Temporal Evidential Networks (TSTEN), as a generalization of Dynamic Bayesian Network to belief functions. TSTEN are graphical models representing conditional independencies between variables within and across positions in a sequence. As emphasized in [START_REF] Murphy | Dynamic bayesian networks: Representation, inference and learning[END_REF], modelling of timeseries data is natural by directed graphical models, which can capture the fact that time flows forward. Arcs within a timeslice can be directed or undirected, since they model "instantaneous" correlation. We rather use "time-sliced" instead of "dynamic" because the latter often means the graph parameters and structure change over time.

Generalizing probabilistic Representation -Inference -Learning (RIL) is a necessary condition for developing TSTEN.

1) Inference in TSTEN: The RI-problem (Representation and Inference) was treated by Shafer, Shenoy [START_REF] Shenoy | Valuation-based systems: A framework for managing uncertainty in expert systems[END_REF], [START_REF] Shenoy | Axioms for probability and belief function propagation[END_REF] and Smets using Valuation-Based Network and Directed Evidential Network [START_REF] Smets | Beliefs functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF]. To our knowledge, inference and representation were treated in the static case. Their procedures also applies in the temporal case and the first application was proposed in Evidential HMM.

EvHMM is a TSTEN where a time-slice is composed of two nodes: one discrete (X t ) and one continuous (Y t ). The temporal link is represented by an arc from X t and X t+1 , i.e. two discrete nodes across successive slices.

The main particularity of EvHMM is that it considers hidden states X t , that means only Y t is observable and we need to infer X t . Inference tools were formulated in this paper and used for classification and state sequence recognition.

Inference in TSTEN is carried out as follows:

• Within a time-slice: Apply a local propagation scheme 1 to update belief masses on all variables within a time-slice.

• Between time-slices: Apply inference tools proposed in this paper to project and update belief masses on variables linked between two time-slices. • Apply the classification algorithm (Alg. 1) proposed in this paper to classify a sequence.

2) Training in TSTEN:

To our knowledge, the problem of parameter training in evidential networks was not considered in the past, and the same holds for TSTEN. There are three categories of parameters that have to be estimated:

• Transitions between time-slices which are the conditional BBAs of elements in X t given elements in X t-1 , • Conditional BBAs within a time-slice and representing the link between elements in a variable and elements in another connected variable, • Parameters of models for hidden variables.

a) Observable variables in TSTEN: It is the simplest case because when all variables are observable, one can compute distribution of observations. For transitions, one can also use the proposed ITS algorithm.

b) Hidden variables in TSTEN: This case was considered only in EvHMM. In this paper, we proposed an algorithm called RCGI that links observations to hidden states. The same procedure can be applied in more general TSTEN for all hidden variables. Besides, ITS algorithm can be applied for transition estimation.

c) Training all parameters jointly: We proposed two disjoint procedures to estimate the parameters of transitions (ITS) and of observation models (RCGI). However, it should be more adapted to use an algorithm that could estimate transition and models jointly.

These parameters should be chosen such as to minimize the overall conflict given the data, which is equivalent to maximize the overall plausibility. For a TSTEN with parameters θ, we can use the following iterative process:

1) Perform inference (see previous section), 2) Perform classification (Alg. 1), 3) Update parameters θ such as to increase the overall plausibility (Eq. 17) for the next iteration (equivalent to decrease conflict).

VI. A SYNTHESIS OF METHODS FOR DYNAMICAL SYSTEMS ANALYSIS BASED ON BELIEF FUNCTIONS

To our knowledge, the problem of state sequence recognition based on belief functions was first stated by Rombaut et al. [START_REF] Rombaut | State recognition in discrete dynamical systems using Petri nets and Evidence theory[END_REF] in 1999. They used a simple singly-connected tree to represent a sequence of states. The tree is initialised with a vacuous belief function to reflect total ignorance. The belief mass then flows down in the tree until the last state according to transition truthfulness. Sequence classification was done using the last state's plausibility. The main problem of this method is the sensitivity of transitions because they depend on observations which may be noisy.

In 2000, Fouque et al. [START_REF] Fouque | Evidential markovian model for data fusion and unsupervised image classification[END_REF] proposed the first method for image analysis mixing Markovian modelling and belief functions. This is the basis of Pieczynski's work on evidential Markovian models (see [START_REF] Pieczynski | Multisensor triplet markov chains and theory of evidence[END_REF] and references inside). However, the author generally makes probabilistic assumptions. This was also the case in [START_REF] Mohamed | Generalized HMM -part 1: Theoretical frameworks[END_REF] where the authors generalized HMM to fuzzy measures. Although the final model is very close to HMM, the generalization capability is decreased by assumptions which are very similar to HMM's ones (e.g. combinations are made using simple product). Moreover, it is not proved whether belief functions are covered.

In 2003, IDRES system was proposed for driving situation recognition [START_REF] Nigro | IDRES: A rule-based system for driving situation recognition with uncertainty management[END_REF]. The system is dedicated to a physical system and thus is difficult to generalize. In 2005, the paper of Smets on conflict analysis [START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF] is also a good introduction for Markovian modelling with belief functions.

In 2004, Smets and Ristic proposed to study the Kalman filter for joint tracking and classification in belief function framework [START_REF] Ristic | Kalman filters for tracking and classification and the transferable belief model[END_REF]. They conclude that Kalman equations are quite similar to the probabilistic ones but they also showed that belief functions had a better capability to represent implication rules in the classification phase.

The next work in 2007 includes the development of a Temporal Evidential Filter (TEF) [START_REF] Ramasso | State filtering and change detection using TBM conflict[END_REF] which is used for belief functions filtering. This work was then used in [START_REF] Ramasso | Belief scheduler based on model failure detection in the TBM framework. application to human activity recognition[END_REF] (2010) for deterministic state sequence classification. In 2007 was also proposed the first steps in the generalization of HMM to belief functions (EvHMM [START_REF] Ramasso | Forward-backward-viterbi procedures in TBM for state sequence analysis using belief functions[END_REF]) without probabilistic assumption. In [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF] (2009), a formulation is proposed to represent imprecise knowledge on states in the training set used in probabilistic HMM training.

In 2010, an algorithm for Belief State Estimation (BSE) [START_REF] Nassreddine | State estimation using interval analysis and belief-function theory: application to dynamic vehicle localization[END_REF] of continuous state using interval analysis and belief functions is described.

Finally, a first step towards the generalization of inference mechanisms in Dynamic Bayesian Network to belief functions was proposed in [START_REF] Pollard | Bayesian networks vs. evidential networks. an application to convoy detection[END_REF]. However, their proposition is not general and is actually a particular case of EvHMM.

VII. EXPERIMENTS

As an example of RCGI algorithm for classification, we considered the challenge dataset concerning diagnostic and prognostics of machine faults from the first Int. Conf. on Prognostics and Health Management [START_REF] Saxena | Damage propagation modeling for aircraft engine run-to-failure simulation[END_REF]. The dataset is a multiple multivariate time-series (26 variables) with sensor noise. Each time series was from a different engine of the same fleet and each engine started with different degrees of initial wear and manufacturing variation unknown to the user and considered normal. The engine was operating normally at the start and developed a fault at some point. The fault grew in magnitude until system failure.

The first experiment (train FD001.txt) with five preselected features [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF][START_REF] Zhang | An integrated approach to bearing fault diagnostics and prognostics[END_REF][START_REF] Donga | A segmental hidden semi-markov model (hsmm)based diagnostics and prognostics framework and methodology[END_REF][START_REF] Shafer | A mathematical theory of Evidence[END_REF][START_REF] Smets | The transferable belief model[END_REF] was considered. Each time series was manually segmented into four functioning states: normal mode, transition mode, degrading mode and fault mode. The segmentation is available on demand. For each state a HMM and an EvHMM were built using 8 time-series. Testing (classification) was performed on 32 other time series. In RCGI, the clusterer was a mixture of Gaussians (GMM) with adaptive number of components [START_REF] Ververidis | Gaussian mixture modeling by exploiting the mahalanobis distance[END_REF], [START_REF] Figueiredo | Unsupervised learning of finite mixture models[END_REF] where the parameters were estimated using an EM algorithm.

For normal, transition, degrading and fault modes respectively, the results of state detection are given in table I.

RCGI algorithm greatly improved the detection results. When used within HMM, an average improvement of +6% was obtained (lines 1 and 2). The improvement is also important (+10%) when using EvHMM (lines 1 and 3). In comparison, classification using only GMM leads to a global accuracy of 71% (vs. 88%, lines 2 and 5).

Results obtained by EvHMM is explained by RCGI algorithm which was combined with an efficient clustering method where the number of components was set automatically. This number was adaptively computed according to the distribution of the data which depends on the number of data points used in the training set. Therefore, the proposed algorithm is well suited for limited training sets. Line 4, EvHMM was applied with vacuous transitions leading to a satisfying classification accuracy of 87%. Actually, during experiments on this dataset, transitions were shown to have a limited impact on the detection accuracy. This is mainly due to the evidential transitions matrix generated by ITS which were composed of too many parameters (N •2 N ) and thus their influence were limited.

VIII. CONCLUSION

An original review on methods for state sequence recognition based on belief functions was proposed and emphasized the need of a general tool for stochastic state sequence recognition. The generalization to belief functions of inference mechanisms used in HMM was then presented and illustrated. They are the basis of Evidential HMM (EvHMM) which represents a Time-Sliced Temporal Evidential Network (TSTEN).

Training algorithms for EvHMM parameters estimation were then developed. The first algorithm called RCGI (Regrouping Components with Geometrial Interaction) allows to generate belief functions on states. RCGI first performs a clustering step to pave the feature space. Then clusters are gathered into states (using here the Kullback-Leibler divergence). The second algorithm called ITS (Iterative Transition Specialization) allows to estimate transitions. The first results are encouraging on a diagnostics task. In particular, results provided by RCGI are easily interpreted and this algorithm can also be used in probabilistic HMM. The performance of EvHMM for classification was shown on an example and compared with probabilistic HMM.

The proposed methodology is adapted with poor training sets and more experiments are under way to thoroughly validate the approach for general diagnostics and prognostics tasks.

  Ωt+1 a (•|S i ) is the set of conditional plausibilities representing transitions from subsets of states at t and t + 1, and m Ωt+1 b ≡ m Ωt+1 b (•|O t+1 ) is the observed BBA. The BBA m Ωt+1 β ∩ b on Ω t+1 is first computed by the conjunctive combination of the available BBAs at t + 1 (m Ωt+1 β and m Ωt+1 b

Fig. 1 .

 1 Fig. 1. RCGI steps with N = 4 and M = 6. Filled circles are the components, stars represent the first component called prototypes (obtained in the initialisation step), dotted circles are the final regrouping.

27 ) 1 :

 271 Example Let consider the data of Figure 4. It represents a set of N = 4 states, each one being corrupted by a M = 3 components additive noise (different for each state). Ideally, there are 12 components. Assume that the components are characterized by the following center means: µ = [4.2 3.2 2.2 1.2 1.6 2.7 0.7 3.4 3.7 0.8 3.6 2.3]. Thus, criterion (24) gives the following values: D(i, j) = [51.68 22.08 16.48 34.88 24.64 16.28 53.08 26.08 33.88 48.96 31.04 15.96]. Therefore C 1 = 7 (µ 7 = 0.7) and C 2 = 1 (µ 1 = 4.2). Then the segment length is (4.2 -0.7)/3 = 1.1667 thus Ĉ3 = 3.033 and Ĉ4 = 1.8667 leading to C 3 = 2 (with µ 2 = 3.2) and C 4 = 5 (with µ 5 = 1.6). Finally, the first components of each state are 7, 1, 2 and 5.

Fig. 2 .

 2 Fig. 2. Signal to be segmented.

1 4 :

 4 Find N -2 components between C 1 and C 2 as described in the text: assign A(C i ) = 1, i = 3 . . . N Example 2: (continue) RCGI is applied on the data described in the previous example. It finds a set of N = 4 states, with M = 3 components each. The resulting association is [7 10 4] for state 1, [1 9 11] for state 2, [2 8 6] for state 3 and [5 3 12] for state 4. This association is depicted on Figure 3 Algorithm 3 RCGI Require: Set of components Ω 0 {characterized by some pa-rameters} Require: Number of states N {M = |Ω 0 |/N since we assume the same number of components for each state} Ensure: Association matrix A(i, j) = 1 if component j is assigned to state i 1: A(:, 1) ← ONE STATE RCGI(Ω 0 , N) (Alg. 2) {Initialisation, then remove the prototypes from Ω 0 .} 2: for states i = 1 To N do 3: while j A(i, j) < M do 4:for all remaining components j in Ω 0 do 5:Compute the distance D (i, j) between state i and component j {See comments in text} 6:

Fig. 3 .

 3 Fig. 3. Visualisation of regrouping (one line for each state).

Fig. 4 .

 4 Fig. 4. Segmentation after RCGI.

Algorithm 4

 4 Algorithm ITS (Iterative Transition Specialization) Require: Belief given observations {m Ωt b , ∀t = 1 . . . T } Require: The threshold for convergence {e.g. 1e-5} Ensure: Transition estimate m â * 1: logpl old ← -∞ 2: converged ← ∞ 3: m â0 ← Estimation of transitions using observations {First estimate of transitions by Eq. 31} 4: while |converged| > do 5: [α logpl new ] ← Forward propagation {Eq. 14 and 13, Inference process} 6: m â * ← Estimation of transitions using filtered belief estimate {use α in Eq. 31 instead of m b } 7: converged ← logpl newlogpl old {Convergence} 8: logpl old ← logpl new 9: end while m â * ← (m â * + m â0 )/2 {Consensus, avoid low belief on doubt}

Figure 5

 5 Figure 5 depicts the value of the likelihood at each iteration of ITS (given the data of the previous example).

Fig. 5 .

 5 Fig. 5. Evolution of EvHMM's log-plausibility at each iteration of ITS.

  called Dempster normalisation.

Algorithm 1 Algorithm EvHMM Classification Require: model λ = {A e , B e , Π e } and s {Evidential transitions, evidential models generating masses from observations, and evidential prior on the first state. Also s if a generalized cautious rule is used (Sect. III-C).} Ensure: Evidential likelihood L e {Used in classification} Ensure: Evidential α -β -γ -ξ {Filtering/smoothing} 1: for all instants t = 1 to T do 2: α = Forward propagation {Eq. 14} 3: α * = Normalise α {Eq. 5} 4: end for 5: Compute L e {Eq. 13} 6: for all instants t = T to 1 do 7:

  TABLE I EVHMM 1 = GMM+RCGI+ITS, EVHMM 2 = WITH VACUOUS TRANSITIONS, GMM: CLUSTERING ONLY, GA IS THE GLOBAL ACCURACY.

Such as Smets algorithm[START_REF] Smets | Beliefs functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF] which requires less computations than Shafer-Shenoy algorithm but that is more restricted than the latter because limited to directed networks.

ACKNOWLEDGMENT

We thank the French Ministry of Advanced Education and Research for supporting this work.


Mokrane Boudaoud

Yassine Haddab

Ieee Member

Yann Le Gorrec

Philippe Lutz

Effects of environmental noise on the accuracy of millimeter sized grippers in cantilever configuration and active stabilisation

This paper presents a study about the effects of environmental noise on millimeter sized grippers in cantilever configuration. The study is motivated and conducted aiming at assessing the level of accuracy loss when performing micromanipulation/microassembly tasks in noisy environments as well in typical microrobotics laboratories as in industrial locations or operating rooms. Ground motion and acoustic noises within a typical microrobotic laboratory are characterized in the frequency domain and their effects on cantilevers of different lengths are inspected. The relevance of a typical vibration isolation table is evaluated and the effects of low and high acoustic noises are assessed. A modeling of a cantilever with base excitation is thereafter conducted in the state space using finite difference formulation and a stabilization of a disturbed cantilever is obtained at the nanometer level in noisy environments allowing perspectives to high precision micromanipulation tasks in hostile locations.

I. INTRODUCTION

Accurate and high precision micromanipulation tasks are required in a wide range of microrobotics applications such as microassembly [START_REF] Zubir | Development of a Compliant-Based Microgripper for Microassembly[END_REF], force sensing [START_REF] Chu | Lateral nano-Newton forcesensing piezoresistive cantilever for microparticle handling[END_REF] and surgical operations [START_REF] Eisinberg | Microfabricated Instruments for Fetal Cardiac Surgery: Experiments on Haptic Tissue Recognition[END_REF]. In that sense, numerous microgrippers have been previously designed based on actuators endowed with high position resolutions and good deformation/force ratios allowing precise motions of microgrippers arms, such as the one used in our previous work [START_REF] Boudaoud | Modelling of a MEMSbased microgripper: application to dexterous micromanipulation[END_REF]. However, despite high performances of actuators, the vibratory behaviour specific to the arms is considered as the main source of accuracy loss [START_REF] Guoyong | Force-controlled automatic microassembly of tissue engineering scaffolds[END_REF] [6] [START_REF] Weck | Equipment technology for flexible and automated micro-assembly[END_REF] prejudicing wanted performances in a given micromanipulation task. Unwanted vibrations are mostly due to the environmental noise such as ground motion and acoustic noises which can be produced by human activity, operating machines, fans, etc within a given location. Ground motion is often characterized by a complex spectrum consisting of fast and slow motions [START_REF] Chao | Handbook of accelerator physics and engineering[END_REF] [9] [START_REF] Arai | Estimation of Ground Motion Characteristics and Damage Distribution in Golcuk, Turkey, Based on Microtremor Measurements[END_REF]. While slow motions relates on the own activity of the earth which is concentrated below few hertz, it is the cultural noise with frequencies higher than a few hertz that has the potential of affecting flexible structures and especially near their resonant frequencies by acting on clamped parts. Cultural noise relating mainly on operating machines has generally a significant energy from a few hertz up to a few hundred of hertz [START_REF] Chao | Handbook of accelerator physics and engineering[END_REF] and its frequential behavior can vary from one location to another. To deal with performance limitations caused by ground motion, microgrippers are often mounted on vibration isolations M. Boudaoud, Y. Haddab, Y. Le Gorrec and P. Lutz are with the Automatic Control and Micro Mechatronic Systems Department, FEMTO-ST Institute, UFC-ENSMM-UTBM-CNRS, University of Franche-Comté, Besanc ¸on, France. (mokrane.boudaoud, yassine.haddab, legorrec, philippe.lutz)@femto-st.fr tables and mechanical designs are sometimes studied to reduce the low frequency vibrations [START_REF] Anis | Modal analysis of microgrippers used in assembly of MEMS devices[END_REF]. However, acoustic noises are rarely taken into account in micromanipulation tasks although this noise can have an important effect on mechanical structures [START_REF] Bolzon | Study of vibrations and stabilization at the sub-nanometer scale for CLIC final doublets[END_REF] and can be over than 70 dB in typical operating rooms [START_REF] Shapiro | Noise in the operating room[END_REF], while numerous microgrippers are devoted to surgical applications [START_REF] Ku | Design and control of a teleoperated microgripper for microsurgery[END_REF]. In this case, vibration isolation tables can be insufficient and acoustic isolation may be necessary for high precision operations. The study presented in this paper is conducted with the aim of assessing the level of accuracy loss within microgrippers when performing micromanipulation/ microassembly tasks in noisy environments as well in typical microrobotics laboratories as in industrial locations or operating rooms. As starting point, the focus is given to mechanical designs in cantilever configuration with millimeter sized dimensions wich is often encountered on the arms of microgrippers such as in [START_REF] Jain | Micro gripper for micromanipulation using IPMCs (ionic polymer metal composites)[END_REF], the developed microgripper is based on three arms in cantilever configuration (40 mm × 10 mm × 0.2 mm) , also in [START_REF] Rakotondrabe | Quadrilateral Modelling and Robust Control of a Nonlinear Piezoelectric Cantilever[END_REF] a piezoelectric cantilever is used for microassembly tasks with 15 mm length, 2 mm width and 0.3 mm thickness. As such, for the given study, cantilevers of different lengths clamped on the same stiff support have been designed for experiments such as their first flexural resonance is located in low frequencies (few hundred of hertz) where ground motion and acoustic noises should be both relevant as stated in the literature. A frequential characterisation of these noises is then conduced in our laboratory to check precisely about the frequency range where they are significant and their effects on the designed cantilevers are inspected. For this purpose, effects of ground motion are studied in low acoustic noise conditions and the relevance of a vibration isolation table for vibration rejection is inspected. After that, effects of low and high acoustic noises are assessed when the experimental station is located on the vibration isolation table, in which a loudspeaker is used to generate 70 dB acoustic perturbations as in operating rooms for high acoustic noise case. The interest of this approach is to check for each condition, in which frequential domain a stabilisation of the cantilevers is needed aiming at improving position accuracy. A modeling of a cantilever with base excitation is thereafter conducted using the finite difference Fig. 2. Experimental station for noise analysis in a microrobotic laboratory.

approximation with an optimisation of dynamical parameters, leading to the development of a reliable state space model for an active vibration control. Finally, using a piezoelectric stack actuator and a high resolution laser interferometer, a stabilization of the most disturbed cantilever is obtained at the nanometer level while tracking sinusoidal reference in a noisy environment, allowing perspectives to high precision micromanipulation applications in hostile locations.

II. DESCRIPTION OF THE EXPERIMENTAL STATION Starting from a bulk of aluminum, four cantilevers of different lengths (TABLE I) have been machined using a wire processing such as all cantilevers are clamped on the same stiff support (no machined part) (Fig. 2). Vibration measurements are performed using a high resolution (0.01 nm) laser interferometer sensor (SP-120 SIOS Mebtechnik GmbH) covering a frequency range from few hertz up to 1 MHz, while a microphone (1/2" 50mV/Pa, 01dB-metravib) connected on an amplifier (PRE21S, 01dB-Metravib) allowed acoustic noise measurements (3.15 Hz up to 20KHz) . High acoustic noises are generated using a loudspeaker (LD 130 CR08 -ATOHM) and a piezoelectric stack actuator (P-249.20, Physik Instrument GmbH) with 20 KHz resonant frequency is used for the mechanical characterization of the cantilevers through base excitations. For small displacements (less than 50nm), experimental measurements showed that the stack actuator obeys to a linear supply voltage/displacement characteristic with a sensitivity equal to Kact = 1.6nm/V olts.

III. ENVIRONMENTAL NOISE ANALYSIS WITHIN A TYPICAL MICROROBOTIC LABORATORY

A. Ground motion and acoustic noise measurements

Ground motion and acoustic noise have been measured in the microrobotic laboratory (Automatic Control and Micro-Mechatronic Systems Department, Femto-ST institute) during the day when all usual sources of noise have been present (running computers + fan + different amplifiers + experimental station for noise analysis) including low human activity relating only to people working on their stations and speaking together such as no ground motion measurements have been performed when people were walking on the floor. Considering that an important part of the motion of the ground is transmitted to the base of cantilevers, the Frequency (Hz) PSD (m²/Hz)

Ground motion out of vibration isolation table Ground motion on vibration isolation table

Fig. 3. PSD of ground motion within the microrobotic laboratory.

term "ground motion" has been assigned through misuse of language to the vibratory behaviour of the base. Then, the laser interferometer sensor has been used in order to perform horizontal vibration measurements on the base with 25 KHz sampling frequency. Measurements have been performed during one hour, which is sufficient for the characterisation of fast motion [START_REF] Arai | Estimation of Ground Motion Characteristics and Damage Distribution in Golcuk, Turkey, Based on Microtremor Measurements[END_REF]. Moreover, by way of comparison, measurements have been performed on a vibration isolation On the other hand, acoustic noises have been measured during the day when three persons were present within the laboratory (case of low human activity), and secondly twelve persons talking together (not walking) have been added in order to check about the increase of acoustic noise level in high human activity conditions and also to assess whether the level of acoustic noise produced by humans can have a significant effect on the cantilevers. Each acoustic measurement has been performed during 60 seconds with 5208,33 Hz sampling frequency. Power and amplitude spectral densities (PSDs and ASDS) of noises have been averaged 128 times using the Welch method which is often recommended for the case of noisy signals [START_REF] Welch | The Use of Fast Fourier Transform for the Estimation of Power Spectra: A Method Based on Time Averaging Over Short, Modified Periodograms[END_REF]. As shown in (Fig. 3), the effectiveness of the vibration isolation table is clearly observed, such as on this table only the PSD of the internal laser interferometer noise is detected due to its resolution. Ground motion is in this case less than 0.01 nm. However, out of the vibration isolation table, the PSD of ground motion generally decreases with increasing the frequency and vanishes beyond 350 Hz (below the resolution of the laser interferometer). The measured ground motion in this case is due to the cultural noise. For this reason and in order to keep the same frequential behavior, effects of ground motion are thereafter analysed by keeping the same sources of perturbations. On the other hand, through the frequential behavior of acoustic noises (Fig. 4), it is possible to observe that the threshold of audibility (0 dB) is reached at 500 Hz in low human activity, while it is about 3 KHz in high human activity conditions. human speech can then cause an important increase of acoustic noise which is nevertheless the most significant below 1 KHz in high human activity.

B. Effect of acoustic noise and ground motion on the cantilever beams within the microrobotic laboratory

Vibration measurements are performed at the free end of each cantilever to check about the effect of the environmental noise in the previous studied conditions. In this case, a comparison between the vibratory behaviour of the cantilevers on and out of the vibration isolation table has been conducted with low human activity (Fig. 5), (Fig. 6).

After that, measurements are only performed on the vibration isolation table (reducing the motion of the ground) in and high human activity conditions for the analysis of the effect of acoustic noises. Moreover, in order to assess about the effects of acoustic noises which can be found in typical operating rooms, vibrations of the cantilevers have been also measured on the vibration isolation table while the loudspeaker was generating 70 dB sinusoidal acoustic noise exciting the first resonance of each cantilever.

)UHTXHQF\ +] '6$ Pð+] &DQWLOHYHU &DQWLOHYHU &DQWLOHYHU &DQWLOHYHU +] +] +] +]
Fig. 6. PSD of cantilevers vibrations on the vibration isolation table within the microrobotic laboratory.

In all computed PSDs, only the first flexural resonance of each cantilever has been clearly observed, other resonances which are located above 1 KHz were drowned in the interferometer noise. For this reason, and in order to get displacement values around the significant resonances, integrated RMS displacement have been extracted from each PSD in ∆f = f2 -f1 = 50Hz bandwidth around first resonance where the effect of the environmental noise is the most significant. This was conducted using the integrated RMS method such as [START_REF] Peter | Understanding and Measuring Noise Sources in Vibration Isolation Systems[END_REF] :

RM Sint(f1, f2) = f 2 f 1 P SD(f ).∆f (1)
In this study, only RMS displacements are presented (TA-BLE II). Note that the maximum displacement is higher than the RMS one. In this case, nanometer RMS displacements have then been measured at the free end of each cantilever due to the environmental perturbations which may represent a limitation if nanometer accuracy is required in a given micromanipulation task. Moreover, as it could be expected, the longer are the cantilevers, the more is the effect of environmental noise, while long cantilevers are more suitable for large displacements. The vibration isolation table is then important for high precision operations until the flexural resonance of the cantilevers is below frequencies neighbouring 350 Hz (see the case of cantilever 4). However due to other origin of noises such as acoustic ones, the given table may be not enough. Indeed, with the mere increase of the number of people talking in the laboratory, the RMS displacement of all cantilevers increased reaching ones measured out of this table in low human activity conditions. Also, vibrations reaching the micrometer level are observed for cantilevers 1 and 2 with the action of the loadspeaker (70 dB). In addition Consider the partial differential equation of Euler-Bernoulli, describing the vibratory behaviour v(x, t) of a beam subject to an applied force F (x, t) per unit length :

E.I. ∂ 4 v(x, t) ∂x 4 + δ. ∂v(x, t) ∂t + ρ.S. ∂ 2 v(x, t) ∂t 2 = F (x, t) (2)
Where E is the Young modulus, I is the area moment of inertia about z axis, δ is the damping factor, ρ is the mass density and S defines the area of the transverse section. In this study, partial derivatives in spatial dimension are approximated with the central finite difference scheme, using N grid points (nodes) separated by a length of h on the beam (Fig. 7) where v(xn) designates the deflexion of the beam at a location n × h. For the cantilever case with a base excitation expressed by the variable b(t), the boundary conditions at both ends of the flexible structure are defined as [START_REF] Ghosh | Vibration of a cantilever beam on a composite support with base excitation[END_REF]:

     v(x0, t) = b(t) = h 4 E.I .F (t) v (x0, t) = 0 v (x N , t) = (x N , t) = 0
The partial differential equation ( 2) can be converted into state space representation, for which the input of the model is granted to the base motion while the output relates to the displacement of the cantilever free end, such as :

Ẋ(t) = A.X(t) + B.b(t) v(x N , t) = C.X(t) X = V V T , A = 0 N ×N I N -(ρ.S.I N ) -1 . E.I h 4 .(deriv4) -(ρ.S.I N ) -1 .δ.I N , B = 0 N ×1 (ρ.S.I N ) -1 .M f , C = 0 1×(N -1) 1 0 1×N A ∈ 2N ×2N , B ∈ 2N ×1 and C ∈ 1×2N .
I N ∈ R N ×N is the identity matrix

The load matrix M f and the fourth derivative matrix [derive 4] are derived from finite difference formulation with a respect of the boundary conditions, such as :

M f = E.I h 4 .(-6, 4, -1, 0, . . . , 0) T [derive4] =                0 -8 1 0 • • • 0 0 7 -4 1 0 • • • 0 1 -4 6 -4 1 0 • • • 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 1 -4 6 -4 1 0 0 • • • 0 1 -4 6 -4 1 0 • • • 0 1 -4 5 -2 0 • • • 0 2 -4 2               
The developed model is only an approximation of the dynamics of the actual system, theoretical approach must be then compared with experiments and especially for the damping around the first flexural resonance. For further details about finite difference formulations, the reader can refer to [START_REF]Analysis of beams on elastic foundations using finite difference theory[END_REF].

B. Damping formulation and numeric model validation

According to N = 512 grid points in the discretized scheme, the damping matrix has been computed using Lord Rayleigh's hypothesis [START_REF] Rayleigh | Theory of Sound[END_REF], for which :

δ.I N = α.( E.I h 4 .[derive4]) + β.(ρ.S.I N ) (3)
Weighting parameters α and β can be extracted by defining damping ratios of two resonant modes [START_REF] Rayleigh | Theory of Sound[END_REF]. However, in our study we have chosen to perform an optimization of weighting parameters with a least squares identification method (Levenberg-Marquardt algorithm) using experimental data. Moreover, in order to get through the model a first resonant frequency as close as the experimental one, the Young modulus has been also used as a parameter to be optimized using its theoretical value E = 67GP a as initialisation. The mass density in this case has been fixed at ρ = 2900Kg/m 2 . Using the piezoelectric stack actuator fixed near the clamped part of the cantilever 1, a 1 Volts step excitation has been applied and the corresponding free end response has been used for parameters optimization (Fig. 7). Thus, optimal parameters leading to a minimum value of error between the output of the model and the experimental data have then been defined as : E = 67.15GP a, α = 2.31.10 -7 and β = 1.3572. For model validation, the measured ground motion remaining out of the vibration isolation table (Fig. 3) with low human activity has been used as an input signal to the numerical model and the output which relate to the vibrations of Nth node of the discretized cantilever (free end) has been extracted to compute PSD. Results are presented in (Fig. 8) through which the effectiveness of the model can be observed. An active controller for vibration rejection can be designed based on the developed model, aiming at improving the accuracy of the cantilever in the nanometer level.

V. ACTIVE STABILIZATION OF THE CANTILEVER 1 SUBJECT TO NOISE DISTURBANCES

In addition to the vibration isolation table, a stabilization of the cantilever 1 free end position at the nanometer level is discussed through active noise control. An optimal linear quadratic LQ discret controller is suggested.

A. Discrete state space model for active control

Starting from the previous designed model containing 1024 states, an order reduction has been performed for the control part. Based on implicit balancing techniques to compute the reduced-order approximation [START_REF] Varga | Balancing-Free Square-Root Algorithm for Computing Singular Perturbation Approximations[END_REF], a forth order model has been retained, and for 10 KHz sampling frequency, the discrete form of the state space model is given as :

X d (k + 1) = A d .X d (k) + B d .b d (k) v d (x N , k) = C d .X d (k) A d =    0.

B. Optimal controller design and real time implementation

The piezoelectric stack actuator has been used to generate base excitations following the control low and aiming at counteracting cantilever free end vibrations which are measured in real time by the laser interferometer. The optimal controller is calculated on the basis of the reduced state space model in such a way that the feedback law

U d (k) = b d (k).K -1 act = -Kc.X d (k) minimizes the performance criteria J(k) in which Q and R are positive definite matrices. J(k) = ∞ i=k X T d (i).Q.X d (i) + U T d (i).R.U d (i). (4)
For a discrete computation of the optimal controller :

Kc = (R + (B d .Kact) T .Pc.B d .Kact) -1 .(B d .Kact) T .Pc.A d (5)
Pc is the solution of Riccati equation and can be calculated from matlab software using dare function for which weighting parameters R and Q must be beforehand selected. Moreover, a conventional Luenberger observer has been added allowing the estimation of the state variable X de (k) such as :

X de (k + 1) = F d .X de (k) + B d .Kact.U d (k) + Ko.v d (x N , k) (6)
Where

F d = (A d -Ko.C d ),
and Ko is the gain of the observer used such as the discrete error e d (k) = X d (k) -X de (k) converge asymptotically to zero with a dynamic higher than the one of the closed loop system. As such Ko has been chosen such as the discrete error converge to zero with a response time ten times smaller than the one of the closed loop system, which resulted : For vibration rejection, weighting parameters of the optimal criterion have been selected experimentally leading to : R = 10 -9 and Q = diag(10 9 , 1, 10 9 , 1)

Thus : Kc = 10 8 . 3.1737 5.2338 -6.0746 -0.6704 The control algorithm has been developed using the MAT-LAB/Simulink software and implemented in real time with a dSPACE (RTI1104) control board running at 10 KHz sampling frequency. Experimental results are presented in (Fig. 10 (a)) for vibrations rejection when the cantilever 1 is subject to 70 dB acoustic noise, and in (Fig. 10 (b)) in high human activity condition. Moreover in (Fig. 11), it possible to observe the improvement of the cantilever accuracy while tracking 15 nm sinusoidal reference with 1 Hz frequency in high human acoustic noise. In this paper, an inspection about the effects of environmental noise on millimeter sized cantilevers which may represent end effectors of micromanipulators have been performed with the aim of assessing the level of accuracy loss when working in noisy environments. Ground motion and acoustic noises within a typical microrobotics laboratory have been studied and characterized in the frequency domain. The vibration isolation table proved that it was not sufficient for high position accuracy when using microgrippers with low resonant frequencies (less than 1 KHz) and especially in the case of acoustic perturbations even produced by humans. Moreover, vibrations reaching the micrometer level have been observed in the case of operating rooms conditions. In this case, an optimal active vibration controller has been proposed to ensure a stabilisation of the most disturbed cantilever at the nanometer level in presence of acoustic perturbations. The effectiveness of the controller has been verified experimentally in the case of high human activity condition and while disturbing the cantilever with 70 dB acoustic noise leading to interesting perspective for high precision micromanipulation tasks in harsh environments.

Fig. 1 .

 1 Fig. 1. Simplified scheme of a microgripper made up of two arms in cantilever configuration subject to environmental noise.

Fig. 4 .

 4 Fig. 4. ASD of acoustic noises within the microrobotic laboratory.

Fig. 5 .

 5 Fig. 5. PSD of cantilevers vibrations out of the vibration isolation table within the microrobotic laboratory.

Fig. 7 .

 7 Fig. 7. Spatial discretization of a cantilever beam and optimal estimation of mechanical parameters.

Fig. 8 .

 8 Fig. 8. PSD of cantilever 1 vibrations subject to ground motion

Fig. 9 .

 9 Fig. 9. Block diagram of the closed loop control system.

Ko = [ 8 .

 8 3573 21.6619 7.3919 9.2190 ] T

Fig. 10 .

 10 Fig. 10. Active control of cantilever 1 subject to 70 dB acoustic noise disturbance (a) and in high human activity conditions (b).

Fig. 11 .

 11 Fig. 11. Active control of cantilever 1 while tracking 15 nm sinusoidal reference at 1 Hz in high human activity conditions

TABLE II EFFECT

 II OF THE ENVIRONMENTAL NOISE ON THE ALUMINUM CANTILEVERS : RMS DISPLACEMENT AT CANTILEVERS FREE END

		cantilever 1 cantilever 2 cantilever 3 cantilever 4
	On the vibration isolation table with low human activity	7.2 nm	0.9 nm	0.45 nm	0.1 nm
	On the vibration isolation table with high human activity	123.8 nm	20 nm	6 nm	0.5 nm
	On the vibration isolation table with 70 dB acoustic disturbance (loadspeaker)	1.8 µm	0.82 µm	200 nm	85 nm
	Out of the vibration isolation table with low human activity	112.8 nm	19.1 nm	5 nm	0.4 nm
	to the vibration isolation table, a stabilisation of cantilevers
	position may be necessarily to increase position accuracy and
	especially in the case of harsh environments. In that sense,
	the next section deals with a modelling of a cantilever with
	base excitation allowing the development of a reliable state
	space model for an active stabilisation of tip displacements.
	In this paper, modelling and control are treated only in the
	case of cantilever 1. Nevertheless, the same work can be
	done on other cantilevers.
	IV. DYNAMIC MODELLING OF A CANTILEVER WITH BASE
	EXCITATION
	A. Finite difference formulation of the Euler-Bernoulli can-
	tilever and state space representation

  Moreover, since the actuator is characterized by a high resonant frequency comparing to the one specific to the cantilever, its dynamic has been neglected in the feedback control design, such as only the sensitivity Kact (static case) is considered in the model.

							Acoustic disturbance
							Base
						Ref = 0 V	+	Ud (k)	bd(k)	Laser	vd(xN,k)
							interferometer
							State observer
							dSPACE
							Kc
							Xde(k)
		9940	0.1088	0	0	
		-0.1088 0.9940 0 0	0 0.7753	0 0.6306	 ,
		0	0	-0.6306 0.7753
	B d =	0.0114 0.1847	-0.4693 0.1670 T ,
	C d =	0.6705	-0.0048	-0.0010	-0.2438 .

VII. ACKNOWLEDGMENTS

The authors would like to thank GUIBERT David for cantilevers fabrication.