Elsevier

Mechanism and Machine Theory

Synthesis of workspaces of planar manipulators with arbitrary topology using shape representation and simulated annealing

Abstract

This paper presents a general methodology for the synthesis of the external boundary of the workspaces of a planar manipulator with arbitrary topology. Both the desired workspace and the manipulator workspaces are identified by their boundaries and are treated as simple closed polygons. The paper introduces the concept of best match configuration and shows that the corresponding transformation can be obtained by using the concept of shape normalization available in image processing literature. Introduction of the concept of shape in workspace synthesis allows highly accurate synthesis with fewer numbers of design variables. This paper uses a new global property based vector representation for the shape of the workspaces which is computationally efficient because six out of the seven elements of this vector are obtained as a by-product of the shape normalization procedure. The synthesis of workspaces is formulated as an optimization problem where the distance between the shape vector of the desired workspace and that of the workspace of the manipulator at hand are minimized by changing the dimensional parameters of the manipulator. In view of the irregular nature of the error manifold, the statistical optimization procedure of simulated annealing has been used. A number of worked-out examples illustrate the generality and efficiency of the present method.

Introduction

Workspace synthesis involves determination of the kinematic dimensions of the links in a manipulator for a prescribed workspace. In other words, the desired workspace is given and it is required to find out the dimensions of the linkage such that the locus of the end-effector covers a region that is as close to the desired workspace as possible. There are very few works in literature that deal with the problem of workspace synthesis. Early manipulator synthesis efforts aimed at optimizing the manipulator for the largest workspace with minimum defects like voids and holes. These procedures can be classified as absolute synthesis procedures. Workspace synthesis is basically a relative synthesis problem where a target workspace is desired to be obtained from a given manipulator structure. There are two basic approaches to this problem based on how the target workspace is specified. The first paper to address the problem of workspace synthesis[1] considered the target workspace as a volume represented by a cloud of points and thus can be considered as a region based approach. On the other hand, Ref.[2] considered the target workspace to be given by specifying its boundary which is a curve or a set of curves; this can be regarded as the boundary based approach. In Ref.[2], the boundary was supposed to be a sequence of circular arcs and straight lines which is true for the class of manipulators addressed. For planar manipulators of general architecture, the ones addressed in this paper, workspaces are bounded by higher order algebraic curves which cannot be represented exactly by circular and straight segments. Also, for a manipulator of general architecture, no closed-form relationship between the workspace boundary and linkage dimensions can be expected. Hence, in this paper, the workspace synthesis problem is formulated as an optimization problem as follows: given a curve representing desired workspace and another curve representing the actual workspace of a manipulator, minimize the error between the curves to obtain the optimal dimensions of the linkage. An optimization formulation of the problem raises two fundamental issues:

1.

how to measure the error between two curves; and

2.

what is a good way of altering manipulator dimensions in order to reduce the error.

Studies are available in pattern recognition literature for comparing simple polygonal shapes. The authors of this paper have developed a highly efficient method for determining polygonal approximation of the external boundary of the workspaces of planar manipulators of arbitrary topology[3]. In Ref.[3], it is shown that, with proper choice of parameters, very good approximations can be obtained extremely fast. In this paper we used Ref.[3] for the determination of workspace boundaries as necessitated by the optimization procedure.

A problem closely related to the problem of boundary synthesis of workspace is the problem of coupler curve synthesis. Relevant literature in the area4, 5, 6, 7 of coupler curve synthesis is found to determine the error estimate as a measure of point-to-point distances or area mismatch (Fig. 1). In the workspace synthesis literature, especially in the region based approaches, the error is calculated as the area of mismatch but the objective of the optimization procedure is different. Referring to Fig. 2, let A 1 represent the area which is in B but not in A and A 2 represent the area which is in A but not in B, where A is the desired curve and B is the generated curve. Then, the error can be represented as e=A 1+wA 2 where w signifies the relative importance of these two types of areas of mismatch. Whereas in curve synthesis procedures w=1, giving equal importance to both A 1 and A 2, in workspace synthesis w is set to a large value giving more importance to A 2 than A 1. The objective of workspace synthesis is to achieve a minimal superset of the desired workspace; ideally, A 2=0 and A 1 is minimum. The evaluation of error in that case, is quite difficult although, in the limit, both converge to the same solution (in principle). Moreover, the boundary region of a workspace is normally avoided for task placement. Hence, it can be assumed that the desired workspace is a conservative estimate of a minimal workspace requirement. In that case, the synthesized workspace with simple error measure is acceptable as long as A 2 does not cut into the minimal workspace requirement. Hence, in the present case, synthesis of the workspace which contains the desired workspace is not adhered to.

