Didier El Baz
email: elbaz@laas.fr

Vincent Boyer
email: vboyer@laas.fr

Julien Bourgeois
email: julien.bourgeois@univ-fcomte.fr

Eugen Dedu
email: eugen.dedu@univ-fcomte.fr

Kahina Boutoustous
email: kahina.boutoustous@univ-fcomte.fr

Distributed part differentiation in a smart surface

Keywords: MEMS, smart surface, part differentiation, distributed algorithms, asynchronous algorithms, multi-core

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Micro-Electro Mechanical Systems (MEMS) actuator arrays with embedded intelligence, also referred to as smart surfaces, seem to have great potential impact for manipulating micro parts in many industrial areas like semiconductor industry and micromechanics (see [START_REF] Biegelsen | Airjet paper mover[END_REF][START_REF] Fukuta | Design fabrication and control of MEMS-based actuator arrays for air-flow distributed micromanipulation[END_REF]).

The Smart Surface project aims at designing a micro robotics system (an array of fully integrated micro modules that are also referred to as cells) for conveying, sorting or positioning micro parts (see [START_REF] Boutoustous | A framework to calibrate a MEMS sensor network[END_REF][4][5]). Each cell will contain a sensor, processing unit and actuators (see Fig. 1). Distributed computing on dedicated architectures like smart surfaces is a source of a rich problematic mainly due to the scarcity of resources, e.g.: number of sensors (each part will recover a small number of sensors), memory size and computing power or the presence of faults. To the best of our knowledge, the literature on sorting and positioning micro parts in a low resolution context is almost nonexistent. For different approaches related to other applications in the low resolution context, we make reference to Ishida [START_REF] Ishida | Recognition of low resolution characters by a generative learning method[END_REF], for low resolution character recognition and Tabbone [START_REF] Tabbone | A new shape descriptor defined on the Radon transform[END_REF], for a novel approach based on the Radon transform for complex shapes identification (see also [START_REF] Kare | Backyard star wars[END_REF]).

In this paper, we propose an original approach for distributed part differentiation. Our method is decomposed into two phases. First, a distributed algorithm is used to obtain the discrete representation of parts on the smart surface as well as their position. Then, a distributed algorithm is used to differentiate the parts. The former phase is the so-called discrete state acquisition phase. The latter phase corresponds to the so-called differentiation phase that ends when each cell that is covered by a part has identified the type of the part.

We consider the case where many parts can be on the smart surface and extend the results in [START_REF] Baz | Distributed discrete state acquisition and concurrent pattern recognition in a distributed MEMS-based Smart Surface[END_REF] (where we have made the assumption that there is at most one part at the same time on the smart surface). We give a mathematical model of discrete state acquisition and propose several distributed state acquisition algorithms. We consider synchronous and asynchronous iterative algorithms. We propose also simple initial points and give convergence results for the studied distributed algorithms. We propose stopping criteria in the synchronous case and in the asynchronous case.

We take opportunity of the high level of parallelism available on the array of micro modules to derive an original distributed algorithm that finally performs concurrent part differentiation. The techniques developed in this paper are particularly interesting when cells present faults or when parts are initially positioned any manner on the smart surface.

Finally, we present SSS, a multi threaded Java Smart Surface Simulator that has permitted us to evaluate and validate experimentally our distributed algorithms on multi-core machines.

Section 2 presents the smart surface. Section 3 deals with distributed discrete state acquisition. A first approach for part differentiation is presented in Section 4. Distributed part differentiation with gaps is proposed in Section 5. In Section 6, we present SSS, a multithreaded Java Smart Surface Simulator. Experimental results obtained with SSS are given and analyzed in Section 7. Conclusions are drawn in Section 8, where future work is also discussed.

THE SMART SURFACE

Assembly line workstations need to be fed with well-positioned and well-oriented parts. These parts are often jumbled and they need to be sorted and conveyed to the right workstation. To do so, the following operations must be performed on parts: identification, sorting, orienting, positioning and feeding. Among the most promising solutions to perform these tasks, is the combination of MEMS in order to form a micro robotics array.

