Keywords: systèmes hybrides dynamiques, contraintes continues, monades

Contrôler des contracteurs avec des monades pour les systémes hybrides dynamiques Résumé : L'élaboration de sytèmes autonomes est le résultat d'interactions entre différents domaines: réseau de capteurs, robotique, optimisation, raisonnement automatique, etc. Cet article, ancré dans cette philosophie pluridisciplinaire, montre une connexion entre les systèmes hybrides dynamiques, la propagation de contraintes sur intervalles et la programmation fonctionnelle. Plus précisément, il montre comment concevoir un programme monadique en Haskell pour contrôler les contracteurs (propagateurs de contraintes) permettant l'estimation d'état de systèmes dynamiques multi-modéles (hybrides), sujets à des mesures partielles et incertaines. L'exemple de système pris ici est un ascenseur qui peut monter, descendre ou être stopé. L'altitude est mesurée directement et le problème d'estimation est simplement de suivre son mouvement. L'objectif de la bibliothéque Haskell est d'offrir un cadre à la fois flexible et de haut niveau pour construire des stratégies de propagation basées sur les connaissances ou les pré-requis de l'utilisateur.

Introduction

Many real-life systems are continuous by nature but controlled by discrete inputs (switches, valves, digital devices). The typical example is a gas burner with a boolean state (leaking/not leaking) and continuous variables representing timers or quantity of leaked/stored gas.

In these systems, two kinds of dynamics are thus interacting: the continuous one, governed by physics laws, and the discrete one, unpredictable or subject to randomness. These systems are usually referred to as hybrid systems [START_REF] Grossman | Hybrid Systems[END_REF]. One problem with hybrid systems is called observation, that is, estimating the system state from both the knowledge of its dynamics and measurements supplied by sensors.

This paper proposes a first constraint-based approach for the state estimation of hybrid systems, i.e., observable dynamical systems subject to configuration changes. A simple example of an elevator with elastic cable is used all along the paper to illustrate the concepts.

Estimation is made by contracting (filtering) domains with respect to the physics equation in a branch & bound process where branching are choices in the set of possible configurations.

To be controlled in a suitable way, constraint propagation requires in this context different levels of abstraction. We will identify three of them; basically, the first corresponding to the discrete events, the second to the continuous dynamics and the last to the integration of measurements. Each level has its own strategy and the solver is obtained as a composition of them.

Therefore, the goal is to generate a dedicated solver by composing contractor strategies acting at different levels. Programming this with an imperative language would clearly be very tedious and doomed to result in a poorly maintainable software. Our contribution is a framework written in a functional language, Haskell, where the power of monads is used to properly address the required composability. This paper is not about interval computations but about how to control them in a specific (but significant) context: hybrid dynamical systems. For that reason, the Haskell program itself does not perform numerical computations. The job is left to an interval constraint library, the details of which being not relevant for this paper. The Haskell program solely requires the interface of each operation to match the definition of contractor (see below).

The interval library used for our experiments was Ibex [START_REF] Chabert | IBEX[END_REF], but the above requirement on the interface is so simple that any other library could be easily plugged as well. This makes our approach generic.

In Section 1.1, we briefly review the different existing approaches for hybrid systems and point out the benefits of the constraint paradigm in this area. In Section 1.2, we introduce how contractors (or propagators) are used so far in dynamical systems. We motivate then why building an upper layer on top of contractors is necessary to tackle hybrid systems and why Haskell is a good choice for this aim. For simplicity, the paper focuses then on a particular example: the tracking of an elevator and the expected features of the Haskell framework, in regard to this application, are listed in §1. [START_REF] Chabert | Contractor Programming[END_REF].

The technical contribution of the paper is in Section 2. All the features are implemented in Haskell and the results obtained are shown graphically. The Haskell implementation is detailled in Section 3.

RR n°7451

Perspectives of this work are finally discussed in a conclusion.

Hybrid Systems

Hybrid systems in the literature are often modeled by hybrid automata where vertices represent configurations (with associated dynamics law) and transitions configuration switches. These transitions are tagged with explicit constraints, making the system deterministic. Formal verification methods exist typically to check safety properties (reachability analysis) of such systems [START_REF] Guéguen | On the Formal Verification of Hybrid Systems[END_REF] [START_REF] Balluchi | Ariadne: a Framework for Reachability Analysis of Hybrid Automata[END_REF]. Estimation can be achieved by tuning solvers dedicated to differential equations like VNode [START_REF] Nedialkov | Validated Solutions of Initial Value Problems for Ordinary ifferential Equations[END_REF] since hybrid automata are not far different from piecewise EDOs. Note that solvers for global optimization (e.g., Baron [START_REF] Sahinidis | Branch-And-Reduce Optimization Navigator[END_REF]) cannot be employed in dynamical systems because the number of variables resulting from time discretization is too big, even with finite degrees of freedom.

Hybrid automata do not integrate observability (measurements) nor the fact that transitions may depend on unpredictable events (obstacles, etc.). For nondeterministic systems interacting with the environment, estimation can be made in the setting of Markov decision processes [START_REF] Altman | Asymptotic Optimization of a Nonlinear Hybrid System Governed by a Markov Decision Process[END_REF]. In this case, the measurement noise is modeled explicitly (e.g., by a Gaussian distribution) and transition have some associated probability. Classical Bayesian observers (e.g., Kalman filter) can then be adapted to manage the possible transitions in the prediction and update of state distributions.

The probabilistic approach has fundamental advantages: uncertainties are more finely represented by a probability than by two simple bounds. Propagation of uncertainties is therefore more informative. This is blatant if measurements are potentially very inaccurate but with a small deviation and if the system behavior is poorly constrained. Under these conditions, intervals can get quickly arbitrary large, i.e., irrelevant, whereas probabilities supply expected values with good confidence.

However, distributions are not compatible with constraint reasoning and backtracking schemes: they can only be propagated safely with linear constraints and cannot be bisected anyway. On the contrary, intervals allow to integrate external constraints that typically arise when the system has a perception of the environment. An example is a robot detecting objects that have only a fixed number of occurrences. This knowledge can be integrated in the estimation process as a global constraint [START_REF] Chabert | A Constraint on the Number of Distinct Vectors with Application to Localization[END_REF], providing significant contraction. Intervals also supply validated solutions, including with nonlinear equations.

Contractors

The concept of contractor in interval constraints (i.e., constraints over the reals) is similar to the concept of propagator with discrete domains. We first give the definition of a contractor and then show the main existing variants. Contractors for dynamical systems will be our base ingredient afterwards.

The following notations will be used. All the unknowns are real and have their domains represented by intervals. The set of real intervals is denoted by IR. A vector of intervals in IR n is called a box. Intervals and boxes are represented by bracketed symbols, e.g., [x].

Contractor A contractor is an operator C : R n → R n such that 1 ∀[x] ∈ IR n , C([x]) ⊆ [x].

Contractors in classical CSPs.

Interval constraints have been successfully used in global optimization; especially for finding guaranteed solutions of nonlinear equations since this problem fits in well with the framework of CSP (Constraint Satisfaction Problems). The problem is to find the set of vectors x such that f (x) = 0, where f : R n → R m .

