Document Type : Original Research Paper


Shahid Rajaee Teacher Training University


Background and Objectives: This paper presents a new optimization problem in the field of linkage reconfiguration. This is the problem of minimizing moving parts of a given robot arm for positioning the end effector of the given robot arm at the given target point as well as minimizing the movement of the movable parts.
Methods: Initially, formal modeling is accomplished by minimizing the movement problem. At this time, a criterion called AM (Arithmetic Measure) is introduced, and this criterion is used to quantify the motion of the linkage. Afterward, it is indicated that the presented problem is an NP-Hard problem. Consequently, a greedy heuristic algorithm is presented to minimize the movement of the robot's moving components. After identifying the moving components and the movement of these parts, an algorithm is provided to determine the final configuration of the robot arm.
Results: The results indicate that the discussed model successfully reduced the moving parts of the robot arm. Moreover, the results show that the proposed approach fulfills the goal of minimization of the linkage components. Furthermore, this method leads to erosion of arm, reduces energy consumption and the required parameters and variables for calculating the final configuration of the linkages.
Conclusion: The mentioned algorithm solves the problem by mapping the robot arm with an arbitrary number of links to a robot with a single link or two links. The proposed heuristic approach requires O(n2) time using O(n) space.

©2018 The author(s). This is an open access article distributed under the terms of the Creative Commons Attribution (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, as long as the original authors and source are cited. No permission is required from the authors or the publishers.


Main Subjects

[1] “All on robots,” [Accessed 02 08 2016].

[2] B. Wanlund‎, “Robots and automation – sage business researcher,”.

[3] J. J‎. ‎Craig, “Path Generation," in Introduction To Robotics, First, Ed., Boston, ‎Addison-Wesley Longman Publishing Co., 257-269, 1989.

[4] L. Guibas, "Motion Modeling," in Discrete and Computational Geometry, 2nd ed., Chapman & Hall/CRC,: 1114-1132, 2004.

[5] R. Connelly, J. O’Rourke, “Linkages," in Geometric Folding Algorithms, Cambridge, Cambridge University Press: 9-11, 2007.

[6] S. L. Devadoss, J. O'Rourke, "Configuration Spaces," in Discrete and Computational Geometry, Princeton, University Press: 215-219, 2011.

[7] K. Shin, N. McKay, “A dynamic programming approach to trajectory planning of robotic,” IEEE Transactions on Automatic Control, 31(6): 491-500, 1986.

[8] Wu‎, ‎Z. Shi‎, ‎Y. Li‎, ‎M. Wu‎, ‎Y. Guan‎, ‎J. Zhang‎, ‎H. Wei, “Formal kinematic analysis of a general 6r manipulator using the screw theory,” Mathematical Problems in Engineering, 2015(2): 1-7, 2015.

[9] Y. Kouskoulas‎, ‎A. Platzer‎, ‎P. Kazanzides, “Formal Methods for Robotic System Control Software,” Johns Hopkins APL Technical Digest, 32(2): 490-498, 2013.

[10] T. Chettibi, H. E. Lehtihet, M. Haddad, S. Hanchi, “Minimum cost trajectory planning for industrial robots,” European Journal of Mechanics A/Solids, 23(4): 703–715, 2004.

[11] J. Choi, E. Amir, “Factor-guided motion planning for a robot arm," presented at the IEEE/RSJ International Conference on Intelligent Robots and Systems, San Diego, CA, USA, 2007.

[12] Y. Zhang‎, ‎X. Lv‎, ‎Z. Li‎, ‎Z. Yang‎, ‎K. Chen, “Repetitive motion planning of pa10 robot am subject to joint physical limits and using lvi-based primal–dual neural network,” Mechatronics, 18(9): 475-485, 2008.

[13] H. Ding‎, ‎M. Zhou‎, ‎ O. Stursberg, “Optimal motion planning for robotic manipulators with dynamic obstacles using mixed-integer linear programming,” presented at the Mediterranean Conference on Control & Automation, Makedonia Palace, Thessaloniki, Greece, 2009.

[14] F. L. Traversa, C. Ramella, F. Bonani, M. Ventra, “Memcomputing np-complete problems in polynomial time using polynomial resources and collective states,” Science Advances, 1(6): 1-9, 2015.

[15] A. Nourollah, M. R. Razzazi, “Minimum cost open chain reconfiguration,” Discrete Applied Mathematics, 159: 1418-1424, 2011.

[16] A. Nourollah, M. R. Razzazi, “A linear time approximation algorithm for ruler folding problem,” Journal of Universal Computer Science, 14(4): 566-574, 2008.

[17] A. Nourollah, M. R. Razzazi, “Near-optimum folding for a reconfigurable,” Advanced Robotics, 23(1-2): 239-256, 2009.

[18] R. Connelly, E. Demaine, “Geometry and topology of polygonal linkages,” Discrete and Computational Geometry: 213-235, 2004.

[19] J. Hopcroft, J. O’Rourke, S. Whitesides, “On the movement of robot arms in 2-dimensional bounded regions,” SIAM J. Computer, 14(2): 315-333, 1985.

[20] E. D. Demain, J. O’Rourke, “Geometric and folding algorithms: Linkages, Origami, Polyhedra,”Cambridge, University Press: 9-11, 29-31,59-67, 2007.

[21] A. Lieutier, J. Rameau, “Mechanical linkage design and NP-hardness,” Mechanism and Machine Theory, 82: 97-114, 2014.

[22] G. Panina, D. Siersma, “Motion planning and control of a planar polygonal linkage,” Journal of Symbolic Computation, 88: 5 -20, 2018.

[23] C. Haasea, S. Kiefer, “The complexity of the kth largest subset problem and related problems,” Information Processing Letters, 116(2): 111-115, 2016.


Journal of Electrical and Computer Engineering Innovations (JECEI) welcomes letters to the editor for the post-publication discussions and corrections which allows debate post publication on its site, through the Letters to Editor. Letters pertaining to manuscript published in JECEI should be sent to the editorial office of JECEI within three months of either online publication or before printed publication, except for critiques of original research. Following points are to be considering before sending the letters (comments) to the editor.

[1] Letters that include statements of statistics, facts, research, or theories should include appropriate references, although more than three are discouraged.

[2] Letters that are personal attacks on an author rather than thoughtful criticism of the author’s ideas will not be considered for publication.

[3] Letters can be no more than 300 words in length.

[4] Letter writers should include a statement at the beginning of the letter stating that it is being submitted either for publication or not.

[5] Anonymous letters will not be considered.

[6] Letter writers must include their city and state of residence or work.

[7] Letters will be edited for clarity and length.