ارزیابی مبتنی بر برنامه ریزی خطی از دقت هندسی: ارائه استاندارد و سطح برنامه

An application of the linear programming (LP) approach to form and position accuracy assessments based on the minimum zone (MinZ) method is considered. The standard form of the optimization function and constraints using linearized form of the substitute feature is considered. A linearization-caused error is estimated by reference to the second order terms within the Taylor series expansion of the rotation matrix. The acceptable range of the LP-based assessments is defined for some levels of an allowable error. The LP-based assessment for a surface is simulated. Actual measurements show that the LP-based estimations have equal or fewer values in comparison with those obtained by other methods.

A modern 3D metrology employs measurements on coordinate measuring machines (CMM) for observation of actual surfaces [1], [2] and [3]. When one uses these measurements to estimate the accuracy of form and position, the calculation process contains an optimization procedure as a key step of the process. Depending on the type of optimization criterion, two main groups of assessments are applied: least mean square (LMS), and minimax. Until recently, only the LMS-type assessments were applied, but nowadays international and national standards for form and position tolerancing widely use minimum zone (MinZ) for accuracy assessments [2] and [3]. As an example, a comparison of two types of assessments for flatness is given in Fig. 1. The LMS-based assessment ΔLMS is obtained as a sum ΔLMS=Δmax+Δmin of two extreme point deviations from the mean plane (Fig. 1b), while the MinZ-based assessments are calculated as a distance ΔMinZ between the MinZ boundaries (Fig. 1a). Among the typical minimax assessments, such as maximum inscribed, minimum circumscribed, and MinZ, we will consider only the last-listed assessment. When an accuracy of the surface or line is measured, the MinZ is built as follows: a substituted feature (i.e., the feature of the nominal form) is extracted from the measured points; the zone boundaries are built so that all the points of the actual surface lie between or on the boundaries of the zone, and the width of the zone is minimal. Full-size image (24 K) Fig. 1. (a) MinZ-based—and (b) LMS assessments for flatness: 1—actual plane; 2, 3—external and internal boundaries of the MinZ; 4—LMS plane. Figure options It has been known that a procedure of the MinZ construction reduces to a solution of the minimax optimization problem [4], [5], [6], [7] and [8]. Various approaches are known to solve this problem: statistical approach, computational geometry techniques, non-linear programming, linear programming, etc. The Monte Carlo search [9] is a statistical method based on the random selection of variables defining the surface. Because of this random selection, this method requires many sampling points to assure high accuracy. Another statistical approach is described by Yang et al. [10]. Yang et al. used large sets of uniform sample points measured from five machined surfaces and compared the form error using individual points and fitted surfaces obtained through a spatial statistic method. This method takes into account a correlation between spatial coordinates of the sample points. A large number of samples (on the order of 1000) is required to make this method feasible. In the widespread computational geometry technique, specific geometry features are built, such as convex hulls, Voronoi diagrams, and so on. A convex hull algorithm [6], [11], [12], [13] and [14] is based on constructing the minimum polygon that will enclose all the measurement points. For straightness and flatness, Traband et al. [11] presented a method based on the concept of a convex hull of the measurement data. The algorithm for evaluating flatness tolerance based on constructing a 3D convex hull is described by Lee [13]. The overall solution procedure consists of three stages, and the complexity of this method becomes O(N2logN), where N is the number of sampled points. As described by Lin et al. [12], the convex hull in 3D space is a minimum polyhedron that encloses all the given points. To compute this polyhedron, the projection of these points in the XY, XZ, and YZ planes must be first computed. These convex hulls are then merged together to obtain set of vertices for the polyhedron. The procedure for calculating MinZ is reduced to calculating the distance of each point from each of the faces of the convex polyhedron. Samuel et al. [14] developed an algorithm consisting of five steps for function-oriented evaluation of straightness and flatness using minimum and maximum enveloping features. The overall complexity of this algorithm is O(NlogN). The Voronoi diagrams method [9], [15] and [17] is based on collecting the nearest or farthest ‘neighborhood’ for each of the measurement points. The circularity assessment method proposed by Murthy et al. [9] is based on the construction of both the nearest Voronoi diagram and the farthest Voronoi diagram and then finding the intersection of the two. Roy and Xu [16] proposed a computational technique for the cylindricity assessment which is based on measurements of actual cylindrical surfaces in some cross-sections. The 2D MinZ is built for each cross-section using Voronoi diagrams. The axis of the 3D MinZ is obtained by means of an LMS technique, and then the diameters of the tolerance zone are established as a minimum and maximum of the diameters in the cross-section. In this method, it is necessary to have more than three points in each cross-section; therefore, this method cannot be applied if, for example, the measurement points are located along the helical line. Huang [17] used 3D Voronoi diagrams to construct the MinZ for sphericity evaluation. The Voronoi diagram in a 3D space is defined as a bisector plane between two measured points, where any point on plane is of equal distance to each of the corresponding measured points. Non-linear programming [5], [8], [18] and [19] is applied when the problem is formulated as a non-linear optimization problem with respect to the optimization parameters. It must be noted that non-linear algorithms are rather complicated. Wang [5] proposed a non-linear optimization method for the straightness and flatness MinZ evaluation. The computational results show the relatively high performance of the optimization method; however, convergence to local optimal solutions due to the non-convex objective function and computational complexity of the problems will be a critical limitation on its practical use. Radhakrishnan et al. [7] described the application of an iterative cyclic coordinate algorithm to minimax non-linear cylindricity estimation problem. The complexity of this algorithm is shown to be O(N6), where N is the number of sampled points. Choi et al. [8] formulated the construction of the MinZ as a non-linear unconstrained optimization problem and used an iterative search technique to solve it. Orady et al. [19] developed an iterative method for the MinZ evaluation of the cylindricity. The proposed algorithm consists of seven steps, beginning with the fitting by LMS. The LP procedure used in the following papers has well-established advantages over other minimax optimization methods [20], such as a rich variety of effective algorithms and software, fast computing, flexibility with respect to on-line data presentation, etc. These advantages have resulted in many attempts to apply this procedure to accurate assessment of problems [22], [23], [24], [25] and [26]. The principal condition for the application of the LP is the necessity to represent both the optimization criterion and the constraints in linear form. Since size deviations are small in comparison with the nominal dimensions (the ratio of those is in the range of 10−5 to 10−7 for ISO tolerancing grades IT5-IT12), linear presentation of these deviations is a usual process for regular-sized values. The applications of the LP to the MinZ assessment, as discussed by Chetwynd [21], showed that the MinZ evaluation of circle could be approximated as LP problem to be solved numerically by the simplex method. As an example, linearization of the parameters about the origin is known as “limacon approximation” for roundness measurement [21]. A linear approximation of the minimax center estimation problem for roundness assessment is obtained by replacing the Euclidean norm with a block norm by Ward et al. [27]. A simplex search technique proposed by Murthy [9] uses the mean plane obtained from the LMS method as a starting plane. A heuristic search procedure based on the minimum average tolerance was proposed by Shunmugam [28]. The deviations are expressed in the linear form by using the limacon approximation, and the simplex search is again applied to minimize average deviations of some geometric features. An algorithm of optimization by LP was suggested by Turner [23] and completed by Sodhi [24]. Turner described a mathematical-programming strategy for determining part position in assemblies for 2D models. Because manufacturing variations in the part models are always small relative to the nominal geometry, the mathematical formulation of constraints and goals is linearized, and the problem is solved using LP techniques. Analysis of the research dealing with the LP approach for accuracy assessment shows that the following problems must be solved: • The standard linear presentation of the optimization function and constraints must be formulated. • The error caused by using the LP-based assessment procedure must be estimated for an acceptable range of applications. It has been known that both the optimization function and constraints depend on dimensional and positional errors. The determination of positional errors has been widely studied [22], [25], [29] and [30]; however, there is no standard presentation for dimensional errors. Furthermore, despite the sufficient application of LP-based methods to accuracy estimations, there have been no attempts to estimate the error caused by this linearization. The present paper deals with the application of LP for the MinZ assessment. It will be shown that an LP-based method can be applied with a suitable level of accuracy to a majority of the types of geometrical features. To satisfy the requirements of the LP-based method (i.e., the linearity of the constraints and criteria), the variational method [26], [31] and [32] for accuracy computation is applied. According to this approach, correspondence is established between the deviations of size, position, and form, on one hand, and, on the other, three formal operations: the total differentiation of the nominal feature with respect to set of parameters, the small displacement of the nominal feature as a rigid body, and the variation of the nominal feature. Presentation of results of the measurements of the actual surface and the minimax estimation by an LP-based method is carried out as follows: (i) the position error of the point of the actual surface is represented as a linear form with respect to dimensional and geometric errors, and, thus, a vector of unknowns is formed; (ii) conditions describing positions of the measured points relative to the boundaries of the MinZ are formulated: all the measured points must be located between two boundaries of the MinZ; these conditions are represented as a set of constraints for the LP; and, (iii) an objective function for the LP is formulated as a linear form of the unknowns, and the LP procedure is carried out. The LP procedure is represented in terms of the “Mathematica” software system [33] as a minimization problem for a set of non-negative unknowns constrained by set of “larger than or equal to” inequalities. The method may be applied for the broad spectrum of the assessments of the geometrical features (e.g. straightness, flatness, cylindricity, and sphericity). An estimation of errors caused by the linearization of the optimization parameters for the cylindricity assessment is obtained for the three levels of an allowable error (0.27, 1, and 5%). The estimation shows that nominal sizes greater than 1.0 mm, and all tolerance grades up to IT8, are characterized by the linearization-caused error of less than 0.27% of the value of the corresponding tolerance. For nominal sizes greater than 1.0 mm, and for all tolerance grades up to IT16, the linearization-caused error is less than 5% of the value of the corresponding tolerance. Thus, the LP permits the accurate results for regular cases of nominal sizes and tolerance grades.

