Charles Hudin
email: charles.hudin@cea.fr

Jose Lozada
email: jose.lozada@cea.fr

Vincent Hayward
email: vincent.hayward@isir.upmc.fr

Localized Tactile Stimulation by Time-Reversal of Flexural Waves: Case Study With a Thin Sheet of Glass

Keywords: H, 5, 2 [Information Interfaces and Presentation]: User Interfaces-Haptic I/O

This paper addresses the issue of producing localized tactile stimuli on a transparent surface. An approach based on time reversal of acoustic waves is presented and implemented on a thin glass surface actuated by piezoelectric transducers located at the periphery. The physical performance measurement, completed by a user study demonstrates the ability to provide localised and perceivable tactile stimulation.

INTRODUCTION

Tactile feedback is an important component of interaction design research [START_REF] Maclean | Putting haptics into the ambience[END_REF][START_REF] Jones | Tactile displays: Guidance for their design and application[END_REF]. Feedback provided through multiple sensory channels can increase task performance, for example in the context of interaction with mobile devices, or more generally, enhance usability [START_REF] Oulasvirta | Interaction in 4-second bursts: the fragmented nature of attentional resources in mobile HCI[END_REF][START_REF] Burke | Comparing the effects of visual-auditory and visual-tactile feedback on user performance: a meta-analysis[END_REF][START_REF] Pasquero | Tactile feedback can assist vision in mobile interaction[END_REF]. In such applications, stimulating the fingertip through a transparent surface has special importance.

Several approaches have been proposed to elicit tactile sensations from a transparent medium, beyond simply vibrating the front plate or the whole case of a device. When it comes to textures or small tactile variations experienced while sliding a finger on a smooth surface, non-linear acoustic pumping is able modulate friction by vibrating the surface at ultrasonic frequencies to create an air film between the surface and the finger [START_REF] Giraud | Design of a transparent tactile stimulator[END_REF][START_REF] Lévesque | Enhancing physicality in touch interaction with programmable friction[END_REF][START_REF] Biet | Squeeze film effect for the design of an ultrasonic tactile plate[END_REF][START_REF] Chubb | Shiverpad: A glass haptic surface that produces shear force on a bare finger[END_REF][START_REF] Watanabe | A method for controlling tactile sensation of surface roughness using ultrasonic vibration[END_REF]. Electrovibration takes advantage of electrostatic forces to attract the finger toward the surface, resulting in an increase of friction [START_REF] Mallinckrodt | Perception by the skin of electrically induced vibrations[END_REF][START_REF] Strong | An electrotactile display. Man-Machine Systems[END_REF][START_REF] Bau | TeslaTouch: electrovibration for touch surfaces[END_REF]. Of course, the whole surface can be vibrated, provided that the position of the finger be accurately known with a resolution commensurate with the size of the details to be rendered [START_REF] Wiertlewski | Causality inversion in the reproduction of roughness[END_REF], which trades off actuation complexity for sensing complexity.

These techniques do not lend themselves naturally to producing localized stimuli, let alone stimulating multiple fingers independently, unless special precautions are used, such as the use of multiples electrodes for electrovibration [START_REF] Tang | A microfabricated electrostatic haptic display for persons with visual impairments[END_REF], reducing an already weak effect, or producing patterns of constructive or destructive wave interferences for acoustic pumping [START_REF] Kim | Traveling vibrotactile wave-a new vibrotactile rendering method for mobile devices[END_REF], an approach that offers only limited options.

We previously demonstrated that the computational time reversal of acoustic waves was a viable approach to achieve localized tactile stimulation in a transparent medium [START_REF] Hudin | Tradeoffs in the application of time-reversed acoustics to tactile stimulation[END_REF]. With this technique, transducers located at the periphery of a stretched membrane produced flexural waves that propagated to interfere constructively, at a given time and at a given place, to produce localized mechanical deformation.

In the reference [START_REF] Hudin | Tradeoffs in the application of time-reversed acoustics to tactile stimulation[END_REF], we analysed from first principles the conditions under which computational time reversal could be applied to tactile stimulation. We also exemplified this technique in the case of a stretched BoPET membrane (biaxially-oriented polyethylene terephthalate). In this application, using a membrane as a propagation medium is quite demonstrative but it is not practical, owing to the drift in wave propagation velocity in the face of small mechanical and thermal instabilities. In the present article, we describe the application of time reversal to a cavity made of an ordinary sheet of glass, consumer-electronics-grade piezoelectric actuators, and simplified signal processing. Collectively, these improvements yield a system demonstrating much greater practically. We then show by a simple detection and discrimination study that this simplified equipment can elicit an easily detectable tactile sensation localized within a 1 cm 2 region.

OPERATION PRINCIPLE AND REALIZATION

Brief Recall of the Time Reversal of a Wave Field

For the sake of exposition, consider first a reverberant cavity with no attenuation. The wave propagation equation, ∂ 2 u/∂t 2 = c 2 ∇ 2 u, with u denoting material displacement, and t denoting time, involves even-order time derivatives only. The solutions, φ (x,t), of a given propagation problem, including its initial and boundary conditions, are thus symmetrical, that is, φ (r,t) = φ (r, -t). Since the time-reversed, or time-symmetric field, φ (r, -t) is a solution of the same problem, it propagates as time grows until reaching the initial condition at time t = 0. If this initial condition is an impulse force exerted at some point of the domain, the direct solution φ (r,t) is a diverging wave-front while the time reversed one would be a converging wave-front. The energy that propagated from a point to the whole volume can be back-propagated to its initial point.

At first sight, the creation of a time-reversed wave-front seems to require an entire direct solution record at every point of the domain. In particular, intuitively, such process would also require a very large collection of transducers able to sample space sufficiently finely. Surprisingly, such is not the case. The Fresnel-Kirchhoff integral theorem states that a wave field inside a volume can be entirely retrieved from the value of the solution and from that of its first derivative on a surface enclosing it. In fact, it is possible to use a finite set of transducers on the boundary of a domain to record the direct field and then to reconstruct an approximation of the same time-reversed field. This insight is behind the fundamental principle of the computational time-reversal of an acoustic field, as initially described by Fink and collaborators [START_REF] Fink | Time reversal of ultrasonic fields. i. basic principles. Ultrasonics, Ferroelectrics and Frequency Control[END_REF][START_REF] Wu | Time reversal of ultrasonic fields. II. experimental results[END_REF].

Accounting for reflections of waves at the boundaries of the domain leads to the notion of virtual sources and sinks, just like the reflection of light on a mirror leads to the notion of virtual sources. With properly designed cavities, it is possible to reduce the number of transducers down to a single one to achieve the approximate reconstruction of a field by computational time-reversal [START_REF] Draeger | One-channel time-reversal in chaotic cavities: Experimental results[END_REF]. This reduction comes with a tradeoff, however. The number of useful virtual transducers is related to the number of wave reflections on the boundaries the domain, and by consequence to the duration, T , of the recorded signal of the direct field.

Generally speaking, the quality of the focusing process can be quantified with reference to an ideal delta function. An important measure of quality is the contrast ratio, C, the ratio of the amplitude reached at the focused point over the RMS value of displacement elsewhere. The contrast ratio in general increases with the number of transducers, N, either real or virtual. It is also a function of the recording time, T , but up to a limit. Beyond a given time, T c , characteristic of a particular cavity, new information brought about by additional virtual transducers becomes redundant and the contrast ratio tappers off.

The characteristic time is equal to the inverse of the average difference of the frequencies of consecutive modes, that is, it is related to the modal density of the cavity T c = 1/∆ f . A further limit to contrast enhancement when T becomes greater than the attenuation characteristic time, τ, beyond which no new information is added. The amount of information contained per unit duration of signal is also related to its bandwidth, B. Previously cited references show that in a 2D cavity, the contrast ratio obeys

C ≃ √ BNT , (1)
as long as NT ≪ T c and T ≪ τ, while the amplitude at focused point U peak obeys,

U peak ∝ BNT, (2)
as long as T ≪ τ.

The reader is referred to [START_REF] Hudin | Tradeoffs in the application of time-reversed acoustics to tactile stimulation[END_REF] for more details regarding the various engineering tradeoffs needed to achieve computational timereversal for use in tactile stimulation.

PHYSICAL REALIZATION 3.1 Mechanical design

We used a rectangular glass sheet of dimensions 63 × 102 mm 2 and thickness 0.2 mm. Its edges sides were bonded to a rigid supporting frame. The optimal thickness of piezoelectric transducers, when used to actuate a glass plate is 1/4 of the plate thickness [START_REF] Jones | Optimal design of piezo-actuators for active noise and vibration control[END_REF]. The diameter of the transducers limit the shortest usable wavelength. The selected transducers were eight piezoelectric diaphragm (Murata 7BB-12-9) with a diameter of 12 mm and a thickness of 0.120 mm. Their bottom electrode layers were electrically grounded and bonded with epoxy resin to the glass surface at a distance d ≃ 5 mm of sides and with a distribution depicted in fig. 1. An uneven distribution of transducers aims at avoiding symmetries that would give correlated waveforms. The first resonance frequency of the device was f 0 = 170 Hz. The attenuation time, τ = 3 ms, was found by fitting a decreasing exponential on the envelope of an impulse response. The characteristic time, T c = 10 ms, was calculated in the same way as in [START_REF] Hudin | Tradeoffs in the application of time-reversed acoustics to tactile stimulation[END_REF]. The sampling frequency was F s = 50 kHz, giving a bandwidth B = 25 kHz.

Signal acquisition and processing

The first step of a time reversal process is to record the direct propagation field. Since the aim is to create a localised tactile feedback, the appropriate direct field is the response to a point displacement.

