Zhenjiang Ni
email: ni@isir.upmc.fr

Aude Bolopion
email: aude.bolopion@femto-st.fr

Joël Agnus
email: joel.agnus@ens2m.fr

Ryad Benosman
email: ryad.benosman@upmc.fr

Stéphane Régnier
email: regnier@isir.upmc.fr

published or not. The documents may come     Asynchronous Event-based visual shape tracking for stable haptic feedback in Microrobotics.

Asynchronous Event-based Visual Shape Tracking for Stable Haptic Feedback in Microrobotics

Zhenjiang Ni 1 , Aude Bolopion 2 , Joël Agnus 2 , Ryad Benosman 3 and Stéphane Régnier 1

Abstract-Micromanipulation systems have recently been receiving increased attention. Tele-operated or automated micromanipulation is a challenging task due to the need for high-frequency position or force feedback to guarantee stability. In addition, the integration of sensors within micromanipulation platforms is complex. Vision is a commonly used solution for sensing; unfortunately the update rate of the frame-based acquisition process of current available cameras can not ensure-at reasonable costs-stable automated or tele-operated control at the microscale level, where low inertia produces highly unreachable dynamic phenomena. This paper presents a novel vision-based microrobotic system combining both an asynchronous Address Event Representation (AER) silicon retina and a conventional frame-based camera. Unlike frame-based cameras, recent artificial retinas transmit their outputs as a continuous stream of asynchronous temporal events, in a manner similar to the output cells of a biological retina, enabling high update rates. This paper introduces an Event-based Iterative Closest Point algorithm to track a microgripper's position at a frequency of 4 kHz. The temporal precision of the asynchronous silicon retina is used to provide a haptic feedback to assist users during manipulation tasks, whereas the frame-based camera is used to retrieve the position of the object that must be manipulated. This paper presents the results of an experiment on tele-operating a sphere of diameter around 50 µm using a piezo-electric gripper in a pick-and-place task.

I. INTRODUCTION

Versatile 3D manipulation systems able to operate in ambient conditions on micrometer-sized objects would greatly increase the potential applications of microtechnology [START_REF] Sariola | Hybrid microassembly combining robotics and water droplet self-alignment[END_REF]. However, the development of such systems faces a major obstacle: the lack of position and force feedback [START_REF] Chaillet | Microrobotics for Micromanipulation[END_REF]. Sensors have been developed [START_REF] Fahlbusch | Force sensing in microrobotic systemsan overview[END_REF], [START_REF] Beyeler | A six-axis MEMS forcetorque sensor with micro-Newton and nano-Newtonmeter resolution[END_REF], but their integration into dedicated tools increases significantly the complexity and cost of the tool fabrication. In particular, even if some microgrippers offer sensing capabilities (at the expense of a complex design) [START_REF] Duc | Electrothermal microgripper with large jaw displacement and integrated force sensors[END_REF], [START_REF] Kim | Micronewton force-controlled manipulation of biomaterials using a monolithic MEMS microgripper with two-axis force feedback[END_REF], [7], most still lack force measurement capabilities [START_REF] Lopez-Walle | Principle of a submerged freeze gripper for microassembly[END_REF], [START_REF] Andersen | Multimodal electrothermal silicon microgrippers for nanotube manipulation[END_REF].

Vision is a promising way to avoid the complexity of integrating sensors [START_REF] Zhang | Automatic control of mechanical forces acting on cell biomembranes using a vision-guided microrobotic system in computer microscopy[END_REF], [START_REF] Zhang | Autonomous robotic pickand-place of micro objects[END_REF]. Visual information can be converted to force measurements to monitor the efforts applied on the objects during manipulation [START_REF] Chawda | Vision-Based force sensing for nanomanipulation[END_REF], [START_REF] Reddy | Miniature compliant grippers with Vision-Based force sensing[END_REF]. This is achieved by using deformable tools after a calibration step [START_REF] Cappelleri | Two-dimensional, vision-based µN force sensor for microrobotics[END_REF]. In particular, the stiffness of the tools must be determined in order to relate the measured deformations to the applied forces. However, the precise value of the force might not be necessary for controlling micromanipulation systems, whether in the teleoperated or the automated mode. In these cases, the position feedback obtained from vision sensors might be sufficient. In all cases, highly dynamic phenomena due to the low inertia at this scale must be recorded. Most of the existing vision-based systems provide feedback at a couple of tens of Hertz, and their complexity depends on the size of the observed scenes [START_REF] Greminger | Vision-based force measurement[END_REF]. Thus they can not ensure the proper monitoring of highly dynamic motion.

Conventional frame-based cameras' lack of dynamic information and their redundancies set an important limit to potential micromanipulations in automated or tele-operated modes. Event-based computer vision based on Address Event Representation (AER) provides a sound solution to highspeed vision problems [START_REF] Delbruck | Frame-free dynamic digital vision[END_REF]. This newly developed discipline is motivated by mimicking biological visual systems [START_REF] Delbruck | Activity-driven, event-based vision sensors[END_REF]. The Dynamic Vision Sensor (DVS) silicon retina used in the research presented in this paper reacts to changes of contrast, which are then converted into a stream of asynchronous timestamped events [START_REF] Lichtsteiner | A 128*128 120 db 15us latency asynchronous temporal contrast vision sensor[END_REF]. The reduction of redundant information makes this technique promising for high-speed tracking.

The use of event-based retinas requires the development of time-oriented event-based algorithms, in order to benefit fully from the properties of this new framework [START_REF] Ni | Asynchronous event based high speed vision for micro-particles tracking[END_REF]. Neural shape coding is a difficult issue as there is almost an infinite number of representations of shapes in the real world. A computationally efficient method is HMax: it models a biological visual system to extract features of different forms for object recognition [START_REF] Riesenhuber | Models of object recognition[END_REF]. However, the shapes of micromanipulators are not very complex. As will be shown, simpler algorithms making full use of the high temporal resolution of the DVS (µs precision) allow fulfilling the high-frequency requirements of micromanipulation. The Iterative Closest Point (ICP) is an efficient algorithm, dedicated to minimizing the difference between a data point set and a model point set [START_REF] Besl | A method for registration of 3-d shapes[END_REF]. Many variants have been proposed to enhance its performance and adaptability [START_REF] Rusinkiewicz | Efficient variants of the ICP algorithm[END_REF]. However, 2D image processing can only be achieved at a frequency of several 10 Hz, depending on the number of points to be matched [START_REF] Martínez | Mobile robot motion estimation by 2d scan matching with genetic and iterative closest point algorithms[END_REF]. Although this is sufficient for many robotic applications, these frequencies are far from sufficient for automated or tele-operated micromanipulation, which requires refresh rates greater than 1 kHz to ensure the stability of the control loop, because of the highly dynamic physical phenomena involved [START_REF] Colgate | Passivity of a class of sampled-data systems: Application to haptic interfaces[END_REF]. This paper presents an Event-based Iterative Closest Point algorithm (EICP) directly applied to the silicon retina's output. It allows tracking the manipulation tool at a frequency of 4 kHz. The positions of static objects are provided by a conventional frame-based camera. This approach was validated by a tele-operated pick-and-place task using a piezo-electric gripper, involving a sphere with a diameter of about 50 µm. Haptic feedback directly estimated from the output of both the event-based retina and the conventional frame-based camera is provided to assist users during the manipulation. The first 3D pick-and-place manipulation with haptic feedback using a microgripper is successfully achieved. Stable vision-based tele-operation has been achieved in this project by the use of event-based retinas and the EICP algorithm.

This paper is based on several previous papers. In [START_REF] Ni | Asynchronous event based high speed vision for micro-particles tracking[END_REF], DVS was used to develop an event-based Hough transformation to track specifically circles. Hough transformations rely on a voting scheme and maximum detection within the accumulation spaces to identify the location of a shape. That paper ends by showing that this can be used to detect the rapid dynamics of Brownian motion. In this paper, we develop a new method to track an arbitrary complex shape, which uses an incremental method that is able to compute, in real time at several kHz, the geometric transformation that maps a complex reference shape to the events acquired by the DVS. This method is related to the family of Iterative Closest Point techniques applied to asynchronous events. This paper also combines the use of a frame-based camera and an event-based camera. Apart from the new vision algorithm, the contribution of this paper includes the action of the DVS at very high frequency as a position sensor, providing valuable haptic feedback. A previous paper treated virtual haptic guides for pick-andplace operations at the microscale [START_REF] Bolopion | Haptic teleoperation for 3D microassembly of spherical objects[END_REF]. However, it used a homemade AFM composed of two independent cantilevers, which made the system very difficult to use. The cantilevers were equipped with force sensors (two optical levers) that provided haptic feedback, but this increased the complexity of the setup since the laser beams had to be aligned with the cantilevers and photodiodes. It was thus definitely not a system that could be used by non-expert users. For these reasons, a simple gripper was chosen for the project presented here. Compared to [START_REF] Bolopion | Haptic teleoperation for 3D microassembly of spherical objects[END_REF], where the two AFM cantilevers were equipped with force sensors, the gripper used in the present project is sensor-deprived. Vision is thus used to compute the haptic feedback. At the microscale, the integration of sensors inside the manipulation tools increases the complexity and cost of the fabrication. Here, we show that event-based cameras can provide this feedback. The integration of this sensor is then a sound solution for microscale applications. Its high frequency and low data load enable the monitoring of the rapid dynamics common at the micro scale. This paper is organized as follows. The experimental setup is presented in Section II. Section III gives details about the vision algorithms used to compute the haptic feedback, which in turn is described in Section IV. The proposed approach is validated by the experimental results presented in Section V. Finally, Section VI concludes the paper.

II. SETUP