There have been numerous projects on MEMS actuator arrays in the past and more particularly in the 1990's. These pioneering research works have developed different types of MEMS arrays that are based on actuators which are either pneumatic (see [START_REF] Fujita | Group work of microactuators[END_REF][START_REF] Pister | A planar air levitated electrostatic actuator system[END_REF]), magnetic or thermo bimorph, electrostatic or servo roller wheels (see [START_REF] Bohringer | Algorithms for sensorless manipulation using a vibrating surface[END_REF]). Recent research works have been conducted in order to include sensors and to add intelligence to MEMS actuator arrays but these works either failed to propose solutions at a micro-scale or that are fully integrated (e.g. see [START_REF] Fukuta | Design fabrication and control of MEMS-based actuator arrays for air-flow distributed micromanipulation[END_REF]).

The objective of the Smart Surface project (see [START_REF] Fort-Piat | Smart Surface based on autonomous distributed micro robotic systems for robust and adaptive micromanipulation[END_REF] and [START_REF] Matignon | Design of semi-decentralized control laws for distributed-air-jet micromanipulators by reinforcement learning[END_REF]) is to design a distributed and integrated micro manipulator based on an array of micro modules in order to realize an automated positioning and conveying surface. Each micro module will be composed of a micro actuator, a micro sensor and a processing unit. The cooperation of micro modules thanks to an integrated network will allow the system to recognize the parts and to control micro actuators in order to move and position accurately the parts on the smart surface. We consider small parts that cover a small number of micro modules and that are moved via air nozzles actuators (the rectangular holes on the front-side of Fig. 1). Air-flow comes through a micro valve in the back-side of the device and then passes through the nozzle (see Fig 2, for a front-side and back-side view of an actuator). The advantage of this solution is that the micro actuators, the most fragile part of the surface, are protected. Circle holes (see Fig. 1) are used by the micro sensors to detect the presence of the part on the surface.

DISTRIBUTED DISCRETE STATE ACQUISITION

In this Section, we give a mathematical model for distributed discrete state acquisition and we derive several distributed algorithms. Cells are connected via a communication network. Each cell has at most 4 neighbors (see Fig. 2).

The problem is to obtain in a distributed way global knowledge of the discrete state of the smart surface, i.e. to obtain discrete representations of parts that lay on the smart surface and their exact position. In [START_REF] Baz | Distributed discrete state acquisition and concurrent pattern recognition in a distributed MEMS-based Smart Surface[END_REF], we have made the assumption that there is only one part on the smart surface. In this paper, we extend this result to the case where several parts may lay on the Smart Surface.

Mathematical model of distributed state acquisition

Without loss of generality, we assume that there is only one sensor per cell. State acquisition can be modeled as the following fixed point problem: find such that is the smallest fixed point which satisfies:

where is the number of cells of the smart surface and is a mapping from into A vector represents an augmented global state of the smart surface. This vector can be decomposed into sub vectors where denotes the augmented local state of the th cell. As a consequence, each cell needs only bits in order to store its augmented local state (similarly, each cell needs at most bits in order to store the augmented local state of its neighbors). The augmented local state of a given cell corresponds to its current vision of the smart surface. The augmented local state can be decomposed into the actual local state of cell that is denoted by the scalar (if there is a part on cell , then otherwise we have ) and the current knowledge cell has of the smart surface, i.e.

. The mapping permits one to obtain a mathematical formulation of the state acquisition problem and to derive several useful distributed algorithms. Cells make acquisition of the global state of the smart surface via data exchange, i.e. via messages they receive from their direct neighbors. Let denote the set of all neighbors of cell the mapping that can be decomposed the same way as vector is defined as follows:

where the operations and are defined as follows: let otherwise; similarly, and otherwise.

Definition 1: Distributed synchronous state acquisition can be described via the following successive approximation method (this method is also referred to as a discrete iteration or an iteration on a product of finite sets):

Where the initial approximation is chosen as follows:

Remark 1: Clearly, is not the only fixed point for It is possible that the sequence generated by a discrete iteration starting from remains stationary at a given vector where the order relation is component wise, i.e. A simple illustration can be obtained by choosing such that In this case, we clearly have:

