A. Nguyen, L.J. Guibas, and M. Yim, Controlled module density helps reconfiguration planning, Workshop on Algorithmic Foundations of Robotics 2000, 23--36.

Abstract:

In modular reconfigurable systems, individual modules are capable of limited motion due to blocking and connectivity constraints, yet the entire system has a large number of degrees of freedom. The combination of these two facts makes motion planning for such systems exceptionally challenging. In this paper we present two results that shed some light on this problem. First we show that, for a robotic system consisting of hexagonal 2D modules, the absence of a single excluded configuration is sufficient to guarantee the feasibility of the motion planning problem (for any two connected configurations with the same number of modules). We also provide an analysis of the number of steps in which the reconfiguration can be accomplished. Second, we argue that skeletal metamodules, which are scaldinglike structures in 2D built out of normal modules, offer an interesting alternative. General shapes can be built out of these metamodules and, unlike the case for shapes built directly out of modules, a metamodule can collapse and pass through the interior of its neighboring metamodules, thus eliminating all blocking constraints. This tunneling capability makes the motion planning problem easier and allows faster reconfiguration as well, by providing a higher bandwidth conduit, the interior of the shape, through which the modules can ow. The conclusion of our work is that it is worthwhile to study subclasses of shapes that (1) approximate closely arbitrary shapes, while also (2) simplifying significantly the motion planning problem.

Bibtex: 

@inproceedings{ngy-cmdhrp-2000
      , author =       "A. Nguyen, L. J. Guibas, and M. Yim"
      , title =        "Controlled Module Density Helps Reconfiguration Planning"
      , booktitle =    "Proc. 4th International Workshop on Algorithmic Foundations of Robotics"
      , year = 2000
      , pages =        "23--36"
}