Motion planning algorithms are traditionally restricted to finding spatial or "physical" paths only, while manipulator dynamics is ignored. The attendant low-level problem of timing and velocity along the path is left to the trajectory planner. In this study, these two aspects have been combined. The overall problem has been cast as an optimal control problem. The obstacle avoidance conditions have been for mulated as state-variable inequality constraints. These con straints are shown to be continuously differentiable in our formulation. The continuous-time problem is converted to a discrete-time problem to permit the use of nonlinear pro gramming algorithms for the heavily constrained problem. Computational issues such as discretization effects and al gorithmic efficiency have been addressed. Simulations are performed for the proposed method.
Get full access to this article
View all access options for this article.
References
1.
Arora, J.S.1985. Theoretical manual for IDESIGN. Technical report ODL-85.9. Iowa City, Iowa: Department of Mechanical Engineering, University of Iowa.
2.
Bellman, R.E.1957. Dynamic Programming. Princeton, N.J. : Princeton University Press.
3.
Bobrow, J.E., Dubowsky, S., and Gibson, J.S.1985. Time optimal control of robotic manipulators along specified paths. Int. J. Robot. Res.4(3):3-17.
4.
Brooks, R.A.1983. Planning collision free motions for pick and place operations . Int. J. Robot. Res.2(4):19-44.
5.
Budak, B.M., Berkovich, E.M., and Solov'eva, E.N.1969. Difference approximations in optimal control applications . SIAM J. Control7(1):18-31.
6.
Bulirsch, R., and Stoer, J.1976. Introduction to Numerical Analysis. New York: Springer-Verlag.
7.
Cullum, J.1972. Finite dimensional approximations of state constrained optimal control problems. SIAM J. Control10(4):649-670.
8.
Daniel, J.W.1969. On the convergence of a numerical method for optimal control problems. J. Optimiz. Theory Applic.4(2):330-342.
9.
Donald, B.R.1984. Motion planning with six degrees of freedom. AI-TR-791. Cambridge, Mass.: M.I.T. Artificial Intelligence Laboratory .
10.
Dubowsky, S., Norris, M.A., and Shiller, Z.1986. Time optimal trajectory planning for robotic manipulators with obstacle avoidance: A CAD approach. Proceedings of the IEEE Conference on Robotics and Automation, Vol. 3. San Francisco, Calif.: IEEE, pp. 1906-1912.
11.
Gilbert, E.G., and Johnson, D.W.1985. Distance functions and their applications to robot path planning in the presence of obstacles. IEEE J. Robot. Automat. RA-1(1):21-30.
12.
Han, S.P.1977. A globally convergent method for nonlinear programming . J. Optimiz. Theory Applications. 22(3):297-309.
13.
Hisahi, M., Fukushima, M., and Tanaka, Y.1984. On the use of ∈-most active constraints in an exact penalty function method for non-linear optimization. IEEE Trans. Auto. ControlAC-29(11):1040-1042.
14.
Hopcroft, J.E., Joseph, D., and Whitesides, S.1982. On the movement of robot arms in 2-dimensional bounded regions. Technical report TR 82-486. Ithaca, New York: Department of Computer Science, Cornell University .
15.
Kahn, M.E., and Roth, B.1971. The near-minimum time control of open loop articulated kinematic chains. ASME J. Dyn. Sys. Measurement Control93(3):164-172.
16.
Khatib, O.1986. Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res.5(1):90-98.
17.
Kim, B.K., and Shin, K.G.1984. An efficient minimum time robot path planning under realistic conditions. Proceedings of the American Control Conference. San Diego, Calif.: IEEE, pp. 296-303.
18.
Leu, M.C., and Hemati, N.1986. Automated symbolic derivation of dynamic equations of motion for robot manipulators. ASME J. Dyn. Sys. Measurement Control108(3):172-179.
19.
Lozano-Pérez, T.1981. Automatic planning of manipulator transfer movements . IEEE Trans. Sys. Man Cybernt. SMC-11(10):681-698.
20.
Lozano-Pérez, T.1983. Spatial planning: A configuration space approach . IEEE Trans. ComputersC-32(2):108-120.
21.
Lozano-Pérez, T., Wesley, M.1979. An algorithm for planning collision free path among polyhedral obstacles. Camm. ACM22(10):560-570.
22.
Luh, J.Y.S., Walker, M.W., and Paul, R.P.1980. Resolved acceleration control of mechanical manipulators . IEEE Trans. Auto. ControlAC-25(3):468-474.
23.
Markiewicz, B.R.1973. Analysis of the computed torque drive method and comparison with conventional position servo for computer controlled manipulators . Technical memorandum 33-601. Los Angeles, Calif.: Jet Propulsion Laboratory.
24.
Maurer, H.1979. On the minimum principle for optimal control problems with state constraints. Schriftreihe des Rechenzentrums der Universitat Munster, report 41. Munster, Germany: University of Munster.
25.
Miele, A., and Wu, A.K.1980. Sequential gradient restoration algorithm for optimal control problems with non-differential and general boundary conditions, parts 1 and 2. Optimal Control Applicat. Methods1(1):69-88, 119-130.
26.
O'Dunlaing, C., Sharir, M., and Yap, C.K.1984a. Generalized Voronoi diagrams for moving a ladder: I. Topological analysis. Technical report no. 32. New York : Robotics Laboratory, NYU-Courant Institute.
27.
O'Dunlaing, C., Sharir, M., and Yap, C.K.1984b. Generalized Voronoi diagrams for moving a ladder: II. Efficient construction of the diagram. Technical report no. 33. New York: Robotics Laboratory, NYU-Courant Institute .
Pontryagin, L.S., Boltyanski, V.G., Gamkrelidze, R.V., and Mischenko, E.F.1962. The Mathematical Theory of Optimal Processes. New York: Wiley ( Interscience Publishers).
30.
Pschenichny, B.N., and Danilin, Y.M.1978. Numerical Methods in Extremal Problems. Moscow, U.S.S.R .: Mir Publishers.
31.
Schwartz, J.T., and Yap, C.K.1987. Advances in Robotics. New York : Lawrence Erlbaum Associates.
32.
Shiller, Z., and Dubowsky, S.1988. Global time optimal motions of robotic manipulators in the presence of obstacles. Proceedings of the IEEE Conference on Robotics and Automation. Philadelphia : IEEE, pp. 370-375.
33.
Shin, K.G., and McKay, N.D.1986. A dynamic programming approach to trajectory planning of robotic manipulators. IEEE Trans. Auto. Control AC-31(6):491-500.
34.
Singh, S., and Leu, M.C.1987. Optimal trajectory generation for robotic manipulators using dynamic programming. ASME J. Dyn. Sys. Measurement Control109(2):88-96.
35.
Singh, S.K., and Leu, M.C.1988. Identification of parameters for manipulator dynamics . Proceedings of the USA-Japan Conference on Robotics and Flexible Automation. Minneapolis: ASME, pp. 51-57.
36.
Singh, S.K.1988. Motion planning with obstacles and dynamic constraints. Ph.D. dissertation, Department of Mechanical Engineering , Cornell University.
37.
Singh, S.K.1989. The ConSERTD effort: A control system environment for real-time decision-making. Proceedings of the IEEE Conference on Robotics and Automation, Cincinnati, Ohio : IEEE, pp. 118-123.
38.
Singh, S.K.1990. Decentralized variable structure control for tracking in nonlinear systems. International Journal of Control, 52(4):811-831.
39.
Spong, M.W., Thorp, J.S., and Kleinwaks, M.J.1986. The control of robot manipulators with bounded input. IEEE Trans. Auto. ControlAC-31(6):483-490.
40.
Tan, H.H., and Potts, R.B.1988. Minimum time trajectory planner for the discrete dynamic robot model with dynamic constraints. IEEE J. Robot. Automat.4(2):174-185.
