Sage Journals: Discover world-class research

Abstract

We present the first algorithms for computing all placements of (frictionless) point fingers that put a polygonal part in form closure and all placements of point fingers that achieve second-order immobility of a polygonal part. Our algorithms run in O(n^2+∈ +K) and O(n² log² n + K) time in the case of form closure and second-order immobility, respectively, where n is the number of vertices of the polygon, K is the description size of the resulting set of finger placements, and ∈ is an arbitrarily small constant. The basis of our algorithm is a translation of the problem into geometric searching problems, which are solved using efficient data structures. Our results can be extended to the problem of computing all placements of a line and two points that put a polygonal part in form closure. The resulting algorithm runs in O(n² log² n + K) time, where K is again the description size of the output.

Get full access to this article

View all access options for this article.

References

Brost, R. C., and Goldberg, K. Y. 1996. A complete algorithm for synthesizing modular fixtures for polygonal parts . IEEE Tr. on Robotics and Automation 12: 31–46 .

de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 1997. Computational Geometry–Algorithms and Applications. Berlin: Springer-Verlag .

Ferrari, C., and Canny, J. F. 1992. Planning optimal grasps . Proc. IEEE Int. Conf. on Robotics and Automation, Nice, France, pp. 2290–2295 .

Markenscoff, X., Ni, L., and Papadimitriou, C. H. 1990. The geometry of grasping . Int. J. of Robotics Research 9: 61–74 .

Markenscoff, X., and Papadimitriou, C. H. 1989. Optimum grip of a polygon . Int. J. of Robotics Research 8: 17–29 .

Mirtich, B., and Canny, J. F. 1994. Easily computable optimum grasps . Proc. IEEE Int. Conf. on Robotics and Automation, San Diego, CA, pp. 739–747 .

Mishra, B., Schwarz, J. T., and Sharir, M. 1987. On the existence and synthesis of multifinger positive grips . Algorithmica 2: 541–558 .

Nguyen, V.-D., 1988. Constructing force-closure grasps . Int. J. of Robotics Research 7: 3–16 .

Overmars, M., Rao, A., Schwarzkopf, O., and Wentink, C. 1995. Immobilizing polygons against a wall . Proc. 11th Ann. ACM Symp. on Computational Geometry, Vancouver, BC, pp. 29–38 .

10.

Ponce, J., and Faverjon, B. 1995. On computing three-finger force-closure grasps of polygonal objects . IEEE Tr. on Robotics and Automation 11: 868–881 .

11.

Ponce, J., Stam, D., and Faverjon, B. 1993. On computing force-closure grasps of curved two-dimensional objects . Int. J. of Robotics Research 12: 263–273 .

12.

Ponce, J., Sullivan, S., Sudsang, A., Boissonnat, J.-D., and Merlet, J.-P. 1997. On computing four-finger equilibrium and force-closure grasps of polyhedral objects . Int. J. of Robotics Research 16: 11–35 .

13.

Reuleaux, F. 1876. The Kinematics of Machinery. London: Macmillan ; republished by Dover (New York, 1963).

14.

Rimon, E., and Burdick, J. W. 1998a. Mobility of bodies in contact–Part I: A second-order mobility index for multiple-finger grasps . IEEE Tr. on Robotics and Automation 14: 696–708 .

15.

Rimon, E., and Burdick, J. W. 1998b. Mobility of bodies in contact–Part II: How forces are generated by curvature effects . IEEE Tr. on Robotics and Automation 14: 709–717 .

16.

Sudsang, A., Ponce, J., and Srinivasa, N. 1997. Algorithms for constructing immobilizing fixtures and grasps of three-dimensional objects. In Algorithms for Robotic Motion and Manipulation, ed. J.-P. Laumond and M. Overmars, 363–380. Wellesley, MA: A. K. Peters .

17.

Wagner, R., Zhuang, Y., and Goldberg, K. Y. 1995. Fixturing parts with seven modular struts . Proc. IEEE Int. Symp. on Assembly and Task Planning, Pittsburgh, PA, pp. 133–139 .

18.

Wallack, A., and Canny, J. F. 1994. Planning for modular and hybrid fixtures . Proc. IEEE Int. Conf. on Robotics and Automation, San Diego, CA, pp. 520–527 .

19.

Wallack, A., and Canny, J. F. 1996. Modular fixture design for generalized polyhedra . Proc. IEEE Int. Conf. on Robotics and Automation, Minneapolis, MN, pp. 830–837 .

20.

Wentink, C. 1998. Fixture Planning–Geometry and Algorithms. Ph.D. thesis, Dept. of Computer Science, Utrecht University, the Netherlands.

21.

Wentink, C., van der Stappen, A. F., and Overmars, M. H. 1997. Algorithms for fixture design. In Algorithms for Robotic Motion and Manipulation, ed. J.-P. Laumond and M. Overmars, 321–346. Wellesley, MA: A. K. Peters .

Computing Immobilizing Grasps of Polygonal Parts

Abstract

Get full access to this article

References