The propagation equation is linear, therefore any shape can be created on the surface by summing the weighted contributions of responses at individual points. It is therefore sufficient to record the impulse responses, h i j (t), between each pair of points, j, and transducers, i. The reciprocity principle can be advantageously applied to ease the recording step. This principle states that the electric potential obtained across the electrodes of any transducer, i, resulting from the displacement of any point, j, is identical to the displacement measured at point j once an impulse of potential is applied to transducer i. Therefore, there is no need to stimulate the surface with a hard-to-achieve displacement impulses in order to record the responses at the transducer locations, but rather to apply voltage impulses to the actuators, which is easy, and to record the displacement at point j. Since piezoelectric transducers play the role of actuators both for recording and for reproduction, the driving electronics is greatly simplified, and the need to create calibrated and repeatable mechanical impulses at locations of the surface is avoided.

However, since the voltage impulses ought to be brief to increase signal bandwidth, the energy injected in the plate is low, causing a noisy measurement. To avoid this issue, the input voltage, V i (t), was replaced by a pulse of white noise. By recording the displacement, U j (t), of the surface, the impulse response h i j (t) can be computed from its definition,

h i j (t) = FT -1 H i j (ω) = FT -1 U j (ω) V i (ω) , (3)
where H i j (ω), U j (ω) and V i (ω) denotes the Fourier transform of h i j (t), U j (t) and V i (t) respectively and FT -1 is the inverse Fourier transform operation. This operation is repeated for each transducer and each point of the surface. The time reversal operation then consists on sending to each actuator, i, the time reversed signal h i j (Tt) corresponding to the point, j.

Lastly, it has been shown that the signal phase is the most important parameter to achieve good focusing [START_REF] Montaldo | Generation of very high pressure pulses with 1-bit time reversal in a solid waveguide[END_REF], to the point that amplitude information can be compressed to just the sign of the signal, that is, to just one level of quantification. Thus, single-bit driving electronics suffice and since the result is not sensitive to dc component, the need for a bipolar power supply can also be avoided. As an added bonus, the square driving signal injects more energy into the plate than an amplitude modulated signal, leading to a higher peak amplitude for the same contrast ratio. The voltage applied to actuator i in order to re-focus at point j is thus given by

V i j (t) = 1 2 V pp 1 + sign h i j (T -t) , (4)
where V pp is the peak-to-peak voltage.

To achieve the focusing at a point j, voltages V i j (t) are applied simultaneously to each actuators i. Figure 2 summarize this acquisition and focusing procedure.

Physical Validation

The performance in terms of peak spatial spread and amplitude are reported in this section. Two cases were considered according to whether or not a finger touched the surface.

Unloaded Performance

In a first test, the duration of the time reversal window was set to T = 2 ms and the peak-to-peak voltage to V pp = 24 V. A laser vibrometer (Polytec OFV 534) mounted on a three-axis motorised table was moved across the surface, by steps of 2 mm. Figure 3 illustrates the vibrometer pointing a laser beam at the surface.

The same focusing operation was performed at each position while the actuator driving voltage and the point displacement, integrated from velocity, were recorded at a sampling rate of 100 kHz. The driving voltage was the same for all focusing operations. Its onset served as a reference from which the vibrometer signal could be synchronised. Owing to the good repeatability of the process, a reconstruction of the experimental focusing could be performed. Figure 4 shows the reconstructed displacement of the surface at time T = 2 ms at which the focusing occurs. The focus point is clearly visible with an amplitude of 12 µm and a diameter about 10 mm. The measurements, see fig. 5, show the proportionality of the amplitude, U peak , reached at the focus point to the driving voltage, V pp . In this configuration and for T = 2 ms, the gain was G = U peak /V pp ≃ 0.5 µm/V. At the maximum operating voltage, V max pp = 54 V, which is close to the transducers admissible voltage, the amplitude at the focus point was U max peak = 28 µm. The contrast ratio, however, was not affected by the driving voltage, since peak and background noise amplitude were affected equally. For this setup and for T = 2 ms, the measured contrast ratio was C ≃ 15 for only eight actuators.

unloaded Fn = 0.05 N Fn = 0.20 N Figure 5: Displacement measurements as a function of the driving voltage amplitude V pp . Amplitude shown in the absence of finger contact (circles), pressing at 0.05 N (squares) and at 0.20 N (diamonds). For V pp = 30 V,a displacement of 5 to 10 µm is obtained according to the finger contact force. Achieving a diplacement of 10 µm requires a driving voltage amplitude between 30 and 55V.

Finger Loaded Performance

Touching the active surface muffled some of the vibration and actual displacement of the finger pulp was thus smaller than the unloaded response. Therefore, we proceeded in measuring the fingerloaded response.

The attenuation factor was expected to be dependent on finger impedance and contact area [START_REF] Hudin | Tradeoffs in the application of time-reversed acoustics to tactile stimulation[END_REF]. The plate displacement was measured by pointing the vibrometer beam on the bottom side of the plate, while the finger pressed the plate at the same position on the opposite side. The entire assembly was set on a precision scale, see fig. 6.

Figure 7 shows the displacement measured with the loaded and unloaded plate at the focused point and away from it for a loading force F = 200 mN. From this figure we can see that the displacement is reduced by a factor three when the plate is loaded by a finger and that this reduction factor affects the peak amplitude as well as the background noise in similar proportions. The contrast ratio is therefore not affected by the presence of a finger. This measurement was repeated for various driving voltage amplitudes and for load forces of Fn = 0.05 N and Fn = 0.20 N.

These values were considered to be in the reasonable range of tactile exploration. The results are seen on fig. 5. This figure shows that, loaded or not, the plate displacement is proportional to the driving voltage amplitude. Thus, there is also proportionality between the displacement reached when exerting a constant normal force and the displacement in the absence of finger contact. This proportionality factor is however dependent on the force applied and is approximately U loaded /U unloaded = R = 0.3 for a 0.2 N load and R = 0.5 for 0.05 N load. This means that the presence of a finger induces both an attenuation of the amplitude and a dependence of this amplitude with respect to the load force.

4P ERCEPTUAL VALIDATION

Two testing procedures were carried to demonstrate the ability of the device to produce noticeable and localised tactile feedback, a detection task to determine whether there was a threshold at which stimulation could be felt and a discrimination task to determine at which distance two nearby stimulation regions could be separated.

Intensity Threshold

A wide variety of parameters could influence stimulus detection. Such parameters include its duration, the repetition frequency, the temporal modulation and so on. We investigated the simplest case, namely, the effect of amplitude since amplitude is the natural control parameter of the device. The detectability of a stimulus can be quantified by determining the threshold value above which observers can detect the stimulus more than 50 percent of its occurrences. We used the method of constant stimuli in an attempt to determine the psychometric function between the probability of stimulus detection and the corresponding driving voltage amplitude V pp .

Stimuli, Participants, and Procedure

The stimuli were produced by focusing the waves at position known to the observers at a rate of 150 Hz during five seconds. The time window of time reversal was T = 2 ms. The amplitude was changed in each trial by selecting it randomly among six uniformly distributed values ranging from 6 V to 51 V. Seven volunteers, three female and four male, aged 22 to 30 participated in the study. One hundred of these stimuli were presented to each participant and their responses, stimulus/no-stimulus, were recorded. They received no directions as to how to touch the surface and they were allowed to move their finger in the vicinity of the point. They wore isolating headphones playing white noise during the whole duration of the task .

Results

The probability of detection of a stimulus was calculated for each participant and each driving voltage amplitude. This probability is, at a given stimuli amplitude, the ratio of the number of detected stimuli over the number of presented stimuli. The dots and the vertical bars on fig. 8 show the average and standard deviation of detection probability over all participants. The continuous line shows the fitted psychometric function f (x)= 1 2 1 + erf (xt)s/ √ π where s is the function slope at threshold value t. As expected, the detection probability increased with driving voltage amplitude. It reached 0.85, indicating an high rate of detection of the stimuli. The detection threshold can be estimated to be at V th pp = 3 2 V.

Discussion

The actual displacement was not measured during this experiment. Figure 7, however, allows us to estimate the displacement to be between 5 and 10 µm. This detection threshold might seem quite high when compared to literature values for detection threshold of vibrotactile stimuli [START_REF] Verrillo | Sensation magnitude of vibrotactile stimuli[END_REF]. This is likely to come from the very short duration of the impulse. Indeed, the maximum frequency used to build the interference is f max = 25 kHz which implies that the impulse duration is T i = 1/25000 = 40 µs. Because of this frequency range and the impulsive nature of the stimuli, comparison with detection threshold of sinusoidal vibrotactile stimuli does not seem appropriate.

Such frequencies indeed fall well above vibrotactile sensibility range and should at first sight prevent the impulse from being felt. One hypothesis, that requires further investigations, would be that the high acceleration resulting from the briefness of the impulse, induces some non linear effects, such as skin/plate separation, leading to a finger skin deformation much longer than the actual stimuli duration.

The large standard deviation seen on these results denotes a significant spread in sensitivity among the participants. This effect can be explained by the device's sensitivity to forces exerted by the users during exploration. Figure 5 shows that a driving voltage between 30 and 55 Volts is needed to achieve a 10 µm with a finger-loaded plate and that this figure can vary according to the force applied.

Assuming that this dependence comes from the change in finger impedance with changing load force, the simplified model of interaction between the plate vibrations and the finger proposed in [START_REF] Hudin | Tradeoffs in the application of time-reversed acoustics to tactile stimulation[END_REF] can be invoked. According to this model, the ratio, R, of loaded by unloaded displacements is R = 2Z S /(Z F + 2Z S ), where Z S and Z F are the surface and finger impedance. The rate of change of R with respect to changes in finger impedance is then dR/dZ F = -2Z S /(2Z S + Z F ) 2 . Consequently, increasing the impedance of the surface, Z S , would increase R and also reduce its sensitivity with regard to the finger impedance. With an larger surface impedance, the finger displacement would be kept more constant with respect to possible perturbations. The price to pay would be a higher power consumption.

The fact that the detection probability of 1.0 was not achieved indicates that the amplitude provided by the device could be increased to facilitate the detection either by increasing unloaded plate peak displacement or the transmission ratio R.

Separable Distance

The focal spot produced by a time reversal process has a finite size, given by the diffraction limit which is therefore related to the signal bandwidth, leading to a finite display resolution. Here we aimed at measuring the minimum distance between stimuli so that they could be separated.

