Document Type: Original Research Paper


Shahid Rajaee Teacher Training University


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. Initially, the formal modeling is accomplished by minimizing the movement problem. At this time, a criterion which 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 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. 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  time using  space.

Graphical Abstract


Main Subjects

[1]     "All On Robots, "[Online]. Available:[Accessed 02 08 2016].

[2]     B. Wanlund‎, "Robots and Automation – SAGE Business Researcher,"[Online].Available: [Accessed 03 07 2016].

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

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

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

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

[7]     K. Shin and N. McKay, "A Dynamic Programming Approach to Trajectory Planning of Robotic," IEEE Transactions on Automatic Control, vol. 31, no. 6, pp. 491-500, 1986.

[8]     Wu‎, ‎Z. Shi‎, ‎Y. Li‎, ‎M. Wu‎, ‎Y. Guan‎, ‎J. Zhang‎, ‎and H. Wei, "Formal Kinematic Analysis of a General 6R Manipulator Using the Screw Theory," Mathematical Problems in Engineering, vol. 2015, p. 7, 2015.

[9]     Y. Kouskoulas‎, ‎A. Platzer‎, ‎and P. Kazanzides, "Formal Methods for Robotic System," Johns Hopkins APL Technical Digest, vol. 32, pp. 490-498, 2013.

[10]  T. Chettibi;H.E. Lehtihet;M. Haddad and S. Hanchi , "Minimum cost trajectory planning for industrial robots," European Journal of Mechanics A/Solids, vol. 23, p. 703–715, 2004.

[11]  J. Choi and E. Amir, "Factor-Guided Motion Planning for a Robot arm," in IEEE/RSJ International Conference on Intelligent Robots and Systems, San Diego, CA, USA, 2007.

[12]  Y. Zhang‎, ‎X. Lv‎, ‎Z. Li‎, ‎Z. Yang‎, ‎and K. Chen, "Repetitive Motion Planning of PA10 Robot Am Subject to Joint Physical Limits and Using LVI-Based Primal–Dual Neural Network," Mechatronics, vol. 18, no. 9, pp. 475-485, 2008.

[13]  H. Ding‎, ‎M. Zhou‎, ‎and O. Stursberg, "Optimal Motion Planning for Robotic Manipulators with Dynamic Obstacles using Mixed-Integer Linear Programming," in Mediterranean Conference on Control & Automation, Makedonia Palace, Thessaloniki, Greece, 2009.

[14]  F. Traversa, C. Ramella, F. Bonani and M. Ventra , "Memcomputing NP-complete Problems in Polynomial Time Using Polynomial Resources and Collective States," Science Advances, vol. 1, no. 6, pp. 1-9, 2015.

[15]     A. Nourollah and M.R. Razzazi, "Minimum Cost Open Chain Reconfiguration," Discrete Applied Mathematics, vol. 159, pp. 1418-1424, 2011.

[16]     A. Nourollah and M.R. Razzazi, "A Linear Time Approximation Algorithm for Ruler Folding Problem," Journal of Universal Computer Science, vol. 14, no. 4, pp. 566-574, 2008.

[17]     A.  Nourollah and M.R. Razzazi, "Near-Optimum Folding for a Reconfigurable," Advanced Robotics, vol. 23, pp. 239-256, 2009.

[18]     R. Connelly  and E. Demaine, "Geometry and Topology of Polygonal Linkages", Discrete and Computational Geometry, pp. 213-235, 2004.

[19]     J. Hopcroft, J. O’Rourke, and S. Whitesides, "On the movement of robot arms in 2-dimensional bounded regions", SIAM J. Computer, vol. 14, no. 2, pp. 315-333, 1985.

[20]     E. Demain and J. O’Rourke, "Geometric and Folding Algorithms", Cambridge, University Press, pp. 9-11,29-31,59-67, 2007.

[21]     A. Lieutier, A. and J. Rameau, "Mechanical linkage design and NP-hardness", Mechanism and Machine Theory, vol. 82, pp. 97-114, 2014.

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

[23]     C. Haasea and S. Kiefer, "The Complexity of the Kth Largest Subset Problem and Related Problems", Information Processing Letters, vol. 116, no. 2, pp. 111-115, 2016.