AbsmeCIn this paper we present generic distributed algorithms for assembling and repairing shapes using modular self-reeonfiguring robots. The algorithms work io the sliding cube model. Each module independently evaluates a set of local rules using diITerent evaluation models. Two methods are used to determine the comctness of the algorithms--a graph analysis technique which can prove the rule set is eo& for specific instances of the algorithm, and a statistical technique which can produce arbitrary bounds on the likelihood that the rule set functions correctly. An extension of the assembly algorithm can be wed to produce arbitrary non-cantilevered convex shapes without holes. The algorithms have been implemented and evaluated in simulation. Current research in self-reconfiguring robots is focused on desi,@g and building hardware, and developing algw rithms coupled to specific hardware. We are interested in developing architecture-independent control and planning algorithms for such systems. In our previous work we describe distributed controllers for two tasks for self-reconfiguring robots: compliant locomotion gaits and splitting a large robot with a given behavior into smaller robots with the same behavior. We demonstrate a methodology for doing this urork using the sliding cube model, in which modules are represented as cubes. Each module can translate on a substrate of identical cubes and make convex and concave transitions on the substrate. The resulting algorithms are provably correct and can be instantiated easily to a wide range of physical platforms such as the Molecule and Crystal robots built in our lab [4] as well as other robot systems [XI, [141, [IS]. Deriving algorithms in this fashion has several advantages: (1) the algorithms are simpler in this abstract model; (2) the algorithms are easier to analyze in the abstract model; (3) the same basic algorithm can be instantiated fox many different hardware types, thus providing a rigorous framework in which to compare different algorithms and hardware systems; (4) the analyses and correctness proofs will be inherited by the instantiated algorithms: and (5) ultimately this framework will lead to a better understanding of the computational problems that arise in self-reconfiguring robot research. In this paper we extend our previous work by demonstrating distributed control algorithms for synthesizing shapes and repairing holes in them. Our approach is based on four ideas: . Use the simplest abstraction for the robot module that fits with existing robot systems (both in shape and actuation) . Develop distributed algorithms in the form of rules that only require local information . Prove correctness of these algorithms with respect to the task . Instantiate these algorithms onto real systems in a way that preserves the algorithmic propenies The use of local rules for compliant locomotion is maightforward, since locomotion does not require precise global shape control. However, it was unclear whether the exclusive use of local rules would be appropriate for assembly tasks in which a specific goal shape is required. Although each module is provided with the goal description, the possible moves are restricted to those permitted by the rule set-the goal description is only used to determine the proximity to the goal shape. As our assembly results demonstrate, it is possible to construct shapes using only local rules for a certain class of configurations. Our hole repair rule set also uses local rules to fill voids in a multilayer configuration of modules. This is accomplished by modules moving into the void and recruiting neighbor modules to follow them. Local sfate in the modules sinulates message passing to neighbor modules which causes them to move toward the hole. For both the assembly and repair algorithms simulation is used to verify algorithmic correctness, either by graph analysis or by generating a statistical bound on the possible number of erroneous sequences of rule applications. 11. RELATED WORK Self-recomiguring robots were fust proposed in [SI. In this planar system modules were heterogeneous and semi-autonomous. Other research focused on homogeneous systems with non-autonomous modules in two dimensions
In REF the sliding cube model was presented to represent latticestyle modules.