Stimuli, Participants, and Procedure

Seven points, depicted in fig. 1, were uniformly distributed along a line with a 3 mm spacing. Point one was systematically focused alternatively, either with itself or with one elected among the six other possibilities. The driving voltage was V pp = 51 V. Again, a constant stimulus method was employed, giving a probability of 0.5 for the perfect detection of two distinct points. Time reversal could focus simultaneously two or more points by summing the signals but the same total energy would have to be divided by the number of points. On the other hand, the decay time constant of the cavity of τ = 3 ms made it possible to repeat the focusing process at a rate up to 300 Hz without increasing the background noise level. The two points could thus be focused alternatively at a rate of 150 Hz each, with a time reversal window of T = 2 ms. The same seven subjects participated. One hundred pairs of points were presented for five seconds. The locations of extreme points were known to the participants and they were free to explore the region in-between before answering whether they felt two distinct stimuli. Likewise, they wore isolating headphone playing white noise during the whole duration of the task.

Results

The probability to distinguish two stimuli was calculated for each participants. Figure 9 shows the average and standard deviation over participants, as a function of distance between focused points. The discrimination threshold was found to d th = 10 mm.

Discussion

As could be expected, the discrimination probability increased with the distance between points. The existence of a discrimination threshold validates the localization capabilities of the device. The notion that the peak amplitude was actually differentiated from the background noise was reinforced by the finding that distance threshold value of 10 mm which coincides with the spread of a focused point observed on fig. 4. The probability to discriminate the location of two points does not reach one even for the most distant points. This is likely due to the detection probability of a single stimuli for V pp = 51 V found in the first study to be bellow unity. Thus the probability of not detecting one of points is not zero, no matter how distant they are from each other.

CONCLUSION

A functional tactile display based on computational time-reversal and using a glass surface and consumer-grade actuators was demonstrated. It operated from simplified data acquisition and processing. This simplified procedure appealed to the reciprocity principle and to the ability of piezoelectric transducers to act as sensors or as actuators, avoiding the need for mechanical calibration of the impulse responses. A second innovation was the use of singlelevel electronics to drive the actuators, achieving enormous cost and complexity reduction. Physical measurement combined with a user study showed the produced stimuli were clearly detectable and confined to a region of about 1 cm 2 area, thus validating the effectiveness of the time reversal approach to display localised tactile informations. Further research will aim at transposing these results to the ultrasound frequency range to avoid sound production. The influence of finger on the focusing quality will be also further investigated.

Figure 1 :

 1 Figure 1: Geometrical parameters of the experimental setup. The double circles represent the 12 mm actuators. The dots indicate the re-focusing positions used in the perceptual validation described in Section 4.

Figure 2 :

 2 Figure 2: Procedure followed to focus waves at a point j. Impulse responses are computed and processed individually for each actuators. During the focusing step, corresponding voltages are applied simultaneously to all actuators.

Figure 3 :

 3 Figure 3: Setup picture. The laser vibrometer is mounted on a threeaxis motorised table to measure the surface displacement of the device at a given position.

12

 12

Figure 4 :

 4 Figure 4: Experimental out of plane displacement at focus time for a driving voltage amplitude V pp = 24 V.

Figure 6 :

 6 Figure 6: Set up for the measurement of finger normal force and plate displacement under the finger. The vibrometer laser beam is deflected by the mirror and reflected on the bottom side of the glass plate.

Figure 7 :

 7 Figure 7: Displacement obtained for V pp = 24 V and T = 2 ms at focused point in the absence(a)/presence(b) of a finger and at a point away from focusing in the absence(c)/presence(d) of a finger pressing at F = 0.2 N.

Figure 8 :

 8 Figure 8: Probability of detection of a focused point for various driving voltage amplitudes

Figure 9 :

 9 Figure 9: Probability of discrimination of two focused point as a function of their relative distance


Massinissa Ait
email: massinissa.aitaba@cea.fr

Lilia Zaourar

Alix Munier

Approximation Algorithm for Scheduling a Chain of Tasks on Heterogeneous Systems

Keywords: Linear chain of tasks, Makespan, Energy Approximation algorithm 1

This paper presents an efficient approximation algorithm to solve the task scheduling problem on heterogeneous platform for the particular case of the linear chain of tasks. The objective is to minimize both the total execution time (makespan) and the total energy consumed by the system. For this purpose, we introduce a constraint on the energy consumption during execution. Our goal is to provides an algorithm with a performance guarantee. Two algorithms have been proposed; the first provides an optimal solution for preemptive scheduling. This solution is then used in the second algorithm to provide an approximate solution for non-preemptive scheduling. Numerical evaluations demonstrate that the proposed algorithm achieves a close-to-optimal performance compared to exact solution obtained by CPLEX for small instances. For large instances, CPLEX is struggling to provide a feasible solution, whereas our approach takes less than a second to produce a solution for an instance of 10000 tasks.

Introduction

Today, our daily life requires massive calculations on different computing systems (desktop, data centers) to perform various needs such as physical simulations or google searches. In order to improve the performance of these systems while keeping their energy consumption reasonable, heterogeneous system has merged. This heterogeneous architecture combines both processing elements (such as CPUs, GPUs), and reconfigurable logic (FPGAs).

However, taking advantage of such heterogeneous systems requires efficient use of resources to make profit from the performance of each part for application execution. Thus efficient scheduling of task's applications is difficult problem often faced by designers and engineers using these complex systems. In fact, with the complexity of applications and architectures, it becomes increasingly difficult to distribute the tasks application effectively. More than a simple load balancing problem, heterogeneity leads to consider efficient scheduling techniques to take account of the different resources specificities. The objective of this work is to determine an efficient scheduling of a parallel application on a heterogeneous resources system in order to minimize both the total execution time (makespan) and the energy consumption. For this purpose, we introduce a constraint on the total energy consumed by the system. We consider in this work, a chain of tasks and communication delay. We conducted this research using the fully heterogeneous micro-server system Christmann RECS c |BOX [START_REF] Griessl | FPGA-accelerated heterogeneous hyperscale server architecture for next-generation compute clusters[END_REF]. The rest of the paper is organized as follows. Section 2 discusses some previous efforts in scheduling parallel application on heterogeneous systems, with a focus on makespan and energy minimization. Section 3 presents a detailed description of the mathematical model proposed. In Sect. [START_REF]IBM: IBM ILOG CPLEX V12.5 user's manual for CPLEX[END_REF], we present an optimal algorithm for a chain of preemptive task. In Sect. 5 we describe the proposed algorithm for non-preemptive scheduling and approximation ratio we obtain. Section 6 shows some preliminary numerical results. The paper ends with a conclusion in Sect. 7.

Related Work

Due to its key importance on performance, the task scheduling problem on heterogeneous platform has been extensively studied and numerous methods have been reported in the literature. They proposed various models and techniques such as dynamical voltage scaling (DVS), list algorithms and genetic heuristics to optimize essentially two main objectives: makespan and energy consumption. Xie et al. [START_REF] Xie | Schedule length minimization of parallel applications with energy consumption constraints using heuristics on heterogeneous distributed systems[END_REF], demonstrate that minimizing schedule length of a DAG-based parallel application with energy consumption constraint on heterogeneous distributed systems is a nondeterministic polynomial-hard optimization problem. They decompose the problem in two sub-problems beginning by treating the problem of the energy constraint. At each task assignment phase, the energy consumption constraint of the application can always be satisfied by supposing that the unassigned tasks are assigned to the processor with the minimum energy consumption. Then, they proceed to the minimization of makespan, assigning tasks to processors using the earliest finish time (EFT).

Authors in [START_REF] Young | Heterogeneous makespan and energy-constrained DAG scheduling[END_REF], considered the objective of maximizing the probability of completing tasks before a deadline D and to satisfy an energy constraint with execution times and stochastic communications delays. Zhang et al. [START_REF] Zhang | Maximizing reliability with energy conservation for parallel task scheduling in a heterogeneous cluster[END_REF]h a v e treated the problem of robustness under energy constraint. The aim is to maximize system reliability by repairing runtime errors caused by various reasons such as hardware flaws and program bugs while maintaining the energy constraint. Authors in [START_REF] Zhong | Energy-aware modeling and scheduling for dynamic voltage scaling with statistical real-time guarantee[END_REF] began by giving an IP (Integer Programming) formulation of the problem, then a three-phase algorithm is proposed using the Dynamic Power Management (DPM) and DVS techniques. Several heuristics (iterative, Greedy, random, . . . ) are proposed in [START_REF] Sheikh | Efficient heuristics for joint optimization of performance, energy, and temperature in allocating tasks to multi-core processors[END_REF] for the problem of scheduling on heterogeneous processors that can change their frequencies among a set of possible values. The objective is to minimize the temperature more than performance and energy of the system. A three-phase list algorithm is proposed by Fard et al. [START_REF] Fard | A multi-objective approach for workflow scheduling in heterogeneous environments[END_REF]. They began by analyzing and classifying the different objectives and their impacts on the optimization process. The objective is to find a solution that minimizes up to four objectives (energy, makespan, reliability, economic cost).

Many works have also been done using genetic algorithms. Authors in [START_REF] Lee | Minimizing energy consumption for precedenceconstrained applications using dynamic voltage scaling[END_REF], proposed the ECS heuristic (Energy Concious Heuristic) which is used in [START_REF] Mezmaz | A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[END_REF]t o form a hybrid approach with the multi-objective genetic algorithm. This approach provides a set of Pareto solutions. More recently in [START_REF] Zhang | Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[END_REF], authors proposed a new genetic algorithm to study both objectives at once. Authors in [START_REF] Tarplee | Efficient and scalable pareto front generation for energy and makespan in heterogeneous computing systems[END_REF][START_REF] Tarplee | Energy and makespan tradeoffs in heterogeneous computing systems using efficient linear programming techniques[END_REF][START_REF] Vasquez Perez | Ordonnancement de tâches pour concilier la minimisation de la consommation d'énergie avec la qualité de service: optimisation et théorie des jeux[END_REF] also use game theory strategies to prove the existence of Nash equilibrium and find a Pareto point.

However, all the aforementioned works did not consider approximation techniques. To the best of our knowledge, we propose the first algorithm with a guarantee of performance. Our model is inspired by [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF], where authors seek to minimize the energy consumed during execution by imposing a Deadline D on completion time. In addition, we consider in this work communication cost between tasks and processing elements. Preliminary results on modeling applications and heterogeneous platforms have been presented in [START_REF] Zaourar | Modeling of applications and hardware to explore task mapping and scheduling strategies on a heterogeneous micro-server system[END_REF], we focus in this work on tasks chain to determine a performance guarantee algorithm.

3M o d e l

This study considers a fully connected heterogeneous multiprocessor platform in which M is a set of m heterogeneous processing elements (GPU, CPU, FPGA. . . ) noted PE. Each element PE k ∈ M is characterized by its execution frequency f j 1, j = 1..m. The processing elements are sorted by increasing order of their frequencies (f 1 f 2 ... f m ). An application A of n tasks is modeled using a DAG graph G(V, E, w). V represents set of nodes in G, and each node v i ∈ V represents a task t i which is characterized by its weight w i , i = 1..n. We note by W the total sum of the weights W = n i=1 w i . E is set of communication edges. Each edge e i,j ∈ E represents a precedence constraint between two tasks t i and t j and refers to the volume of communication from t i to t j denoted by Ct i,j if they are not assigned to the same processing element. Communication cost between each pair of processing elements (PE k , PE l ) is denoted by Cm k,l with Cm k,l Max i execut i,k , ∀i ∈{1, 2,...,n} and ∀k, l ∈{1, 2,...,m} as in [START_REF] Zaourar | Modeling of applications and hardware to explore task mapping and scheduling strategies on a heterogeneous micro-server system[END_REF].

A task t i can be executed only after the execution of all its predecessors. We do not allow duplication of tasks or preemption. A task can be executed by all processing units. Execution of task t i on PE k generates execution time equal to execut i,k = wi f k and power p i,k = w i * f 2 k . We denote by E the allowed quantity of energy consumed during the execution. E represents in our case an energy bound that should not be exceeded during the execution.

We focus this work to a chain of tasks. Our problem can be modeled by mixed integer quadratic constrained program (P ). The first constraint simply expresses that each task must be executed only once and on a single processing element. Constraint (2) keeps energy consumption during execution less than E. The third constraint describes that the task t i+1 must be carried out after the starting time of the task t i (i = 1..n -1) plus the execution time of t i .T h e communication cost (Ct i,i+1 + Cm j1,j2 ) is added if both tasks are executed on two different processing elements (PE j1 and PE j2 )s.tx i,j1 =1andx i+1,j2 =1.

x i,j = 1 if task t i is placed on the processing elementPE j ,i = 1..n, j = 1..m 0 otherwise start i = the starting time of the task t i ,i = 1..n.

(P )

⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ m j=1 x i,j =1, ∀i = 1..n (1)
n i=1 m j=1 x i,j * p i,j ≤ E (2) start i +x i,j1 * execut i,j1 +x i,j1 * x i+1,j2 (Ct i,i+1 + Cm j1,j2 ) start i+1 (3) ∀j 1 = 1..m, ∀j 2 = 1..m ∀i = 1..n -1 j 1 = j 2 Z(min)=start n + m j=1 x n,j * execut n,j 4
Optimal Scheduling Algorithm for a Chain of Preemptive Tasks

In this section we propose an algorithm to find the optimal solution of the preemptive scheduling without communication cost for a chain of n tasks on a set of m processing elements.

Lemma 1. The set of schedules that saturate energy constraint is dominant.

Proof. Let C max be the makespan of a solution such that C max = P1 f1 + P2 f2 +...+ Pm fm , P i 0 is the quantity of work put on the processing element PE i , i = 1..m. m i=1 P i = W . We assume that m j=1 P j * f 2 j <E. We construct another solution such that: l = max{j ∈{ 1..m}, We start by finding the fastest processing element PE j , on which we can perform all the tasks. Then we look for the weight of tasks that can be put on the next processing element (PE j+1 ) in order to saturate the energy constraint. We denote by W j the quantity of work put on the processing element PE j , W j+1 on PE j+1 . The best solution is obtained when the energy constraint is saturated s

j i=1 P i f 2 m + m i=j+1 P i f 2 i <E} and P ′ 1 =0 , P ′ 2 =0 ,..., P ′ l =0 ,P ′ l+1 = E-l+1 j=1 Pj f 2 m -m j=l+2 Pj f 2 j f 2 l+1 -f 2 m , P ′ l+2 = P l+2 , ..., P ′ m = P m + l j=1 P j +(P l+1 -P ′ l+1 ). We obtain a new solution C ′ max = m j=1 P ′ j fj with m j=1 P ′ j f 2 j = E. C ′ max = m j=1 P ′ j fj = P ′ l+1 f l+1 + m j=l+2 Pj fj + l j=1 Pj +(P l+1 -P ′ l+1 ) fm . Since f m >f j , j = 1..l + 1, induces P ′ l+1 f l+1 + (P l+1 -P ′ l+1 ) fm P l+1
.t W j f 2 j + W j+1 f 2 j+1 = E with W j + W j+1 = W .
The solution of the system of two equations with two unknowns is

W j = E-W * f 2 j+1 f 2 j -f 2 j+1
and W j+1 = W -W j . This keeps the realizability of the solution:

E -W * f 2 j+1 0 because W * f 2 j+1 E and f 2 j -f 2 j+1 < 0 because f j <f j+1 . Then W W j > 0 induces W j+1 0.
Algorithm 1. Preemptive scheduling (PS).

Data: Set of processing elements M = {PE j ,j =1..m} with f 1 f 2 ... fm, weights of the tasks w 1 ,w 2 ,...,wn, E. C max . The second case corresponds to all frequencies are greater than f j+1 such that

Result: Optimal preemptive scheduling. begin W = n i=1 w i ; j = max{l ∈{1..m},W * f 2 l E} if W * f 2 j <E then W j = E-W * f 2 j+1 f 2 j -f 2 j+1 W j+1 = W -W j else W j = W , W j+1 =0 k = max{p ∈{1..n}, p i=1 w i <W j }; w ′ k+1 = W j -k i=1 w i Put t 1 ...
f j+1 f 1 f 2 ... f k . Hence, k i=1 P i * f 2 i k i=1 P i * f 2 j+1 = W * f 2 j+1 > E.
The last case corresponds to f 1 ... f j <f j+1 ... f k . To study this case, we start with the following Lemma 2.

Lemma 2. Let A, B, C be three positive integers such as 1 ≤ A<B<C and W 1 , W 2 be two non negative integers such as

W 1 + W 2 = W .I fW 1 * A 2 + W 2 * C 2 = W * B 2 then W1 A + W2 C > W B . Proof. By replacing W 2 by (W -W 1 )i nW 1 * A 2 + W 2 * C 2 = W * B 2 ,w e obtain W 1 = W ( C 2 -B 2 C 2 -A 2 ). Then, by replacing W 1 by (W -W 2 ) we obtain W 2 = W ( B 2 -A 2 C 2 -A 2 ). Follows, W1 A + W2 C = W (C 2 -B 2 ) A(C 2 -A 2 ) + W (B 2 -A 2 ) C(C 2 -A 2 ) . Let ∆ = W1 A + W2 C -W B , we prove in the following that ∆>0. ∆ = W (C 2 -B 2 ) A(C 2 -A 2 ) + W (B 2 -A 2 ) C(C 2 -A 2 ) -W B = W C 2 -A 2 ( C 2 -B 2 A + B 2 -A 2 C -(C 2 -A 2 )

B

). We set X = B A and Y = C A . Observe that X>1a n dY>X . Follows:

∆ = W Y 2 A 2 -A 2 ( Y 2 A 2 -X 2 A 2 A + X 2 A 2 -A 2 YA -(Y 2 A 2 -A 2 ) XA ). ∆ = W Y 2 A-A ( XY 3 -X 3 Y +X 3 -X-Y 3 +Y XY )= W Y 2 A-A ( -(X-1)(Y -1)(X-Y )(X+Y +1) XY ). Since X>Y >1w eh a v e( Y -1) > 0, (X -1) > 0 and (X -Y ) < 0. Therefore -(X-1)(Y -1)(X-Y )(X+Y +1) XY > 0. Furthermore, W Y 2 A-A > 0 because Y>1. Finally, ∆>0 induces W1 A + W2 C > W B . ⊓ ⊔ Proposition 1. If k i=1 P i * f 2 i = W j * f 2 j + W j+1 * f 2 j+1 and k i=1 P i = W j + W j+1 , then k i=1 Pi fi > Wj fj + Wj+1 fj+1 .
Proof. Let ϕ be a sequence of real such as

ϕ 1 = f 1 and ϕ i = i-1 α=1 Pα * ϕ 2 i-1 +Pi * f 2 i i α=1 Pα
, for i = 2..j. This sequence guarantees that ϕ i-1 <ϕ i <f i , ∀ i = 2..j. Indeed, since

ϕ 1 = f 1 , ϕ 2 2 = P1 * ϕ 2 1 +P2 * f 2 2 P1+P2 > P1 * f 2 1 +P2 * f 2 1 P1+P2 = f 2 1 . Furthermore, P1 * f 2 1 +P2 * f 2 2 P1+P2 < P1 * f 2 2 +P2 * f 2 2 P1+P2
<f 2 2 induces ϕ 1 <ϕ 2 <f 2 . We assume that this is true for i = j -1 i.e. ϕ j-2 <ϕ j-1 <f j-1 .

