This paper describes the development of a new type of non- collision constraint function for use in numeric path planning. It is valid even when computed for configurations in collision. This allows for greater freedom in hypothesizing trajectories to be relaxed intact into admissibility. The motivation lead ing to its development is discussed, along with its theory and properties. By way of example, its application in a naive path planning algorithm is described, which leads to surprising results when compared with a contemporary subdivision method.
Get full access to this article
View all access options for this article.
References
1.
Avriel, M.1976. Nonlinear Programming: Analysis and Methods. Englewood Cliffs: Prentice-Hall.
2.
Brooks, R.A., and Lozano-Pérez, T.1982 (Dec.) A subdivision algorithm in configuration space for findpath with rotation. A. I. Memo 684. Cambridge: M.I.T.Artificial Intelligence Laboratory.
3.
Buckley, C.E.1985a. The Application of Continuum Methods to Path-Planning. Ph.D. thesis, Stanford University, Mechanical Engineering Department.
4.
Buckley, C.E.1985b. (Los Angeles). A proximity metric for continuum path-planning. Ninth Int. Joint Conf. Artificial Intelligence: 1096-1102.
Cahn, D.F., and Phillips, S.R.1975(Sept.). Robnav: a range-based robot navigation and obstacle avoidance algorithm. IEEE Trans. Systems, Man, Cybernet. 5(5):544-551.
7.
Cameron, S.1982. The clash detection problem. Working Paper 126. University of EdinburghDepartment of Artificial Intelligence .
8.
Cameron, S.A., and Culley, R.K.1986 (San Francisco). Determining the minimum translational distance between two convex polyhedra. Int. Conf. Robotics and Automation. IEEE, pp. 591-596.
9.
Chazelle, B.M.1980. Computational geometry and convexity. Computer Science Department Report CMU-CS-80-150, Carnegie-Mellon University .
10.
Comba, P.G.1968. A procedure for detecting intersections of three-dimensional objects. J. Assoc. Comput. Mach.15(3):354-366.
11.
Culley, R.K., and Kempf, K.G.1986 (San Francisco). A collision detection algorithm based on velocity and distance bounds. Int. Conf. Robotics and Automation. IEEE, pp. 1064-1069.
12.
Donald, B.R.1984. Motion planning with six degrees of freedom. Technical Report 791, Cambridge, Mass.: M.I.T.Artificial Intelligence Laboratory.
13.
Garcia, C.B., and Zangwill, W.I.1981. Pathways to Solutions, Fixed Points, and Equilibria. Englewood Cliffs: Prentice-Hall.
14.
Gilbert, E.G., and Johnson, D.W.1985. Distance functions and their application to robot path planning in the presence of obstacles. IEEE J. Robotics Automat.1(1):21-30.
15.
Kane, T.R., Likins, P.W., and Levinson, D.A.1982. Spacecraft Dynamics. New York: McGraw-Hill.
16.
Khatib, O.1980. Commande dynamique dans l'espace operationnel des robots manipulateurs en présence d'obstacles. Doc.-Ing. Thesis, French National SuperiorSchool of Aeronautics and Astronautics.
17.
Lewis, R.A., and Bejczy, A.K.1973 (Stanford, Calif.). Planning considerations for a roving robot with arm. Third Int. Joint Conf. Artificial Intelligence.
18.
Liegeois, A.1977. Automatic supervisory control of the configuration and behavior of multibody mechanisms. IEEE Trans. System, Man, Cybernet.7(12):868-871.
19.
Loeff, L.A., and Soni, A.H.1975 (Aug.). An algorithm for computer guidance of a manipulator in between obstacles. ASME J. Engin. Indust.: 836-842.
20.
Lozano-Pérez, T.1981. Automatic planning of manipulator transfer movements. IEEE Trans. Systems, Man, Cybernet. SMC-11(10):681-698.
21.
Lozano-Pérez, T.1983. Spatial planning: a configuration space approach. IEEE Trans. Comput.C-32(2):108-120.
22.
Lozano-Pérez, T.1986 (Philadelphia). A simple motion planning algorithm for general robot manipulators. National Conf. Artificial Intelligence. AAAI, pp. 626-631.
23.
Lozano-Pérez, T., and Wesley, M.A.1979. An algorithm for planning collision-free paths among polyhedral obstacles. Comm. ACM22(10):560-570.
24.
Luh, J.Y.S., and Lin, C.S.1981 (June). Optimum path planning for mechanical manipulators . ASME J. Dynamic Syst., Meas., Control102:142-151.
25.
Myers, J.K.1981. A supervisory collision-avoidance system for robot controllers. Master's thesis, Carnegie-Mellon University.
26.
Peiper, D.L.1968. The kinematics of manipulators under computer control. Ph.D. thesis, Stanford University, Mechanical Engineering Department.
27.
Powell, M.J.D.1964. An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput. J.7:155-162.
28.
Preparata, F., and Hong, S.1977 (Feb.). Convex hulls of finite sets of points in two and three dimensions. Comm. Assoc. Comput. Mach.20:87-93.
29.
Rockafellar, R.T.1970. Convex Analysis. Princeton, N.J.: Princeton University Press.
30.
Scheinman, V.S.1969 (June). Design of a computer controlled manipulator. Artificial Intelligence Memo AIM-92, Stanford University.
31.
Schwartz, J.T., and Sharir, M.1982 (Feb.). On the piano movers' problem. II. General techniques for computing topological properties of real algebraic manifolds. Courant Institute of Mathematical Sciences Report 41, New York University.
32.
Udupa, S.M.1977. Collision detection and avoidance in computer controlled manipulators. Ph.D. thesis, California Institute of Technology , Pasadena, California, Electrical Engineering Department.
33.
Whitney, D.E.1969. State space models of remote manipulation tasks. IEEE Trans. Automat. Contr. AC-14(6):617-623.
34.
Widdoes, C.1974. A heuristic collision avoider for the Stanford robot arm . Unpublished term paper for Stanford University course CS227.
35.
Yoshikawa, T.1984. Analysis and Control of Robot Manipulators with Redundancy , pp. 735-747. Cambridge, Mass.: MIT Press.
