Member, IEEE Dimitri Galayko
email: dimitri.galayko@lip6.fr

Andrii Dudka
email: andrii.dudka@lip6.fr

Student Member, IEEE Armine Karami
email: armine.karami@gmail.com

Student Member, IEEE Eoghan O'riordan
email: eoghan.o-riordan@ucdconnect.ie

Senior Member, IEEE Elena Blokhina
email: elena.blokhina@ucd.ie

Fellow, IEEE Orla Feely
email: orla.feely@ucd.ie

Philippe Basset
email: p.basset@esiee.fr

K.-H D Chen

A Galayko

Karami

Capacitive Energy Conversion With Circuits Implementing a Rectangular Charge-Voltage Cycle

Keywords: Capacitance, circuit analysis, DC-DC power conversion, energy harvesting, power systems, switched systems

come

I. INTRODUCTION

M ICROSCALE kinetic energy harvesters (KEH) are con- sidered a useful complement to other available power sources such as chemical batteries and solar cells. Microscale KEHs are a relatively new class of device, which emerged a little over a decade ago [START_REF] Mitcheson | Energy harvesting from human and machine motion for wireless electronic devices[END_REF]. The interest in microscale energy harvesting is explained by the success of micromachining technologies allowing a fabrication of very efficient miniature electromechanical systems (MEMS). KEHs are complex heterogeneous systems: they require advanced engineering of mechanical and electrical parts, and their operation is described by nonlinear multiphysics models. The electromechanical conversion mechanism is the main aspect distinguishing different implementations of KEH.

The diagram in Fig. 1 presents the structure of a KEH placed in a vibrating reference frame , which vibrates with an acceleration with regard to an inertial reference frame . A mobile mass, when considered in the frame , is subjected to a force equal to , where is the value of the mass. This force is a source of mechanical energy. The mass may be freely moving [START_REF] Galchev | A piezoelectric parametric frequency increased generator for harvesting low-frequency vibrations[END_REF] or may be coupled with the vibrating frame by a spring, as shown in Fig. 1. Electromechanical transducers have two mechanical terminals: one is fixed to the vibrating frame, and the other is attached to the mobile mass. When the mobile mass moves, the electricity is generated at the electrical terminals of the transducer. The physics of this process depends on the transducer implementation. For any transduction mechanism, the KEH requires a power management system which transforms the harvested electricity into a form suitable for the load supply (e.g., rectification, DC voltage stabilization, etc.). Indeed, the output voltage may only be a few hundreds of millivolts in the case of electromagnetic or piezoelectric harvesters, and special start-up and voltage level up circuits are necessary. On the contrary, capacitive transducers (as in Fig. 1) may generate tens of volts, and downward DC-DC conversion is needed. The electronics interfacing with the energy harvesters are usually designed under severe restrictions due to the power consumption, and are often integrated on silicon for the sake of miniaturisation [START_REF] Torres | Electrostatic energy-harvesting and battery-charging cmos system prototype[END_REF], [START_REF] Kempitiya | Low-power interface IC for tri-plate electrostatic energy converters[END_REF].

Unlike piezoelectric and electromagnetic transducers, capacitive transducers are passive devices. In addition to the above mentioned interface with the load and the power management, they require a special electrical conditioning (biasing) in order Fig. 2. Diagram showing all charge-voltage cycles which have been used to date for conditioning of capacitve transducers in KEHs: OCB (constant-charge), OAB (constant-voltage), DFBE (rectangular) and "tear drop" cycle corresponding to the continuous conditioning circuit or KEH with electret layer [START_REF] Naruse | Electrostatic micro power generation from low-frequency vibration such as human motion[END_REF]. All cycles are drawn for the same extreme values of the variable capacitance and for the same maximal voltage .

to convert motion into electricity. The implementation of efficient conditioning circuits for electrostatic KEH is hindered by a low power level available from the electrostatic conversion, hardly more that tens of microwatts per . In capacitive transducers, the mechanical energy is converted into electricity when the transducer is biased while its capacitance decreases, i.e., when electrical force does negative mechanical work on the mass. The electromechanical energy conversion process is characterized by the charge-voltage diagram (said "QV diagram"), which is a graphical representation of the evolution of the electrical state of a capacitive transducer. For a periodic variation of the transducer capacitance, the QV diagram is a loop whose area is numerically equal to the energy converted during a cycle. Moreover, in relation to the energy conversion process, the shape of the QV diagram is an obvious basis for the classification of conditioning circuits. Fig. 2 presents all QV diagrams implemented by known conditioning circuits.

One of the main roles of a conditioning circuit is to provide the transducer with a dynamic voltage biasing corresponding to the desired QV cycle. If the maximum voltage supported by the used transistor technology is limited to , the dynamic biasing allowing the most optimal electromechanical conversion is achieved by a circuit called "constant voltage circuit" [START_REF] Meninger | Vibration-to-electric energy conversion[END_REF] (cycle OAB in Fig. 2). However, since the early noughties, several architectures of conditioning circuits for capacitive transducers have been proposed: the continuous conditioning circuit [START_REF] Mitcheson | Electrostatic microgenerators[END_REF] (tear drop QV cycle, cf. Fig. 2), circuits implementing the constant charge QV cycle [START_REF] Meninger | Vibration-to-electric energy conversion[END_REF] (triangular QV cycle OCB), circuits based on a charge pump [START_REF] Roundy | Micro-electrostatic vibration-toelectricity converters[END_REF] and recently circuits based on Bennet's doubler (rectangular QV cycle DFBE). Such a large number of concurrent solutions is explained by the difficulty in the practical implementation of the conditioning circuit with the constant voltage operation. The evolution of the conditioning circuits goes toward the simplification of the external management required for their operation: while the constant voltage and constant charge circuits require two synchronized switches at each period of vibration, the charge pump based circuit requires only one switching over several periods of vibrations. The Bennet's doubler based circuit does not require controlled switching at all.

Conditioning circuits based on the charge pump have been considered since 2002 (cf. basic architecture by Roundy et al. [START_REF] Roundy | Micro-electrostatic vibration-toelectricity converters[END_REF]); their great advantage is an automatic synchronisation of the charge flow on the capacitive transducer with the mobile mass vibration. Their common property is the rectangular shape of the QV diagram. The basic charge pump is usually complemented with a flyback, which defines its optimal steady-state operation (cf. Section III-A and III-B).

Recently, a new topology of conditioning circuit whose architecture is inspired by the Bennet's electricity doubler has been discovered. In comparison with previous conditioning circuits, these circuits increase their initial biasing by using the energy converted from the mechanical domain without employing any inductive DC-DC conversion. It was recently shown that these circuits also implement a rectangular QV cycle, and by consequence, they should be considered as belonging to the same family as the circuits based on the charge pump.

To date, conditioning circuits based on Roundy's charge pump and on the Bennet's doubler have been analyzed separately, and only from the point of view of electrical engineering. The published works have focused on experimental demonstration of the energy conversion with these circuits. However, a fundamental study of the behavior of these circuits as a part of an electromechanical system such as a KEH is still missing. An analysis of electromechanical behavior due to the transducer has never been done; it is not known how a transducer which operates following a rectangular QV cycle impacts the mechanical domain of the harvester. Understanding the common properties of these two apparently different architectures, but having very similar QV diagrams, must help in the optimization of converted power for given design specifications.

This paper, composed of two articles Part 1 and Part 2, presents a complete electrical and electromechanical analysis of a KEH which uses a capacitive transducer biased by a rectangular QV cycle. This analysis will be based on tools proposed for nonlinear KEH in previous works [START_REF] Blokhina | Steady-state oscillations in resonant electrostatic vibration energy harvesters[END_REF] allowing a nonlinear analysis of coupled electromechanical systems.

Part 1 (this article) addresses the analysis of the conditioning circuits from the electrical point of view. It is organized as follows. In Section II, we present properties and main figures of merit for an energy harvester employing a rectangular QV cycle. We explain how an ideal conditioning circuit implementing a QV cycle may be optimized from the electrical point of view, as a function of different system-level limitations. In Section III we address the practical implementation of a rectangular QV cycle. The geometric parameters of the cycle will be related to the physical parameters of the conditioning circuits based on the Roundy charge pump and Bennet's doubler. We explain how the circuits should be optimized so as to maximize the power of the electricity generation for different practical hypotheses, and we will highlight differences between these two circuits. We present the concept of adaptive operation of the circuits based on the Roundy's charge pump, and show how smart electronics may ensure that for any change in the external vibrations, the operation of the circuit is still optimal. Section V discusses practical implementations and experimental results.

Part 2 of the paper is devoted to the analysis of the system "{conditioning circuit; resonator; transducer}." A precise analytical model is developed for the Roundy charge pump with resistive flyback. This model is then solved with the multiple scales method, which belongs to the family of the perturbation techniques. The method predicts the dynamics of the mobile mass vibration, resulting from the action of the external forces (vibrations), from mechanical properties of the resonator, and from the action of the transducer biased by the conditioning circuit. The knowledge about the resonator amplitude provides information about the dynamic of the transducer capacitance variation. Hence, with the electrical analysis presented in Part 1, it is possible to know the rate of the energy conversion (the power). Predictions on the system dynamics resulting the proposed analysis method agree very well with the experiment, done with a fabricated MEMS device.

