Robotic Manipulation

Contact: Frank van der Stappen

Description
Computer-supported design of industrial part handling processes can lead to a substantial cost reduction in automated manufacturing. We study efficient algorithms for the design of low-cost and robust solutions to common part handling tasks such as part feeding and singulation (in which parts are oriented and separated, respectively), grasping or fixturing (in which parts are immobilized by fingers or fixturing elements), and assembly and disassembly.

Research of recent years shows that sequences of simple physical actions by simple manipulators using little or no sensory input can often accomplish the same manipulation tasks as the anthropomorphic robot hands and arms that are normally encountered in factories. As an example, a simple gripper consisting of two parallel jaws is able to orient any prismatic part by a sequence of squeeze actions. The sequence is computable from the shape of the part and does not rely on sensory data. Manipulation systems based on simple hardware elements bear a promise of increased reliability, speed, and suitability for automated planning, much lower cost, and rapid reconfigurability.

Algorithms for the automated design of these reliable low-cost manipulation systems rely on a thorough understanding of the behavior of parts subjected to seemingly simple physical actions such as pushing, dropping and touching parts. Our focus is to analyze the relation between physical actions and their impact on a part and to use this knowledge to derive efficient algorithms for determining sequences of simple actions that will accomplish a higher-level manipulation task. We want our algorithms to be complete, meaning that they must report a solution if one exists. Geometry is a major parameter in the definition, modeling, and solution of manipulation problems.

Interaction in a virtual environment often takes place through manipulation of the objects that are present in the environment, either by a user or by a computer-controlled creature. Insight in manipulation of objects will not only aid the automated design of manipulation systems; it will eventually also lead to more natural behavior of computer-controlled virtual humans in virtual environments. A better understanding of the effects of physical actions will result in a better match between the actions performed and the higher-level task these action aim to accomplish.

Manipulation plays a crucial role is surgery simulation. The aim is to provide surgeons with virtual patients and surgical tools, and allow them to use those, rather than real surgical tools on real patients, to rehearse a difficult surgical intervention. At the core of such a simulation is a system that computes deformations as well as the changes to the object caused by the user's cutting actions. A separate page is devoted to our work on cutting in deformable objects.

The Center for Geometry, Imaging and Virtual Environments closely collaborates with the group of Professor Ken Goldberg at the Department of Industrial Engineering and Operations Research at the University of California at Berkeley.

Current projects
Immobilization of non-rigid structures
Immobilization is a fundamental concept to manufacturing processes. It refers to preventing any motion of a part, despite the possible application of external forces and torques. Immobilization is of importance to grasping by multi-fingered robot hands, and crucial to fixturing, where a part is held by fixturing elements to be subjected to for example a machining operation. Immobilization of rigid objects is a fairly well-studied problem, but hardly any results exist for non-rigid objects, such as assemblies, deformable objects, or mechanisms.
CLAMP (Complete Algorithms for Manipulation Planning)
Most results for manipulation systems based on simple hardware elements apply to perfectly shaped planar polygonal parts. This NWO-funded project takes up the challenge to tackle this idealization as real industrial parts are three-dimensional, often curved, and manufactured to tolerances. It studies these issues in the context of two important manipulation tasks: part holding - which is concerned with (partially or completely) constraining the motion of part - and part feeding - which is concerned with orienting parts.

Past projects
Geometric design of part feeders
The part feeding process takes in a stream of identical parts in arbitrary orientations and outputs each part in the same (known) orientation. In this NWO-funded project we studied efficient complete algorithms for the design of trap filters for vibratory bowls, of feeders consisting of a conveyor belt with curved fences, on feeders based on a pulling robotic finger, and on feeders based on pushing orthogonal planar jaws. The results have been reported in several papers and in the PhD thesis of Robert-Paul Berretty.
Fixture planning: geometry and algorithms
In this project we studied efficient complete algorithms for computing grasps involving point and line contacts, and modular fixtures consisting with locators, clamps, and so-called edge fixels, whose placements are constrained by an underlying regular grid of holes. The results have been reported in several papers and in the PhD thesis of Chantal Wentink.

