Sage Journals: Discover world-class research

Abstract

A modular robotic system consists of standardized joint and link units that can be assembled into a number of different kinematic configu rations to meet various task requirements. Owing to typical symme tries in module design, different assembly configurations may lead to robotic structures that are geometrically identical, or isomorphic. This paper focuses on the problem of enumerating the set ofkinemat ically distinct modular robot assembly configurations from a given set of modules. We first consider how to enumerate the nonisomor phic (or geometrically unique) assembly configurations of a modular robotic system. Our scheme is based on a novel representation of a modular robot assembly configuration as an assembly incidence matrix (AIM). Equivalence relations based on symmetries in mod ule geometry and graph isomorphisms are defined on the AIMs. An enumeration algorithm to generate nonisomorphic assembly config urations based on this equivalence relation is proposed. We then present an algorithm to identify the kinematically equivalent robots. The application of these two algorithms will result in the set of kine matically unique assembly configurations. Examples demonstrate that this method is a significant improvement over a brute-force enu meration process.

Get full access to this article

View all access options for this article.

References

Beckenbach, E. 1964. Applied Combinatorial Mathematics New York: Wiley.

Beyer, T. , and Hedetniemi, S. 1980. Constant time generation of rooted trees SIAM J. Comput. 9(4):706-712.

Brockett, R. 1983. Robotic manipulators and the product of exponential formula Proc. MTNS-83 Int. Symp. Beer Sheba, Israel, pp. 120-129.

Chen, I.-M. 1994. Theory and applications of modular reconfigurable robotic systems. Ph.D. Thesis, California Institute of Technology .

Cohen, R. , Lipton, M.G. , Dai, M.Q. , and Benhabib, B. 1992. Conceptual design of a modular robot ASME J. Mech. Design 114:117-125.

Deo, N. 1974. Graph Theory with Applications to Engineering and Computer Science Englewood Cliffs, NJ: Prentice-Hall.

Dinits, E. , and Zaitsev, M. 1977. Algorithm for the generation of nonisomorphic trees Automatic Remote Control 38:554-558.

Dobrjanskyj, L. , and Freudenstein, F. 1967. Some applications of graph theory to the structural analysis of mechanisms ASME J. Eng. Industry 89:153-158.

Fraleigh, J.B. 1982. A First Course in Abstract Algebra Reading, MA: Addison-Wesley.

10.

Fukuda, T. , and Nakagawa, S. 1988. Dynamically reconfigurable robotic system. Proc. IEEE Int. Conf. Robot. and Automat Los Alamitos, CA: IEEE, pp. 1581-1586.

11.

Harary, F. , and Yan, H. 1990. Logical foundations of kinematic chains: Graphs, line graphs, and hypergraphs ASME J. Mech. Design 112:79-83.

12.

Herstein, I. 1975. Topics in Algebra New York: Wiley.

13.

Kozina, A. 1975. Coding and generation of nonisomorphic trees Cybernet. 15:645-651.

14.

Liu, C.L. 1968. Introduction to Combinatorial Mathematics New York: McGraw-Hill.

15.

Miller, W. 1972. Symmetry Groups and Their Applications New York: Academic Press.

16.

Paden, B. , and Sastry, S. 1988. Optimal kinematic design of 6R manipulators Int. J. Robot. Res. 7(2):43-61.

17.

Read, R. 1970. Combinatorial Structures and Their Applications New York: Gordon and Breach.

18.

Schmitz, D. , Khosla, P. , and Kanade, T. 1988. The CMU reconfigurable modular manipulator system Technical Report CMU-RI-TR-88-7, Carnegie Mellon University .

19.

Skiena, S. 1990. Implementing Discrete Mathematics Red-wood City, CA: Addison-Wesley.

20.

Stewart, D. , Volpe, R. , and Khosla, P. 1992. Integration of real-time software control modules for reconfigurable sensor-based systems Proc. IEEE/RSJ Int. Workshop on Intell. Robot. and Sys.

21.

Wells, A. 1994. Grammars for engineering design. Ph.D. Thesis , California Institute of Technology.

22.

Woo, L.S. 1967. Type synthesis of plane linkages ASME J. Eng. Industry 89:159-172.

23.

Wright, R.A. , Richmond, B. , Odlyzko, A. , and McKay, B.D. 1986. Constant time generation of free trees SIAM J. Comput. 15(2):540-548.

24.

Wurst, K. 1986. The conception and construction of a modular robot system Proc. 16th Int. Symp. Industrial Robot. (ISIR), pp. 37-44.

25.

Yan, H.-S. , and Hwang, Y-W. 1991. The specialization of mechanisms Mech. Machine Theory 26(6):541-551.

Enumerating the Non-Isomorphic Assembly Configurations of Modular Robotic Systems

Abstract

Get full access to this article

References