II. A PRIMITIVE CIRCUIT IMPLEMENTING A RECTANGULAR QV CYCLE

Since in Part 1 only the electrical behavior is considered, in this article the resonator and transducer are modeled as a variable capacitor. Its capacitance varies cyclically in time between its extreme values and with a period (where is the frequency), and we suppose that the function has only one local maximum and minimum over a period.

A. Idealized Circuit

An idealized conditioning circuit implementing a rectangular QV cycle is given in Fig. 3(a). The voltage sources are related as and the diodes are supposed ideal with zero threshold. Let us analyze the evolution of the electrical state of the transducer starting from the moment at which , and the transducer voltage is , D1 being on. The charge on is . As the transducer capacitance reduces because of the motion of the mobile mass, its voltage increases, switching off the diode D1, and the voltage across increases as:

(1)

The transducer capacitance decreases until ; if there exists a capacitance value such that and such that:

(2) the diode D2 turns on before reaches , and as , the diode D2 is on, and . During this phase, the transducer gives charges and energy to the source . When reaches , the charge on the transducer is .

When starts to increase, the reverse process takes place. First, both diodes are off, and the voltage across decreases as [START_REF] Torres | Electrostatic energy-harvesting and battery-charging cmos system prototype[END_REF] If there exists a capacitance value such that , and such that [START_REF] Kempitiya | Low-power interface IC for tri-plate electrostatic energy converters[END_REF] the diode D1 turns on before reaches , and as , the diode D2 is on, and . During this phase, the transducer collects charges from the source . The described process, when goes from to and back to , defines a conversion cycle. The corresponding QV diagram is given in Fig. 3(b). In summary, during one cycle the transducer operates twice with a fixed charge, and , and twice biased by a constant voltage, and . The energy converted by the transducer during such a cycle is immediately calculated from the QV diagram, as the area of the cycle (Fig. 3(b)):

(5)

The energy is not negative if and only if , or

If this condition is not fulfilled, the capacitance variation is not large enough to allow the amplitude of the variation to overcome the potential gap . In this case the transducer operates having a constant charge which depends on its initial condition. The corresponding QV cycle is a horizontal line, having a zero area and hence zero converted power.

The values and are strongly linked to the parameters of the device and to the mechanical mode, and may often be considered as imposed by a given design or application context. The converted energy depends on the extreme values of the transducer capacitance and on the voltages and . The latter depend on the practical implementation of the sources. This is discussed in Section III-D.

Since the goal of KEHs is a maximization of the converted energy, one may wonder what the optimal values of the pair achieving it are. From ( 5), one can see that the pair does not have an optimal value maximizing the converted energy

. Nevertheless, if one of these voltages are fixed (cf. Section II-B1), there exists an optimal value for the second voltage. If is fixed, the optimal value for is given by: [START_REF] Mitcheson | Electrostatic microgenerators[END_REF] and the corresponding converted energy is (8)

If

is fixed, the optimal is calculated as:

(9) and the optimal energy is [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF] It is now interesting to compare the energy converted in one rectangular cycle with the energy converted in a constant voltage triangular QV cycle OAB, Fig. 2. If the voltage of the available source is , the energy is given by [START_REF] Meninger | Vibration-to-electric energy conversion[END_REF]:

A meaningful comparison of these two circuits is possible, if the technology limits the maximal voltage supported by the diodes and the transducer to . In this case, the maximal energy obtained by the charge pump is given by ( 8), in which is substituted with . As it can be seen from Fig. 2, the optimal rectangular QV cycle produces less energy than the constant voltage cycle. In the best case, when , the ratio is 1/2.

B. Practical Implementation 1) Circuit Structure and Operation:

The network implementing the schematic of Fig. 3(a) was proposed by Roundy et al. [START_REF] Roundy | Micro-electrostatic vibration-toelectricity converters[END_REF]. It is shown in Fig. 4, with solid lines. The voltage source is implemented with a large reservoir capacitor, whose value is large enough to neglect its voltage variation over one capacitance variation period. The voltage source is implemented by a storage capacitor , which is small compared to , but much greater than the maximum value of the transducer capacitance . capacitor is initially charged to a voltage , and so are and capacitors, because of the charge sharing through the diodes D1 and D2.

In this way, by initially precharging the circuit to a voltage , we implement the configuration of Fig. 3(a) with , in which the converted energy per cycle should be zero. However, since the voltage source is implemented by a capacitor , the charge transfer from to during the first cycle slightly increases the voltage across . Hence, the corresponding QV cycle is actually triangular, as shown in Fig. 5. The next cycle starts in a configuration with a slightly larger , yielding a trapezoidal QV cycle. After each cycle, increases, so that all further cycles are different. It can be shown that the slope of the line , is (steeper than , but exaggerated on the figure): the shape of the cycles is close to rectangular, as . It can be seen that the QV trajectory follows a succession of cycles, starting from and asymptotically approaching the degenerated cycle corresponding to . This value is called the "saturation voltage" of the charge pump.

As a result of the operation of this circuit, the capacitor receives energy from , and in addition, it receives energy converted from the mechanical domain (the harvested energy). In this way, at every QV cycle of the charge pump operation, the overall electrical energy of the circuit increases. In what follows, we present a quantitative analysis of this process.

The voltage at the end of the th cycle evolves following the recursive equation [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF]:

(12) where [START_REF] Nayfeh | Introduction to Perturbation Techniques[END_REF] The solution of the discrete equation ( 12) is: [START_REF] Galayko | AMS modeling of controlled switch for design optimization of capacitive vibration energy harvester[END_REF] where is the voltage on capacitor at the zeroth cycle. In this article, it is assumed . Note that if variations are periodic, the variable is the operating time of the charge pump divided by the period of variation, . It is easy to see that the asymptotic value of as is . As increases, the voltage slowly decreases, as the amount of charges on and is constant (as one neglects the charges at ): [START_REF] Dudka | Smart integrated conditioning electronics for electrostatic vibration energy harvesters[END_REF] An example of the evolution of and is given in Fig. 6(a), where the charge pump starts from the state . From formula [START_REF] Florentino | Electrostatic vibration energy harvester with piezoelectric start-up generator[END_REF] it can be seen that if , the increment of during every cycle is small, and the charge pump run through cycles for all possible , from to the saturation value . 2) Evolution of the Harvested Energy: Neglecting the energy in the transducer capacitance since it is small, and supposing that the voltage is initially , the energy harvested during first vibration periods is stored in the capacitors and , and is given by: [START_REF] Dudka | Design of controller IC for asynchronous conditioning circuit of an electrostatic vibration energy harvester[END_REF] where is the voltage after vibration cycles, is the initial voltage of . At the same time, the sum of charges of and is constant , so, the following relation holds (neglecting the charge sharing with ): [START_REF] Bennet | An account of a doubler of electricity, or a machine by which the least conceivable quantity of positive or negative electricity may be continually doubled, till it becomes perceptible by common electrometers, or visible in sparks[END_REF] Using ( 17), ( 16) can be simplified: [START_REF] De Queiroz | The doubler of electricity used as battery charger[END_REF] This shows that the harvested energy is stored in the capacitor composed of and connected in series. This formula can be further simplified if and if is large, so that . In this case: [START_REF] Risquez | Self-biased inductor-less interface circuit for electret-free electrostatic energy harvesters[END_REF] This equation shows that the converted energy is mainly stored in the capacitor. The value [START_REF] Dragunov | Electrostatic vibration energy harvester with increased charging current[END_REF] gives the energy converted during one cycle. For the case when , this quantity can also be found from ( 5) by substituting , and . Equation [START_REF] Risquez | Self-biased inductor-less interface circuit for electret-free electrostatic energy harvesters[END_REF] relates the harvested energy only with the voltages and , hiding the operation by which the charge pump came to this state. It is thus possible to consider and as "macroscopic state parameters" of the charge pump, remove the indices and write: [START_REF] Dorzhiev | Electret-free micromachined silicon electrostatic vibration energy harvester with the bennet's doubler as conditioning circuit[END_REF] If, during the operation of the charge pump, the voltage increases from some to some , the corresponding converted energy is given by: ( 22) Fig. 6(b) presents the plots characterizing the energy conversion by the charge pump. During every cycle , the total energy (lower plot, square dots) increases by the value given by ( 5) calculated for the resulting from the previous cycle (upper plot, squares dots). The energy converted at each cycle is presented by the plot with triangular dots. Only a few cycles convert a significant amount of energy: those corresponding to values close to the optimal , (cf. the analysis of Section II for fixed

). This value is situated in-between the extreme values of , and a freely running charge pump finishes by entering into the saturation mode, in which and .