However, the values of the component derived from do not correspond to the actual local state of the cell of the smart surface, unless the part covers completely the surface. This shows the importance of choosing a good initial approximation in order to converge to a fixed point that makes sense in term of state acquisition. We shall see in the sequel that the above defined initial vector which is in fact a sub solution, i.e. which satisfies (the inequality being considered component wise), is a good starting point in order to converge to the solution of the fixed point problem that makes sense in term of state acquisition.

The reader is referred to Robert [START_REF] Robert | Discrete Iterations, a Metric Study[END_REF] for a study on mathematical and algorithmic aspects of discrete iterations. We note that is finite for any As a consequence, the distributed discrete algorithm converges monotonically to in finite number of iterations; Q.E.D.

Let us denote now by the largest Manhattan distance of the smart surface.

Theorem 3: The number of iterations of the discrete algorithm is bounded by Proof: The distributed discrete iteration starting from generates a monotone sequence of vectors of Time after time, each cell makes acquisition of the augmented local state of its neighbors via messages it receives from them and combines these augmented states with its own augmented state in order to produce an updated augmented state, i.e. a more accurate vision of the state of the mart surface. At each new iteration, cells gain a more accurate vision of the actual discrete state of the smart surface by a unit of distance. This corresponds to a link between two cells along each direction. Finally, the sequence converges to the fixed point which is such that this shows that at convergence, all augmented local states are similar and that all cells have the same vision of the global state of the smart surface). Q.E.D.

For a rectangular smart surface with size at most sequences of communications are necessary to make acquisition of local states and at most iterations are necessary to obtain the solution.

In [START_REF] Baz | Distributed discrete state acquisition and concurrent pattern recognition in a distributed MEMS-based Smart Surface[END_REF], we have proposed a local stopping test that permits one to reduce the number of iterations in situations where we assume that there is at most one part on the smart surface.

Implementation of the distributed algorithm

For simplicity of notation, we denote in the sequel by the set of neighbors of node The th neighbor of node is denoted by The behavior of the distributed synchronous discrete algorithm can be represented as follows.

For i from 1 to n do

Distributed asynchronous algorithms

In the above subsection we have presented a first model of distributed state acquisition in the synchronous case. We present now a mathematical model in the more general asynchronous context where each cell can perform updating phases at its own pace, i.e. computation can be done without order nor synchronization. We derive convergence results by using the general convergence theorem of Bertsekas (see [START_REF] Bertsekas | Parallel and distributed iterative algorithms: a selective survey[END_REF]). We propose also a stopping method.

We assume that there is a set of times at which one or more sub vectors of vector are updated by some cells. We denote by the subset of times at which the sub vector is updated. Let be the subset of labels used during the updating phases of cell with:

We assume that this assumption guarantees that new values of the components of the sub vectors are used as computations go on. We also assume that the sets are infinite; this assumption guarantees that no component of the iterate vector is abandoned forever. In particular, cells will not stop their computations before convergence.

We denote by the set of labels used during the computations performed by the different cells. Definition 3: Distributed asynchronous state acquisition can be described via the following successive approximation method denoted by where is the initial approximation defined in subsection 2.1.

Theorem 4: The distributed asynchronous discrete iteration converges to

Proof: In order to show convergence of the asynchronous algorithm we build a sequence of level sets which satisfies the conditions of the general asynchronous convergence theorem of Bertsekas, see page 431 in [START_REF] Bertsekas | Parallel and distributed iterative algorithms: a selective survey[END_REF].

Let we define the sets

The so-called synchronous convergence condition of Bertsekas and every limit point of is a fixed point of if is satisfied. This result follows from Theorem 2, the monotone property of mapping and the fact that is the smallest vector such that

The so-called box condition of Bertsekas, i.e.:

is also satisfied since the level sets are Cartesian products of subsets . As a consequence, the general asynchronous convergence theorem of Bertsekas applies. Q.E.D.

We note that the sequence of nonempty subsets satisfies:

and

The reader is also referred to Radid [START_REF] Radid | Itérations Booléennes et sur des ensembles de cardinal fini[END_REF] for various results related to asynchronous discrete iterations.