In the point based approach, determination of the correspondence between the points on the two curves is difficult but essential; otherwise, even curves, apparently in good match, might indicate high error (Fig. 1). In the second approach, computation of the mismatch area between the curves is difficult, because it involves not only determination of all the points of intersection but also identification of the corresponding segments of the curves forming the mismatch areas—classification of the different areas as A 1 or A 2. Moreover, both approaches assume that the desired curve is already so located on the actual area that the initial error is quite low which need not be true in general; the desired and actual curves might lie far apart and in that case the derivative based optimization schemes might fail. Hence, in the present approach a normalizing transformation is performed on both the curves so that they are brought to a conceptually best match configuration before the error is estimated. This concept of normalization reduces the curve synthesis problem to a shape synthesis problem together with a reduction in the number of design variables. Shape has been defined in pattern recognition[11] literature as those aspects of an object that are independent of its size and coordinate system, i.e., those aspects which are invariant under the operations of translation, rotation, scaling and reflection. Designing for shape rather than the actual curve not only reduces the number of design variables[9] but also gives higher accuracy. The number of design variables reduces by four: two for translation and one each for rotation and scaling. Accuracy depends mostly on the method of shape representation used and also on the number of design variables. Although literature on shapes is quite rich, virtually no study is available that uses the concepts for the synthesis of mechanisms or manipulators. All basic mechanism synthesis problems like function generation, path generation and curve generation can be formulated as shape synthesis problems. Ref[10] used the concept of shape for coupler curve classification and clustering and Ref.[9] gave a shape formulation for coupler curve synthesis based on the Fourier descriptor[18]. However, Ref[9] did not consider the problem of best match configuration. It is not enough to get a mechanism that generates a workspace of desired shape, actual matching of the desired and synthesized workspace must be obtained. The above mentioned normalization transformation provides an easy way for finding the best match configuration.

Moment invariants[11] and Fourier descriptors[8] allow representation of shapes as vectors. This paper, however, uses a global property based vector representation of shape, most of the elements of which are easily obtained during the procedure of shape normalization. Representing the shape of the polygonal curves as vectors, error between them can be very easily computed as the distance between the two corresponding vectors. In the following, using distance between two shape vectors as the error measure, and representing key dimensions of mechanisms in vectors, a parametric study of variation of error has been carried out which shows that the error manifold is not very smooth and hence, derivative based optimization schemes cannot be used. Therefore, the statistical optimization procedure of simulated annealing has been used for optimization.

Section snippets

The best match configuration

A curve generated by a mechanism bears a linear relationship with the parameters of the mechanism i.e., if the mechanism as a whole is shifted to some other location, the corresponding points of the present curve and the curve generated by the mechanism are also shifted by the same amount. Similarly, if the mechanism is rotated, the curve is also rotated by the same amount and if the mechanism is scaled up or down, the curve is also scaled up or down by the same amount. Thus, if any linear

Curve normalization

The idea of curve normalization is to bring each one of the curves to a canonical configuration such that a simple matching of this canonically transformed curve gives a measure of the minimum error configuration. The normalization procedure adopted here is based on the fact that every curve has an intrinsic coordinate frame whose origin is at the centre of gravity of the curve and the x-axis is along the major principal axis of the second moment of length of the curve. The idea of

Shape representation with normalized global properties

Although the area mismatch method is conceptually easy to appreciate, computation of the error is difficult. On the other hand, after normalization, the curves lose their original position, orientation and size attributes. Hence, comparing two curves after normalization is equivalent to comparing the shapes of the curves. shape in the above sense is in use in pattern recognition literature. Although there are several methods of pattern matching based on the concept of shape and there are

Vector representation of mechanism parameters

Mechanism parameters are the numbers which determine the actual kinematic dimensions of the links of the mechanism. For simple mechanisms such as a four bar, mechanism parameters are easily obtained as the link lengths. However, when the mechanism contains polygonal links, link length cannot be defined properly. In such cases, some length parameters and some angle parameters are generally provided for ease of construction. Since in our implementation the kinematics is solved by using the

Selection of the method of optimization

The vector representation of geometry of the mechanism makes it easy to alter the geometry by varying these parameters. Any change in these parameters will change the shape of the curve generated by the mechanism (workspace boundary or a coupler curve) which, in turn, will change the distance of the curve from the target curve in shape space and hence the error measure. This parametric relationship between the mechanism and the measure of mismatch makes the task of workspace synthesis quite