People
The following people are currently involved in this research area:
Publications
  • O.C. Goemans, A. Levandowski, K. Goldberg, and A.F. van der Stappen, On the design of guillotine traps for vibratory bowl feeders, Proceedings of the IEEE International Conference on Automation Science and Egineering (2005).
  • J.-S. Cheong and A.F. van der Stappen, Output-sensitive computation of all form-closure grasps of a semi-algebraic set, Proceedings of the IEEE International Conference on Robotics and Automation (2005).
  • J.-S. Cheong, H.J. Haverkort, and A.F. van der Stappen, On computing all immobilizing grasps of a simple polygon with few contacts, Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) (2003), Lecture Notes in Computer Science 2906 , Springer Verlag, Berlin (2003), pp. 260-269. Full paper submitted to journal (Technical Report).
  • J.-S. Cheong, K. Goldberg, M.H. Overmars, and A.F. van der Stappen, Fixturing hinged polygons, Proceedings of the IEEE International Conference on Robotics and Automation (2002), pp 876-881. Full paper, co-authored by Elon Rimon, submitted to journal (Technical Report).
  • A.F. van der Stappen, R.-P. Berretty, K. Goldberg, and M.H. Overmars, Geometry and part feeding, in: Sensor Based Intelligent Robot Systems (G.D. Hager, H.I. Christensen, H. Bunke, R. Klein Eds.), Lecture Notes in Computer Science 2238 , Springer Verlag, Berlin (2002), pp. 259-281. Technical Report.
  • R.-P. Berretty, M. Overmars, and A.F. van der Stappen, Orienting polyhedral parts by pushing, Computational Geometry: Theory and Applications 21 (2002), pp. 21-38 Technical Report.
  • R.-P. Berretty, K. Goldberg, M.H. Overmars, and A.F. van der Stappen, Trap design for vibratory bowl feeders, International Journal of Robotics Research 20 (11) (2001), pp. 891-908. Technical Report.
  • R.-P. Berretty, K. Goldberg, M.H. Overmars, and A.F. van der Stappen, Orienting parts by inside-out pulling, Proceedings of the IEEE International Conference on Robotics and Automation (2001), pp. 1053-1058.
  • A.F. van der Stappen, On the existence of form-closure configurations on a grid, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (2000), pp. 1237-1242.
  • A.F. van der Stappen, C. Wentink, and M.H. Overmars, Computing immobilizing grasps of polygonal parts, International Journal of Robotics Research 19(5) (2000), pp. 467-479. Technical Report.
  • A.F. van der Stappen, K. Goldberg, and M.H. Overmars, Geometric eccentricity and the complexity of manipulation plans, Algorithmica 26 (2000), pp. 494-514. Technical Report.
  • R.-P. Berretty, K. Goldberg, M.H. Overmars, and A.F. van der Stappen, Algorithms for fence design, in: Robotics: The Algorithmic Perspective (P.K. Agarwal, L.E. Kavraki, M.T. Mason Eds.), A.K. Peters, Natick, MA (1998), pp. 279-296. Technical Report.
  • R.-P. Berretty, K. Goldberg, M.H. Overmars, and A.F. van der Stappen, Computing fence designs for orienting parts, Computational Geometry: Theory and Applications 10 (1998), pp. 249-262 Technical Report.
  • C. Wentink, A.F. van der Stappen, and M.H. Overmars, Fixture design with edge-fixels, in: Intelligent robots: Sensing, modeling and planning (R. Bolles, H. Bunke, H. Noltemeier Eds.), Series on Machine Perception & Artificial Intelligence, Volume 27 , World Scientific Publ. Co., Singapore (1997), pp. 269-286.
  • C. Wentink, A.F. van der Stappen, and M.H. Overmars, Algorithms for fixture design, in: Algorithms for Robotic Motion and Manipulation (J.-P. Laumond and M. Overmars Eds.), A.K. Peters, Wellesley, MA (1997), pp. 321-346. Technical Report.

Facilities
For implementation and testing we have a lab available with modern top-end PC workstations with stereo viewing facilities. This lab was partially donated by Microsoft.

Student projects
There are ample opportunities for students to do master projects in this area. The list above gives a number of research themes. The projects can both be theoretically oriented and more experimental in nature. The lab is available for the students to work in. If you are interested, contact Frank van der Stappen. For more information see the education page.
webmaster: Frank van der Stappen