Among the many interests of distributed asynchronous iterations, one can quote the better efficiency of the algorithms since each cell goes at its own pace and there is no waiting time for synchronization. This is particularly true in the case of monotone convergence, where the use of last updates permits always one to improve the iterate vector. One can quote also fault tolerance since distributed asynchronous iterations tolerate some messages losses (see [START_REF] Bertsekas | Parallel and distributed iterative algorithms: a selective survey[END_REF]).

In the case of a cell fault, a distributed asynchronous algorithm may end with an approximation of the solution that is slightly different from , however, we shall see in the next Section that the gap-based techniques developed in this study permit one to overcome this difficulty . Moreover, there will be no deadlock with such an asynchronous algorithm.

Implementation of distributed asynchronous algorithms

In this subsection, we show how asynchronous algorithms have been implemented. We consider also convergence detection of asynchronous algorithms. Several procedures can be used in order to detect convergence of distributed asynchronous discrete iterations. One can use for example the Dijkstra and Scholten procedure [START_REF] Dijkstra | Termination detection for diffusing computation[END_REF] (see also [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF][START_REF] Baz | An efficient termination method for asynchronous iterative algorithms on message passing architecture[END_REF]). The reader is also referred to El Baz [START_REF] Baz | A method of terminating asynchronous iterative algorithms on message passing systems[END_REF] for a method based on level sets. The procedure in [START_REF] Dijkstra | Termination detection for diffusing computation[END_REF] relies on generation of activity graph and acknowledgement of messages. Initially, only one cell is active, i.e. the so-called root that is denoted by The cell starts computation and sends messages to its neighbors; these messages activate the neighbors that become the so-called sons of and so on. All cells become eventually active. All messages are acknowledged at once but activation messages of father that are acknowledged only when a son becomes inactive. The activity graph moves on according to the messages received and satisfaction of the conditions: A cell sends messages to its neighbors if and only if it is active and the above condition is not satisfied. Finally, the algorithm stops when the cell R stops; i.e. all local stopping criteria are satisfied and there is no message in transit in the system. This type of convergence detection method is quite natural in the context of discrete iterations since it is not necessary to modify the distributed asynchronous iterative algorithm so that it converges in finite time.

Let us denote by Active( ) the logical variable that stores the behavior of the th cell: if Active( ) is True, then the th cell performs computation. If Active( ) is False, then the th cell does nothing. Initially, all cells are inactive, but . A cell becomes active when receiving a message. A cell becomes inactive when the following extended local asynchronous stopping criterion is satisfied.

Definition 4: The extended asynchronous local stopping test is given by: and all cells activated by cell are inactive.

All cells can be activated many times but the root, which is active only once. Finally, the algorithm stops when becomes inactive. In the sequel, we shall denote by isend and ireceive, respectively, non blocking send and receive, respectively. These communication primitives permit one to implement asynchronous communication. Formal proofs of validity for this type of algorithm including convergence detection method have been established in [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF][START_REF] Baz | An efficient termination method for asynchronous iterative algorithms on message passing architecture[END_REF].

A FIRST APPROACH FOR DISTRIBUTED PART DIFFERENTIATION

We assume that there are a limited number of types of parts. We shall consider in this paper that we have three types of parts. Thus, any part on the smart surface belongs to one of these three classes. The algorithms we propose, nevertheless, work well with more classes.

This Section presents the first approach we have proposed for part differentiation in a low resolution context and when there is only one part on the smart surface (see [START_REF] Boutoustous | A framework to calibrate a MEMS sensor network[END_REF]). This approach is based on the computation of criteria. These criteria are basically contour-based differentiation criteria like number of components of vector with value 1 such that there exists or region-based criteria, like number of components of vector with value 1, i.e. surface like criteria, or maximum length between 1 of the part. The different criteria used in this paper are detailed in [START_REF] Boutoustous | A framework to calibrate a MEMS sensor network[END_REF] (see also [START_REF] Boutoustous | An exhaustive comparison framework for distributed shape differentiation in a MEMS sensor actuator array[END_REF]).

The approach presented here is particularly interesting when one aims at determining if part differentiation is possible or not. This is why we also refer to this approach as total differentiation. This approach consists of two stages that are detailed below.

