since 05 February 2011 :
View(s): 959 (2 ULiège)
Download(s): 5340 (0 ULiège)
print        
Ali Nourollah & Nooshin Behzadpour

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

(Volume 85 - Année 2016 — Actes de colloques — Special edition)
Article
Open Access

Attached document(s)

original pdf file

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

To cite this 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.ulg.ac.be/0037-9565/index.php?id=5649.

About: Ali Nourollah

Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran

About: Nooshin Behzadpour

Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran