Sébastien Briot
email: sebastien.briot@irccyn.ec-nantes.fr

Victor Rosenzveig
email: victor.rosenzveig@irccyn.ec-nantes.fr

Philippe Martinet
email: philippe.martinet@irccyn.ec-nantes.fr

The Hidden Robot Concept: a Tool for Control Analysis and Robot Control-based Design

Keywords: Parallel robots, Control analysis, Robot design

Exteroceptive sensors can be used to estimate the robot pose in order to suppress inaccuracies coming from the accumulation of modelling errors when using the classical control approach. In some cases, it is impossible to directly observe the end-effector. Thus we can replace it efficiently by the observation of the legs directions. However, with such an approach, unusual results were recorded, namely: (i) the possibility of controlling the robot by observing a limited number of legs, and (ii) in some cases, the robot does not converge to the desired end-effector pose, even if the observed leg did. These results can be explained through the use of the hidden robot concept, which is a tangible visualisation of the mapping between the observed leg direction space and Cartesian space. In the present paper, it is explained (1) why the tools used in mechanical design can be efficently applied in control analysis via the use of the hidden robot concept which is, in our opinion, a way to unify the analysis of the mechanical and control performances and (2) why we believe that the hidden robot concept must be used to modify the robot design methodologies in order to include control-based performance indices.

Introduction

Sensor-based control approaches have proven to be more efficient than model-based control approaches when accuracy is required in robotized industrial applications [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF]. The most usual approach is to observe the robot end-effector pose through the use of a camera. However, for some operations, such as the milling of materials, it is not possible to observe the end-effector. An innovative vision-based control approach that can be used on parallel robots has been proposed in [START_REF] Andreff | Vision-based control of a Gough-Stewart parallel mechanism using legs observation[END_REF]. It is based on the fact that parallel robot links are usually made of rectilinar cylindrical rods that can be easily detected in the camera space. The information being acquired through an external sensor, this technique allows to estimate indirectly the pose of the end-effector from it.

Servoing through the robot leg observation was sucessfully applied to several types of robots, such as the Gough-Stewart (GS) platform, the Adept Quattro and other robots of the same family [START_REF] Andreff | Vision-based control of a Gough-Stewart parallel mechanism using legs observation[END_REF][START_REF] Andreff | Vision-based kinematic modelling of some parallel manipulators for control purposes[END_REF].

However, two unexpected results arose from the use of this technique: (1) it was possible to control the robot by observing a number of legs fewer than the total number of legs; this is surprising because in actuator-based control schemes, each actuated leg has to be controlled to fully servo the robot, and (2) in some cases, the robot did not converge to the desired pose, even if all observed leg directions did.

Not only were these two points inexplicable, but other questions arose too: (3) are we sure there are no local minima (for which the error in the observation space is non zero while the robot platform cannot move [START_REF] Chaumette | The Confluence of Vision and Control, chap. Potential problems of stability and convergence in image-based and position-based visual servoing[END_REF]) and ( 4) are we sure that there is no singularity in the mapping between the leg direction and the Cartesian spaces?

Due to the unusual nature of this visual servoing technique, all these points were left unanswered. Indeed, the nature of the mapping was not clearly understood. The answer came only recently, when two of the authors of the present paper proposed the existence of a virtual robot model "hidden" within the controller. This robot presents singular configurations and assembly modes different from the controlled robot, and it is this hidden robot whose properties are being used through the observation of the real robot's leg directions. This proposition was fully demonstrated and validated through experiments in [START_REF] Rosenzveig | A method for simplifying the analysis of leg-based visual servoing of parallel robots[END_REF].

The aim of the present paper is to introduce the generalized concept of hidden robot model and to show why the tools used in mechanical design can be efficently applied in control analysis and how the hidden robot concept must modify the robot design methodologies in order to include control-based performance indices.

Leg observation based control

Cylindrical leg observation and Interaction matrix

The controller proposed in [START_REF] Andreff | Vision-based control of a Gough-Stewart parallel mechanism using legs observation[END_REF] is based on the fact that the robot leg directions c u i (extracted from the projection of the cylindrical link in the image space -Fig. 1) are controlled and that the leg direction velocities can be linked to the platform twist c τ c through the expression (the superscript "c" denotes the camera frame):

c ui = M T i c τ c (1)
where M T i is the (3 × 6) interaction matrix for the leg i.

c n i 1 c n i 2 c n i 1 c n i 2 c u i
Fig. 1 Projection of a cylinder in the image For spatial parallel robots, matrices M i are in general of rank 2 [START_REF] Andreff | Vision-based control of a Gough-Stewart parallel mechanism using legs observation[END_REF]. As a result, for spatial robots with more than 2 dof, the observation of several independent legs is necessary to control the end-effector pose. An interaction matrix M T can be obtained by stacking k matrices M T i of k legs, which leads to:

c u = c ui , c u j , . . . , c um T = [M i , M j , . . . , M m ] T c τ c = M T c τ c (2)

Control

For the visual servoing of a robot, one achieves exponential decay of an error e(s, s d ) between the current primitive vector s and the desired one s d using a proportional linearizing and decoupling control scheme. The visual primitives being unit vectors, it is more elegant to use the geodesic error rather than the standard vector difference, i.e. the error grounding the proposed control law will be e i = c u i × c u di , where c u di is the desired value of c u i . A control is then chosen such that e, the vector stacking the errors e i associated to of k legs, decreases exponentially (i.e. ė = -λ e). Then, introducing

L T i = -[ c u di ] × M T i
, where [ c u di ] × is the cross product matrix associated with the vector c u di , the control law can be derived:

c τ c = -λ L T + e (3)
where L T can be obtained by stacking the matrices L T i of k legs and the upperscript "+" corresponds to the matrix pseudo-inverse.

This expression can be transformed into the control joint velocities:

q = -λ c J inv L T + e (4)
where c J inv is the inverse kinematic matrix of the robot relating the end-effector twist to the actuator velocities, i.e. c J invc τ c = q. It can be proven that the controller can meet numerical issues if:

u i platform base A 0 A 1 A 2 A n A n-1 A n-2
passive joints active joint robot links (a) A general robot leg

u i platform base A 0 A 1 A 2 A n A n-1 A n-2
passive joints active U joint passive PPP chain (b) its corresponding hidden robot leg when the vector u i is observed Fig. 2 A general robot leg and its corresponding hidden robot leg when the vector u i is observed

• the matrix L T is rank deficient: in that case, a null error vector e can lead to a non null platform twist c τ c . This appears if and only if M T is rank deficient. • the pseudo-inverse L T + is rank deficient: in that case, we can meet a local minimum of the controller [START_REF] Chaumette | The Confluence of Vision and Control, chap. Potential problems of stability and convergence in image-based and position-based visual servoing[END_REF] for which the value of the platform twist c τ c is zero while the error e is not. This appears if and only if M T + is rank deficient.

Clearly, only stacking leg interaction matrices (which is usual in the visual servoing community) is not enough and the singularities of the controller must be studied. The rank-deficiency conditions are difficult to analyze, and indeed, the complexity for the formerly studied robots was so high that they were never obtained. It is shown in the next part that they can be analyzed by taking into account that the matrix M T is indeed the inverse kinematic matrix of a virtual robot hidden into the controller.

3 The concept of hidden robot model

How to define the legs of the hidden robots

The concept of hidden robot model comes from the following observation: in the classical control approach, the encoders measure the motion of the actuators and this measure is linked to the forward kinematic problem (fkp) x = H (q), where x represents the platform pose and q the encoder measures; in the previously described control approach, the leg directions are observed. So, in a reciprocal manner, one could wonder to what kind of virtual actuators such observations correspond, i.e. what is the virtual robot hidden below the new fkp x = G (u).

The virtual robot hidden into the controller corresponding to x = G (u) can be described as follows [START_REF] Rosenzveig | A method for simplifying the analysis of leg-based visual servoing of parallel robots[END_REF]. First, the observed links mounted to the platform must be disassembled from the rest of the robot and mounted onto active U joints (Fig. 2). The U joint must be linked to a passive kinematic chain composed of at most 3 orthogonal passive P joints that ensures that the link on which is it attached performs a translation w.r.t. the base frame. This passive chain is also linked to the segments before the observed links so that they do not change their motion. Note that:

• it is necessary to fix the PPP chain on the preceeding leg links because the information given by the vectors u i is not enough for rebuilding the full platform position and orientation: it is also necessary to get information on the location of the anchor point A n-1 of the observed segment [START_REF] Andreff | Image-based visual servoing of Gough-Stewart parallel manipulators using legs observation[END_REF]; • 3 P joints are only necessary if and only if the point A n-1 describes a motion in the 3D space; if not, the number of P joints can be decreased such as in [START_REF] Briot | Minimal representation for the control of Gough-Stewart platforms via leg observation considering a hidden robot model[END_REF]; • when the vector u i is constrained to move in a plane (e.g. for planar legs), the virtual actuator becomes an R joint which must be mounted on the PPP chain.

It should be noticed that, in several cases for robots with a lower mobility, the last joint should be changed so that, if the number of observed legs is inferior to the number of real legs, the hidden robot keeps the same mobility (see [START_REF] Rosenzveig | Minimal representation for the control of the Adept Quattro with rigid platform via leg observation considering a hidden robot model[END_REF]). Moreover, we have presented above the most general methodology, but not the most elegant. In many cases, a hidden robot leg architecture can be obtained such that less modifications w.r.t the real leg are achieved. For example, for the Quattro [START_REF] Rosenzveig | Minimal representation for the control of the Adept Quattro with rigid platform via leg observation considering a hidden robot model[END_REF] made of R-{2-UU} legs for which the parallelogram links are observed ({2-UU} subchain links), the R-PPP chain of the hidden robot leg (which is indeed a{R-PPP}-{2-UU} leg) could be fully-equivalently replaced by a planar parallelogram (Π joint) [START_REF] Rosenzveig | Minimal representation for the control of the Adept Quattro with rigid platform via leg observation considering a hidden robot model[END_REF].

