Minimal Fixturing of Frictionless Assemblies: Complexity and Algorithms

David Baraff, Raju Mattikalli, and Pradeep Khosla
tech. report CMU-RI-TR-94-08, Robotics Institute, Carnegie Mellon University, April, 1994


Download
  • Adobe portable document format (pdf) (221KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
In many assembly tasks, it is necessary to insure the stability of a subcollection of contacting objects. To achieve stability, it is often necessary to introduce fixture elements (also called "fingers" in some work) to help hold objects in place. In this paper, the complexity of stabilizing multiple contacting bodies with the fewest number of fixture elements possible is considered. Standard fixture elements of the type explored in previous single-object grasping work are considered, along with two generalized fixture element variants. The types of stability considered are: form-closure (complete immobility of the assembly); stability with respect to a specific external force and torque on each body; and stability in the neighborhood of a specific external force and torque on each body. The major result is that for most of the combinations of fixture element varieties, and types of stability considered, achieving an optimal solution (that is, finding a smallest set of fixture elements yielding stability) is NP -hard. However, for many fixturing problems it seems likely that suboptimal, yet acceptably small solutions can be found in polynomial time, and some candidate algorithms are presented.

Notes
Grant ID: DACA76-89-C-0014, DAAE07-90-C-R059
Number of pages: 42

Text Reference
David Baraff, Raju Mattikalli, and Pradeep Khosla, "Minimal Fixturing of Frictionless Assemblies: Complexity and Algorithms," tech. report CMU-RI-TR-94-08, Robotics Institute, Carnegie Mellon University, April, 1994

BibTeX Reference
@techreport{Baraff_1994_328,
   author = "David Baraff and Raju Mattikalli and Pradeep Khosla",
   title = "Minimal Fixturing of Frictionless Assemblies: Complexity and Algorithms",
   booktitle = "",
   institution = "Robotics Institute",
   month = "April",
   year = "1994",
   number= "CMU-RI-TR-94-08",
   address= "Pittsburgh, PA",
}