ASME Journal of Mechanical Design, 117 (1), March 1995 (p. 27) OPTIMAL CURVED FENCES FOR PART ALIGNMENT ON A BELT Mike Brokowski (1) Michael Peshkin (1) Ken Goldberg (2) ABSTRACT In automated packing or assembly it is often necessary to bring randomly oriented parts into uniform alignment. Mechanical methods such as vibratory bowl feeders are often used for this purpose, although there is no theory for the systematic design of such feeders. A slanted ŅfenceÓ attached to the stationary sides of a conveyor belt is also capable of orienting a stream of parts and a sequence of such fences has been shown [17] to function as a systematically designable linear parts feeder. A limitation of fence alignment is that once a part has left contact with a fence, its final orientation is confined to a narrow range of angles but is not unique. Here we consider the design of a single fence, consisting of a straight slanted section followed by an optimal curved tail. The straight section selectively aligns certain edges of the part, while the curved tail preserves this alignment precisely as the part leaves contact with the fence. We have found the shortest tail which guarantees alignment. Optimal curved fences may be used individually for alignment of parts on a conveyor belt. They also lend themselves to systematic design of multi- fence linear parts feeders [8] , [17] . (1) Department of Mechanical Engineering Northwestern University Evanston, Illinois 60208-3111 (2) Department of Computer Science University of Southern California Los Angeles, California 90089-0273 TEXT 1. Introduction and Background In robotics and in manufacturing operations involving packing or assembly, parts may need to be oriented before being grasped. Parts feeders perform this function by taking parts from random orientations to a unique one. Figure 1 shows the use of a conveyor belt with fences to orient parts. When the corner of a part hits a fence the part rotates until a flat edge is aligned with the fence, and then continues to slide along the fence on that edge. As the part leaves the fence, it turns further as it interacts with the curved tail of the fence. It stops turning as it loses contact with the fence, and does not rotate until it contacts the next fence. As Figure 2 illustrates, only certain edges of a part are stable (Figure 2A), meaning that the part can slide along a fence on that edge without turning onto the next edge (Figure 2B). Although in general several different edges of a part are stable, by arranging a sequence of fences at appropriate angles, one can ensure that a single unique edge of all parts rests against the final fence, so that all parts leave the final fence from that same edge. Figure 3 shows a parts feeder based on this concept (from [17] ). A more common method of part alignment uses a vibrating bowl. (Boothroyd [1] describes this and other feeders.) The vibration of a bowl feeder moves parts out of a pile in the bowl and up along a spiral track circling the bowlÕs rim. While the parts move along the spiral track, various obstacles fixed to the track knock off parts that are not properly oriented, passing only those parts that have a particular orientation. This method works well for many parts and has the advantage of being relatively compact. Vibratory bowl feeders are unfortunately not systematically designable. There is no known systematic way of arranging the obstacles which guarantees that all parts will leave the device properly oriented (although see [11] for an attempt). Experience and trial-and-error are used to determine an effective obstacle arrangement. Parts in unanticipated positions commonly jam feeders. Also, since the technique often relies on rejecting improperly oriented parts rather than reorienting them, a feeder may reject a large percentage of the incoming parts, yielding a low throughput. Hitakawa [10] described a parts feeder that uses an array of nests (silhouette traps) cut into a vibrating plate. The nests and the vibratory motion are designed so that the part will remain in the nest only in a particular orientation. By tilting the plate and letting parts flow across it, the nests eventually fill up with parts in the desired orientation. Although the vibratory motion is under software control, trial and error is required to design the nest for each part. Singer and Seering [20] proposed several designs for parts feeders, one using impact and another where programmed vibration, based on part geometry, was used to drive parts into a stable orientation. Grossman and Blasgen [9] used a vibrating box to insure that parts fall into one of a finite number of stable orientations under the influence of gravity. They then used a sequence of tactile probes to discriminate among these orientations. Mason [13] was the first to analyze the role of pushing in robot manipulation. Building on results from classical mechanics, he identified a fundamental rule for predicting the sense of rotation (CW or CCW) of a part as it is pushed in the presence of Coulomb friction. Although the partÕs exact motion depends on microscopic variations in the support surface, Mason showed that its sense of rotation depends only on the location of the partÕs center of mass and where it is pushed. Other geometric methods for predicting part motion in the presence of frictional contacts were described in [6] , [7] , [19] , [4] , and [3] . MasonÕs rule provided the basis for BrostÕs [2] push diagram, which represents all possible motions of a part as it is grasped by a parallel-jaw gripper. Brost showed how to use this diagram to identify single-step sensorless grasping actions that are robust to substantial uncertainty in initial part orientation. When there is greater uncertainty in the initial orientation of a part, more than one action may be required to construct a sensorless orienting strategy. Several researchers have addressed the problem of finding a sequence of actions (a multi-stage plan) for orienting polygonal parts. Mani and Wilson [12] considered pushing actions using a single planar fence. Peshkin and Sanderson [17] considered an arrangement of fixed fences where a conveyor belt causes parts to make contact with the fences, as in Figure 3. Erdmann and Mason [7] considered tilting actions that cause a part to slide into contact with the edges of a rectangular tray. Goldberg and Mason [9] considered grasping actions using a parallel-jaw gripper. In each case the authors developed a mechanical analysis and partitioned the set of possible actions into a finite number of equivalence classes based on part geometry. (Christiansen [5] describes how automated experiments, in lieu of mechanical analysis, can be used for this purpose.) Each applied a breadth-first exhaustive search to find a sequence of actions guaranteed to produce a unique final orientation of the part. Each method is complete in the sense that it is guaranteed to find such a plan if one exists. However, there is no bound on the computational cost for any of these search-based planners. Goldberg [8] described an O(n2) algorithm for finding a sequence of grasp actions that will orient a given polygonal part, and he proved that such a sequence exists for any polygonal part. There is some evidence that this algorithm can be modified for the automatic design of Peshkin-type fence arrangements for conveyor belt feeders. However, the algorithm requires that each fence produce a finite set of possible outcome orientations rather than the continuous ranges obtainable with straight fences. Problem Addressed In this work we concentrate on an aspect of the belt-based feeder shown in Figures 1 and 3. It is systematically designable and suitable for high volumes. This feeder takes advantage of the sliding friction between a part and the surface it moves on to orient parts on a conveyor belt. By letting parts on the belt run into a sequence of stationary fences fixed to the sides of the conveyor, each fence changing the partÕs orientation in a known way, we can ensure that all parts leave the final fence oriented in a unique way. One problem with the belt-based system is that all parts leaving a straight fence emerge in a range of orientations (typically ±10”) instead of in a unique orientation. Figure 4 shows the cause: some parts turn little as they leave a fence (4A) and some turn more (4B). When the part edge that had slid on the fence leaves the fence parallel to the beltÕs direction of motion we refer to that part as aligned with the belt motion. A convex part cannot turn beyond alignment with the belt motion. In this paper we solve the problem of parts leaving fences unaligned with belt motion by attaching a curved section of fence (a ŅtailÓ) to the end of the straight fence. An optimal tail reorients the edge of the part that was sliding along the fence as quickly as possible, until it is aligned with the direction of motion of the belt. Figure 5 shows such a curved section. 2. Contribution of this work We will find the optimal (most compact) fence shape which nevertheless guarantees a part will leave the end of a fence aligned with the belt motion, with arbitrarily small orientational error. Note that this problem is equivalent to one in which a part sits upon a stationary surface while a fence moves by and pushes it into alignment. The fence motion relative to the part is the important characteristic. In analyzing the problem, it is simpler to look at the case where the fence moves. Our analysis assumes several things. „ The part will be described as a convex polygon. Concave edges can be accommodated but will not be discussed here. „ We consider only parts moving on a flat surface and being pushed near that surface (that is, there is no tendency to overturn the parts). „ All motion occurs in the plane. Therefore, no sequence of fences can flip a part over, e.g. from this configuration to this one „ This paper develops fence shapes assuming frictionless contact between the part and the fence. However, we will explain that this is the conservative assumption; these fences also work in the presence of friction. „ We assume that the straight section of fence preceding an attached curved tail is long enough that all tumbling and edge selection will have occurred before a part encounters the curved section of fence. „ We assume that the motion of the parts is quasi-static [14] [18] ; that is, mass “ acceleration is small compared to the frictional forces acting upon a part. „ There are no collisions between parts; we do not address the problem of isolating parts (commonly known as singulating). In previous work we have shown that we can take many part shapes from arbitrary initial orientations to a unique final orientation range using a sequence of straight fences. Here, we focus on reducing that range of final orientations by developing curved fences whose output ranges are arbitrarily small. Our solutions determine the most compact (shortest) curved shape which guarantees alignment based upon three part parameters describing part geometry (section 3). We also find a slightly conservative, universal shape which scales simply based on only one part parameter to guarantee alignment (section 4) for any part. 3. Optimal Curved Fences 3.1 How Fences Push Parts To design fences which orient parts, we first look at how a part moves when pushed by a fence. When a partÕs corner touches a fence, the part turns until one edge of the part is parallel to the fence. The direction of the force applied to the part and its point of application determine the sense of rotation (clockwise or counterclockwise) of the part. Figure 6 shows a typical part-fence contact. With coefficient of (kinetic) friction mc between the part and the fence, the contact force lies between vectors A and B, which denote the friction cone on either side of a line perpendicular to the fence. Note also the vector f which begins at the contact point and is directed along the direction of motion of the fence relative to the part. Mason has shown [15] that whether a part will turn clockwise or counter- clockwise can be determined by the number of the vectors A, B, and f which lie on either side of the partÕs center of mass (CM, shown as ). If more lay to the left of the CM, the part will turn clockwise; if more lay to the right of the CM, it will turn counterclockwise; and it will move in pure translation when an equal number of vectors lay on both sides of the CM. (Technically, is the center of friction, but this is the same as the CM for sliding surfaces with spatially uniform friction coefficients.) The part shown in Figure 6 will turn clockwise. Once a part starts turning, it will continue to turn until an edge comes into alignment with the fence. If that edge of the part is stable (Appendix A), the part will continue to slide along the fence until it reaches the fenceÕs end and then turn further as it leaves the fence. If the edge is not stable, the part will continue turning onto the next edge until it finds a stable edge. Figures 7A-C show a part being aligned on a stable edge with a single straight fence. 3.2 Uncertainty in Part Motion Figures 7D-F show the part leaving the fence and Figure 7F reminds us that the partÕs edge may not necessarily leave the fence aligned with the direction of fence motion Ń vertical in this case. How exactly the part moves as it leaves the fence depends on how its weight is distributed on the sliding surface. This pressure distribution will depend upon contact geometry between the part and the surface as well as the mass distribution of the part itself. Variations in surface flatness or ŅbumpsÓ on the bottom of the part will affect the pressure distribution and the partÕs motion. Figure 8 shows how two parts with different contact geometry will turn differently. Part A, resting around its perimeter, will slide substantially as well as rotate as it is pushed, but part B which rests on a central hump will undergo nearly pure rotation. Because it turns slowly, an edge of part A will not come as closely into alignment with the direction of fence motion when leaving a straight fence as an edge of part B will. 3.3 Characterizing Part Motion with Uncertainty To create fences that fully align even the most slowly turning parts like the one shown in Figure 8A, we must more thoroughly describe the motion of a moving part. This subsection summarizes previous results [16] for the motion of a part pushed in the presence of uncertainty. First, note that a part sliding on a planar surface has three degrees of freedom but it has only two degrees of freedom when required to remain in contact with its pusher. We can characterize this partÕs motion by the location of its instantaneous center of rotation (COR) somewhere in the plane so that any infinitesimal motion of the part is a pure rotation dq about its COR. As we would expect, the location of a partÕs COR depends on how the part is supported by the sliding surface: the pressure distribution between the part and the surface it slides on. Since we wish to determine the motion of any part without knowing its exact pressure distribution, which may vary among parts in any case, we can determine all of the possible CORs for a given part [16] over all possible pressure distributions. We can bound the CORs for a given part, regardless of pressure distribution, within an area of the plane called the COR locus. By choosing a disk centered at the partÕs center of mass (CM) and large enough to enclose the entire part, we guarantee that any pressure distribution that the part might have is also one that the disk might have [16] . Therefore, by determining the COR locus of the disk, we bound the COR locus of the part. Previous work reveals the shape of this locus, whose exact form [16] neednÕt concern us here, and Figure 9 shows the boundary of the COR locus for a typical part pushed by a section of fence. Shown in this figure and of particular interest is rtip, the distance from the CM to the most distant point in the COR locus. This most distant point represents the slowest possible turning for a part of this shape. The vector rtip is parallel to the fence at the contact point. It has been shown [16] [17] that rtip = \F(a2, c cosq) (1) where c is the length of \O\AC(c,®), the vector from the CM to the contact point; a is the radius of the enclosing disk mentioned before; and q is the angle between \O\AC(c,®) and the fence. These parameters are shown in Figure 10 below. We will be considering the situation where the fence is tangent to a part edge (see section 3.5), so q may be thought of as the angle between \O\AC(c,®) and the part edge at the contact point. Notice that c/a cannot exceed unity, and for any rectangle of uniform density c/a = 1. When pushing a stable edge, q is in the range 0” to 90”. Note that the parameters q, a, and c are characteristics of the part and independent of its orientation, though they take different values for different part edges. Parts that turn about CORs in the rest of the COR locus will rotate more and slide less than the slowest turning parts, which rotate about rtip. A fence will not have any trouble pushing them into alignment if it can push the slowest turning parts into alignment. We assume here that the coefficient of friction between the part and the pusher mc = 0. We can treat the non-zero case but we will explain later that mc = 0 is the conservative assumption. 3.4 Describing Fence Shapes Now that we know how our worst case (slowest turning) part can move, we can construct a fence shape that will nevertheless turn it. We describe our curved fence in (a, R) coordinates, where a is the angle (local slope) of the fence and R is the local radius of curvature of the fence. a is measured with respect to the fenceÕs direction of motion as shown in Figure 11. Notice that, at a given angle a, a smaller R describes a sharper curve in the fence and a larger R describes a less sharp curve. By using this description of the fence shape, we can replace a segment of fence by a Ņlocal circleÓ: a circular pusher of the same local radius of curvature. We can then address the simpler question of how the radius R of the circular pusher depends on the angle a at which the part is pushed. The answer to this central question determines the shape of our curved fence. We note here that we can convert our (a, R) coordinates to more familiar orthogonal coordinates through a couple of substitutions. For a, we can substitute tan(a) = dy/dz, (2) choosing z to be the direction of motion of the fence. And R is the radius of curvature r which is given by r = \F(\B(1 + (dy/dz)2)3/2, d2y/dz2) (3) 3.5 Determining Optimal Fence Shapes Now we can apply this description of a fence pushing a part to determine the shape a fence must have to guarantee part alignment. Figure 12 shows a differential view of this problem. The fence, represented by its local circle, moves straight up, pushing a little bit (ds) on the part, which rotates da about its center of rotation (COR). Here r is the length of the line from the partÕs CM to the COR. Now we can describe the partÕs motion as it is pushed by a fence. When our most slowly turning part is pushed by a fence of a local radius of curvature R at an angle a, it will rotate about a particular COR. This geometry problem gives us the relationship between four variables: R, a, and the location (the two planar coordinates) of the COR. By imposing two mathematical conditions forcing our fence to accommodate the worst case part, we can eliminate two of these variable Š the location of the COR. This allows us to determine the relationship between R and a, which describes the optimal fence shape. First, we require that for the most slowly turning part, the trailing end of the partÕs aligned edge will begin and remain tangent to the contact point on the fence. Figure 13B shows this condition on tangency, as does Figure 12 above. If the part turned more quickly than this, then it would simply be aligning itself more quickly by Ņrolling forwardÓ on the fence (Figure 13C). If the part turned more slowly it might not keep up with the fence and begin loosing tangency with the fence without any way of assuring that the fence could push it back into alignment (Figure 13A). Accommodating the most slowly turning part assures that all parts will leave the fence, at worst, aligned with the slope of the end of the fence and, at best, aligned with the fenceÕs direction of motion. By extending the curved section of fence, we can make the difference between these two extremes arbitrarily small. The condition on tangency allows us to solve part of the geometry problem mentioned above and illustrated in Figure 12. Satisfying this condition, the part is initially tangent to the circle and remains tangent as it rotates about its COR. We might as well imagine that the circle is rigidly attached to the part, moving with the part as the part turns. The center of the circle moves straight up. This implies that the COR lies on a line perpendicular to the circleÕs upward motion and passing through the center of the circle. So, by using the condition on tangency, we have one constraint on the CORÕs location Ń the COR must lie along the dashed horizontal line shown in Figure 12. Figure 14 highlights the pertinent geometry of Figure 12. Since the center of the circle must lie on the same horizontal line as the COR, we can see that the z-components of the three bold vectors must add up to zero. (Note that z is vertical). These are: Rz =R sin (a) (4) cz = c sin (q + a Š 90”) (5) rz = r sin (90” Š a) (6) For our condition on tangency to hold true we require Rz + cz = rz. (7) Substituting (4), (5), and (6) into (7) and solving for R, we find: R = \F(r,tan a) + \F(c cos q,tan a) Š c sin q (8) Our second condition is slowest part accommodation. We want to accommodate the most slowly turning part because any faster turning part will align itself anyway. This means that the conservative COR is the one for the slowest turning part; r = rtip. (9) Our slowest part accommodation condition tells us where exactly on the dotted line the COR lies. Since equation (1) gives an expression for rtip in terms of part geometry, we can solve for the relationship between R and a. We find this to be R = \F(1,tan(a)) \B(\F(a2,c cos(q)) + c cos(q)) Š c sin(q). (10) This equation describes the shape of the fence in the (R, a) coordinates depicted in Figure 11. To convert these to orthogonal (y, z) coordinates, we can substitute equations (2) and (3) into equation (10). These substitutions reveal a second order ordinary differential equation: \F(d2y,dz2) = \F((1 + (dy/dz)\S\UP5(2))\S\UP5(3/2),\F(a2,c (dy/dz) cos(q)) + \F(c cos(q),(dy/dz)) Š c sin(q)) (11) Equation (11) gives the exact shape of the optimal fence curve in orthogonal coordinates and we solve it numerically. By solving the equation from a » 90” (dy/dz » °)* until a has reached some sufficiently small value (afinal), we bound the variation of the final partÕs orientation so that its aligned edge will lie between afinal and 0” from the fenceÕs direction of motion. We have assumed frictionless contact between the fence and the part. Any mc > 0 will cause the part to turn more quickly than it would with zero friction, causing it to align itself with the fence more quickly, which is fine. Thus, since a fence designed for mc = 0 will still work in the presence of friction, our assumption of frictionless contact is conservative. Of course, if mc is too high, the aligning side will be unstable and the part will tumble over the leading edge and onto its next side. Appendix A defines a stability such that if the straight section of fence is stable, so too will be any curved section attached to it. Figure 15 shows an exact fence curve generated for a square part using equation (11). This fence starts at a = 71.57” and ends at a = 1”. The square shown is drawn to scale and shows that, to align this part to within 1”, the fenceÕs y dimension must extend to about 1.1 times the squareÕs width. Exact fence shapes scale directly with part size a as we expect so that, to accommodate a square twice the size of the one shown, we would merely double the dimensions of the fence. Figure 16 also shows a dashed line representing a straight section of fence. A curved section of fence may be attached tangent to a straight section at any angle. 3.6 A Conservative, ŅUniversalÓ Fence Shape Recall that (R, a) are coordinates used to describe the fence shape and q, a, and c are part parameters. The fences described by equations (10) and (11) depend on these three parameters which account for particular part geometry. Further, these equations result in a different shape for different part parameter values q and c. That is, we cannot simply take the fence generated for a part with a particular q and scale it to fit a part with a different q. We would like to determine a single fence shape that is guaranteed to work for all parts, or a universal fence, by making conservative assumptions about part interaction with the fence. Examining equation (10), we see that the last term, Šc sin(q), will always be negative and therefore will always reduce R at a given a. Since a larger R describes a less sharp curve, which is easier for a part to follow, we can safely neglect this term and have less sharp fences that will still align parts, albeit more slowly and conservatively than necessary. Thus, the equation describing a universal shape is R = \F(k,tan a) (13) where k = \F(a2,c cos(q)) + c cos(q). (14) is a characteristic part number: a factor by which the single universal shape described by (13) can be simply scaled to align a particular part. The parameters q, c, and a are shown in Figure 10. The minimum k for any part is 2a, and occurs when c/a = 1 and q = 0”. Equation (13) describes a universal shape which will align any part. By this we mean that the one shape described by equation (13) will work for all parts; k is simply a scaling factor. Moreover, since a larger R is conservative, a part with characteristic part number k1 will also be aligned by a fence scaled by k2 if k2 > k1. We can substitute equations (2) and (3) into equation (13) to find the differential equation describing this fence in orthogonal coordinates: \F(d2y,dz2) = \F((dy/dz)(1 + (dy/dz)\S\UP5(2))\S\UP5(3/2),k) (15) Equation (15) may be solved to find z as a noninvertible function of y. If our fences start at the origin, we find this function to be \F(z,k ) = \R(Š(y/k )2 Š 2(y/k ) ) + \F(1,2) ln \B\BC\((\F(1 Š \R(Š(y/k )2 Š 2(y/k ) ),1 + \R(Š(y/k )2 Š 2(y/k ) ))) (16) We note that both y and z always appear normalized by k. Any fence generated for k = 1 can be made to work for any other k simply by scaling the shape along the y and z axes. Unlike the exact optimal fence shape described in the previous section, these universal fences are well behaved at a = 90” and it is not necessary that a fence generated this way start at an angle less than 90”. Even the most slowly turning parts on this conservative fence are turning more quickly than the fence and, instead of remaining tangent to it, they ŅrollÓ as shown in Figure 13C. The universal fence shape described by equation (16) is shown in Figure 16. This fence is scaled for a square part of side length 1, for which k = 3/2. Here a starts at 90” and ends at 1”. Shown near the top left of the fence at a = 57” is a section of straight fence attached tangent to the fence. A curved section of fence can be attached tangent to any straight section of fence to guarantee alignment of stable parts leaving that fence. Of concern to us in practical uses of the fence is how wide (y) a fence must be to guarantee a partÕs orientation to a required angular tolerance. For example, Figure 16 shows that, to get the square within 1” of alignment, the fence width must be roughly 3a/\R(2), or roughly 1.5 times the length of the squareÕs sides, which is slightly wider than the exact fence generated for the same square in Figure 15. As our tolerance afinal ® 0”, equation (16) asymptotically approaches a finite value Šk. In practice, we do not want infinitely long fences. The relationship between the fence angle a and the y-width of the fence is given by tan a = \F(dy,dz) = \F(y + k,\R(Š2ky Š y2)) (17) or y = k (sina - 1 ) (18) We can use equation (18) to determine how wide a fence must be to guarantee part alignment. Of course, we can also determine how long (z) a fence will be using equation (16). Conclusions We have found the optimal class of fence shapes for use in belt-based parts feeders that orient parts to within an arbitrarily small range. Fences of this design guarantee that a part will move into proper orientation regardless of the specific pressure distribution between the part and the surface upon which it slides. They are optimal in that they are the most compact shapes guaranteed to align parts. The optimal shape for a given curved section of fence can be generated automatically based upon three simple geometric parameters of the part via equation (11). This curved section of fence may be attached to a straight section of fence for use in parts feeder design. We have also defined a characteristic part number k and developed a more conservative but slightly less compact single fence shape which scales simply with k. This universal fence shape, described by equation (16), can be scaled with k to guarantee alignment for all parts. As with the exact fence shapes, the curved section of this type of fence may be attached to any straight section of fence. Acknowledgments We wish to thank Northwestern University and the National Science Foundation (NSF grant DMC 8857854) for supporting this work, and William L. Kath for assistance in solving equation (13). References 1. Boothroyd, G. P., Corrado; Murch, Lawrence E. Automatic Assembly. 1982 Marcel Dekker, Inc. 2. Brost, R. C. "Automatic Grasp Planning in the Presence of Uncertainty." International Journal of Robotics Research. (February): 1988. 3. Brost, R. C. "Analysis and Planning of Planar Manipulation Tasks." 1991. PhD thesis, Carnegie Mellon University. 4. Brost, R. C. ;. Mason, Matthew T. "Graphical Analysis of Planar rigid body dynamics with multiple frictional contacts." 5th International Symposium on Robotics Research, 1989. 5. Christiansen, A. D. "Automatic Acquisition of Task Theories for Robotic Manipulation." 1991. PhD thesis, CMU School of Computer Science. 6. Erdmann, M. A. "On motion planning with uncertainty." 1984. MS Thesis, Massachusetts Institute of Technology. 7. Erdmann, M. A. and M. T. Mason. "An Exploration of Sensorless Manipulation." IEEE International Conference on Robotics and Automation, 1986. 8. Goldberg, K. Y. "Orienting Polygonal Parts without Sensors" Algorithmica 10(2): August 1993. (Special Issue on Computational Robotics) 9. Goldberg, K. Y. and M. T. Mason. "Bayesian Grasping." IEEE International Conference on Robotics and Automation, 1990. 9. Grossman, D. D. ;. Blasgen, M. W. "Orienting mechanical parts by computer controlled manipulator." IEEE Transactions on Systems, Man, and Cybernetics. 5: 1975. 10. Hitakawa, H. "Advanced parts orientation system has wide application." Assembly Automation. 8(3): 1988. 11. Lozano-Perez, T. "Motion Planning and the Design of Orienting Devices for Vibratory Parts Feeders." IEEE Journal of Robotics and Automation. : 1986. 12. Mani, M., Wilson, W. R. D. "A Programmable Orienting System for Flat Parts." North American Manufacturing Research Institute Conference XIII, University of California, Berkeley. 1985. 13. Mason, M. T. "Manipulator Grasping and Pushing Operations." 1982. PhD thesis, MIT. 14. Mason, M. T. "On the Scope of Quasi-static Pushing." 3rd International Symposium on Robotics Research, 1985. 15. Mason, M. T. "Machanics and planning of manipulator pushing operations." The International Journal of Robotics Research. 5(3): 53-71, 1986. 16. Peshkin, M. A. and A. C. Sanderson. "The Motion of a Pushed, Sliding Workpiece." IEEE J. Robotics and Automation. 4(6): 569-598, 1988. 17. Peshkin, M. A. and A. C. Sanderson. "Planning Robotic Manipulation Strategies." IEEE J. Robotics and Automation. 4(5): 1988. 18. Peshkin, M. A. and A. C. Sanderson. "Minimization of Energy in Quasistatic Manipulation." IEEE J. Robotics and Automation. 5(1): 53-60, 1989. 19. Rajan, V. T.; Burridge, R.; Schwartz, J. T. "Dynamics of a rigid body in frictional contact with rigid walls." IEEE Conference on Robotics and Automation, 1987. 20. Singer, N. C. ; Seering. W. "Utilizing dynamic stability to orient parts." Journal of Applied Mechanics. 54: 1987. Appendix A. Part Stability Sometimes, for instance when friction is too high, we cannot guarantee alignment of a particular edge of a part because that edge is unstable. An unstable edge occurs when a part tumbles over its leading or trailing contact (see Figure A1). We require that a stable part not tumble anywhere on a curved fence, from the start at a = astart (where it might be attached to a straight section) down to a = 0”. This implies that the force vector along the left edge of the friction cone at the leading contact must not be directed to the left of the partÕs center of mass, otherwise the part will rotate clockwise onto its next edge. Figure A2 shows the force at the leading contact along the left edge of the friction cone which is directed away from a normal to the fence at the contact point by an angle b which is tan-1mc. To guarantee leading edge stability, this force must point to the right of the CM. If the length of the edge is l, we can show that mc < \F(l Š ccosq,csinq) (q < ¹/2) (A1) for an edge to be stable all the way down a curved section of fence. Since a part has to roll over this contact point to tumble and l, c and q are constant for this edge, an edge that is stable will remain stable. This means that some edges can never be stable, even with mc = 0, if cos q ³ l/c. It is also possible for certain parts to tumble ŅbackwardsÓ over their trailing contacts. This is only possible for parts where q > 90”. Figure A3 shows this situation. For such parts, tumbling is most likely when a is near 90”. In fact, if astart isnÕt less than 180” Š q, the part will tumble right at the start, regardless of friction. In parts like Figure A3Õs, when the force at the trailing contact points to the right of the partÕs center of mass the part will rotate counterclockwise to its next edge. To guarantee stability, the friction force (Figure A4) must point to the left of the center of mass, which is left of the normal force by q Š 90”. This implies that mc > Š cot q (q > ¹/2) (A2) Appendix B. Starting angles for exact fences A detail we encounter with the exact fence shapes described by equation (11) is that we cannot start the curved section of a fence quite at a = 90”. Looking at Figure 12 again, we can see that if, as shown, the contact point is above the COR, then the contact point will move up and to the right when first pushed. Likewise, if the contact point is below the COR, then it will move up and to the left. The contact point will move straight up when the COR and the contact point are at the same horizontal level. A problem arises when we try to start a part at a = 90” because then the contact point is necessarily below the COR. From this starting point, the part, while moving up, must also move initially left and then right. For a fence to accommodate this, it must stay tangent to the contact point as the part moves by. This results in a cusp. Figure B1 shows a blowup of the beginning of a fence designed to push a square starting at a = 90”, which causes such a cusp. It is not possible to build a real fence where the part rests properly on such a fence, since the part would initially have to pass through the fence as it slid in the +z direction. To avoid this problem we start our numerical solution for fences at the tip of the cusp. The highest angle a where a fence solution may start is where the contact point is level with the COR: tan (amax. start) = \F((a/c)2,cos(q) sin(q)) + \F(cos(q),sin(q)) (B1) In most instances, friction will render high starting values of a impossible anyway because the part would stick on the straight section of fence. We can minimize a in equation (B1) with respect to (c/a) and q. As a result, the lowest (worst) value for amax. start is ~70.53” and occurs at q » 55” and c/a = 1. Any exact fence starting at this angle, regardless of part geometry, will have no cusp. * A detail we encounter with exact fence shapes is that we cannot start the curved section of a fence quite at a = 90”. See Appendix B.