外文翻譯--自動夾具在三維中的合成-17頁[中英word]【中英文文獻譯文】,中英word,中英文文獻譯文,外文,翻譯,自動,夾具,三維,中的,合成,17,word,中英文,文獻,譯文 AUTOMATIC FIXTURE SYNTHESIS IN 3D Kamen Penev Programmable Automation Laboratory Computer Science Department and Institute for Robotics and Intelligent Systems University of Southern California Los Angeles, CA 90089-0781Aristides A. G. Requicha Programmable Automation Laboratory Computer Science Department and Institute for Robotics and Intelligent Systems University of Southern California Los Angeles, CA 90089-0781 ABSTRACT A fixture is an arrangement of fixturing modules that locate and hold a workpart during a manufacturing operation. In this work we. consider fixtures with frictionless point contacts and present a method for placement of contact points on a non-prismatic 3D workpart. It is a non-deterministic, potential field algorithm for contact point placement. The method provides a basic framework for the integration of heterogeneous high-level fixturing agents through an interface based on zones of attraction and repulsion on the workpart boundary. The algorithm may produce redundant fixtures, and can augment partial solutions to complete form closure fixtures. 1. INTRODUCTION A fixture is an arrangement of fixturing modules that locate and hold a workpart during a manufacturing operation, such as machining, assembly and inspection. Fixturing is of essential importance to industrial manufacturing and constitutes a significant part of all manufacturing costs. Therefore, fixture design automation is very important. Fixture design involves a great variety of considerations, such as restraint, deterministic location, loadability, and tool accessibility. Efficient algorithms that address the whole range of fixturing issues for a comprehensive domain of workparts do not yet exist. Recently, Brost and Peters published an algorithm [Brost & Peters 1996] that extends the earlier classic work of Brost and Goldberg [Brost & Goldberg, 1994] to the 3D domain. This algorithm, however, requires vertical and horizontal planar surfaces to constitute a substantial part of the workpart boundary. It generates all possible fixtures and then rates them accordingly to certain metrics. This is computationally expensive. Wagner et al presented an algorithm that uses seven modular struts mounted in a box to fixture polyhedra [Wagner et al 1995]. This algorithm is not complete in the sense that it cannot effectively handle certain cases, such as a cube with faces parallel to the box. It also suffers from high computational complexity. Wallack and Canny suggested another method with an “enumerate-and-rate” flavor [Wallack & Canny 1996]. It can fixture prismatic workparts with planar and cylindrical vertical surfaces. Ponce proposed an algorithm that utilizes curvature effects to compute fixtures with four fingers for polyhedral parts [Ponce 96]. The reduced number of contacts should provide for better complexity of this algorithm, but the quality of the produced fixtures seems to be inferior to the ones that utilize more contacts and provide classical form closure. In this paper we present a new potential-field algorithm that efficiently produces quality fixture designs. Our algorithm works for arbitrary workparts and provides convenient universal means for representing various fixturing requirements. This algorithm is a direct generalization of the 2D potential field fixturing algorithm of Penev and Requicha [Penev & Requicha 1996]. We consider fixtures with frictionless point contacts. It has been proven that seven contacts are necessary1. [Somoff, 1900] and sufficient [Markenscoff et al, 1990] to immobilize any workpart2 in 3D Following a least-commitment strategy, the process of fixture synthesis may be separated into three stages – fixturing task analysis, contact point placement, and fixture layout design. In the fixturing task analysis phase the workpart geometry and manufacturing process are analyzed to identify various parameters of the fixturing problem, such as cutting forces, inaccessible or forbidden areas, and also to find features that may be useful for applying fixturing devices, such as machined flat surfaces, horizontal and vertical surfaces, pairs of parallel surfaces, pairs of perpendicular surfaces, etc. Figure 1: Contact point placement In the contact point placement phase a number of contact points are placed on the workpart boundary (Figure 1), so that the resulting configuration of contacts satisfies the constraints identified in the analysis phase as well as certain kinematic requirements that must be satisfied by any fixture, such as total restraint. ba Figure 2: From contact point configuration to fixture layout design In the layout design phase “towers” of fixturing components are built and placed around the workpart so as to contact the part at the point locations computed in the contact point placement phase. For example, a contact point on a horizontal workpart surface (Figure 2a) may lead to the instantiation of an overhead clamp that contacts the workpart at that particular point (Figure 2b). This is a design-for-function problem constrained by the set of available fixturing modules and their parameters. The set of contact points are the functional specification and the fixture layout is a configuration of components that achieves it. In this research we focus on contact point placement and its integration with part and task analysis. An arrangement of contact points must satisfy certain kinematic conditions in order to be a basis for a good fixture. In particular, it must provide form closure, deterministic location, clamping stability, detachability and loadability [Asada & By]. The algorithm uses a discretization of the workpart boundary, similar to the meshes used in FEA. However, unlike FEA, our attention is on the mesh nodes, rather than on the mesh elements. Discretization was chosen for the following reasons: First, we can handle workparts with arbitrary geometry, as long as the part’s boundary is a collection of smooth surfaces which we know how to mesh. This requirement is satisfied by all surfaces used in modern CAD systems. Second, discretization is necessary in order to avoid an expensive computation of geodesic curves. Third, discretization should not significantly affect the results, as long as the number of discrete candidate locations on the boundary is much larger than the number of surfaces. In our implementation the discretized boundary consists of several hundred points only. Experimental evidence indicates that this is sufficient for realistic workparts. We introduce a potential field on the workpart boundary defined by zones of attraction and repulsion, which we call P-zones. The contacts are modeled as charged particles that move on the boundary driven by this potential field. The contacts are also subject to mutual repulsion based on the distance between each two contacts in the wrench vector space. The algorithm executes a series of simulation epochs. Each epoch starts with a random configuration, proceeds through a certain number of steps toward lower potential energy and ends with a test for kinematic conditions (form closure). The algorithm terminates when an epoch produces satisfactory configuration. To spread the contact points on the boundary we simulate repulsion between each pair of them. The intensity of repulsion between two contact points depends on the distance between their corresponding wrenches in the wrench vector space. Our simulation proceeds in a limited number of steps or until equilibrium is reached. The resulting placement should have a good chance of leading to a good fixture. Such a randomized method assumes that the set of n-tuples of contact points (for n greater than three) that satisfy the kinematic requirements has measure greater than zero and is relatively large. That is, the solution space is large. Although we have not been able to prove this hypothesis mathematically, our experiments have confirmed it. Moreover, the measure increases with the number of contact points, e.g. it is easier to find a form closure arrangement with eight points than with seven. The notion of repulsion is essential in our method as it allows other considerations to be accommodated easily. We can put additional repulsion spots on the workpart boundary to represent forbidden regions. We can also introduce centers of attraction. These correspond to areas that were recommended by the analysis phase as desirable for placing contact points, e.g. datum surfaces. Thus, we propose a potential field for uniformly representing heterogeneous fixturing information. Regions of repulsion correspond to areas with positive potential. Negative potential is associated with attraction. Zero potential corresponds to neutral areas. The initial randomly selected contact points are regarded as particles that are being attracted or repelled by a potential field that includes a pairwise repulsion. The goal of the system of contact points is to minimize its total potential energy. 2 THE INPUT The input to our algorithm consists of CAD models of the workpart boundary and a set of solid P-zones. Each P-zone defines a potential-field influencing region with non-zero charge. 3 DISCRETIZING THE WORKPART BOUNDARY The first step in our method is to discretize the boundary of the workpart, thus creating the candidate contact point locations which we call nodes. Discretization is done by invoking a standard faceter embedded in the geometric modeler we use. The discretization is stored in an oriented graph data structure. Each node of the graph corresponds to a node on the mesh. The edges of the graph correspond to edges of the mesh connecting neighboring nodes. At each node the screw representing the point contact is computed and stored. A screw is a concise and convenient representation of the surface normal and the location of the node. It is used in all kinematic tests based on screw theory. 4 COMPUTING THE POTENTIAL FIELD The contact points in our algorithm are subject to the combined action of two components forming the potential field. The background potential field is one of these components. It is generated by the P-zones and does not depend on the location of the contact points. The background potential field is computed only once, in the beginning of the algorithm. The other component is dynamic and is due to the repulsion between the contacts. The dynamic component is computed at each epoch. The computation of the background potential field proceeds as follows: First, we find all nodes that lie inside P-zones. We perform membership classification of each node against each P-zone [Tilove 1980]. If the node is inside a certain P-zone, the charge of the P-zone contributes to the node’s charge. The contribution may be positive or negative, depending on the sign of the zone’s charge. After this procedure the nodes that classify outside all P-zones remain with zero charge. If a node m classifies inside P-zones z1, z2... zk its charge Cm equals the sum of the charges of those P-zones: Cziki??1 After the charge of the nodes inside P-zones is evaluated we proceed by computing the potential of all nodes. We define the potential at a charged node to be initially equal to its charge Pm=Cm. For each charged node m with charge Cm we perform a breadth-first traversal of its neighbors updating their potential according to the formula：??Pdnn?????????1210, Here d(m,n) is the distance between nodes m (the charged node) and n, and d0 is a constant called distance of influence. The distance between two nodes is defined as the number of edges on the shortest path between them on the mesh boundary approximation (Figure 3). n m d(m,n)=7 Figure 3: Distance between two nodes on the mesh Assuming the mesh satisfies certain common quality requirements, this distance approximates quite well the actual geodesic distance between two points on the object’s boundary. The breadth-first traversal goes only d0 nodes deep. Thus a charged node causes updates of the potential only in its d0-neighborhood. For example, if the three dark nodes in Figure 4 have charge 100 and d0=3 the potential in this part of the mesh will be as shown by the numbers next to each node. 0 0 0 0 0 0 0 0 0 8 8 16 16 16 16 16 8 8 8 8 8 16 8 8 74 74 74 49 49 49 49 16 16 16 49 49 Figure 4: Potential field generated by three charged nodes The dynamic potential represents repulsion between the contact points. The repulsion between two contacts depends on how distant their corresponding screws are as 6- dimensional vectors: ??Pmnn(,)(,)?????1142? Here ? is a small number to avoid division by zero, ? is a scaling factor that makes the dynamic potential compatible with the background component, and ?(m,n) is the Euclidean distance between the screws at nodes m and n. The rationale behind repulsion based on screw-distance is the following: A necessary and sufficient condition for form closure is that the set of contact screws positively spans the entire R6 [Wagner et al. 1995]. As the contact screws repel each other, they will tend to distribute regularly in the space, thus increasing the possibility of form closure. 5 EPOCHS Each epoch starts with a random initial placement of contact points. Then these contact points are subjected to the combined forces due to the background potential field and the repulsion between the contact points themselves. The algorithm proceeds in an iterative fashion. First, the dynamic component of the aggregated potential field is computed accordingly to (3). The dynamic potential is computed only at the contacts and their immediate neighbors. After the combined potential is computed, each contact is moved to the neighbor node with the lowest potential. Thus a step is completed. If the number of steps has reached a certain limit, or no contact was moved (i.e. equilibrium has been reached), the epoch is completed. Throughout this process special attention is paid to nodes that lie on edges and vertices of the workpart. These nodes do not have a screw associated with them as there is no normal defined there. Therefore, they cannot be a possible contact location. Instead, they serve merely as transit nodes in the simulation. This is achieved by always considering the neighbors of such a node whenever the node itself is addressed. The net result of an epoch is that the initially random configuration transforms into one that has more regular distribution of contact screws in the screw vector space, while at the same time keeping away from repulsion zones and providing contacts inside attraction zones. 6 TEST In the test phase we check whether the placement of contact points provides form closure. This is done using the method of Chou et al. [Chou et al. 19??] It tests whether there exists a non-zero motion screw that complies with the constraints imposed by the contact wrenches: ????swiCi?01? The existence of s is tested using linear programming techniques. If no such motion exists the arrangement of contacts provides form closure. If the test succeeds the algorithm terminates. Otherwise a new epoch is initiated. If the test fails and a certain number of generations have been tried we increase the number of contact points C. Increasing C improves the probability of ending up with a form closure configuration as well as having more contacts in P-zones of attraction. The algorithm ensures that no two contact points are placed on the same mesh node. Therefore, in the extreme case there are three contacts on each face. Such a placement obviously immobilizes any polyhedral part. Hence the completeness of the algorithm (at least for polyhedral parts). After a redundant form-closure configuration is computed, the algorithm can remove the extra contacts in the order of decreasing background potential, i.e. starting with the ones in P- zones of highest repulsion. Redundant fixtures are sometimes preferred, as they minimize part deflection and vibration. The system can operate with or without redundancy reduction. The decision might be guided by the analysis phase based on the geometric shape of the part and the magnitude of the external forces, or a human operator may allow redundancy manually and even force it by setting the initial number of contacts to be more than the theoretical minimum (7 in 3D). It is possible for the kinematic test to succeed, but the potential at some contacts to be high. This can happen if a contact is trapped in a local minimum of the potential field where the potential is high. To handle such situations we introduce a threshold parameter called maximum allowable potential. Arrangements with potential at any contact higher than the threshold are discarded. This new test may lead to situations in which the algorithm does not terminate because no fixture exists with sufficiently small potential. (Imagine the extreme example that the entire workpart boundary is a forbidden region.) Therefore, we limit the number of epochs to ensure termination. In the case of such termination the algorithm outputs the solution with the lowest maximum potential. 7. DISCUSSION The proposed algorithm solves the essential problem in fixture design – placing contact points on the workpart that provide form closure. It can be incorporated in a complete fixture design system that provides modules for fixturing task analysis and layout design. The algorithm provides a simple, but powerful interface to the fixturing task analysis modules based on zones of attraction and repulsion. Admittedly, not every contact configuration can be implemented by a certain fixturing toolkit in the layout design phase. It may be necessary to invoke the contact placement algorithm several times until a feasible configuration is produced. 7.1 Fixturing Task Analysis Various fixturing heuristics and requirements can be expressed in terms of zones of higher attraction or repulsion. For example, attraction zones may be used to represent: ? datum surfaces ? machined surfaces ? surfaces with “good” orientation ? areas with good accessibility ? areas that need additional support to prevent deflection and deformation Repulsion zones can represent: ? inaccessible areas ? forbidden areas due to tool accessibility requirements ? surfaces with poor orientation ? cast surfaces ? sensitive surfaces that are vulnerable to scratching etc. An important open problem is how to assign numerical values to the P-zone potential. One possibility is to classify the constraints into a small number of categories, e.g. “strong repulsion”, “repulsion”, “neutral”, “attraction”, “strong attraction”. All constraints within the same category are assigned the same potential. While such a scheme does not reflect subtle differences in priorities of the fixturing constraints, it will probably capture the most important ones. 7.2 Fixture Completion An important property of the algorithm is that it allows partial fixtures to be input. Partial fixtures may be produced by other fixturing agents, humans or computer programs, who place certain fixels they know are necessary and hand the work over to our algorithm for completion. The algorithm then places additional contacts so that form closure is achieved. We represent the partial fixture as fixed contacts which participate in the mutual repulsion with the free contacts, but are not allowed to move. In this light, the algorithm may be viewed as a fixture completion engine 7.3 Non-determinism and Redundancy. Due to the randomness of the initial placement in each generation, the algorithm is non- deterministic, i.e. it can produce different solutions given the same input. This is desirable as a contact point configuration may be rejected by the layout design module and the algorithm will have to produce another solution. The algorithm may produce redundant fixtures in certain cases. Redundant fixtures have drawbacks as well as advantages over the minimal ones. Certainly, they impair loadability and waste components. However, they may also minimize part d