Main Research Questions for Heterogeneous Self-Reconfiguring Robots

To design heterogeneous SR systems, there are significant challenges involved. A fundamental issue is the degree to which modules are different from each other. There are many possible dimensions of heterogeneity, such as size and shape differences, various sensor payloads, or different actuation capabilities.

These differences all impact the main algorithmic problem, which is how to reconfigure when all units are not identical. Present reconfiguration algorithms are based on homogeneity. Heterogeneous reconfiguration planning is similar to the Warehouse problem which is P SPACE-hard in the general case. Beyond the reconfiguration planning problem itself, many other challenges remain in developing applications that capitalize on module specialization. In response to these challenges, we would like to develop an algorithmic basis for heterogeneous self-reconfiguring robots, and to develop software simulations that demonstrate our solutions along with hardware experiments where possible. Below are the four main research questions:
1. Framework for heterogeneity. There are many possible differences between SR modules. In order to reason about heterogeneous systems, a categorization scheme is required that models the various dimensions of heterogeneity. The benefit of such a framework is that algorithms can be developed for classes of systems instead of specific robots. We will identify some primary axes of heterogeneity and build this framework.
2. Reconfiguration algorithms. Reconfiguration planning is the main algorithmic problem in SR systems. Because of homogeneous reconfiguration algorithms are insensitive to module differences, we need to develop a new class of reconfiguration algorithms that are distributed, scalable, and take into account different types of resources, or tradeoffs between resources.
3. Lower bounds for reconfiguration. We propose to determine lower bounds for the complexity of reconfiguration problems under various assumptions about heterogeneity as developed in our framework defined above.
4. Applications. The solution to the heterogeneous reconfiguration problem is significant from a theoretical perspective, it is also interested in developing example applications in simulation and in the physical world.