We have developed an algorithm that automatically detects embeddability of modular robot configurations. Simply put, a given design embeds another design if it can replicate its structure, and therefore simulate its functionality. We introduce a novel graph representation for modular robots, and formalize the notion of embedding through topological and kinematic conditions. Our algorithm involves dynamic programming and maximum cardinality matching, and decides embeddability in O(Nsub * Nsuper2) time, where Nsub and Nsuper are the number of nodes in the subdesign (embedded design) and superdesign (embedding design), respectively.
We demonstrate our algorithm on the SMORES robot and show that we can detect embeddability of complex designs efficiently. When an embedding is detected, our algorithm returns a mapping of subdesign DoF into superdesign DoF, allowing controllers for the subdesign to be used with the superdesign. For example, after we detect that Walker design embeds the Grasper design, we can use controllers designed for the Grasper on the Walker, allowing it to grasp an object.
Code for automatic embedding detection is available open source! A download link will be posted here.
Publication
Y. Mantzouratos∗ , T. Tosun∗ , S. Khanna, and M. Yim, “On embeddability of modular robot designs,” in IEEE International Conference on Robotics and Automation, 2015. (PDF)