Several tools have been developed to manipulate micrometer-sized objects in ambient conditions. The most common ones include cantilevers and grippers. Cantilevers can be used for 2D manipulations, such as pushing or pulling [START_REF] Chaillet | Microrobotics for Micromanipulation[END_REF]. Pick and place operations have also been demonstrated using two protruding tip cantilevers, but the complexity of the setup limits its applicability [START_REF] Bolopion | Haptic teleoperation for 3D microassembly of spherical objects[END_REF]. A microgripper designed at the FEMTO-ST Institute1 (Fig. 1) is used in this project to perform 3D manipulations that will enable a large range of applications, including microassembly. It is based on a pair of piezo-electric beams with two degrees of freedom, called a duo-bimorph, as the actuation principle of the two fingers [START_REF] Agnus | Silicon end-effectors for microgripping tasks[END_REF]. On each actuator, four electrodes referred to a central ground and two voltages are necessary to impose the displacements, based on the deflections of the piezo-electric beam. This configuration offers a number of capabilities: not only an open-and-close motion, but also an up-and-down motion that allows, for example, a fine up-and-down approach or a fine alignment of the finger tips. Objects are grasped by the mean of two silicon end effectors, fabricated by a DRIE (Deep Reactive-Ion Etching) process. They are designed to minimize the sticking effects between the end effector and the objects, in order to facilitate the release of the objects. The end-effectors are fixed on the piezo-electric actuators with reversible thermal glue. The gripper is controlled with instructions sent from a PC to a high-voltage interface (four channels of +/ -150 V) via an RS232 link. Such a microgripper presents a typical stroke of open/close motion and up/down motion of, respectively, 320 µm and 200 µm at the end of the finger tips for +/ -100 V. The gripping force is on the order of a millinewton. The gripper is mounted on a 3-axis motorized micromanipulator2 to allow accurate positioning with respect to the substrate (Fig. 1). The manipulator used relies on stepper motors with a step size of 0.040 µm. It is a cable-driven system with cross roller bearings, it has a sub micrometer resolution, and a travel range of 25 mm. The manipulator was originally controlled through a serial port. However, to increase the communication frequency, a joystick is emulated by programming the manipulator's parallel port using a PCI6259 National Instrument acquisition card.

As shown in Fig. 1, the observed scene is monitored by two optical sensors which record the same view. The light beam is divided into two optical paths, and redirected to an asynchronous event-based silicon retina and a conventional frame-based camera (GigE vision, Basler). The scene recorded by both sensors is magnified by a 10× objective (Olympus).

Haptic feedback is provided to users by an Omega haptic device 3 , with three degrees of freedom for both displacement and force feedback. Forces higher than 5 N are saturated, to avoid any damage to the interface. Both the micromanipulator and the gripper are controlled through the use of this device.

A single PC (Intel Xeon core, 2.93 GHz) operating under Windows 7 runs the threads corresponding to the gripper, the micromanipulator, the vision detection, and the haptic feedback.

III. VISUAL TRACKING A. Event-based artificial vision

Information about a visual scene is transmitted in an asynchronous manner by biological retinas, unlike framebased cameras, and with less redundancy. The event-based vision sensor compresses the digital data in the form of events, removing redundancy, reducing latency, and increasing the dynamic range compared with conventional imagers. A complete review of the history and the existing sensors can be found in [START_REF] Delbruck | Activity-driven, event-based vision sensors[END_REF].

The Dynamic Vision Sensor (DVS) used in this work is an Address-Event Representation (AER) silicon retina with 128 × 128 pixels [START_REF] Lichtsteiner | A 128*128 120 db 15us latency asynchronous temporal contrast vision sensor[END_REF]. As shown in Fig. 2(a), when the change in scene reflectance in log units exceeds a set threshold, a +1 or -1 event is generated by the pixel, depending on whether the log intensity increased or decreased. Because the DVS is not clocked (as are conventional cameras), the timing of the events can be conveyed with a temporal resolution of approximately 1 µs. Thus the 'effective frame rate' is typically several kilohertz. The absence of events when no change of contrast is detected implies that the redundant visual information usually recorded in frames is not carried in the stream of events. Events are transmitted to a computer using a standard USB connection.

Let us denote by ev(p,t) an event occurring at time t at the spatial location p = (x, y) T . Fig. 2(b) shows an example of the spatio-temporal visualization of a set of DVS events in response to the microgripper's closing on a microsphere. An event ev(p,t) describes an activity in the spatio-temporal space. Similar to biological neurons, its influence lasts for a certain amount of time after it has been active. This temporal property of events can be introduced in the form of a decay function applied to model this phenomenon. We can then define S(t), the spatio-temporal set of events active at time t, by

S(t) = ev(p,t i )|e t-t i τ > δ t , (1)
with τ being the time constant parameter of the decay function and δ t the predefined threshold. 3) are shown at chosen temporal locations; they correspond to the accumulation maps of the events, namely, the projection of all events over a time interval on a single plane (X,Y ) regardless of their timings.

B. The Event-based Iterative Closest Point algorithm

The principle of ICP algorithms is to use iteratively a model point set delineating the desired object contour to match an acquired data point set (the matching step). Each step estimates a rigid transformation between the known model and the data, which expresses their geometric relationship (the tracking step). The ICP algorithm is particularly adapted to the task of tracking the gripper's position, as most of its constituent shapes remain unchanged over time; more importantly, the scale of the observation remains unchanged during all the tracking. Let G(t) be the set of positions of 2D model points defining the shape of the gripper at time t. M ev (t) is the set of pixellic locations of active pixels of the silicon retina at time t, defined by

M ev (t) = p ∈ R 2 |ev(p,t) ∈ S(t) . (2)
Following the ICP algorithm, a matching function is needed to pair the model points with the active pixels of the silicon retina. An active event is matched with an element of G(t) by computing the minimal distance between the event's position and all points of G(t) that have not yet been paired.

We can then define the matching function by

match : M e (t) → G(t) p → p k , k | arg min k∈{1,...,N G } d(p, p k ), (3)
where d(p, p k ) is the Euclidean distance between two points and N G is the size of G(t).

It then becomes possible to estimate the rigid body transformation (R, T) between M ev (t) and G(t) by minimizing a mean square cost function:

min R∈SO(2),T∈R 2 ∑ p∈M ev (t) Rp -T -match(p) 2 , ( 4
)
where R is the rotation matrix belonging to the 2D special orthogonal group SO(2) and T is the translation vector. Readers interested in the details of this minimization can refer to [START_REF] Besl | A method for registration of 3-d shapes[END_REF]. Fig. 3 provides the principle of the event-based algorithm. Update the content of S(t) and M ev (t).

3:

Compute match(p).

4:

Estimate (R,T) according to equation (4).

5:

Update the position of model points of G(t) using (R,T). 6: end for

The gripper closes at a speed of 13 pixels per second (1 pixel=1.5 µm), producing a mean rate of 14k events per second. The edge width of the gripper in the DVS focal plane is around three pixels. When the gripper finger passes a pixel, 10.6 events on average are generated on it. Therefore, according to the timestamp, one pixel remains active for 2.46 ms. The decay function permits a pixel's activity to be considered during a certain period after it has been spiked, which is tuned to about 10 ∼ 15 ms. The EICP is event driven, and its update rate has a mean value of 4 kHz. The algorithm is implemented in Java under the JAER open-source project [27].

As far as we know, high speed tracking of relatively complex shaped micromanipulation tools by using software alone has not yet been reported. However, the general visual tracking performance of an ICP algorithm has been experimentally demonstrated. The closest performance can be found in a hardware implementation of a frame-based technique in [START_REF] Belshaw | A high speed iterative closest point tracker on an fpga platform[END_REF], where it is shown that the processing speed reaches a rate of 200 fps for 512 data points and 2048 model points. That paper also demonstrates that a software implementation of the same algorithm runs at a rate of 39 Hz with extra optimization. The use to be presented here of an event-based camera using a classic PC with no particular software speeding process outperforms existing algorithms, since several kHz are reached.

The performance benefits of using DVS over frame-based cameras is significant. A dynamic vision sensor does not generate frames: its pixels are autonomous and react asynchronously to temporal contrast changes. The current shape registration algorithms are designed to work on image frames, usually acquired at a fixed rate. An acquired frame must then be processed, an edge detection must be applied, and in a second stage the registration algorithm is used to track the object. This operation is time consuming. The data load of a classic frame grabber at a frequency of 1 kHz would be so huge that the computation power needed would require specific hardware or a computer grid. The benefits of a dynamic vision sensor is that it encodes during its acquisition process a compression and a natural edge detection. Thus, the amount of data provided by a DVS is really low: the seminal paper [START_REF] Lichtsteiner | A 128*128 120 db 15us latency asynchronous temporal contrast vision sensor[END_REF] shows that this can amount to 10% of an equivalent framecamera of the same resolution. The second advantage of its computation is that it introduces an alternative approach to visual processing by introducing the timing of the changes as a main computational feature, and not grey level values.

The frame-based camera in our system serves as a complement to the DVS silicon retina solely for static object detection. The focal planes of both the DVS (128×128 pixels) and the frame camera (659 × 494 pixels) are related by a homography transform, as both observe the same 2D plane [START_REF] Hartley | Multiple View Geometry in computer vision[END_REF]. The homography is estimated off-line by extracting from both sensors' focals plane the coordinates of six corner points of the gripper fingers and linking them to the actual metric of the gripper's points in the scene (see Fig. 4). During the application, the circle corresponding to the sphere to be manipulated is detected using a frame-based Hough transform through the conventional camera output. Once detected, its location is converted into the coordinate system of the focal plane of the event-based retina. This operation provides the locations of both the gripper and the sphere in the same coordinate system. It then becomes possible to estimate the distance δ x between the gripper's fingers. If an object is detected between the two fingers, the relative finger-object distance on the left and the right sides δ xl , δ xr and the distance between the centre of the sphere and the gripper δ y (Fig. 4) are estimated as well. These distances will be used to compute the haptic feedback.

IV. HAPTIC COUPLING

A. Manipulation modes

