Hakim Mabed
email: hmabed@femto-st.fr

Eugen Dedu
email: eugen.dedu@femto-st.fr

Haithem Skima
email: haithem.skima@femto-st.fr

Multicriteria Optimization in Distributed Micro-Conveying Platform

Keywords: Multicriteria conveying problem, distributed MEMS system, distributed algorithms, shortest path

In this paper, we study the optimal use of a conveying surface, called smart surface, using distributed microrobotic system that is designed to manipulate fragile micro objects. The smart surface is composed of a 2D array of decentralized micro-modules. Each micro-module is composed of a microactuator, a microsensor, computing and communication units. The cooperation among these micro-modules allows the micro-object to be accurately located and moved on the surface. We discuss in this paper the algorithmic solutions that allow the system to determine the best path to move an object from an initial to a target position in the surface. The optimality of the path is evaluated according to two different and complementary criteria corresponding to short and long term visions. The short term vision optimizes on the speed of conveyance. The long term vision optimizes on the lifespan of the system and maintenance issues. We describe the best way to deal with these two aspects and their impact on the smart surface performance. The results observed confirm the improvement of smart surface performance compared to a naive approach, with a gain in lifespan of up to 160% and good objects transfer times.

INTRODUCTION

A conveyor represents a mechanical equipment that allows the transportation and/or manipulation of various kinds of materials. The use of conveyors is profitable in many operations such as the transportation of imposing objects [START_REF] Pang | Large-scale conveyor belt system maintenance decision-making by using fuzzy causal modeling[END_REF] or tiny and fragile components [START_REF] Helin | Micro-conveying station for assembly of micro-components[END_REF][START_REF] Edo | Two-dimensional micro conveyer with integrated electrostatic actuators[END_REF]. They are useful for their quick and efficient transportation with a wide variety Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

SAC 2017,April 03-07, 2017, Marrakech, Morocco

Copyright 2017 ACM 978-1-4503-4486-9/17/04. . . $15.00 http://dx.doi.org/10.1145/3019612.3019704 of materials, which makes them very popular in the materials handling, assembling and packaging industries. The conveying systems differ according to the used mechanisms, summarized by M. G. Kay [START_REF] Kay | Material handling equipment[END_REF] in 19 different technologies, including the chain conveyor, wheel conveyor, flat belt conveyor, magnetic belt conveyor, bucket conveyor, vibrating conveyor, pneumatic conveyor, etc. Using conveyors is much safer than using a forklift or other machines, and the absence of human intervention makes them a less strenuous and less expensive alternative.

A smart surface [START_REF] Boutoustous | Distributed control architecture for smart surfaces[END_REF] is a distributed surface composed of numerous Micro-Electro-Mechanical System (MEMS) developed for the transportation of microscopic objects over short distances. A grid of MEMS microblocks composed of microsensors, microactuators and control units collaborate to move the objects to target locations 1 . The smart surface conveying system presents two main advantages. First, contactbased technologies are not appropriate for fragile and tiny micro-objects (medicines, micro-electronics parts, etc.), which can be easily damaged, contaminated or even scratched during conveyance. Thus, systems based on air-jet technology [START_REF] Konishi | A conveyance system using air flow based on the concept of distributed micro motion systems[END_REF][START_REF] Dahroug | Design, modeling and control of a modular contactless wafer handling system[END_REF][START_REF] Fukuta | fabrication, and control of mems-based actuator arrays for air-flow distributed micromanipulation[END_REF] such as smart-surface system avoid contact with conveyed objects and provide safer manipulation conditions. Second, a conveyor usually consists of a single monolithic block dedicated to a specific task in a fixed environment. As a consequence, when a failure occurs on a component of the system, the system becomes unable to perform the dedicated task and has to be replaced. The modularity of the smart surface system results in self-reconfiguration features (different paths to convey the object until its destination location) and leads to better flexibility and fault tolerance. The distributed approach compared to a centralized one (e.g. external computational resource) provides scalability and fault tolerance.

In this work, we aim to increase the efficiency of future production lines. The conveying principle consists in sending micro-objects from a start block to a final destination using controlled air flow coming from MEMS valves. To do so, the degradation of all MEMS valves involved in the object transport has to be controlled [START_REF] Medjaher | Condition assessment and fault prognostics of microelectromechanical systems[END_REF]. MEMS components suffer from various failure mechanisms [START_REF] Tanner | MEMS reliability: Where are we now?[END_REF][START_REF] Shea | Reliability of MEMS for space applications[END_REF] which impact their performance and reduce their lifespan. This highlights the need to monitor their behavior and estimate their remaining time before failure (RUL, Remaining Useful Life), and take appropriate decisions accordingly, such as reconfiguration and maintenance [START_REF] Skima | Hybrid prognostic approach for micro-electro-mechanical systems[END_REF]. These tasks are studied using Prognostics and Health Management (PHM) approaches [START_REF] Jay | Prognostics and health management design for rotary machinery systems reviews, methodology and applications[END_REF][START_REF] Javed | A robust and reliable data-driven prognostics approach based on extreme learning machine and fuzzy clustering[END_REF][START_REF] Medjaher | Hybrid prognostic method applied to mechatronic systems[END_REF]. This paper does not address the PHM aspect, but only the algorithmic solution allowing to coordinate blocks' actions in order to optimally convey the objects. The next section presents research works related to similar problems and emphasizes the particularity of the conveying problem in smart surface system. Section 3 summarizes the main contributions and major highlights of this work. Section 4 presents the distributed MEMS-based surface. Section 5 describes the scalable distributed algorithm used for optimizing the conveying path. Section 6 presents the studied criteria to manage the tradeoff between system lifespan and object transfer time. Section 7 introduces the test simulator and presents the simulation results. The last section concludes the paper.

RELATED WORK