ϕ 2 j = j-1 α=1 Pα * ϕ 2 j-1 +Pj * f 2 j j α=1 Pα < j-1 α=1 Pα * f 2 j-1 +Pj * f 2 j j α=1 Pα < j-1 α=1 Pα * f 2 j +Pj * f 2 j j α=1 Pα = f 2 j . ϕ 2 j = j-1 α=1 Pα * ϕ 2 j-1 +Pj * f 2 j j α=1 Pα > j-1 α=1 Pα * ϕ 2 j-1 +Pj * ϕ 2 j j α=1 Pα
induces ϕ 2 j >ϕ 2 j-1 . Finally, ϕ j-1 <ϕ j <f j . By recurrence, we deduce that ϕ i-1 <ϕ i <f i . From Lemma 2 we have:

P1 f1 + P2 f2 > P1+P2 ϕ2 , P1+P2 ϕ2
+ P3 f3 > 3 i=1 Pi ϕ3
and then, ∀ l ∈{ 1..j} l-1 i=1 Pi ϕ l-1

+ P l f l > l i=1 Pi ϕ l . Follows, j i=1 Pi fi > j i=1 Pi ϕj .
Let another sequence of real φ such as

φ k = f k and φ i = k α=i+1 Pα * φ 2 i+1 +Pi * f 2 i k α=i Pα
for i ∈{j +1..k -1}. In the same way, we get f i <φ i <φ i+1 , ∀ i ∈{j +1..k -1}.

And from Lemma 2, we obtain

k i=j+1 Pi fi > + k i=j+1 Pi φj+1 . It result that k i=1 Pi fi > j i=1 Pi ϕj + k i=j+1 Pi φj+1 .
In order to apply once again Lemma 2, we have to decompose j i=1 P i and

k i=j+1 P i into 4 values W L1 ,W L2 ,W R1 ,W R2 such that: ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ W L1 + W L2 = j i=1 P i W R1 + W R2 = k i=j+1 P i W L1 + W R1 = W j W L2 + W R2 = W j+1 W L1 * ϕ 2 j + W R1 * φ 2 j+1 = W j * f 2 j W L2 * ϕ 2 j + W R2 * φ 2 j+1 = W j+1 * f 2 j+1 =⇒ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ W L1 = W j * (φ 2 j+1 -f 2 j ) (φ 2 j+1 -ϕ 2 j ) W L2 = W j+1 * (φ 2 j+1 -f 2 j+1 ) (φ 2 j+1 -ϕ 2 j ) W R1 = W j * (f 2 j -ϕ 2 j ) (φ 2 j+1 -ϕ 2 j ) W R2 = W j+1 * (f 2 j+1 -ϕ 2 j ) (φ 2 j+1 -ϕ 2 j )
This part of proof is illustrated by Fig.

= WL1 ϕj + WR1 φj+1 + WL2 ϕj + WR2 φj+1 > W1 fj + W2 fj+1 . Follows, k i=1 Pi fi > Wj fj + Wj+1 fj+1 . ⊓ ⊔ Now, from Proposition 1, C ′ max = k i=1 Pi fi > C max = Wj fj + Wj+1 fj+1 .
Remark 1. The proof remains valid if

k i=1 P i * f 2 i W j * f 2 j + W j+1 * f 2 j+1
. Indeed, from Lemma 1, we can construct another solution with P

An Approximation Scheduling Algorithm for Chain of Non-preemptive Tasks with Communication Costs

We assume here a communication cost Cm j,j+1 between PE j and PE j+1 and communication cost Ct i,i+1 between each pair of tasks t i and t i+1 with 2 * min i Ct i,i+1 max j Ct j,j+1 , ∀ i, j ∈{ 1..n -1}. We do not allow preemption of tasks and we transform the previous solution of preemptive scheduling, using the processing elements PE j and PE j+1 only. Proposition 2. If only two processing elements PE j and PE j+1 are available, the schedules with only one communication between them are dominant.

Proof. Let {t k+2 ...t n } be the set of uncut tasks of the preemptive solution on PE j+1 and S 1 the sum of their weights. Let C max1 the makespan of a feasible solution obtained by processing tasks {t 1 ...t k+1 } on PE j and {t k+2 ...t n } on PE j+1 . By contradiction, let suppose that there exists a feasible solution with at least two displacements such as S 1 S 2 , where S 2 is the sum of the tasks weights on PE j+1 with this solution, let C max2 be its makespan. We prove that C max2 C max1 . Since the second solution is feasible, S2 W j+1 .B yt h e previous algorithm, W j+1 S 1 +w k+1 S 1 +max w i with i ∈{1 ...n}, and thus

S 2 S 1 +Max w i ,i = 1..n. C max1 = W -S1 fj + S1 fj+1 + Cm j,j+1 + Ct k+1,k+2 and C max2 W -S2 fj + S2 fj+1 +2 * Cm j,j+1 +2 * min Ct i,i+1 , i ∈{1 ...n-1}. Follows, C max2 -C max1 = S2-S1 fj+1 -S2-S1 fj + Cm j,j+1 +2 * min Ct i,i+1 -Ct k+1,k+2 . Since S2-S1 fj+1 0 and 2 * min Ct i,i+1 -Ct k+1,k+2 0, ∀ i = 1..n -1, induce C max2 - C max1 Cm j,j+1 -S2-S1 fj . Finally, Cm j,j+1 -S2-S1 fj Cm j,j+1 -Max wi fj , i = 1..n. According to the hypothesis, Cm j,j+1 -Max wi fj 0, ∀ i = 1..n. Therefore C max2 -C max1 0= ⇒ C max2 C max1 . ⊓ ⊔ Theorem 2.
The following Algorithm 2 provides a solution for non-preemptive scheduling starting from the preemptive scheduling solution obtained by Algorithm 1 with a complexity of θ(n + m).

The two variables α and β are used to determine the assignment of tasks. In the case W j+1 = 0, we put all the tasks on PE j . Otherwise, let Cost 1 (v)b e the cost of executing the first tasks (t

1 to t v )o nPE j with v i=1 w i W j , then the rest on PE j+1 . Cost 1 (v)={Ct v,v+1 + v i=1 wi fj + n i=v+1 wi fj+1
+ Cm j,j+1 }.L e t Cost 2 (v) be the cost of executing the first tasks (t 1 to t v )o nPE j+1 , then the rest on PE j with

n i=v+1 w i W j . Cost 2 (v)={Ct v,v+1 + v i=1 wi fj+1 + n i=v+1 wi fj + Cm j,j+1 }.
We start by finding the tasks v 1 and v 2 that give the best respective scheduling makespan (Cost 1 ) and (Cost 2 ), and keeping the best one. Finally, we check if the cost generated by using both processing elements PE j and PE j+1 is less than the scheduling makespan obtained by performing all tasks on PE j .

Example 1. Consider the task graph given by Figure 2. It contains ten task nodes (n = 10) labeled from t 1 to t 10 with two additional nodes S and E (beginning and end of the application). The edges are labeled with the communication cost between tasks. The nodes are labeled with the weight of each task. Consider a heterogeneous platform with 3 processing elements, their frequencies are given in Table 1. The communication cost between processing elements are given in Table 2. The maximum energy consumption is E = 1350.

The application of preemptive scheduling Algorithm 2 gives PE j = PE 2 and PE j+1 = PE 3 with W 2 =0 , 5625 and W 3 =3 7 , 4375. Since W 3 > 0, we obtain .

Cost 1 = Ct 1,2 + w1 f2 + 10 i=2 wi f3 + Cm 2,3 = 17, v 1 =1.Cost 2 =
= Cost1 Cost2 = min{Cost2(v),v ∈{1..n -1}, n i=v 2 +1 wi Wj};l e t v 2 ∈{1..n -1} such that Costv 2 = Cost2 if Cost1 <Cost2 then Cost = Cost1, β = v1, α =1 else Cost = Cost2, β = n, α = v2 +1 if Cost > W f j then Cost = W f j , β = n,
Proof. The optimal solution C ′ max of the preemptive scheduling is given by C ′ max = Wj fj + Wj+1 fj+1 . In the worst case for our algorithm, all tasks are executed on the processing element f j ,t h u sw eg e t C max W fj . Follows

Cmax C ′ max W f j W j f j + W j+1 f j+1 W Wj + f j W j+1 f j+1
. By optimality of Algorithm 1,

C ′ max C ⋆ max induces Cmax C ⋆ max Cmax C ′ max , then Cmax C ⋆ max W Wj + f j W j+1 f j+1 . ⊓ ⊔ Remark 2.
This ratio is reached, let consider an instance which generates W j+1 =0a n dW j = W for the preemptive solution, then, 1

Cmax C ⋆ max W Wj + f j W j+1 f j+1 = W W =1
. So, we obtain the optimal solution, C max = C ⋆ max .

Remark 3. Since

fj fj+1 < 1, W Wj + f j W j+1 f j+1 < W f j f j+1 (Wj +Wj+1)

Experimental Results

In order to measure the efficiency of our algorithm, we performed several tests on randomly generated instances with different dimensions. For this purpose, we developed a random instances generator in C++ adjustable with several parameters.

General settings are number of tasks n and processing elements m.W e denote by test n m instance defined by these two parameters. The weights of the tasks are generated randomly over an interval [w min ,w max ]. The frequencies of the processing elements are randomly generated over an interval [f min ,f max ] while ensuring the heterogeneity of the system by generating different values. The communication costs between tasks are generated randomly over an interval [Ct min ,Ct max ] and between processing elements over an interval [Cm min ,Cm max ] in accordance with the hypothesis described in Sect. 3.The bound E is randomly generated with respect to W * f 2 1 <E<W * f 2 m . Our proposed Algorithm 2 were implemented in C++. The exact solution is obtained by solving the model (P ) with CPLEX 12.5.0 [START_REF]IBM: IBM ILOG CPLEX V12.5 user's manual for CPLEX[END_REF] and the OPL script language. The following Table 3 shows the results of tests on different instance sizes. We have generated 30 instances for the first four rows (from instance test 8 3t otest 20 4) and then one instance for the others due to the large running time on CPLEX.

