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.


Main Subjects

[1] “All on robots,” [Online]. Available: http://www. types-of-robots.html. [Accessed 02 08 2016].

[2] B. Wanlund‎, “Robots and automation – sage business researcher,” [Online]. Available: http://businessr 20150209/ robots-and-automation. [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, no. 2, pp. 1-7, 2015.

[9] Y. Kouskoulas‎, ‎A. Platzer‎, ‎and P. Kazanzides, “Formal Methods for Robotic System Control Software,” Johns Hopkins APL Technical Digest, vol. 32, no. 2, 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, no. 4, p. 703–715, 2004.

[11] J. Choi and 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‎, ‎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,” presented at the Mediterranean Conference on Control & Automation, Makedonia Palace, Thessaloniki, Greece, 2009.

[14] 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] Nourollah and M. R. Razzazi, “Minimum cost open chain reconfiguration,” Discrete Applied Mathematics, vol. 159, pp. 1418-1424, 2011.

[16] 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] Nourollah and M. R. Razzazi, “Near-optimum folding for a reconfigurable,” Advanced Robotics, vol. 23, no. 1-2, 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] Demain and J. O’Rourke, “Geometric and folding algorithms : Linkages, Origami, Polyhedra,”Cambridge, University Press, , 2007, pp. 9-11,29-31,59-67.

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

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

[23] 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.