-offline stage: during this stage a database that contains the values of criteria used to differentiate parts is produced. Only a limited number of parts that will be the so-called reference parts is considered. The values of the criteria are stored at each cell. -online stage: during this stage cells try to differentiate the part on the Smart Surface by comparing the criteria values of the current part on the smart surface with the database.

Offline stage

This stage permits one to associate to each reference part a set of criteria values. For each reference part, the following phases are executed in sequence:

-the reference part is rotated one degree with respect to its centre and translated with s/10 cells, where s denotes the width of the rotated part; -a matrix associated with sensor values is generated, the matrix fits the Smart Surface, i.e. there is one entry per sensor, an entry of the matrix is equal to 1 if its associated sensor is covered by a part, it is equal to 0 otherwise; -sub-matrices of the initial matrix without rows and columns that contain only zeros are generated, these sub-matrices are the so-called masks, multiple copies of the same mask are discarded; -values of the several criteria are calculated for all masks of each reference part.

These criteria values form the database to be used as input of the online stage.

Online stage

This stage takes place after the discrete state acquisition phase. The aim of this stage is to differentiate, in real-time, a part on the Smart Surface.

Once each cell of the smart surface has made acquisition of the binary representation of the part on the smart surface, it computes the criteria values. These values are compared to the criteria values computed at the offline stage in the database. If there is a criterion value or a combination of criteria values that matches exactly the one in the database, then the part is considered to be differentiated. If no such correspondence is found, then no decision is taken.

DISTRIBUTED PART DIFFERENTIATION WITH GAPS

In this Section, we propose an original distributed part differentiation method based on gaps. As in the previous Section, we assume that there are a limited number of types of parts (we recall that only three types of parts are considered in this paper). Our algorithm, nevertheless, works well with more classes.

We take benefit of the high level of parallelism available on the array of micro modules to derive a distributed algorithm. Modules will compute concurrently several contour-based or region-based criteria related to the part that covers them. Decisions that are based on the value of the criteria are taken concurrently. The differentiation phase ends when each cell that is covered by a part has identified the type of the part.

We detail now the decision process. We note that the value of the different criteria can vary according to the orientation and position of the part on the smart surface. In the case of part rotation, for example, we have observed that the surface of 3x3 square, where the unit of distance is the length of a cell, can vary from 9 to 13, according to the orientation of the part on the smart surface, see Fig. 3 obtained with SSS, a multithreaded smart surface simulator that will be detailed in the next Section. Fig. 4 shows a view of an actual part on the smart surface and its discrete representation. In the sequel, we present two new approaches for part differentiation. The first approach relies on the use of a single reference position for each part. Each cell compares computed values of the criteria for the current position of the part on the smart surface with values of criteria of each part obtained for a single reference position (those values are stored in a database of registered parts). We propose to compute gaps between the measured criteria and the criteria value of registered parts for differentiation purpose. This method is particularly interesting when some cells present faults. Another particularity of the first approach is to consider only a subset of well known criteria like surface or perimeter of the part. The criteria that amplify tiny differences between parts, like product of the differences between consecutive columns and consecutive line are discarded. In the sequel, the number of criteria considered will be denoted by . Let denote the number of different parts. Let denote the reference value of th criterion of the th part (those values are computed offline). Let denote the value of the th criterion of the part on the smart surface. Each cell computes the following gaps:

The second approach relies on the use of a set of reference positions for the different parts on the smart surface. We take into account rotations of parts with one degree increments. Without loss of generality and for symmetry reason, only rotations from 1 up to 45 degrees can be considered. Let

We denote by the reference value of th criterion of the th part rotated by degrees; those values are also computed offline. We denote by the set of all reference values for part Each cell computes the following gaps.

We note that the former gap, presents the advantage to require a limited amount of memory and a small computing time, while the latter gap, permits one to expect better differentiation of parts, particularly in the case where parts can have any orientation on the smart surface.

Decision making concerning pattern recognition at each cell relies on the respective values of the gaps. The pattern that is chosen corresponds to the gap or that is the closest to zero. We note that all cells make the same computation concurrently and thus take the same decision.