How analyzing the controllability of the servoed robots

The aim of this Section is to show how to use the hidden robots for answering points 1 to 4 enumerated in the introduction of the paper. Point 1: Let us consider a general parallel robot composed of 6 legs (one actuator per leg) and having six dof. Using the approach proposed in Section 3.1, each observed leg will lead to a modified hidden robot virtual leg with at least one actuated U joint that has two degrees of actuation. For controlling 6 dof, only 6 degrees of actuations are necessary, i.e. three actuated U are enough. Thus, in a general case, only three legs have to be observed to fully control the platform dof (e.g. see [START_REF] Briot | Minimal representation for the control of Gough-Stewart platforms via leg observation considering a hidden robot model[END_REF]). Point 2: In many cases, the hidden robot may have assembly modes and singular configurations different from those of the real robot. If the initial and final robot configurations are not included in the same aspect [START_REF] Merlet | Parallel Robots[END_REF], the robot will not be able to converge to the desired pose, but to a pose that corresponds to another assembly mode that has the same leg directions as the desired final pose (e.g. see [START_REF] Briot | Minimal representation for the control of Gough-Stewart platforms via leg observation considering a hidden robot model[END_REF][START_REF] Rosenzveig | Minimal representation for the control of the Adept Quattro with rigid platform via leg observation considering a hidden robot model[END_REF]). Point 3: The interaction matrix M T involved in the controller is the inverse kinematic matrix of the hidden robot (and, consequently, M T + is the hidden robot kinematic matrix) which, is most of cases, is not free of singularities. Thus, finding the condition for the rank-deficiency of M T and M T + is equivalent to find the Type 1 and 2 (also called serial and parallel) singularities of the hidden robot [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF]. Point 4: The robot could converge to local minima if the matrix M T + is rank deficient, i.e. the hidden robot model encounters a Type 1 singularity. For illustrating that section, we have decided to consider the case of the well-known planar 3-RRR robot controlled via the observation of the distal links (links between the passive R joints on each leg). Using the results of previous section, it can be found that its equivalent hidden robot model is a 3-Π RR robot (Fig. 3(a) -grey joints denote actuated joints). Each of its legs is composed of a passive planar parallelogram (Π joint) which is able to maintain constant the orientation of the links B i D i w.r.t. the base and of an RR chain which is mounted on the link B i D i . Forward kinematics and assembly modes. All the solutions to the fkp are at the intersections of the coupler curve (which represents the displacement loci of one platform extremity when one of the leg is disassembled, the actuators of the two other being fixed (see Fig. 3(b)) -for the present robot, the coupler curve is a sextic curve) with the vertex space of the disassembled leg (here, a circle) [START_REF] Merlet | Parallel Robots[END_REF]. Thus, the solutions of the fkp are at the intersection points (which are at most 6 [START_REF] Merlet | Parallel Robots[END_REF]) between the aforementioned circle and sextic curve (Fig. 3(b)). Singular configurations. The Type 1 singularities of 3-Π RR robot appear when one leg is fully streched or folded. Its Type 2 singularities appear when the lines of direction w i (i = 1, 2, 3 -Fig. 3(a)) passing through points C i intersects in the same point (that can be at infinity). Those conditions are different from the Type 2 singular configurations of the 3-Π RR robot, for which they appear when all lines passing through C i of direction u i intersects in one point [START_REF] Bonev | Singularity analysis of 3-dof planar parallel mechanisms via screw theory[END_REF].

u 1 v 1 u 2 v 2 u 3 v 3 w 1 =v 1 w 2 =v 2 w 3 =v 3 A 1 B 2 C 1 A 2 A 3 B 3 B 1 C 2 C 3 E 1 D 1 E 2 D 2 E 3 D 3 (a) 3-Π RR robot kinematics

Rethinking the robot design by using the hidden robot concept

Through the concept of hidden robot, the tools and methodology used in mechanical design -for solving the fkp (e.g. [START_REF] Caro | Singularity analysis of a six-dof parallel manipulator using Grassmann-Cayley algebra and Groebner bases[END_REF][START_REF] Merlet | Parallel Robots[END_REF], etc.), for analyzing the singularities (e.g. [START_REF] Ben-Horin | Singularity analysis of a class of parallel robots based on grassmanncayley algebra[END_REF][START_REF] Merlet | Parallel Robots[END_REF], etc.) -can be efficiently used in control design and analysis. However, this concept can also be used to rethink the design process of robots controlled via the use of exteroceptive sensors: the concept of hidden robot can lead to the definition of control-based performance indices. We want to mention that, even if we have

Detailling

Feedback

Fig. 4 How the hidden robot concept should be taken into account into the robot design process deliberately limit the approach to the leg-based visual servoing of parallel robots, the hidden robot concept can be extended to any types of robots controlled via the use of exteroceptive sensors (e.g. cameras, lasers, etc.) which are observing robot internal motions in order to estimate the robot external properties (end-effector pose).

Figure 4 illustrates that point. The design process is typically separated into four main phases: (1) the specification of the product requirements coming from the need definition, (2) the phase of conceptual design during which concepts are proposed and evaluated, (3) the embodiement of schemes during which the concepts are developed and analyzed, and (4) the detailed design that leads to the CAD drawing and the manufacturing of prototypes. Phases (1) to (3) are obviously linked in order to modify / improve the design solutions in case of feasability issues.

If, for a given application, it is specified that a robot must be controlled via the use of exteroceptive sensors observing its legs, the designer has to know that such a requirement leads to the definition, for any kind of robot architecture, to a generic concept of hidden robot (such as the one in Fig. 2(b) for leg-based visual servoing). Then, during the conceptual design phase, for each proposed robot architecture, the corresponding hidden robots can be defined and their singularities can be analyzed. A feedback can be given to the designer so that he can choose, for example, the robot architectures that have the hidden robot models with the minimal number of singular configurations. If, for any reason, all hidden robots are architecturally singular, the design specifications concerning sensor types and observed elements must be modified (by proposing other sensors, or other observed elements). Then, once the potential architectures are selected, they must be optimized in phase 3. More detailed kinematic models of the robots and of their corresponding hidden robots are defined and used for extracting performances indices (e.g. w.r.t. accuracy), for defining a controller, and simulating the robot behavior. If the results do not meet the design requirements, previous design steps must be conducted again. Finally, during the implementation of the controller in the manufactured prototype, the hid-den robot model equations must be implemented. Our future works will focus on the practical implementation of such a design methodology.

Conclusion

In that paper, it has been shown that some sensor-based control approaches well adapted for servoing parallel robots involve the presence of virtual robots hidden into the controller, which have assembly modes and singularities different from the real robots. The analysis of the robot models hidden into the controllers developped by the sensor-based control community required the use of mathematical tools developped by the mechanical design community. This analysis is crucial to avoid control issues that can arise if interaction matrices are stacked without deeper analysis. It has also been shown that the tools used in mechanical design can be efficently used in control analysis and that the hidden robot concept can be smartly used in the design process of robots in order to include control-based performance indices.

Fig. 3

 3 Fig.3The hidden robot model of the 3-RRR robot and its hidden robot model

This work was supported by the French ANR project ARROW (ANR 2011BS3 006 01).


S Briot

V Glazunov

V Arakelian
email: vigen.arakelyan@insa-rennes.fr

On the Design Conditions of Planar Parallel Manipulators in Near-Singular Configurations

Keywords: design, effort transmission, instantaneous centre of rotation, planar parallel robots, pressure angle, singularities

Singularity is a major problem for parallel manipulators as it causes severe problems: uncontrollable or unstable motions, loss of stiffness, infinite forces/torques in actuated joints, and possibility of a breakdown. Many studies have been devoted to these problems. In particular, various criteria for measuring the closeness to singularities have been proposed. They are based on the limitation of the values of the input force/torque, pressure angle, natural frequency, etc. The present paper expands the previous work by incorporating a new criterion into mentioned problem, which allows the limitation of the reaction in passive joints. For this purpose, a new approach is developed, which shows that for given external force and moment applied on the platform, the reactions in passive joints depend not only on the pressure angle but also the position of the instantaneous centre of rotation of the platform. The developed approach is not only an effective way to reduce computation time but also to give a qualitative and geometrical interpretation of the problem. The suggested procedure for the determination of the reachable manipulator workspace taking into account the admissible reactions in passive joints is illustrated via a planar 3-RRR parallel manipulator.

I Introduction