C. Shortcomings of the Primitive Circuit

Because of the saturation, the charge pump alone is not useful for capacitive KEHs. Practical conditioning circuits should be able to i) ensure a sustainable energy conversion, ii) be able to accumulate the converted energy. These two very important points are discussed in this subsection.

1) Need for a Flyback: The plot in Fig. 6(b) can be seen as the average power converted in a cycle. The goal of a harvester is to permanently maintain the converted power close to a maximum level. For this reason, a charge pump needs periodic flyback: a mechanism returning some of charges from to so as to keep close to the optimal value and to prevent the charge pump from saturation. Possible implementations of the flyback will be discussed in the next two sections.

The action of the charge pump can be seen as the generation of an average current flowing from a low potential to a higher potential . This current is roughly equal to [START_REF] Galayko | Capacitive kinetic energy harvesting: System-level engineering challenges[END_REF] The flyback must create an opposite current from to , preventing the accumulation of charges on , and so, avoiding the charge pump saturation. This current, flowing from the high to low potential, removes the electrical energy from the charge pump, and in a practical application, this energy should be transferred to a useful load. In the steady-state mode, the rate at which the energy is removed from the charge pump is equal to the power of the electromechanical conversion.

2) Auto-Increasing of the Internal Energy: From ( 5) and further analysis of Section II-B1, it can be seen that the energy converted by a charge pump is proportional to the square of the voltage and , i.e., proportional to the internal energy of the circuit in Fig. 4. Practical studies highlight that up to tens of volts may be needed for optimal operation [START_REF] Basset | Electrostatic vibration energy harvester with combined effect of electrical nonlinearities and mechanical impact[END_REF]. However, the initial charge can only be obtained by a low-voltage battery existing in the system, or by a complementary piezoelectric KEH as proposed in [START_REF] Florentino | Electrostatic vibration energy harvester with piezoelectric start-up generator[END_REF]. In both cases, the initial voltage generated in this way will certainly be low (few volts).

By consequence, the conditioning circuit should be able to use a part of the converted energy in order to increase its biasing: its internal energy represented by the voltage on the largest capacitor, . We call this property "auto-increasing of the internal energy," and the corresponding operation mode "accumulative mode." This mode allows not only a definition of high initial bias, but also a compensation of eventual losses in the conditioning circuit (leakages in the capacitors).

The auto-increasing capability is not offered by the basic charge pump.

III. CIRCUITS DERIVED FROM THE PRIMITIVE CHARGE PUMP

A. Resistive Flyback

The simplest way to implement a flyback is to connect a load between and (Fig. 4), originally proposed in [START_REF] Florentino | Electrostatic vibration energy harvester with piezoelectric start-up generator[END_REF]. Here, the load is represented with a resistance whose current is: [START_REF] Dudka | Wideband electrostatic vibration energy harvester (e-veh) having a low start-up voltage employing a high-voltage integrated interface[END_REF] A simplified analysis may be done by analyzing independently the charge flows of the charge pump and of the resistor, and then by superimposing them. The point at which both currents are equal to each other corresponds to steadystate operation. Although it is an approximation based on the averaging method [START_REF] Nayfeh | Introduction to Perturbation Techniques[END_REF], it gives good analytical results.

In the steady state, the average voltage on a period is the same for all cycles. The stability of this mode can be easily proven by supposing a perturbation which yields, for example, . In this case, the load current consumption outweighs the current due to the charge generation by the pump, and decreases. This results in decreasing of , and so in reducing the initial perturbation.

Under these considerations, the average steady-state voltage with resistive flyback can be predetermined by equating ( 23) and [START_REF] Dudka | Wideband electrostatic vibration energy harvester (e-veh) having a low start-up voltage employing a high-voltage integrated interface[END_REF]. Conversely, the value of yielding a desired (for example, that yielding a maximal

) can be calculated. The resistive flyback configuration provides a sustainable energy conversion by preventing the charge pump from the saturation. This is an efficient solution from the point of view of the simplicity of implementation. However, it does not allow an auto-increasing of its internal energy (cf. Section II-C2), and for this reason, is not usable in practical applications.

B. Inductive Flyback 1) Architecture and Operation:

The inductive flyback is a Buck DC-DC converter, transferring energy from to (Fig. 7(a)) [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF]. The flyback operates in two steps: i) When is high so that the efficiency of the charge pump decreases, some external control device (cf. the explanation below) activates the switch , and the current in the inductor starts to increase. This results in: i) charges being transferred from to , so that decreases, ii) the energy previously generated by the charge pump on is transferred to . ii) As the magnitude of decreases, it becomes close to , and the same external device cuts the switch, so that the inductor discharges through the flyback diode onto . This results in a transfer of the inductor energy to , and an increase of the voltage, since the diode is connected to the ground. In this way, the converted energy is used to extract charges from the ground and inject new charges into the charge pump. It can be seen that receives charges twice: in the first phase, it receives the charges previously given to during the pump operation, and in a second phase, it receives new charges from the ground. In this way, receives the energy it has given to during the operation of the charge pump, and it receives the energy converted from the mechanical domain. If such an operation is cyclic, the average voltage and energy of will grow. In this way, two problems are solved: i) even if the capacitors are leaky, the losses are compensated by the charges extracted from the ground, ii) a large capacitor contains the harvested energy available for the load (represented by dotted lines in Fig. 7(a)). If no load is present, accumulates the converted energy, and so implements an "auto-increasing" or "accumulative" mode.

The advantage of the charge pump with inductive flyback is the possibility of a precise control of the QV cycle corresponding to the energy conversion. This is achieved by a modulation of the average voltage so as to remain in the optimal mode for energy conversion.

A drawback of the circuit is the need of an external command for the switch. However, this command is synchronized not with the mobile mass vibrations, but with the evolution of the voltage : firstly, a voltage can easily be measured, and secondly, the evolution is low compared to the period of the capacitance variation. Hence, the cost of such a command is smaller than for circuits implementing constant-voltage or constant-charge QV cycles (cf. Section I). 2) Practical Implementation: In order to take maximum advantage of the charge pump with inductive flyback, a "smart" management of the flyback is required (cf. functional representation in Fig. 7(a)). This was firstly highlighted in [START_REF] Galayko | AMS modeling of controlled switch for design optimization of capacitive vibration energy harvester[END_REF]. The most important issue is the selection of an interval for values, so that , and and are close to . As far as and are chosen, the operation of the switch is ordered by a finite-state machine (Fig. 7(b)), and the evolution of and the average power is given in Fig. 8. The voltage and may be defined as , where is chosen large enough so to minimize the frequency of the switch activation, but at the same time small enough to keep the average power close to the maximal value. By considering [START_REF] Galayko | AMS modeling of controlled switch for design optimization of capacitive vibration energy harvester[END_REF], the reader can verify that the value of the capacitance controls the number of cycles during which the voltage goes from to , and at the same time, the energy that the flyback circuit must transfer from to . A trade-off must be found, as a function of the practical implementation of the whole system. However, is not directly measurable, and this is a fundamental problem. From ( 9), it can be seen that depends on , which is not known a priori in practice, as it depends on the amplitude of the mobile mass vibration (cf. Part 2 of this paper). One of the possible ways to determine is to measure the saturation voltage of a freely run charge pump. This voltage is given by . As it can be seen in Fig. 8, the values of and can just be chosen in-between and , for example,

As far as is known, the calculation on , may be done by simple analog circuits, such as a voltage divider [START_REF] Dudka | Smart integrated conditioning electronics for electrostatic vibration energy harvesters[END_REF]. To determine , the charge pump should be run up to saturation periodically, and the final value should be measured and memorized. This measurement should be periodic, since the vibration amplitude may change with time. We call this technique "auto-calibration," since a periodic re-calculation of and allows an optimal operation of the circuit for a range of parameters of external vibrations.

Practical implementation of adaptive architecture in Fig. 7 is challenged by the relatively low power available for the control Fig. 9. Original schematic of conditioning circuit based on the Bennet's doubler [START_REF] De Queiroz | The doubler of electricity used as battery charger[END_REF]. circuitry, and by the need to manage high voltages in the conditioning circuit. Most studies used an "old" CMOS technology supporting high voltages (e.g., 0.7

CMOS in [START_REF] Kempitiya | Low-power interface IC for tri-plate electrostatic energy converters[END_REF]). The work [START_REF] Dudka | Design of controller IC for asynchronous conditioning circuit of an electrostatic vibration energy harvester[END_REF] used a mixed high-voltage/low-voltage 0.35 CMOS technology, where high voltage circuits are used for the interface with the charge pump, and the processing is done by low voltage parts. This allows a minimization of the power overhead of the control electronics. Implementation of a high-side high voltage MOS switch for the flyback control with a low voltage control interface represented a particular difficulty. An advanced study of a fully integrated CMOS implementation of the control architecture, as in Fig. 7, was presented in [START_REF] Dudka | Smart integrated conditioning electronics for electrostatic vibration energy harvesters[END_REF], [START_REF] Dudka | Design of controller IC for asynchronous conditioning circuit of an electrostatic vibration energy harvester[END_REF]. Although the full IC was not implemented, the circuit was designed up to the layout. Transistor-level simulations highlight a power consumption of the overall smart adaptive circuit with self-calibration of less than 1. [START_REF] Naruse | Electrostatic micro power generation from low-frequency vibration such as human motion[END_REF] .