(

) 1
To solve (1), contractors have been developed to satisfy

∀[x] ∈ IR n , ∀x ∈ [x], (f (x) = 0) =⇒ x ∈ C([x]),
that is, all the values removed from [x] are not solutions. A survey of techniques used for building contractors is given in [START_REF] Neumaier | Complete Search in Continuous Global Optimization and Constraint Satisfaction[END_REF]. From the language perspective, a formalism to build complex contractors from basic ones is proposed in [START_REF] Chabert | Contractor Programming[END_REF] through the concept of contractor programming. As an example, a complex contractor can encapsulate a fine control on the constraint processing order. Solving (1) is performed then by a "branch & contract" process. A search loop, or paver, is therefore easy to supply. Note that, once the branching heuristic is set up, one can decide precisely the form under which the output has to be produced, simply by programming contractors in a suitable way [START_REF] Chabert | Contractor Programming[END_REF].

Hence, there is not much a need for controlling contractors apart from choosing the branching heuristic (i.e., how to select the next current box and how to bisect it). Our point is that such a unique all-in-one algorithm is unlikely to exist for hybrid dynamical systems.

Dynamical Systems.

The potential of interval constraints is far to be restricted to optimization-like problems. Contractors are also successfully employed for calculating validated enclosures of the solutions of nonlinear ordinary differential equations [START_REF] Nedialkov | Validated Solutions of Initial Value Problems for Ordinary ifferential Equations[END_REF]. The approach is of great interest including for equations involving input vectors and measurement vectors, that is, for systems studied in automation. The main application is the state estimation of nonlinear dynamical systems [START_REF] Jaulin | Interval Constraint Propagation with Application to Bounded-Error Estimation[END_REF]. We will not consider input vectors in the sequel. Under this restriction, the problem is to characterize in a time window [t 0 , t N ] the set of functions x : [t 0 , t N ] → R n such that:

x(t 0 ) = x 0 and ∀t ∈ [t 0 , t N ] ẋ(t) = f (x(t)) y(t) = g(x(t)) (2)
where x 0 is the initial state and y(t) the observation. We shall consider henceforth a discretization (t 0 , t 1 , . . . , t N ) of [t 0 , t N ] with a fixed time step δ t = t it i-1 , ∀i > 0. Measurements usually only provide imprecise values of y(t) for t in a subset of the t i 's.

Definition (Model-compatibility). Given a motion model, i.e., a function f , a couple (x i-1 , x i ) is said to be f -compatible if there exists a trajectory z : [0,

δ t ] → R n such that z(0) = x i-1 , z(δ t ) = x i and ż(t) = f (z(t)) for all t ∈ [0, δ t ].
Remark. Since f does not depend on t (the system is autonomous), we see that model-compatibility between states at two successive instants does not actually depend on the instants (i.e., the subscript i) but only on the states themselves. This will have consequences further.

Similarly, we will say that x i is compatible with the i th measurement if either there is no measurement at t = t i or g(x i ) ∈ ỹi ± δ i , where ỹi stands for the measurement value (got from the sensors) and δ i a bound on the measurement error. If we set [y] i := ỹi ± δ i and [y] i := (-∞, +∞) in case of unavailable measurement, we see that, at all events, g(x) ∈ [y] i .

In this context, we usually resort to 1. a model contractor M that takes as input a (2×n

)-box ([x] i-1 , [x] i ) and yields a subbox ([x] ′ i-1 , [x] ′ i ) such that all model-compatible couples (x i-1 , x i ) of [x] i-1 ×[x] i belong to [x] ′ i-1 × [x] ′ i . 2. a measurement contractor M µ i that takes as input a box [x] i and yields a box [x] ′
i such that all the values consistent with the i th measurement, if any, are kept.

model-compatible couples

[x] ′ i [x]i [x] ′′ i [x]i-1 [x] ′ i-1 [x]i-2 measure-compatible values z ( t ) Figure 1: Contractors in dynamical systems. The box [x] i is contracted by the model to [x] ′
i .The latter is guaranteed to contain all the extremities z(δ t ) (marked with black circles) of the trajectories z(t) obeying the differential equation and whose other extremity z(0

) is inside [x] i-1 . The box [x] ′ i can be con- tracted in turn thanks to a measurement to obtain [x] ′′ i .
This is illustrated in Figure 1. Examples of recent methods to build model contractors are in [START_REF] Ramdani | A Hybrid Bounding Method for Computing an Over-Approximation for the Reachable Space of Uncertain Nonlinear Systems[END_REF]. To solve (2), we can still use a all-in-one algorithm that basically calculate the fix-point of model contractors and measurement contractors (bisection is prohibited in general). Note, however, that a fix-point is dramatically time-consuming for a large number of time steps.

Motivating Example

The example chosen in this paper is an elevator that can either be moving upward (up), downward (down) or stopped (stop), the latter resulting into oscillations around the halting position. In this example, the state x has three components: the altitude of the elevator, its speed and the cable stretch. However, we will only observe the first one, the altitude. Whether the elevator example corresponds to a real-life hybrid system or not does not matter.

The goal is to track the elevator, i.e., to calculate its altitude with time, from noisy and partial measurements. Of course, configuration changes are unknown. Model contractors are used to make consistent two consecutive positions with respect to a configuration of the elevator (either up, down or stop) at the corresponding time. So there is a different contractor for each configuration, and one must decide which contractors are enforced in turn to obtain an overall feasible trajectory, that is, as thin as possible and consistent with all the measurements. Let us call this a strategy. Of course, a choice point is necessary when two different models are compatible with measurements (either for real or apparently) at a given time step. So a strategy acts as a solver. The less backtracks, the better the strategy.

Contribution of the Paper

This paper is not intended to give a turn-key strategy for the state estimation of the elevator. This would be of little interest because the success of a strategy strongly depends on the problem. A good strategy for our toy example may not be applicable elsewhere.

The purpose is to describe a framework for the development of strategies. More precisely, the program in the next section can be viewed as a kit to build your own strategy.

The main qualities of our framework are modularity and expressiveness. First, it gives the ability to develop a strategy by working at different levels. Second, each level can be programed in a flexible and independent way. There are three levels, each corresponding to a different abstraction of the problem.

level 1.

The behavior of the system is often constrained globally. For instance, one may know that the scenario is a sequence of up, followed by a sequence of stop and a sequence of down (but not the times when switches occur). The system may also have some latency: once a switch occurs, the new model remains valid for a lapse of time. This type of knowledge is modeled with an automaton and Level 1 refers to the integration of such automata into strategies.

1.4.2 level 2.
Once a sequence of models is enforced, one may decide to propagate contractors in different ways. Model and measurement contractors can be interleaved in a specific order, some contractors can be called twice, etc. Level 2 refers to the choices made in a strategy for calculating an enclosure of the propagation fix-point.

level 3.

This level contains the structure and functions at the core of the search process: choice points, fails and backtracks.

Our program will be illustrated on the elevator tracking example. The target strategy will have to be based on the following requirements, one for each level:

1.4.4 req 1.
It is known that the elevator starts by up and necessarily stops between the configurations up and down (in this order and in the other way around). Furthermore, each model has a latency of 4 time steps.