It is well known that a parallel manipulator at a singular configuration can gain one or more degrees of freedom. Moreover, at such a configuration, it cannot be controlled, and it can have infinite force/torque in actuated joints, as well as infinite reactions in passive joints, leading to a manipulator breakdown. Therefore the singular configurations and the properties of parallel manipulators close to these configurations have been studied. The singularity analysis of parallel manipulators have been carried out from kinematic [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF][START_REF] Basu | Singularity analysis of platform-type multi-loop spatial mechanisms[END_REF][START_REF] Merlet | Singular configurations of parallel manipulators and grassmann geometry[END_REF][START_REF] Zlatanov | Constraint singularities of parallel mechanisms[END_REF][START_REF] Bonev | Singularity analysis of 3-DOF planar parallel mechanisms via screw theory[END_REF], kinetostatic [START_REF] Alba-Gomez | Consistent kinetostatic indices for planar 3-DOF parallel manipulators, application to the optimal kinematic inversion[END_REF][START_REF] Arakelian | Increase of singularity-free zones in the workspace of parallel manipulators using mechanisms of variable structure[END_REF][START_REF] Hubert | Static of parallel manipulators and closeness to singularity[END_REF] and dynamic points of view [START_REF] Nenchev | Dynamic analysis of parallel manipulator under the singularity-consistent parameterization[END_REF][START_REF] Briot | Optimal force generation of parallel manipulators for passing through the singular positions[END_REF][START_REF] Briot | On the dynamic properties of rigid-link flexible-joint parallel manipulators in the presence of type 2 singularities[END_REF]. The task of avoiding singular configurations raises the question of how one has to stay away from singular configurations. From this point of view, different criteria and several approaches have been proposed. The optimization under constraints has been used [START_REF] Pottmann | Approximation in line space: Applications in robot kinematics and surface reconstruction[END_REF] to determine the linear complex that is closest to a singularity. This methodology was applied to describe the instantaneous behavior near singularities [START_REF] Wolf | Investigation of parallel manipulators using linear complex approximation[END_REF]. The optimization under constraints was also adapted in order to generalize the concept of centerof-compliance [START_REF] Lipkin | Geometrical properties of modelled robot elasticity: Part I -decomposition[END_REF][START_REF] Lipkin | Geometrical properties of modelled robot elasticity: Part II -center of elasticity[END_REF]. The dexterity and conditioning indices were also proposed [START_REF] Gosselin | The optimum design of robotic manipulators using dexterity indices[END_REF][START_REF] Gosselin | A global performance index for the kinematic optimization of robotic manipulators[END_REF]. These indices are based on the Jacobian matrix or its "norm", which relate the actuator velocities (efforts, resp.) to the platform twist (wrench, resp.) by the following relations:  t Jq  and T   w J τ

(1) where J is the Jacobian matrix, t the platform twist, q  the input velocities,  the actuator efforts, and w the wrench applied on the platform.

However, it is known that because of the non homogeneity of the terms of the Jacobian matrix, the previous indices are not well appropriated for mechanisms having both translational and rotational degrees of freedom (DOF). Moreover, as they are based on the Euclidian norm of the input vector (|| q  || or |||| being considered equal to 1), while it is clear that each actuator may have a velocity or an effort comprised between a minimal and a maximal value ( i q   [-

max i q  , max i q  ] and  i  [-max i  , max i  ]
, i q  and  i being the velocity and effort of actuator i), they do not take into account the 'technological reality' of the mechanism.

In order to overcome these drawbacks, in [START_REF] Hubert | Static of parallel manipulators and closeness to singularity[END_REF] it is proposed to characterize the force workspace of robots, which is the workspace for which, considering a given fixed wrench applied on the platform, the actuator efforts are always comprised in the interval [

-max i  , max i  ].
However, this workspace depends on the given direction and norm of the external wrench and will change if another wrench is considered. Moreover, for many robot applications, the wrench direction is not known, contrary to its norm. Therefore, in [START_REF] Briot | Optimal technologyoriented design of parallel robots for high-speed machining applications[END_REF], a way to compute the maximal workspace taking into account the actuator effort limitations for a given norm of the external wrench was proposed. This approach is based on the computation of the transmission factors of matrix J -T , which are obtained geometrically through the mapping of a cube by the Jacobian matrix.

The main drawback of the last two approaches appears in the fact that they analyze the mechanism breakdown by considering input torque limitations only. However, it can exist such poses of the manipulator close to the singularity for which the limitations of input torques can be satisfied but where the reactions in passive joints are not admissible. To have a better understanding of this fact, let us consider a simple example. For the planar 5R manipulator close to the singularity (Fig. 1), a small effort w applied on the end-effector will create a large reaction R 1 in the passive joint B. But in this pose, the actuator torques  1 will stay under acceptable values, as it depends only on the small component F 1 of the reaction R 1 .

Thus we see that the limitation of the passive joints' reactions is also an important consideration. It is a complementary criterion for measuring closeness to singularity. The most trivial way to compute the maximal passive joint reactions is to apply the Newton-Euler theorem to the manipulator platform and, by variation of the force vector directions and moment values, to compute the joint reactions. However, this is a complicated way which requires considerably huge computation time.

Therefore, in this paper a new method for obtaining the maximal efforts in passive joints taking into account the norm of the external wrench applied on the platform of planar parallel manipulator is proposed. It will be shown that, for a given ratio between the norm of the external wrench and of the maximal admissible effort into the passive joints, the mechanical breakdown can be avoided if the pressure angle and the minimal distance between the considered passive joint and the platform instantaneous axis of rotation are bounded. The developed approach is not only an effective way to reduce computation time but also to give a qualitative and geometrical interpretation of the problem.

II. A new criterion for evaluation of the passive joints efforts

For any planar manipulator, the forces R i transmitted by the legs through the passive joints linked to the platform (Fig. 2) can be related to the external wrench w T = [f T , m] T (f is the external force, and m the scalar value of the external moment applied on the platform) using the Newton-Euler theorem at any point Q:

3 1 i i    f R and 3 1 T QBi i i m     d R (2) where [ , ] T QBi QBi QBi y x   d
, with x QBi and y QBi are the coordinates of vector QB i along x and y axes. Considering that R i = R i r i , where ||R i || = R i , and applying the Newton-Euler theorem at point B 1 , it comes that:

T T B B B B T R R R                          
, i T T T i i B B i      f (3) 1
r d r being a unit screw corresponding to the direction of the wrench applied by the actuators on the platform.

Matrix A used in equation ( 3) is defined in [START_REF] Gosselin | Singularity analysis of closed-loop kinematic chains[END_REF] as the parallel Jacobian matrix than can be found through the differentiation of the loop closure equations of the robot with respect to the platform coordinates. As a result, this matrix is always invertible if the robot is not in a Type 2 singularity.

The reactions R of the passive joints can be found from (3):

T    R A w, (4
) where matrix A -1 can be expressed in the form:

1       1 2 3 A t t t , with [ , ] T T i i i   t v (5)
where t i is a screw collinear to the twist of the platform expressed at point B i when leg i is disconnected, v i is the translational velocity of point B i , and  i the platform rotational velocity [START_REF] Arakelian | Increase of singularity-free zones in the workspace of parallel manipulators using mechanisms of variable structure[END_REF] (Fig. 2). On this picture, point I 1 corresponds to the instantaneous centre of rotation of the platform when leg 1 is disconnected. Taking into account that A T A -T = I, we obtain: 1 It was shown in [START_REF] Arakelian | Increase of singularity-free zones in the workspace of parallel manipulators using mechanisms of variable structure[END_REF] that the pressure angle of the leg 1, depicted as  1 (see Fig. 2), may be expressed as the acute angle between the directions of vectors r 1 and v 1 . Therefore:

T T   1 1 1 1 f t r v .
1 cos T   1 1 1 1 r v r v , i.e. 1 cos T   1 1 1 1 r v r v (6)
By definition, r 1 is a unit vector. As a result,  

1 1 cos   1 v
.

For a rigid body in a planar displacement, it is known that the norm of the translational velocity v Q of any point Q is equal to the product of the angular velocity absolute value by the distance between Q and the instantaneous centre of rotation of the body (denoted as I). Thus, we have

1 1 d   1 v
, where d 1 is the distance from the platform instantaneous centre of rotation I 1 to point B 1 (Fig. 2).

Developing (4), it comes that:

    1 1 1 1 1 1 ( ) ( ) T T T T B P B P R m m            1 1 v f d f v d f .
For a given norm f of the external force f and a given value m of the external moment, and for any direction of vector f, the maximal value R 1max of R 1 appears when

  1max 1 , 2 2 1 1 1 1 1 1 max( ) 2 c o s m R R f b b m          f 1 1 v v (7)
where b 1 is the distance between the application point of the external wrench, denoted as P, and point B 1 .  1 is the angle between vectors v 1 and

1 1 B P   d .
For a numerical computation of the joint reactions, using (7) could be sufficient, as all of these parameters can be defined via matrix A and the mechanism geometry. But, it will be shown below that we can go deeper in the analysis using the pressure angle  1 and the distance d 1 . These indices will give valuable insights for the effort transmission inside of the mechanism.

Transforming expression (7) taking exp. ( 6) into account, and generalizing the approach to the other legs, we obtain the maximal value R imax of the platform joint reaction at B i (i = 1 to 3) max / cos

i i i i f m d R     ( 8
)
where

  2 1 / 2cos / i i i i i i b d b d     
, d i is the distance between point B i and the instantaneous centre of rotation of the platform when leg i is disconnected,  i is the pressure angle of the leg i, b i is the distance between P and B i , and  i is the angle between vectors v i and i BiP   d (and as a result between vectors B i P and B i I i -Fig. 3), BiP d , v i and  i being defined at (2) and ( 5). It should be mentioned that the distance between point P

and I i is equal to  i d i .
This equation is the basic result of the present paper, which shows that, for a given set of external force and moment applied on the platform, the reactions in passive joints depend not only on the pressure angle but also the position of the instantaneous centre of rotation of the platform. This property has not been rigorously formulated and demonstrated before. It allows not only giving a qualitative evaluation of the kinetostatic properties of the parallel manipulators and reducing the computational time but also disclosing the geometrical interpretation of the problem: from the equation ( 8), it can be shown that the mechanical system under study can be instantaneously replaced by a virtual cantilever attached to the ground at I i (Fig. 3) lying on a virtual point contact at B i , of which direction is parallel to the vector R i . The external force f is applied on the point P of the cantilever.

As  i and d i are criterion used for the kinetostatic design of robots [START_REF] Alba-Gomez | Consistent kinetostatic indices for planar 3-DOF parallel manipulators, application to the optimal kinematic inversion[END_REF][START_REF] Arakelian | Increase of singularity-free zones in the workspace of parallel manipulators using mechanisms of variable structure[END_REF], it is of interest to find their boundaries with respect to some design requirements. In order to avoid the breakdown of the studied joint, technological requirements imply that the admissible value of R i should not be superior to a given value R adm , i.e. max i adm R R 

. Thus, we would like to find  i and d i , i.e. the parameters of the equivalent cantilever system, for which this inequality is respected. Introducing (8) into the last inequality leads to:

  2 1 / 2 cos / cos / i i i i i adm i i f b d b d R m d       . (9)
Please note that, as by definition, f, cos  i , d i and R adm have positive values, a necessary condition for the existence of ( 9) is:

0 cos / adm i i R m d     cos i adm i m d R   . ( 10
)
If not, the left term of (9) will always be superior to R adm . Let us now square the left and right sides of equation ( 9) and multiply them by 2

    2 2 2 2 2 1 1 1 1 1 1 1 2 1 1 2 cos cos ... 2 c o s adm adm f d b bd d R m d m R         (11)
The obtained expression can be rewritten as: 0 ( )

i i p d  , (12) where, 2 ( )
i i i i i i i p d u d v d w    , 2 2 2 cos i adm i u R f    ,   2 2 c o s c o s i a d m i ii v mR bf      , 2 2 2 i i w m f b   .
The inequality [START_REF] Pottmann | Approximation in line space: Applications in robot kinematics and surface reconstruction[END_REF] has different solutions, depending on the vanishing and signs of terms u i , v i and w i . There are three main cases u i > 0, u i < 0 and u i = 0.

Let us consider these cases.

A. u i > 0 u i > 0 implies that cos

adm i f R   .
In this case, the polynomial p i has got two roots but only one corresponds to the real mechanism, i.e. to a solution of [START_REF] Nenchev | Dynamic analysis of parallel manipulator under the singularity-consistent parameterization[END_REF]. The other root is solution of:

  2 2 2 2 2 2 1 1 1 1 1 1 cos 2 cos adm adm f d d R m d m R        (13)
In order to obtain a root of ( 12) with physical values, it is necessary that the condition 2 4 0

i i i v uw   should be respected, i.e     2 2 2 2 2 2 2 4 2 2 cos 2 cos cos ... sin 0 adm i i adm i i i i i R f b m R b f b f f m         (14)
Developing and simplifying, it can be shown that this polynomial in cos  i has roots with real values if and only if:

2 2 2 4
sin 0

adm i i i R b f w   . ( 15
)
For the analysis of this inequality, two following cases must be considered: w i ≤ 0 and w i > 0.

A1. w i > 0

The condition w i > 0 implies that m > f b i . Here, [START_REF] Lipkin | Geometrical properties of modelled robot elasticity: Part I -decomposition[END_REF] has no real roots, i.e. ( 14) is true for any value of  i . Thus, the condition for (9) to be true is that

      1 max , / cos i i adm i d d m R   . ( 16
).
where     2 1 [START_REF] Zlatanov | Constraint singularities of parallel mechanisms[END_REF] 2

i i i i i i d v v uw u     is the root of (12)
solution of (9).

A2. w i ≤ 0

The condition w i ≤ 0 implies that m ≤ f b i . ( 14) is true if its roots are bounded by 2 2 2 cos sin cos

i i i i adm i m fb m R b       (17a) or 2 2 2 cos sin cos i i i i adm i m fb m R b       (17b)
After mathematical simplifications, it can be proven that if (17b) is true, then,

cos i adm i adm m f R b R    . ( 18
)
which is in contradiction with u i > 0. Therefore, the only condition for ( 14) to be true is that 2 2 2 cos sin cos max ,

i i i i adm i adm m fb m f R b R               (19)
However, it can be demonstrated that, for u i > 0 and w i ≤ 0 2 2 2 cos sin

i i i adm i adm m fb m f R b R      . ( 20
)
Thus ( 19) implies that u i > 0, which is true. Then, ( 14) is always true is this section. As a result, the only condition for ( 9) to be true is [START_REF] Gosselin | The optimum design of robotic manipulators using dexterity indices[END_REF].

B. u i < 0 u i < 0 implies that cos adm i f R  
. Introducing this into (9) leads to 0 ≤  i ≤ 1, i.e. the cantilever allows decreasing the applied force f. Here also, two cases should be studied: w i ≤ 0 and w i > 0.

B1. w i > 0

If w i > 0, i.e. m > f b i , from [START_REF] Briot | Optimal force generation of parallel manipulators for passing through the singular positions[END_REF] it can be shown that:

cos cos i i adm i adm i m fb d R R     . ( 21
)
As in section II.B u i < 0, which is equivalent to R adm

cos  i < f, from (21) it comes cos i i adm i fb b R   , thus i i b d  . ( 22
)
If ( 22) is true, the expression of  i at (8) is bounded by

0 i i i i i i i b d d b d d       . ( 23
)
Introducing ( 23) into ( 9), and as m > f b i , it comes that:

    cos i i i i i adm i i i f d b fb f d b m f R d d         . ( 24
)
Thus, cos

adm i f R  
, or equivalently u i > 0, (25) which is impossible in section 2.2.

B2. w i ≤ 0

If w i ≤ 0, i.e. m ≤ f b i , it could be shown after several mathematical simplifications that ( 14) is true if and only if 2 2 2 cos sin cos

i i i i adm adm i m fb m f R Rb        . ( 26
)
Once this condition is achieved, the condition for ( 9) to be true is that

  2 max , cos 2 cos i i i adm i i m b d d R             . ( 27
)
where     2 2 [START_REF] Zlatanov | Constraint singularities of parallel mechanisms[END_REF] 2

i i i i i i d v v uw u    
is the root of ( 12) solution of [START_REF] Nenchev | Dynamic analysis of parallel manipulator under the singularity-consistent parameterization[END_REF].

C. u i = 0

We have to analyze one last case:

u i = 0, i.e. cos / i adm f R   .
Here also, this condition leads to 0 ≤  i ≤ 1, i.e. the cantilever allows decreasing the applied force f. In such a case, the solution of ( 12) is solution of

0 i i i v d w   with   2 cos i i i v f b f m    and 2 2 2 i i w m f b  
. Three cases will appear: v i > 0, v i < 0 and v i = 0.

C1. v i > 0

In this case, max

i adm R R  can be satisfied if and only if   2 2 2 2 cos i i i i i i w f b m d v f bf m       . ( 28
) C2. v i < 0 In this case, max i adm R R  can be satisfied if and only if   2 2 2 0 2 cos i i i i i i w f b m d v f b f m        . ( 29
)
As in section 2.2.1, the condition w i > 0 is not compatible with the fact that u i = 0. For w i ≤ 0:

  2 2 2 0 2 cos i i i f b m f bf m     . (30)
Therefore, if v i < 0, the only condition is that (10) should be respected.

C3. v i = 0

Condition ( 12) can be satisfied if and only if w i ≥ 0. But, as previously, w i > 0 is not compatible with the fact that u i = 0. Therefore, it exist only one possible case, w i = 0, i.e. i fb m  .

In table 1 are summarized all conditions for obtaining

max i adm R R 
. It should be mentioned that for planar parallel robots, the reactions in the other joints that are not linked to the platform can be found using linear relationships with respect to R imax (not detailed here).

Let us now consider an illustrative example.

III. Illustrative example

In this part, it is studied the effort transmission in a 3-RRR parallel manipulator (Fig. 2), with actuated joints located at C i (represented in grey) having the following characteristics:

-points A 1 , A 2 and A 3 and points B 1 , B 2 and

B 3 form equilateral triangles -circumcircle of A 1 A 2 A 3 of radius r b = 0.35 m -circumcircle of B 1 B 2 B 3 of radius r p = 0.1 m -links length l AiCi = l CiBi = 0.4 m
For this robot, it is known that the directions of the forces R i in the passive joints are directed along the vectors A i B i (Fig. 2) [START_REF] Bonev | Singularity analysis of 3-DOF planar parallel mechanisms via screw theory[END_REF]. Moreover, its Type 2 singular configurations appears when [START_REF] Bonev | Singularity analysis of 3-DOF planar parallel mechanisms via screw theory[END_REF]:

the orientation of the platform is equal to 0 or 180 deg, for any position of the platform centre -when the platform centre, for a given orientation , is located on a circle C centred in O of which radius is equal to For 3-RRR robots, it can be shown that the matrix A T expressed at point B i is equal to [START_REF] Bonev | Singularity analysis of 3-DOF planar parallel mechanisms via screw theory[END_REF]:

m fb  i m fb  i m fb  cos i adm f R     1 max , cos i i adm i m d d R           cos i adm f R   N/A 2 2 2 cos sin cos i i i i adm i m fb m R b       ,   2 max , cos 2 cos i i i adm i i m b d d R             v i > 0 v i < 0 v i = 0 v i > 0 v i < 0 v i = 0 cos i adm f R   N/A max , cos i i adm i i m w d R v            N/A N/A cos i adm i m d R   N/A i i d b  , for 0 i  
1 2 3 T m m m             1 2 3 1 2 3 f f f A R R R (31)
with sin cos