C. Bennet's Doubler

First introduced at the end of the 18th century [START_REF] Bennet | An account of a doubler of electricity, or a machine by which the least conceivable quantity of positive or negative electricity may be continually doubled, till it becomes perceptible by common electrometers, or visible in sparks[END_REF], the Bennet's doubler of electricity has recently been proposed by Queiroz [START_REF] De Queiroz | The doubler of electricity used as battery charger[END_REF] for capacitive KEH (cf. Fig. 9). Since then, several works have further developed this concept, adapting it to microscale KEH [START_REF] Risquez | Self-biased inductor-less interface circuit for electret-free electrostatic energy harvesters[END_REF]- [START_REF] Dorzhiev | Electret-free micromachined silicon electrostatic vibration energy harvester with the bennet's doubler as conditioning circuit[END_REF].

1) Basic Configuration: Detailed analysis of the mechanism of the energy conversion in the circuit of Fig. 9 has been presented in the papers cited above. Here, emphasis is made on the similarity between this circuit and an idealized charge pump (Fig. 3(a)), and on the application of the analysis developed in Section II-A.

Let's consider as a positive voltage source that can be used to pre-charge when desired. When applied, it also charges to through D2. Then, for several cycles, thanks to the capacitance variation that allows the circuit to overcome the diodes potential gaps, charges through which acts as a charge buffer: when goes to , it absorbs charges from , and when it goes to , the energy of the charges is elevated and the charges are released to . At the end of this transient process, the voltages on capacitors and are equal, with polarities as indicated in Fig. 9. A more detailed description of the transient process for the Bennet's doubler can be found in [START_REF] Dorzhiev | Electret-free micromachined silicon electrostatic vibration energy harvester with the bennet's doubler as conditioning circuit[END_REF].

After the transient, the circuit is in the energy conversion mode, which will be referred to as the steady-state operation mode of the circuit. As shown in [START_REF] De Queiroz | The doubler of electricity used as battery charger[END_REF], this mode shows an avalanche-like growth of the circuit voltages: the energy converted by the circuit in one cycle is distributed among the circuit capacitors, and so increases the circuit initial bias for the next cycle. Since the energy converted in a cycle is proportional to the square of the voltages, both the voltages and the energy in the circuit's capacitors grow exponentially. The steady-state operation is an auto-increasing mode (discussed in Section II-C2), which, contrarily to the charge pump with inductive flyback, does not require an external control.

A similarity between the Bennet's doubler in the steady-state mode and the basic configuration of the charge pump (Fig. 3(a)) can be exposed if the circuit is redrawn as in Fig. 10(a). It can be shown that the conduction of D2 in the steady-state mode is negligible, if (cf. [START_REF] De Queiroz | The doubler of electricity used as battery charger[END_REF]). If D2 is removed and if the fixed capacitors are represented by voltage sources (valid if they are much greater than ), then by equivalent circuit transformations presented in Fig. 10(b)-(d) one obtains an equivalent topology given in Fig. 10(e). The similarity with the network of Fig. 3(a) is obvious if one puts , . Details of the equivalent circuit transformation are given in the legend of Fig. 10.

The QV cycle corresponding to the circuit (Fig. 11) has the parameters:

(26) and since , for this configuration, the relation is fixed as a ratio of 2 by the topology (Fig. 11(a)). The main shortcoming of the basic configuration of the Bennet's doubler is that the ratio must be at least 2 for the operation of the circuit (cf. condition (6)), and transducers implemented in MEMS technology often display lower performances.

2) Generalization of the Circuit: Recent studies highlighted that ratios lower than 2 can be achieved by a modification of the circuit topology. In [START_REF] Risquez | Self-biased inductor-less interface circuit for electret-free electrostatic energy harvesters[END_REF], a voltage multiplier is used in order to define a ratio between and as:

(27) , . The previous analysis done on the basic Bennet's circuit is still valid; the QV cycle is given by substituting ( 27) into ( 26).

This allows one to consider a generalized Bennet's doubler circuit, in which the ratio between and can be any value. To date, only topologies with integer ratios have been implemented, but further investigation may result in the discovery of configurations with non-integer rational ratios. In general, for any and values such that , the energy converted in a cycle by a general Bennet's doubler is obtained by combining ( 5) and ( 26):

(28)

The circuit generates electricity as long as in ( 28) is positive, i.e., when (29) By consequence, the advantage of the Bennet's doubler with voltages and given by ( 27), is a compatibility with transducers having ratio less than 2 if . The corresponding QV cycle is given in Fig. 11.

D. Comparison of Bennet's Doubler and the Charge Pump

The energy conversion yield of circuits implementing rectangular QV cycles was discussed in Section II, and the results are fully applicable to both the circuits based on the charge pump and on the Bennet's doubler. It was shown that the efficiency of the conversion is controlled by the ratio , and that the optimization depends on which one of the two voltages is fixed. However, and are defined differently in the two circuits, and a direct comparison can not be done, unless an application case is defined. We propose to study two cases, which are discussed below. The synthesis of this comparison is given in Table I, which expresses the energy converted during one QV cycle by all circuits considered in this paper.

i) The same fixed voltage is applied on the pre-biased capacitor ( in the chargepump, in the Bennet's doubler). This is a reasonable assumption from the standpoint of practical applications, since the prebiased capacitor is directly connected to an interface with the load, and its voltage is likely to be limited by the transistor technology. Setting , from (28), ( 27) we obtain the energy converted in one cycle by the Bennet's doubler:

(30) The maximal energy produced in a cycle by the charge pump circuit with a fixed is given by [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF], where, for the comparison, should be substituted by . Let us now compare this maximal energy with the value given for (30), for different . If (basic Bennet's doubler), the charge pump is advantageous for any value of (note that for , the basic Bennet's doubler does not work, cf. ( 29)). However, for large (so that can be neglected in (30)), the comparison is mitigated: for the charge pump is more advantageous. However, for the cases where is small and comparable with unity (which is very common with MEMS devices), the Bennet's doubler with multiplication becomes much more interesting. The price to pay for this improvement is a high maximum voltage which should be supported by the transducer and the diodes: it is equal to . ii) For this reason, another case is relevant, when the maximum voltage supported by the transducer is fixed to by the transistor/diode technology, or by the limitations of the electromechanical device. The maximal energy provided by the charge pump at fixed is given by ( 8): For the comparison, should be substituted with . In order to compare the maximal energy yield of the charge pump with that of the Bennet's doubler, and should be expressed through . Setting in (26), we recalculate the voltages of the Bennet's doubler , , and we obtain the energy converted in one cycle:

(31)

The comparison shows that a conventional Bennet's doubler is less advantageous than the charge pump for comparable to unity, and for large they offers equivalent yields. If is large (so that ), the charge pump is still more efficient for , and the Bennet's doubler is only advantageous for . As a conclusion, the Bennet's doubler has a better power yield for cases when is small, a voltage multiplier is used and there is no major limitation on the maximum voltage supported by the devices. In all other cases, the charge pump allows a greater or similar converted power. However, the price to pay for this advantage is the need of an external control for the charge pump and of an inductor which is complicated to integrate. For a steady optimal operation, the voltage should be maintained at its optimal value defined by the ratio, and this costs power and complexity.

IV. EXPERIMENTAL RESULTS Several studies have addressed experimental validation of different circuits with rectangular QV cycle. Most of them implemented the self-increasing operation. The study of this "accumulative" (loadless) mode is particularly interesting, since it provides a characterization of the power conversion for a range of the bias voltage. The value of the converted power is given by the rate of the energy evolution on the reservoir capacitor. In the accumulative mode, the circuits highlights an exponential increase of the voltage on in the charge pump [START_REF] Kempitiya | Low-power interface IC for tri-plate electrostatic energy converters[END_REF], [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF], or on in the Bennet's doubler [START_REF] De Queiroz | The doubler of electricity used as battery charger[END_REF]. In the experiments where macroscopic variable capacitors are used, this increase of voltage reaches hundreds or thousands of volts, provoking an electrical break-down of the used insulator. Few experiments successfully conditioned microscale MEMS devices with circuits implementing rectangular QV cycles [START_REF] Dorzhiev | Mems electrostatic vibration energy harvester without switches and inductive elements[END_REF], [START_REF] Galayko | Capacitive kinetic energy harvesting: System-level engineering challenges[END_REF]. The diagram of the experiment is presented in Fig. 12. The used MEMS device is a micro resonator associated to a capacitive transducer presented and characterized in [START_REF] Basset | Electrostatic vibration energy harvester with combined effect of electrical nonlinearities and mechanical impact[END_REF]. The MEMS device was submitted to sinusoidal external vibrations, with fixed frequency and amplitude. Both Bennet's doubler (Fig. 9) and charge pump based circuit with inductive flyback (Fig. 7(a)) were implemented with discrete elements, and tested with the above mentioned MEMS transducer. In the charge pump circuit, the flyback switch SW was driven by a fixed periodic sequence. Both circuits, when operating in accumulative mode, demonstrated a similar behavior different from the case when a macroscopic variable capacitor was used (cf. Fig. 13). At low bias voltages, the increase of the internal energy is exponential. At moderate and high voltages (above 15 V), the circuit displayed a slowing down and then a saturation of the internal energy of the system. This is because the electrical forces generated by the strongly biased MEMS capacitor interact with the mechanical dynamics of the MEMS resonator. This results in a modification of the resonance frequency, the pull-in phenomena, etc. Such a behavior cannot be explained in the frame of the purely electrical model used in this article. For that reason, the Part 2 of the article presents a methodology of electromechanical analysis of the system, and provides a formal characterisation of the coupled behavior of the harvester.

Fig. 13(a) presents the evolution of the and voltages in a charge pump obtained in the experimental setup described in [START_REF] Dudka | Wideband electrostatic vibration energy harvester (e-veh) having a low start-up voltage employing a high-voltage integrated interface[END_REF], as the switch is driven by a fixed periodic time sequence, as in [START_REF] Yen | A variable-capacitance vibration-to-electric energy harvester[END_REF]. The autocalibration mechanism was not implemented, but since the parameters of the external vibrations were fixed, this time sequence was optimized so to maximize the output power. The evolution of voltage is locally similar to the theoretical behavior presented in Fig. 8.

The originality of this experiment is in the use of an integrated MOS switch implemented in a high voltage 0.35 technology, interfaced with low voltage (3.3 V) command circuit through a ultra low power static level shifter presented in [START_REF] Dudka | Design of controller IC for asynchronous conditioning circuit of an electrostatic vibration energy harvester[END_REF] (cf. discussion at the end of Section III-B).

V. CONCLUSIONS This study, Part 1, presented an original vision unifying the theory of several structurally different conditioning circuits for electrostatic kinetic energy harvesters, by considering the QV cycle as their common and fundamental characteristic. This approach provides a comprehensive methodology for design and optimization, by defining three separate steps: i) selection of the optimal dynamic biasing of the transducer (QV cycle), ii) selection of the architecture implementing it, iii) selection of the optimal electrical mode of this architecture. It was formally shown that the energy yield of the circuits with rectangular QV cycle is determined by the ratio between the extreme voltages and characterizing the cycle geometry. This provides a comprehensive tool for selecting the optimal operation mode as a function of the parameters of the transducer (the ratio ) Fig. 13. Experimental results obtained for: (a) charge pump with inductive flyback, measurement setup is described in [START_REF] Dudka | Wideband electrostatic vibration energy harvester (e-veh) having a low start-up voltage employing a high-voltage integrated interface[END_REF]. (b) Bennet's doubler used with a MEMS device described in [START_REF] Basset | Electrostatic vibration energy harvester with combined effect of electrical nonlinearities and mechanical impact[END_REF]. The parameters of the experiment are given in the plots.

