When a three-dimensional object is placed in contact with a supporting plane, gravitational forces move it to one of a finite set of stable poses. For each stable pose, there is a region in the part's configuration space called a capture region; for any initial configuration within the region, the object is guaranteed to converge to that pose. The problem of computing maximal capture regions from an object model is analyzed assuming only that the dynamics are dissipative; the precise equations governing the system are unnecessary. An algorithm, based on Morse theory, is first developed for objects with smooth, convex hulls. The formulation is then extended to objects with piecewise-smooth hulls using a catalog of critical points de rived from stratified Morse theory. Algorithms have been fully implemented for objects with smooth and polyhedral convex hulls. As examples from the implementation demonstrate, calcu lating these regions from a geometric model is computationally practical.
Banchoff, T., Gaffney, T., and McCrory, C.1982. Cusps of Gauss Mappings. Boston, MA : Pitman.
3.
Boothroyd, G., and Ho, C.1977. Natural resting aspects of parts for automatic handling . ASME J. Eng. Industry99:314-317.
4.
Boothroyd, G., Redford, A., Poli, C., and Murch, L.1972. Statistical distributions of natural resting aspects of parts for automatic handling. SMEManufacturing Eng. Trans.1(72):93-105.
5.
Brokowski, M., Peshkin, M., and Goldberg, K.1993. Curved fences for part alignment. Proceedings of the IEEE Conference on Robotics and Automation, Atlanta, GA: IEEE Computer Society Press, pp. 467-473.
6.
Brost, R.C.1991a. Analysis and planning of planar manipulation tasks. PhD Thesis, Carnegie Mellon University.
7.
Brost, R.C.1991b, Computing possible rest configurations of two interacting polygons. Proceedings of the IEEE Conference on Robotics and Automation, Sacramento, CA: IEEE Computer Society Press, pp. 686-693.
8.
Brost, R.C.1992. Dynamic analysis of planar manipulation tasks. Proceedings of the IEEE Conference on Robotics and Automation , Nice, France: IEEE Computer Society Press, pp. 2247-2254.
9.
Canny, J.1988. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press.
10.
Carlisle, B., Goldberg, K., Rao, A., and Wiegley, J.1994. A pivoting gripper for feeding industrial parts. Proceedings of the IEEE Conference on Robotics and Automation , San Diego, CA: IEEE Computer Society Press, pp. 1650-1655.
11.
Chiang, H., Hirsch, M., and Wu, F.1988. Stability regions of nonlinear autonomous dynamical systems , IEEE Trans. Automat. Control33:16-27.
12.
Clarke, J.H.1990. Optimization and Nonsmooth Analysis. Philadelphia, PA: SIAM Press.
13.
Collins, G.E.1975. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition, vol. 33. New York: Springer-Verlag.
14.
do Carmo, M.1976. Differential Geometry of Curves and Surfaces. Englewood Cliffs, NJ: Prentice-Hall.
15.
Donald, B.1988. A geometric approach to error detection and recovery for robot motion planning with uncertainty. Artificial Intell.37:223-271.
16.
Erdmann, M.1986. Using backprojections for fine motion planning with uncertainty . Int. J. Robot. Res.5(1):19-45.
17.
Erdmann, M.A., Mason, M.T., and Vaněček, G.1993. Mechanical parts orienting: the case of a polyhedron on a table. Algorithmica10(2).
18.
Genesio, R., Tartaglia, M., and Vicino, A.1985. On the estimation of asymptotic stability regions: state of the art and new proposals. IEEE Trans. Automat. Control30(8):747-755.
19.
Goldberg, K.1993. Orienting polygonal parts without sensors. Algorithmica10(2):201-225.
20.
Goresky, M., and Macpherson, R.1980. Stratified Morse Theory. New York: Springer-Verlag.
Hung, C.-K., and Ierardi, D.1994. Constructing convex hulls of piecewise smooth objects . Technical Report USC-CS-94-583, University of Southern California.
23.
Koditschek, D.E.1991. The control of natural motion in mechanical systems, ASME J. of Dyn. Sys.113(4):547-551.
24.
Koenderink, J.J.1990. Solid Shape. Cambridge, MA: MIT Press.
25.
Kriegman, D.1994. Let them fall where they may: computing capture regions of curved 3D objects. Proceedings of the IEEE Conference on Robotics and Automation, San Diego, CA: IEEE Computer Society Press, pp. 595-601.
26.
Kriegman, D., and Ponce, J.1991. A new curve tracing algorithm and some applications. In P. J. Laurent, A. L. Méhauté, and L. L. Schumaker (eds.): Curves and Surfaces. Boston, MA: Academic Press, pp. 267-270.
Lozano-Pérez, T., Jones, J., Mazer, E., and O'Donnell, P.1992. HANDEY-A Robot Task Planner. Cambridge, MA: MIT Press.
30.
Lozano-Pérez, T., Mason, M.T., and Taylor, R.H.1982. Automatic synthesis of fine-motion strategies for robots . Int. J. Robot. Res.3(1):3-24.
31.
Mason, R., Rimon, E., and Burdick, J.1995. The stability of heavy objects with multiple contacts . Proceedings of the IEEE Conference on Robotics and Automation, Nagoya, Japan: IEEE Computer Society Press, pp. 439-445.
32.
Milnor, J.1963. Morse Theory. Princeton, NJ: Princeton University Press.
33.
Morgan, A.1987. Solving Polynomial Systems using Continuation for Engineering and Scientific Problems. Englewood Cliffs, NJ: Prentice-Hall.
34.
Murase, H., and Nayar, S.1994. Illumination planning for object recognition using parametric eigenspaces. IEEE Trans. Pattern Analysis Machine Intell.16(12):1219-1227.
35.
Ngoi, B., Lim, L., and Lee, S.1995. Analyzing the probabilities of natural resting for a component with a virtual resting face. SMEJ. Eng. Industry.
36.
Peshkin, M., and Sanderson, A.1989. Minimization of energy in quasi-static manipulation. IEEE Trans. Robot Automat.5(1):53-60.
37.
Preparata, F.P., and Shamos, M.I.1985. Computational Geometry: An Introduction. New York: Springer-Verlag.
38.
Rao, A., Kriegman, D., and Goldberg, K.1995. Complete algorithms for reorienting polyhedral parts using a pivoting gripper. Proceedings of the IEEE Conference on Robotics and Automation, Nagoya, Japan: IEEE Computer Society Press, pp. 2242-2248.
39.
Rimon, E., and Canny, J.1994. Construction of c-space roadmaps from local sensory data: what should the sensors look for? In IEEE Conference on Robotics and Automation, pp. 117-123.
40.
Rimon, E., and Koditschek, D.E.1992. Exact robot navigation using artificial potential functions. IEEE Trans. Robot. Automat.8(5):501-518.
41.
Sedykh, V.1977. Singularities of the convex hull of a curve in R3. Functional Analysis Appl.11(1):72-73.
42.
Sedykh, V.1986. Structure of the convex hull of a space curve. J. Soviet Mathematics33(1):1140-1153.
43.
Tournassoud, P., Lozano-Pérez, T., and Mazer, E.1987. Regrasping. Proceedings of the IEEE Conference on Robotics and Automation, Raleigh, NC: IEEE Computer Society Press, pp. 1924-1928.
44.
Whitney, H.1957. Elementary structure of real algebraic varieties. Annals Mathematics66(3):545-556.
45.
Wiegley, J., Rao, A., and Goldberg, K.1992. Computing a statistical distribution of stable poses of a polyhedron. Proceedings of the Allerton Conference on Communications, Control and Computing. Allerton, IL .
46.
Zakalyukin, V.1978. Singularities of convex hulls of smooth manifolds. Functional Analysis Appl.11(1):225-227.