The PS (Preemptive Scheduling) columns present the makespan average solution obtained by the Algorithm 1.T h eNPS (Non-Preemptive Scheduling) columns present the makespan average solution obtained by the Algorithm 2 and its average execution time. The CPLEX columns present the average makespan solution of the resolution of the model (P ) with CPLEX and the average computation cost required as well as the optimality of the solutions. Finally, the columns GAP 1 and GAP 2 present the average ratio between the solution obtained by Bound 1 = CPLEX solution and Bound 2 = Preemtive solution with NPS solutions which is calculated as follow:

GAP i = Heuristic Solution-Boundi Boundi * 100,i ∈{1, 2}.
Since the execution time of a quadratic model is generally too large, we have therefore limited the running time for CPLEX to 60 min. In Table 3,w ec a n notice that for most of the instances with less than 30 tasks, our algorithm gives an optimal solution with smaller running time than CPLEX. Moreover, for larger instances, CPLEX takes much longer to find a solution, whereas NPS gives a solution in less than one second for an instance with 10000 tasks. This paper presents an efficient approximation algorithm to solve the task scheduling problem on heterogeneous platform for the particular case of linear chain of tasks. Our objective is to minimize both the total execution time (makespan) and the energy consumption by imposing a constraint on the total energy consumed by the system. This work has shown that finding an efficient scheduling is not easy. Tests on large instances close to reality shows the limits of solving the problem with a solver such as CPLEX.

The main contribution of this work is to give an algorithm which provides a solution with small running time, and also guarantee the quality of the solution obtained compared to the optimal solution. The ratio obtained depends on the frequencies of two successive processing elements PE j and PE j+1 used in preemptive scheduling. The performance ratio of our algorithm is bounded by fj+1 fj . As part of the future, we will focus on the extension to more general classes of graphs to handle real application.

Theorem 1 .

 1 The following Algorithm 1 gives the optimal solution for preemptive scheduling without communication cost with a complexity of θ(m).

  t k and a part w ′ k+1 of t k+1 on PE j Put t k+2 ...tn and the rest (w k+1w ′ k+1 )o ft k+1 on PE j+1 We show in the following that Algorithm 1 gives an optimal solution. Let C max be the makespan of the solution obtained by the Algorithm 1: C max = Wj fj + Wj+1 fj+1 due to the precedence constraint. Let C ′ max = P1 f1 + P2 f2 + ...+ P k f kbe another solution on a set of k>2 processing elements, k i=1 P i = W .W e distinguish three possible cases. The first case corresponds to all frequencies are lower than f j s.t f 1 . Finally, since f j <f j+1 induces

  2 i = W j * f 2 j + W j+1 * f 2 j+1

Fig. 1 .

 1 Fig. 1. Resume of the first part of the proof.

  Ct 7,8 + Cost 1 = 17, β =1a n dα = 1. Finally, W f2 = 38 2 =1 9>C o s t . We put the task t 1 on the Algorithm 2. Non-Preemptive Scheduling (NPS). Weights of the tasks w1,w2,...,wn. Communication costs between tasks Cti,i+1, i ∈{1..n -1}. Result: Approximate solution Cmax for non preemptive scheduling.

	begin
	Find PEj, PEj+1 and Wj, Wj+1 with preemptive scheduling algorithm
	if Wj = W then
	β = n, α =1
	else Cost1 = min{Cost1(v),v ∈{1..n -1}, v i=1 wi Wj};l e t
	v1 ∈{1..n -1} such that Costv 1
	7 i=1 wi f2	+
	10 i=8 wi
	f3

+ Cm 2,3 = 19, v 2 =7 .Cost 1 <C o s t 2 , induces Cost = Data:

Table 1 .

 1 α =1 Put tasks between tα and t β on the processing element PEj Order the rest on the processing element PEj+1, Cmax= Cost Frequencies of processing elements.

		5533335335
	S	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	E
		0	2	2	2	2	3	3	2	4	4	0
					Fig. 2. Task chain graph.
	PEj PE1 PE2 PE3
	fj	1	2	6

Table 2 .

 2 Communication cost between processing elements. processing element PE 2 and tasks t 2 to t 10 on PE 3 . C max = Cost = 17. For this instance, our approach gives the optimal solution.

	PEj PE1 PE2 PE3
	PE1 0	7	6
	PE2 7	0	7
	PE3 6	7	0

Table 3 .

 3 Evaluation of the NPS heuristic compared to CPLEX.

	Instances	PS	NPS		CPLEX		Gap1	Gap2
			Sol	Time Sol	Time	Opt
	test 8 3	15.03 19.89 0.0004 s 19.89 0.76 s	X 0%	31.14%
	test 12 3	24.82 32.55 0.0005 s 32.55 2.17 s	X 0%	15.80%
	test 15 4	29.87 34.59 0.0005 s 34.58 6.46 s	X 0.02%	21.91%
	test 20 4	27.51 33.54 0.0007 s 33.54 8min 3s X 0%	2.25%
	test 30 6	24.84 25.40 0.001 s 25.40 35 min X 0%	7.02%
	test 50 6	40.27 43.10 0.01 s 102.24 60 min /	-57.84% 8.03%
	test 100 9	53.78 55.39 0.02 s 843.48 60 min /	-93.43% 2.99%
	test 200 9	123.21 128.92 0.03 s 1929.20 60 min /	-93.31% 4.63%
	test 500 11	207.44 217.52 0.05 s 3587.39 60 min /	-93.93% 4.85%
	test 10000 11 4814.62 4828.06 0.5 s	/	60 min /	/	0.27%
	7 Conclusion and Future Work


Franck Gonzalez

Wael Bachta

Florian Gosselin

Smooth Transition-Based Control of Encounter-Type Haptic Devices

Encounter-type devices have been introduced to solve one of the main drawbacks of common haptic interfaces i.e. their limited transparency in free space and their restricted ability to render realistic transitions between free space and contact. Advantageously, encounter-type interfaces collide with fingers and display interaction forces only if a contact occurs in the virtual environment. In free space, their end-effectors are mechanically detached from the operator and closely track his fingers, allowing for a perfect transparency. This paper introduces a control scheme that handles the transition between tracking and force display modes in a smooth way. Experimental results using a custom encounter-type interface are also given. The obtained results show the efficiency of the proposed control law when compared to the conventional switch-based control usually found in the literature.

I. INTRODUCTION

Haptic interfaces are purposed for natural interactions between an operator and a virtual or a remote environment [START_REF] Fuchs | Virtual Reality: Concepts and Technologies[END_REF], [START_REF] Koyama | Multi-fingered exoskeleton haptic device using passive force feedback for dexterous teleoperation[END_REF], [START_REF] Bouzit | The Rutgers Master 2 -new design force-feedback glove[END_REF], [START_REF] Monroy | Masterfinger: Multi-finger haptic interface for collaborative environments[END_REF], [START_REF] Endo | Haptic display by a side-faced-type multi-fingered haptic interface[END_REF]. They should enable the user to sense correctly even high impedances of distant or virtual objects, and also display negligible impedance when there is no contact with the environment [START_REF] Massie | The PHANTOM haptic interface: A device for probing virtual objects[END_REF]. The latter requirement calls for an interface with low inertia links and motors, along with small gear ratios. These specifications may be in conflict with rigidity and force level requirements. Force control strategies can also be implemented to reduce the apparent impedance in free space motion [START_REF] Weir | Stability of haptic displays[END_REF]. Their performances are however limited.

In this context, Encounter-Type Haptic Displays (ETHDs) are of interest as their working principle relies on a mechanical detachment between the user and the interface in free space motion [START_REF] Mcneely | Robotic graphics: a new approach to force feedback for virtual reality[END_REF], [START_REF] Tachi | A construction method of virtual haptic space[END_REF], [START_REF] Yokokohji | What you can see is what you can feel -development of a visual/haptic interface to virtual environment[END_REF], making them perfectly transparent. As shown in Fig. 1, the interface closely tracks an operator's finger thanks to a thimble-like end-effector featuring embedded optical distance sensors and encounters it only when a contact occurs in the virtual or remote environment [START_REF] Yoshikawa | A touch and force display system for haptic interface[END_REF].

{franck.gonzalez, florian.gosselin}@cea.fr wael.bachta@isir.upmc.fr This research was partly supported by the "Agence Nationale de la Recherche" (Mandarin project -ANR-12-CORD-0011, labeled by "Cap Digital Paris Région", the French cluster for digital contents and services), and partly accomplished within the laboratory of excellence SMART supported by French state funds managed by the ANR within the Investissements d'Avenir program (ANR-11-IDEX-0004-02).

Real World

Virtual World Various technological solutions can be used for the design of this thimble. To measure the motion of the operator's fingertips, each of the end-effectors of the Encounter-Type hand exoskeletons for teleoperation in [START_REF] Nakagawara | An encounter-type multi-fingered master hand using circuitous joints[END_REF], [START_REF] Honggen | An exoskeleton master hand for controlling DLR/HIT hand[END_REF] is equipped with an optical sensor that records the position of a thin reflecting plate pushed against the nail by means of a spring. The thin plate and the spring are chosen so that the force exerted on the finger during free space motion be negligible. In [START_REF] Yoshikawa | A touch and force display system for haptic interface[END_REF], [START_REF] Yoshikawa | A three-dimensional touch/force display system for haptic interface[END_REF], optical-fiber sensors matrices are used to estimate the finger position in a 2D ring and a 3D cap mounted on simple serial ETHDs.

In the literature, a position control scheme is usually adopted to track the movements of the user when no contact is required and a force display control is used to render the environment after contact. A simple switch handles the transition between the two control modes. In this paper, the limits of this conventional approach are discussed before proposing a smooth transition-based control law. The importance of the transition is highlighted since it has a key role in the naturalness of the haptic rendering.

The remainder of the paper is organized as follows: Section II presents the switch-based control law as implemented in the literature, then discusses its drawbacks and describes a smooth transition-based control scheme intended to overcome its shortcomings. Then Section III gives an experimental assessment of the two control laws. A 2-DoF ETHD used as an experimental set-up is presented, followed by the results of the experiments. Finally, Section IV concludes and discusses future work.

II. CONTROL LAWS

