Near-Optimum Folding for a Reconfigurable Snake-Like Robot

摘要

To improve reachability of a snake-like robot depending on the problem, the links of the robot need to be resizable. In such a case folding links of the robot help to better plan obstacle avoidance. Optimum folding of the robot is the aim of our paper. We introduce a practical idea to construct reconfigurable and resizable snake robots which can be folded and an approximation algorithm to find near-optimum folding for the robot. Since an open chain is an abstract model of a snake-like robot, folding algorithms for the proposed robot are given in terms of an open chain. Ruler folding is a well-known NP-Complete problem. It considers folding of an n-link open chain linkage to the minimum length. The best previously known approximation algorithm for this problem has been developed by Hopcroft et al. They achieved the upper bound of 2m 1 for the length of the folded chain in all cases, where m 1 is the length of the longest link of the given chain. Already there are no any algorithms for open chain folding which guarante that the folded length of the open chain is less than 2m 1. In this paper, we introduce an approximation algorithm which runs in O (n log n) using O (n) space. We introduce a function for the upper bound of the folded chain which depends to the lengths of all links in the given chain. Our experimental results show that for more than 95% of the problem instances we can achieve the same results in O (n) time. Using our folding algorithm, we can design the length of each link in an open chain to get x · m 1 folded length where 1 < x < 2 is given and m 1 is the length of the longest link of the chain. We introduce how to design a snake-like robot for which it can be folded in the given interval.