Motion planning for a self-reconfigurable robot
involves coordinating the movement and connectivity of each of
its homogeneous modules. Reconfiguration occurs when the shape
of the robot changes from some initial configuration to a target
configuration. Finding an optimal solution to reconfiguration
problems involves searching the space of possible robot configurations.
Because this space grows exponentially with the number
of modules, optimal planning becomes intractable. We propose
a hierarchical planning approach that computes heuristic global
reconfiguration strategies efficiently. Our approach consists of
a base planner that computes an optimal solution for a few
modules and a hierarchical planner that recursively calls this
base planner at each level of the hierarchy to ultimately compute
a global suboptimal solution. We present results from a prototype
implementation of the method that efficiently plans for selfreconfigurable
robots with several thousand modules. We also
discuss tradeoffs and performance issues including scalability,
heuristic metrics and plan optimality.