T i i i q q       f and, if B i = B 1 then    
                           2 3 f f (32a) if B i = B 2 then         1 2 3 sin 3 cos 0 sin 2 / 3 3 cos 2 / 3 T p T p m R m m R                                  1 3 f f (32b) if B i = B 3 then        
                                   1 2 f f (32c)
The pressure angles and the distances to the instantaneous centre of rotation can be computed using the geometric representation shown in Fig. 2. In Fig. 4 are presented the variations of the joint reactions at point B 1 within the workspace for several platform orientations , for f = 100 N and m = 5 Nm. Indeed, for this kind of robot, it can be shown that the reactions inside of the whole joints of leg i are equal to R i . Therefore studying the value of R imax at B i allows having good information about the force transmission inside of leg i.

It can be observed that, the closer to Type 2 singularities, the higher the joint reaction. Moreover, the lowest values of the joint reactions appear in zones close to the workspace centre.

Let us now compute the force workspaces of the manipulator. The method consists in discretising the workspace using polar coordinates (r, ). For one given angle , the algorithm tests for all rising values of r that the manipulator can support the applied wrench (see table 1). In the case where the manipulator cannot support the applied wrench, the boundary of the force workspace is defined by the previous computational point.

In the following of this example, it is considered that the maximal admissible value R adm of the reactions of the revolute joints should be equal to 200 N in one case, and to 130 N in a second case. The same wrench as previously is applied on the platform, i.e. a force of norm f = 100 N, and a moment of norm m = 5 Nm. The shape of the force workspace, for one given assembly mode and for several values of platform orientation  and of R adm is shown in Figs. 5 and6.

It can be observed that, the smaller , i.e. the closer from the orientation for which the robot is in singular configuration for any position of the platform centre, the smaller the workspace.

V. Conclusions

In this paper has been presented a method that allows computing the maximal efforts in the joints of planar parallel manipulators. Trivial solution of this task could be the calculation of joint reactions for several values of the external wrench. However such a solution is very time consuming and do not give any quantitative or geometrical evaluation of the effort transmission. In the present paper a new approach has been developed, which has shown that for given external force and moment applied on the platform, the reactions in passive joints depend not only on the pressure angle but also the position of the instantaneous centre of rotation of the platform. This is the first time that such a kinetostatic property is rigorously formulated and clearly demonstrated. The obtained results allow expanding the knowledge about the criteria for measuring closeness to singularity and to avoid the mechanical breakdown by exceeding the admissible values of reactions in passive joints of planar parallel manipulators. In this aim, the optimal boundaries for the values of the pressure angle and of the distance to the instantaneous centre of rotation are computed. The 3-RRR robot has been studied as an illustrative example. Its effort transmission has been studied as well as its maximal reachable workspace.

Fig. 1 .

 1 Fig. 1. Planar 5R manipulator close to the Type 2 singular pose.

Fig. 2 .

 2 Fig. 2. Determination of the pressure angle for the planar 3-RRR robot.

Fig. 3 .

 3 Fig. 3. Instantaneous system equivalent to the planar 3-RRR robot platform.

  in Mechanism and Machine Science, Guanajuato, México, 19-25 June, 2011 A12-277

.

  As a result, we will study the effort transmission in the passive joints of the robot in workspaces delimited by circles C..

  i

  Fig. 4. Variations of the joint reactions (in Newtons) at B 1 within the workspace for several platform orientations , for f = 100 N and m = 5 Nm.

  Fig. 6. Constant orientation workspace for several platform orientations , for f = 100 N and m = 5 Nm and R adm = 130 N.

TABLE 1 .

 1 Conditions for limiting the maximal values of the revolute joint linked to the platform. 13th World Congress in Mechanism and Machine Science, Guanajuato, México, 19-25 June, 2011

	A12-277


V Arakelian
email: vigen.arakelyan@insa-rennes.fr

S Briot

S Yatsun
email: jatsun@kursknet.ru

A Yatsun
email: ayatsun@yandex.ru

A New 3-DoF Planar Parallel Manipulator with Unlimited Rotation Capability

Keywords: design, modeling, singularity, 3-DoF planar parallel manipulator, unlimited rotation capability

Most of three-degree-of-freedom (3-DoF) planar parallel manipulators encountered today have a common disadvantage that is their low rotational capability. However, for many industrial applications, by example in automated assembly systems, cutting machines, simulators, or micro-motion manipulators, a high rotation capability is needed. To overcome such a difficulty, this paper focuses its attention on the proposal of a new 3-DoF planar parallel manipulator capable of high rotational capability. Firstly, structure and mobility of the suggested manipulator are discussed. Then the forward and inverse kinematic problems are analyzed, as well as it is disclosed its singular configurations. The shaking force and shaking moment balancing are also considered. The proposed design concept is illustrated by a driven demonstrator which is a first model of the suggested manipulator.

I Introduction

In the search for a suitable means for simulating flight conditions for the safe training of helicopter pilots, the design of parallel mechanisms has been proposed having all the freedom of motion and capable of being controlled in all of them simultaneously. A typical 6-DoF parallel mechanism consists of a moving platform connected to a fixed base by six serial chains called legs or limbs. Due to its parallel structure these manipulators offer the advantages of low inertia, considerable stiffness, large payload to manipulator weight ratio and higher operating speeds. The advantages however come at the expense of a reduced workspace, difficult mechanical design and more complex kinematics and control algorithms. They have been utilized for many practical applications and many researchers have paid attention to the design of these structures. Therefore, a large number of papers place emphasis on the study of 6-DoF parallel manipulators [START_REF] Dasgupta | The Stewart platform manipulator: a review[END_REF], [START_REF] Merlet | Parallel Robots[END_REF]. However, in most of applications, parallel manipulators with less than six degrees of freedom are more useful. These structures can be presented by the following principal groups: (i) 2-DoF translational manipulators [START_REF] Gao | Performance evaluation of two degrees of freedom parallel robots[END_REF]- [START_REF] Da Silva | Integrating structural and input design of a 2-DOF high-speed parallel manipulator: a flexible model-based approach[END_REF]; (ii) planar 3-DoF parallel manipulators [START_REF] Gosselin | The optimum kinematic design of a planar tree-degrees-of-freedom parallel manipulator[END_REF], [START_REF] Foucault | Synthesis, design and prototyping of a tree-of-freedom reactionless parallel manipulator[END_REF]; (iii) spherical 3-DoF parallel manipulators [START_REF] Gosselin | The optimum kinematic design of a spherical three-degree-of-freedom parallel Manipulator[END_REF]- [START_REF] Karouia | A three-DOF tripod for generating spherical rotation[END_REF]; (iv) 3-DOF translational parallel manipulators [START_REF] Clavel | a fast robot with parallel geometry[END_REF]- [START_REF] Caro | Sensitivity Analysis of the Orthoglide, a 3-DOF Translational Parallel Kinematic Machine[END_REF]; (v) 3-DOF parallel manipulators with combined translational and rotational motions [START_REF] Lee | Kinematic analysis of a three-degrees-offreedom in-parallel actuated manipulator[END_REF]- [START_REF] Yang | Synthesis and analysis of a group of 3degree-of-freedom partially decouped parallel manipulators[END_REF]; (vi) 4-DOF parallel manipulators for Schoenflies motion [START_REF] Rolland | The Manta and the Kanuk: Novel 4-DOF Parallel Manipulators for Industrial Handling[END_REF]- [START_REF] Richard | Kinematic Analysis and Prototyping of a Partially Decoupled 4-DOF 3T1R Parallel Manipualtor[END_REF]; (vii) 5-DOF parallel manipulators [START_REF] Jin | Structure synthesis of a class of five-DOF parallel robot mechanisms based on single-open-chain units[END_REF]- [START_REF] Briot | PAMINSA: A new family of partially decoupled parallel[END_REF].

Recent reports indicates that the technology of parallel manipulators has not yet made a substantial impacts for the raison that the complicated nonlinearity of parallel manipulators in design and control is not completely accepted by end users [START_REF] Merlet | An initiative for the kinematic study of parallel manipulators[END_REF], [START_REF] Brogårdh | PKM Research -Important issues, as seen from a product development perspective at ABB Robotics[END_REF]. Thus, many basic problems are still opened in order to obtain an efficient exploitation of these structures. One of the drawbacks of the developed parallel structures is also the limited rotation capability. This problem has been studied in [START_REF] Liu | A new family of spatial 3-DOF fully-parallel manipulators with high rotational capability[END_REF]- [START_REF] Nabat | Parallel robot with articulated platforms: from concept to industrial solution for pick-and-place operations[END_REF] for spatial parallel manipulators but it is not considered for planar parallel manipulators.

The aim of this paper is to propose a new planar 3-DOF manipulator with unlimited rotation capability.

II Description of the suggested manipulator

