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 anO(n 2 logn) algorithm to find a single commanded motion direction that 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai. Visibility of disjoint polygons.Algorithmica, 1:49–63, 1986.
A. J. Briggs. An efficient algorithm for one-step planar compliant motion planning with uncertainty. InProc. ACM Symposium on Computational Geometry, Saarbrücken, June 1989, pp. 187–196.
R. C. Brost. Computing metric and topological properties of configuration-space obstacles. InProc. IEEE International Conference on Robotics and Automation, Phoenix, AZ, May 1989, pp. 170–176.
J. F. Canny. On computability of fine motion plans. InProc. IEEE International Conference on Robotics and Automation, Phoenix, AZ, May 1989, pp. 177–182.
J. F. Canny and J. Reif. New lower bound techniques for robot motion planning problems. InProc. IEEE Symposium on Foundations of Computer Science, 1987, pp. 49–60.
B. R. Donald. The complexity of planar compliant motion planning under uncertainty. InProc. ACM Symposium on Computational Geometry, Urbana, IL, June 1988, pp. 309–318.
B. R. Donald.Error Detection and Recovery in Robotics, Lecture Notes in Computer Science, vol. 336, Springer-Verlag, Berlin, 1989.
B. R. Donald. The complexity of planar compliant motion planning under uncertainty.Algorithmica, 5(3):353–382, 1990.
M. A. Erdmann. On motion planning with uncertainty. Technical Report MIT-AI-TR 810, Artificial Intelligence Laboratory, MIT, 1984.
M. A. Erdmann. Using backprojections for fine motion planning with uncertainty.International Journal of Robotics Research, 5(1):19–45, 1986.
J. Friedman, J. Hershberger, and J. Snoeyink. Compliant motion in a simple polygon. InProc. ACM Symposium on Computational Geometry, Saarbrücken, June 1989, pp. 175–186.
J. Jennings, B. R. Donald, and D. Campbell. Towards experimental verification of an automated compliant motion planner based on a geometric theory of error detection and recovery. InProc. IEEE International Conference on Robotics and Automation, Phoenix, AZ, May 1989, pp. 632–637.
J. C. Latombe. Motion planning with uncertainty: The preimage backchaining approach. Technical Report STAN-CS-88-1196, Department of Computer Science, Stanford University, March 1988.
T. Lozano-Pérez. Spatial planning: A configuration space approach.IEEE Transactions on Computers, 32:108–120, 1983.
T. Lozano-Pérez, M. T. Mason, and R. H. Taylor. Automatic synthesis of fine-motion strategies for robots.International Journal of Robotics Research, 3(1):3–24, 1984.
M. T. Mason. Manipulator grasping and pushing operations. Technical Report MIT-AI-TR-690, Artificial Intelligence Laboratory, MIT, 1982.
M. T. Mason. Automatic planning of fine motions: Correctness and completeness. InProc. IEEE International Conference on Robotics, Atlanta, GA, 1984, pp. 492–503.
B. K. Natarajan. On Moving and Orienting Objects. Ph.D. thesis, Department of Computer Science, Cornell University, Ithaca, NY, 1986.
J. Neivergelt and F. P. Preparata. Plane-sweep algorithms for intersecting geometric figures.Communications of the Association for Computing Machinery, 25(10):739–747, 1982.
D. Whitney. Force feedback control of manipulator fine motions.Journal of Dynamic Systems, Measurement, and Control, 99(2):91–97, June 1977.
Author information
Authors and Affiliations
Additional information
Communicated by C. K. Wong.
A preliminary version of this paper appeared in theProceedings of the ACM Symposium on Computational Geometry, Saarbrücken, June 1989. This paper describes research done in the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research is provided in part by the National Science Foundation under Grant IRI-8802390 and by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute.
Rights and permissions
About this article
Cite this article
Briggs, A.J. An efficient algorithm for one-step planar compliant motion planning with uncertainty. Algorithmica 8, 195–208 (1992). https://doi.org/10.1007/BF01758843
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01758843