Increasing conveying system lifetime by carefully choosing paths presents some similarities with intelligent transportation problems. The energy-saving question in multi-hop wireless networks [START_REF] Blough | Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks[END_REF][START_REF] Floréen | Lifetime maximization for multicasting in energy-constrained wireless networks. Selected Areas in Communications[END_REF][START_REF] Kang | On lifetime extension and route stabilization of energy-efficient broadcast routing over MANET[END_REF] is one of these problems. During packet routing, some nodes are used more often than others, and their energy may be exhausted faster the others. To avoid this, packets need to be routed through paths which optimize the energy of nodes in the network. The problem is different from smart surface conveying problem. In the network case, sources and destinations are spread over the whole surface, whereas in conveyors only one or a few nodes (usually on the border of the surface) can act as source or destination, leading to specific usage patterns. In addition the reuse of blocks also leads to longer transfer time due to degradation effects, which is not the case in multi-hop wireless network.

Finding optimal paths in road systems is another similar problem [START_REF] Huang | Optimal paths in dynamic networks with dependent random link travel times[END_REF]. In both problems, external conditions such as road accidents or dust on the smart surface, affect the system characteristics (transfer time of the MEMS blocks or the traffic speed on the roads). There are differences between these problems. In road networks, many cars circulate at the same time. As a result, the traffic flow propagates in both time and space. This sometimes leads to congestion. Instead, in our conveying problem, objects are introduced in sequence and only one object at a time exists on the surface. Secondly, the road infrastructure lifespan is not immediately impacted by the traffic while the lifespan of the smart surface is partially determined by block use. Finally, the road planner is a centralized computing unit with considerable capabilities, while the path optimization is a distributed process since the MEMS blocks have limited memory and computing capacity.

CONTRIBUTIONS

As previously mentioned, even though the principles are the same, each problem has its own features and from this point of view the smart-surface conveying problem is an original one. The distributed nature of the path optimization algorithm is a real challenge. We ensure that the algorithm, run by each block is scalable with a memory and computational complexity less than O(m) (m is the number of blocks). Furthermore, the convergence of the algorithm is ensured with a time complexity O(m). Additionally, to the best of our knowledge, no article in the literature deals with increasing conveyor lifespan by avoiding overused blocks.

The paper present an original study about how to manage the tradeoff between the short-term performance of the surface (transfer time of an object) and the long-term performance (surface lifespan). The work presented here focuses on sequential conveying system where a new object is introduced one the precedent object is removed from the surface. This assumption allow us to ignore, at this stage, the physical conflicts between objects (collision problem).

THE DISTRIBUTED MEMS-BASED CON-VEYOR

The conveying surface is composed of a 2D array of decentralized micro-blocks, see Fig. 1. Each block includes a sensor to detect whether an object is above it, an actuator as a MEMS valve, a micro-controller executing code, a power supplier, and a network module allowing communication with its four neighboring blocks. The valves generate air, which allows objects above it to be moved from one point to another.

Let's consider a smart surface composed of m blocks, each one including a MEMS valve. The number of cycles of a block b, C(b), represents the number of objects that the block has already moved to an adjacent position. Every MEMS block is defined by two dynamic values: the RUL and the transfer time. The RUL (remaining useful life) designates the expected remaining number of times that the block could be used before it fails. In real world scenarios, this value is computed in real-time, using the current health state of the block and the formula obtained in the learning step (an offline initial procedure where the behavior of the block is observed); this is studied by Prognostics and Health Monitoring (PHM) field. The transfer time of a given block is the time needed to move an object from the given block to the adjacent one, and depends on valve state, e.g. the more the valve is used, the less it opens to allow the air to push the object. These two values are subject to variations over time due to a variety of causes. According to the degradation model, criteria such as transfer time of the last object(s), number of uses, frequency of uses and last use date can be considered to forecast the RUL and next transfer time on a given block. Section 7 describes the degradation model used in tests to measure the remaining time before failure of a given block and the transfer time of the block.

In this work, we propose a distributed protocol that allows the surface to determine, in real time, the best itinerary between the current position of an object and its target position. Each time the surface detects an object to move to a given final position, the system computes the best path that reduces the transfer time of the current object while preserving the system lifetime. The distributed conveyance procedure allows each block to determine the neighbor to send the object to if the object crosses it. The conveying procedure called by each block aims to reduce the time to reach the final position and extend the surface lifespan. Whereas the reduction of transfer time is clearly identified as the sum of the transfer time over all the blocks within the path:

T (p) = ∑ b∈p T (b) (1)
the evaluation of the system lifespan on the basis of RU L(b) values is a complex question. Therefore, in this paper we study different measurement functions of the RUL of a path.

In the same manner, each block tries to optimize the RUL of the remaining path before reaching the final position. The RU L of a path p starting from block b1st is computed using the recursive function RU L(p) described in equation 2, where F is a function to be defined:

RU L(p) = F (RU L(p -{b1st}), RU L(b1st)) (2)
F is an increasing or decreasing monotonic function that should be defined in such manner that it respects the following condition:

RU L(p)    ≤ or ≥    F (RU L(p), RU L(b)) (3)
where the comparison operator is constant, either ≤ or ≥.

The monotonicity is needed to avoid aberrant situations where adding a loop to a given path may improve its evaluation according to the chosen function F .

To convey an object, a block can communicate only with its four neighbors and can send the object to only one of them.

When the object reaches its destination, it gets out of the surface, and a new object enters the system.

MULTICRITERIA DISTRIBUTED CON-VEYING ALGORITHM

As already stated, our problem presents similarities with the problem of finding the shortest path in a graph. Hence, we decide to reuse the well known Dijkstra's algorithm. According to literature, Dijkstra's algorithm has the smallest complexity among all the algorithms finding the optimal solution. However, Dijkstra's algorithm was conceived for mono-criterion problems. Hence it needs to be adapted to fit our multi-criteria problem.

The distributed Dijkstra approach consists in comparing the best current path with a new path provided by a neighbor, and do this for each node (Algo. 1, line 8). The comparison procedure between two different paths is one of the key aspects in the model discussed in the simulation section. This point defines the selection policy among two potential solutions evaluated according to two numerical criteria, especially when no dominated solution exists.

Definition 1. Let s1 and s2 two potential solutions (paths in our case) and let (f1, ..., fn) be n evaluation criteria. s1 is said dominating s2 if and only if:

• ∀fi, fi(s1) is better or equal than fi(s2) and

• ∃fj, fj(s1) is better than fj(s2)
In our distributed algorithm, each block stores only its own RU L and T , called myRU L and myT , and determines only its next block to reach the dest position. The memory complexity of the algorithm is reduced to a constant value O(1), making the algorithm scalable. The broadcasting of the state changes of a block is unneeded, hence there is no update message. The complete optimal path is not stored by any block, only the next position is known. Therefore, at the end of the algorithm, every block knows, in advance, where to move the object (next) when it is detected above the block.

Our algorithm is presented in Algo. 1, in which the yet to be defined function F is the one given in eq. 2. The different partitions of the path are explored and compared in parallel by blocks to provide the best path, thus reducing the CPU time of the procedure. Each block that receives an OP T IM IZE message from a neighbor compares the path (between the neighbor and the dest) with the best ever known. If the new path is better, the considered block sends an OP T IM IZE message to the other neighbors (different from the sender) to inform them about this new best path.

Termination condition

In the absence of a global knowledge of the system state, the distributed procedure requires a termination condition that ensures that no better path would be found by the neighbors. To this end, two solutions can be used. In the first solution, the worst case is studied to determine the limit of time after which no new path would be found. This worst case happens when the best conveying path, according to F , corresponds to the longest path in terms of number of blocks. Fig. 2 shows three examples of the worst case. These cases occur when the best path includes slightly more than half of the surface blocks. Numerous simulations and bibliographic research showed that the longest path in terms of the number of blocks cannot exceed the value M axP athLength:

M axP athLength = m 2 + max ( x 2 + ỹ, y 2 + x) (4)
where x, y are respectively the number of columns and lines of the surface (x × y = m) and Ñ is equal to N if N is odd and 0 otherwise ( Ñ = N × N %2).

Proof. Let's consider the worst case described at the right of Fig. 2, where the best found path between the starting and the final blocks follows a zigzag (snake) pattern which represents the longest path in the x × y matrix [START_REF] Keshavarz-Kohjerdi | An efficient parallel algorithm for the longest path problem in meshes[END_REF]. In the worst case, the massively distributed algorithm converges when the longest path, which is also the best path, is evaluated. Let's consider a horizontal zigzag pattern. The path is composed of y/2 or y/2 + 1 lines (depending on whether the number of lines is even or odd) plus y/2 blocks to link the lines. The longest path length is then (y/2 + y%2)x + y/2. On the contrary, if the zigzag pattern is vertical, the longest path length is (x/2 + x%2)y + x/2.

We assume that a message sent during one round of the computing process is available during the next round at the receiver. Therefore the algorithm will be run on each block M axP athLength rounds. The time complexity of the algorithm is then O(m 1 2 ), including potentially many idle rounds that do not consume energy (rounds with no new received message).

The second solution to ensure the termination of the algorithm is to limit the program execution to M axRounds ≪ M axP athLength rounds. Indeed, long paths, even if they satisfy the optimization criteria, increase the long-term degradation of the surface since many blocks are used. Therefore the importance of optimal resolution of the problem should be put into proper perspective by constraining the conveying path length. The execution time of the algorithm is then improved without really impacting the solution quality. In our tests we set M axRounds to twice the direct trajectory length between the source and the destination of the object, bringing the time complexity of the algorithm to O(m):

M axRounds = 2 × d M anhattan
(5)

OPTIMIZATION CRITERIA

The aforementioned algorithm uses an objective function F which computes the quality of a given path in order to select the best one (the maximum or minimum). In this section, we analyze the best way to combine the two criteria (RU L and T ) within a single function. The choice of the objective function is a key factor of the efficiency of the proposed solution.

It determines the desired trade-off between the short-term (fast object conveyance) and the long-term vision (high system lifespan). The objective function determines also how the lifetime notion measured for each block is extended to measure the global degradation of the system, and especially the impact of a given conveying path on the system durability. In the following paragraphs, we present the different objective functions.

Direct line

In this case, the notion of RU L and T are completely ignored and a naive approach is adopted consisting in the direct line linking the source and the destination blocks. Therefore the Dijkstra's algorithm is not used and no optimization criteria is needed.

MaxMin RUL function

min p RU L(p) = min p ∑ b∈p β C(b) ( 7
)
where β is a numerical parameter to be defined. The use of the function power aims to favor the selection of blocks with lower usage by minimizing the value of the function.

Minimum transfer time function

The chosen path is the fastest path, i.e. with the minimum transfer time to convey an object from source to destination, no matter the RUL of path's blocks:

min p T (p) = min p ∑ b∈p T (b) (8)

SIMULATION AND ANALYSIS

In this section, we present the simulator and the scenarios used, and compare the different objective functions presented above.

Scenarios

A scenario is defined by the dimensions of the surface, n × n = m, by the generation rule of the initial and final positions of the objects, and by the degradation model of the system. We simulate surfaces of dimension 6 × 6, 10 × 10, 15 × 15 and 20 × 20.

We also consider two kinds of rules which select randomly the initial and final positions of objects: in the first rule, source and destination can be any block on the surface; in the second rule, the source is on an edge of the surface and the destination on another edge. The first rule refers to manipulation or placement applications while the second rule fits sorting applications.

We use a simple model to estimate the Remaining Useful Life of a given block. In this model, a block is conceived to be usable a given number of times, Cmax, corresponding to its theoretic capacity (the number of times that the airjet valve can be activated to move an object before being revised or replaced). Therefore, the remaining time before failure of the surface is determined according to the number of uses of each block. The conceptual capacity Cmax of the blocks is known and given by the constructor.

RU L(b) = Cmax -C(b) (9)
We also consider two transfer time degradation models. The first one is a dummy model, also used in [START_REF] Skima | Optimal path evolution in a dynamic distributed {MEMS}-based conveyor[END_REF], where a block transfer time is linearly degraded when the block is used, so each time a block is crossed by an object, the transfer time increases by a constant value α:

T (b) = T0 + αC(b) (10)
The second degradation model is a more realistic model, based on experimental results [START_REF] Skima | A hybrid prognostics approach for MEMS: From real measurements to remaining useful life estimation[END_REF]. In our case, we introduce a probabilistic degradation effect modeled by an exponential distribution with mean α. The transfer time of a block b is simulated by a recursive function where after each activation of a block, its transfer time is degraded as follows:

T (b) = T (b) -α log(RN D) (11)
where RN D is a random value uniformly selected in [0,1].

In the following, we refer to a scenario by the notation n : GEN : DEG, where n × n is the dimension of the surface, GEN ∈ {any, edge} is the generation rule of the objects, and DEG ∈ {lin, exp} is the degradation model used.

Simulator

We implemented a simulator in VBA Microsoft Excel. It executes a given scenario until a maintenance procedure is required as a result of a block degradation (∃b, RU L(b) = 0). The simulator algorithm is described in Algo. 2.

In all tests, we used the following parameters: Cmax = 100, T0 = 1 s, α = 10 s, and the parameter in powers functions Algorithm 2 Procedure of simulating a scenario. Require: n, GEN, DEG 1: while no need for maintenance do 2: a new object enters the surface at initial and final position given by GEN method 3:

run the distributed algorithm to convey the object 4:

update C, RUL and transfer time values according to DEG method 5:

object gets out of the surface 6: end while is β = 1.04. The initial surface is new, i.e. C(b) = 0 for all blocks.

Optimization Criteria Comparison

In this section we test and discuss the advantages and disadvantages of the different objective functions presented before. We consider each of the objective functions for 16 scenarios. A comparison is made on the basis of the number of conveyed objects, the average transfer time of conveyed objects, and the average transfer time of only the first 200 conveyed objects. The latter is important since a surface which conveys many objects will clearly be more degraded at the end than a surface which only conveys a few objects. Also, the average on the first 200 objects allows to assess the conveyance rapidity during the starting period of the system. The good performance of the powers function can be explained mainly by the penalization of the use of overused blocks. The idea is to ensure that the distributed algorithm prefers to use b rather than b ′ if C(b) < C(b ′ ). The Powers function represents, therefore, a good tradeoff between the MaxMin function and a hypothetical average RUL function. An example is given in figure 5. According to MaxMin function, the bottom left path is the best with a minimum RUL equal to 14 (against 12 and 13 for the two other paths). However this path is clearly the worst since it crosses 7 blocks with low RUL. According to the average RUL function, the middle and the top right paths are equal, whereas using the power function, the top right path will be preferred because the use of the block with RUL=12 is more penalized.

The direct line function provides the worst results. Results show that central blocks are much more frequently used than edge blocks, making the system falls sooner. The good results of direct line function according to the average transfer time are due to few conveyed objects, which shows that direct line method leads to a heterogeneous use of the surface. In terms of average transfer time, the functions emphasiz- ing transfer time (Min time function) provide the best results. However, this criterion alone is not sufficient, since, as stated in the beginning of the section, a function, such as powers, which conveys more objects is penalized compared to a function, such as average time, which conveys fewer objects; indeed, last conveyed objects take more time than first conveyed objects, due to the surface degradation. To complete this comparison we should also consider the average transfer time of the first 200 objects. In this case, power function provides good results. For example in scenario 15:any:exp, power function conveys the first 200 objects in an average time of 57 s, while minimum transfer time function conveys the first 200 objects in an average time of 56 s (just one second of difference).

CONCLUSION AND PERSPECTIVES

In this paper we studied the problem of conveying objects on a 2D distributed MEMS surface called smart surface. Despite some similarities with well known problems in transportation and communication fields, the problem remains particular. This particularity is due to the millimetric scale of the system, inducing hardware and software constraints (memory storage, computing capabilities), and to the degradation phenomena observed on the MEMS modules. Degradation effects make that a path to convey an object could be good at a given moment and become bad later. Therefore we proposed a bicriteria model that takes into account a short-term objective consisting to convey the current object as soon as possible to its final position, and a long-term objective related to the extension of the system lifespan.

We proposed a scalable (in terms of computational and memory complexity) distributed algorithm to optimize the conveying path and we studied different ways to combine the shortterm and long-term criteria within a single objective function used by the optimization algorithm. We proved that methods based on the progressive penalization of the overused blocks provide best results.

The results obtained are encouraging since the lifespan of the system is extended by up to 160% without reducing conveying speed. On the contrary, unbalanced use of the surface blocks provokes the reduction of conveying speed. The relationship between the number of use cycles and the degradation of the transfer time determines the suitable tradeoff between the RUL and transfer time criteria. We have analyzed two different degradation models defining this relationship. However, other phenomena that could potentially impact the degradation level should be studied, such as the frequency of use, the non-use of a block for long periods, etc.

Two major studies are needed to complete this work. First of all, how to adapt the model and the distributed algorithm to take into account the presence of concurrent objects above the surface. Secondly, we need to introduce the number of orientation changes in the object's followed path as a third criterion to minimize. Indeed, every orientation change implies to stop the object and then start it in the new direction, and both stopping and restarting the movement consume energy and time.

Figure 1 :

 1 Figure 1: The conveyor and the path taken by an object from S to D.

Figure 2 :

 2 Figure 2: Three examples of conveying algorithm worst case. 'S' represents the starting block and 'D' the destination block.