In this section, the conventional switch-based control law is first presented and its drawbacks are pointed out. Then a smooth transition-based control law is presented, which cuts off with the raised shortcomings.

A. Switch-Based Control Law

The conventional ETHD control law is composed of a position tracking mode in free space and a force display for the rendering of the environment. This subsection describes these two control modes as well as the switch modality.

1) Finger Tracking in Free Space: Let X r/0 and X f /0 denote the centers coordinates of respectively the robot endeffector and the finger. Both are expressed in a frame attached to the robot base (see Fig. 2). In this control mode, the goal is to maintain the finger in the center of the ring. The tracking error ǫ X (see Fig. 3) is therefore directly obtained by measuring X r/f , which is the position of the ring center with respect to the finger.

Expressing the error in the joints space allows for an easier tuning of the controller since the interface dynamics are less coupled in this representation [START_REF] Plumet | Shall we use a dynamic model to control the motions of industrial manipulators?[END_REF]. In case of a close tracking, ǫ X is small so it can be expressed in the articular space as follows:

ǫ θ = J -1 (q) • ǫ X (1)
with J(q) the Jacobian matrix of the robot in the reference frame.

This error is sent to a Proportional-Derivate controller which provides the robot with the reference torque τ t :

τ t = (K t + B t s)ǫ θ (2)
Finally, its joints positions are used to compute the position of the ring's center X r/0 through a geometric model.

2) Transition Between Modes: As shown in Fig. 3, the switching between tracking mode (1)-( 2) and contact mode ( 6)- [START_REF] Weir | Stability of haptic displays[END_REF] (see below) is triggered by F e through the matrix S, defined as follows:

S = e -α||F e || 0 0 e -α||F e|| (3)
with α a dimensionless number so that ∀F e , α ≫ ||F e ||. This way, when the finger's avatar encounters a virtual object, ||F e || = 0. The switch is triggered: the robot is no more influenced by the tracking (e -α||F e|| ≃ 0) but only by contact forces. When the finger's avatar leaves the virtual object, ||F e || = 0, the force display is set off and the tracking torque reference is sent to the servo-drive with a unit gain.

Several works have been dedicated to the computation of distances in a virtual environment [START_REF] Larsen | Fast proximity queries with swept sphere volumes[END_REF], [START_REF] Ericson | Real-Time Collision Detection[END_REF]. Let d f /e be the distance of the finger's avatar periphery to the closest point of a virtual object, along the normal n to the virtual object at this point (computed from the position of the finger's center X f /0 and R f ). We define a compensatory tracking term ∆X = f (d f /e ) by (see Fig. 4):

if d f /e > R r -R f ∆X = 0 if d f /e ∈ [0; R r -R f ] ∆X = (R r -R f -d f /e )n (4
) with R r the radius of the ring. The Cartesian error ǫ X is modified as follows:

ǫ X = -X r/f -∆X (5)
This way, when d f /e > R r -R f , the finger is kept centered with the ring. Then, for 0 < d f /e ≤ R r -R f , the ring's inner surface approaches the finger linearly. Finally, when the finger's avatar comes into contact with the virtual environment, the ring touches the finger.

- + 0 S J -1 (q) ǫ X K t + B t s ǫ θ + + + τ e τ h τ t Robot - + X f /0 X r/f X r/0 τ Human Operator f (•) K e + B e s J T (q) + + ∆X F e F e
Fig. 3. Control law with switch, in the framework of [START_REF] Yoshikawa | A touch and force display system for haptic interface[END_REF]. S: Switch, see [START_REF] Bouzit | The Rutgers Master 2 -new design force-feedback glove[END_REF]. Dashed area: Virtual Environment. f (•): tracking compensation, see [START_REF] Monroy | Masterfinger: Multi-finger haptic interface for collaborative environments[END_REF]. 3) Force Feedback in Contact: When the user's avatar encounters a virtual object, the interface must render the associated interaction force F e . Assuming a viscoelastic compliant virtual environment without tangential friction, this force is defined as a unilateral spring-damping set, as follows:

d f /e > Rr -R f ∆X = 0 d f /e V.W. d f /e d f /e = Rr -R f ∆X = 0 d f /e d f /e < Rr -R f ∆X = 0 d f /e d f /e = 0 ∆X = (Rr -R f )n
if d f /e ≥ 0 F e = 0 if d f /e < 0 F e = (K e + B e s)d f /e n (6)
The torque τ applied on the interface joints is given by:

τ = τ h + τ e (7)
where τ h is the torque due to the force F h applied by the finger on the end-effector, and τ e is a torque corresponding to the interaction force F e . This torque is given by:

τ e = J T (q)F e (8)

B. Smooth Transition-Based Control Law

In this subsection, the drawbacks of the switch-based control law are first discussed. Then, a smooth-transition based control law is proposed.

1) Limitations of Previous Approach:

To achieve a quality rendering, the switching must occur exactly when the virtual or remote object is encountered. At this very moment, the interface's end-effector must be in contact with the finger of the operator. In the switch-based control law, the switch time and location are based on the knowledge of the finger radius. This assumes that the finger contour is cylindrical: this assumption may not be robust. Indeed, a finger geometry is more complex and deformable, so it is likely to change during the contact. In order to highlight this issue, two scenarios illustrating the effects of a wrong estimation of the finger radius are discussed in the sequel (Fig. 5):

• Over-estimation of the finger radius R f . As the finger's avatar is larger than the real finger, a contact would occur in the virtual world before the operator's finger touches the ring. A force F e would thus be displayed by the interface although the finger is not in contact with the ring. In other words, the interface would move back and hit the operator's finger. Thus the user would feel parasitic movements of the robot bumping into his finger, modifying the behavior of the environment. Center of ring's avatar X r/0 Fig. 5. Main factors influencing the tracking and force feedback in the real world, and their counterparts in the virtual environment. Note that the ring's avatar is of the same size as the real ring inner periphery, which is perfectly known, whereas the size of the finger's avatar, which is estimated, can differ from the real one.

• Under-estimation of the finger radius R f . This would translate into the finger hitting the end-effector before its avatar come into contact with the virtual wall. In this case, the user would feel as if the virtual object were made of two layers. The first sensation would correspond to a parasitic force

F p = (K t + B t s)(R r - R f -d f /e
)n due to the tracking mode, which would not be disabled as the finger's avatar would not be in contact with the virtual wall yet. When the finger's avatar would finally encounter the virtual wall, the second (purposed) rendering would be sensed.

These behaviors decrease the transparency of the interface and limit the interaction quality. Their effects may be minimized by enhancing the end-effector's tracking performances in order to better detect the finger geometry. However, this would involve expensive solutions that cannot be considered in a majority of applications. In the sequel, a smooth transition control law, independent on the finger geometry, is proposed to overcome these limitations without any change on the hardware.

2) Proposed Solution:

To achieve a smooth transition, the tracking control law component should be set off at the very instant when the finger avatar collides with the virtual environment. In the switch-based control law, this is achieved by servoing the robot end-effector center to a distance R r -R f to the virtual environment at the instant of the collision. At the same time, the tracking control component is disabled using S. Since it is based on the finger radius, the efficiency of this method is limited. Another way of implementing the transition consists in adapting the tracking control component in function of the distance d f /e between the avatar of the finger and the virtual object. When this distance is large, the full tracking control magnitude is used. Conversely, when this distance is small, only a very little amount of this component is used. The interface can no longer be centered around the finger and the latter can collide with the ring. This method is practically implemented

- + 0 β J -1 (q) ǫ X K t + B t s ǫ θ + + + τ t Robot τ - + X r/0 Human Operator f (•) K e + B e s J ⊺ (q) F e X f /0 τ h τ e d f /e X r/f
β Fig. 6. Smooth control law without switch. using an adaptive gain β which depends on d f /e (see Fig. 6):

     if d f /e > R r β = 1 if d f /e ∈ [R r -R f,max ; R r ] β = 1 -0.99 Rr-d f /e R f,max if d f /e < R r -R f,max β = 0.01 (9) with R f,max chosen so that ∀ R f , R f,max > R f . Also, d f /e
is computed with R f,max , so the tracking component is reduced progressively. Using this adaptation, the tracking force would be unchanged as long as

d f /e > R r . When R r -R f,max ≤ d f /e ≤ R r
, the ring's avatar would come into contact with the virtual wall. Finally, when 0 ≤ d f /e ≤ R r -R f,max and the operator encounters the ring, β = 0.01 and the tracking effect would be almost canceled, whereas ||F e || = 0.

We also propose that the force display depend on the ring's avatar rather than on the finger's to avoid relying on the less known finger radius, as follows:

F e = (K e + B e s)d r/e n (10)
with d r/e the distance between the ring's avatar and the closest point of the virtual object along n. This way, the ring should remain at the surface of the virtual object and wait for the finger to encounter it. The control is expected to be more stable as the ring's geometry is better known and do not undergo any deformation or non-measurable motion.

III. EXPERIMENTAL RESULTS

This Section describes an experimental setup on which the control schemes are implemented in turn, in order to further investigate the assets and restrictions of the proposed approaches.

A. Experimental Setup

In order to compare the different control laws, an encounter-type interface is developed. It consists in a 2D haptic interface equipped with a custom end-effector. The hardware as well as the software of this interface are described in this section.

1) Robot: An optimized version of a 2D sub-structure saved from a 6DOF parallel robot available in our laboratory is used [START_REF] Gosselin | Design of a high fidelity haptic device for telesurgery[END_REF]. This robot, originally intended for telesurgery, is highly transparent and its performances are in adequacy with the simulation of fine manipulation tasks in which realistic contact rendering is of primary importance, hence intermittent contact potentially interesting. As shown on Fig. 7, the robot is placed so that its workspace lies in a vertical plane. It is powered with two Maxon RE-35 DC motors equipped with 1,000 pts incremental optical encoders.

