Iraklis Leontiadis
email: leontiad@eurecom.fr

Melek Önen
email: onen@eurecom.fr

Refik Molva
email: molva@eurecom.fr

M J Chorley
email: m.j.chorley@cs.cardiff.ac.uk

G B Colombo
email: fg.colombo@cs.cardiff.ac.uk

Privacy preserving similarity detection for data analysis

Keywords: Information security, privacy, data analysis, similarity detection

Current applications tend to use personal sensitive information to achieve better quality with respect to their services. Since the third parties are not trusted the data must be protected such that individual data privacy is not compromised but at the same time operations on it would be compatible. A wide range of data analysis operations entails a similarity detection algorithm between user data. For instance clustering on big data groups together objects based on the heuristic that similar objects are likely to be put under the same cluster. Similarity decisions are important for numerous applications such as: online social networks, recommendations systems and behavioral advertisement.

In this paper we propose a mechanism that protects user privacy and preserves data similarity results although encrypted. We analyze the security of the scheme and we further demonstrate its correctness and feasibility through a real life experiment where "personality traits" by users are collected for a 4square application.

I. INTRODUCTION

Most of today's ICT applications tend to leverage user information more and more to achieve better content delivery. In particular recommendation systems collect data about users and their interactions with their environment in order to deliver the most appropriate and personalized content to them. The leveraged information spanning users' social relations and personal interests consist of highly sensitive data and hence raises the problem of privacy; a naive solution on the aforementioned problem could be to encrypt data before analyzing them. This would not solve the problem as operations after encryption would not be feasible. A more suitable solution could be to encrypt data homomorphically thus statistical properties on data after encryption are preserved. Even though this solution seems approachable the current homomorphic encryption schemes fall short of giving a solution for a global analysis system applied to some large scale dataset. Moreover anonymization techniques do not offer the appropriate security guarantees for individual data privacy and also have been vulnerable to attacks [START_REF] Narayanan | Robust deanonymization of large sparse datasets[END_REF].

One of the basic building blocks in the vast majority of data analysis scenarios is similarity detection. By analyzing users' dataset, a recommendation engine can discover similar profiles and thus recommend a newly arrived user some content that was already consumed by other existing "similar users". Online advertisers sought to increase their revenues by inspecting the online behavior of users. That implies an outsourcing of personal sensitive information by online retailers to the advertisers.

The aforementioned applications imply a privacy violation risk. Since the input to the data analysis operations is personal sensitive private information and operations performed over them violate user privacy. As such, users and companies either tend not to submit their data for further analysis to untrusted parties or they give limited access on it due to individual privacy violation risks [START_REF] Narayanan | Robust deanonymization of large sparse datasets[END_REF][START_REF] Rouf | Neighborhood watch: security and privacy analysis of automatic meter reading systems[END_REF][START_REF] Lisovich | Inferring personal information from demand-response systems[END_REF][START_REF] Mclaughlin | Protecting consumer privacy from electric load monitoring[END_REF]. Radical solutions include a restriction either on the available data analysis operations from the analyzer perspective or an outsource of aggregate information instead of individual data. But this will degrade very much the accuracy on data analysis and also this method is not always feasible.

We analyze a well-known similarity detection algorithm, namely the cosine similarity and combine it with some obfuscation mechanisms in order to achieve a privacy preserving similarity computation solution.

In this paper we present a privacy preserving protocol for similarity detection. Cosine similarity can recognize similar vectors based on the formed angle between the vectors.This new privacy preserving mechanism first maps users' data into vectors and applies some geometrical transformations that on the one hand preserve the angle between any pair of vectors and assures the confidentiality of the content of their coordinates. The accuracy of the proposed solution is then evaluated with the study on users' personality characteristics.

In section II we present related work in the area of privacy preserving data analysis. In III there is the problem description. We give our solution in section IV and in section V we argue for the security of the scheme. The evaluation of solution with real world data is analyzed in VI.

II. RELATED WORK

We proceed into a taxonomy of previous solutions in the area of privacy preserving data analysis. We start with more generic solutions and we further describe previous work in the context of specific privacy preserving similarity detection algorithms for clustering.

Data perturbation Several techniques have been proposed in order to obfuscate data such that when users submit their data to the data analyzer individual data privacy is being protected but specific data mining algorithms can be applied on it. Privacy preserving data mining by adding noise on data has been first proposed in [START_REF] Agrawal | Privacy-preserving data mining[END_REF][START_REF] Aggarwal | On the design and quantification of privacy preserving data mining algorithms[END_REF]. The solution has been proposed for privacy preserving decision trees as a solution to derive association rules from databases. In [START_REF] Oliveira | Privacy preserving clustering by data transformation[END_REF] the authors proposed geometrical transformation for data clustering. Transformation though are data dependent and do not scale for multidimensional data.

Anonymization Data anonymization asks for unlinkability on data records and users. K-anonymity [START_REF] Sweeney | k-anonymity: a model for protecting privacy[END_REF] has been proposed as a solution to protect the release of data to an untrusted party such that the personal private information for each data record cannot be distinguished from k-1 other users. Suppression and generalization are two techniques to achieve k-anonymity. By generalization [START_REF] Iyengar | Transforming data to satisfy privacy constraints[END_REF] specific attributes are generalized in order to protect user anonymity. For instance instead of releasing the exact data of birth only the month and the year is released. With suppression [START_REF] Samarati | Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression[END_REF] no data is released. Solutions for data anonymity imply an information loss through out the described techniques and operation after the release of the data are inconsistent.

Data separation In [START_REF] Lindell | Privacy preserving data mining[END_REF] cryptographic tools are being used to protect user data privacy when the id3 tree is constructed for association rules. The id3 tree is a widely known technique for data classification. The categorical data of a set of records is being constructed by choosing the attributes than containing the higher information gain. Information gain is expressed as conditional entropy and the problem of id3 construction is approximated by finding the attributes that information gain is maximized. The authors assume that data are split horizontally, thus the data analyzer in order to compute the conditional entropy of two users should separately and privately obtain the data from both. It turns out that information gain for an attribute between two users is expressed as (u 1 +u 2 )•log(u 1 + u 2 ). The problem has been addressed as a secure multi-party computation of this expression for two users.