6 )

 6 In MaxMin funtion, the path RUL is equal to the smallest RUL in the path (eq. 6). The objective is to find the path with the highest value of RU L. RU L(p) and RU L(p ′ ) are compared to determine which path, p or p ′ , is better. If RU L(p) and RU L(p ′ ) are equal then the path with a better transfer time is taken. max p RU L(p) = max p min b∈p RU L(b) (Powers function The RUL of a path corresponds to the sum of β C(b) over the blocks of the path:

Figure 3 :

 3 Figure 3: Comparison of different objective functions.

Figure 4 :

 4 Figure 4: Numerical values refer to RU L(b). In (a) the dark left path is better according to the minimum RUL value (34 against 33), but when using this path many worn blocks become even more worn. In (b) the two paths are equal according to the minimum RUL value (40), but the light right path is better since its blocks have generally higher values.

Figure 5 :

 5 Figure 5: Numerical values refer to RU L(b). The bottom left path is the path selected by MaxMin function even if it is the longest one. The sum of RULs of blocks (path RUL) is identical for the middle and top right paths. In contrast, using powers, the top right path is preferred since crossing the block with RUL=12 is more penalizing.

  Figure3shows the results of this comparison. The functions based on the entire path's blocks such as powers function are better than the functions based on a part of the path, such as MaxMin function. Trying at any cost to avoid overused blocks leads to more crossed blocks with only marginally less degradation (see Fig.4.a). Furthermore, the maximum block use does not capture the values of the other blocks in the path. Thus, two paths with equal minimum block RUL can be completely different when considering all the blocks of the path (see fig.4.b). In some cases, generated paths are longer, leading to many blocks used every time. With the scenarios based on linear degradation, the Min time function performs slightly better than power function. The reason for this is that, in such scenarios, path transfer time is strongly correlated with the path sum of RUL (eq. 9 and 10). However, in exponential degradation scenarios (where RUL and time functions are less correlated), the Min time function provides clearly worse results than the power function.

	S 45 56 75 88 33	S 55 41 65
	37	59	40	66 53 40
	35 36 34 34	43	45 47 40	63
	35	47	47	62
	36	53	41	54
	37 34 D	50 42 44 D
	(a)		(b)

Smart Surface is a research project (ANR 06 ROBO 0009) supported by French National Research Agency (ANR).


Kamran Javed

Rafael Gouriveau

Noureddine Zerhouni

Daniel Hissel

PEM fuel cell prognostics under variable load: a data-driven ensemble with new incremental learning

Proton Exchange Membrane Fuel cells (PEMFC) are one of the most promising fuel cell technologies, which qualify for variety of applications as power generation source. The Prognostics & Health Management of fuel cell is an emerging field, which is paving the way for large scale industrial deployment of PEMFC technology. More precisely, prognostics of PEMFC become a major area of focus nowadays that enables predicting the behavior of PEMFC to produce actionable information to extend its life span. This paper contributes the first application on data-driven prognostics of PEMFC stack under variable load for combined heat and power generation (µCHP). In brief, an ensemble structure of Summation Wavelet-Extreme Learning Machine models is proposed with a new incremental learning scheme, to achieve long-term predictions on stack state of health (SOH) and to give confidence for better decisions. The proposed prognostics model is validated on data from PEMFC stack used for a µCHP application under variable load profile for a complete year. A thorough comparison on SOH predictions results clearly shows the significance of proposed prognostics model, which can predict with few learning data for a long-term prognostics horizon around 650 hours with high accuracy and low uncertainty.

I. INTRODUCTION

Fuel cell (FC) is an energy system that offer clean and efficient way to generate electricity. The PEMFCs are considered the most versatile among available fuel cell technologies due to the advantages like: low operating temperature, high energy output and low pollutant emissions [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF]. Hence, due to those advantages, PEMFCs qualify as a promising source for power generation for stationary, portable, and transportation applications, Fig. 1. However, FC aging is an unavoidable process, the optimization of its service and minimization of its life cycle costs/ risks require continuous monitoring of the degradation process and accurate prediction of its future behavior to enable timely decisions. In this context, Prognostics and Health Management (PHM) of FCs is an emerging field, which aims extending their life span, while reducing exploitation and maintenance costs. Therefore, paving the way for large scale industrial deployment of PEMFC technology. More precisely, PEMFC prognostics becomes a major area of focus nowadays, as a key task in PHM cycle with future capabilities. In brief, prognostics uses condition monitoring data (CM) from PEMFC stack (i.e., assembly of elementary cells) to identify degradation at early stages, to predict long-term behavior and to estimate its remaining useful life (RUL). This will enable, short term, medium term or long term decisions to prolong the life span of the fuel cell/ stack. Such decisions can be related to control, maintenance or changing mission profiles. According to author's knowledge, few works have been published on prognostics of PEMFC on stack level. Those works can be classified into two main categories, 1) prognostics under constant load current, and 2) prognostics under variable loads current. The methods that belong to the first category are data-driven prognostics approaches, namely: Summation-Wavelet Extreme Learning Machine [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF], Echo state network (ESN) [START_REF] Morando | Fuel cells prognostics using echo state network[END_REF], Adaptive Neuro-Fuzzy Inference System (ANFIS) [START_REF] Silva | Proton exchange membrane fuel cell degradation prediction based on adaptive neuro-fuzzy inference systems[END_REF] and Particle Filtering framework [START_REF] Jouin | Prognostics of pem fuel cell in a particle filtering framework[END_REF]. In the second category only one method has been published using a hybrid prognostics approach on PEMFC for a stationary application for combined heat and power for small buildings (µCHP) Fig. 1, [START_REF] Jouin | Prognostics of prm fuel cells under a combined heat and power profile[END_REF]. Unfortunately, no work has been done so far on datadriven prognostics of PEMFC under variable load. This is due to quantity and quality CM data from PEMFC stack, which prevents building data-driven model that are robust enough to manage the uncertainty of data and modeling phase. Also data-driven approaches under constant loads are mainly based on the assumption that stack aging is irreversible degradation, which limits applicability of those methods for variable load. To address those issues, this paper presents first application on data-driven prognostics of PEMFC under variable load current for µCHP. In brief, a data-driven ensemble of Summation Wavelet-Extreme Learning Machine models is proposed with new incremental learning scheme to improve the adaptability of the model (online), to achieve accurate long-term predictions of PEMFC state of health (SOH) and to give confidence to predictions. The main contributions of this development are:

• ensemble structure to manage uncertainty;

• incremental learning to improve adaptability;

• application on PEMFC stack under variable load.

The remaining paper is organized as follows. Section II elaborates issues related to CM data under constant vs. variable loads and modeling. It also highlights the importance of incremental learning and uncertainty related tasks for prognostics. Section III presents the proposed data-driven connectionist ensemble with incremental learning scheme. Section IV validates our proposition on PEMFC stack under variable loads for µCHP and compares with hybrid approach [START_REF] Jouin | Prognostics of prm fuel cells under a combined heat and power profile[END_REF]. Section V concludes this work and gives future perspectives.

II. CM DATA, MODELING, UNCERTAINTY: CHALLENGES

The CM data are fundamental to implement a right model for health assessment, prognostics and to estimate its parameters. Such data are collected at regular intervals through a procedure of monitoring carefully selected parameters of health condition/ state of the equipment. CM data that can be continuously measured (or acquired), controlled and economically possible from PEMFC stack are: aging time (t), stack voltage (V ), stack power (P ), current (A), air/ H 2 / cooling water temperatures and air compressor speed. Among those data, stack voltage/ power are considered as useful indicators to assess the condition of the stack and to predict its degrading behavior. However, such data are noisy and non-stationary even under constant current, whereas variable load current poses an additional challenge for data-driven approaches. Fig. 2 depicts this issue with a clear example by comparing power drop signals from two stacks under constant and variable loads. Both stacks show a totally different aging behavior. The data-driven methods for prognostics of PEMFC under constant loads ([1], [START_REF] Morando | Fuel cells prognostics using echo state network[END_REF], [START_REF] Silva | Proton exchange membrane fuel cell degradation prediction based on adaptive neuro-fuzzy inference systems[END_REF], [START_REF] Jouin | Prognostics of pem fuel cell in a particle filtering framework[END_REF]), are mainly based on the assumption, that stack aging process is an irreversible degradation. Therefore, prognostics with those methods is performed by projecting the stack voltage/ power trend (e.g. see [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF]). Also they did not use current as an input to the prognostics model, knowing that it will remain constant throughout the life of PEMFC stack. However, such assumptions limit the applicability of data-driven methods for PEMFC prognostics under varying load. Nevertheless, using current as an input to the prognostics model can enable learning the relation between inputs and targets [START_REF] Gašperin | Model-based prognostics under non-stationary operating conditions[END_REF]. The learned model is further used to assess the current condition of the PEMFC stack and to predict its aging behavior with changing current profile. However, due to limited learning data, measurement noise, model inaccuracy, etc., a single model is incapable to encounter uncertainty related to input data and to accurately predict stack aging over long prediction horizon. As a result, the predicted response of the model is different from true response and thus the prognostics is uncertain. The uncertainty in the case of health assessment and prognostics is called as modeling uncertainty, which can be reduced by improved methods [START_REF] Celaya | Uncertainty representation and interpretation in model-based prognostics algorithms based on kalman filter estimation[END_REF]. Finally, whatever the type of uncertainty, it should be quantified and propagated to give confidence to predictions, which facilitates offline/ online decisions to prolong the life span of the stack (i.e., by control, maintenance or changing mission profiles).

According to above discussions and challenges, following points are vital for efficient prognostics of PEMFC.

1) Data are the key source of information that must be used intelligently to manage uncertainty. 2) Multidimensional data is essential for prognostics.