Let us consider the architecture of the suggested manipulator (Fig. 1). It is composed of three legs. Each leg is composed of two rigid links O i A i and A i B i (i = 1, .., 3). The links O i A i are connected to the base via actuated revolute joints located at axes O i and they are defined by the coordinates q i . The platform of the manipulator is connected with the links A i B i via revolute joints. The difference between the traditional planar 3-RRR manipulator and the suggested architecture is the position coincidence of the axes B 1 and B 2 . In this case, we obtain a structure in which the position ) , ( y x of the centre C of the platform is controlled by a 5R planar manipulator (O 1 A 1 CA 2 O 2 ) and its orientation () by a four-bar linkage (O 3 A 3 B 3 C). Thus, in the presented structure the linear displacements and the orientation are decoupled: the actuators 1 and 2 control the position of the end-effector, and actuator 3 its orientation.

As it is shown in Fig. 1 the axis x 0 is along of the vector O 1 O 2 . The lengths of the elements O i A i are denoted as L 1i . The lengths of the elements A i B i are denoted as L 2i . The dimension of the platform CB 3 is denoted as R. The positions of the base axes O i along x 0 and y 0 axes are denoted as (x Oi , y Oi ), with x O1 = y O1 = y O2 = 0.

Let us consider the geometric models of the manipulator. From the previous description, one can find the loop-closure equations:

i i i i i i     OC OO O A A B B C (1)
from which it comes 1 2 1 2 cos cos sin sin

Oi i i i i BiC Oi i i i i BiC x L q L x x y L q L y y                      (2)
where [x CBi , y CBi ] T represents the expression of vector CB i in the base frame. For i = 1 or 2, [x BiC , y BiC ] T = 0, and

[x CB3 , y CB3 ] T = R [cos , sin ] T .
Rearranging (2) and squaring both sides, we obtain the following system:

    2 2 2 1 1 1 1 1 1 1 2 1 cos sin 0 g x L q y L q L       (3a)     2 2 2 2 2 12 2 12 2 22 cos sin 0 O g x x L q y L q L        (3b)     2 3 3 1 3 3 2 2 3 1 3 3 2 3 cos cos ... sin sin 0 O O g x R x L q y R y L q L             (3c)
more generically it can be written

    2 1 2 2 1 2 cos ... sin 0 i C B i O i i i CBi Oi i i i g x x x L q y y y L q L           (4)

III Inverse kinematics

Developing (4) and factorizing with respect to cosine and sine q i , it comes cos sin 0

i i i i i a q b q c    (5) where   1 2 i B i C O i i a x x x L     (6a)   1 2 i B i C O i i b y y y L     (6b)     2 2 2 2 1 2 i B i C O i B i C O i i i c x x x y y y L L         (6c)
Using the following relationships

2 2 1 cos 1 i i i t q t    , 2 2 sin 1 i i i t q t   with tan 2 i i q t        (7)
(5) becomes

  2 2 0 i i i i i i i c a t bt c a      (8)
Thus, the solutions t i of this polynomial can be found as

2 2 2 i i i i i i i b b c a t c a       (9)
Therefore, for one given position of the end-effector, the inverse geometric model can be found as:

2 2 2 1 2 tan i i i i i i i b b c a q c a                (10)
in which the sign ± stands for the two possible working modes of the leg i.

IV Forward kinematics

Due to the decoupling properties of the robot, the forward geometric model of this robot can be solved in two steps:

1. find the expression of x and y as a function of q 1 and q 2 , using (3a) and (3b);

2. find the expression of  as a function of q 1 , q 2 and q 3 using (3c). Developing (3a) and 3b and factorizing with respect to x and y, it comes

0 x d x y e y f      (11a) 2 2 2 2 2 0 x d x y e y f      (
IMD-123 3   1 2 c o s i O i i i d x L q    (12a) 1 2 sin i i i e L q   (12b) 2 2 1 2 i i i f L L   (12c)
From (11a) and (11b), one can obtain the following relation

2 1 2 1 ( ) ( ) d d x e e y    (13)
Introducing it into (11a) leads to, for 2 1 0

d d   : 2 1 1 1 0 u y v y w    (14)
where

2 2 1 2 1 2 1 ( ) ( ) u d d e e     (15a)   1 2 1 21 1 2 ( ) v d d d e d e    (15b) 2 1 2 1 1 ( ) w d d f   (15c) Solving (14) leads to 2 1 1 1 1 1 4 2 v v uw y u     (16)
in which the sign ± stands for two possible assembly modes of the system composed of legs 1 and 2. Introducing ( 16) into (13) allows finding the position of the end-effector. Then, introducing ( 13) and ( 16) into (3c) and developing leads to

2 2 2 cos sin 0 u v w      (17) where   2 3 1 3 3 2 c o s O u R x x L q    (18a)   2 3 1 3 3 2 s i n O v R y y L q    (18b)     2 2 3 1 3 3 2 2 2 3 1 3 3 2 3 cos ... sin O O w x x L q y y L q L R         . ( 18c
)
Using the following relationships

t t     , 2 2 sin 1 t t    with tan 2 t         (19) (17) becomes   2 2 2 2 2 2 2 0 w u t v t w u      (20)
Thus, the solutions of this polynomial can be found as

2 2 2 2 2 2 2 2 2 v v w u t w u       (21)
Therefore, for one given position of the end-effector, the inverse geometric model can be found as:

2 2 2 2 2 2 2 1 2 2 2 tan v v w u w u                 (22)
in which the sign ± stands for the two possible assembly modes of the platform.

V Singularity analysis

Differentiating (3a) to (3c) with respect to time leads to the following relation:

 At + Bq 0  (23)
where

[ , , ] T x y   t    is the platform twist, 1 2 3
[ , , ] T q q q  q     the vector of the articular velocities, and A and B two matrices of which expressions are 3 0 0

T T i i i T g g g x y m                                             1
                    B q (24b) with [cos ,sin ] T T i i i    r (25a)   3 3 sin m R     (25b)   1 2 sin ii i i b LL q    (25c)
where r i is the direction of the wrench applied by the leg i on the platform, and m i its moment. As a result: 1. the Type 1 singularities appear when b ii = 0, for i = 1, 2 or 3; such relation appear when the segments O i A i and A i C i are located on the same line (Fig. 2) 2. a first case of Type 2 singularities appear when m 3 = 0; such relation appear when the segments CB 3 and A 3 B 3 are located on the same line (Fig. 3a) 3. a second case of Type 2 singularities appear when r 1 is collinear to r 2 ; such relation appear when the segments A 1 B 1 and A 2 B 2 are located on the same line (Fig. 3b) It known that in the case of high-speed motions, the shaking force and shaking moment bring about variable dynamic loads on the frame and, as result, vibrations.

One of the effective means for reduction of these vibrations is the mass balancing of moving links of manipulators. Therefore in the next section the shaking force and shaking moment balancing of the suggested manipulator is considered

VI Balancing

Let us start by shaking force balancing of the suggested manipulator.

A. Shaking force balancing

In order to achieve the dynamic balancing of the suggested manipulator, we first have to ensure that it is force balanced. For this purpose, the masse of the platform could be substituted by two equivalent point masses located at the axes B 3 and C:

3 3 1 1 0 pl pl B pl B S CS C m m L L m                       ( 26
)
where m B3 is the point mass located on the joint axis B 3 ; m C is the point mass located on the joint axis C; m pl is the mass of the moving platform; L B3Spl is the distance of joint centre B 3 from the centre of mass S pl of the platform; L CSpl is the distance of axe C from the centre of mass S pl of the platform. This allows for the transformation of the manipulator balancing problem into a problem of balancing legs carrying concentrated masses. The centre of mass of each leg relative to its base O i (Fig. 1) can be found by the expressions [START_REF] Arakelian | Design of planar 3-DOF 3-RRR reactionless parallel manipulators[END_REF]:

    Si i Si i Si Bi Bi i i Bi x m x m x m x m m m         (27)     Si i Si i Si Bi Bi i i Bi y m y m y m y m m m        ( 28
)
where cos

Si i i x R q  ( 29
)
sin

Si i i y R q  (30) 1 cos ' cos Si i i i i x L q R     (31) 1 sin ' sin Si i i i i y L q R     ( 32
) i i i i Bi L q L x  cos cos 2 1   ( 33
) i i i i Bi L q L y  sin sin 2 1   ( 34
)
m i and i m are the masses of links O i A i and A i B i ; m B1 = m B2 = 0.5 m C ; R i is the distance of the centre of mass i S of the link O i A i from the joint centre O i ; R' i is the distance of the centre of mass i S of the link A i B i from the joint centre A i .

Thus, for the position of centre of mass to remain constant it is sufficient that the coefficients of the variables i q and i  be equal to zero, i.e. '

0 i i i B i m R m L    (35) 1 ( ) 0 i i i i B i m R m m L     (36)
The conditions ( 35) and ( 36) can be satisfied by adding two counterweights on each leg, which produce negative values of radii R and R . After such a redistribution of masses, the centre of mass of the manipulator remains motionless for any motion of links and hence, the manipulator transmits no inertia loads to its base (Fig. 4).

B. Shaking moment balancing

Now that the inertia force balancing is achieved, we have to consider the cancellation of the shaking moment. For the suggested manipulator, the shaking moment balancing is constructively more efficient by inertia flywheel [START_REF] Arakelian | Design of planar 3-DOF 3-RRR reactionless parallel manipulators[END_REF]. Fig. 4 shows the fully force-balanced manipulator and balancing inertia flywheel, which is mounted on the base of the manipulator.

To balance this shaking moment, the inertia flywheel with an axial moment of inertia denoted as I can be used. The angular acceleration of this inertia flywheel driven by a complementary actuator 4 is the following:

/ sh q M I   (37)
It should be mentioned that the axial inertia moment of the flywheel must be selected in such a manner that its rotation with prescribed acceleration will be feasible.

Therefore, the reaction of the balancing inertia flywheel on the frame cancels the shaking moment due to the parallel manipulator. In other words, the actuator, which moves the balancing inertia flywheel with a prescribed angular acceleration q  has a reaction on the frame which is similar but opposite to the shaking moment of the parallel manipulator. Thus, full shaking moment is annulled. The angular velocity ) (t q  and angular displacements q(t) can be determined by simple integration of the obtained values of   t q  . In order to numerically verify the shaking force and shaking moment balancing of the manipulator an ADAMS model was developed and dynamic simulations were carried out.

For the simulations, the geometric parameters used are of the model are those of the demonstrator that is given in section VII. With regard to mass and inertia parameters the following values have been used: m 1 = m 2 = 0,497 kg, m 3 = 0,565 kg, m' 1 = m' 2 = 0,483 kg, m' 3 = 0,620 kg, m pl = 0,210 kg; -I 1 = I 2 = 1,43.10 -3 kg.m², I 3 = 2,08.10 -3 kg.m², I' 1 = I' 2 = 1,32.10 -3 kg.m², I' 3 = 2,73.10 -3 kg.m², I pl = 0,26.10 -3 kg.m²; -R i = 0.5 L 1i , R' i = 0.5 L 2i , L B3Spl = L CSpl = 0.5 R;

In order to cancel the shaking force the counterweights should be added. Their parameters are given by: -L OiCpi = 0.5 L 1i , L AiCp(i+3) = 0.5 L 2i ; -m Cp1 = m Cp2 = 3.06 kg, m Cp3 = 3.68 kg, m Cp4 = m Cp5 = 0.694 kg, m Cp6 = 0.830 kg; where L OiCpi corresponds to the distance between point O i and the counterweights positioned at C pi and L AiCp(i+3) to the distance between point A i and the counterweights positioned at C p(i+3) (Fig. 4); m Cpi is the mass of the counterweight located at C pi .

In Fig. 5 are presented the shaking force and shaking moment before (full black line) and after (dotted black line) balancing. It is observed that, after mass balancing, the shaking force is cancelled while the shaking moment increases. In order to balance the shaking moment, an optimal trajectory planning is introduced into the control of the inertia flywheel using eq. [START_REF] Jin | Structure synthesis of a class of five-DOF parallel robot mechanisms based on single-open-chain units[END_REF]. Taking into account that the axial moment of inertia of the flywheel is equal to 0.02 kg.m², its optimal displacement is presented at Fig. 6. After the use of this optimal planning, the shaking moment is also cancelled (Fig. 7c, grey full line).

VII Demonstrator

In order to better illustrate the proposed concept, a driven demonstrator has been built. The parameters of the manipulator are the following: As 5R robots have the ability to cross the Type 1 singular configurations [START_REF] Campos | Development of a five-bar parallel robot with large workspace[END_REF], it can be shown that any of the workspace points can be attained without crossing of the Type 2 singular configurations presented at Fig. 3b, that are due to the 5R positioning architecture. It should also be mentioned that the Type 2 singularities presented at Fig. 3a, that appear for some specific platform orientations, can be crossed using optimal motion generation [START_REF] Briot | Optimal force generation of parallel manipulators for passing through the singular positions[END_REF].

Taking into account these considerations, it is possible to define the maximal regular workspaces of the robot, for any platform orientation [START_REF] Ur-Rehman | Multiobjective path placement optimization of parallel kinematics machines based on energy consumption, shaking forces and maximum actuators torques: application to the Orthoglide[END_REF], [START_REF] Chablat | The kinematic analysis of a symmetrical three-degree-of-freedom planar parallel manipulator[END_REF]. It is proposed here to characterize the size of two different maximal regular workspaces: a circle and a square. Using some CAD software [START_REF] Bonev | A Geometrical method for computing the constant-orientation workspace of 6-PRRS parallel manipulators[END_REF], it can be shown that, for this driven demonstrator: the maximal inscribed circle is centred in (90, 64.5) mm and has a radius of 105.75 mm -the maximal inscribed square is centred in (90, 85) mm and has a edge length of 170 mm. Finally, it should be noted that for dynamic tests a prototype will be developed with prescribed mass/inertia parameters and optimized control system.

VIII Conclusion

In this paper, the development of a new 3-DoF planar parallel manipulator with unlimited rotation capability was addressed. The advantage of the proposed design concept is the high rotational capability, which can be useful for many industrial applications: in automated assembly systems, cutting machines, simulators, micromotion manipulators. This is a first publication, in which structural and kinematic properties were disclosed, as well as the shaking force and moment balancing. The linear displacements and orientation of the platform is illustrated via a driven demonstrator, which is a first driven model of the manipulator.

Dynamic simulations, optimization and tests, that can perform this design concept will be a next step of this project.

Fig. 1 .

 1 Fig. 1. Kinematic chain of the suggested manipulator.

  11b) where 13th World Congress in Mechanism and Machine Science, Guanajuato, México, 19-25 June, 2011

13th 123 Fig. 2 .Fig. 3 .

 12323 Fig. 2. Example of Type 1 singularities.

Fig. 4 .

 4 Fig. 4. Shaking moment balancing of fully force-balanced manipulator by an inertia flywheel.

2

 2

Fig. 5 .

 5 Fig. 5. Shaking force before (full black line) and after (dotted black line) mass redistribution and shaking moment before (black lines) and after (grey line) balancing by the inertia flywheel. -two circles C 1 and C 4 centred in O 1 , of respective radii equal to L 11 + L 21 and L 11 -L 21 ; these circles represent the extreme displacements of the robot leg 1; -two circles C 2 and C 5 centred in O 2 , of respective radii equal to L 12 + L 22 and L 12 -L 22 ; these circles represent the extreme displacements of the robot leg 2;

Fig. 6 .

 6 Fig. 6. Definition of the optimal angular displacement for the inertia flywheel.

Fig. 7 .

 7 Fig. 7. Motion generation via a driven demonstrator built in the South-West State University of Kursk.

Fig. 8 .

 8 Fig. 8. Maximal reachable workspace of the robot (to scale).

13th World Congress in Mechanism and Machine Science, Guanajuato, México, 19-25 June, 2011 IMD-123

2 1 1 1

Acknowledgments

This research was supported by a grant from Russian National Agency of Innovation.


Issam Mabrouki
email: mabrouki@tcl.ite.mee.com

Gwillerm Froc
email: froc@tcl.ite.mee.com

Xavier Lagrange
email: xavier.lagrange@enst-bretagne.fr

Biased Random Walk Model to Estimate Routing Performance in Sensor Networks

Keywords: Réseaux de capteurs, routage, marche aléatoire, entropie, performance

Les réseaux de capteurs sans fils sont constitués d'un grand nombre de noeuds assujettis à de sévères contraintes en terme d'énergie, de capacité de traitement et de communication. Dans ce contexte, afin de réduire la complexité, un des défis majeurs rencontrés dans ce type de réseau est le calcul des routes et la mise en oeuvre de schémas de routage efficaces tout en minimisant la quantité d'information utilisée sur l'état du système. De nombreux travaux ont étudié ce compromis de fac ¸on qualitative ou grâce à des simulations. Nous proposons un modèle basé sur la théorie de la marche aléatoire pour estimer analytiquement ce compromis en considérant plus particulièrement l'influence du degré de connaissance de l'état du système que possède un noeud sur le temps moyen de collecte dans un réseau de capteurs sans fils.

Introduction

A wireless sensor network (WSN) is formed by a large number of sensor nodes deployed over an extended region. Sensor nodes, usually battery-operated, are simple and cheap, and cannot offer plentiful resource. The routing problem is an important issue to be considered here because it is significantly sensitive to the previous constraints for two reasons. First, searching a large space of possible routes -derived from having a large number of nodes-may prove computationally prohibitive for low complexity devices such as sensor nodes. Second, performing explicit route discovery/repair computations and maintaining explicit state information about available routes at the nodes is costly in terms of complexity and energy. Thus, the selection of a routing scheme depends on the knowledge available at the network nodes and the communication overhead that can be tolerated. Such knowledge provides nodes with a picture of the network that can be exploited to make decisions. There exist different routing approaches in this respect. In centralized approach, each node is provided with full topology information, then the shortest path algorithm can be applied. Large networks with reasonably stable nodes over time, where autonomous nodes do not know the full network graph (e.g., the Internet), require a distributed routing approach. However, this approach induces significant communication overhead, which is problematic for large scale networks with high constraints (e.g., WSN). A localized approach, where nodes make decisions solely based on partial information available from neighbors is rather suitable. These approaches leverage the intuitive idea that the more knowledge is available at the network nodes, the more efficient is the routing scheme but against the complexity and the energy expenditure.

Many research works have addressed this tradeoff but only from a qualitative view or by means of simulations [START_REF] Servetto | Constrained random walks on random graphs: Routing algorithms for large scale wireless sensor networks[END_REF]. In this paper we use the random walk theory to quantitatively estimate the influence of the requisite knowledge on the routing efficiency in WSN. This is motivated by the fact that making appropriate decisions to forward data depends readily on the amount of state information a node holds. Thus, without any state information, nodes would blindly forward data. This results in a packet wandering from node to node until reaching its destination. As analyzed in [START_REF] Froc | Design and performance of wireless data collection networks based unicast random routing[END_REF], the routing problem becomes then a problem of an unbiased random walk taking place on a graph. However, if some state information is available at nodes, the induced random walk would be biased with a favored direction to enhance performance. We consider in this paper the case of a periodic lattice network of finite square cells, each containing two kind of nodes: sensor and sink nodes. We choose this simple structure because it fits well the actual properties of some WSN (e.g., mesh or grid networks) while being useful to incorporate theoretical elements to modelize the impact of the requisite knowledge on the routing efficiency.

0 1 • • • N -1 0 1 • • • N -1 e 1 e 2 1 4 1 4 (1-ε) 2 ε 2 (a)

The Model: Definitions and Notation

Let C denote a finite square cell of size N × N. The envisioned network is then induced by replicating C by rigid translations specified by vectors N m, where m ∈ Z 2 . With a large number of cells, we can assume that the formed network is infinite and hence, it is equivalent to a torus lattice T formed by connecting the opposite ends of cell C. Every node r ∈ T is labeled with (r 1 , r 2 ), where r 1 and r 2 are integers such that 0 ≤ r 1 , r 2 ≤ N -1. At a given node r, let p( r, s) be a nonnegative real such that ∑ s∈T p( r, s) = 1. This defines a transition probability distribution over the nodes of T at fixed r. When a packet reaches node r, the next hop to node s occurs with probability p( r, s). The random sequence of nodes selected this way is a random walk on T, and p( r, s) is called the transition function of the random walk [START_REF] Hugues | Random Walks and Random Environments[END_REF]. By making different assumptions on the topology of the underlying network and on constraints imposed on p( r, s), we are able to explore a large space of possible routing schemes. In particular, let us consider N sink nodes corresponding to the set C of nodes s j = (0, j) where j = 0, • • • , N -1. Set C is called the gathering border. The other nodes are members of S, the set of sensor nodes. The data generated by all sensor nodes are collected by the sink nodes without any specific mapping between sensor nodes and sink nodes. At a given sensor node r, we assume that the next hop occurs only to the 4-nearest neighbors with probability 1 2 (1 -ε) to the right neighbor, 1 2 ε to the left neighbor (0 ≤ ε ≤ 1), and 1 4 to either top or bottom neighbor (Fig. 1(a)). Key probabilities from which main results can be derived are P n ( r, s) the probability of being at node s after n hops, given that a packet has been issued at node r, and F n ( r, s) the probability of arriving at node s for the first time on the nth hop, given that the packet started at node r. They are called the node occupation probability and the first-passage probability respectively. We make use in this paper of the generating function formalism to deal with a sequence {c n } n∈N by capturing all these coefficients into a formal infinite series defined as C(z) = ∑ ∞ n=0 c n z n where the complex variable z is small enough to ensure the convergence of this series. C(z) is called the generating function associated with {c n } n∈N . Thus, we denote the generating functions associated with P n ( r, s) and F n ( r, s) as P( r, s|z) and F( r, s|z) respectively. P( r, s|z) and F( r, s|z) are related to each other according to a classical relation extensively used in random walk theory

P( r, s | z) = δ r s + F( r, s | z) P( s, s | z), r, s ∈ T. (1)
The proof of this relation is based on the law of total probability and can be found in [START_REF] Hugues | Random Walks and Random Environments[END_REF].

Before estimating analytically the influence of the requisite knowledge on the routing efficiency, let us give an interpretation of parameter ε. If H ε denotes the entropy associated with the transition probabilities at a given sensor node, we can then write

H ε = 3 2 -1 2 ε log 2 (ε) + (1 -ε) log 2 (1 -ε)
. However, from information theory, H ε describes how much uncertainty (or knowledge) is carried by a single transition. Therefore, parameter ε can be considered as an estimator of the amount of requisite knowledge available at a given sensor node. Note that for ε = 1 2 , H ε is maximal which corresponds to an equally likely hops. Otherwise, the uncertainty is lower, which corresponds to transitions with a favored direction leading to performance enhancement.

Mean Data Gathering Delay: a Routing Efficiency Indicator

The data gathering delay of a packet issued from sensor node r is the time or the number of hops it takes to reach C where it is trapped. This time is a random variable denoted by D ε ( r). We propose in the following to evaluate E D ε ( r) , the mean data gathering delay, as an indicator of the routing efficiency. For that, let G n ( r) be the probability that a packet issued from sensor node r will be trapped at C on the nth hop. Therefore, in terms of probability notation we have Pr{D ε ( r) = n} = G n ( r). If G( r|z) denotes the generating function associated with G n ( r), E D ε ( r) can be then expressed as

E D ε ( r) = ∞ ∑ n=0 n G n ( r) = ∂G( r|z)/∂z | z=1 • (2)
Let us now make G( r|z) explicit. Using the law of total probability, it can be possible to decompose the event that a packet issued from sensor node r will be trapped at C on the nth hop, which has the probability G n ( r), into the N mutually exclusive events that the packet arrives at the sink node s j for the first time on the nth hop, which has the probability F n ( r, s j ). Thus, we obtain G n ( r) = ∑ N-1 j=0 F n ( r, s j ). The n-dependence can be eliminated from this equation by multiplying both sides by z n and summing over all n. Therefore, we obtain G( r|z) = ∑ N-1 j=0 F( r, s j |z). However, from (1), F( r, s j |z) = P( r, s j |z)/P( s j , s j |z). Since a packet starting from sink node s j never leaves, we have P n ( s j , s j ) = 1 for all n, which leads to P( s j , s j |z) = 1/(1z). Hence, we obtain

G( r|z) = (1 -z) N-1 ∑ j=0 P( r, s j |z).
(3)

Montroll et al. [START_REF] Montroll | Random walks on lattices. continuous-time walks and influence of absorbing boundaries[END_REF] evaluated the discrete Fourier transform of the sequence {P( r, s j |z)} j at points 0 ≤ k ≤ N -1. Remarking that the sum involved in (3) is nothing but the value of this discrete Fourier Transform at the origin (k = 0), (3) can be then rewritten as

G( r|z) = ρ 1 (z) r 1 -ρ 2 (z) r 1 ρ 1 (z) N -ρ 2 (z) N + ρ 1 (z)ρ 2 (z) r 1 ρ 1 (z) N-r 1 -ρ 2 (z) N-r 1 ρ 1 (z) N -ρ 2 (z) N , (4)
where

ρ 1 (z) ρ 2 (z) = 1 ± 1 -4A(z)B(z) 2A(z) and A(z) = z (1 -ε)/(2 -z) B(z) = z ε/(2 -z).
By plugging (4) into (2), the mean data gathering delay can be simplified as

E D ε ( r) = 2 (2ε -1) r 1 -N 1 -( ε 1-ε ) r 1 1 -( ε 1-ε ) N , for ε = 1 2 , 1. (5)
By expanding (5) close to ε = 1/2 and ε = 1, it can be deduced that E D ε ( r) is continuous for all 0 ≤ ε ≤ 1. We retrieve that E D 1/2 ( r) = 2 r 1 (Nr 1 ) and E D 1 ( r) = 2 r 1 respectively. Moreover, note that the value of G( r|z) at point z = 1 equals to unit, which represents the probability that a packet issued from sensor node r is ever trapped by C . This means that the data gathering ensured by the random walk process is certain.

Remark also that E D 1-ε ( r) = E D ε (N e 1r) , which means that the plots of E D ε ( r) and E D 1-ε ( r) as functions of r 1 are symmetric about the axis X = N/2. It suffices then to assume that 1/2 ≤ ε ≤ 1.

Let us now give a physical interpretation of (5). Indeed, if we denote the displacement of a packet issued from sensor node r after n hops by M n ( r), then M n ( r) = ∑ n j=1 H j ( r) where the random vector H j ( r) represents the displacement on the jth hop. Since we have the same transition probability distribution over all sensor nodes, the mean displacement after n hops is given by E M n ( r) = n µ where µ denotes the mean displacement on a single hop. Vector µ represents also the bias of the random walk and can be interpreted as the mean velocity of propagation of a packet. We have µ = 1 2 (1 -2 ε) e 1 . Therefore, we deduce that for 1/2 ≤ ε ≤ 1 the negative direction of the X-axis is favored by the walk. In other word, for 1/2 ≤ ε ≤ 1 packets are attracted by the random walk towards the gathering border. A packet issued from sensor node r travels then the distance r 1 before being trapped by the gathering border with a speed | µ |= 1 2 (2 ε -1), hence, the time required by this packet before being trapped is simply the distance divided by the speed, that is, 2 r 1 /(2 ε -1). This result could be retrieved from the first term of (5).

The impact of the requisite knowledge via the bias on the mean data gathering delay is illustrated in Fig. 1(b). We see that the higher are the values of ε (lower entropy), the lower is the delay. Moreover, it turns out that an attractive bias (i.e., 1/2 < ε ≤ 1) towards the gathering border accelerates the data gathering process whereas a repulsive bias (i.e., 0 ≤ ε < 1/2) backwards the gathering border decelerates the data gathering process. The case of ε = 1/2 (maximum entropy) corresponds to an unbiased walk where no direction is favored. This represents the worst case for the performance of the walk. Note also that for fixed ε such that 1/2 < ε < 1, the mean data gathering delay increases with r 1 until it reaches a maximum value from which it decreases as r 1 increases. This observation can be explained by the fact that with the periodicity property of the torus lattice, the gathering border (X = 0) is replicated to infinity by rigid translations specified by vectors mN e 1 where m is an integer. In particular, the axis X = N corresponds to a line of sink nodes. Hence, when r 1 increases, the attractive effect of the bias is compensated by the farness from the gathering border X = 0 until the nearness from the axis X = N takes away and therefore, the mean data gathering delay goes down again.

Conclusion

In this paper we have related quantitatively the degree of knowledge to the routing performance and we have studied to what extend the state information available at network nodes can be minimized to reduce the complexity while ensuring an efficient routing scheme. This paradigm arises especially in the design of WSN where the localized approach is extensively embraced. With the aid of random walk theory, we have confirmed analytically the intuitive result that the larger the amount of state information, the more efficient the routing scheme. All details of this model will appear in the full version of this paper.

Figure 1 :

 1 Figure 1: (a) Torus lattice T is formed by connecting the opposite ends of the square lattice. Hops are represented by red arrows. (b) Mean data gathering delay as a function of the position r 1 for different values of ε and for N = 15.

Acknowledgments

Authors would like to thank Stéphane Paquelet for helpful discussions about the reduction of complexity in large scale systems.