Privacy preserving data classification on horizontally partitioned data has been addressed in [START_REF] Kantarcioglu | Privacy-preserving distributed mining of association rules on horizontally partitioned data[END_REF][START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF] as well. The solution is based on a privacy preserving protocol for sum computation based on randomization and privacy preserving union set computation. Those two functionalities can securely be used by an untrusted party to infer the global confidence of an attribute in order to infer the association rules that will classify the data. In [START_REF] Oliveira | Privacy-preserving clustering by object similarity-based representation and dimensionality reduction transformation[END_REF] privacy preserving clustering on vertically partitioned data is addressed by submitting only the similarities on objects and not the real data. However how the users are computing the similarities while at the same time preserving their privacy is not clearly addressed. Vaidya et al. tackle this issue by constructing a protocol for secure dot product computation without the use of a trusted party. However the communication cost for computing all the dot products between users is high [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF] Our Contributions As opposed to previous solutions we propose a scheme that is data independent and assures higher level of privacy. Previous solutions that are based on geometrical transformations do not scale for multidimensional data [START_REF] Oliveira | Privacy preserving clustering by data transformation[END_REF] and also there is no concrete security analysis with respect to the leakages of the protocol for example. We did not tackle our similarity problem with respect to data anonymization as anonymization does not fully assure data confidentiality. Moreover, data separation techniques in which data are split in between different sites are not always a real world scenario in which each user holds its data in its entire form.

III. PROBLEM STATEMENT

A. Similarity and privacy

We assume a set of n users. Each user U i holds its personal sensitive private data D i . An untrusted data analyzer A seeks to obtain D i from each user U i , where 0 ≤ i ≤ N . We consider each D i as a multidimensional vector of size m:

D i = (d 1 , d 2 , d 3 , • • • , d m ).
After the data collection, A is applying a similarity detection algorithm F over any pair of data vectors in order to identify similarities between them in order to further form clusters. During the detection of similarities in between data the privacy of users should not be compromised. As such we are looking for an obfuscation mechanism φ : R m → R m such that for any two vectors x, y:

F(D i , D j ) = F(φ(D i ), φ(Dj))
where φ will preserve the privacy of individual data and at the same time similarity detection through cosine computation will be compatible.

B. Cosine similarity

Cosine similarity is a widely used distance metric for numerical data. Cosine similarity [START_REF] Manning | Introduction to Information Retrieval[END_REF] depicts the geometrical similarity of two objects in an Euclidean space by measuring the angle θ formed by their vector representation in a n dimensional Euclidean space. The dot product < a

• b > of two vectors a,b is < a • b >= ||a|| • ||b|| cos θ , where ||a|| = n i=0 a i 2
is the norm of vector a and a i denotes the coefficients of this vector. Thus,

cos θ = < a • b > ||a|| • ||b||
and the more similar the data the closer the angle between their corresponding vectors is and the closer to 1 their cosine. The cosine similarity is our similarity detection function F. Intuitively, the security guarantee we require from a PPDA scheme is that given encrypted vectors Di an adversary cannot learn any information about the plaintext D i although it may learn the outpu of the function F.

C. Correctness and Privacy

IV. SOLUTION

A. Idea of Solution

The idea of the solution is to apply some transformations to original vectors which on the one hand preserve the angle between any pair of them and on the other hand assure privacy. Since rotation in a two dimensional space preserves angles, we apply this transformation to two-dimension vectors named as sub-vectors which originate from the data vector. Additionally, these sub-vectors are further randomly scaled and thus obfuscated while still not having an impact on the angle.

The reason why rotation and scaling are combined is that random scaling alone raises some security problems. Indeed, if only random scaling is applied then an adversary can discover whether the coordinates of that vector are similar or not. Hence thanks to the rotation, the adversary cannot discover similarities between one vector's coordinates. The mapping of vectors into subvectors also decreases the probability of discovering the original vector since the scaling factor differs from subvector to subvector.

B. Preliminaries

Vector scaling

Vector scaling with a scaling factor s is defined by a multiplication operation between the vector v and the identity matrix S in which the main diagonal has been substituted with the scale factor s.

v • S = v• s 0 0 s
Vector Rotation Vector rotation with an angle θ is defined by a matrix multiplication between the vector v and the rotation matrix

R θ : v • R = v• cos(θ) -sin(θ) sin(θ) cos(θ)

C. Protocol description

We now describe the details of the protocol with respect Definition 1.

Encryption During the encryption phase each user U i holds a vector with the random scaling factor s i :