Fig. 5 represents the coupling between the haptic device and the microgripper. The operator applies a force F op to the haptic device and receives a force feedback F h based on the distance between the gripper and the sphere δ x , δ xl , δ xr and δ y determined from vision. Using the haptic interface, the user can control the displacement of the micromanipulator as well as the opening and the closing of the gripper. Scaling factors α d and α oc are introduced to convert the position of the haptic handle to the variables used to control the position and the actuation of the gripper.

To ensure ease of manipulation, different modes have been defined with adapted haptic feedback:

• Planar displacement: the operator controls the displacement of the gripper in a plane parallel to the substrate, the (x, y) plane. No force feedback is provided: F h T = 0 0 0 , • Vertical displacement: the operator controls the displacement of the gripper along the vertical direction. A constant repulsive force feedback is provided along the z direction so that the user has to make an effort to approach the gripper to the substrate, to avoid unexpected contact: (1) 1)-( 6)) have been chosen to calculate the homography transform H. The detected circle (left) is transferred by UDP socket so that the DVS part has both gripper and circle position available (right). δ xl and δ xr describe the distance between the gripper's fingers and the sphere on the left side and the right side, δ x is the distance between the two fingers, and δ y is the distance between the centre of the fingers and the centre of the sphere.

F h T = 0 0 F hz , (a)
• Gripper control: the operator controls both the opening and closing of the gripper and its position along the y-axis to align the gripper with the middle line of the sphere. A 2D force feedback (explained in detail in the next paragraph) is provided to assist the user:

F h T = F hoc 0 F hy .
The operator selects the appropriate manipulation mode on a graphical user interface developed in C++. To avoid any large and sudden changes in force feedback during transitions between different modes, the haptic force is filtered by a Haptic coupling scheme. The user controls the position of the gripper and the actuation of the gripper's fingers using the haptic interface and receives haptic feedback through the device. The haptic force is based on the distance between the gripper and the sphere, determined from vision algorithms. Scaling factors α d and α oc convert the position of the haptic handle to the variables used to control the position and the actuation of the gripper.

second-order low-pass filter for the first couple of seconds after the selection of the desired mode. The filter is then deactivated to enable all the force variations to be sent to the user without smoothing. Note that even if the haptic feedback is delayed because of the time response of the filter, this is not an important issue as it occurs before the user actually starts to manipulate the gripper in the chosen mode.

B. Gripper control

To increase the success rate of the pick-and-place operation, two criteria should be met: the sphere should be grasped on its middle line, and the grasping force should be enough to lift the sphere yet controlled to avoid any damages to the object. The haptic feedback must assist the user in these two operations.

To help the user align the gripper with the middle line of the sphere, a haptic force corresponding to a spring of stiffness k between the position of the gripper and the sphere is provided,

F hy = -kδ y , (5)
where δ y is the distance between the centre of the gripper and the centre of sphere along the y-axis (see Fig. 4).

A haptic feedback F hoc is provided so that the user can monitor the grasping force. Contrary to what is commonly proposed in the literature, we are not here interested in computing the exact efforts applied to the object, but only in deriving information to assist the user while performing a given task. The calibration process which enables relating the tool deformations to the applied force is thus unnecessary. While closing the gripper, the user has to counteract a haptic force F hoc ,

F hoc =    F max e -δ f x 2 α if not in the contact zone F contact if in the contact zone. (6)
Here, δ f x is the free space between the two fingers of the gripper. If the sphere is situated between the fingers, then δ f x = δ xl + δ xr , which corresponds to the sum of the distances between each of the fingers and the sphere; otherwise, δ f x = δ x . F max is the maximum force that can be transmitted to the user when the gripper is close to the sphere but has not yet entered the contact zone. α is a constant chosen to tune the decrease of the haptic force as the distance between the two fingers increases. F contact is the force sent while the gripper is grasping the sphere. The step between F max and F contact must be high enough to indicate clearly the contact between the sphere and the gripper. The contact zone is reached if δ xl and δ xr are less than a given distance δ 1 = 3 µm (which corresponds to 6% of the sphere diameter). The gripper will then reach the non-contact zone if δ xl and δ xr are greater than δ 2 = 7.5 µm. This hysteresis avoids undesirable frequent transitions between contact and non-contact modes because of noise or tracking error. The hysteresis values δ 1 and δ 2 were chosen, based on our experience, for a comfortable user sensation. The force step that is sent to the user when contact is detected is filtered to avoid large and sudden force changes. Even if the user does not receive the maximum force feedback at the instant of contact, the increase in the force can be distinctly felt, and so it can be inferred that contact has happened.

V. EXPERIMENTAL RESULTS

A. The influence of the sampling rate on stability

To visualize the influence of the sampling rate on the stability of the haptic feedback, an experiment consisting of grasping a sphere is performed for different resampled frequencies from the vision algorithm output. The estimated distances are transferred to the haptic thread with resampled dynamics manually set to 10 ms and 100 ms for comparison with the unfiltered output of the EICP. For each frequency, the object is grasped and released three times (without being lifted). The results are given in Fig. 6. It can be seen that as the frequency decreases, the effort is less smooth. This is very disturbing for the user, who has to counteract this variation. The user attenuates the oscillations by grasping firmly the haptic handle, which is equivalent to adding damping to the system. The plots show the attenuated oscillations. Fig. 6 does not represent an unstable response from a control point of view, since the user manages to limit the oscillations. However, the haptic feedback is highly uncomfortable and the user has to concentrate to counteract it. For low frequencies, the system's performance decreases, which makes it unsuitable for complex 3D manipulation. Fig. 6. Haptic forces during the grasping operation for different frequencies of the vision feedback. The haptic force F hoc that helps monitor the grasping force is provided. Note that for each experiment, the user grasped the sphere three times, and released it. As the frequency decreases, oscillations appear.

B. Pick-and-place of microspheres

Some experiments were performed to validate the use of event-based vision in computing haptic feedback. The microspheres are glass beads of about 50µm in diameter from Polysciences, Inc. 4 . To avoid issues of sticking while releasing the spheres, a Gel-Pack substrate was selected. When the gripper lets go of the sphere, the Gel-Pack substrate provides enough adhesion to prevent the sphere from sticking to the gripper.

The experiment consists of positioning the gripper with respect to the sphere (in plane displacements), grasping it, picking it up, moving it, putting it down, and, finally, releasing it. The precision of gripper tracking during this process is depicted in Fig. 7, where the ratio of the mean ICP tracking error to the microsphere diameter is calculated. It can be seen that when the gripper closes, the tracking error converges to a constant value, which corresponds to 7% of the diameter of the sphere. The 'picking up' operation may cause a z-axis defocusing, so the error slightly increases. The 'putting down' operation produces similar results. For the sake of clarity, it has been omitted from the figure.

To assist the user in aligning the gripper with the sphere, haptic feedback is provided for both the grasping and the releasing tasks. The results are given in Fig. 8 for the grasping. They are similar for the releasing stage, which is hence omitted. The user controls the position of the gripper along the y-axis. A haptic force F hy that corresponds to a virtual stiffness between the centre of the gripper's fingers and the centre of the sphere is transmitted to the operator. At the beginning of the experiment, the gripper is misaligned, and the user feels an attractive force that pulls the user to the correct position. After 13 s, the gripper is correctly aligned, and the haptic feedback drops to zero.

The evolution of F hoc , the haptic force that helps the user monitor the grasping force, is given in Fig. 9 for both the grasping and releasing stages. When t 1 < 11.8 s, the user closes the gripper on the sphere. As the free space between the gripper's fingers and the sphere decreases, the operator has to counteract an increasing haptic force F hoc . At t 1 = 11.8 s, the gripper enters the contact zone, and the user feels a large and sudden increase of the haptic force. The sphere is grasped. Due to an initial misalignment of the finger tips (along the vertical z-axis), this grasping causes a rotation of the sphere between the two fingers and amplifies the misalignment. Thus, the right finger goes down, and left finger goes up. Since the gripper is mounted with an angle of about 45 • with respect to the horizontal plane (see Fig. 1), a shift between the finger tips along the y-axis can be observed by the projection on the top view in the inset of Fig. the grasping and releasing operations, the user receives haptic feedback which helps in the performance of the task.

During the lifting and the putting operations, a constant repulsive haptic force field, set to 2 N, is provided to avoid any involuntary contact with the substrate (Fig. 10). When the sphere has been lifted above the substrate to the desired height, the user can move it freely in the (x, y) plane parallel to the substrate (α x d = 4.0 × 10 3 , α y d = 2.5 × 10 3 ) 5 . For this operation, the haptic feedback is turned off.

A high frequency capability for the sensor is of the utmost importance for real-time applications at the microscale, since the low inertia of the objects induces rapid dynamics. In addition, due to the scale difference, position and/or force scaling factors are necessary to decrease the movements performed by the user so that they can be used as an input for the micromanipulation system and to enhance the force so that it can be used as a haptic feedback (if the interaction force between the gripper and the sphere is measured). To ensure stability, the ratio of these scaling factors multiplied by the square of the sampling rate of the system and the stiffness of the contact must be less than the inertia of the haptic device (see [START_REF] Bolopion | Variable gain haptic coupling for molecular simulation[END_REF]). Ensuring stability is possible either by adapting the scaling factors or by increasing the sampling 5 Different factors are used along the three axes of the micromanipulator to achieve easy positioning. They are set according to the user's comfort of manipulation. rate. Adapting the scaling factors leads to time consuming experiments or very weak haptic feedback. In practice, this renders the system uncomfortable and difficult to use. A sensing capability higher than 1 kHz is commonly recommended [START_REF] Colgate | Passivity of a class of sampled-data systems: Application to haptic interfaces[END_REF]. Getting high frequency sensing is the only solution for providing usable haptic feedback systems. In this paper, the vision sensors and detection algorithms provided a highfrequency feedback that enabled users to successfully perform a 3D tele-operated manipulation on micrometer-sized objects. The results in this paper will surely benefit tele-operated or automated microassembly and open new perspectives for complex micromanipulation.

VI. CONCLUSION