req 2.

When one estimation is sharpened by a measurement, all the estimations at the previous time steps have to be smoothed accordingly.

req 3.

When two models can be applied, the one that leads to an estimation that maximizes likelihood with respect to the measurement should be tried first.

Do we have to extend contractor programming to achieve this goal? Probably not. The purpose of contractor programming is to build complex contractors from basic ones, not to control them. This is precisely why branching heuristics were overlooked in [START_REF] Chabert | Contractor Programming[END_REF]. Branching is a matter of controlling contractors, as said above. Furthermore, controlling is more complex in the case of hybrid dynamical systems and involves user knowledge in a similar way as business rules. It cannot be reduced to the parameterization of a monolithic algorithm.

A Good Candidate: Haskell

We have decided to program our framework in Haskell [START_REF]Haskell 98 Language and Libraries -The Revised Report[END_REF]. Haskell is a functional, lazy, higher-order and typed programming language. The main implementation of Haskell, GHC relies on the C compiler gcc which makes it simple to link an Haskell program and a C program (such as Ibex). It has recently been successfully used to control discrete constraint solvers such as Gecode [START_REF] Schrijvers | Monadic Constraint Programming[END_REF][START_REF] Wuille | Monadic Constraint Programming with Gecode[END_REF]. Higher-order and lazy features of Haskell makes it possible to define domain specific languages as sets of combinators. For instance, the monadic parser library [START_REF] Hutton | Monadic Parsing in Haskell[END_REF] provides BNF-like operators. They enable users to program backtracking parsers simply by defining grammars. This library strongly inspired us to define (backtracking) controllers as grammars. In the next section, we present our framework.

Controlling Contractors in Haskell

Let us first restate the problem. A hidden command sequence (say, up-up-downstop-etc.) or scenario has given a trajectory to the elevator. At some moments, the state of the elevator can be estimated from measurements. There may be different scenario compatible with these measurements and our goal is to find one sequence, i.e., one of the solutions. This solution is not necessarily the hidden sequence.

The problem can formally be cast into a CSP as follows. There are two sets of variables: X = {x 0 , . . . , x N } and U = {u 1 , . . . , u N }. For all time step, x i is the i th state vector and u i the command, that is, the model which applies between t i-1 and t i . For all i, domains for x i and u i are [x] i = (-∞, +∞) 3 and {up, stop, down} respectively.

Let us denote c µ i the constraint y i = g(x i ) and c UP i , c STOP i and c DOWN i the constraints that (x i-1 , x i ) are compatible with up, stop and down respectively (see the definition of model-compatibility above).

The set of constraints is therefore:

(c µ 0 ∧ . . . c µ N )∧ (c UP 1 ∧ ¬c STOP 1 ∧ ¬c DOWN 1 ⇐⇒ u 1 = up) ∧ . . . . . . ∧ (c DOWN N ∧ ¬c UP N ∧ ¬c STOP N ⇐⇒ u N = down).
It makes no sense to look for solutions in terms of (X , U ) since (1) the problem is extremely under-constrained (partial and noisy measurements) and ( 2) we cannot check satisfiability for model constraints (only contraction is possible). The goal is rather to find solutions in terms of U only. A solution is an instantiation of U such that propagation leads to a nonempty set.

An alternative way of proceeding is to consider the set of 3 N CSP:

(c µ 0 ∧ . . . c µ N ) ∧ (c UP 1 ∧ c UP 2 ∧ . . . ∧ c UP N ), . . . , . . . , (c µ 0 ∧ . . . c µ N ) ∧ (c DOWN 1 ∧ c DOWN 2 ∧ . . . ∧ c DOWN N )
, each scenario being identified to a unique scenario U . The idea is then to find the first consistent scenario.

Such a generate and test solution avoids disjunctions or reified constraints. However the number of scenarios is unacceptable. There are many scenarios that should be discarded thanks to a priori knowledge on the system behavior (as said in §1.4). Moreover, there are many redundant computations: propagation for two scenarios sharing a subchain of constraints should be factorized.

A Search Tree with Incremental Propagation

Let us take an example. We know that the elevator starts by moving up and keeps moving up until it is stopped. It remains then stopped indefinitely. A grammar modeling this behavior is

(R 1 ) U → up U (R 2 ) U → up S (R 3 ) S → stop S
The basic idea is to build a search tree that generates all the words accepted by the automaton (see Figure 2) and to remove the inconsistent ones as soon as possible.

A node at depth i in this tree is therefore the i th terminal that can be read and corresponds to a choice, that is, the instantiation of u i . An edge between u i and u i+1 represents the rule applied. Propagation is performed along the way: each time a choice is made (a new node u i appears in the tree), this choice is propagated by adding a new contractor on-the-fly. Of course, the effect of the second-level sequence basically only results from tradeoffs between efficiency and accuracy. It is not directly related to the system. Both levels should be programed in a complete separate way.

First-Level Strategy

As said in the remark of §1.2, time is a free variable in our system. This means that the user knowledge makes never appear time explicitly. Take the example of switches with latency (cf. Req 1). The strategy tells that when the system switches from up to stop then stop is valid for 4 additional time steps. The subscript i is never specified. Furthermore, first-level sequences like (5) are synchronized with the clock so that time could be made implicit.

The idea is to drop subscripts and to let first-level contractors manage the ticks (clock increments). The first-level sequence (5) becomes in the syntax of our framework:

stepUp >> stepUp >> stepStop.

A first-level contraction simply applies the sequence of second-level contractors and increments the clock (see next section). The nice point is that, under the form (6), a scenario is both an operational program (that check consistency of the scenario) and a word of Σ * , where Σ is {up, stop, down}. This will give us the ability to generate scenarios from grammars (that is, to build our solver) in the fashion of parsers.

But instead of building a parser for these grammars that would generate solvers with obscure code, we shall use monads (cf. §2.5), a very powerful feature of functional languages that allows to build executable grammars like [START_REF] Grossman | Hybrid Systems[END_REF]. Let us give now an example of a valid strategy that fulfills our first requirement.