The LP procedure for geometrical accuracy assessments using the MinZ approach is considered. To satisfy the requirements of the LP-based method, the standard linear presentation of the optimization function and constraints is obtained by application of the variational method for accuracy computation. According to this method, the geometrical error presents in the matrix form as a sum of the small spatial deviations of the rigid body and total differential with respect to dimensional parameters. 2. The important advantages of the LP-based method relating to constructing the MinZ are as follows: a rich variety of effective methods, algorithms, and software; fast computing; building the MinZ independently of the dimensionality of the problem; the one-step optimization, regular achievement of the global optimum, etc. These advantages are demonstrated by examples of measurements of some actual surfaces. As a rule, these LP-based assessments are equal or less than those obtained by the other methods. 3. The estimation of linearization-caused error associated with the LP application has been formulated and calculated. This error is estimated by the second order terms of the Taylor series approximation of position deviations. As an example, the cylindricity assessment for the three levels of an allowable linearization-caused error (0.27, 1, and 5%) is calculated. It is shown that the nominal sizes greater than 1.0 mm and all the tolerance grades up to the IT16 are characterized by the linearization-caused error of less than 5% of the value of the corresponding tolerance. The nominal sizes greater than 1.0 mm and all the tolerance grades up to the IT8 are characterized by the linearization-caused error of less than 0.27% of the value of corresponding tolerance.