LI Tao. Rigid Subchain Detection Algorithm of Mechanism Kinematic Chain and Realization of Recursive Program[J]. International Journal of Plant Engineering and Management, 2020, 25(3): 171-185

Rigid Subchain Detection Algorithm of Mechanism Kinematic Chain and Realization of Recursive Program
LI Tao
Ceramic Research Institute of Light Industry of China, Jiangxi Jingdezhen 333001, China
In the process of kinematic chain type synthesis, it is necessary to solve the problems of isomorphism identification and rigid subchain detection. The problem of rigid subchain detection can be reduced to subgraph isomorphism problem, which belongs to NPC problem. This paper introduces the properties, detection methods, algorithm time complexity and program code of rigid subchain of kinematic chain. The detection codes of rigid subchains with different number of links are different. It is necessary to modify the for-loop nesting times of program code according to the change of the link number, so the code reusability is very low. In view of this, the recursive pseudo code of rigid subchain detection algorithm is proposed for the first time, which makes the program can be directly used for rigid subchain detection of any number of links, improves the reusability of the code, and provides a certain reference for the realization and optimization of computer programs for NPC problems in other disciplines. A rigid subchain detection software of kinematic chain was developed, and the rigid subchain detection process of a 16-link kinematic chain was successfully realized in the software.
Key words:    mechanism kinematic chain    rigid subchain    type synthesis    recursive program   
Received: 2020-06-16     Revised:
DOI: 10.13434/j.cnki.1007-4546.2020.0304
Corresponding author:     Email:
Author description:
PDF(271KB) Free
LI Tao

[1] Luo X H. Prime representation and isomorphism identification of mechanism kinematic chains via the adjacent matrix[J]. Chinese Journal of Mechanical Engineering, 2013,49(5):24-31(in Chinese)
[2] Luo X H, Li T. Topology transformation and isomorphism identification of weighted mixed graphs[J]. Journal of Ceramics, 2014,35(4):419-424
[3] Yan H S, Hwang W M. Atlas of basic rigid chains[C]//Proceedings of 9th Applied Mechanisms Conference. 1985
[4] Tuttle E R. Generation of planar kinematic chains[J]. Mechanism and Machine Theory, 1996,31(6):729-748
[5] Liu C H, Geng D S. New theorems on a rigid subchain[J]. Mechanical Science and Technology, 2000,19(3):350-352(in Chinese)
[6]Song L, Huang Y, Yang J. Distinguishing method for negative sub-chain in model synthesis of planar kinematical chain with multiple joints[J]. Journal of Machine Design, 2004,21(2):46-48(in Chinese)
[7] Lee H J, Yoon Y S. Detection of rigid structure in enumerating basic kinematic chain by sequential removal of binary link string[J]. JSME International Journal. Ser. 3, Vibration, control engineering, engineering for industry, 1992, 35(4):647-651
[8] Lee H J, Yoon Y S. Algorithm to identify the type of degrees of freedom in kinematic chains[J]. JSME International Journal. Ser. C, Dynamics, control, robotics, design and manufacturing, 1996, 39(1):144-148
[9] Ding H, Huang Z, Mu D. Computer-aided structure decomposition theory of kinematic chains and its applications[J]. Mechanism and Machine Theory, 2008,43(12):1596-1609(in Chinese)
[10] Ding H. Loop theory of kinematic chains and its application to isomorphism identification and atlas database establishment[D]. Hebei:YanShan University, 2007(in Chinese)
[11] Ding H, Huang Z. Loop-structure decomposition of kinematic chains, application to rigid sub-chain detection[C]//Asme International Design Engineering Technical Conferences & Computers & Information in Engineering Conference. 2007
[12] Xia S, Ding H, Kecskemethy A. A loop-based approach for rigid subchain identification in general mechanisms[M]//Latest Advances in Robot Kinematics. Springer Netherlands, 2012
[13] Nie S H. Research on planar mechanism type synthesis and innovative scheme designs[D]. Xi'an:Xi'an University of Technology, 2008(in Chinese)