To overcome the lack of sensing capabilities at the microscale, a vision-based system has been proposed. To enable a wide range of applications, in particular for automated or teleoperated micromanipulations, the frequency of the vision feedback must be higher than 1 kHz, as the low inertia present at this scale induces highly dynamic phenomena. This is ensured by the output of the DVS sensor, which conveys temporal contrast in the scene in the form of time-stamped events. An Event-based Iterative Closest Point algorithm (EICP) has been proposed, to track the tool at more than 4 kHz. This feedback is combined with the output of a classical frame-based camera, used to derive information about static parts of the scene, and in particular the position of the object that must be manipulated. This approach was tested with a pick-and-place experiment of a glass sphere with a diameter about 50 µm using a piezo-electric gripper. The task was realized by teleoperation with haptic feedback. This application is especially challenging as a frequency of more than 1 kHz is required for the system's stability. The influence of the frequency rate on the system's stability has been experimentally highlighted, and the benefits of the DVS sensor over conventional frame-based cameras with lower frequencies was shown. A successful pickand-place task of micrometer-sized objects with 3D haptic feedback based on vision tracking was performed with this system.

These results can be easily extended to other applications, involving different objects or tools. In particular, vision-based force measurement could be performed with the DVS sensor after the calibration of the tool. Fully automated manipulation also would benefit from the high frequency of the feedback to guarantee the system's stability. Future research projects include the use of a model of the gripper to avoid tracking drift from the loss of focus while performing out-of-plane movements.

VII. ACKNOWLEDGMENT This work was supported by the French Agence Nationale de la Recherche, through the NANOROBUST project (contract ANR 2011 NANO 006).

Fig. 1 .

 1 Fig. 1. Setup of the micromanipulation platform

Fig. 2 .

 2 Fig. 2. (a) Principle of the generation of events of DVS pixels, adapted from Lichtsteiner et al. [18]. Events with +1 or -1 polarity are emitted when the change in log intensity exceeds a predefined threshold. (b) Events are generated in (X,Y,t) space when the gripper closes on a sphere. Images (1)-(3) are shown at chosen temporal locations; they correspond to the accumulation maps of the events, namely, the projection of all events over a time interval on a single plane (X,Y ) regardless of their timings.

Fig. 3 .

 3 Fig.3. The principle of event-based iterative closest point tracking (EICP). The first row is a sequence of conventional images showing the closing of the gripper. The middle row shows the events' accumulation maps. The last row is the convergence of the EICP model to the gripper edges. The four images in the first column (a) show the initial state when the gripper is fully opened. The model set (solid lines) is trying to match the corresponding closest events, which are represented on an accumulation map (AC map), and the rigid body transformation (R, T ) is estimated to update the model position. In (b), the model is converging to the real gripper's position, until it converges to the gripper's location (c). Finally, in (d), while the gripper is closing, the model's position is updated simultaneously.

Fig. 4 .

 4 Fig.[START_REF] Beyeler | A six-axis MEMS forcetorque sensor with micro-Newton and nano-Newtonmeter resolution[END_REF]. The calibration between the classical image (left) and the DVS accumulation map (right). Six points (crosses (1)-(6)) have been chosen to calculate the homography transform H. The detected circle (left) is transferred by UDP socket so that the DVS part has both gripper and circle position available (right). δ xl and δ xr describe the distance between the gripper's fingers and the sphere on the left side and the right side, δ x is the distance between the two fingers, and δ y is the distance between the centre of the fingers and the centre of the sphere.

  Fig. 5.Haptic coupling scheme. The user controls the position of the gripper and the actuation of the gripper's fingers using the haptic interface and receives haptic feedback through the device. The haptic force is based on the distance between the gripper and the sphere, determined from vision algorithms. Scaling factors α d and α oc convert the position of the haptic handle to the variables used to control the position and the actuation of the gripper.

Fig. 7 .

 7 Fig. 7. Gripper position-tracking error. Images represent different steps. a-b): the gripper converges to the gripper contour from its initial position; c-d): the gripper closes, and its position is tracked; e): the sphere is lifted and the gripper starts to defocus. This induces a smoothing of contours that then lowers the tracking precision.

Fig. 8 .

 8 Fig.8. The haptic force F hy that assists the user to align the gripper with the middle line of the sphere during the grasping operation. Eq. (5) is used with the following parameters: k = 50000 N • m -1 (a misalignment of 100 µm produces the maximum force admissible by the haptic interface, 5 N). The displacement scaling factor along the y-axis is set to α y d = 2.5 × 10 3 .

Fig. 9 .

 9 Fig.9. Haptic force F hoc used to control the grasping force. It is computed using Eq. (5) with the following coefficients: F contact = 5 N (set to the maximum admissible force of the haptic interface), F max = 2 N, α = 1.44 • 10 -8 (a distance of 100 µm produces a haptic force of 1 N). The opening/closing scaling factor is set to α oc = 1.8 × 10 -3 m.V -1 .

Fig. 10 .

 10 Fig.10. The vertical haptic force F hz sent to users during lifting, moving, and putting down operations. To perform the vertical displacements, a scaling factor α z d = 12.5 × 10 3 is used.

  at time t 3 = 43.5 s. As the gripper contacts the sphere, a constant haptic force is felt (equal to 5 N), which helps the user open the gripper. At t 4 = 45.3 s, the gripper is opened, and the fingers are out of the contact zone. The haptic force drops suddenly. It can be noted that it does not reach 0, as the force is still assisting the user to open the gripper (and avoid unexpected closing). For the entirety of each of

[START_REF] Andersen | Multimodal electrothermal silicon microgrippers for nanotube manipulation[END_REF]

(or more clearly in the insets of Figs. 7d) or 7e)). At t 2 = 15.6 s, the operator begins the pick-and-place operation. To avoid any disturbance during this operation, F hoc is set to zero. The user starts to release the sphere

http://www.femto-st.fr/

Sutter Instrument, http://www.sutter.com/MP 285

Force Dimension, http://www.forcedimension.com

http://www.polysciences.com/


T Coudert

B Grabot

B Archime

Á De

Production/maintenance cooperative scheduling using multi-agents and fuzzy logic

Within companies, production is directly concerned with the manufacturing schedule, but other services like sales, maintenance, purchasing or workforce management should also have an in¯uence on this schedule. These services often have together a hierarchical relationship, i.e. the leading function (most of the time sales or production) generates constraints de®ning the framework within which the other functions have to satisfy their own objectives. We show how the multiagent paradigm, often used in scheduling for its ability to distribute decisionmaking, can also provide a framework for making several functions cooperate in the schedule performance. Production and maintenance have been chosen as an example: having common resources (the machines), their activities are actually often con¯icting. We show how to use a fuzzy logic in order to model the temporal degrees of freedom of the two functions, and show that this approach may allow one to obtain a schedule that provides a better compromise between the satisfaction of the respective objectives of the two functions.

Introduction

Within industrial companies, several functions, often called Departments or Services, have very close links with production at the operational level, even though their respective objectives may be partially con¯icting. These functions can be the following.

. Sales: main objective of which is to provide the customer with the right product at the right moment. . Distribution: objective of which is to respect the product due date and minimize the distribution cost. . Maintenance: aims to insure the availability of the production resources through curative, and also preventive or cleaning activities. . Inventory management: has to make raw materials and components available for production. . Purchasing management: its mission is to buy the resources and services required by the company. . Human Resource management: one of its operational objectives is to manage the workforce according to technical (skill) and legal (working time) criteria.

These functions are in some cases linked by the product ¯ow, since they may act at di erent steps of the process elaboration. It is, for example, the case for Purchasing, Inventory Management, Production and Sales, which are sequentially involved. Nevertheless, their respective actors may have di erent ideas on the optimality of the ¯ow that they manipulate. The link between functions may also result from the use of common resources, like Production and Human Resource management (which both concern the workers), or Production and Maintenance (acting on the manufacturing machines).

Like in any control problems, the possible con¯icts may be avoided by a hierarchical coordination, or solved by negotiation. Nevertheless, note that in practise, the respective degrees of freedom of the functions are determined at the middle term and are seldom set into question at an operational level like the scheduling level. Lot sizes, inventory levels, teams or periods of maintenance are so de®ned once and belong to the set of hypothesis which constrain the schedule.

In that context, it is paradoxical that even if scheduling has been recognized for a long time as a multi-objective process [START_REF] Smith | Knowledge-base production management: approaches, results and prospectives[END_REF], it is seldom admitted that other functions should interfere with production during the schedule elaboration. In practise, the objectives taken into account are usually only related to the customer's satisfaction (`external' or `exogenous' objectives, related to due date, quality or service) or aim at satisfying internal constraints of the production system (`internal' or `endogenous' objectives: minimize work in progress, optimize resource use, etc.) (ZuÈ lch et al. 1994[START_REF] Grabot | Objective satisfaction assessment using neural nets for balancing multiple objectives[END_REF]).

Scheduling techniques like constraint-base d analysis [START_REF] Fox | Constraint-directed Search: A Case Study of Job-shop Scheduling[END_REF] could allow one to model and dynamically take into account objectives coming from other functions while performing the schedule, but the division between functions seems still to be an obstacle at the operational level. Besides, this division is often considered as preventing an improvement of the manufacturin g e ciency, and process-oriented reorganization techniques like Business Process Reengineering [START_REF] Hammer | Reengineering the Corporation: A Manifesto for Business Revolution[END_REF] are increasingly more widely spread.

