A geometric reasoning system for moving an object while maintaining contact with others

ABSTRACT

This paper concerns the motion of moving a polyhedral object while maintaining contact with a set of stationary polyhedral objects. A method is developed for deriving a sequence of compliant-guarded motions in order to move an object from an initial configuration to a final configuration while it is in contact. This sequence is derived from a sequence of spatial relationships among the features of the objects. The construction of a graph of spatial relationships representing the space where the object is in contact with its environment is described. This is done using a geometric reasoning system which is able to find a relationship equivalent to a conjunction of two relationships and to construct the new features among which the new relationship holds.

REFERENCES

• 1: [HOPCROFT, WILFONG 84a] Hopcroft, J. E., and Wilfong, G. T., "On the Motion of Objects in Contact", TR 84-602, Dep. of Comp. Sci., Cornell University, May 1984.
• 2: [HOPCROFT, WILFONG 84b] Hopcroft, J. E. and Wilfong, G. T., "Reducing Multiple Object Motion Planning to Graph Searching", TR 84-616, Dep. of Comp. Sci., Cornell University, July 1984.
• 3: [KOUTSOU 84] Koutsou, A., "A Spatial Reasoning System for Parts Mating Operations", D. A. I. Working Paper No. 173, Dept. Art. Intell., University of Edinburgh, October 1984.
• 4: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 5: [MASON 79] Mason, M. T., "Compliance and Force Control of Computer Controlled Manipulator", MIT, AI LAB, Memo No. 605, 1979.
• 6: [MASSEY 78] Massey, W. S., "Homology and Cohomology Theory", Marcel Dekker, Inc., New York, 1978.
• 7: [POPPLESTONE 79] Popplestone, R. J., "Specifying Manipulation in Terms of Spatial Relationships", D. A. I. Research Report No. 117, Dept. Art. Intell., University of Edinburgh, 1979.
• 8: [REQUICHA, TILOVE 78] Requicha, A. G. and Tilove, R. B., "Mathematical Foundations of Constructive Solid Geometry: General Topology of Closed Regular Sets", Tec. Memo No. 27, Production Automation Project, University of Rochester, March 1978.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Motion

General Terms:
Design, Measurement, Performance, Theory