A. Nguyen, L.J. Guibas, and M. Yim, Controlled module density helps reconfiguration planning, Workshop on Algorithmic Foundations of Robotics 2000, 23--36.
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.
, 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"