Self-Reconfiguring Robots (SRR) are composed of many modules that have the ability to autonomously attach and detach, enabling adaptation to a variety of tasks in unknown surroundings. In order to change shape into a particular form, an SRR must plan a sequence of module movements. This reconfiguration problem is challenging because of the many mechanical degrees of freedom and the resultant large number of possible SRR configurations which contribute to a vast and high-dimensional search space. To support the operation of an SRR in a practical environment, reconfiguration planners must satisfy a number of properties including decentralized computation, parallel motion of modules, real-time execution and planning in the native kinematic space of the module mechanism. The ultimate solution would be a general planner that solves reconfigurations of arbitrary module designs in this way. This thesis has taken a step in this direction of generality by developing a reconfiguration planner of the 3R module that is easily instantiable to other module types. The planner is scalable and decentralized, and considers the native kinematics of a module. It demonstrates the ability to coordinate the parallel motion of modules and executes in real-time. The thesis presents both centralized and decentralized implementations of the algorithm along with performance evaluation for several reconfiguration examples, as well as an analysis of achievable SRR reconfigurations.