Even in standard function-based organizations, we think that important improvements can be obtained by providing the actors with e cient operational tools which could manage the negotiation process, as long as the objectives of each function have been clearly expressed. We have chosen the multi-agent paradigm for the de®nition of such tool because of its well-known ability to support distributed decision-making. The prototype system that has been developed illustrates the possible cooperation of Maintenance and Production while performing a schedule: these functions are often a source of con¯ict in companies (e.g. [START_REF] Weinstein | Integrating maintenance and production decisions in a hierarchical production planning environment[END_REF] since, as stated above, they both act on the manufacturing machines. Moreover, reducing the work-in-progress requires that the machines are available when they are required. Tight links should thus be introduced between Production and Maintenance [START_REF] Swanson | The impact of new production technologies on the maintenance function: an empirical study[END_REF].

A panorama on related research is given in Section 2: some relevant studies on multi-agent systems for scheduling are discussed, then some approaches aimed at making Production and Maintenance cooperate are described. Our implementation framework is based on an already existing multi-agent scheduler, the RAMSES system, which is described in Section 3. RAMSES II, the suggested Production/ Maintenance scheduler, is described in Section 4. To allow negotiation, the degrees of freedom of the negotiating partners must be expressed in the same formalism. Section 5 shows that fuzzy sets allow one to de®ne the temporal degrees of freedom of Production and Maintenance as fuzzy temporal windows, allowing one to solve con¯icts through a negotiation process which is described. The results of this negotiation-base d approach are described in Section 6.

Panorama on related research

Multi-agent approaches for scheduling

The multi-agent paradigm o ers a convenient framework for modelling the various entities that constitute the manufacturin g system: an agent class can represent a type of entity of the system (machines, orders, workers, etc.) and allows to encapsulate the behaviour of each entity (objectives, reaction to events, etc.). The schedule performance emerges then from the local behaviour of the involved agents, allowing distributed decision-making and reaction capacities. A state-of-the-ar t of multi-agent approaches for intelligent manufacturing can be found in [START_REF] Shen | Agent-based systems for intelligent manufacturing: a state of the art survey[END_REF], which describes more than 30 di erent studies among which many are oriented on scheduling. Most of these approaches are based on the Contract-Net communication protocol [START_REF] Smith | The contract-net protocol: high level communication and control in a distributed problem solver[END_REF]. Using the Contract-Net, an announcement concerning a task to perform is sent within the multi-agent system. Bids are made by the agents capable of performing the task. The bids are collected and compared, and a contract is made with the agent which has made the best proposal. YAMS (Yet Another Manufacturing System) [START_REF] Parunak | Manufacturing experience with the contract net[END_REF]) is certainly the ®rst attempt of using the Contract-Net for task allocation within a manufacturing system. The production system is considered as a hierarchy of manufacturing cells, each node being modelled by an agent. YAMS does not directly allow to generate a schedule, but can repair an existing solution set into question by the occurrence of a disturbance. A multi-agent scheduler, also based on the Contract-Net approach, has been suggested in [START_REF] Saad | Performance evaluation of contract netbased heterarchical scheduling for ¯exible manufacturing systems[END_REF]. Agents model the articles to manufacture and the machines, the manufacturing objectives being to minimize resource use and cycle time, and to meet the due dates. When an article enters the system, the corresponding agent makes an announce concerning its manufacturing operations. For each operation, bids are made by the capable machine-agents, including a beginning date and the list of operations already planned on the machine. The article-agent chooses the machine which agent suggests the earliest beginning date.

The Contract-Net protocol is again used in Metamorph [START_REF] Maturana | Metamorph: an adaptive agent-based architecture for intelligent manufacturing[END_REF]): agents model one more time products and resources, and are coordinated by higher level agents which can keep trace of the machines which bids have not been selected. If a disturbance occurs, a reaction can be de®ned using these machines.

Other approaches, like [START_REF] Liu | Distributed problem solving through coordination in a society of agents[END_REF], suggest a coordination mechanism requiring the de®nition of the scheduling problem as a constraint satisfaction problem. Resource-agents express the capacity constraints, whereas job-agents express the precedence constraints between tasks, so that the earliest beginning and delivery dates. A similar method is suggested in [START_REF] Miyashita | CAMPS: a constraint-based architecture for multiagent planning and scheduling[END_REF] with the di erence that each agent addresses its own constraint satisfaction problem separately from the others. A negotiation process then solves the con¯icts.