D i = (d 1 , d 2 , d 3 , . . . , d m ) of size m. It generates subvectors of 2 dimensions d (k,l) i = d k d l . If m is odd then (m +
S j i = s j i • d (k,l) i
, if k and l are new coefficients of the subvector. That is, if any of the coefficients of the subvector d (k,l) i has been previously selected to form a vector then the old random scale factor s i must be used for d (k,l) i . Then the intermediate vector S i is further rotated with a rotation matrix R θ , where θ is the rotation angle:

dk,l i = S j i • R θ = S j i • cos(θ) -sin(θ) sin(θ) cos(θ) .
In the end each user

U i sends Di = ( d(1,2) i , d(2,3) i , • • • , d(k,l) i ), ∀k, l ∈ [0 • • • m]s.t : {k, l} = m to the data analyzer A.
In hereafter we will write d j i to denote the j th subvector of user U i and dj i for the j th encrypted subvector of user U i . As such the obfuscated mechanism φ consists of random scalings and rotations by an angle θ:

φ(d i ) = s j i • d k,l i • R θ .
Analyze The analyzer then performs the similarity detection function F over the encrypted data: ∀U i , U j , i = j :

F( di , dj ) =      cos( d1,2 i , d1,2 j ) . . . cos( d m/2 i , d m/2 j ) D. Correctness Theorem 2
The PPDA scheme presented above is correct.

Proof: It is known that cos(a, b) = <a•b> a • b = a T •b a • b .
For the proof of the theorem we need to prove the following three lemmas:

Lemma 1 The transpose of an orthogonal matrix A, A T is equal to its inverse A -1

Proof: It is known that:

A • A -1 = I A (1)
where I A it's the identity matrix of A. Also we obtain:

A • A T = A T 1,1 • A 1,1 • • • A T 1,m • A 1,m A T n,1 • A n,1 • • • A T n,m • A n,m =    1 • • • 0 . . . . . . . . . 0 • • • 1    = I A (2)
From ( 1), (2) we have that for any orthogonal matrix A, A T = A -1

Lemma 2 The multiplication two vectors a, b with a rotation matrix R preserves its cosine similarity.

Proof: cos(Ra, Rb) = <Ra•Rb> Ra • Rb = (Ra) T •Rb Ra • Rb = a T R T •Rb a • b = a T R -1 •Rb Ra • Rb = a T •b a • b = cos(a, b)
where

Ra = cos(θ) -sin(θ) sin(θ) cos(θ) a 1 a 2 = a and Rb = cos(θ) -sin(θ) sin(θ) cos(θ) b 1 b 2 = b Lemma 3
The random scaling of two vectors a, b with different random scaling factors r 1 and r 2 preserves its cosine similarity

Proof: cos(r 1 a, r 2 b) = <r1a•r2b> r1a • r2b = (r1a) T •r2b r1 a •r2 b = r1a T •r2b r1 a •r2 b = a T •b a • b = cos(a, b)
From lemma 1,2 and 3 we have that multiplication of a random vector and random scaling is a correct encryption mechanism. The proof of lemma 2 is based on lemma 1: the rotation matrix R is orthogonal and as such R -1 = R T . Furthermore the rotation doesn't change the vector norms.

V. SECURITY Theorem 1 The PPDA scheme presented above is secure according to definition 3.

Proof: The security of the scheme is based on the randomness of the scale factor S i and on the rotation matrix R θ . The data analyzer cannot recover the original vector D i of a user U unless it performs brute force guesses for the scaling factor and the Rotation matrix.

We observe security leakages when the obfuscated mechanism does not entail both random scalings and rotations. If each user only selects random scaling as the encryption mechanism then an attacker by obtaining a good guess for a coefficient of a user's vector it can recover the specific two dimensional vector by computing the inverse of the guessed element and multiplying it by the encrypted coefficient.

On the other hand, thanks to rotations the aforementioned problem is mitigated but the following one is appearing if used alone: if two users with secret vectors D i , D j respectively have the same value at the same position of their vectors then only by encrypting with a rotation matrix R θ of angle θ , the corresponding encrypted vectors would have the same value at this position. This violates the security definition 3. So in order for the cosine similarity to be securely preserved after the encryption of the vectors, both random scaling and rotations must by applied.

To be more precise with our security analysis, we consider two categories of adversaries: we define external adversaries as data analyzers and internal adversaries as users themselves.

External adversaries Data analyzers do not know the rotation matrix and as such the aforementioned attacks cannot happen as long as the angle θ of the rotation matrix is kept secret. The data analyzers cannot identify common values in a specific data vector because the rotation with an unknown angle adds an additional security level for the vectors.

Internal adversaries

We consider as internal adversaries the users that know the rotation matrix R θ . In such a scenario the user that has a good guess for the coefficient of another user can reveal only the coefficients that are involved in a common random scaling factor per vector. That is if U i has 5 coefficients and it defines cosine similarity in between the ((1,2), [START_REF] Lisovich | Inferring personal information from demand-response systems[END_REF][START_REF] Mclaughlin | Protecting consumer privacy from electric load monitoring[END_REF], [START_REF] Narayanan | Robust deanonymization of large sparse datasets[END_REF][START_REF] Agrawal | Privacy-preserving data mining[END_REF]) coefficients then an adversary with a good guess for the first coefficient can recover only the second and fifth coefficient and nothing more, since for the second subvector the user would choose different a random scaling factor.

VI. EVALUATION

We demonstrate the correctness of our protocol through an experimental evaluation setup. We obtain data originating from a personality experiment. We first cluster the data based on cosine similarity using a well known clustering algorithm. The same clustering algorithm is further applied over the encryption of the same data using φ which as already described combines rotation and random scaling. We proceed into an analysis of the data and next on the clustering algorithms that we use.

A. Data Set

The dataset contains an extract of the results from the Foursquare Personality Experiment1 which uses the mobile social network Foursquare2 combined with a standard personality test to allow the link between personality (as defined by the five-factor model [START_REF] Goldberg | An Alternative "Description of Personality": the Big-Five Factor Structure[END_REF]) and the places that people visit to be examined. To the best of our knowledge, this is the first time that it has been possible to correlate personality with place on such a granular level.

When accessing the experiment, users sign in using their Foursquare account, allowing us to access the list of venues which they have 'checked in' to on the Foursquare service. We access only this list, storing the venues that the user has been to and the number of times they have visited each venue, but without accessing or storing the information about the individual checkins -we do not store when each visit to the venue occurred, nor the order in which venues were visited. Once users have accessed the system they then take a 44-item personality test [START_REF] John | Paradigm shift to the integrative big five trait taxonomy[END_REF][START_REF] John | The big five inventoryversions 4a and 54[END_REF], revealing their five-factor personality scores. The five-factor model gives each person a score between 1 and 5 for each of the five personality traits: Openness, Conscientiousness, Extraversion, Agreeableness and Neuroticism.

The users participating in the study are a self-selecting group comprised of 173 people who both use Foursquare online location based tagging system and are willing to take part in a personality-based experiment.

B. Clustering

Clustering algorithms seek to group similar objects together. Similarity is measured with a distance metric which in our case is cosine similarity. Hierarchical clustering is a widely known approach for clustering. It constructs a binary tree of clustering objects that successively are merged under the same cluster with respect to the linkage metric. The linkage metric links clusters and objects together. It acts as an intergroup similarity measure. Two most popular linkage metrics are the complete metric which defines the maximum similarity between two objects as a verification to whether or not one object would be merged under the same cluster with another one and the single metric in which the minimum similarity is treated as the intergroup similarity metric. At the first step of the algorithm each object belongs to each own cluster. Then all the possible pairwise similarities between objects with respect to the defined distance metric are defined. Afterwards the algorithm iteratively merge clusters with respect to the linkage metric until there would be one cluster with the all the examined objects.

C. Simulation Setup and Results

We apply the hierarchical algorithm over the personality dataset with the complete linkage metric and based on cosine similarity.

The data consists of 173 different 5 dimensional vectors describing users' personality with respect to the 5 personality traits as previously described. We did not include venue visits frequency since we believe that personality traits are considered much more sensitive data compared to location information and that users would be more interested in hiding such information. We consider similarity on 3 subvectors per user data: the subvectors are constructed with the (1 st , 2 nd ), (3 rd , 4 th ) and (1 st , 5 th ) coordinates of the original vector respectively. Any pairwise subvector could be have chosen such that the union of the set of subvectors entail all the coefficients. The main similarity metric is computed as the average of the similarities between subvectors.

In order to protect their privacy, every user chooses a random scaling factor per two dimensions. After the random scaling process users apply the rotation operation to their partially obfuscated subvectors.

In figure 1 we plot the two dendograms of hierarchical clustering before and after the operation φ applied on data. The horizontal axis corresponds to cluster indexes that are formed by the algorithm and the vertical axis to the linkage similarity based on cosines. Clusters are connected with upside-down U-shaped lines. The clusters are exactly the same due to the correctness of the algorithm as has been previously proved. All the cosines between all the binomial coefficients of 2 over 173 elements has been computed. That results into a set of 14878 distances. For the linkage function we chose the complete option. Thus, two clusters will be merged together according to the maximum distance between their elements.

Results shown in figure 1 demonstrate the correctness of our protocol: Geometrical transformation on data based on random scaling and rotation is compatible with cosine similarity for clustering and in addition preserves individuals' privacy.

D. Discussion

In our experiments we use as a single point of similarity an aggregate output of each three per user similarities. This is the average of cosine similarities. As such during the clustering the similarity between points depicts similarities between the averages. We could have demonstrated three different scenarios during the clustering process one for each subvector in order to check the correctness of our obfuscation mechanism but since this has been demonstrated once the other experiments wouldn't add extra knowledge to us. We also want to state that the aggregate function should not always be used for every case. This would imply an inconsistency on correctness since many inputs could evaluate the same average similarity. Suppose for instance that data consist of user interests on m items and for each user n similarities per two dimensions are computed. Then a single aggregate function on user n similarities might group together during clustering dissimilar objects that average the same similarities but on different inputs.

VII. CONCLUSION

The interplay between data analysis and privacy is emerging rapidly. Researchers from machine learning area have highlighted the merit of data analysis operations. However this exposure of personal sensitive data, facilitates privacy violations. Adversaries by gaining access to personal information can learn the real identity of users and overcome data legal regulations and restrictions. That postulates a mechanism that would shield individual data confidentiality. This would not be of significant value since data encryption to protect data confidentiality is more mature and well analyzed than 30 years before. The tricky approach is to allow operations on data by the security mechanism while at the same time personal sensitive information is not exposure to third parties.

In this paper we have presented a mechanism for privacy preserving clustering that is based on geometrical transformation of objects. Data are encrypted appropriately such that operations with respect to cosine similarity detection are compatible. We proceed into an analysis of the security risks of each operation and we conclude that the most secure way is a combination of random scalings and rotations. The rotation angle even if its known to the users it can only be used to reveal some coordinates of the vector only if the user has a good guess for one of the coordinates. Still this weakness is not of crucial importance for external adversaries (data analyzer) since they don't know the rotation matrix. Without scaling and only with rotation, similarities on the same position coordinates are possible to occur by both internal and external adversaries. This is mitigated by a random scaling factor, which is different per user and per subvectors with no common coefficients. We proceed into an experimental evaluation of a scheme in order to demonstrate its correctness. Personality traits have been obtained by 173 users and identical clustering results have been observed before and after the obfuscation proposed solution.

Definition 1 (

 1 Privacy Preserving Data Analysis(PPDA)) In a Privacy preserving data analysis scheme a set of n users U i are perturbating their data and afterwards the data are sent to the data analyzer A for analysis. PPDA consists of 2 polynomial time algorithms P P DA = Encrypt,Analyze: Encrypt(D i ) → Di : It takes as input user data and it outputs the encryption of it. Analyze( Di , Dj ) → F( Di , Dj ): It takes as input two encrypted data vectors and it outputs the result of a data analysis algorithm F( Di , Dj ). Definition 2 (Correctness) A PPDA scheme is correct if for all pairwise combinations of data D i , D j the analyzer executes Analyze(Encrypt(D i )) and it obtains F( Di , Dj ) = F(D i , D j ), Definition 3 (Confidentiality) Let Υ = (Encrypt, Analyze) be a PPDA scheme. Υ is defined as confidential if any adversary cannot recover D i from Di

  1)/2 are constructed, otherwise if m is even then we have m/2 subvectors. In general we have m/2 subvectors. Afterwards each user choses a random scaling factor for each subvector and it scales each subvector d

	(k,l)
	i