Synthesis with simulated annealing

Statistical optimization procedures are most appropriate for systems cluttered with local minima or for systems where objective functions are discontinuous or non differentiable or where the solution space is discrete. In the present application, though in principle the objective function is differentiable, in the absence of an expression for workspace boundary in terms of the mechanism geometry, and given the computational geometric approach for the boundary determination[3], the analytic

Illustrative examples of workspace synthesis

The ideas presented in the preceding sections are applied to different cases in the following examples. The objective of this study is to demonstrate the efficiency of the present approach in terms of speed and accuracy of the synthesis procedure. In the following examples, the term GPSA refers to the synthesis procedure using simulated annealing for optimization and the global property based shape descriptor. The authors have also explored synthesis with a Fourier descriptor for shape

Concluding remarks

The work presented in this paper introduced a novel shape based method for synthesis of manipulator workspaces using optimization techniques. The emphasis of this work has been to achieve a globally optimal solution under the constraints of a kinematically "good" mechanism. The concept of shape makes the comparison of generated and desired workspaces coordinate and scale invariant, and the concept of best match configuration maps the coordinate independent design to the desired configuration.

References (18)

  • et al.

    A discrete-state perspective of manipulator workspaces

    Mech. Mach. Theory

    (1994)
  • C.H. Suh et al.

    Optimal design of mechanisms with the use of matrices and least squares

    Mech. Mach. Theory

    (1973)
  • Y.C. Tsai et al.

    Workspace synthesis of 3R, 4R, 5R and 6R robots

    Mech. Mach. Theory

    (1985)
  • C.M. Gosselin et al.

    The synthesis of manipulators with prescribed workspace

    ASME J. Mech. Des.

    (1991)
  • D. Sen, T.S. Mruthyunjaya, A computational geometry approach for determination of boundary of workspaces of...
  • F. Freudenstein et al.

    Synthesis of path-generating mechanisms by means of a programmed digital computer

    Trans. ASME J. Engng. Ind.

    (1959)
  • A.J. Nechi

    A relaxation and gradient combination applied to the computer simulation of a plane four-bar chain

    Trans. ASME J. Engng. Ind.

    (1971)
  • H. Nolle

    Linkage coupler curve synthesis: a historical review-III. Spatial synthesis and optimization

    Mech. Mach. Theory

    (1975)
  • C.T. Zahn, R.Z. Roskies, Fourier descriptors for plane closed curves, IEEE Trans. Comp. C-21(3) (1972)...

There are more references available in the full text version of this article.

Cited by (30)

  • A new design methodology for four-bar linkage mechanisms based on derivations of coupler curve

    2016, Mechanism and Machine Theory

    Because only the distance between the generated trajectory and target is calculated, TE cannot represent the velocity of the coupler point. Other indexes such as mismatch area error [23] and structure error [24] also cannot represent the velocity of the coupler point. Therefore, we defined the GT index, which can represent the shape and velocity simultaneously for objective comparison.

  • Comprehensive closed-form solution for the reachable workspace of 2-RPR planar parallel mechanisms

    2014, Mechanism and Machine Theory

    The 3-PRRR and 3-DOF mechanisms are other types of planar parallel mechanisms which have been previously investigated [9–13], but the workspace solution is mechanism specific and cannot be generalized to other cases. The workspace solutions of other notable planar parallel mechanisms also either provide numerical solutions to the workspace of their mechanism [14–21] or are unable to solve non-symmetric identical kinematic chains [22]. Although a myriad of workspaces for different types of planar mechanisms have been previously investigated, to the best knowledge of the authors, no analytical or mathematical closed-form solution to the boundary of the RW of 2-RPR planar parallel mechanisms has been presented.

  • Shape optimization for path synthesis of crank-rocker mechanisms using a wavelet-based neural network

    2009, Mechanism and Machine Theory

    We therefore adopted the simple but effective technique for this task proposed in [27]. Given that a bounding unit square for each normalized curve has been determined by following the normalization procedure proposed in [10], we apply the method proposed by Wunsch and Laine [27], that consists of always taking the starting point of the path to be the contour point that is closest to the bottom left corner of the square. In this way, the input angle parameter representing the starting point is eliminated.

Arrow Up and Right View all citing articles on Scopus
View full text

Copyright © 1998 Elsevier Science Ltd. All rights reserved.