We apply the Fourier transform on the discrete-motion group to the problem of computing the configuration-space obstacles of mobile robots which move among static obstacles, the problem of finding the workspace density of binary manipulators with many actuators, and the problem of determining workspace boundaries of manipulators with continuous-motion actuators. We develop and implement Fourier transforms for the discrete-motion group of the plane. These transforms allow us to apply fast Fourier transform methods to the computation of convolution-like integrals that arise in robot kinematics and motion planning. The results of the implementation are discussed for particular examples.
Get full access to this article
View all access options for this article.
References
1.
Basavaraj, U., and Duffy, J. 1993. End-effector motion capabilities of serial manipulators . Intl. J. Robot. Res.12(2): 132–145 .
2.
Ceccarelli, M., and Vinciguerra, A. 1995. On the workspace of general 4R manipulators . Intl. J. Robot. Res.14(2): 152–160 .
3.
Chirikjian, G. S. 1994 (San Diego, CA). A binary paradigm for robotic manipulators . Proc. of the IEEE Intl. Conf. on Robot. and Automat. Washington, DC: IEEE, pp. 3063–3069 .
4.
Chirikjian, G. S. 1995. Kinematic synthesis of mechanisms and robotic manipulators with binary actuators . ASME J. Mech. Design117(Sept.): 573–580 .
5.
Chirikjian, G. S. 1996. Fredholm integral equations on the Euclidean motion group . Inverse Problems12(Oct.): 579–599 .
6.
Chirikjian, G. S. 1997. Inverse kinematics of binary manipulators using a continuum model . J. Intell. and Robot. Sys.19: 5–22 .
7.
Chirikjian, G. S., and Ebert-Uphoff, I. 1998. Numerical convolution on the Euclidean group with applications to workspace generation . IEEE Trans. Robot. Automat.14(1): 123–136 .
8.
Chirikjian, G. S., and Kyatkin, A. B. Forthcoming. Engineering Applications of Noncommutative Harmonic Analysis. Boca Raton, FL: CRC Press . (Scheduled to appear in 2000.)
9.
Cooley, J. W., and Tukey, J. 1965. An algorithm for the machine calculation of complex Fourier series . Math. Comput.19: 297–301 .
10.
Coppersmith, D., and Winograd, S. 1987. Matrix multiplication via arithmetic progressions. Proc. of the 19th ACM Symp. on the Theory of Computing. New York: ACM , pp. 1–6.
11.
Ebert-Uphoff, I., and Chirikjian, G. S. 1995. Efficient workspace generation for binary manipulators with many actuators . J. Robot. Sys.12(6): 383–400 .
12.
Ebert-Uphoff, I., and Chirikjian, G. S., 1996a (April, Minneapolis, MN). Inverse kinematics of discretely actuated hyper-redundant manipulators using workspace densities . Proc.oftheIEEEIntl.Conf.onRobot.andAutomat. Washington, DC: IEEE, pp. 139–145 .
13.
Ebert-Uphoff, I., and Chirikjian, G. S. 1996b (Aug., Irvine, CA). Discretely actuated manipulator workspace generation by closed-form convolution . Proc. of the 1996 ASME Design Eng. Tech. Conf. and Comp. in Eng. Conf. New York: ASME.
14.
Elliott, D. F., and Rao, K. R. 1982. Fast Transforms: Algorithms, Analyses, Applications. New York: Academic Press .
15.
Gauthier, J. P., Bornard, G., and Sibermann, M. 1991. Motion and pattern analysis: Harmonic analysis on motion groups and their homogeneous spaces . IEEE Trans. Sys. Man Cybernet.21: 159–172 .
16.
Guibas, L., Ramshaw, L., and Stolfi, J. 1983. A kinetic framework for computational geometry. Proc. of the IEEE Symp. on Found. of Comp. Sci. Los Alamitos, CA: IEEE , pp. 100–111.
17.
Gurarie, D. 1992. Symmetry and Laplacians. Introduction to Harmonic Analysis, Group Representations, and Applications. The Netherlands: Elsevier .
18.
Janssen, T. 1973. Crystallographic Groups. New York: North-Holland .
19.
Kavraki, L. 1995. Computation of configuration-space obstacles using the fast Fourier transform . IEEE Trans. Robot. Automat.11: 408–413 .
20.
Koliskor, A. 1986 (Suzdal, former USSR). The l-coordinate approach to the industrial robot’s design . Information Control Problems in Manufacturing Technology: Proc. of the 5th IFAC/IFIP/IMACS/IFORS Conf., pp. 225–232 . (Preprint).
21.
Kwon, S.-J., Youm, Y., and Chung, K. 1994. General algorithm for automatic generation of the workspace for n-link planar redundant manipulators . ASME Trans.116(Sept): 967–969 .
22.
Kyatkin, A. B., and Chirikjian, G. S. 1998a (March 5–8, Houston, TX). Fourier methods on groups: Applications in robot kinematics and motion planning . Proc. of the 3rd Workshop on Algorithmic Found. of Robot.
23.
Kyatkin, A. B., and Chirikjian, G. S. 1998b. Regularization of a nonlinear convolution equation on the Euclidean group . Acta Appl. Math.53(Aug.): 89–123 .
24.
Kyatkin, A. B., and Chirikjian, G. S. 1999a. Synthesis of binary manipulators using the Fourier transform on the Euclidean group . ASME J. Mech. Design121: 9–14 .
25.
Kyatkin, A. B., and Chirikjian, G. S. 1999b. Template matching as a correlation on the motion group . Computer Vision and Image Understanding74(1): 22-35 .
26.
Lees, D. S., and Chirikjian, G. S. 1996a (April, Minneapolis, MN). An efficient method for computing the forward kinematics of binary manipulators . Proc. of the IEEE Intl. Conf. on Robot. and Automat. Washington, DC: IEEE, pp. 1012–1017 .
27.
Lees, D. S., and Chirikjian, G. S. 1996b (April, Minneapolis, MN). A combinatorial approach to trajectory planning for binary manipulators . Proc. of the IEEE Intl. Conf. on Robot. and Automat. Washington, DC: IEEE, pp. 2749–2754 .
28.
Lees, D. S., and Chirikjian, G. S. 1996c (Aug.). An efficient trajectory planning method for binary manipulators . CD-ROM of Proc. of ASME Mechanisms Conf., 96-DETC/MECH-1161 ( 9-9 pp.).
29.
Lozano-Perez, T. 1983. Spatial planning: A configuration space approach . IEEE Trans. Comp.32: 108–120 .
30.
Maslen, D. K. 1993. Fast transforms and sampling for compact groups. PhD dissertation, Dept. of Mathematics, Harvard University, Boston, MA.
31.
McCarthy, J. M. 1991. An Introduction to Theoretical Kinematics. Cambridge, MA: MIT Press .
32.
Murray, R. M., Li, Z., and Sastry, S. S. 1994. A Mathematical Introduction to Robotic Manipulation. Boca Raton, FL: CRC Press .
33.
Newman, W., and Branicky, M. 1991. Real-time configurationspacetransformsforobstacleavoidance . Intl.J.Robot. Res.10: 650–667 .
34.
Orihara, A. 1961. Bessel functions and the Euclidean motion group . Tohoku Math. J.13: 66–71 .
35.
Park, F. C., and Brockett, R. W. 1994. Kinematic dexterity of robotic mechanisms . Intl. J. Robot. Res.13(1): 1–15 .
36.
Pieper, D. L. 1968 (Oct.). The kinematics of manipulators under computer control. PhD dissertation, Stanford University.
37.
Rockmore, D. N. 1994. Efficient computation of Fourier inversion for finite groups . J. Assoc. Comp. Machinery41: 31–66 .
38.
Roth, B., Rastegar, J., and Scheinman, V. 1973. On the design of computer controlled manipulators. First CISM-IFTMM Symp. on Theory and Practice of Robots and Manipulators. pp. 93–113.
39.
Sugiura, M. 1990. Unitary representations and harmonic analysis, 2nd ed. The Netherlands: Elsevier .
40.
Talman, J. 1968. Special Functions. Amsterdam: W. A. Benjamin .
41.
Vilenkin, N. J. 1956. Bessel functions and representations of the group of Euclidean motions . Uspehi Mat. Nauk.11: 69–112 . (In Russian.)
