Applying 3D-MBP to Self-Repair of SR Robot

The problem of self-repair is to restore functionality to a SR robot, without outside intervention, in response to module failure. Our strategy is to detect the failure, eject the failed module from the system, and replace it with a spare built into the robot’s structure. Path planning in this problem is based on finding rectilinear paths that minimize the number of turns. Our 3D-MBP algorithm addresses this issue, and in this section we describe how 3D-MBP is applied to the self-repair application. This technique is also a type of reconfiguration algorithm for systems with limited heterogeneity.

The Crystal’s motion planning based on virtual module relocation reduces to finding a rectilinear path through the robot structure. Each segment of the path can be executed in constant time, assuming no failed modules, so an efficient motion plan requires a rectilinear path of minimum bends. Replacing a failed module (filling a “hole” in the structure) can be solved using virtual module relocation. To eject a failed module, this planning technique can not be used directly since here a particular module must be actually pushed (or pulled) to a position on the surface of the robot. However, pushing gaits to move the failed module, also exhibit the property that turns are more expensive than straight line motion. To find path of a minimum-bend is therefore useful in both steps.

An MBP problem is constructed by modeling the source and destination points in module coordinates, and holes and concavities This motion planning technique leads to a 2D self-repair solution, and easily extends to 3D given an efficient shortest path algorithm. A 3D rectilinear path is able to be decomposed into a sequence of 2D turns (not all of which are in the same plane). Therefore, given a 3D rectilinear path, a motion plan can be constructed by iterating the appropriate module gait over each path segment. Note that pushing gaits require a minimum amount of supporting structure, but we can build this into the path planning problem by growing the obstacles (holes in the structure and boundaries) by the required amount. This ensures that any path returned by the algorithm is feasible.