Million Module March: Scalable Locomotion for Large Self-Reconfiguring Robots

摘要

Self-reconfiguring robots have the potential to explore highly variable terrain, operating as parallel groups or combining to surmount large obstacles. If the modules are at a smaller scale, they may also be able to physically render arbitrary shapes in an interactive way. In order to realize these capabilities, groups with large numbers of modules must be used, and algorithms to control such large groups must be extremely scalable in order to be executed on simple modules. In this work, we present an algorithm for locomotion of lattice-based self-reconfiguring robots that uses constant memory per module with execution times that are sublinear in the number of modules. The algorithm is inspired by reinforcement learning and uses dynamic programming to plan module paths in parallel. We have also developed a novel localized cooperation scheme that allows the modules to move both without disconnecting the system and with small amounts of communication. The combined algorithm is able to direct locomotion over arbitrary obstacles, and due to continuous replanning the goal can be moved at any time to `joystick' the robot over the environment. The formulation of the goal used in the planning also encourages dynamic stability. We have developed both centralized and decentralized implementations in simulation, as well as an implementation for the Superbot system, and present empirical results showing the sublinear nature of our technique.