(Req 1). The following grammar introduces latencies of 4 time steps and eliminate the forbidden transitions (from up to down and conversely): up = repeat 3 stepUp » up' up' = stepUp » (end 'or' (up' 'or' stop)) stop = repeat 3 stepStop » stop stop' = stepStop » (end 'or' (stop' 'or' down 'or' up)) down = repeat 3 stepDown » down' down' = stepDown » (end 'or' (down' 'or' stop))

Indeed, the first non terminal up starts by a sequence of 3 stepUp, then ( » ), the non terminal up' also starts by one stepUp. The operator or composes two executable grammars. It is similar to the choice operator | of BNF. For instance, in this grammar, up' leads either to the terminal end (which succeeds when the clock is equal to the final time step), or it loops to up', or it leads to stop.

The graphical result of this controller for the elevator is shown in Figure 3. This figure represents the possible altitudes of the elevator in function of time, calculated by our strategy. The initial position of the elevator has been measured and is quite precise (almost reduced to a point). Then a model (here up) predicts the next position of the elevator, and so on. Positions get less and less precise until a new measurement comes up and constrains the position again.

We can first observe visually that the shape of the trajectory follows the hidden scenario, shown by the dashed arrows in the figure. However, the uncertainties make other scenarios possible. In the solution given by our strategy, the first switch occurs at t = 52 instead of t = 46. The figure suggests that this shift is probably not imputable to the strategy but to the inherent uncertainty (that is, the lack of measurements). Indeed, it is apparent that the first model switch can be postponed a few more steps after 46. The sequence of switches returned by our strategy is: From the time step 0 to the time step 51 the model up has been applied, then from 52 to 55 the elevator has stopped, then from 56 to 64 it has moved down, etc.

Second-Level Strategy

To obtain (3), we write in Haskell stepUp = do contract up contract measurements tick

where contract up and contract measurements are simply monadic wrappers for M UP i and M µ i , where i is the current time (see §2.5). The tick increments the solver's clock.

(Req 2). To perform backward propagation as in (4), we write:

stepUp = do choice m RR n°7451
contract up r ← contract measurements tick when (r==signif) backwardPropag

It is quite similar to the previous version. Additionally, it adds the model m to the list of recorded choices and triggers a backward propagation when the result of the measurement contractor is significant. backwarPropag just flattens the list of choices made so far and backwardPropag' applies the model contractor again for each choice, in the reverse chronological order. This backward propagation proceeds as long as a model contractor significantly contracts boxes as denoted by the statement when in the recursive definition of backwardPropag'. Each sublist of choices contains the sequence of model contractors between choice points. In order to limit the backward propagation from the current time to the previous choice point we simply can replace concat by head in backwardPropag in order to select the first sublist of choices.

We can see in Figure 3 that estimations ahead of measurements have been smoothed by the backward propagation.

Monadic Operators

Haskell provides a formal framework to define and compose effects: monads [START_REF] Simon | Imperative Functional Programming[END_REF]. For instance, the IO monads encapsulates side effects (such as calling a C function) and the Maybe monads enables us to encapsulate failures and backtracks. In our case, we define a new monad for executable grammars with the type2 type Ibex a = State → IO (State,Maybe a)

It can be read as follows: an executable grammar takes a state (containing the clock, the choices and the trail) as a parameter and applies a sequence of contractors (i.e., calls C contractors in Ibex, whence the IO). The result is a modified state (e.g., the clock has been incremented) and a return value of type (Maybe a) which indicates if the strategy (executable grammar) was successful.

A monad defines two functions: return and ( » ). In our case, the function return defines an empty grammar that applies no contractor. The function ( » ) defines the sequential composition of two grammars.

Our grammars provide choice points and backtrack based on trailing. Our monad provides two more functions: mzero and or. The function mzero defines a grammar that fails and terminates a sequence of contractors. The function or composes two executable grammars and introduces a choice point. When m1 'or' m2 is executed, first m1 is executed. If m1 fails (i.e., calls mzero), then the trail is used to restore the domains and m2 is executed. If m1 succeeds, then m2 is never executed. Note that we never explicitly call mzero but a guard statement does when an invariant is violated. For instance:

contract m = do i ← time r ← contractC m i guard (r/=unfeas)
In this definition, contract gets the current time and calls the C contractor (contractC) defined in Ibex. If fails and backtracks when the contractor returns unfeasibility (the box gets empty). Otherwise, the execution proceeds in sequence.

Third-Level Strategy

Our monadic operators hide implementation details about side-effects and backtrack by trailing. Our second level strategies hide implementation details about the time and backward propagation. Our approach is all about encapsulation and providing the right level of abstraction to the user. When the programmer write up' 'or' stop, he hopes up' more likely succeeds than stop. When the programmer does not have such a piece of information, he can rely on heuristics.

(Req 3). We can design an alternative operator orH in answer to this requirement: orH (model1,g1) (model2,g2) = do bm ← try measurements b1 ← try model1 b2 ← try model2 if (dist bm b1 < dist bm b2) then g1 'or' g2 else g2 'or' g1 dist boxMeasurement boxModel = abs (mid boxMeasurement -mid boxModel) + abs (radius boxMeasurement -radius boxModel)

The operator takes two models and two grammars as parameters. It applies the measurement contractor, saves the contracted box in bm and restores the original box. The same is done for model1 and model2. The Hausdorff distances with bm are then compared for both results so that the most probable grammar is executed first. This new operator enables us to find a solution that compares advantageously to the one found with the or operator in §2.3. With orH, the solution is less jumpy: it is a sequence of only 10 models (instead of 13) obtained for the cost of 2664 backtracks (instead of 5059).

Monadic Operators Implementation

In Section 2.5, we gave a quick overview of the monad used in our framework. We now dive into more technical details. First, in Section 3.1 we detail our monad definition. Second, in Section 3.2 we discuss the implementation of the backtrack by trailing. Third, in Section 3.3 we show how monadic expression can be rewritten dynamically to satisfy monadic laws.

Monadic Parsers Revisited

We have designed and implemented a monadic library in Haskell strongly inspired from the monadic parser libraries. However, our library does not parse sequences of commands but it enumerates them. At the same time it enumerates the models in a sequence, the sequence is tested by applying the corresponding constraints. If a constraint makes an interval empty, the sequence is declared not valid and the next sequence is enumerated and tested. This requires first to undo the side effects of the constraints of the first sequence. This backtrack is implemented by a trailing mechanisms. Indeed, a constraint has a local side effects on the C array: it modifies the variables at index i and i + 1 only, where i is the current time step. So, it would be to inefficient to copy the full array of variables for each choice point.

The type of our monad Ibex a is defined as a function that takes the current State as a parameter and returns a pair with the updated state and possibly a result (i.e., Maybe a): newtype Ibex a = Ibex { runIbex :: State → IO (State,Maybe a) } Note that, even when there is no result (i.e., Nothing) the state is returned. Indeed, the state contains the growing trail which enables backtracking. Our monad is used to call foreign C functions so its type is based on IO.

The monadic operators are defined as follows: The operator return just returns the current state and a result. The bind operator »= runs its first argument with the current state. (Here runIbex is the deconstructor of the type Ibex a). When there is no result, the second argument of the bind operator is ignored and the current state is returned. When there is a result, the second argument is evaluated as for the classic state monad.

Our monad is also a monad plus that provides the notions of choice point and failure with the function mplus (a.k.a. or in the previous sections) and For instance, we define

contract :: Model → Time → Ibex Return contract m i = liftIO $ c_contract m i

Backtrack by Trailing

The state of our monad is defined as follows:

data State = State { clock :: Time , back :: Int , trailS :: TrailS , choiceS :: ChoiceS } It encapsulates a clock (i.e., an integer corresponding to the current index in the C array), a counter of backtracks for profiling, a trail that registers the actions to be undone in order to restore a previous state, and the list of past chosen models (i.e., which constraint has been applied at what time).

Both the trail and the chosen models are structured as list of list: each sublist represents the actions, or the models, between two choice points.

type TrailS = [[Action]] type ChoiceS = [[(Model,Time)]]
There are two kinds of action corresponding to modifications of the clock or modification of the C array by a constraint.

Left Distribution in Monadic Expressions

Monads come with laws. In particular, a monad plus must satisfy the left distribution law:

(m1 'mplus' m2) » m3 = (m1 » m3) 'mplus' (m2 » m3)

RR n°7451

Unfortunately our monad Ibex does not satisfy this law. Indeed, if m1 succeeds then its result is returned and the second branch m2 is discarded. So, this second branch m2 is lost when m3 fails (the correct behavior would be to backtrack and try m2 » m3 as specified by the right hand side of the law). Our examples in this paper do not exhibit this problem because their definitions match the right-hand side of the law only. However, it could be convenient to use the left-hand side pattern too. For instance, the sequences of a given model can be defined as up'' = stepUp » (up'' 'mplus' empty) stop'' = stepStop » (stop'' 'mplus ' empty) where empty that applies no model and succeeds is simply defined as return unsign. In this case, an expression such as up'' » stop'' is structured as the left-hand side of the law.

A work around consists in defining a data type IbexS to represent monadic expression. In this definition R stands for return, B for bind, Z for zero, P for plus and A for atomic expression of type Ibex with no inner choice (e.g., call a C function). The type of the bind operator »= requires existential quantification to define its corresponding constructor B.

There is no need of parser to construct a term of this type but we simply define a monad plus and its operators so that they return a term. Finally, we define an interpreter run that restructures the terms and eventually calls the actual operators of Ibex. Where evalIbex is the usual function that evaluates a monadic expression by passing it the initial State.

Conclusion

In this article, we have proposed a framework to control contractors for the state estimation of hybrid dynamical systems. It promotes the design of tailor-made constraint solvers. It is composed of three layers that offer different levels of abstraction. The top-level layer enables the user to declaratively yet operationally specify research strategies as ambiguous grammar. The second layer provides abstractions for controlling the propagation heuristic. Finally, the third layer implements choice points and backtrack with a trail. Our framework is implemented as a monadic library in Haskell on top of the Ibex contractor library in C. It benefits from the expressiveness and safety of Haskell and from the efficiency of C. We have introduced and illustrated our framework with an elevator running example, but it can be used for any hybrid dynamical system as long as a list of models is handled (instead of just three).

Opportunities for future work are manyfold. Here are two of them. First, our backtrack mechanism relies on trailing. However, the longer the system lives, the longer the trail gets. For a scale up, the third layer of our framework could be modified to integrate a sliding time window that keeps only a limited trail of the past. Second, the approach could be extended to estimation problems in mobile robotics where strategies are more complicated: the unknowns include the environment (in addition to the state of the robot) and new kinds of contractors (relating the state of the robot and that of detected objects) are involved.

Figure 3 :

 3 Figure 3: Inference of a scenario. Model switches of the hidden scenario are marked by the vertical lines. The inferred scenario differs significantly. Some switches are just shifted (e.g., stop at t = 111 instead of 106) but superfluous switches also appear at t = 56, 65, etc. The stability of the solution is improvable simply by increasing the latency.

  backwardPropag = do cs ← choices backwardPropag' (concat cs) backwardPropag' ((m,i):es) = do r ← contractAt m i when (r==signif) (backwardPropag' es)

instance

  Monad Ibex where return a = Ibex $ λs → return (s,Just a) m »= k = Ibex $ λs → do res ← runIbex m s case res of (s1,Nothing) → return (s1,Nothing) (s1,Just a) → runIbex (k a) s1

{

  -# LANGUAGE ExistentialQuantification #-} data IbexS a = R a | forall b. B (IbexS b) (b → IbexS a) | Z | P (IbexS a) (IbexS a) | A (Ibex a)

instance

  Monad IbexS where return a = R a m »= k = m 'B' k instance MonadPlus IbexS where mzero = Z mplus m1 m2 = m1 'P' m2

  run :: IbexS a → Ibex a run ((m1 'B' k1) 'B' k) = run (m1 'B' (λb → ((k1 b) 'B' k))) run ((m1 'P' m2) 'B' k) = run ((m1 'B' k) 'P' (m2 'B' k)) run (m1 'P' m2) = (run m1) 'mplus' (run m2) run (m 'B' k) = (run m) »= (λb → run (k b)) run (R a) IbexS a → IO a eval m = evalIbex (run m)

  Its mzero operator simply returns the current state and no result. Its mplus operator first performs the computation corresponding to its first argument. If there is a result, it is returned and the second computation is never evaluated. If there is no result, the second branch is evaluated. The auxiliary function commit is called before each computation to record a new trail in the state and the function backtrack is called each time a computation has no result to replay the trail backward (i.e., undo side effects in Ibex and remove the corresponding trail from the state). The definitions of the functions commit and backtrack depend on the representation of the State. We postpone them to the next section.Our monad provides access to the low-level C functions with the following lifting operator:

	liftIO :: IO a → Ibex a
	liftIO m = Ibex $ λs → do
	a ← m
	return (s,Just a)
	mzero:
	instance MonadPlus Ibex where
	mzero = Ibex $ λs → return (s,Nothing)
	mplus m1 m2 = Ibex $ λs → do
	(s1,r1) ← runIbex m1 (commit s)
	case r1 of
	Just a1 → return (s1,r1)
	Nothing → do s2 ← backtrack s1
	(s3,r2) ← runIbex m2 (commit s2)
	case r2 of
	Just a2 → return (s3,r2)
	Nothing → do s4 ← backtrack s3
	return (s4,r2)

  data Action = Tick | Undo EventWhen the clock is incremented by tick a corresponding action is added to the trail: This function relies on saveEvent that reads a column of the C array and returns it as a Haskell tuple. Then this tuple is added to the first sublist of trailS.Such a tuple is created and added to the trail by calling the function choice each time a constraint is chosen.The model is also added to the first sublist of ChoiceS.Finally, our backtrack mechanism is implemented by the two functions commit and backtrack called by the function mplus. The function commit introduces a new choice point by simply adding a new empty sublist to the trail and the choices. The function backtrack uses the most recent sublist of the trail to undo the most recent actions and restore a state corresponding to the last choice points. This is performed by the function rollback that decrements the clock for Tick and restores the state of Ibex variables for Undo.

	trailAt :: Time → Ibex ()
	trailAt i = do
	e ← liftIO $ saveEvent i
	modify $ λs → s { trailS=addAction (Undo e) (trailS s) }
	data Event = Event {
	t::Time
	, d0x_lb::Value , d0x_ub::Value
	, d1x_lb::Value , d1x_ub::Value
	, d2x_lb::Value , d2x_ub::Value
	}
	choice :: Model → Ibex ()
	choice m = do
	i ← time
	trailAt i
	modify $ λs → s { choiceS=addChoice (m,i) (choiceS s) }
	commit :: State → State
	commit s = s {trailS=[]:trailS s,choiceS=[]:choiceS s}
	backtrack :: State → IO State
	backtrack s = do
	let as:ts=trailS s
	foldM rollback (s{trailS=ts,choiceS=tail (choiceS s)
	,back=1+back s}) as
	rollback :: State → Action → IO State
	rollback s Tick = return $ s {clock=clock s-1}
	rollback s (Undo u) = do
	restoreEvent u
	return s
	tick :: Ibex ()
	tick = do
	t ← time
	modify $ λs → s { trailS=addAction Tick (trailS s)
	, clock=clock s+1 }
	When a constraint is to be applied, the column of the C arrays it can modify is
	saved by trailAt

RR n°7451

There are actually some additional properties in the definition, but with no incidence here.RR n°7451

For the sake of clarity this is a simplified type, see Section

3.1 for a full definitiion. RR n°7451

new contractor is canceled when backtracking. This is illustrated in Figure 2, with N = 3 (three time steps). The consistency at the grey-filled node is checked by propagating the choice u 3 = stop in a contractor list inherited from the node with dashed contour. This list was built with (u 1 , u 2 ) = (up, up) and consistency was enforced by the node with dashed contour. Copying all the [x] i 's when branching is clearly non affordable and trailing has to be used. Hence, the solver state (not to be confused with the state x) contains a trail: a list that incrementally records the changes brought to the [x] i 's. It also contains the choices made so far (u 1 , . . .) and a clock that indicates on which time step the next choice will operate.

A Two-Layered Structure of Contractors

Each new choice leads to a sequence of contractions. Let us consider the greyfilled node in Figure 2 and denote by >> the composition of two contractors. The basic sequence is

that is, the state interval [x] 3 is estimated by applying the model contractor for stop on ([x] 2 , [x] 3 ) and subsequently updated with the measurement contractor. However, if the measurement entails a significant contraction, one might also decide to refine the past state estimations by propagating backward with the contractors. This would give here:

Since a composition of contractors is a contractor, sequences (3) and (4) form two different versions of a compound contractor C stop 3 resulting from the choice u 3 = stop. Hence, the overall propagation for the scenario (u 1 , u 2 , u 3 ) corresponding to the grey-filled node is a sequence of first-level contractors

each first-level contractor C i corresponding to a choice for u i and being itself a composition of second-level contractors, as shown above.

Why such a structure? The first-level sequence reflects the scenario and is therefore impacted by the behavior of the system. On the contrary, the


K Abdennadher
email: karim.abdennadher@mgeups.com

C Rosset

P Venet

G Rojat

J.-M Rétif

Abstract-This paper presents a low-cost method to realize a real-time condition monitoring and a predictive-maintenance system of an electrolytic capacitor used in uninterruptible power supplies (UPSs). This method consists in detecting the changes in real time of the equivalent series resistance and the capacitance C values of the electrolytic capacitors. Simulation and experimental results are presented to illustrate the proposed monitoring technique. The proposed method can be used in UPS where waveforms are continuously varying in amplitude, frequency, and temperature. The proposed online failure prediction method has the merits of using only the existent resources in UPS and with the use of known algorithms.

Index Terms-Electrolytic capacitors, identification, Kalman filtering, predictive maintenance, real time.

I. INTRODUCTION

E LECTROLYTIC capacitors have been widely used in power-electronic systems because they can achieve high capacitance and voltage ratings with volumetric efficiency and low cost. This type of capacitors has been traditionally used for filtering, coupling, timing networks, bypass, and many other applications in power electronics requiring a cost-effective and volumetrically efficient component. It is known that the common faults in electrolytic capacitor include initial catastrophic failures due to manufacturing or misapplication defect and wear-out faults, which cannot be avoided. Unfortunately, electrolytic capacitors are one of the weakest components in power-electronic converter [1]- [START_REF] Myungchul | Condition monitoring of DC link electrolytic capacitors in adjustable speed drives[END_REF]. For example [1], [START_REF] Lahyani | Failure prediction of electrolytic capacitors during operation of a switchmode power supply[END_REF], in uninterruptible power supplies (UPSs), they are responsible for about 50% of the cases of power-electronic component failures. An electrolytic capacitor has a number of root causes and failure modes. Degradation of this component is due to a combined effect of electrical, thermal, mechanical, and environmental stresses. The main wear-out failure mechanism is the evaporation of the electrolyte solution which is accelerated with temperature rise during the operation and due to ripple currents. This causes a decrease in C and an increase of the equivalent series resistance (ESR) which further increase the temperature (losses). Standard [START_REF] Venet | Detection of faults of filter capacitors in a converter. Application to predictive maintenance[END_REF] suggests that the capacitor should be considered as failed if there is an increase that is double the initial ESR value and a 20% decrease in the capacitance value. Hence, estimation of ESR and the capacitance by taking into account the temperature is important for condition monitoring of the electrolytic capacitor. The purpose of this paper is to propose a method to detect in real time the changes in the value of the ESR and also of the capacitance in order to create a realtime predictive system of electrolytic-capacitor failures. It is further shown in this paper that the proposed method can be applied even in the nonstationary system, such as UPS, where capacitor ripple voltage and current are continuously varying in amplitude and frequency. They also depend on the ambient temperature where the converter operates.

Many papers have proposed different methods or algorithms to determine the ESR and/or capacitance C of the electrolytic capacitor [START_REF] Venet | Detection of faults of filter capacitors in a converter. Application to predictive maintenance[END_REF]- [START_REF] Myungchul | Condition monitoring of DC link electrolytic capacitors in adjustable speed drives[END_REF]. However, many parameters, such as offline additional measurements, and many computations are required, which makes it complicated, difficult, expensive, and impractical for actual application.

Modern UPS can utilize a variety of accurate sensors, numerical treatment systems, and powerful computation resources which are used to control and regulate the UPS in order to improve its performance and efficiency. The suggested method has the merits of making a real-time predictive-maintenance system of electrolytic capacitors by using existing resources in the UPS. This predictive-maintenance system works in background tasks and without disturbing the regulation and the operating system.

II. ELECTROLYTIC-CAPACITOR TECHNOLOGY

A. Electrolytic-Capacitor Modeling

The structure of a screw-terminal electrolytic capacitor [START_REF] Martinez-Vega | Matériaux diélectriques pour le génie électrique 2-Applications spécifiques[END_REF] is shown in Fig. 1. Due to physical design elements and construction, aluminum electrolytic capacitors are modeled by the electrical equivalent circuit [START_REF] Perisse | Simple model of electrolytic capacitor taking into account the temperature and aging time[END_REF], [START_REF] Perisse | Etude et analyse des modes de défaillances des condensateurs électrolytiques a l'aluminium et des thyristors[END_REF] shown in Fig. 2. This model, which is the most used one, is rather simple and gives a good frequency response.

In Fig. 2, C AK is the ideal capacitance between anode and cathode, R p is the parallel resistance which represents all the losses in the dielectric and the leakage between the two electrodes, R l is the connection and electrode serial resistance, and L is connection and winding equivalent series inductance (ESL). This circuit can be simplified with the normalized representation given in Fig. 3. It is a series combination of an ESR which represents all the component losses, a capacitance C, and an ESL, which is due to the wound structure of the capacitor.

From the impedance equality between the circuit elements shown in Fig. 2 and those represented in Fig. 3, we can conclude the following equations, where ω is the electrical pulsation:

C = C AK • 1 + 1 R 2 p C 2 AK ω 2
(1)

ESR = R l + R p 1 + R 2 p C 2 AK ω 2
(2)

ESL = L. ( 3
)
This capacitor representation is important because it is directly given from the impedance frequency measurements. Therefore, the resonant frequency f r of the capacitor is given by Equations ( 1) and ( 2) show that ESR and C can be considered separately from the frequency when the latter is not too low. Therefore, the resistance R p has an effect only on very low frequencies (less than several tens of hertz). This is shown in Fig. 5, which represents the effect of R p versus frequency f on the ESR and C parameters. It is an example of an electrolytic capacitor with a nominal capacitance value of 4700 μF and a nominal ESR of 20 mΩ.

f r = 1 2 • π • √ ESL • C . ( 4
)

B. Electrolytic-Capacitor Aging

Fig. 6 [START_REF] Perisse | Etude et analyse des modes de défaillances des condensateurs électrolytiques a l'aluminium et des thyristors[END_REF] shows the majority of electrolytic-capacitor failure modes and their root causes. As can be seen, the estimation of ESR and C can provide at least all the normal and use-failure defects. Therefore, the estimation of these two parameters is important to realize a real-time predictive-maintenance system of electrolytic capacitor.

III. ELECTROLYTIC-CAPACITOR MONITORING

A. Estimation of ESR and C

As we have just seen before, the electrolytic capacitors can be modeled as a serial combination of a capacitance, an ESL, and an ESR, as shown in Fig. 3. The bode plot of an electrolytic capacitor with ESR = 74 mΩ, ESL = 10 nH, and capacitance C = 470 μF is shown in Fig. 7. Therefore, the converters in the UPS works at a low-frequency band compared with the resonant-frequency one (4), so ESL is usually neglected, and the equivalent model of the capacitor is given by an ESR in series with a capacitance (C). The transfer function of this model is given by

H(s) = Uc(s) Ic(s) = ESR • C • s + 1 C • s . ( 5
)
However, converters are controlled by using digital treatments.

We can consider the z-transform corresponding to (5) to represent the discrete-time domain by using the bilinear method of Tustin and which is given by ( 6), where T s is the sampling period

H(z -1 ) = b 0 + b 1 .z -1 1 -z -1 = ESR + T s 2.C + T s 2.C -ESR .z -1 1 -z -1 . ( 6
)
The bode plot in Fig. 7 shows that the continuous-and discrete-time domain for a sampling period of T s = 12.5 μs are equivalent if we use the bilinear-method discrete time. A Matlab simulation was performed using dynamic equation from the equivalent circuit shown in Fig. 8 of a boost-converter with a 50-V dc voltage input, with a switching frequency of 5 kHz and which is regulated to have a 200-V dc voltage output.

A recursive least square algorithm, which is a particular case of Kalman filter, was used as shown in Fig. 9.

In practice, we do not have a capacitor current sensor because it is difficult and expansive to implement in UPS. To perform and regulate the output voltage, we only dispose of one current sensor used to have the input current inductance L of the boost converter. However, we can identify the capacitor current using Kirchhoff's laws referring to the schematic of the boost converter shown in Fig. 8 Ic = Id -Ich.

(

) 7
When the insulated-gate bipolar transistor is off (the pulsewidth modular PWM = 0), we have Id = Il, so we can conclude the following:

Id = Il * P W M. ( 8
)
In stationary process, the average capacitor current Ic is equal to zero, so, for one regulation period, we have the following:

Ic = Il * P W M -avg(Il * P W M). ( 9
)
Respectively, the simulation results of the capacitor ripple voltage and capacitor current identified with the use of ( 9) are shown in Fig. 10.

The simulation results presented in this section are summarized in Table I.

TABLE I SIMULATION RESULTS FOR ESTIMATED PARAMETERS

B. Aging Algorithm

The aging algorithm, which takes into account the temperature, is given in the following.

The evolution of ESR and C versus ambient temperature T a is given by the following equation [START_REF] Perisse | Simple model of electrolytic capacitor taking into account the temperature and aging time[END_REF] where α, β, γ, χ, ν, and λ are experimental parameters and depend on the used capacitor: The time until failure compared with failure limits of ESR and C can be calculated by using the following [START_REF] Perisse | Simple model of electrolytic capacitor taking into account the temperature and aging time[END_REF]:

ESR(T a , t) = α + β • exp - T γ (10) C(T a , t) = χ + λ • exp - T ν . ( 11
)
t ESR ta ESR = exp Ea ESR k • T -T a (T +273) • (T a +273) ( 12
)
t C ta C = exp Ea C k • T -T a (T + 273) • (T a + 273) ( 13
)
ESR(t ESR )= (ESR(0) + A 1 ) • exp(B 1 • t ESR ) (14)
C(t C )=E • C(0) + F • t C ( 15
)
where T a Ambient temperature (25 Activation energy with C aging indicator.

A 1 , B 1 , E, and F are experimental parameters and also depend on the used capacitor.

From ( 10)-( 13), the time until failure of the capacitor is given by the lower computed time between ESR lifetime limit and C lifetime limit, as shown in Fig. 11.

We have, for these works, different types of capacitors from four different manufacturers. All capacitors are first characterized versus temperature to determine the parameter-evolution laws versus temperature.

The parameters of ( 10) are determined by the nonlinear least square method of Levenberg-Marquardt which allows a very close approximation of the model.

For the example shown in Fig. 12, the method gives the following values for ESR: The parameters of [START_REF] Ondel | A decision system for electrolytic capacitors diagnosis[END_REF] are determined in the same way as those identified in ESR. For the example shown in Fig. 12, we have the following values for C: χ = 0.000812 F λ = 4.600790 times 10 -0.007 F/ • C. Some experimental results show the parameter evolutions of ESR and C after 3390 h of aging (about 5 mo) at 90 • C. Also, we use a Matlab algorithm to make a linear interpolation and extrapolation with the use of experimental data. This allows us to find the parameter-evolution laws and also the time until failure corresponding to the ESR and the capacitance C limit. The ESR and C variations versus temperature for a capacitor of 1000 μF/450 V are shown in Fig. 12.

α = 0.013055 Ω β = 0.75844 Ω γ = 14.888386 • C.
We show in Fig. 13 the interpolated and extrapolated data with the use of experimental measurements for ESR and C parameters of one capacitor (1000 μF/450 V).

C. Experimental Study 1) Experimental Setup:

To verify the validity of the proposed method, an experimental study was performed on a boost converter with a 50-V dc input, 470-μF-450-V capacitor, an R load of 100 Ω, and a switching frequency that is fixed at 5 kHz. Therefore, a fixed-point DSP controller (TMS320F2812) was used for Il, Uc, Ic, and capacitor ripple voltage ΔUc acquisition measurements and switching operations required to perform the 200-V dc output voltage. To do that, we choose the two imbricated-loop principles, one fast current loop with a proportional/integrator controller to perform the current reference and another external voltage loop with a deadbeat controller to perform the 200-V dc output voltage. Moreover, a recursive least square algorithm (a particular case of Kalman In literature [START_REF] Landau | Digital Control Systems Design, Identification and Implementation[END_REF], we know that using different cases of Kalman filter provides cutoff of the dc component of the input and output measurements, which are, respectively, capacitor current (recovered using the inductance current) and capacitor voltage. Therefore, the capacitor voltage and the inductance current are passed through a high-pass filter with cutoff frequency of around f c = 200 Hz to suppress the dc component of the voltage measurements and without including phase shift. Consequently, we have only the capacitor ripple voltage which is in phase with the capacitor current.

A fast Fourier transform (FFT) analysis respectively on the capacitor ripple voltage and capacitor current is shown in Fig. 14, and we see that the bandwidth of the system is about 40 kHz. Therefore, with respect to the Shannon theorem and to have a good ESR and C estimation, we choose a sampling frequency f s = 80 kHz.

To eliminate signal distortion, an antialiasing filter [START_REF] Landau | Digital Control Systems Design, Identification and Implementation[END_REF] with a cutoff frequency f c = (f s /2) ≈ 40 kHz is used, as shown in the global capacitor condition monitoring scheme Fig. 15.

2) Adjusting Channels: The amplitudes of the measurements used to identify ESR and C are variable, depending on several parameters of the system in real time such as temperature, input voltage, and load applied to the power converter. To always have a full scale (3 V) on the DSP entrance for a good accuracy of identified parameters, we choose to apply a system to adjust automatically the amplitude of each measurement channel needed for identification. This system was performed by using a single eight-channel demultiplexer (M74HC4051) for each measure. Each demultiplexer was controlled independently by DSP to implement a variable gain. The gain choice is given by a well-defined algorithm shown in Fig. 16. This algorithm runs in real time and with less priority compared with the system regulation. The coding used to select the variable gain is optimized with minimizing loops (for, if, while, . . .) to have few DSP clock cycles used. The corresponding numerical DSP measurements (after the analog-to-digital converter) of the capacitor ripple voltage and recovered capacitor current (9) are shown in Fig. 18.

The experimental results for the estimated parameters are summarized in Table II.

The least-squares algorithm implemented on DSP uses about 1 kB of a 16 bits word of DSP memory and takes about 2 s to converge and gives the ESR and C estimated values. This time is too small compared with the lifetime of a capacitor. Also, from experiments, a good and fast parameter identification is given by a decreasing forgetting factor. At every turn, the It can be clearly seen that there is a nonsignificant error between the estimated and actual values of ESR and C.

These results are consistent with the measured value using an impedance meter.

IV. CONCLUSION

Due to their large capacity and low cost, electrolytic capacitors, with the abilities of energy storage and voltage regulation, are used for almost all types of power-electronic system. Electrolytic capacitors, which are usually affected by wear-out faults, play a very important role for the quality and reliability of power-electronic system. Therefore, it is important to monitor the condition of an electrolytic capacitor in real time to predict the failure. A new method has been proposed to detect in real time the changes in the ESR and capacitance C values by taking into account the ambient temperature in order to create a real-time failure prediction of an electrolytic capacitor. For the proposed method, capacitor-current and capacitor ripple-voltage measurements using cheap and simple analog circuits are required. Simulation results and hardware experiments show that the proposed electrolytic-capacitor failureprediction technique can be applied to a power-electronic system successfully.

Fig. 1 .

 1 Fig. 1. Structure of a screw-terminal electrolytic capacitor [16].

Fig. 2 .

 2 Fig. 2. Electrical equivalent circuit of an electrolytic capacitor.

Fig. 3 .

 3 Fig. 3. Normalized electrical equivalent circuit of an electrolytic capacitor.

Fig. 4 .

 4 Fig. 4. Z(f ) for aluminum electrolytic capacitor of 4700 µF/500 V.

Fig. 5 .

 5 Fig. 5. Z(f ) for aluminum electrolytic capacitor of 4700 µF/500 V [17].

Fig. 6 .Fig. 7 .

 67 Fig.6. Capacitor failures and their causes[START_REF] Perisse | Etude et analyse des modes de défaillances des condensateurs électrolytiques a l'aluminium et des thyristors[END_REF].

Fig. 8 .

 8 Fig. 8. Schematic of a boost-converter circuit with a dc capacitor circuit.

Fig. 9 .

 9 Fig. 9. Parameter identification using Kalman filter.

Fig. 10 .

 10 Fig. 10. Matlab simulation results of capacitor ripple voltage ΔUc and capacitor current Ic.

Fig. 11 .

 11 Fig. 11. Aging algorithm.

Fig. 12 .

 12 Fig. 12. Electric parameter variations versus temperature of one capacitor (1000 µF/450 V).

Fig. 13 .

 13 Fig. 13. ESR evolution at 5 kHz and C evolution at 200 Hz for one capacitor (1000 µF/450 V).

Fig. 14 .

 14 Fig. 14. FFT analysis of capacitor ripple voltage and capacitor voltage for a sampling frequency fs = 80 kHz.

Fig. 15 .

 15 Fig. 15. Real-time electrolyte capacitor condition monitoring in UPS.

Fig. 16 .

 16 Fig. 16. Online gain choice algorithm.

Fig. 17 .

 17 Fig. 17. Capacitor ripple voltage and capacitor current.

3 )

 3 Experimental Results: The experimental measurements on the scope of capacitor ripple voltage and capacitor current (given by a current probe) are shown in Fig.

17

 17

  .

Fig. 18 .

 18 Fig. 18. Capacitor ripple voltage and capacitor current recovered on DSP with a sampling frequency fs = 80 kHz.

  A Real-Time Predictive-Maintenance System of Aluminum Electrolytic Capacitors Used in Uninterrupted Power Supplies Karim Abdennadher, Student Member, IEEE, Pascal Venet, Member, IEEE, Gérard Rojat, Jean-Marie Rétif, and Christophe Rosset, Member, IEEE

  Ea ESR Activation energy with ESR aging indicator. Ea C

• C for example). T Aging temperature (85 • C for example). ta ESR Aging time for the ESR limit at T a . ta C Aging time for the C limit at T a . t ESR Lifetime limit at T with ESR aging indicator. t C Lifetime limit at T with C aging indicator. t ESR Time until failure with ESR aging indicator. t C Time until failure with C aging indicator. k Boltzmann constant (8.617 times 10 -5 eV/ • K).

TABLE II EXPERIMENTAL

 II RESULTS FOR ESTIMATED PARAMETERS algorithm starts with the last identified parameters of ESR and C.

ACKNOWLEDGMENT

The authors would like to thank E. Brun, Emerging Technologies Director, for the support of the research.

Pascal Venet (M'08) was born in Aix-Les-Bains, France, on March 16, 1965. He received the Ph.D. degree in electrical engineering from Lyon 1 University, Villeurbanne, France, in 1993.

Since 1995, he has been an Assistant Professor at Lyon 1 University. He has developed his research activity in the Electrical Engineering Laboratory (Laboratoire Ampère). His current research interests include static-converter fault diagnostics and aging of components such as electrolytic capacitors, supercapacitors, and batteries. Currently, he is a Senior Technical Expert with APC by Schneider Electric, Saint Ismier, France, working in core control for uninterruptible power supplies. Currently, he is involved in research on fault diagnostics of capacitors and batteries and also in electronic architecture of new uninterruptiblepower-supply topology.

Gérard Rojat was born in