An efficient algorithm for one-step planar complaint motion planning with uncertainty

ABSTRACT

Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give an &Ogr;(n2 log n) algorithm to find a single commanded motion direction which will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.

REFERENCES

• AAG+86: Takao Asano , Tetsuo Asano , Leonidas Guibas , John Hershberger , Hiaroshi Imai, Visibility of disjoint polygons, Algorithmica, v.1 n.1, p.49-63, Jan. 1986 [doi>10.1007/BF01840436]
• Can89: J. Canny. On computability of fine motion plans. In IEEE International Conference on Robotics and Automation, Phoeniz, AZ., May 1989.
• CR87: J. Canny and J. Reif. New lower bound techniques for robot motion planning problems. In Proc. IEEE Symp. on Foundations of Computer Science, 1987.
• Don88: B. R. Donald, The complexity of planar compliant motion planning under uncertainty, Proceedings of the fourth annual symposium on Computational geometry, p.309-318, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73425]
• Don89: Bruce R. Donald, Error detection and recovery in robotics, Springer-Verlag New York, Inc., New York, NY, 1989
• Ede87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• Erd84: Michael A Erdmann, On Motion Planning with Uncertainty, Massachusetts Institute of Technology, Cambridge, MA, 1984
• Erd86: 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]
• LMT84: T. Lozano-Perez, M. T. Mason, and R. H. Taylor. Automatic synthesis of finemotion strategies for robots. ht. J. of Robotics Research, 3(l), 1984.
• Loz83: T. LozanoPCrez. Spatial planning: A configuration space approach. IEEE Trans. on Computers (C-92), pages 108- 120, 1983.
• Mas82: Matthew T Mason, Manipulator Grasping and Pushing Operations, Massachusetts Institute of Technology, Cambridge, MA, 1982
• Mas84: M. T. Mason. Automatic planning of fine motions: Correctness and completeness. In IEEE International Conference on Robotics, Atlanta Ga., 1984.
• Nat86: B K Natarajan, On moving and orienting objects, Cornell University, Ithaca, NY, 1986
• NP82: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• Whi77: D. Whitney. Force feedback control of manipulator fine motions. Journal of Dynamic Systems, Measurement, and Control June, pages 91-97, 1977.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory