Asymptotically Optimal Kinodynamic Motion Planning for Self-Reconfigurable Robots

Date: October 2, 2006 at 1pm
Speaker: Sam Slee
Self-reconfigurable robots are composed of many individual modules that can autonomously move to transform the shape and structure of the robot. In this talk we present a kinodynamically optimal algorithm for the following ``$x$-axis to $y$-axis" reconfiguration problem: given a horizontal row of $n$ modules, reconfigure that collection into a vertical column of $n$ modules. Prior work on self-reconfigurable (SR) robots assumed a constant velocity bound on module movement and so required time linear in $n$ to solve this problem. In this talk we show the problem can be solved in $\Theta(\sqrt n)$ movement time.