Concurrent decision making based on gaps is particularly interesting with respect to fault that may occur on the smart surface, i.e. sensor failures or parts positioned any manner on the smart surface. The use of gaps is also interesting with respect to recognition of pattern slightly modified, i.e. parts that present tiny faults.

SSS, A MULTITHREADED SMART SURFACE SIMULATOR

We present now SSS, a smart surface simulator developed at LAAS-CNRS. The simulator SSS has permitted us to evaluate distributed synchronous and asynchronous state acquisition algorithms and concurrent pattern recognition methods. SSS is a multithreaded Java code that runs on multi-core machines.

SSS has permitted us to validate experimentally the distributed algorithms and to study in detail communications between cells, stopping criteria and the efficiency of the proposed methods. The reader is referred to the site [5] for some demos with SSS.

SSS permits one to build a smart surface that has any size and different basic patterns like squares, rectangles, L shapes, I shapes and so on, that will become references or that will correspond to a given part. SSS permits one also to place the generated patterns everywhere on the smart surface. It is possible to rotate shapes on the smart surface and to introduce sensors faults (see Fig. 3, for a square shape). SSS allows one to choose a synchronous or asynchronous distributed state acquisition algorithm, to carry it out and to display dynamically the augmented local state of any cell (see right window of Fig. 5 that corresponds to iteration 2). One can have a dynamic view on the activity graph of the smart surface, i.e. one can see the cells that are active (those cells who are updating their augmented local state). One can also choose particular criteria and a differentiation method, e.g. gaps based methods or differentiation methods studied in [START_REF] Boutoustous | An exhaustive comparison framework for distributed shape differentiation in a MEMS sensor actuator array[END_REF]. Finally, one can display the results of the pattern recognition phase for the different criteria selected. SSS permits one also to display some statistics. In SSS, each cell is managed by a thread. Cells communicate with their neighbors via buffers (see Fig. 6 and7). Buffers are controlled by flags which enable or disable memory access, e.g. writing. This permits one to handle memory conflicts and to implement synchronization between threads. Memory organization, displayed in Fig. 6, is given as follows. For a typical cell with four neighbors, data sent by neighbors according to communications scheme presented in Fig. 7 are stored in a dedicated buffer, e.g. top buffer, for neighbor that is above the considered cell, right buffer for neighbor that is situated on the right of the cell … Finally, local state is used to store the current value of the augmented local state. This organization presents great flexibility in order to study different algorithms for state acquisition. particular, it permits one to implement easily asynchronous schemes of computation since in this case neighbors can freely exchange data with a cell without synchronization. It permits nevertheless one to implement synchronous schemes of computation whereby neighbors must be granted permission to access buffers.

TESTS

The multithreaded Java smart surface simulator SSS has been carried out in parallel on a multi-core machine with 3.0GHz Quad-Core Intel Xeon processor.

In this Section, we compare a first series of results obtained with SSS for the gap methods proposed in Section 5 and the total differentiation method presented in Section 4. We have considered three parts: a square, the so-called Sq part, an L shaped part and a I shaped part. All parts have been placed randomly 200 times, leading to 200 draws with SSS. We have classified the criteria according to their performance. For each draw, we have computed the values of 17 criteria and we have applied the total differentiation method of Section 4 which gives the differentiation rate. The criteria were afterwards classified according to the differentiation rate and only the criteria with the best differentiation rates were selected.

Table 1 displays results for the best two criteria: S and A, respectively, were S denotes the surface and A the sum of angles of type "V", respectively (see [START_REF] Boutoustous | An exhaustive comparison framework for distributed shape differentiation in a MEMS sensor actuator array[END_REF]). For 200 draws, we note that the criterion S has correctly differentiated the part Sq in 37% of cases. In the second test, we are interested in part differentiation via a combination of the criteria S and A. Table 2 shows the differentiation rate obtained by using the criteria combination. We note that the part Sq was correctly differentiated in 59% of the cases; which is better than with S or A alone. The average differentiation rate was increased from 48.76% (for S alone) and 40.83% (for criterion A alone) up to 67.16% for the combination of A and S. Differentiation rates for criteria combination, total differentiation

