Potential-field based methods for path planning have the ad vantage of speed, but also a reputation for getting stuck in local minima when used with complex systems such as re dundant manipulators. We have developed a novel method of setting up a potential-field system that replaces rigid links by stiff (virtual) springs. The method is fast, directly suitable for parallel processing, and experimentally much less prone to the danger of local minima. Although quite general, it is par ticularly suited to use with manipulators whose links are thin compared with their length.
Get full access to this article
View all access options for this article.
References
1.
Barraquand, J., and Latombe, J.-C.1990. A Monte-Carlo algorithm for path planning with many degrees of freedom. Int. Conf. Robotics andAutomation, Cincinnati, pp. 1712-1717.
2.
Barraquand, J., and Latombe, J.C.1991. Robot motion planning: A distributed representation approach . Int. J. Robot. Res.10(6):628-649.
3.
Brooks, R.A.1983. Solving the find-path problem by good representation of free space. IEEE Trans. Sys. Man Cybernet.13(3):190-197.
4.
Canny, J.F.1988. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press.
5.
Challou, D.J., Gini, M., and Kumar, V.1993. Parallel search algorithm for robot motion planning. Int. Conf. Robotics andAutomation, Atlanta , Vol. 2, pp. 46-51.
6.
Cheung, E., and Lumelsky, V.1990. Motion planning for a whole sensitive robot arm manipulator. Int. Conf. Robotics andAutomation, Cincinnati , pp. 344-349.
7.
Curwen, R.1992. Dynamic contours: Real-time active splines. In Blake, A., and Zisserman, A. (eds.): Active Vision. Cambridge, MA: MIT Press.
8.
Curwen, R., Blake, A., and Cipolla, R.1991. Parallel implementation of Lagrangian dynamics for real-time snakes. In Mowforth, P. (ed.): British Machine Vision Conference. New York: Springer-Verlag, pp. 29-35.
9.
Curwen, R., Blake, A., and Zisserman, A.1992. Real-time visual tracking for surveillance and path planning . In Sandini, G. (ed.): Proc. of ECCV-92. New York: Springer-Verlag .
10.
Faverjon, B., and Toumassoud, P.1987. A local based approach for path planning of manipulators with a high number of degrees of freedom. Int. Conf. Robotics andAutomation, Raleigh, NC, pp. 1152-1159.
11.
Gupta, K.K., and Guo, Z.1992. Motion planning for many degrees of freedom: Sequential search strategy with backtracking. Int. Conf. Robotics and Automation, Nice, France, pp. 2328-2333.
12.
Hague, T.1993. Motion Planning for Autonomous Guided Vehicles. Ph.D. thesis, Department of Engineering Science, University of Oxford.
13.
Hague, T., and Cameron, S.1990. Path planning for the Oxford AGV. Proc. IEEE Int. Workshop on Intelligent Motion Control, Istanbul.
14.
Hague, T., and Cameron, S.1991. Motion planning for non-holonomic industrial robot vehicles. Proc. IROS-91, IEEE, Osaka, pp. 1275-1280.
15.
Hwang, Y.K., and Ahuja, N.1988. Path planning using a potential field representation. Int. Conf. Robotics and Automation, Philadelphia , pp. 648-649.
16.
Kass, M., Witkin, A., and Terzopoulos, D.1987. Snakes: Active contour models. Proc. 1st Int. Conf. Computer Vision, pp. 259-268.
17.
Khatib, O.1986. Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res.5(1):90— 98.
18.
Khatib, O.1987. A unified approach for motion and force control of robot manipulators: The operational space formulation. IEEE J. Robot. Automation3(1):43-53.
19.
Koditschek, D.E.1987. Exact robot navigation by means of potential functions: Some topological considerations. Int. Conf. Robotics andAutomation, Raleigh, pp. 1-6.
20.
Landau, L.D., and Lifschitz, E.M.1972. Mechanics and Electrodynamics: A Shorter Course of Theoretical Physics, Vol. 1. Oxford: Pergamon Press.
Lozano-Pérez, T.1987. A simple motion-planning algorithm for general robot manipulators . IEEE Trans. Robot. Automation3(3):224-238.
23.
Lozano-Pérez, T. and Wesley, M.A.1979. An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM22(10):560-570.
24.
Lumelsky, V.J.1987. Continuous motion planning in unknown environment for a 3D Cartesian robot arm. Int. Conf. Robotics andAutomation , San Francisco, pp. 1050-1055.
25.
McLean, A.1994. A framework for global planning for redundant manipulators . Int. Conf. Intelligent Robotics and Systems, Munich.
26.
McLean, A.1995. Path Planning for Redundant Manipulators, Ph.D. thesis, Department of Engineering Science, University of Oxford.
27.
McLean, A., and Cameron, S.1993. Snake-based path planning for redundant manipulators. Int. Conf. Robotics and Automation, Atlanta, Vol. 2, pp. 275-282.
28.
McLean, A., and Cameron, S.1994. Effective path planning and collision avoidance for redundant manipulators. Int. Conf. Automation, Robotics Computer Vision, Singapore.
29.
McLean, A., and Cameron, S.1995. Path planning and collision avoidance for redundant manipulators in 3D. Int. Conf. Intelligent Autonomous Systems, Karlsruhe .
30.
Peng, J.1992. Rule-Based Spatial Reasoning. Ph.D. thesis, Computing Laboratory, University of Oxford.
31.
Peng, J., and Cameron, S. (1991). Experiments with a rule-based robot palletiser . In Tzafestas, S.G. (ed.): Engineering Systems with Intelligence. Dordrecht/ Boston/London: Kluwer Academic Publishers. pp. 117-124.
32.
Quinlan, S., and Khatib, O.1993. Elastic bands: Connecting path planning and control. Int. Conf. Robotics andAutomation, Atlanta , Vol. 2, pp. 802-807.
33.
Rimon, E., and Koditschek, D.E.1992. Exact robot navigation using artificial potential functions. IEEE Trans. Robot. Automation8(5):501-518.
34.
Takahashi, O., and Schilling, R.J.1989. Motion planning in a plane using generalized Voronoi diagrams . IEEE J. Robot. Automation5(2):143-150.
