Tree-Based Reconfiguration of Metamorphic Robots

Metamorphic robots have gained the attention of many researchers due to their ability to change shape and adapt to various tasks. In order to utilize the versatility of metamorphic systems, we need to be able to find a shape-shifting (reconfiguration) plan efficiently; however, finding these plans is challenging due to the high degree of freedom of modular systems. Reconfiguration algorithms proposed so far either scale poorly with a growing number of modules, impose specific restrictions on modules, or produce plans that are unrealistic outside of zero-gravity environments. This paper presents a new approach to the reconfiguration problem of chain-type metamorphic robots. Our algorithm relies on forming tentacles and using them to transport modules, which allows us to search through a reduced state space by computing many smaller planning instances. As a result, we obtain a heuristic solution that is more scalable than optimal planners, while producing realistic plans that impose no specific module requirements.