2) End-effector: The robot is equipped with a ring-shaped end-effector adapted to 2D intermittent contact (Fig. 8). Sixteen Vishay VCNL4000 infrared proximity sensors are distributed over the inner surface of the ring. They are set up behind diaphragms which limit their fields of view in order to avoid crosstalk during measures. If a finger is placed inside the ring, its center location can be computed at a rate of 300 Hz using the sensors' data, with a precision of ±0.3 mm (note that for simplicity and computation time considerations, even if the end-effector can reconstruct the finger contour in theory, only the position of the finger's center is estimated here). An inner diameter of 24 mm is chosen, which has been shown to be sufficient to allow the device to track a finger at medium speeds (see below).

3) Control Architecture: The proximity sensors measurements are retrieved by eight ATMega328P microcontrollers which transfer the data to the haptic interface controller through a fast serial bus at a rate of 400 kbps. An estimate of the finger's location is computed as the center of the polygon obtained from the measurements. The controller is composed of a PC104 computer running Xenomai realtime operating system and a servo-drive controlling the two motors. A custom software based on the TAO telerobotics library [START_REF] Gicquel | TAO 2000 : A generic control architecture for advanced computer aided teleoperation systems[END_REF] acquires the state of the interface, computes the finger's position and sends the reference torques to the servo-drive at a rate of 1 kHz. To handle the mismatch between the control loop (1 kHz) and the acquisition (300 Hz) rates, a Kalman filter dedicated to extrapolating the finger's position is implemented.

B. Implementation of the Switch-Based Control Law

A first experiment of encountering a virtual wall is implemented using the switch-based control scheme. The tracking gains are set to: with K e in N/m and B e in Ns/m. Note that the maximum stable gains after contact are three to four times higher than the gains in free space as in this case, the reference variable is the robot's position acquired by the actuators' encoders at 1 kHz whereas before contact, it is the finger's position acquired by the proximeters at only 300 Hz and with a lower accuracy.

K t = 20 0 0 15 B t = 0.65 0 0 0.3
The result is displayed in Fig. 9. The positions and peripheries of the finger's avatar and ring are recorded along with F e and F t (i.e. the operational space projection of τ t ). The center and inner periphery of the ring and the virtual wall are also presented (see Fig. 5).

1) Analysis: From 0 to 35 mm, the finger's avatar is far from the virtual wall. Therefore the ring is tracking the finger, so the ring's center and the finger's avatar center are close. During this phase, F t oscillates up to 1.5 N due to limitations on the tracking system frequency. However this is of no influence since the ring never collides with the finger. As the finger's avatar approaches the virtual wall, ∆X increases so that the finger center no longer coincides with the center of the ring whereas their peripheries become close (see area 9a).

When the finger's avatar comes into contact with the virtual wall (i.e. at 1.4 s), ||F t || ≃ 0 and ||F e || 0 which means that the finger is effectively in contact with the ring (area 9b). If the operator pushes the wall, ||F e || increases and the interface behaves like a common haptic device. When leaving the virtual environment, ||F e || decreases to 0 and the tracking turns on (area 9c).

2) Effects of finger radius Estimation Errors: The above results tend to prove that when the finger geometry is properly estimated, the control law with switch works suitably. However one can note that even in this case, some force overshots of about 3 N can be observed (Fig. 9, end of area 9a and beginning of area 9c). In practice, these behaviors alter the haptic sensation since they can be felt by the user.

Moreover, a real finger is not cylindrical and is also deformable, so its geometry vary necessarily during the contact and is not perfectly known. In this sense and following the hypotheses on the behavior of the system presented on Section II-B, two other experiments are carried out to evaluate the influence of finger radius estimation errors.

• Over-estimation of R f : In this experiment, R f is set to 11 mm whereas the radius of the operator's finger is about 7.5 mm (the error is purposely set to a large value to emphasize the phenomenon). The results are reported in Fig. 10. As the finger's avatar is larger than the real finger, a contact occurs in the virtual world before the operator's finger touches the ring, as shown in the beginning of area 10a. A force F e is thus displayed by the interface although the finger is not in contact with the ring. In other words and as previously hypothesized, the interface moves back and hits the operator's finger to take up their gap, at 1 s. On this impulsion, the finger's avatar moves back and the tracking resumes, and so on, giving rise to the parasitic nonlinearities observed in area 10a. Then the force feedback is felt as realistic in contact (area 10b). One can note that in this phase the over-estimation of the finger radius appears as the finger periphery is several millimeters above the ring's. The same phenomenon as in area 10a arises in area 10c when passing back from contact to tracking, but there the transition from contact to free space is felt as realistic since the nonlinearities occur while the ring disconnects from the finger and moves back before tracking it normally. • Under-estimation of R f : In this experiment, R f is set to 3 mm whereas the radius of the operator's finger is of about 7.5 mm (here again the error is purposely large).

The results are reported in Fig. 11 and are correlated with the theoretical assumptions: as the finger's avatar is smaller, the operator's finger hits the ring before the finger's avatar comes into contact with the virtual wall, here at about 0.5 s. Since the system did not switch yet, the operator feels a repulsive force corresponding to the tracking effort (see F t on area 11a). When the finger's avatar periphery finally crosses the virtual wall, at 1.1 s, the system switches to contact mode and the second (purposed) rendering is sensed (area 11b). Thus the operator feels the virtual object as if it were made of two different layers. The same transition is observed when moving away from the virtual wall (area 11c).

The above experiments confirm that an error on the estimation of the finger radius at the contact location can lead to parasitic behaviors which can decrease the realism of the interaction through the haptic device. These effects may be minimized by enhancing the end-effector's tracking performances in order to better detect the finger geometry. However, this would involve expensive solutions that cannot be considered in a majority of applications.

C. Implementation of the Smooth Control Law

The results of an experiment using the proposed smoothed control scheme are given in Fig. 12. The virtual environment is defined as before and the controller's gains are unchanged compared with the switch-based control law. According to [START_REF] Tachi | A construction method of virtual haptic space[END_REF] and in order for the transition to be independent from most users, we purposely set R f,max to 11 mm (from [START_REF] Greiner | Hand anthropometry of U.S. army personnel[END_REF], it could be argued that this value could be taken as a finger radius' upper bound).

From 0 to 35 mm the behavior of the system is unchanged as it is pure tracking. On area 12a the movement of the ring is stopped whereas the finger continues till it encounters the ring (the finger's avatar periphery is not displayed as it is not taken into account in the control law). The influence of β is noticeable as it almost cancels F t when the finger approaches the virtual object (area 12a). No peak of F t nor F e can be seen. In area 12b, F e is provided according to [START_REF] Yokokohji | What you can see is what you can feel -development of a visual/haptic interface to virtual environment[END_REF] and increases more smoothly than in the previous experiments, since it is computed using X r . Thus the behavior of this control law appears to be better than the switch-based one.

IV. CONCLUSION

In this paper, we presented how an existing state-ofthe-art haptic device has been used to build an encountertype interface. To this purpose, a custom ring with position measurement capabilities has been developed. A switchbased control law has been implemented in the developed setup. It consists in a position tracking mode enabled during free space motion, and a force display mode used to render the virtual environment objects. The transition between the two modes is first managed by a hard switch triggered by the occurrence of a contact between the finger's avatar and the virtual environment, as proposed in the literature. It has been shown that in this case the system suffers unwanted behaviors when switching between the two control modes in case of a lack of a precise on-line estimation of the finger radius. On the one hand, if the finger radius is over-estimated, some impact forces and oscillations appear during each transition between contact and free motion. On the other hand, if the finger radius is under-estimated, the operator senses a parasitic stiffness when his finger comes close to or leaves the virtual object.

A smooth transition-based control law is proposed to cope with the raised issues. The developed approach is based upon two main characteristics. First, it does not depend on the finger radius estimation. Instead, the rendered interaction force is computed based upon the ring geometry, which is constant and well known. Second, rather than switching between position tracking and force display, an adaptive gain is introduced. It moderates the influence of the tracking component in a linear way with respect to the proximity of the finger's avatar to the virtual object. An experimental comparison between both strategies shows that the proposed control law exhibits better performances while being more robust as it is independent from the finger's geometric parameters.

Future work will be twofold. First, the control law analysis will be deepened. Although no instability has been observed during the carried experiments, stability criteria will be further investigated. Second, the design of a 3D encounter-type interface will be considered, with the associated development of a whole virtual reality setup.

FingerFig. 1 .

 1 Fig. 1. Main components and operating principle of close-tracking ETHDs.

Fig. 2 .

 2 Fig. 2. Schematic 2D ETHD with reference frame and points. Grey circle: ring. Dashed circle: finger.

Fig. 4 .

 4 Fig. 4. Positions of the avatars of the finger and ring in function of the distance to the virtual wall. Dashed circles: ring; plain circles: finger; singlesided arrows: ∆X. V.W.: virtual wall.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Overview of the 2D ETHD used during the experiments. The 2D virtual world appears at the background: the finger's avatar is represented by a white disk, free space appears in black and the walls in green.

Fig. 9 .

 9 Fig. 9. 1D displacement with switching control law and finger geometry correctly estimated (R f = 7.5 mm).

Fig. 10 .

 10 Fig. 10. 1D displacement with switching occurring too early (R f = 11 mm, over-estimated).

Fig. 11 .

 11 Fig. 11. 1D displacement with switching occurring too late (R f = 3 mm, under-estimated).

Fig. 12 .

 12 Fig. 12. 1D displacement without switch.

CEA, LIST, Interactive Robotics Laboratory, F-91190 Gif-sur-Yvette, FRANCE.

Sorbonne Universités, UPMC Univ Paris 06, Institut des Systèmes Intelligents et de Robotique, F-75005, Paris, FRANCE.

CNRS, UMR 7222, Institut des Systèmes Intelligents et de Robotique, F-75005, Paris, FRANCE.

INSERM, UI 1150, Institut des Systèmes Intelligents et de Robotique, Equipe Agathe, F-75005, Paris, FRANCE.

ACKNOWLEDGMENT

The authors wish to thank Professors Vincent Hayward and Guillaume Morel (Institut des Systèmes Intelligents et de Robotique, Sorbonne Universités, UPMC Univ Paris 06) for their valuable comments and advice during this research.