The minimum-time path for a robot arm has been a long standing and unsolved problem of considerable interest. We present a general solution to this problem which involves joint-space tessellation, a dynamic time-scaling algorithm, and a graph search. The solution incorporates full dynamics of movement and actuator constraints, and can easily be extended for joint limits and workspace obstacles. It was found that optimal paths tend to be nearly straight lines in joint space. We discuss implementation difficulties due to the tessellation and to combinatorial proliferation of paths.
Get full access to this article
View all access options for this article.
References
1.
Asada, H.1984 (March 13-15, Atlanta). Dynamic analysis and design of robot manipulators using inertia ellipsoids . Proc. IEEE Computer Society 1st Intl. Conf on Robotics, pp. 94-102.
2.
Bobrow, J.E.1982. Optimal control of robotic manipulators. Ph.D. thesis, UCLA, Mechanics and Structures Department.
3.
Bobrow, J.E., Dubowsky, S., and Gibson, J.S.1983 (June 22-24, San Francisco). On the optimal control of robotic manipulators with actuator constraints. Proc. Amer. Contr. Conf, pp. 782-787.
4.
Brady, J. M., et al., eds. 1982. Robot motion: planning and control. Cambridge: MIT Press.
5.
Brown, M.L.1984 (June). Optimal robot path planning via state space networks . M.S. thesis, Princeton University, Mechanical and Aerospace Engineering Department.
6.
Dubowsky, S., and Shiller, Z.1985. Optimal dynamic trajectories for robotic manipulators. In Theory and practice of robots and manipulators, eds. A. Morecki, G. Bianchi, and K. Kedzior. Proc RoManSy '84: 5th CISM-IFToMM Symp. Cambridge: MIT Press, pp. 133-144.
7.
Hollerbach, J.M.1983a (Jan.). Dynamic scaling of manipulator trajectories. A.I. Memo 700. Cambridge: MIT Artificial Intelligence Laboratory.
8.
Hollerbach, J.M.1983b (June 22-24, San Francisco). Dynamic scaling of manipulator trajectories. Proc. Amer. Contr. Conf, pp. 752-756.
9.
Hollerbach, J.M.1984. Dynamic scaling of manipulator trajectories. ASME J. Dyn. Sys., Meas., Contr.106:102-106.
10.
Horn, B.K.P.1975 (June). Kinematics, statics, and dynamics of two-D manipulators. Working Paper 99Cambridge: MIT Artificial Intelligence Laboratory.
11.
Kahn, M.E.1969 (Dec.). The near-minimum-time control of open-loop articulated kinematic chains. AIM 106Stanford: Stanford Artificial Intelligence Laboratory.
12.
Kahn, M.E., and Roth, B.1971. The near-minimum-time control of open-loop articulated kinematic chains. J. Dyn. Sys., Meas., Contr. 93:164-172.
13.
Kim, B.K., and Shin, K.G.1985. Minimum-time path planning for robot arms and their dynamics . IEEE Trans. Sys., Man, Cyber. SMC-15:213-223.
14.
Kornhauser, A.L., and Brown, M.L.1985 (Mar. 25-28, St. Louis). Optimal trajectories for robotic manipulators using state-space networks. IEEE Int. Conf. Robotics and Automation, p. 750.
15.
Lin, C.-S., and Chang, P.-R.1985 (Mar. 25-28, St. Louis). Approximate optimum paths of robot manipulators under realistic physical constraints . Proc. IEEE Int. Conf. Robotics and Automation , pp. 737-742.
16.
Lin, C.-S., Chang, P.-R., and Luh, J.Y.S.1983. Formulation and optimization of cubic polynomial trajectories for industrial robots. IEEE Trans. Automatic Contr. AC-28: 1066-1073.
17.
Lozano-Perez, T.1982. Task planning. In Robot motion: planning and control ., ed. J. M. Brady et al. Cambridge : MIT Press, pp. 473-498.
18.
Luh, J.Y.S., and Lin, C.S.1981. Optimum path planning for mechanical manipulators . J. Dyn. Sys., Meas., Contr. 102:142-151.
19.
Luh, J.Y.S., and Walker, M.W.1977 (New Orleans). Minimum-time along the path for a mechanical arm. Proc. IEEE Conf. Decision and Contr, pp. 755-759.
20.
Rajan, V.T.1985 (Mar. 25-28, St. Louis). Planning of minimum-time trajectories for robot arms. Proc. IEEE Int. Conf. Robotics and Automation, pp. 759-764.
21.
Sahar, G., and Hollerbach, J.M.1985 (Mar. 25-28, St. Louis ). Planning of minimum-time trajectories for robot arms . Proc. IEEE Int. Conf. Robotics and Automation , pp. 751-758.
22.
Scheinman, V., and Roth, B.1985. On the optimal selection and placement of manipulators. In Theory and practice of robots and manipulators. eds. A. Morecki, G. Bianchi, and K. Kedzior. Proc. RoManSy '84: 5th CISM-IFToMM Symp. Cambridge: MIT Press, pp. 39-46.
23.
Shiller, Z., and Dubowsky, S.1985 (Mar. 25-28, St. Louis). On the optimal control of robotic manipulators with actuator and end-effector constraints . Proc. IEEE Conf. Robotics and Automation , pp. 614-620.
24.
Shin, K.G., and McKay, N.D.1983 (San Antonio). An efficient robot arm control under geometric path constraints. Proc. 22nd IEEE Conf. Decision and Contr., pp. 1449-1457.
25.
Shin, K.G., and McKay, N.D.1985a. Minimum-time control of robotic manipulators with geometric path constraints. IEEE Trans. Automatic Contr. AC-30:531-541.
26.
Shin, K.G., and McKay, N.D.1985b (June 19-21, Boston). Selection of near-minimum time geometric paths for robotic manipulators. Proc. Amer. Contr. Conf, pp. 346-355.
27.
Taylor, R.H.1979. Planning and execution of straight-line manipulator trajectories . IBM J. Res. and Devel.23:424-436.
