Developing Scalable Abilities for Self-Reconfigurable Robots

Abstract

<p>The power of modern computer systems is due in no small part to their fantastic ability to adapt to whatever tasks they are charged with. Self-reconfigurable robots seek to provide that flexibility in hardware by building a system out of many individual modules, each with limited functionality, but with the ability to rearrange themselves to modify the shape and structure of the overall robotic system and meet whatever challenges are faced. Various hardware systems have been constructed for reconfigurable robots, and algorithms for them produce a wide variety of modes of locomotion. However, the task of efficiently controlling these complex systems -- possibly with thousands or millions of modules comprising a single robot -- is still not fully solved even after years of prior work on the topic.</p><p> </p><p> In this thesis, we investigate the topic of theoretical control algorithms for lattice-style self-reconfigurable robots. These robots are composed of modules attached to each other in discrete lattice locations and only move by transitioning from one lattice location to another adjacent location. In our work, given the physical limitations of modules in a robot, we show a lower bound for the time to reconfiguration that robot. That is, transition the robot from one connected arrangement of modules to a different connected arrangement. Furthermore, we develop an algorithm with a running time that matches this lower bound both for a specific example reconfiguration problem and for general reconfiguration between any pair of 2D arrangements of modules. Since these algorithms match the demonstrated lower bound, they are optimal given the assumed abilities of the modules in the robot.</p><p> </p><p> In addition to our theoretically optimal reconfiguration algorithms, we also make contributions to the more practical side of of this robotics field with a novel, physically stable control algorithm. The majority of prior theoretical work on control algorithms for self-reconfigurable robots did not consider the effects of gravity upon the robot. The result is that these algorithms often transform a robot into configurations -- arrangements of modules -- which are unstable and would likely break hardware on a real robot with thousands or millions of modules. In this thesis we present an algorithm for locomotion of a self-reconfigurable robot which is always physically stable in the presence of gravity even though we assume limited abilities for the robot's modules to withstand tension or sheer forces. This algorithm is highly scalable, able to be efficiently run on a robot with millions of modules, demonstrates significant speed advantages over prior scalable locomotion algorithms, and is resilient to errors in module actions or message passing. Overall, the contributions of this thesis extend both the theoretical and practical limits of what is possible with control algorithms for self-reconfigurable robots.</p>