3) Operating conditions that correlate degradation, should be used as inputs. 4) Prognostics model should be capable of updating its parameters in real-time when new data are available. 5) Uncertainty of the prognostics must be quantified and propagated to give confidence for decisions.

III. PROPOSED DATA-DRIVEN PROGNOSTICS APPROACH

FCs are highly multiphysics (due to electrical, mechanical, thermal engineering, etc.,), multiscale systems (from µ m to m), and it is not easy to access their internal parameters or to fully understand their aging process. Therefore, building an accurate physics based prognostics models can be very hard. Nevertheless, with the advance of modern sensor, data storage and processing technologies, the data-driven prognostics models are becoming popular [START_REF] Hu | Ensemble of data-driven prognostic algorithms for robust prediction of remaining useful life[END_REF], which can also serve as powerful tools to ensure safety and availability of degrading PEMFC. They learn FC/ stack behavior directly from CM data without detailed physical understanding about the aging process, and that knowledge is used to predict degradation. According to discussions on CM data and modeling in previous section, the framework of PEMFC health assessment and prognostics can be easily understood by Fig. 3. Therefore, discussions on data-acquisition and data-processing steps are left aside. As for prognostics modeling, the data-driven model learns directly stack aging behavior from selected health indicators, which are stack aging time, current and stack power drop in our case. The learned model is used at time (t) to assess current SOH of the PEMFC stack, and to predict the evolution SOH from t → t + h, where h is the prediction horizon. This enables timely decisions to prolong its life span by performing maintenance or changing mission profiles. On the basis of our previous development for prognostics of PEMFC [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF], and considering the requirements highlighted in sec. II: for the prognostics modeling step an adaptive ensemble of Summation Wavelet-Extreme Learning Machine algorithm (SW-ELM) is proposed with new incremental learning scheme to predict stack degradation under given variable load profile. The SW-ELM combines neural network and wavelet theory for estimation/ predictions problems [START_REF] Javed | SW-ELM: A summation wavelet extreme learning machine algorithm with a priori parameter initialization[END_REF]. Basically, SW-ELM is one-pass batch learning algorithm for single layer feed forward network (SLFN), Fig. 4. It has an advantage of improved parameter initialization to reduce impact of random weights and bias of input-hidden layer, and an improved structure with two activation functions in each hidden node to encounter nonlinear inputs. Also it works on actual scales of the data. x i = [x i1 , x i2 , ..., x in ] T ∈ n and t i = [t i1 , t i2 , ..., t im ] T ∈ m , and Ñ the number of hidden nodes, each having activation functions (f 1 & f 2 ). To minimize the difference between output o j and target t j , there exist β k , w k and b k such that:

Plan of actions (maintenance/ mission profile)

Data processing extract / select health indicators

Acquisition

Output target

Ñ k=1 β k f [(θ, ψ) (w k .xj + b k )] = tj , j = 1, 2, ..., N (1)
where f is the average output from two different activation functions θ and ψ. w k = [w k1 , w k2 , ..., w kn ] T ∈ n is an input weight vector connecting the k th hidden to input layer neurons, (w k .x j ) is the inner product of weights and inputs, and b k ∈ is the bias of k th hidden neuron. Also, β k = [β k1 , β k2 , ..., β km ] T ∈ m is the weight vector to connect k th hidden neuron to output neuron. In matrix form Eq. 1 can be written as H avg β = T , where T is target matrix and H avg is hidden layer output matrix expressed as:

H avg (w 1 , . . . , w Ñ , x 1 , . . . , x Ñ , b 1 , . . . , b Ñ ) = f (θ, ψ)   (w1.x1 + b1) . . . (w Ñ .x1 + b Ñ ) . . . • • • . . . (w1.xN + b1) . . . (w Ñ .xN + b Ñ )   N × Ñ (2)
β = β T 1 • • • β T Ñ Ñ ×m and T = t T 1 • • • t T N N ×m (3)
Finally, the least square solution of the linear system H avg β = T , with minimum norm of output weights β is:

