RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design
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...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery
2025
|
| Online Access: | https://hdl.handle.net/1721.1/158234 |
| _version_ | 1824458173661052928 |
|---|---|
| author | Zhao, Allan Xu, Jie Konakovic-Lukovic, Mina Hughes, Josephine Spielberg, Andrew Rus, Daniela Matusik, Wojciech |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Zhao, Allan Xu, Jie Konakovic-Lukovic, Mina Hughes, Josephine Spielberg, Andrew Rus, Daniela Matusik, Wojciech |
| author_sort | Zhao, Allan |
| collection | MIT |
| description | 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. |
| first_indexed | 2025-02-19T04:21:41Z |
| format | Article |
| id | mit-1721.1/158234 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:21:41Z |
| publishDate | 2025 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1582342025-02-18T18:28:59Z RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design Zhao, Allan Xu, Jie Konakovic-Lukovic, Mina Hughes, Josephine Spielberg, Andrew Rus, Daniela Matusik, Wojciech Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. 2025-02-18T18:28:58Z 2025-02-18T18:28:58Z 2020-11-26 2025-02-01T08:50:41Z Article http://purl.org/eprint/type/JournalArticle 978-1-4503-8107-9 https://hdl.handle.net/1721.1/158234 Zhao, Allan, Xu, Jie, Konakovic-Lukovic, Mina, Hughes, Josephine, Spielberg, Andrew et al. 2020. "RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design." ACM Transactions on Graphics. PUBLISHER_POLICY en https://doi.org/10.1145/3414685.3417831 ACM Transactions on Graphics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The author(s) application/pdf Association for Computing Machinery Association for Computing Machinery |
| spellingShingle | Zhao, Allan Xu, Jie Konakovic-Lukovic, Mina Hughes, Josephine Spielberg, Andrew Rus, Daniela Matusik, Wojciech RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design |
| title | RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design |
| title_full | RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design |
| title_fullStr | RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design |
| title_full_unstemmed | RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design |
| title_short | RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design |
| title_sort | robogrammar graph grammar for terrain optimized robot design |
| url | https://hdl.handle.net/1721.1/158234 |
| work_keys_str_mv | AT zhaoallan robogrammargraphgrammarforterrainoptimizedrobotdesign AT xujie robogrammargraphgrammarforterrainoptimizedrobotdesign AT konakoviclukovicmina robogrammargraphgrammarforterrainoptimizedrobotdesign AT hughesjosephine robogrammargraphgrammarforterrainoptimizedrobotdesign AT spielbergandrew robogrammargraphgrammarforterrainoptimizedrobotdesign AT rusdaniela robogrammargraphgrammarforterrainoptimizedrobotdesign AT matusikwojciech robogrammargraphgrammarforterrainoptimizedrobotdesign |