| dc.description.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>
|
|