β = H † avg T = H T avg Havg -1 H T avg T (4)
where H † avg shows the Moore-Penrose generalized inverse for the hidden layer output matrix H avg [START_REF] Serre | What Are Matrices[END_REF]. The SW-ELM algorithm can be synthesized as follows (see details in [START_REF] Javed | SW-ELM: A summation wavelet extreme learning machine algorithm with a priori parameter initialization[END_REF]).

B. Building the SW-ELM ensemble

Predicting behavior of aging PEMFC stack is a complicated task, since there are various sources of uncertainty that impact predictions and the error accumulates with increasing prediction horizon. Considering the data-driven framework for prognostics of PEMFC in Fig. 3, at each step the uncertainties get compounded, that can grow beyond control in the prediction phase if not managed properly [START_REF] Saxena | Designing data-driven battery prognostic approaches for variable loading profiles: Some lessons learned[END_REF]. Therefore, considering uncertainties either due to data or either due to modeling phase (sec. II), a single model is not robust to reduce their impact, which could lead to wrong decisions. In comparison, performing prognostics with an ensemble of models would be less likely to be in error than an individual model and appears to be meaningful [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF]. The ensemble approach enables reducing the uncertainty and gives confidence to the predictions to facilitate decisions. A narrow confidence indicates better performances of prognostics in terms of precision and accuracy over wide confidence which indicates large uncertainty. The proposed ensemble structure is achieved by combining small groups of ensembles using SW-ELM. Each individual SW-ELM model has the same network complexity 5 input-55 hidden-1 output neuron, but different learning parameters (algo. 1), see Fig. 5. The parameter constant C to adjust w k and b k of each SW-ELM is set to C = 0.01 (see [START_REF] Javed | SW-ELM: A summation wavelet extreme learning machine algorithm with a priori parameter initialization[END_REF]). The inputs of each SW-ELM are stack aging time (t), current (I), 3 regressors of stack power (P t-2 , P t-1 , P t ). The number of SW-ELM models in each group is set to 10, and the number of groups is set to 20. The predicted output ( Pt+1 ) from the ensemble structure is the median value from medians computed from each group of SW-ELM models. This allows narrowing confidence of predicted values. To improve the adaptability of ensemble structure for better predictions and to manage uncertainty for better decisions, the incremental learning scheme with artificial data is presented as follows.

C. New incremental learning scheme

To perform long-term prognostics, a common practice is to project the current condition of equipment up to failure limit, assuming that predictions follow the degrading trend [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF]. This task is usually achieved by an iterative approach, that is performed by a single model which is tuned to perform onestep ahead prediction xt+1 . The predicted value is used as the regressors of the model to predict the following ones and the process is repeated until the prediction of xt+h (see [START_REF] Gouriveau | Connexionist-systems-based long term prediction approaches for prognostics[END_REF]). This process is repeated each time to evolve model parameters when new measurements are available, till the end of life of the equipment [START_REF] Javed | Improving accuracy of long-term prognostics of pemfc stack to estimate remaining useful life[END_REF]. The whole procedure can be considered as incremental learning, because the prognostics models are re-trained and their parameters are updated according to new data new [START_REF] Polikar | Learn++: an incremental learning algorithm for multilayer perceptron networks[END_REF]. The iterative approach can be useful for projection based prognostics methods under constant operating conditions, however, under variable load the assumption of degrading trends does not apply. Also with iterative approach the error will accumulate at each time step, which can result large uncertainty of prognostics. Therefore, main issues are: 1) how to do incremental learning without new data?, 2) how to manage uncertainty of long-term predictions?. To address those issues, the proposed approach for incremental learning uses the artificial data (or re-simulated data) from one-step ahead prediction model to update data record and the prediction model is retrained with those data Fig. 5. In order to elaborate the learning procedure of ensemble structure, consider CM data record from PEMFC stack with measurements from three health indicators up to time t, i.e., stack aging time t, current I and 3 regressors from stack power P . Each SW-ELM model is trained with those data to perform one-step ahead prediction of power Pt+1 . The median prediction value Pt+1 for ensemble structure is stored sequentially in the data record against the set of inputs at time t, which is considered as the artificial data from prediction to increase the learning frame. The ensemble structure is retrained with new sample (of artificial data) to update parameters, prior to the next prediction step. This procedure is repeated until the end of given current profile to predict the behavior of PEMFC stack SOH with changing current loads and to enable timely decisions. The proposition allows performing incremental learning without actual measurements and using artificial data from predictions, thus improving the adaptability of prognostics model and managing its uncertainty of long-term predictions. When new measurements from the stack are available, the complete procedure of proposed incremental learning scheme is repeated. Note that, due to rapid learning ability of SW-ELM algorithm, the proposed incremental learning can be computationally efficient. However, the classical algorithms for SLFN, like backpropagation algorithm can be computationally expensive. Moreover, the computational time can increase with the complexity of ensemble structure.

IV. EXPERIMENT AND RESULTS DISCUSSION

A. PEMFC stack CM data under µCHP profile

The proposed data-driven ensemble with incremental learning scheme is applied to prognostics of PEMFC stack of 1 kW for a µCHP application. PEMFC stack used for the experiment was composed of 8 cells, with an active area of 220cm 2 . The mission profile to operate the stack for µCHP under variable load current for a complete year (Fig. 6a), was based on the on-field measurements from a demonstration project for which Electricite de France (eDF) was partner [START_REF] Mocoteguy | Field testing of vaillant euro 2 pem fuel cell heating appliance for µ -chp in residential application[END_REF]. The CM data were collected from a 10 kW test bench at FCLAB Research Federation (FR CNRS 3539), Fig. 6b. The operating variables concerning, fluids (1), electrical (2), and thermal flows (3) were acquired from PEMFC (4) at a frequency of 1 Hz. To recall, the data from PEMFC stack continuously measured, controlled and economically possible are: aging time (t), stack power (P ) Fig. 2, current (A) Fig. 7a, stack voltage (V ) Fig. 7b, air/ H 2 / cooling water temperatures and air compressor speed.