In other studies, the multi-agent approach is used to repair a schedule (e.g. [START_REF] Tranvouez | A multi-agent based scheduling system: a cooperative and reactive approach[END_REF] or for real-time control of ¯exible cells [START_REF] Sohier | Applying eco problem solving to the control of an adaptive manufacturing cell[END_REF]. In this last case, the interaction between static agents modelling the production environment (robots, machines, etc.) and dynamic agents (modelling parts, tools or Numerical Control programs) allows one to generate a production scenario.

These studies do not all have the same goals, and di erences may be noticed between the communication or negotiation protocols which are used. Nevertheless, they have some important common points.

. In most of these approaches, the agents that model the parts have in charge the respect of the `external' manufacturing objectives, i.e. those related to the customer's satisfaction, whereas the agents modelling the resources have in charge the respect of the `internal' objectives, i.e. objectives expressing the need to produce at best cost. . Approaches using constraint propagation do not usually allow one to add or remove constraints during the solving process, having for consequence the de®nition of a rather rigid framework. An advantage is that their global approach may lead to an optimal solution. . Contact-Net o ers a rather ¯exible way to manage the degrees of freedom that may exist in the choice of the resource to perform an operation. A drawback is that the method is myopic, i.e. the choice of a resource is usually based on a local performance evaluation. . In all the cases, the negotiation process must be carefully controlled: many resource con¯icts are usually to be solved during the schedule elaboration, and solving these con¯icts through negotiation can be time consuming. Therefore, it is important to only introduce negotiation where it brings an added value.

Cooperation between production and maintenance

Several types of Maintenance are to be distinguished since they lead to di erent kinds of interactions with Production (e.g. [START_REF] Paz | Maintenance scheduling: issues, results and research needs[END_REF]. Their classi®cation may vary according to the chosen criterion, but the following categories are usually de®ned.

. Curative maintenance occurs after a machine breakdown. In that case, there is no con¯ict between Production and Maintenance since the concerned machine is not anymore available for Production. Nevertheless, con¯icts may arise between several manufacturing resources when they require at the same time a curative maintenance activity. This type of con¯ict may be considered as internal to the Production function and is usually solved thanks to an implicit of explicit level of priority between machines requiring a curative maintenance activity. . In preventive maintenance, the decision to perform an activity precedes the occurrence of disturbance. Three main preventive maintenance categories may be distinguished:

. Systematic preventive maintenance, characterized by a periodicity between maintenance activities, determined arbitrarily or according to the resource law of behaviour. . Condition-based maintenance, triggered by the occurrence of symptoms or by reaching a given level of damage. . Predictive maintenance, based on the occurrence of events that may lead to disturbances.

Scheduling maintenance activities is a problem on its own: the duration of the maintenance activities may be imprecisely known [START_REF] Paz | Maintenance scheduling: issues, results and research needs[END_REF] and the beginning date of a preventive maintenance activity may be brought forward or postponed in comparison with the optimal date [START_REF] Gits | Structuring maintenance control systems[END_REF]). Many studies have been done on the composition of maintenance teams, like [START_REF] Basker | Simulating multi-skill maintenances: a case study[END_REF] and [START_REF] Barnett | Trade demarcations in maintenance: determination of optimum crew sizes by the Monte-Carlo simulation technique[END_REF]. The e ciency and cost of maintenance policies are also often compared [START_REF] Pateâ-Cornell | Warning of malfunction: the decision to inspect and maintain production process on schedule on or demand[END_REF][START_REF] De Carvalho | A Markov model for the optimization of a maintenance system with a performance constraint[END_REF][START_REF] Kelly | Impact of maintenance policies on the performance of manufacturing cells[END_REF].

Three possible hierarchical positions of Production and Maintenance can be used in industrial systems.

. Production can have a higher position, with the result that preventive maintenance is only performed during under-loaded periods. This can be the case when a high utilization ratio of the machines is required, especially when the machines are easy to maintain. . Maintenance can have the higher position: preventive maintenance activities are positioned ®rst and de®ne closed periods in the machine calendars. The manufacturing operations are scheduled as a second step. . Production and Maintenance can be considered as having the same hierarchical level, requiring either coordination or cooperation. This cooperation or coordination is particularly needed when the periods of preventive maintenance are short regarding the manufacturing processing times, and/or when the maintenance activities are long in comparison with the manufacturing operations.

In that context, the coordination or cooperation between Maintenance and Production has several objectives.

. Be sure that enough time is left by Production to Maintenance activities.

. Be sure that Maintenance performs the preventive maintenance activities at the right moment. . Be sure that Maintenance reacts rapidly to machine breakdowns [START_REF] Gits | Structuring maintenance control systems[END_REF][START_REF] Rishel | Incorporating maintenance activities into production planning; integration at the master schedule versus material requirement level[END_REF][START_REF] Swanson | The impact of new production technologies on the maintenance function: an empirical study[END_REF]. [START_REF] Rishel | Incorporating maintenance activities into production planning; integration at the master schedule versus material requirement level[END_REF] described an approach where Maintenance is considered together with Production in an MRP system: a Material Requirement Planning is performed for the two types of activities and various maintenance policies are tested and assessed. [START_REF] Weinstein | Integrating maintenance and production decisions in a hierarchical production planning environment[END_REF] showed a multi-objective linear programming method that performs a hierarchical planning for production and maintenance activities. In [START_REF] Brandolese | Production and maintenance integrated planning[END_REF], a ¯ow-shop system is scheduled, and a probabilistic model taking into account cost and reliability calculates the temporal windows where the maintenance operations should be located. The use of probabilistic approaches has also been considered in order to plan maintenance activities on production lines in [START_REF] Sanmarti | Batch production and preventive maintenance scheduling under equipment uncertainty[END_REF] where, in each temporal interval of the simulation horizon, a model allows one to choose between producing and having the risk to see a failure occur and performing a maintenance activity and making the cost increase. A similar approach is used in [START_REF] Ashayeri | A production and maintenance planning model for the process industry[END_REF]: the maintenance activities are modelled as ®ctive manufacturing orders (MOs) and scheduled together with manufacturing operations. In [START_REF] Deniaud | Plani®cation de la maintenance pre ventive d'une ligne de fabrication d'Alstom[END_REF], an industrial case is considered in which simulation is used for balancing maintenance and manufacturing activities.

In all these works, it can be seen that a higher level coordination is de®ned, which may prevent a good reactivity of the system. On the other hand, this coordination is less time consuming than cooperation when a schedule is performed.

More generally, in [START_REF] Ayel | Concurrent decisions in production management[END_REF] can be found the description of a multi-agent system where each agent represents a decision centre of the production system. The various agents may then represent di erent functions and the possible con¯icts between functions are solved by negotiation. Nevertheless, the purpose of this multiagent system is mainly to synchronize di erent activities and not to coordinate di erent functions acting on the same activity. Consequently, the results can hardly be adapted to the problem of cooperative scheduling.

As stated above, multi-agent systems may provide an e cient paradigm for modelling negotiation activities between di erent entities and have e ciently been used in scheduling. We describe below how an existing multi-agent scheduling system has been modi®ed to provide a cooperation medium for scheduling maintenance and production activities.

RAMSES multi-agent scheduler

The RAMSES (ReActive Multi-agent SystEm for Scheduling) environment has been developed to test various scheduling strategies in a multi-agent context (ArchimeÁ de and Coudert 2001). It is quite open and ¯exible and allows one, for instance, to deal with ¯exible routings (an operation can be performed by several machines under di erent conditions, operations can be de®ned as permutable, etc.) and to associate di erent objectives to the agents. The RAMSES multi-agent model is based on the architecture described in ®gure 1.

This communication protocol between agents used in RAMSES is close to the Contract Net protocol. At the beginning of the scheduling process, the supervisor agent creates and initializes the MO and machine agents. The possible objectives of a MO agent are to minimize its cycle time, to respect a due date or to minimize a manufacturing cost (the machines can have di erent hourly rates). The supervisor is in charge of controlling the execution of the negotiation cycles between agents and the access to the blackboard describing the current solution and the bids under negotiation.

A MO agent has to plan manufacturing operations de®ned in its associated routing. It expresses its requirements by an announce containing the operations, their characteristics (activity, minimum processing times) and an earliest in®nite capacity planning which is communicated to the blackboard. This blackboard can be seen as a virtual Gantt chart representing the current state of the negotiation process at di erent conceptual levels: operations are ®rst associated to activities (drilling, lathe, etc.), then to machines while some operations are de®nitively located whereas others can still be moved.

Like in the Contract-Net, the Machine Agents make bids on the operations o ered by the MO agents. Each bid includes a correction of the processing time according to the capacity of the machine to perform the activity, and suggests a location of the operation. The particularity of the RAMSES approach compared with the classical Contract Net protocol concerns the nature of the bids. In RAMSES, two di erent bids are made by each Machine agent, corresponding to an e ective and potential position.

. E ective position: takes into account all the other operations that have already been placed on the machine, and also all the operations that the machine has o ered to process and which have not yet been accepted by the MO agents. It refers so to a situation in which all the bids in progress would be accepted. . Potential position: obtained by only taking into account the considered operation. All the other bids in progress are considered as being rejected.

Consequently, the e ective position gives the worst proposition of a Machine Agent, while the potential position gives its best possible proposition, subject to deterioration through time if bids in progress are accepted.

Each MO agent compares the di erent bids received from the machine agents to its objectives. The MO agents can accept the e ective positions suggested by the machine agents: in that case, the negotiation process ends. If the e ective position does not give satisfaction, and if the potential position is much better, the MO agent can take the risk to wait, expecting that this potential position will become e ective.

In that purpose, the MO agent makes a new bid on the base of the potential position.

Another major di erence between RAMSES and the Contract-Net is that in the latter, an order is usually planned operation by operation without any competition with the other orders: the processing sequence of the MOs has so a great in¯uence on the result. In RAMSES, MOs are competing with each other for each operation. Other originalities of RAMSES concern the de®nition of the routings, e.g. with the concept of activity which provides more degrees of freedom for negotiation. Finally, a global validation process can be used in order to validate at the same time all the operations of a MO, on the base of the e ective positions suggested by the machines. A graph is built containing the possible choices for performing the operations, and the most favourable path according to the current objectives (mainly duration and cost) can be adopted in a single step. This possibility permits a more global view on the manufacturing process, which corrects the myopia which is often inherent to the Contract-Net approach.

RAMSES has been implemented in C ‡ ‡ on a PC and uses a standard Windows Interface. It is compliant with the CORBA communication standard and can therefore be remotely used through a network.

The modi®cations of RAMSES allowing a Production and Maintenance cooperation are detailed below.

RAMSES II: a production/maintenance multi-agent scheduler 4.1. RAMSES_Maintenance multi-agent system

As stated above, scheduling maintenance activities cannot be directly assimilated to scheduling manufacturing activities. As a ®rst step, a RAMSES_Maintenanc e multi-agent system has so been derived from the RAMSES system. This multi-agent system is dedicated to the schedule of maintenance operations and has required the following changes:

Several types of `maintenance orders' can be planned.

. A preventive maintenance order is characterized by a preferred temporal window, whose de®nition is discussed in Section 5.2. It is associated to one or several maintenance activities de®ning a maintenance routing. Each maintenance activity requires maintenance resources (operators and/or tools). . A condition-based maintenance order is created according to a condition related to the schedule of manufacturing operations (schedule of a soiling activity, schedule of a given sequence of manufacturing activities, etc.). This type of order is not associated to a temporal window and requires the RAMSES_Maintenanc e system to be connected to a RAMSES_Productio n system. . A corrective maintenance order is associated with a machine. It is characterized by an earliest beginning date and composed of one or several maintenance activities. A priority level can also be considered if available. A corrective maintenance order is only planned in the case of reactive scheduling when a machine breakdown occurrence has been reported. It will only be used if the RAMSES_Maintenanc e is connected with a RAMSES_Production , which is also used for executing the schedule.

In an autonomous mode, the maintenance supervisor agent activates the maintenance order agents, which write on the blackboard the announcement concerning the operations they need to perform. The possible maintenance resource agents make bids on these announces with a process similar to the RAMSES_Productio n one.

The main di erence is that the maintenance order agents consider the respect of the temporal windows as performance criteria for assessing the bids and not the due dates like in RAMSES.

RAMSES II: connection of RAMSES_Production and

RAMSES_Maintenance systems A RAMSES II scheduler is composed of several RAMSES_Productio n and RAMSES_Maintenanc e multi-agent systems, which blackboards are actualized during the negotiation process. Each RAMSES_Productio n system represents a workshop, and each RAMSES_Maintenanc e system represents a set of maintenance resources (for instance, a team). Within the Maintenance multi-agent system, a maintenance agent is created for each manufacturing machine. For simpli®cation, we shall illustrate the system behaviour on the case of one production and one maintenance system. Two new types of agents have been added to the system.

. `User agent', in order to allow a direct action of the human user on the scheduling process. The possible actions that can be performed through the user agent concern changes in the rules that de®ne the behaviour of the Machine agents, changes in the objectives of the involved agents or relaxation of di erent types of constraints. The user agent also allows one to describe a disturbance occurring while the schedule is executed. . `Negotiator agent', in charge of the negotiation process. This agent does not have a higher hierarchical position than the maintenance and production agents but aims at accelerating negotiation by gathering the data coming from the two systems. The de®nition of the compromise between the requirements expressed by the maintenance and production agents, contained in the Negotiator, can be modi®ed by the User agent.

When only systematic preventive maintenance activities and manufacturing operations are considered, the negotiation process is performed as summarized in ®gure 2.

. When a manufacturing operation is to be scheduled by a machine agent, a temporal window showing the earliest and latest possible beginning date for the operation is calculated. Details on these temporal windows are given in Section 5. The information is sent to the Negotiator (message À ).

. Negotiator asks the Maintenance agent of the considered machine whether maintenance activities could interfere with the temporal window of the manufacturing operation (message Á ).

. Maintenance agent sends the list of the concerned Maintenance activities with their temporal windows (message  ).

. Negotiator checks whether there is a real con¯ict between the manufacturing and maintenance operations. If a position of the operations allows to satisfy the constraints expressed by the temporal windows, there is no con¯ict, and the Negotiator asks the Machine agent to plan the operation according to this position (message à ).

. If there is a real con¯ict, i. create the Maintenance order, then to calculate its temporal window. Conditionbased maintenance orders can be strict, i.e. no manufacturing operation can be scheduled on the machine before the maintenance operation, or may accept a given tolerance on their positioning. This tolerance is described in the temporal window attached to the condition-base d maintenance order. If the Maintenance order is mandatory, there is no con¯ict since it is planned ®rst. Otherwise, the global negotiation process is performed as explained above.

In the ®rst version of RAMSES II, the temporal windows of the operations have been de®ned as crisp intervals [START_REF] Coudert | Un systeÁ me multi-agents pour la coop-e ration Production/maintenance[END_REF]. The satisfaction provided by the position of a maintenance activity was as a consequence binary: full satisfaction if the operation was beginning within the window, null satisfaction if not. As discussed above, this is not very consistent with the location of preventive maintenance activities, which is subject to preferences, but is seldom mandatory. For instance, it is clear that being early or late by a few hours is not very important for a monthly maintenance operation. A well-known interest of fuzzy logic is to cope with the problem of arbitrary thresholds: we explain below how the system behaviour has been made more realistic by modelling the temporal degrees of freedom of the operations by fuzzy windows.

Modelling degrees of freedom and con¯ict solving in RAMSES II

The idea of de®ning relaxable temporal constraints by fuzzy sets has often been used in scheduling, from [START_REF] Kerr | A job shop scheduling system based on fuzzy arithmetic[END_REF] to [START_REF] Ishii | Scheduling problems with fuzzy constraints[END_REF]. We shall see below how fuzzy temporal windows can be de®ned for due dates, manufacturing operations and maintenance operations. The degree of satisfaction attached to the location of an operation (maintenanc e or manufacturing ) will provide a way to assess a compromise, which is a mandatory condition for an e cient management of the negotiation process.

Fuzzy modelling of a due date

The modelling of the preference associated to the respect of a due date `a' by a fuzzy set was ®rst introduced by [START_REF] Kerr | A job shop scheduling system based on fuzzy arithmetic[END_REF] and it is now a classic in fuzzy scheduling. We have chosen to represent a fuzzy due date satisfaction as described in ®gure 3, expressing that the order may be early … full satisfaction, i.e. • … t † ˆ1 8 t < a † and that a delay becomes progressively unacceptable … satisfaction from • … t † ˆ1 to • … t † ˆ0 for a < t < b † . In ®gure 3, the last manufacturing operation is represented by a hatched rectangle: in that example, the satisfaction of the due date constraint is • … t † ˆ0:3. This type of model is more consistent with the industrial reality than a binary evaluation, but in some exceptional cases the due date can of course remain a crisp constraint (departure of a truck or ship, real just-in-time with the customer, etc.).

Fuzzy modelling of a maintenance operation

According to what has been stated in Section 2.2, the preference attached to the beginning date of a maintenance activity can be modelled by the fuzzy set of ®gure 4. Starting from the centre, the left slope can be interpreted as a decreasing satisfaction due to an early maintenance that increases the maintenance cost. The right slope can be interpreted as a decreasing satisfaction due to a possible loose of reliability. This fuzzy set allows one to assess the degree of satisfaction associated to the position of a maintenance operation: it is, for example, 0.8 for the activity represented by a grey rectangle in ®gure 4.

Fuzzy modelling of a manufacturin g operation

In our opinion, the fuzzy maintenance temporal windows as described above are a quite realistic extension of the classical maintenance windows. Performing a negotiation process requires one to model the degrees of freedom available for each partner: describing the preference attached to the possible location of a manufacturing operation by a fuzzy set is so necessary. The di culty is that RAMSES_Productio n performs a schedule in a way close to list scheduling (when a machine can perform several operations, the machine agent chooses their sequence according to a dispatching rule). Therefore, the system does not de®ne temporal windows for manufacturing operations. Nevertheless, other techniques like analysis under constraints [START_REF] Erschler | Finding some essential characteristics of the feasible solutions for a scheduling problem[END_REF]) perform a schedule by de®ning temporal windows for manufacturing operations, then by propagating these constraints in order to ®nd a feasible schedule. Even if this method is not implemented in RAMSES, we have used the same approach in order to de®ne the temporal windows of the manufacturing operations. The window of the nth manufacturing operation is de®ned by placing the previous operations of the routing as early as possible, and the following ones as late as possible. The time between the end of operation … n ¡ 1 † and the beginning of operation … n ‡ 1 † de®nes the temporal window of operation n. We could have used these crisp temporal windows in RAMSES II, but the consequence would be an imbalance between the maintenance operations, which location could provide a partial satisfaction, and the manufacturing operations which location would only be 0 or 1. What we really need is a way to model to what extent the constraint expressed by the window can be relaxed. Figure 5 shows a way to de®ne this possible relaxation. The hull of the fuzzy set describing the preferred position (i.e. the points for which • … t † 6 ˆ0 † is the period between the ®rst possible beginning of the operation (place À on ®gure 5) and the last possible beginning, i.e. when the operation is set at the latest possible position, denoted Á ).

Consider the slack time of the operation to be planned, de®ned as the time left until its due date minus the sum of processing times of the remaining operations of the MO. To determine what positions give complete satisfaction … i.e. the kernel of the fuzzy set, which is the set of points for which • … t † ˆ1 † , let us share the slack time between the operations to be planned (considered operation ‡ remaining ones). In ®gure 5, three operations plus the considered one remain to be planned. The slack time is divided by 4, and we consider that the beginning of the manufacturing operation to be planned gives full satisfaction if the operation only consumes its portion of slack time. This slack time is equivalent to the free slack time of the PERT method. If the beginning of the operation is outside the kernel of the fuzzy set, the slack time of the following operations is progressively consumed, even if the due date can still be met. This is the equivalent of the total slack in PERT: the satisfaction provided by this location decreases progressively as far as the total slack is consumed. After position Á of ®gure 5, it is not possible anymore to meet the due date: this position is considered as providing a null satisfaction.

If the due date is itself fuzzy, the crisp due date of ®gure 5 is replaced by the last point of the fuzzy due date … point for which • … t † 6 ˆ0 † . If it is not possible to meet the due date (end of last operation > due date), we consider that only an immediate beginning of the operation provides satisfaction: the fuzzy temporal window is then reduced to a point. It can be noticed that the upper boundary of the fuzzy window is crisp since it is given by the ®rst possible location of the operation.

Let us now explain more precisely the negotiation process described in ®gure 2 using these fuzzy temporal windows.

Con¯ict solving through negotiation in the presence of fuzzy temporal windows

First, the maintenance agents must be provided with a method to allow them to detect con¯icts with the manufacturing operation which has to be planned. With the notation shown in ®gure 6, the condition of con¯ict is that

… b1 ‡ L1 > c2 † AND … b2 ‡ L2 > c1 † .
The comparison of the possible location of a maintenance activity or manufacturing operation with its temporal window allows us to assess the satisfaction provided by each position. It is then necessary to de®ne an operator allowing one to aggregate these two degrees of satisfaction in order to assess the quality of the compromise de®ned by these two positions. If we consider as a ®rst step that maintenance and production have the same priority, the choice of an aggregation operator is ®rstly constrained by conditions on limits:

. if the two operations have a fully satisfactory position, the aggregated result should be 1; . if one of the operations has a null satisfaction, the result should be 0.

Taking the average degree of satisfaction does not ®t these requirements, or the maximum operator. The minimum or product operator can be used. The ®rst one has been used here, but other criteria may be de®ned in order to express more complex relationships between maintenance and production (weighted average value, etc.). Multicriteria optimization can also be of interest in order to address this aggregation problem.

Because of this choice, our goal while trying to ®nd an acceptable position for the maintenance and manufacturing activities is to maximize the minimum degree of satisfaction provided by the two positions.

From ®gure 6, we can see the following.

. The manufacturing operation can be performed ®rst without having a null satisfaction of the maintenance activity position if … b2 ‡ L2 < d1 † . In that case, the optimal position is de®ned by a manufacturing operation performed as early as possible (beginning at b2) followed by the maintenance activity … beginning at … b2 ‡ L2 † † . In ®gure 6, the position of the manufacturing operation gives satisfaction with a degree 1, whereas the position of the maintenance activity gives satisfaction with a degree 0.4. . The maintenance activity (denoted MaintAct) can be performed ®rst without having a null satisfaction of the manufacturing operation (ManOp) position if … a1 ‡ L1 < d2 † . Since we want to maximize:

M ˆmin … • … begin ManOp † ,
• … begin MaintAct † † , the best position is obtained when • … begin ManOp † •… begin MaintAct † . The maintenance activity begins in the ascending slope of the fuzzy set of the top of ®gure 6 or in its kernel, whereas the manufacturing operation begins in the kernel of the fuzzy set of the bottom of ®gure 6, or in its descending slope. If the two conditions …… b2 ‡ L2 < d1 † and … a1 ‡ L1 < d2 † † are satis®ed, the two previous solutions must be tested (maintenance ®rst and production ®rst) in order to check which positions provide the best aggregate d satisfaction degrees. If none of the two conditions is satis®ed, one of the positions will be satis®ed with a degree 1, the other with a degree 0. In that case, it is necessary to ask the user whether the maintenance or the production is to be privileged.

Taking into account the capacity of the maintenance resources

Until now, we have implicitly considered that the resources required to perform the maintenance activities were always available, i.e. we have performed a schedule with ®nite capacity on the manufacturing resources, but in®nite capacity on the maintenance resources.

As explained above, several di erent maintenance resources can be available in order to perform a required maintenance activity. In that case, the negotiation protocol shown in ®gure 2 is modi®ed as follows.

. When the maintenance agent identi®es that a maintenance activity is required on a machine, it reacts like a MO agent, i.e. it sends an announcement to the maintenance resources describing the type of maintenance activity and the required temporal window. . Each maintenance resource has its own blackboard, i.e. a virtual Gantt chart showing its periods of occupancy. It can so generate a calendar showing the periods when it can perform the suggested activity. A bid including the calendar of each possible resource is then sent to the Maintenance agent by the Resource agents, which can perform the maintenance activity. . The bid that best ®ts the Maintenance objectives is selected. In this ®rst version, the assessment only concerns the respect of the location of the maintenance activity, then the cost (depending of the resource hourly rate). The resource that has the calendar with the largest intersection with the maintenance window is selected. If several resources have a full intersection, the resource with the lower cost is selected. The test of more complex strategies, e.g. based on multicriteria optimization, is in progress.

The temporal window of the selected resource is sent to the Supervisor, which tries to ®nd the best position for the maintenance and manufacturing operations, according to the earlier detailed protocol.

Examples and results

Examples of schedules

A ®rst example of the result is shown in ®gure 7, which was obtained with 25 MOs using two machines on which nine preventive maintenance activities were performed. The upper Gantt chart shows the planning of the Maintenance team (only one team is considered here), while the bottom Gantt chart shows the schedule of the operations on the manufacturing resources. On this chart, manufacturing operations are represented by coloured rectangles and maintenance operations by hatched ones. The two Gantt charts can be visualized on di erent computers since the negotiation process can be performed through the Net using the CORBA protocol.

The fuzzy sets representing the preference given to the beginning dates of the maintenance operations have been drawn on the upper Gantt chart for clarity, and the degrees of satisfaction provided by the position of each operation are given. It can be seen in ®gure 7 that after the negotiation process, the maintenance activities 3, 4, 6 and 8 have been delayed, while activity 9 is performed earlier than expected. For maintenance activities 1, 2, 5 and 7, it has been possible to ®nd a location allowing one to keep a satisfaction degree equal to 1.

The use of condition-based maintenance operations is shown in ®gure 8. Two operations of 60 minutes and three of 30 minutes have been positioned on the maintenance and manufacturing planning: these operations are conditioned by their following manufacturing activity. Therefore, they stand here for set-up operations. If they are conditioned by their previous operations, they can also model cleaning operations.

A drawback of the method is that the bid and negotiation processes are time consuming. Consequently, the scheduling process is much slower than a classical one. The time needed not only depends on the negotiation, which is speeded up by the presence of the negotiator, but also mainly on the number of resources that can perform an activity (manufacturing or maintenance activity), which all send bids in response to an announcement . This will be shown with the following schedule.

. Manufacturing : 50 MOs, six machines in the workshop, six operations per routing. . Maintenance: 24 maintenance activities, one maintenance activity per day for each machine, one maintenance team.

The time needed to perform a schedule in this example according to the number of activities that can be performed by each machine is shown in table 1. The processor used here is very slow (Pentium 133 MHz), but the increasing power of the processors makes the comparison between the di erent processing times more relevant than their absolute values. Table 1 shows that the time needed to perform a schedule through a Production/ Maintenance negotiation increases exponentially with the number of activities that can be performed on each machine of the workshop. Nevertheless, if the routings do not use the `activity' concept and if no maintenance activity is considered, the time required to perform a schedule remains reasonable and it can be compared with the time taken by market schedulers. The reason is that in this example the MOs alone do not represent an important load for the workshop: when the best machine that o ers to perform an activity is chosen according to the cost and delay objectives, this choice is seldom set into question since most of the orders can be delivered on time. The time needed to perform the production schedule alone increases in that case almost linearly when the number of activities that can be performed by a machine increases.

On the other hand, the manufacturin g activities set new tight constraints. Each time a maintenance activity is in con¯ict with a manufacturing operation, the choice of the machine is set into question if the con¯ict solving does not allow total satisfaction of the two partners. This case occurs very often and, consequently, the management of the degrees of freedom created by the activities makes the processing time increase exponentially. The increase of the processing time can be limited if thresholds are set on the satisfaction degrees of the manufacturin g and maintenance operations, the machine allocation only being set into question if the satisfaction decreases under these thresholds.

Test conditions and results

The interest of a negotiation between Production and Maintenance depends very much on the workshop and routings characteristics, e.g. if the machines do not have an important load, planning the maintenance operation ®rst at their optimal location, then planning the manufacturing operations around these maintenance activities should not make an important di erence with the negotiated schedule. On the other hand, the global satisfaction provided by negotiation increases when real con¯icts occur, which requires that the workshop has an important load and that degrees of freedom do exist. These are the main characteristics having an in¯uence on the interest of negotiation.

. Interval of time between two preventive maintenance activities: a preventive maintenance operation performed once a month is clearly less disturbing than if it occurs twice a day. . Compared duration of the maintenance and manufacturin g activities.

. Degree of freedom existing in the positioning of a maintenance activity, modelled by the hull of the fuzzy sets described in ®gure 4.

Production/maintenance negotiation should be of main interest when maintenance activities are long compared with manufacturing activities and when they are frequently performed. Moreover, the negotiation requires degrees of freedom: as a consequence, the result should be better if su cient degrees of freedom exist on the positioning of the maintenance activities, i.e. if the hull of the fuzzy temporal windows is not too narrow.

To check these assumptions, we have de®ned a set of tests combining di erent categories of the previous characteristics. Three categories have been de®ned for each characteristic, standing for `low', `average' and `important' and they are de®ned as follows.

. Frequency of Maintenance (FM) activities:

. Low: maintenance activity every 4 days. . Medium: maintenance activity every 2 days. . High: one maintenance activity per day.

. Maintenance Duration (MD): each duration is drawn according to a uniform law in the range:

. Low: average duration: . Constraint on Maintenance Operation Positioning (MP): this constraint is low when the size of the maintenance fuzzy window is large, and conversely:

. Low: kernel ˆ120 mn, hull ˆ600 mn.

. Medium: kernel ˆ60 mn, hull ˆ240 mn.

. High: kernel ˆ30 mn, hull ˆ120 mn.

A test denoted `HHM' means for instance that the frequency of maintenance duration is high, the maintenance duration is high and the constraint on maintenance positioning is medium.

When combining these values, some test benches are clearly not relevant, e.g. performing twice-a-day maintenance operations with an average duration of 3 hours sets constraints that are not possible to satisfy and, moreover, which are irrelevant.

Consequently, we have selected the 20 sets of hypothesis described in ®gure 9 among the 27 possible ones.

Finally, for each set of hypothesis, 95 schedules have been performed on di erent workshops, generated as follows.

. Workshop composed of ®ve machines is considered. . Ten routings composed of ®ve operations each have been generated with pre-de®ned processing times associated with each operation. Each processing time has a duration of between 30 and 135 mn. . Forty MOs are generated with prede®ned due dates, each being associated with one of the routings, randomly drawn. To each operation is then associated a resource, randomly drawn among the machines of the workshop.

To compare the Production/Maintenance negotiation with a classical scheduling technique, we have also performed two other schedules for each test:

. one in which production activities have systematically priority on maintenance activities; . the other in which maintenance activities are scheduled ®rst.

We have mainly analysed in the following the lateness of the MOs and the degree of satisfaction provided by the location of maintenance activities.

Figure 9 shows the average lateness of the MOs in the 20 examples according to the three types of schedule performed (the percentage of late orders gives very similar graphs). The lateness of the MOs is of course minimum when production has priority on maintenance (dark front bars) and do not depend on the test conditions which only concern maintenance parameters. When maintenance has priority (white rear bars), it can be checked that the size of the fuzzy window has no in¯uence (maintenance activities are positioned as early as possible): the results are always similar for three consecutive tests. One can also verify that the lateness increases with maintenance frequency and duration. We can also verify in ®gure 9 that negotiation provides intermediate results between priority to maintenance and priority to production. The bene®t for the lateness is not very high in the very tight cases (tests 3±5), but is more important in the `intermediate' tests (tests 6±14). Of course, we shall see below that this improvement is obtained at the price of a less good positioning of the maintenance activities.

Figure 10 shows the average degree of satisfaction provided by the positioning of the maintenance activities. As expected, this degree is equal to 1 when maintenance has priority (white rear bars). Figure 10 shows that the satisfaction of the positioning is drastically improved by negotiation: the average positioning satisfaction on all the tests jumps from 0.3 (priority to production) to 0.85 (compromise). The average satisfaction increases when the constraint on the maintenance activities position decreases (size of the fuzzy window increasing), which is denoted by increasing steps in three consecutive examples. The domain of interest of compromises can be veri®ed by correlating ®gures 9 and 10: on tests 3±5, which denote the most tighten cases, the increase in the maintenance activity positioning requires one to accept an almost maximum lateness of the MOs. On tests that present higher degrees of freedom (e.g. tests 6±14), the increase of MOs lateness remains limited while the satisfaction of the maintenance activities positioning is drastically improved. As suggested by the good sense, negotiation is particularly interesting when each partner has su cient degrees of freedom for negotiation Figures 11a and11b show the distribution of the satisfaction degrees provided by the maintenance activities position in case of priority to production (®gure 11a) and negotiation (®gure 11b). In the ®rst case, the majority of the maintenance activities have a positioning providing a null satisfaction, while almost 85% of the maintenance activities have fully satisfactory positioning in case of negotiation.

Conclusion

The planning of preventive maintenance activities in given time intervals may disturb the schedule of the MOs, but is mandatory to insure the long-term availability of the production system, especially when maintenance activities are often required. These maintenance activities may be performed on the machine itself, but they may also concern tools, changes of baths in thermal treatments or cleaning activities in dirty processes, like painting or o set printing. In that context, the multiagent paradigm may provide an implementation framework allowing one to model the negotiation process between the maintenance and production functions. We have shown here that fuzzy logic provides interesting facilities for modelling the degrees of freedom of the negotiation in a quite natural way. New developments are now in progress in order to de®ne negotiation frameworks for other functions. Two types of cooperation seem promising at this moment: workforce management/production, especially in the context of annualized hours, which is now increasingly more common in France, and inventory control/production. Since the RAMSES II environment can coordinate the schedules of several workshops, the latter gives one the opportunity to address Supply Chain problems with a negotiation point of view, which opens new areas of investigation.

Figure 1 .

 1 Figure 1. RAMSES architecture.

  Figure 2. Cooperation/negotiation between maintenance and machine agents.

Figure 3 .

 3 Figure 3. Fuzzy modelling of the preference attached to the due date respect.

Figure 4 .

 4 Figure 4. Preferred beginning dates for a maintenance activity.

Figure 5 .

 5 Figure 5. Fuzzy temporal window for the beginning of a manufacturing operation.

Figure 6 .

 6 Figure 6. Example of con¯ict between a maintenance activity and a manufacturing operation.

Figure 7 .

 7 Figure 7. Negotiated schedule of preventive maintenance operations.

Figure 8 .

 8 Figure 8. Gantt chart with preventive and condition-based maintenance activities.

Figure 9 .

 9 Figure 9. Average lateness of the manufacturing orders.

Figure 10 .

 10 Figure 10. Satisfaction provided by the positioning of maintenance activities.

Figure 11

 11 Figure 11. (a) Distribution of maintenance activities satisfaction: priority to production. (b) Distribution of maintenance activities satisfaction: negotiation.

Table 1 .

 1 Time needed to perform a schedule.

	Number of activities per machine	Manufacturing	Manufacturing ‡ maintenance
	1	0:00:06	0:01:41
	2	0:00:27	0:08:50
	3	0:00:30	0:19:27
	4	0:00:45	0:30:15
	6	0:01:30	1:26:40

  • d d ˆ60 mn, d min ˆ30 min, d max ˆ90 mn. . Medium: • d d ˆ180 mn, d min ˆ90 min, d max ˆ270 mn. . High: • d d ˆ360 mn, d min ˆ180 min, d max ˆ540 mn.