MIT Machine Learning Uses ‘Graph Grammar’ to Automate and Optimize Robot Design – InApps 2022

Over the last few years, we’ve seen quite a few interesting projects emerge from the field of robotics. From multifunctional robots that shapeshift by melting their own joints, to multifluidic soft robots and nano-scale DNA robots, it’s seemingly possible to create some kind of robotic solution for almost any situation. Of course, some experts have pointed out that these hyper-customized approaches can result in a kind of piecemeal fragmentation in the evolution of robotics: different teams are “re-inventing the wheel” each time a robot is designed, creating divergent kinds of hardware and software. In response, some are suggesting using alternatives like modular robotic systems, or even a broader open source approach to designing robots.

Grammar structural “rules” represented by letters, and the actual robotic components they represent.

Over at MIT, researchers are proposing yet another possible course of action: using a kind of “robot grammar” system to create robots that can be automatically optimized to the needs of the moment, and for different kinds of terrain.

Dubbed RoboGrammar, the system is based on what’s called graph grammar, a technique borrowed from computer science where a series of related objects — or “graph” — are algorithmically transformed into new “graphs”, thus generating new abstractions that adhere to a set of transformational rules, much like how grammar rules affect the way human languages are structured. Graph grammars essentially provide rule-based mechanisms for generating, manipulating and analyzing such structures.

“RoboGrammar is a framework for finding specialized robot designs for different terrains,” explained Allan Zhao, a Ph.D. student who is part of Professor Wojciech Matusik’s group in MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), and lead author of the paper. “We express the designs using a ‘graph grammar’, which restricts how robot parts can be put together and helps avoid nonsensical designs.”

Flexible and Creative Grammar System

The idea behind RoboGrammar is to leverage machine learning algorithms to find more innovative robot designs, and to automatically optimize them for whatever terrain they are needed in. But to make the process more efficient, the number of possible outcomes and arrangements is constrained by a small set of rules. For example, a grammar-based system can stipulate the leg segments of a robot prototype should be linked up by joints, not to an arm or another leg.

Accordin” to the team, the RoboGrammar system was initially inspired by the forms of arthropods — segmented organisms with exoskeletons, which include specimens like insects, spiders, and lobsters. Evolutionarily speaking, these organisms are some of the most successful on Earth, as they make up more than 80 percent of known animal species. So the notion here was to adapt some of nature’s best design ideas, while still allowing for novel schemes to emerge, rather than wasting time on developing prototypes that might not prove feasible in the long run.

“Other existing systems for robot design do not constrain the way the parts can be put together, meaning that very few of the possible combinations will work,” said Zhao. “The graph grammar helps reduce the number of combinations that need to be searched over while still leaving room for creativity.”

Narrowing Down the Possibilities

In particular, the team’s system uses what they call “graph heuristic search” — a new method for efficiently searching through a design space populated with many different possible combinations, and prioritizes the exploration of the most promising options, while also mapping out any incomplete designs, and the best performance levels that might be achieved by further developing them.

“Our graph heuristic search is inspired by the A-star algorithm [one of the best techniques used in path-finding and graph traversals], with some ideas borrowed from reinforcement learning,” explained Zhao. “We use a learned heuristic function based on a graph neural network to decide which design to try in each iteration. After getting the performance of a design, we update the heuristic function using backpropagation. The idea is that the heuristic function will become more accurate over time, and narrow down the search to more promising branches of the design space.”

Overall, the RoboGrammar system first defines the problem — noting what kind of terrain is present, how slippery it is and so on — and then generates possible robot designs, before selecting the best solutions. A human user can also input other factors into the process, like specifying how many robotic components like arms, legs, wheels and motors are available. In doing so, the system can then come up with thousands of possibilities, which human users can then choose to develop further.

But a robot doesn’t move on its own; it also needs a system to control it. So in addition, the team also used an algorithm called model predictive control, which tailors the control system to each robot’s particular form, thus rapidly optimizing the control system toward a stable, forward gait, no matter its shape.

To test out their system, the team generated simulated robots, and found that in general, the best design solutions came in quadruped form. “This didn’t really come as a surprise, but many of the best designs ended up having four legs in the end. Perhaps four legs offer a good balance between stability and weight,” Zhao surmised.

The team’s intention is to provide RoboGrammar as a tool to help robot engineers streamline their design process, but there could be other potential applications.

“It could be useful in the early stages of designing a robot, when trying to decide on a general form,” added Zhao. “But it could also be used to quickly populate virtual worlds with many different creatures. The results so far are only based on simulation, and translating them to the real world would be a logical next step, which we are currently working on. The grammar could also be expanded to include an even greater variety of forms, such as sea creatures.”

One prototype generated by RoboGrammar’s system, and two graphs showing how several different prototypes perform in two terrains.

Read the team’s paper here, or download the code on GitHub.