On planning assemblies

ABSTRACT

This paper concerns the problem of assembling composite objects. We study the problem on two fronts; Firstly we study the complexity of deciding the existence of an assembly sequence and show that this is PSPACE-hard in general. Secondly we define a new measure of complexity, one that attempts to measure the minimum number of hands required to assemble a given composite. We analyze various classes of composite objects with respect to this measure.

REFERENCES

• 1: Doug Campbell, The Cornell Robot System Design Report, Cornell University, Ithaca, NY, 1985
• 2: Dawson, R., 1984, On Removing a Ball without Disturbing Others Mathematics Magazine, Vol. 57, No. 1, January.
• 3: Leo J. Guibas , F. Frances Yao, On translating a set of rectangles, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.154-160, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804663]
• 4: Hopcroft, J.E., Schwartz; J., & Sharir, M., 1984, On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- hardness of the Warehouseman's Problem, International Journal of Robotics Research, Vol 3, No. 4, Winter.
• 5: Libermann, L.I., and Wesley, M.A., 1977, AUTOPASS: An Automatic Programming System for Computer Controlled Mechanical Assembly, IBM Journal of Research and Development, July.
• 6: Tony Owen, Assembly with robots, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 7: Keith Rathmill, Robotic Assembly, Springer-Verlag New York, Inc., Secaucus, NJ, 1986
• 8: Reif, J.H., 1979, Complexity of the Mover's Problem and Generalizations, Symposium on Foundations of Computer Science, San Juan, Peurto Rico.
• 9: Toussaint, G.T., and El Gindy, H.A., 1984, Separation of Two Monotone Polygons in Linear Time, Robotica, Vol 2.
• 10: Toussaint, G.T., and Sack, J.R., 1983, Some New Results on Moving Polygons in the Plane, Proc. Robotic Intelligence and Productivity Conference, Detroit.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Manipulators

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided manufacturing (CAM)

General Terms:
Algorithms, Design, Measurement, Performance, Theory