The complexity of planar compliant motion planning under uncertainty

ABSTRACT

We consider the computational complexity of planning compliant motions in the plane, given geometric bounds on the uncertainty in sensing and control. We can give efficient algorithms for generating and verifying compliant motion strategies that are guaranteed to succeed as long as the sensing and control uncertainties lie within the specified bounds. We also consider the case where a compliant motion plan is required to succeed over some parametric family of geometries. While these problems are known to be intractable in 3D, we identify tractable subclasses in the plane.

REFERENCES

• BK: C. Bajaj , M. Kim, Compliant motion planning with geometric models, Proceedings of the third annual symposium on Computational geometry, p.171-180, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41976]
• BLP: Brooks, R., and T Lozano-P~rez, "A Subdivision Algorithm in Configuration Space for Findpath with Rotation", Eighlh International Joint Conference on Artificial Intelligence, Karlsruhe, Germany, August, 1983.
• Bra: Michale Brady , John M. Hollerbach , Timothy L. Johnson , Matthew T. Mason , Tomas Lozano-Perez, Robot Motion: Planning and Control, MIT Press, Cambridge, MA, 1983
• Bro: Brost, R., "Automatic Grasp Planning in the Presence of Uncertainty", IEEE ICRA, San Francisco, April, 1986.
• Buc: Stephen J. Buckley, Planning and Teaching Compliant Motion Strategies, Massachusetts Institute of Technology, Cambridge, MA, 1987
• BRS: Burridge, R., Rajan, V. T., and Schwartz, J. T. The Peg-ln-ftole Problem: Statics and Dynamics of Nearly Ri#id Bodies in Frictional Contact, IEEE ICRA, Raleigh, NC (1987).
• Ca: Canny, 3.F. A New Algebraic method for Robot Motion Planning and Real Geometry, FOCS (1987).
• CD: J. Canny , B. Donald, Simplified Voronoi diagrams, Proceedings of the third annual symposium on Computational geometry, p.153-161, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41974]
• CD2: John Canny , Bruce Donald, Simplified Voronoi diagrams, Discrete & Computational Geometry, v.3 n.3, p.219-236, Jan., 1988 [doi>10.1007/BF02187909]
• CR: Canny, J., and J. Relf, "New Lower Bound Techniques for Robot Motion Planning Problems", FOGS (1987).
• DA: DiSessa, A. and Abelson9 H. Turtle Geometry, MtT Press, Cambridge (1978).
• Don: Bruce R. Donald, A search algorithm for motion planning with six degrees of freedom, Artificial Intelligence, v.31 n.3, p.295-353, March 1987 [doi>10.1016/0004-3702(87)90069-5]
• D: Donald, B. R. Robot Motion Planning with Uncertainty in the Geometric Models of the Robot and Environment: A Formal Framework for Error Detection and Recovery, IEEE International Conference on Robotics and Automation, San Francisco (1986).
• D2: Donald, B. R. A Theory of Error Detection and Recovery for Robot Motion Planning with Uncertainty, Intl. Workshop on Geometric Reasoning, Oxford, England (1986b).
• D3: Donald, B. R. Error Detection and Recovery for Robot Motion Planning with Uncertainty, MIT Artificial Intelligence Laboratory, MIT-AI-TR 982 (1987b).
• D4: Bruce R. Donald, A geometric approach to error detection and recovery for robot motion planning with uncertainty, Artificial Intelligence, v.37 n.1-3, p.223-271, Dec. 1988 [doi>10.1016/0004-3702(88)90056-2]
• D5: Bruce R Donald, Towards Task Level Robot Programming, Cornell University, Ithaca, NY, 1987
• E: M Erdmann, Using backprojections for fine motion planning with uncertainty, International Journal of Robotics Research, v.5 n.1, p.19-45, Spring, 1986 [doi>10.1177/027836498600500102]
• EM: Erdmann, M., and M. Mason, "An Exploration of Sensorless Manipulation", IEEE International Conference on Robotics and Automation, San Francisco, 1986.
• Gri: D. Yu. Grigor'ev, Complexity of deciding Tarski algebra, Journal of Symbolic Computation, v.5 n.1-2, p.65-108, February/April 1988 [doi>10.1016/S0747-7171(88)80006-3]
• HW: Hoperoft J., and Wilfong G., "Motion of Objects in Contact," Int. Jour. Robotics Res. vol 4, no. 4, (1986).
• Kod: Koditschek, D., "Exact Robot Navigation by Means of Potential Functions: Some Topological Considerations", Proc. IEEE Intl. Conf. Robotics, Raleigh, March 1987.
• Kou: A. Koutsou, A geometric reasoning system for moving an object while maintaining contact with others, Proceedings of the first annual symposium on Computational geometry, p.67-74, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323243]
• LP: Lozano-P6rez, T. Spatial Planning: A Configuration Space Approach, IEEE Trans. on Computers (C-32):108-120 (1983a).
• LP2: Lozano-P 6rez, T., "Robot Programming", IEEE Proceedings, 1983b.
• LMT: Lozano-P~rez, T., Mason, M. T., and Taylor, R. H. Automatic Synthesis of Fine-Motion Strategies for Robots, Int. J. of Robotics Research, Vol 3, no. 1 (1984).
• Lum: Lumelsky, V. J. Continuous Motion Planning in Unknown Environment for a 31) Cartesian Robot Arm. , Proc. IEEE ICRA, pp. 1569-1574 (1986).
• Ma: Mason, M.T. Compliance and force control for computer controlled manipulators, IEEE Trans. on Systems, Man and Cyberneti,'s (SMC-11):418-432 (1981).
• Ma2: Mason, M. T. Automatic Planning of Fine Motions: Correctness and Completeness, 1984 IEEE International Conference on Robotics, Atlanta Ga. (1984).
• Nat: B K Natarajan, On moving and orienting objects, Cornell University, Ithaca, NY, 1986
• Nat1: Natarajan, B. K. 1986 (Oct. 27-29, Toronto, Ontario). An Algorithmic Approach to the Automated Design of Parts Orienters. Proc. FOCS, pp. 132-142.
• OSY1: 6'Dfinlaing, C., Sharir, M., and Yap C., "Generalized Voronoi diagrams for moving a ladder: I Topological Analysis," NYU-Courant Institute, Robotics Lab. Tech. report No. 32 (1984)
• OSY2: 0'Dfnlaing, C., Sharir, M., and Yap C., "Generalized Voronoi diagrams for moving a ladder: II Efficient construction of the diagram," NYU-Courant Institute, Robotics Lab. Tech. report No. 33 (1984)
• OY: 6'Dfinlalng C., and Yap C., "A retraction method for planning the motion of a disc," J. Algorithms (6) (1985).
• SHS: Jacob T. Schwartz , Micha Sharir , John E. Hopcroft, Planning, geometry, and complexity of robot motion, Ablex Publishing Corp., Norwood, NJ, 1986
• SY: Schwartz J. and Yap C. K., "Advances in Robotics," Lawrence Erlbaum associates, Hillside New Jersey, (1986).
• T: Taylor, R. H. The Synthesis of Manipulator Control Programs from Task-level Specifications, Stanford Artificial Intelligence Laboratory, AIM-282, July (1976).
• Y: Yap, C., "Coordinating the motion of several discs," NYU- Courant Institute, Robotics Lab. No. 16 (1984)
• Y2: Yap, C., "Algorithmic Motion Planning", in Advances in Robotics: Volume 1, edited by J. Schwartz and C. Yap, Lawrence Erlbaum Associates, 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation; Dynamic programming
      I.2.9 Robotics
          Subjects: Sensors
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Projections
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

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