http://www.cs.cf.ac.uk/recognition/foursqexp

http://www.foursquare.com

Acknowledgement This research has been funded by RECOGNITION grant 257756, an EC -FP7 Future Emerging Technologies project concerning Self-Awareness in Autonomic Systems.


Bilal Komati
email: bilal.komati@femto-st.fr

Muhammed R Pac
email: muhammed.pac@mavs.uta.edu

Isura Ranatunga

C Édric Cl

Dan O Popa
email: popa@uta.edu

Philippe Lutz
email: philippe.lutz@femto-st.fr

EXPLICIT FORCE CONTROL V.S. IMPEDANCE CONTROL FOR MICROMANIPULATION

This paper presents a study of different force control schemes for controlling contact during manipulation tasks at the microscale. Explicit force control and impedance control are compared in a contact transition scenario consisting of a compliant microforce sensor mounted on a microrobotic positioner, and a compliant microstructure fabricated using Silicon MEMS. A traditional double mass-spring-damper model of the overall robot is employed to develop the closed-loop force controllers. Specific differences between the two control schemes due to the microscale nature of contact are highlighted in this paper from the experimental results obtained. The limitations and tradeoffs of the two control laws at the microscale due to the presence of backlash are discussed. A simple method to deal with the pull-off force effects specific to the microscale is proposed. Future improvements of the impedance control schemes to include adaptation are discussed in order to handle objects with unknown stiffness.

