Bulletin de la Société Royale des Sciences de Liège Bulletin de la Société Royale des Sciences de Liège -  Volume 85 - Année 2016  Actes de colloques  Special edition 

Introducing a New NP-Hard Problem Regarding an Open Chain Linkage Using a New Greedy Method

Ali Nourollah
Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
Nooshin Behzadpour
Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran

Abstract

Linkages exhibit numerous applications especially in modelling robot arms. Until now, NP-Complete and PSPACE-Hard problems have been introduced within the linkage context. The main subject of this paper is to introduce a new NP-Hard problem regarding movement of open chain linkages. The objective of this problem is to minimize the moving components of the linkage and their related movement impact, in a way that the end effector is ultimately placed at the target point. For this purpose, first, the problem is formalized and its NP-Hard condition is proved using reduction of sum of subset problem. A greedy algorithm with the time complexity of O(n2) and space complexity of O(n) is proposed for solving the problem, and computation results from implementing the algorithm are compared with the optimized results. This comparison demonstrates the efficiency and capability of the proposed algorithm.

Keywords : Greedy Method, NP-Hard problems, open chain linkage, reachability problem, reconfiguration problem

Pour citer cet article

Ali Nourollah & Nooshin Behzadpour, «Introducing a New NP-Hard Problem Regarding an Open Chain Linkage Using a New Greedy Method», Bulletin de la Société Royale des Sciences de Liège [En ligne], Volume 85 - Année 2016, Actes de colloques, Special edition, 766 - 777 URL : https://popups.uliege.be/0037-9565/index.php?id=5649.