Criteria

Criteria

We compare now the results of the above differentiation method with those obtained with the methods based on gaps introduced in Section 5 of this paper. Differentiation rates with the second gap These results show that the methods based on gaps g and g' improve the differentiation rate in the following cases: -with a single criterion, e.g. the criterion S, the differentiation rate is improved from 48.76% (see first row of Table 1) to 99% for g (see first row of Table 3) and 99% for g' (see first row of Table 4).

.

-with several criteria, the combination of criteria also improves the differentiation rate from 67.16% (see first row of Table 2), to 98.83% (see third row of Table 3) and 92.83% (see third row of Table 4), respectively, for g and g', respectively.

We conclude that the differentiation methods based on gaps give better results than the total differentiation method when parts can have any orientation on the smart surface. Additionally, one criterion alone may be sufficient to reach almost 100% differentiation rate.

CONCLUSIONS AND PERSPECTIVES

In this paper, we have considered a smart surface for conveying, sorting or positioning micro parts. We have given a mathematical model for discrete state acquisition. We have proposed several distributed synchronous and asynchronous algorithms, some stopping criteria and we have established convergence results for the studied methods. We have also proposed a distributed part differentiation method based on gaps. Finally, we have presented SSS, a multithreaded Java Smart Surface Simulator, that we have developed in order to evaluate and validate distributed algorithms and we have displayed and analyzed a first series of results for randomly generated instances with SSS.

Future directions of research concern fault detection and solutions that propose degraded but everlasting behavior particularly in the synchronous case.

We shall consider concurrent pattern recognition methods that exploit smart surface natural parallelism, e.g. each cell can apply a mapping to and compute criteria. Typical mappings can be some rotations. This kind of preconditioning can enrich pattern recognition.

We shall also study combined part differentiation and part motion; it may be efficient to recognize a part while moving it on the smart surface. The reader is referred to [START_REF] Boutoustous | Distributed control architecture for smart surfaces[END_REF] for a first study.

It may also be interesting to derive pattern recognition techniques that are not criteria based and which exploit directly the part code.

Finally, implementation on the distributed smart surface must be made in order to complete the study.

ACKNOWLEDGEMENTS

The authors would like to thank Femto-ST for photos of the parts and information regarding the smart surface.

Fig. 1 .

 1 Fig. 1. General overview of the Smart Surface

Fig. 2 .

 2 Fig. 2. Front-side and back-side of a micro-actuator

Fig. 3 .

 3 Fig. 3. Communication network of the smart surface

Theorem 1 :

 1 The mapping is monotone. Proof: from the definition of the mapping we clearly have Q.E.D. Theorem 2: The distributed discrete iteration converges to Proof: from the definition of mapping we have Moreover, we have Since the mapping is monotone, and We denote by a discrete distance on . We have: Let be the Manhattan distance on we have:

For k from 1

 1

For from 1

 1

Fig 4 .

 4 Fig 4. Examples of different surface values for the same square with different orientations (SSS screenshots)

Fig. 5 .

 5 Fig. 5. View of an actual H shape part on the Smart Surface and its discrete representation (courtesy of Femto-ST)

Fig. 6 .

 6 Fig. 6. SSS smart surface window (left) and -extended‖ local state window of a given cell at iteration 2 (right)

Fig. 7 .Fig. 8 .

 78 Fig. 7. Basic cell architecture with SSS

TABLE 1

 1 DIFFERENTIATION RATES FOR THE CRITERIA A AND S,TOTAL DIFFERENTIATION

TABLE 2

 2

  Table 3 displays the results obtained with the gaps g.

	Criteria	Sq	I	L	Average
	S	100%	99.00%	98.00%	99.00%
	A	100%	99.00%	78.00%	92.33%
	A and S	100%	100%	96.50%	98.83%

TABLE 3

 3 Differentiation rates with the first gap Table4gives the results obtained with the gaps g'.

	Criteria	Sq	I	L	Average
	S	100%	99.00%	98.00%	99.00%
	A	100%	99.00%	78.00%	92.33%
	A and S	100%	99.50%	79.00%	92.83%

TABLE 4

 4