- Home
- 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
View(s): 957 (2 ULiège)
Download(s): 5339 (0 ULiège)
Introducing a New NP-Hard Problem Regarding an Open Chain Linkage Using a New Greedy Method
Attached document(s)
original pdf fileAbstract
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.