INTRODUCTION

The development of microsystems (MEMS and MOEMS) has led to increasingly complex microstructures and smaller components. This development has increased the need of microassembly and micromanipulation. In the last few decades, researches have defined many micromanipulation and microassembly techniques [START_REF] Savia | Contact micromanipulation-survey of strategies[END_REF], and have developed many robotic systems for microassembly [START_REF] Dechev | Development of a 6 degree of freedom robotic micromanipulation for use in 3d mems microassembly[END_REF][START_REF] Das | µ 3 : Multiscale, deterministic micro-nano assembly system for construction of on-wafer microrobots[END_REF]. The role of these robotic systems is to perform precise positioning and faster processes.

For automating microassembly or micromanipulation tasks, many of the past work deals with vision-based control [START_REF] Wang | Automated 3-d micrograsping tasks performed by visionbased control[END_REF][START_REF] Anis | Automated selection and placement of single cells using vision-based feedback control[END_REF]. In many cases, vision feedback can only enable position control and ignores the interaction forces like gripping forces and contact forces between the grasped micropart and the substrate. In some other simple cases, force information can be derived from vision information if the contact conditions are simple and the environmental stiffness is known [START_REF] Greminger | Vision-based force measurement[END_REF][START_REF] Liu | Vision-based cellular force measurement using an elastic microfabricated device[END_REF]. However, this becomes difficult if both the gripper and the environment are compliant, and if the stiffness of the microparts is unknown. As a result, new microgrippers with integrated force sensing have been recently developed to enable force-feedback control during manipulation at the microscale, such as FemtoTools microgrippers [8]. Furthermore, at the microscale, interaction forces experience significant nonlinear effects that cannot be simply modeled with a spring, such as adhesive forces. It is notably manifested by pull-off force which can be 84 times the 100µm x 1000µm x 1000µm silicon micropart weight [START_REF] Rabenorosoa | Measurement of pull-off force for planar contact at the microscale[END_REF]. Another important reason to take the microscale forces into consideration is the fragility of the components at small scale. Indeed, microparts and microgripppers can easily break during manipulation and handling.

Issues relevant to robot force control at the macroscale are well known due to extensive research conducted in the 80's and 90's. Several classic control schemes have been developed including explicit force control, admittance control [START_REF] Seraji | Adaptive admittance control: An approach to explicit force control in compliant motion[END_REF], impedance control [START_REF] Hogan | Impedance control -an approach to manipulation. i -theory. ii -implementation. iii -applications[END_REF][START_REF] Singh | An analysis of some fundamental problems in adaptive control of force and impedance behavior: theory and experiments[END_REF], and hybrid force/position control [START_REF] Raibert | Hybrid position/force control of manipulators[END_REF]. Recently, several of these control strategies have been used in microscale [START_REF] Komati | Automated guiding task of a flexible micropart using a two-sensing-finger microgripper[END_REF][START_REF] Lu | A force-feedback control system for microassembly[END_REF] but no comparative study has been yet performed to see whether the physics of the microscale adds anything new to the existing body of knowledge.

This paper investigates differences between force control schemes due to scaling. The work in this paper is limited to studying explicit force and impedance controllers, due to the fact that many other schemes are based on them. For instance, admittance control is similar to the impedance control since the admittance is the inverse of the impedance and the hybrid force/position requires to have many axes and to control some axes in position and the others in force.

The importance of this work is that it provides a good theoretical and experimental base for research using force control for micromanipulation and microassembly applications. The paper is organised as follows. The experimental setup used in this paper and some of the microscale specific effects are explained in Section 2. The system modeling and some force control laws formulation are developed in Section 3. Section 4 presents the experimental results obtained for the force control laws integrated into the experimental setup. Section 5 concludes the article.

FORCE CONTROL AT MICROSCALE

A motivating microscale scenario for this paper is depicted in this section and some of the microscale specific effects are explained in order to take them into consideration for the control design.

Experimental Setup

The hardware shown in Fig. 1 and 2 was used to control the interaction between a MEMS force sensor and a compliant environment. A microstructure made of 100 µm thick Silicon via microfabrication was used as the spring mechanism of the environment. A force sensing probe from FemtoTools AG, Switzerland, used as a manipulator, was attached to a motorized stage and the spring mechanism was attached to a stationary base. The stage was controlled through a National Instruments, Austin, Texas, USA servo motion controller. The force feedback was acquired through an analog input data acquisition board, and the controller was implemented in using NI LabVIEW.

The motorized stage from Newport Corporation, Santa Ana, California, USA, has a minimum incremental motion of 0.1 µm and an uni-directional repeatability of 0.5 µm. The stage also has a backlash of 12 µm.

Scaling Issues

There are many differences between contact models at macroscale and microscale. We can mention the different predominant forces, the different signal to noise ratios for sensors and the added nonlinearities/positioning errors for actuators. Surface force being predominant at the microscale, it is required to evaluate the influence of surface forces during the studied task. These forces appear when a contact between the environment and the force sensor happens. To automatically achieve a contact/non-contact transition at the microscale, pull-off force has to be accounted for. It is the force necessary to break a contact due to stiction and has a predominant role when contact happens between microscale objects.