or of the electrical limitations imposed by the technological context (maximal supported voltage, maximum available external DC voltage). The paper considered two families of circuits implementing a rectangular QV cycle: circuits based on the Roundy charge pump, and circuits based on Bennet's doubler. Whereas Bennet's doubler based circuits do not require any external control for steady energy conversion, a charge pump needs to be periodically de-saturated with a flyback circuit, with use of an externally controlled inductive DC-DC converter.

However, the simplicity of implementation of the Bennet's doubler circuit has a cost: an impossibility to adapt its operation to dynamic variation of the ratio . Such a variation is highlighted by both the experiment and the theory; the reason for this variation may be external (variation in the amplitude of the external vibrations) or internal (compressing of the mobile mass amplitude because of the electromechanical coupling). In the both cases, the Roundy charge pump with inductive flyback, when provided with a smart electronics, is able to adapt the voltages and so as to keep an optimal mode of the energy conversion. In the case of the Bennet's doubler, the ratio is defined by the circuit topology, and can not be dynamically modified. For this reason, the Bennet's doubler is only efficient for a specific range of amplitudes of the mobile mass.

The Bennet's doubler with high multiplication factor is particularly interesting in configurations when the ratio is weak: this is a frequent situation with MEMS capacitive transducers, and this topology has a high potential for practical implementations in microscale harvesters.

The analysis presented in this article was made in the electrical domain: it means that the starting hypothesis is a fixed and known law of the transducer's capacitance variation. The latter requires a knowledge of the amplitude of the mobile mass vibrations, which, in turn, requires a coupled analysis of the system in both mechanical and electrical domains. This is the subject of the Part 2 of the paper.

Fig. 1 .

 1 Fig. 1. Structural view of a kinetic energy harvester with capacitive interface.

Fig. 3 .

 3 Fig. 3. Schematic of an ideal conditioning circuit implementing a rectangular charge voltage cycle (a) and the plot of the corresponding QV cycle (b).

Fig. 4 .

 4 Fig. 4. Schematic of a practical charge pump used for the conditioning of capacitive transducers in KEHs. Dotted lines show the configuration with a resistive flyback, cf. Section III-A.

Fig. 5 .

 5 Fig. 5. Succession of charge-voltage cycles as the charge pump operates starting from the state when : the first cycle , the subsequent cycles . If , the cycle is degenerated to a line passing through the points .

Fig. 6 .

 6 Fig. 6. Evolution of the electrical state of the charge pump without flyback. a) Evolution of and voltages, b) Evolution of the total converted energy and of the energy converted at one cycle . The simulation was done with , , , , .

Fig. 7 .

 7 Fig. 7. Conditioning circuit with inductive flyback. (a) The architecture of the circuit: the basic charge pump (as presented in Section II-B), the inductive flyback (grey background, Section III-B), and the architecture of the adaptive control (cf. Section III-B), (b) the finite state automaton explaining the algorithm of the flyback switch control.

Fig. 8 .

 8 Fig. 8. Evolution of dynamic quantities of the charge pump with inductive flyback. The parameters of the circuit used in the simulation are the same as for Fig. 6.

Fig. 10 .

 10 Fig. 10. Demonstration of similarity of the Bennet's doubler operation in the steady-state mode with basic charge pump (Fig. 3(a)): (a) circuit in Fig. 9 redrawn, (b) the same topology presented in steady-state mode without D2 and where the fixed capacitors are replaced by voltage sources; (c) the same circuit with source and swapped, since they are in series, (d) the source "passes" through the bottom node appears in the left and right side branches, (e) the same as (d) redrawn. The topology (e) is equivalent to that of Fig. 3(a) if , .

Fig. 11 .

 11 Fig. 11. (a) QV cycle diagram for the basic configuration of Bennet's doubler [18], QV cycle diagram for the more general Bennet's doubler [19].

Fig. 12 .

 12 Fig. 12. Diagram describing the experiment highlighting the increase of internal energy of considered conditioning circuits in autonomous mode.

