RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design

Allan Zhao      Jie Xu      Mina Konaković Luković     Josephine Hughes     

Andrew Spielberg      Daniela Rus      Wojciech Matusik
Massachusetts Institute of Technology


We present RoboGrammar, a fully automated approach for generating optimized robot structures to traverse given terrains. In this framework, we represent each robot design as a graph, and use a graph grammar to express possible arrangements of physical robot assemblies. Each robot design can then be expressed as a sequence of grammar rules. Using only a small set of rules our grammar can describe hundreds of thousands of possible robot designs. The construction of the grammar limits the design space to designs that can be fabricated. For a given input terrain, the design space is searched to find the top performing robots and their corresponding controllers. We introduce Graph Heuristic Search – a novel method for efficient search of combinatorial design spaces. In Graph Heuristic Search, we explore the design space while simultaneously learning a function that maps incomplete designs (e.g., nodes in the combinatorial search tree) to the best performance values that can be achieved by expanding these incomplete designs. Graph Heuristic Search prioritizes exploration of the most promising branches of the design space. To test our method we optimize robots for a number of challenging and varied terrains. We demonstrate that RoboGrammar can successfully generate nontrivial robots that are optimized for a single terrain or a combination of terrains.


RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design
Allan Zhao, Jie Xu, Mina Konaković Luković, Josephine Hughes, Andrew Spielberg, Daniela Rus, Wojciech Matusik
ACM Transactions on Graphics 39(6) (Proc. SIGGRAPH Asia 2020)
[Paper]  [Video]  [Code]  [BibTeX]

Video Demo

Related Papers

Multi-Objective Graph Heuristic Search for Terrestrial Robot Design
Jie Xu, Andrew Spielberg, Allan Zhao, Daniela Rus, Wojciech Matusik
IEEE International Conference on Robotics and Automation (ICRA 2021)
[Project Page]