It was shown in [START_REF] Rabenorosoa | Measurement of pull-off force for planar contact at the microscale[END_REF] that the pull-off force can reach 196µN for a planar 50µm x 50µm silicon contact surface that can typically happen in the present case. During the contact/non contact transition, the breaking of the lateral contact may induce a pull-off force for each side of the contact. In this case, the evolution of the lateral contact force according to the position of the micropart can follow curves in Fig. 3,i.e once a contact (micropart/environment) happens, the pull-off force acts as a sticking effect. As shown in Fig. 3, an opposite force is applied during the withdrawal to break the contact. At point A, the lateral contact force is zero but the contact remains due to adhesive force. The contact is broken at B when enough force is applied to balance the adhesive force.

The signal to noise ratio is another difference between the microscale and macroscale. This is caused by the fact that the signals at the microscale have large bandwidths, small amplitudes and high noise. The noise is due to the type of components used, their sensitivity to the environmental conditions (temperature, humidity, small vibrations) and the microfabrication uncertainties. To deal with these microscale specificities, some filters The bandwidth of microsystems usually contains high frequencies, so using low pass filters will affect the dynamics of the system. In addition, the controller must be able to deal with the noise and must not confuse between contact force and noise.

SYSTEM MODELING AND CONTROL

In this section, the model of the system used in this paper is discussed. Then, explicit force control and impedance control are studied showing the differences between these two strategies.

Model of the system

The contact interaction between a robot and the environment is typically modeled by mass-spring-damper models. In this paper, the proposed models are divided into two parts: an environment part modeled by a mass-spring-damper and a gripper part modeled also by mass-spring-damper. This corresponds to a flexible-gripper, flexible-part interaction scenario typically encountered at the microscale. The proposed model is shown in Fig. 4.

In Fig. 4, m is the mass of the contact surface (gripper + environment), m s , k s and d s are respectively the mass, the stiffness and the damping of the gripper, k e and d e are respectively the stiffness and the damping of the environment, x s is the actual position of the stage which moves the gripper, x d and x are respectively the desired and the actual position of the environment. x, x s and x d are relative positions to the initial positions before contact.

During contact, the dynamics equation is given by (1):

m ẍ = F gripper→m + F environment→m (1)
Where F gripper→m and F environment→m are respectively the forces exerted form the spring and damper of the gripper to the mass and from the spring and damper of the environment to the mass. The dynamics of the system is given by (2):

m ẍ + f m + f e = 0 ( 2
) FIGURE 5. EXPLICIT FORCE CONTROL SCHEME
where f m is the force exerted by the mass on the gripper and f e is the force exerted on the environment. f m given by (3), is the force measured by the force sensor.

f m = -F gripper→m = d s ( ẋ -ẋs ) + k s (x -x s ) (3)
The force exerted on the environment f e is given by [START_REF] Wang | Automated 3-d micrograsping tasks performed by visionbased control[END_REF].

f e = -F environment→m = k e x + d e ẋ (4)
Robots are usually controlled by motor efforts (force or torque). In some applications, and especially at the microscale, the robots are controlled in position or velocity instead. In this case, we change the existing control schemes where the calculated command is the force to a controller in which the calculated command by the controller is an incremental position or velocity of a moving stage. The aim is to control the force exerted to the environment f e in order to guarantee the stability of the grasp in micromanipulation, and also to not break components.

Explicit Force Control

The explicit force control aims to control the force exerted on the environment f e in reference to a desired force f d [START_REF] Volpe | A theoretical and experimental investigation of explicit force control strate-gies for manipulators[END_REF]. Two types of explicit force control exist: force-based and inner position loop based. The most commonly discussed technique in the literature is the force-based explicit force control in which P, PI or PD controllers are used [START_REF] An | Dynamic stability issues in force control of manipulators[END_REF][START_REF] Colgate | An analysis of contact instability in terms of passive physical equivalents[END_REF][START_REF] Eppinger | Understanding bandwidth limitations in robot force control[END_REF]. In this article, the inner position loop based explicit force control is used because the robotic system is controlled by position. The explicit force control scheme used in this paper is given by Fig. 5. The force controller calculates the position command x s using the error ε between the desired force and the measured force exerted on the environment f e and sends it to the controlled stage. If f e is not measured, it should be estimated using the position and another measurement, if possible, f m . The form of the controller changes in function of the application and of the requirements of the system. The most commonly used controllers are a P, PI or PD controllers. These controllers are used for their simplicity and their effectiveness. Other types of controllers could be used as well. An incremental controller like the one used in [START_REF] Komati | Automated guiding task of a flexible micropart using a two-sensing-finger microgripper[END_REF] could also be used (see Fig. 6). The idea of this controller is to compare the desired force to the output force and then the controller sends . The advantage of this type of controller is that it is easy to implement, robust and effective even if the system is nonlinear. The drawbacks of this controller is that the response of the system is slow or it chatters as a function of the gain of the controller (see Section 4). A PD controller could be used if the reference force is constant which is usually the case. In this case, the command could be calculated using [START_REF] Anis | Automated selection and placement of single cells using vision-based feedback control[END_REF].

x s = K p ( f d -f e ) -K d ḟe (5)
Where f e in ( 5) is the measured or the estimated force exerted on the environment.

Impedance Control

The aim of the impedance control is to control the dynamics of contact. The dynamics of contact are set to follow a desired impedance. It has been demonstrated in [START_REF] Volpe | Real and artificial forces in the control of manipulators: Theory and experiments[END_REF] that an impedance controller with force feedback contains an explicit force controller. In the case of impedance control with force feedback, the force is also controlled in reference to a desired force. Using the Laplace transform of (2) and ( 3), ( 6) could be derived. The position x is replaced by X(s) = f m (s) d s s+k s + X s (s) using (3):

