Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-04T19:36:22.721Z Has data issue: false hasContentIssue false
  • English
  • Français

A geometric approach to manipulator path planning in 3D space in the presence of obstacles

Published online by Cambridge University Press:  09 March 2009

Manja Kirćanski  and
Olga Timčenko
Manja Kirćanski
Affiliation:
“Mihajlo Pupin” Institute, POB 15, Volgina 15, Belgrade (Yugoslavia)
Olga Timčenko
Affiliation:
“Mihajlo Pupin” Institute, POB 15, Volgina 15, Belgrade (Yugoslavia)
Get access Rights & Permissions [Opens in a new window]

Summary

The paper presents a geometric method for collision-free manipulator path planning in 3D Euclidean space with polyhedral obstacles. It ensures that none of the links nor the manipulator tip collide with the objects. The method is computationally very cheap and it does not require intensive off-line preprocessing. Hence, it is real-time applicable if the information about obstacles positions and shapes is obtained from a higher control level. The trajectories generated lie within the reachable workspace. The method is implemented on a VAX 11/750 computer and the simulation results are included.

Keywords

RobotPath planningObstacles avoidancePolyhedral obstaclesEuclidean spaceComputational complexity
Type
Article
Information
Robotica , Volume 10 , Issue 4 , July 1992 , pp. 321 - 328
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Lozano-Perez, T., “Automatic Planning of Manipulator Transfer Movements” IEEE Transactions on Systems, Man, and Cybernetics 11(10), 681–698 (10, 1981).Google Scholar
2.Lozano-Perez, T., “A Simple Motion-Planning Algorithm for General Robot Manipulators” IEEE J. of Robotics and Automation 3(3), 224–238 (06, 1987).CrossRefGoogle Scholar
3.Kuan, D.T., Zamiska, J.C. and Brooks, R.A., “Natural Decomposition of Free Space for Path Planning” Proc. of IEEE Int. Conference on Robotics and Automation,St. Louis, 168–173 (1985).Google Scholar
4.Wong, E.K. and Fu, K.S., “A Hierarchical Orthogonal Space Approach to Three-Dimensional Path Planning” IEEE J. of Robotics and Automation 2(1), 506–513 (03, 1986).CrossRefGoogle Scholar
5.Zhu, D. and Latombe, J. C., “Constraint Reformulation in a Hierarchical Path Planner” Proc. of IEEE Int. Conference on Robotics and Automation,Cincinnati,1918–1923 (1990).Google Scholar
6.Jun, S. and Shin, J.G., “A Probabilistic Approach to Collision-Free Robot Path Planning” Proc. of IEEE Int. Conf. on Robotics and Automation,Philadelphia,220–225 (1988).Google Scholar
7.Ashton, J. and Hoang, D., “An Algorithm for Finding Optimal Paths Between Points While Avoiding Polyhedral Obstacles” Proc. of Int. Conf. on Advanced Robotics ICAR'87,Versailles,307–312 (1987).Google Scholar
8.Hasegawa, T. and Terasaki, H., “Collision Avoidance: Divide-and-Conquer Approach by Determining Intermediate Goals” Proc. of Int. Conf. on Advanced Robotics ICAR'87,Versailles,295–306 (1987).Google Scholar
9.Bajaj, C. and Moh, T.T., “Generalized Unfoldings for Shortest Paths” Int. J. of Robotics Research 7(1), 71–76 (02, 1988).CrossRefGoogle Scholar
10.Franklin, R. and Akman, V., “Locus Techniques for Shortest Path Problems in Robotics” Proc. of SyRoCo, Barcelona, 131–136 (1985).Google Scholar
11.Gilbert, E. and Johnson, D., “Distance Functions and their Application to Robot Path Planning in the Presence of Obstacles” IEEE J. of Robotics and Automation 1(1), 21–30 (03 1985).CrossRefGoogle Scholar
12.Chen, Y. Ch and Vidyasagar, M., “Optimal Trajectory Planning for Planar n–Link Revolute Manipulators in the Presence of Obstacles” Proc. of IEEE Conf. on Robotics and Automation,Philadelphia,202–208 (1988).Google Scholar
13.Shiller, Z. and Dubowsky, S., “Global Time Optimal Motions of Robotic Manipulators in the Presence of Obstacles” Proc. of IEEE Conf. on Robotics and Automation,Philadelphia,370–375 (1988).Google Scholar
14.Takano, M. and Sasaki, K., “Time Optimal Control of FTP Motion of a Robot with Collision Avoidance” Proc. of Int. Conf on Advanced Robotics ICAR'87,Versailles, France,445–456 (1987).Google Scholar
15.Buchal, R. O. and Cherchas, D. B., “An Iterative Method for Generating Kinematically Feasible Interference-Free Robot Trajectories” Robotica 7(2), 119–127 (1989).CrossRefGoogle Scholar
16.Maciejewski, A. and Klein, Ch., “Obstacle Avoidance for Kinematically Redundant Manipulators in Dynamically Varying Environments” Int. J. Robotic Research 4(3), 109–117 (1985).CrossRefGoogle Scholar
17.Kirćanski, M. and Vukobratović, M., “Contribution to control of Redundant Robotic Manipulators in an Environment with Obstacles” Int. J. Robotic Research 5(4), 112–119 (Winter 1987).CrossRefGoogle Scholar
18.Generozov, V.L., “An Algorithm for Manipulator Trajectory Planning in the Presence of Obstacles” Technicheskaya Kibernetika 1, 137–147 (1984).Google Scholar
19.Aksenov, G., Voroneckaya, D. and Fomin, V., “Generation of Programmed Manipulator Motions by Means of Computers” Technicheskaya Kibernetika 4, 50–55 (1978).Google Scholar
20.Baillieul, J., “Avoiding Obstacles and Resolving Kinematic Redundancy” Proc. of IEEE Conf. on Robotics and Automation,San Francisco,1698–1704 (1986).Google Scholar
21.Faverjon, B. and Tournassoud, P., “A Local Based Approach for Path Planning of Manipulators with a High Number of Degrees of Freedom” Proc. of IEEE Conf. on Robotics and Automation,Raileigh,1152–1159 (1987).Google Scholar
22.Chirikjian, G. S. and Burdick, J. W., “An Obstacle Avoidance Algorithm for Hyper-Redundant Manipulators” Proc. of IEEE Conf. on Robotics and Automation,Cincinnati,625–631 (1990).Google Scholar
23.Freund, E. and Hoyer, H., “Real-Time Pathfinding in Multirobot Systems Including Obstacle Avoidance” Int. J. Robotic Research 7(1), 42–70 (02, 1988).CrossRefGoogle Scholar
24.Lee, B.H. and Lee, C.S.G., “Collision-Free Motion Planning of Two Robots” IEEE Trans. on Syst., Man, and Cyber. 17(1), 21–32 (01/02, 1987).Google Scholar
25.Roach, J. and Boaz, M., “Coordinating the Motions of Robot Arms in a Common Workspace” IEEE J. of Robotics and Automation 3(5), 437–444 (10, 1987).CrossRefGoogle Scholar
26.Tournassoud, P. and Faverjon, B., “Cooperation of Two Manipulators” Proc. of Int. Conf. on Advanced Robotics ICAR'87,Versailles, France,313–324 (1987).Google Scholar
27.Nagata, T., Honda, K. and Teramoto, Y., “Multirobot Plan Generation in a Continuous Domain: Planning by Use of Plan Graph and Avoiding Collision Among Robots” IEEE J. of Robotics and Automation 4(1) (02, 1988).CrossRefGoogle Scholar
28.Yamada, Y., Iwata, K., Yonekura, H., Seiki, H., Tsuchida, N. and Ueda, M., “Collision-Free Control of a 3-Link Arm by Using Ultrasonic Proximity Sensors” Proc. of 15th ISIR, Tokyo, 943–952 (1985).Google Scholar
29.Ramirez, C., “Stratified Levels of Risk for Collision-Free Robot Guidance” Proc. of 15th ISIR, Tokyo, 959–966 (1985).Google Scholar
30.Ichikawa, Y. and Ozaki, N., “Autonomous Mobile robot”, J. of Robotic Systems, 2(1), 135–144 (1985).Google Scholar
31.Khatib, O., “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots” Int. J. of Robotic Research 5(1), 90–99 (Spring 1986).CrossRefGoogle Scholar
32.Canny, J. F. and Lin, M. C., “An Opportunistic Global Path Planner” Proc. of IEEE Conf. on Robotics and Automation,Cincinnati,1554–1559 (1990).Google Scholar
33.Lumelsky, V., “Effect of Kinematics and Motion Planning for Planar Robot Arms Moving Amidst Unknown Obstacles” IEEE J. of Robotics and Automation 3(3), 207–223 (06, 1987).CrossRefGoogle Scholar
34.Paul, R., Robot Manipulators: Mathematics, Programming, and Control (The MIT Press, Cambridge, Massachusetts, 1981).Google Scholar