An analysis of the Million Module March algorithm applied to the ATRON robotic platform.

摘要

The Million Module March algorithm is a locomotion planning algorithm for self-reconfiguring robotic systems. It was first introduced by Robert Fitch and Zack Butler. It has already been proven to successfully plan movement for a kinematic abstraction whose traits are very different from the kinematic traits of the ATRON system. In this work we further examine this algorithm, and an adaptation of it to the ATRON robotic system.;We examine a two dimensional proof of the reachability of connected configurations of sliding squares, and expand the proof to the three dimensional SlidingCube model of a self-reconfiguring robot. Using this proof, we explore in greater detail the theoretical basis of the Million Module March algorithm.;We then modify the simulator used in the original Million Module March works to simulate the ATRON platform, and run a series of experiments. Ultimately, it is determined that the algorithm does not consistently perform as desired on the ATRON platform. We demonstrate that this performance is due to the inability of ATRON's kinematics to guarantee reachability of connected configurations, and that therefore no similar algorithm of sublinear complexity can be guaranteed to perform as desired.