Abstract
A self-reconfigurable modular robotic system is a collection of
homogeneous, independently controlled modules that can connect,
disconnect, and move around adjacent modules. These systems are capable
of reassembling themselves to change their shape to a desired target
configuration. Reconfiguration occurs for purposes of locomotion,
manipulation or for the creation of static structures. Motion planning
for such systems is interesting and challenging as it involves
coordinating the movement of a possibly large number of modules while
enforcing motion constraints imposed due to their physical design.
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.