Dimitri

  Galayko (M'12) graduated from Odessa State Polytechnich University, Ukraine, in 1998; he received his master degree from Institut of Applied Sciences of Lyon, INSA-LYON, France, in 1999. He created his Ph.D. thesis in the Institute of Microelectronics and Nanotechnologies (IEMN), Lille, France, and received the Ph.D. degree from the University Lille-I in 2002. The topic of his Ph.D. dissertation was the design of microelectromechanical silicon filters and resonators for radiocommunications. Since 2005 he is an Associate Professor at University of Paris VI (UPMC, Sorbonne Universités), France, in the LIP6 laboratory. His research interests include study, modeling, and design of nonlinear integrated circuits for sensor interface and for mixed-signal applications. Andrii Dudka received the M.S. degree in computer science and electronics from Odessa National Polytechnic University, Ukraine, in 2008, and the Ph.D. degree in electrical engineering from the Pierre and Marie Curie University, lab. LIP6, France, in 2014. He is currently a Postdoctoral Researcher at University of Bordeaux, lab. IMS, France. His research interests are in the areas energy harvesting from vibrations, micropower generation and conversion using MEMS devices, analog electronics, and ASICs. Armine Karami was born in Paris, France, in 1991. He received the M.S degree in electrical engineering from Université Pierre et Marie Curie-Paris 6 (UPMC), France, in 2014. He is currently pursuing the Ph.D. degree at Université Pierre et Marie Curie (UPMC)-Paris 6, at the Laboratoire d'Informatique de Paris 6. His Ph.D. research is focused on the theory, conception and analysis of conditioning circuits for vibration energy harvesting.

TABLE I ENERGY

 I CONVERTED DURING A CYCLE BY DIFFERENT CONSIDERED CONDITIONING CIRCUITS IMPLEMENTING RECTANGULAR QV DIAGRAMS, FOR TWO CASES: (I) THE MAXIMAL SUPPORTABLE VOLTAGE IS FIXED , (II) THE INITIAL AVAILABLE PRE-CHARGE VOLTAGE IS FIXED . THE FOLLOWING PARAMETERS ARE USED: For the constant voltage circuit, the available voltage source generates the maximal voltage applied on the transducer during the cycle. Hence, and are the same, and the same formulae are used in the table.Here it is supposed that .


Alban Derrien

Jean-Guillaume Fages
email: jg.fages@cosling.com

Thierry Petit
email: tpetit@wpi.edu

Charles Prud'homme

A Global Constraint for a Tractable Class of Temporal Optimization Problems

This paper is originally motivated by an application where the objective is to generate a video summary, built using intervals extracted from a video source. In this application, the constraints used to select the relevant pieces of intervals are based on Allen's algebra. The best state-of-the-art results are obtained with a small set of ad hoc solution techniques, each specific to one combination of the 13 Allen's relations. Such techniques require some expertise in Constraint Programming. This is a critical issue for video specialists. In this paper, we design a generic constraint, dedicated to a class of temporal problems that covers this case study, among others. ExistAllen takes as arguments a vector of tasks, a set of disjoint intervals and any of the 2 13 combinations of Allen's relations. ExistAllen holds if and only if the tasks are ordered according to their indexes and for any task at least one relation is satisfied, between the task and at least one interval. We design a propagator that achieves bound-consistency in O(n + m), where n is the number of tasks and m the number of intervals. This propagator is suited to any combination of Allen's relations, without any specific tuning. Therefore, using our framework does not require a strong expertise in Constraint Programming. The experiments, performed on real data, confirm the relevance of our approach.

be displayed whereas constraints stem from different considerations: displaying relevant information, balancing the selected content, having nice transitions etc. Then, the CSP may be solved quite efficiently with a Constraint-Programming (CP) solver. At first sight, this seems an easy task.

. As the video summarization gets more sophisticated, all these approaches suffer from the need of specific and often intricate propagators/models. This is a critical issue for video specialists, who are rarely CP experts. Furthermore, one may need to include in her model other features available in state-of-the-art constraint solvers, such as standard global constraints and predefined search strategies. What is missing is a both expressive and efficient global constraint for modeling a relevant class of problems on time intervals.

We introduce the ExistAllen constraint, defined on a vector of tasks T and a set of disjoint intervals I, respectively of size n and m. Given a subset R of Allen's relations [1], ExistAllen is satisfied if and only if the two following properties are satisfied:

Introduction

The study of temporal relations between elements of a process is a very active topic of research, with a wide range of applications: biomedical informatics [START_REF] Bramsen | Finding temporal order in discharge summaries[END_REF][START_REF] Zhou | Methodological review: Temporal reasoning with medical data-a review with emphasis on medical natural language processing[END_REF], law [START_REF] Schilder | Event extraction and temporal reasoning in legal documents[END_REF], media [START_REF] Berrani | Constraint satisfaction programming for video summarization[END_REF][START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF][START_REF] Ibrahim | Temporal relation analysis in audiovisual documents for complementary descriptive information[END_REF] etc. Temporal reasoning enables to analyze the content of a document in order to infer high-level information. In particular, a summary of a tennis match may be generated from the match recording with Artificial Intelligence techniques [START_REF] Berrani | Constraint satisfaction programming for video summarization[END_REF][START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF]. The summarization requires to extract some noticeable time intervals and annotate them with qualitative attributes using signal recognition techniques. Then, the summary generation may be formulated as a Constraint Satisfaction Problem (CSP) where variables are the video segments to

Background

In this section we give some background and fix the notations used in this paper.

Temporal Constraint Networks

Temporal reasoning has been an important research topic for the last thirty years. One may distinguish qualitative temporal reasoning, based on relations between intervals and/or time points, from quantitative reasoning where duration of a given event is represented in a numerical fashion. Allen's algebra [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] represents qualitative temporal knowledge by interval constraint networks. An interval constraint network is a directed graph where nodes represent intervals and edges are labelled with disjunctions of Allen's relations. Table 1 details those relations. Many state-of-the-art papers deal with generic solving techniques and tractability of temporal networks [START_REF] Choueiry | An efficient consistency algorithm for the temporal constraint satisfaction problem[END_REF][START_REF] Dechter | Temporal constraint networks[END_REF][START_REF] Koubarakis | From local to global consistency in temporal constraint networks[END_REF][START_REF] Peter Van Beek | Exact and approximate reasoning about temporal relations[END_REF], including temporal problems with quantified formulas [START_REF] Koubarakis | Querying temporal and spatial constraint networks in PTIME[END_REF][START_REF] Peter | Satisfying first-order constraints about time intervals[END_REF]. Most of these methods make no strong restriction on the constraint network to be solved.

A few techniques, more specialized, focus on optimization problems. The two most related to this paper are the following. Kumar et al. [START_REF] Satish Kumar | Simple temporal problems with taboo regions[END_REF] consider temporal problems with "taboo" regions, minimizing the number of intersections between tasks and a set of fixed intervals. These problems occur in scheduling applications, among others. In the context of video summarization, a recent paper [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF] proposes the idea of using global constraints involving a set of ordered intervals. Each constraint is restricted to one specific relation in the 2 13 combinations of Allen's relations. The propagators are not described.

Constraint Programming (CP)

CP is a problem solving framework where relations between variables are stated in the form of constraints, which together form a constraint network. Each variable x has a domain D(x), whose minimum value is x and maximum value is x. A task T in a set T is an object represented by three integer variables: sT, its starting time, eT, its ending time, and pT, its processing time. The task should satisfy the constraint sT +pT = eT. An interval I in a set I is a fixed task, defined by integer values instead of variables. A propagator is an algorithm associated with a constraint, stated on a set of variables. This propagator removes from domains values that cannot be part of a solution to that constraint. The notion of consistency characterizes propagator effectiveness. In this paper, we consider bound (Z)-consistency [START_REF] Bessière | Constraint propagation[END_REF]. When domains are exclusively represented by their bounds (i.e., have no holes), bound (Z)-consistency ensures that for each variable x, x and x can be part of a solution of the constraint.

The ExistAllen constraint

This section introduces the ExistAllen constraint and its propagator. Let T = {T 1 , T 2 , . . . , T n } be a set of tasks, such that any task T i+1 must be scheduled at or after the end of task T i . Similarly, we define a set of ordered Intervals I = {I 1 , I 2 , . . . , I m }. From a subset R of Allen's relations, ExistAllen ensures that any task in T is related to at least one interval in I.

Definition 1 (ExistAllen). ExistAllen(T , R, I) ⇔ ∀T ∈ T , R∈R I∈I T R I ∧ (∀i, 1 ≤ i < n, sT i+1 ≥ eT i ) Example 1.
When summarizing the video of a tennis match, it may be required that each segment (task) selected to be part the summary contains an applause. Applause intervals can be preprocessed [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF]. Such requirement can then be formulated with a ExistAllen constraint, where T are the selected segments, I are the applause segments and R is set to {f i, di, eq, si}.

A symmetry can be used, where the problem is seen in a mirror: starting variables become ending variables and the lower bounds filtering of the mirror relation is applied to the upper bounds (e.g. starts is propagated onto upper bounds using finishes, see Table 1). Therefore, we put the focus on the algorithms for the lower bounds of starting/ending task variables in T . We consider here that processing times are exclusively updated by the constraints sT + pT = eT.

Basic filtering: one relation, one task, one interval

The basic filtering rule specific to each Allen's relation can be derived from timepoint logic relations [START_REF] Vilain | Readings in qualitative reasoning about physical systems. chapter "Constraint Propagation Algorithms for Temporal Reasoning: A Revised Report[END_REF], in order to state lower and upper bounds of starting and ending times of tasks. For instance, consider a task T ∈ T , an interval I ∈ I, and the relation starts. The relation is satisfied if and only if two conditions are met:

T s I ⇔ sT = sI ∧ eT < eI
The only filtering on the lower bounds of task T induced by the two conditions of relation starts is sT ≥ sI. On the same basis, we define in Table 2 the conditions and filtering rules for the 13 Allen's algebra relations between a task T and an interval I.

A first propagator

We propose a propagator based on two procedures. Again, we only present the algorithms adjusting lower bounds of starting times and ending times. The main procedure, ExistAllenQuadratic (Algorithm 1), takes as arguments the sets T and I and a subset R of Allen's relations. Algorithm 1 considers all tasks in T and checks the relations according to intervals in I. At the end of the procedure, the bounds of variables in T are updated according to the earliest support. If no support has been found, a domain is emptied and the solver raises a failure exception. The order between the tasks is maintained by the procedure propagate at line 10, whose propagation is obvious.

Algorithm 1 calls the procedure AllenAllRelation(Algorithm 2, line 6), which performs the check for one task and one interval, with all the relations in R. In order to define a procedure instead of a function returning a pair of bounds, we use two global variables s * and e * , storing permanently the two lowest adjustments, respectively for the lower bounds of the starting and ending time of the current task. An adjustment of the bound of one such variable is made in Algorithm 2 if and only if the current relation gives a support which is less than the lowest previously computed support.

Require: Global Variable : s * , e * 1: procedure AllenAllRelation(T, R, I) 2: for all r ∈ R do 3:

if checkCondition(T, r, I) then 4:

s * ← min(s * , seekSupportStart(T, r, I)) 5:

e * ← min(e * , seekSupportEnd(T, r, I)) 6:

end if 7:

end for 8: end procedure Algorithm 2: Update of s * and e * .

The function checkCondition(T, r, I) (line 3) returns true if and only if a support can be found. Consider again the example of relation starts. From the condition induced by Table 2, col. 2, we have:

checkCondition(T , s, I) ⇔ sT ≤ sI ∧ sT ≥ sI ∧ eT < eI.
If the conditions are met then a support exists. seekSupportStart(T , s, I) returns the lowest support for the starting time variable, that is, sI. As no filtering is directly induced for the ending time variable, the minimal support returned, for the relation s by seekSupportEnd(T , s, I) is max(eT, sI +pT). For each Allen's algebra relation, the three functions are similarly derived from Table 2.

Lemma 1. The time complexity of Algorithm 1 is in O(n × m).
Proof. As the number of Allen's relations is constant (at most 13), and the call of the three functions (lines 3, 4 and 5 in Algorithm 2) are in O(1), the whole filtering of lower bounds is performed in O(n × m) time complexity.

Theorem 1. The propagator based on Algorithm 1 and its symmetric calls for upper bounds of starting/ending variables in T , ensure bounds(Z)-consistency if processing times are fixed integers.

Proof. After the execution of Algorithm 1, the optimal update has been done for each lower bound, according to the current upper bounds. The filtering of upper bounds is symmetric. Therefore, providing that durations of tasks are fixed, the propagator ensures bound (Z)-consistency when a fixpoint is reached.

A fixpoint is not necessarily reached after running Algorithm 1 twice, once to filter lower bounds and once to filter upper bounds. Indeed, the pass on upper bounds can filter values which were previously supports for lower bounds. Let's consider ExistAllen(T , R, I) depicted in Figure 1

T1

for

T1 on di = [0, 6[ T1 for T1 on d = [2, 4[ T1 = sT 1 = [0, 2], eT 1 = [4,6] T2 T2 = sT 2 = [5, 6], eT 2 = [10, 10] I1 = [1, 5], I2 = [6, 8] I1 I2
Fig. 1. Several phases may be required to get a fixpoint when the processing times of tasks are not fixed.

We now simulate the calls of Algorithm 1 required to reach a fixpoint. No values are filtered during the run of Algorithm 1 on lower bounds, since di provides the minimal support for s T1 , d provides the minimal support for e T1 and di provides the minimal supports for T 2 . On the run of Algorithm 1 on upper bounds, since no relation provides support for 6 from s T2 , the value is removed. The ordering constraint (Algorithm 1, line 10) removes 6 from e T1 . Thus, di is no longer valid to provide a support for T 1 . Consequently, a second call to Algorithm 1 on lower bounds has to be done and the minimal value for s T1 will then be 2, given by relation d.

However, when task processing times are constants, the minimum support of the ending date of an activity is the minimum support of its starting date plus the constant. Therefore, the issue mentioned in the previous example cannot occur. The fixpoint can be reached in two passes. One may note that, in this case, we could improve the algorithm by ordering Allen's relations. As our target application involves variable processing times, we do not detail this simplification.

A linear propagator

This section introduces an improved propagator, running in O(n + m) time complexity.

First, one may observe that the satisfaction of the relation precedes can be done in constant time. Indeed, if a task T can precede the last interval I m , the lower bounds are a support. And if not, task T cannot precede any interval. The same way relation precedes inverse can be symmetrically checked with the first intervals. Therefore, to simplify the presentation and without loss of generality, we now consider that relations p and pi can be isolated and treated separately. For each task, they can be checked in constant time. In this section we exclude them from R.

Second, as the sets T and I are chronologically ordered, we can exploit dominance properties that lead to a linear propagator. We now provide those properties and their proof, as well as the ExistAllenLinear procedure. As in Section 3.2, we focus on lower bounds of starting/ending variables of tasks in T . Property 1. An interval I which starts after a support y for the ending time of a task T cannot provide a support for eT lower than y.

Proof. Consider a task T , R ⊆ {m, mi, o, oi, s, si, d, di, f, f i, eq}, y a support for eT and I an interval, such that y < sI. From filtering rules in Table 2, col. 3, no relation in R provides a support lower than y for eT. Property 2. For any of the relations in {mi, oi, s, si, d, f, eq}, an interval I which starts after a support y for the ending time of a task T cannot provide a support for sT lower than y.

Proof. Similar to proof of Property 1.

Property 3. For any of the relations in {m, o, di, f i}, an interval I which starts after a support for the ending time of a task T can provide a support for sT. The lowest support for T is then given by the interval I in I having the lowest sI.

Proof. Let T be a task and r be a relation, r ∈ R = {m, o, di, f i}, x be a support for sT, y be a support for eT and I be the interval in I with the lowest sI, such that sI > y. For each r ∈ R, we distinguish two cases.

Case 1 (T is related to I with relation r, T r I). As the support for eT is at least sI and no rule on starting time is explicitly defined by r (Table 2, col. 3), then the support for sT is at least sI -pT. Given that all intervals from I are chronologically ordered, no interval greater than I can provide a lower x.

Case 2 (T is not related to I with relation r: ¬(T r I)). Consider the m relation. Task T can meet interval I only if sI ∈ [eT, eT] (Table 2 col. 2). As it exists a support y with a value e * < sI and the relation m is not satisfied, we have eT < sI. Given that all intervals are chronologically ordered, no interval with a greater index can meet the task T . A similar reasoning can be applied to the other relations in R.

Thanks to Properties 1, 2 and 3, we can improve the Algorithm 1 by stopping the iteration over intervals in I for a given task T (Line 6) if e * < sI. We now provide two properties from which, for a given task T, the iteration over intervals in I does not have to always start at the first interval of I. Property 4. An interval I which ends before the ending time of a task T i cannot provide a support for the next task T i+1 .

Proof. Let T i be a task and I an interval such that eI < eT i . Then eI < sT i+1 . T i+1 cannot be in relation with I.

Property 5. Given a task T , there exists at most one interval between the interval I i with the highest ending time such that eI i < eT and the interval I j with the lowest starting time such that sI j > eT.

Proof. Let T be a task, let I i be the interval with the highest eI such that eI < eT, we have then eI i+1 > eT, and let I j be the interval with the lowest sI j such that sI j > eT, we have then sI j-1 < eT. Given that all intervals are chronologically ordered, and that sI j-1 < eI i+1 , we have that j -1 ≤ i + 1, that is j -i ≤ 2. As the difference between indices i and j is at most 2, there is at most one interval between i and j.

Thanks to Properties 4 and 5, we know that the next task cannot be in relation with any interval whose index is lower than or equal to j -2. We can improve the Algorithm 1 by starting the iteration over intervals for a given task at j -1. Proof. The number of evaluated intervals is equal to m+2×(n-1): every time a new task is evaluated, the algorithm goes two intervals back. The new algorithm is then in O(n + m).

Improvements

In this section, we describe three improvements brought to the ExistAllen constraint in order to improve its efficiency in practice.

First, the Algorithm 2 can be adapted to store, for a given task, the index of the first interval which satisfied the conditions of a relation. Indeed, intervals located before that interval do not provide a support for the task (and they will never do in the current search sub-tree). By doing so, useless calls to check-Condition can be avoided since they will always return false. In practice, an operation is added after the line 7 in Algorithm 3 to put in j the maximum between j and the first satisfying interval for the task evaluated. These indices are automatically updated upon backtrack.

Similarly, the tasks whose variables have been modified since the last call of the procedure have to be memorized. Thus, the for-loop (line 3-14 in Algorithm 3) can start from the index of the first modified task. Moreover, following tasks that have not been modified can be skipped safely.

Finally, our generic framework enables to replace some remarkable combinations of the Allen's algebra relations with meta-relations. By doing so, even if the complexity of the Algorithm 3 remains the same, the number of operations made to check conditions and seek supports for the combined relations may be reduced. For instance, a "contains" meta-relation, as described in Example 1, which expresses {f i, di, eq, si}, can save up to three calls of the methods in the for-loop in Algorithm 2, lines 2-7. Note that since {p, pi} are handled in a particular way by the constraint, it is even more efficient to limit the combinations to relations in {m, mi, o, oi, s, si, d, di, f, f i, eq}. Adding meta-relations is easy in our implementation since we use a facade design pattern to define the 13 relations. Some meta-relations may require to define their inverse, in order to filter on upper bounds. This is not the case for "contains", though. Indeed, the mirror relation of f i is si, the mirror relation of si is f i, while the mirror relation of di is di and the mirror relation of eq is eq.

Evaluation

The main contribution of this work is an "expressivity gain", which leads to reducing the investment necessary to build and maintain a model. Nevertheless, it is important to check if this gain does not come at the price of efficiency. In this section, we empirically evaluate the impact of the proposed filtering algorithm. First, we recall the video summarization problem. Second, we show that the expressive ExistAllen constraint we introduced is very competitive with the state-of-the-art dedicated approach.

Problem description

The video summarization problem of [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF] consists in extracting audio-visual features and computing segments from an input video. The goal is to provide a summary of the video. More precisely, they consider tennis match records.

Several features (games, applause, speech, dominant color, etc.) are extracted as a preprocessing step, in order to compute time intervals that describe the video. Then, the problem is to compute segments of the video that will constitute the summary. The number of segments to compute and their minimal and maximal duration are given as parameter, as well as the summary duration. In this case-study, the purpose is to build a tennis match summary with a duration between four and five minutes, composed of ten segments, whose duration varies between 10 and 120 seconds.

In order to obtain a good summary (from the end-user point of view), this process is subject to constraints, such as:

-(1a) a segment should not cut a speech interval, -(1b) a segment should not cut a game interval, - (2)
each selected segment must contain an applause interval, -

) the cardinality of the intersection between the segments and the dominant color intervals must be at least one third of the summary, On the assumption that an applause indicates an interesting action, the presence of applause in the summary must be maximized, i.e., the cardinality of the intersection between the computed segments and the applause time intervals must be as large as possible.

Benchmark

We consider the model implementation as well as a 3-instance dataset (see Table 3) kindly provided by Boukadida et. al. [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF].

The model is encoded using integer variables. A segment is represented by three variables to indicate its start, duration and end. If constraints (1a) and (1b) are easily ensured by forbidding values for the segment start and end variables, most constraints have been encoded using ad hoc propagators. This holds on constraint [START_REF] Berrani | Constraint satisfaction programming for video summarization[END_REF], whereas it could be handled with a single ExistAllen constraint wherein T is the set of selected segments, R is equal to {f i, di, eq, si} and I is the set of applause time intervals. Therefore, to evaluate the practical impact of the linear-time ExistAllen propagator, four models are considered.

1. decomp: constraint ( 2) is explicitly represented by the disjunction depicted in Section 3, Definition 1, using primitive constraints of the solver. 2. allen(n.m): constraint ( 2) is represented by an ExistAllen constraint, using the quadratic propagator presented in section 3.2, 3. allen(n+m): constraint (2) is represented by an ExistAllen constraint, using the linear propagator described in sections 3.3 and 3.4. 4. ad hoc: constraint (2) is represented with the dedicated constraints of [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF].

Such model is given for reference only as neither its complexity nor its consistency level are known.

Each of the four models has been implemented in Choco-3.3.0 [START_REF] Prud'homme | Choco3 Documentation[END_REF]. 4 Each of the instances was executed with a 15 minutes timeout, on a Macbook Pro with 8-core Intel Xeon E5 at 3Ghz running a MacOS 10.10, and Java 1.8.0 25. Each instance was run on its own core, each with up to 4096MB of memory.

In order to compare the efficiency on the four models, we first consider a static search heuristic: the variables representing the segment bounds are selected in a lexicographic order and assigned to their lower bounds. In this way, we ensure that the same search tree is explored, finding the same solutions in the same order, and that only the running time is evaluated. The comparative evaluations of the four models are in reported in Figure 2. Each plot is associated with an instance and indicates the improvement of the objective function over time. Recall that the x-axis are in logscale. The three plots are similar.

First of all, a strict reformulation (decomp) is clearly not competitive with the models with specific constraints: decomp is always the slowest. This has to do with the huge number of constraints and additional variables it requires to express the ExistAllen constraint. As an example in the match M 1 where there are 10 tasks, 271 intervals and 4 relations, each triplet T, R, I is expressed by three new binary constraints, each of them reified by a new boolean variable. Second, the quadratic propagator improves the filtering of a strict reformulation. Third, as expected, the performances are even better with the linear propagator. For information purpose, the results of the ad hoc model (as used in [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF]) are reported. allen(n+m), our generic constraint is shown to be the most effective model, mildly faster than ad hoc. This confirms that our generic linear propagator, besides being expressive and flexible and offering guarantees on its complexity and consistency level, is very efficient in practice.

The four models have also been evaluated with the configuration described in [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF], that is, using Activity-based search [START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF] combined with Propagation-Guided Large Neighborhood Search [START_REF] Perron | Propagation guided large neighborhood search[END_REF]. 5 Due to the intrinsic randomness of ABS and PGLNS, each resolution was run 30 times. Thus, the average objective values are reported in Figure 3. Recall that the x-axis are in logscale. The dynamic strategy offered by the combination of ABS and PGLNS enables to reduce the differences between the various models. Although to a slightly lesser extent, the order between efficiency of the four models is preserved when applying a more aggressive search strategy heuristic.

Conclusion

We introduced ExistAllen, a generic constraint defined on a vector of tasks and a set of disjoint intervals, which applies on any of the 2 13 combinations of Allen's algebra relations. This constraint is useful to tackle many problems related to time intervals, such as the video-summarization problem [START_REF] Boukadida | A novel modeling for video summarization using constraint satisfaction programming[END_REF], used as a case study. From a technical viewpoint, we proposed a generic propagator that achieves bound-consistency in O(n + m) worst-case time, where n is the number of tasks and m the number of intervals, whereas the most natural implementation requires O(n × m) worst-case time. Our experiments demonstrate that using our technique is very competitive with the best ad hoc approach, specific to one particular combination of relations, while being much more expressive.

Future work includes the extension of this approach to several task sets, in order to tackle problems beyond the context of video-summarization. In the Satellite Data Download Management Problem [START_REF] Pralet | Satellite data download management with uncertainty about the generated volumes[END_REF], Earth observation satellites acquire data that need to be downloaded to the ground. The download of data is subject to temporal constraints, such as fitting in visibility windows. Using ExistAllen constraint, the visibility windows are the intervals, the amount of acquired data fixes the duration of the download tasks, and the relation required is during. The tasks can be ordered with respect to the type of acquired data and their need to be scheduled.

  wherein: T = {T 1 = s T1 = [0, 2], p T1 = [2, 4], e T1 = [4,6] , T 2 = s T2 = [5, 6], p T2 = [4, 5], e T2 = [10, 10] }, R = {d, di} and I = {I 1 = [1, 5], I 2 = [6, 8]}.

Algorithm 3 :Theorem 2 .

 32 Linear Algorithm for Main Procedure. By construction, Algorithms 3 and 1 do exactly the same filtering. The time complexity of Algorithm 3 is in O(n + m).

Fig. 2 .Fig. 3 .

 23 Fig.2. Comparative evaluation of decomp, ad hoc, allen(n.m) and allen(n+m) on the three matches M 1, M 2 and M 3 with a static search heuristic. The plots report the evolution of the objective value to be maximized with respect to the cpu time in seconds. The x-axis are in logscale.

Table 1 .

 1 Allen's temporal algebra relations.

Table 2 .

 2 Allen's algebra lower bound filtering on each variable of a task T .

	Relation Conditions Filtering	Relation Conditions Filtering
	T p I T pi I	eT < sI eI < sT	sT > eI	T si I	sT = sI eT > eI	sT ≥ sI eT > eI
	T m I T mi I sT = eI eT = sI	eT ≥ sI sT ≥ eI	T d I	sT > sI eT < eI	sT > sI
	T o I	sT < sI eT < eI		T di I	sT < sI eT > eI	eT > eI
		eT > sI sT < eI	eT > sI	T f I	sT > sI eT = eI	sT > sI eT ≥ eI
	T oi I	sT > sI eT > eI	sT > sI eT > eI	T f i I	sT < sI eT = eI	eT ≥ eI
	T s I	sT = sI eT < eI	sT ≥ sI	T eq I	sT = sI eT = eI	sT ≥ sI eT ≥ eI

Table 3 .

 3 Match features.

	Name Total duration # Speech # Applause # Dominant color # Games
	M1	2h08	571	271	1323	156
	M2	1h22	332	116	101	66
	M3	3h03	726	383	223	194

http://www.choco-solver.org

The configuration for ABS and PGLNS are the default one described in[START_REF] Michel | Activity-based search for black-box constraint programming solvers[END_REF] and[START_REF] Perron | Propagation guided large neighborhood search[END_REF].

Acknowledgements The authors thank Haykel Boukadida, Sid-Ahmed Berrani and Patrick Gros for helping us modeling the tennis match summarization problem and for having providing us their dataset.