کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
411299 | 679532 | 2014 | 13 صفحه PDF | دانلود رایگان |
• On finding the least (dis)connect actions to reconfigure between arbitrary shapes.
• A proof that the optimal reconfiguration planning problem is NP-complete.
• An algorithm which can generate the optimal reconfiguration sequence.
• An algorithm that finds the near-optimal reconfiguration sequence in polynomial time.
The goal of optimal reconfiguration planning (ORP) is to find a shortest reconfiguration sequence to transform a modular and reconfigurable robot from an arbitrary configuration into another. This paper investigates this challenging problem for chain-type robots based on graph representations and presents a series of theoretical results: (1) a formal proof that this is an NP-complete problem, (2) a reconfiguration planning algorithm called MDCOP which generates the optimal graph-based reconfiguration plan, and (3) another algorithm called GreedyCM which can find a near-optimal solution in polynomial time. Experimental and statistical results demonstrate that the solutions found by GreedyCM are indeed near-optimal and the approach is computationally feasible for large-scale robots.
Journal: Robotics and Autonomous Systems - Volume 62, Issue 7, July 2014, Pages 1047–1059