zbMATH — the first resource for mathematics

Motion planning for robots with topological dimension reduction method. (English) Zbl 0728.68138
Summary: This paper explores the realization of robotic motion planning, especially Findpath problem, which is a basic motion planning problem that arises in the development of robotics. Findpath means: Give the initial and desired final configurations of a robotic arm in 3- dimensional space, and give descriptions of the obstacles in the space, determine whether there is a continuous collision-free motion of the robotic arm from one configuration to the other and find such a motion of it exists. There are several branches of approach in motion planning area, but in reality the important things are feasibility, efficiency and accuracy of the method. In this paper according to the concepts of Configuration Space (C-Space) and Rotation Mapping Graph) (RMG), a topological method named Dimension Reduction Method (DRM) for investigating the connectivity of the RMG (or the topologic structure of the RMG) is presented by using topological technique. Based on this approach the Findpath problem is thus transformed to that of finding a connected way in a finite Characteristic Network (CN). The method has shown great potentiality in practice. Here a simulation system is designed to embody DRM and it is in sight that DRM can be adopted in the first overall planning of real robot system in the near future.
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] R. T. Chien, Ling Zhang and Bo Zhang, Planning collision-free paths for robotic arm among obstacles,IEEE Trans. PAMI., PAMI-6:1 (1984).
[2] Bo Zhang and Ling Zhang, Planning Collision-Free Paths for 3-Dimensional Object with Rotation, Report on ACADEMIA SINICA (China) and C. N. R. (France) Robotics Workshop, Oct., 1985.
[3] Bo Zhang, Ling Zhang and Jianwei Zhang, An Algorithm for Findpath with Rotation, Proc. of IEEE 1988 International Conference on SMC, Beijing, 795–798.
[4] Bo Zhang, Ling Zhang, Jianwei Zhang and Tian Zhang, A Findpath Algorithm for Manipulator by Finite Division of Configuration Space, Second Intemational Symposium, Robotics and Manufacturing Educations and Applications, Nov. 16–18, 1988, Albuquerque, New Mexico, U. S. A.
[5] T. Lozano-Pérez, Spatial planning: a configuration space approach,IEEE Trans. on Comput, c-32: 2(1983). · Zbl 0513.68081
[6] R. A. Brooks, T. Lozano-Pérez, A Subdivision Algorithm in Configuration Space for Findpath with Rotation, Proc. of 8th IJCAJ-83, pp. 789–806.
[7] T. Lozano-Pérez, A simple motion planning algorithm for general robot manipulators,,IEEE Journal of Robotics and Automation, RA-3:3(1987).
[8] J. T. Schwartz, M. Sharir, J. Hopcroft, Planning Geometry and Complexity of Robot Motion, ABLEX PUBLISHING CORPORATION, Norwood, New Jersey, 1987.
[9] S. H. Whitesides, Computational Geometry and Motion Planning, G. T. Toussaint (Editor), Elserier Science Publishers B. V. (North-Holland), 1985. · Zbl 0588.68055
[10] F. P. Preparata, M. L. Shamos, S-Verley, Computational Geometry–An Introduction, Texts and Mono-Graphs in Computer Science, 1985.
[11] T. Lozano-Pérez, Automatic planning of manipulator transfer movementsIEEE Trans., SMC-11: 10(1985), 681–698.
[12] M. Eisenbery, Topology, Holt Rinehart and Winston, Inc., 1974.
[13] B. T. Sims, Fundamentals of Topology, Nacmillan Publishing Co., INC. New York, 1976. · Zbl 0324.54002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.