ms 2 X s (s) + ms 2 + d s s + k s d s s + k s F m (s) + F e (s) = 0 ( 6
)
where s is the complex argument, X s , F m and F e are the Laplace transforms of x s , f m and f e respectively. The desired impedance proposed by Hogan in [START_REF] Hogan | Impedance control -an approach to manipulation. i -theory. ii -implementation. iii -applications[END_REF], using the Laplace transform, is given by [START_REF] Liu | Vision-based cellular force measurement using an elastic microfabricated device[END_REF].

X d (s) -X(s) = 1 M d s 2 + D d s + K d F e (s) (7)
where X d is the desired position, M d , D d and K d define the desired impedance parameters of the system. Using ( 6) and ( 7), the command sent to the stage x s is given by (8): An external force control loop could be added to the internal impedance controller. The goal of this controller is not only to control the impedance of the contact but also to control the exerted force in reference to a desired force. The final impedance control scheme used in this paper is given by Fig. 7 using the controller equation defined in (8) where the controller has two inputs, the desired position x d , calculated by the force controller, and the force measured by the force sensor f m . The output of the controller x s is the position command sent to the system. The force controller in Fig. 7 could be a P, PD, or PI controller. The proportional force controller is chosen in this case because of its simplicity and to guarantee the stability of the controller which is not the case with the integral controller.

X s (s) = M d s 2 +D d s+K d (M d -m)s 2 +D d s+K d X d (s)- (M d -m)s 2 +(D d -d s )p+(K d -k s ) (d s s+k s )((M d -m)s 2 +D d s+K d ) F m (s) (8)

EXPERIMENTAL RESULTS

In this section, the different types of force control discussed in Section 3 are tested, the dynamical behaviors will be shown and the performances will be compared. These experiments were carried out on the experimental system depicted in Fig. 1 and

Estimation of the force exerted on the environment

Before detailing the experimental results, the force feedback is the force measured by the force sensor f m which is not the same as the force exerted on the environment f e as shown in [START_REF] Dechev | Development of a 6 degree of freedom robotic micromanipulation for use in 3d mems microassembly[END_REF]. Thus, f e should be estimated. Using (2), ( 3) and ( 4) f e could be estimated using two possible equations ( 9) or [START_REF] Seraji | Adaptive admittance control: An approach to explicit force control in compliant motion[END_REF]. In the following two equations, the position x is replaced by X(s) =

In [START_REF] Rabenorosoa | Measurement of pull-off force for planar contact at the microscale[END_REF], f e is estimated using the measurement of the position, x s , the measurement of the stage position given by the encoder, and 9) estimates f e without noise. However, [START_REF] Seraji | Adaptive admittance control: An approach to explicit force control in compliant motion[END_REF] estimates f e using f m and ḟm . Where f m is the force measured by the force sensor which is noisy (for the force sensor used the noise has amplitude of 100 µN). Since ḟm is very noisy, f e will also be very noisy. The amplitude of noise could be reduced, in our case, using a low pass filter to filter the measured force f m . Using the estimation of f e given by ( 9) appears to be a good idea. However, a backlash problem of the stage causes a big problem for estimating f e because the measurement of the stage will not be reliable if many reference signals are applied. Thus, ( 10) is used to estimate f e . Before starting the experiments, the parameters used for control m, d s and d e are calculated theoretically and k e and k s are estimated experimentally. The calculation of the mass was done using the volume of the system. The damping coefficients were calculated using the values of the damping of the Silicon and the sections of the system. k s was estimated by applying a force by the force sensor to a stiff environment and measuring the displacement of the stage.

Experimental results for the explicit force control

As discussed in Section 3, two types of explicit force control are tested and compared: a PD controller and an incremental controller. The response of the system in presence of an incremental control and using the estimation of f e given in ( 9) is shown in Fig. 8.

First, the effect of the step (gain in Fig. 6) of the incremental controller influences the behavior of the system. Big step increments imply a low response time but the amplitude of chattering in the static part is also big. However, small step increments implies a big response time and a smaller amplitude of chattering in the static part. Secondly, in these figures, the effect of backlash appears. The estimated force f e returns to zero while the measured force f m does not. The force feedback being the estimated value of f e using (9), the controller controls the estimated force f e correctly but the estimation of f e is wrong because of the backlash problem.

Using a PD controller could be a solution to have a good response time without chattering in the static part. This type of controller is used because it is simple and gives good performance. The controller used is given by ( 5). The performance is given in Fig. 9. In this case, the estimation of f e given by [START_REF] Seraji | Adaptive admittance control: An approach to explicit force control in compliant motion[END_REF] with a low pass filter is used. Fig. 9 shows that f e and f m follow the same shape and they are almost the same in the static part. However, f e and f m are noisy. The response time of the system is good (≈ 1s). It could be improved by modifying the gains of the PD controller but there is a risk that the system will become unstable in this case.

Experimental results for the impedance control

The impedance control block shown in Fig. 7 and the controller given in (8) are used to control the system. Fig. 10 shows the response of the system using the impedance control scheme defined. The system response is a first order with a response time of ≈ 1s. The behavior is close to the explicit force control. This fact is because the impedance control is used with an external force control feedback. The main difference is in terms of the impedance of the system during contact. The impedance control aims to set the dynamics of the system to a desired impedance defined by the user. Comparing f e in Fig. 9 and Fig. 10, the response of the controlled system is first order in Fig. 10 while in Fig. 9 it exhibits a transient behavior before setting f e to f d .

In impedance control, the desired dynamics of the response of the system is set using three parameters M d , D d and K d . Thus, the controller controls at the same time the impedance of the control and the f e in reference to f d . Some experiments have shown that the use of the proposed impedance control scheme is limited to a flexible environment. However, the stability of the proposed controller is not guaranteed for a very stiff environment as shown in Fig. 11.

A simple comparison between the explicit force control and impedance control results shown in Fig. 9 and Fig. 10 shows that the explicit force controller is simpler than the impedance controller in terms of controller complexity. Both of them are robust. The contact transition for the impedance control is better than the explicit force control. The impedance control is more flexible in design (3 parameters to control) and shows good disturbance rejection.

For instance, the controller is able to set f e to zero when a zero force reference is applied but it is not able to break the contact due to pull-off force. The specific effect due to the microscale is discussed in the following section.

Experimental results showing the pull-off force effect

As shown in Section 2, the pull-off force could appear when a contact happens. The pull-off force acts as a sticking effect. During the experiment, once the contact happens and we aim to separate the contact, setting the desired force to zero will not separate the contact, the contact will persist although the measured force is zero. An easy way to separate the contact is to apply a negative force reference for a short time and then return the desired force to zero. When a negative force reference is applied, the controller aims to set the desired force to the reference and then a command is sent to the stage to come back and then the contact is broken. During this phase, a negative measured force appears due to the pull-off force. This force is not constant during the experiments. It varies as a function of many variables (angle, surface, etc...) [START_REF] Rabenorosoa | Measurement of pull-off force for planar contact at the microscale[END_REF]. Fig. 12, shows the effect of pull-off force on the system. The pull-off force is the negative part of the force f e . It appears while breaking the contact. The contact is not broken directly when the force returns to zero.

Fig. 12 shows also the effect of modifying the estimated values of the parameters. This modification changes the response of the system to a second order with an overshoot in place of a first order response. Other experiments have shown that the impedance controller behavior is acceptable until a parameter change of 40 %. More than 40 %, the reponse of the system will not be acceptable and the system could become unstable.

The problem of signal to noise ratio is avoided, in our case, by adding a low pass filter to the signal because the bandwidth of the system does not contain high frequencies. The results show that the noise level of the output signal f e is small due to filtering.

CONCLUSION

In this paper, a comparison between explicit force control and impedance control for microscale manipulation applications was carried out using experimental results. It was shown that unique effects specific to the microscale affect the effectiveness of these force controllers. Not surprisingly, impedance control showed better performance than explicit force control. Similar to the macroscale, impedance control is better at controlling the dynamics of contact between the manipulator and object. But unlike the macroscale, impedance control is also better at exerting forces on the environment, and more robust at handling flexible components with unknown stiffness. The impedance control scheme used is robust for flexible components and for a small variation of elements. The use of impedance control is limited in presence of a stiff environment. Another limitation would be the parameter uncertainties. Results have shown that the impedance control scheme used in this paper was able to deal with up to 40 % change in the parameters. It was shown that most of the challenges in force control are common for microscale and macroscale but the main differences are the presence of pull-off force at microscale and the signal to noise ratio. A simple method to deal with the pull-off force was proposed. Filtering solves the main problems of the signal to noise ratio, at the expense of bandwidth. To use the impedance control, the parameters of the system should be known m, k e , k s , ... which was the case in this paper. If some parameters are unknown, an adaptive impedance controller could be used to estimate the unknown parameters during the experiments. This will be the focus of future work.

This paper shows that the use of impedance control for microscale is a promising topic in coming years specially with the progress of force control for some microassembly and micromanipulation applications. The impedance control could be used for many microassembly tasks (for picking and releasing a micropart, for guiding a micropart in a rail or for inserting a micropart in a hole). This work was done for a 1 DOF moving stage and it will be extended to more complex systems.

FIGURE 1 .

 1 FIGURE 1. THE DIAGRAM OF THE EXPERIMENTAL SETUP.

FIGURE 2 .

 2 FIGURE 2. SIDE IMAGE OF THE SETUP USED.

FIGURE 3 .

 3 FIGURE 3. THE EVOLUTION OF THE LATERAL CONTACT FORCE IN THE PRESENCE OF PULL-OFF FORCE DURING LEFT SIDE AND RIGHT SIDE CONTACTS IN THE RAIL.

FIGURE 4 .

 4 FIGURE 4. SYSTEM MODEL BASED ON SPRING DAMPER

FIGURE 6 .

 6 FIGURE 6. INCREMENTAL CONTROLLER

FIGURE 7 .

 7 FIGURE 7. IMPEDANCE CONTROL SCHEME

  2 at the University of Texas at Arlington. The control schemes shown in Fig. 5 and 7 consist of motion control, force sensing hardware and a control program developed in LabView as in Fig. 1.

F

  e (s) d e s+k e using (4): F e (s) = d s d e s 2 + (d s k e + d e k s )s + k s k e ms 2 + (d s + d e )s + (k s + k e ) X s (s) (9) F e (s) = d e s + k e ms 2 + d e s + k e F m (s)

FIGURE 8 .

 8 FIGURE 8. SYSTEM RESPONSE FOR AN INCREMENTAL FORCE CONTROLLER (a) WITH A BIG STEP OF THE CON-TROLLER, (b) WITH A SMALL STEP OF THE CONTROLLER

  k e was estimated by applying a force by the force sensor to the flexible environment used and measuring the displacement of the environment. The values used for calculating the control laws are m ≈ 70 mg, d s ≈ d e ≈ 0.3 Ns/m, k e ≈ 20 N/m and k s ≈ 5000 N/m.

FIGURE 9 .FIGURE 10 .

 910 FIGURE 9. SYSTEM RESPONSE FOR A PD FORCE CON-TROLLER

FIGURE 11 .

 11 FIGURE 11. SYSTEM RESPONSE TO IMPEDANCE CONTROL IN PRESENCE OF A STIFF ENVIRONMENT

FIGURE 12 .

 12 FIGURE 12. THE PULL-OFF FORCE APPEARS WHILE BREAK-ING THE CONTACT. EXPERIMENT DONE FOR IMPEDANCE CONTROL SCHEME

ACKNOWLEDGMENT

The authors would like to thank the Net4m project for funding the travel of Bilal Komati from the University of Franche-Comté to the University of Texas at Arlington, the region Franche-Comté in France and the University of Texas at Arlington Research Institute for funding the equipment and hosting the experiments presented in this paper.