B. SOH prediction results

To validate our proposition, during the computer simulations prognostics is initiated around half-life of the PEMFC stack. As mentioned in sec. III, it is assumed that the future load demand of µCHP application is known for a complete year (i.e., for four seasons). Therefore, the current is used as an input to the prognostics model to adapt variation of the stack power over increasing prediction horizon. Like a real situation, prognostics is performed at two different time steps with different lengths of prediction horizons: 1) prognostics initiated at 600 hours, where the prediction horizon is 643 hours, 2) prognostics initiated at 800 hours, where the prediction horizon is 443 hours. The results are discussed and a comparison is given to show improvements. Most importantly, the proposed approach is compared with the recent works on hybrid prognostics of PEMFC under variable loads.

1) Without incremental learning:

The long-term prediction results on SOH of PEMFC with SW-ELM ensemble (Fig. 5), without incremental learning are shown in Fig. 8a,b. Consider the first case, where predictions are initiated after learning measurements up to 600 hours. The median predictions from the ensemble can be seen with a red line. The large uncertainty of predictions over horizon of 643 hours is shown with a wide confidence around predictions, which is due to error accumulation at each step with iterative approach (sec. III). The median predictions from the ensemble are poor and they do not track properly behavior of stack (i.e. blue dotted line). For the second case Fig. 8b, predictions are initiated after learning measurements up to 800 hours. The median predictions from the ensemble are quite good and they track properly the actual aging behavior of the stack. Also, the uncertainty of predictions over the horizon of 443 hours is reduced as compared to the previous case. This indicates the requirement of large frame of learning data for the ensemble model.

2) With incremental learning: The long-term prediction results on SOH of PEMFC with data-driven ensemble (Fig. 5), with incremental learning are shown in Fig. 8c,d for which same legend apply as Fig. 8a,b. For clarity of results a zoom in view of predictions is given in spite of legend. Like previous results, consider the first case, where predictions are initiated at 600 hours. Even with the few learning data, the median predictions from the ensemble follow the stack aging behavior quite well as compared to results in Fig. 8a. Moreover, the confidence around predictions is very compact over the entire horizon of 643 hours, as shown in zoom in view, which indicates the robustness of the prognostics model to encounter uncertainty. However, the predictions from 800 hours up to 1000 hours on the power drop signal are not very accurate, but still better than results in Fig. 8a. For the second case Fig. 8d, predictions are initiated at 800 hours. The median predictions from the ensemble are quite accurate as they closely tracks actual aging behavior of the stack, which is also shown in the zoom in view. The uncertainty bounds of predictions are very narrow as well, over the entire horizon of 443 hours, which indicates higher precision and also the reliability of prognostics model.

3) Comparative analysis:

The SOH predictions results given in Fig. 8 are further evaluated using coefficient of determination metric (R2), for both cases, i.e., without and with incremental learning. Basically, R2 determines, how accurate the future outcomes are to be predicted by the learned model. The comparison of R2 results is given in Fig. 9, for prognostics at 600, 800 and 1000 hours. The comparison show that, the proposed incremental learning scheme can give more accurate prognostics results, when few learning data are available (i.e., up to 600 hours). Following that, the R2 accuracies with both cases (without and with incremental learning) are same for prognostics at 800 hours and 1000 hours. However, it should be noted that, at those time steps without incremental learning, the predictions are less precise as compared to proposed incremental learning scheme, which is already mentioned in sec. IV-B. The results of prognostics accuracy with the proposed datadriven ensemble with new incremental learning scheme are further compared with the hybrid approach on prognostics of PEMFC under variable load [START_REF] Jouin | Prognostics of prm fuel cells under a combined heat and power profile[END_REF]. The R2 results from the hybrid prognostics model are given shown in Fig. 10. For prognostics at 600 hours and 800 hours, with proposed approach the accuracy results are R2 = 0.949 and R2 = 0.995 respectively, whereas with hybrid prognostics at 600 hours and 800 hours, accuracy results are R2 = 0.68 and R2 = 0.73. These results clearly show the significance of the proposed data-driven ensemble with incremental learning.

V. CONCLUSION

In this paper a data-driven approach is proposed for prognostics of PEMFC stack for combined heat and power generation (µCHP). The proposed prognostics model is based on Summation Wavelet-Extreme Learning Machine (SW-ELM) ensemble with a new incremental learning scheme for an online application. The SW-ELM ensemble is applied to monitoring data from PEMFC stack under known variable loads, which is the first application from data-drive category of prognostics approaches. Long-term prognostics on state of health (SOH) of the PEMFC is performed with few learning data. The SOH prediction results with proposed data-driven approach, and its comparison with hybrid prognostics, clearly show the significance of SW-ELM ensemble model which predicts with higher accuracy and lower uncertainty over longterm prognostics horizon. The future developments of this work concern the application of proposed data-driven ensemble on prognostics of PEMFC for transportation application.

Fig. 1 .

 1 Fig. 1. PEM Fuel Cell applications

Fig. 2 .

 2 Fig. 2. Comparing PEMFC stacks power drop signals

  Fig. 3. From CM data to long-term prediction of PEMFC stack SOH

Fig. 4 .

 4 Fig. 4. Machine learning view of SW-ELM

Algorithm 1

 1 Brief learning scheme of SW-ELM Assume: n inputs, m outputs, Ñ hidden nodes Require: N learning samples, Arcsinh & Morlet functions 1: Initialize wavelet parameters (i.e., dilatation & translation). 2: Initialize randomly hidden nodes param. (w k , b k ) & adjust.3: Obtain hidden layer output matrix H avg using Eq. 2. 4: Find the output weight matrix β in Eq. 4.

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig. 6. µCHP profile a) and 10 kW test bench b)

Fig. 9 .

 9 Fig. 9. Comparing prediction accuracy using R2.

Fig. 10 .

 10 Fig. 10. Evaluating prediction accuracy using R2 [5].

ACKNOWLEDGMENT

This work is supported by the ANR project PROPICE (ANR-12-PRGE-0001) and by the Labex ACTION project (contract "ANR-11-LABX-01-01") both funded by the French National Research Agency.