[Paper Notes] RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design
Published:
This post supports English / 中文 switching via the site language toggle in the top navigation.
TL;DR
RoboGrammar automates rigid robot design for a specified terrain. Its pipeline has three layers: a recursive graph grammar generates structurally valid morphologies from available components; model predictive control (MPC) finds a locomotion controller for each completed design; and Graph Heuristic Search (GHS) learns which partial grammar derivations are likely to lead to high-performing robots.
The graph grammar is more than a convenient encoding. It excludes large regions of nonsensical design space, enforces bilateral limb symmetry and valid component connectivity, and makes every robot a sequence of production-rule applications. GHS then assigns value to incomplete designs. A GNN predicts the best reward reachable from each partial graph, allowing search to prioritize promising branches before paying for an expensive dynamics-and-MPC evaluation.
Across flat ground, low-friction ice, ridges, gaps, stairs, and wall obstacles, different bodies emerge: short low-inertia legs for speed, long reaching legs for gaps, articulated arms for ice, and flexible bodies for turning. GHS finds stronger designs in 2,000 evaluations than MCTS and random search find in 5,000. The main limitations are equally important: the grammar encodes a human-designed arthropod prior, the controller favors stable periodic gaits, continuous dimensions are fixed, and fabricability is checked only at the component-layout level without physical deployment.
Paper Info
The paper is “RoboGrammar: Graph Grammar for Terrain-Optimized Robot Design” by Allan Zhao, Jie Xu, Mina Konaković-Luković, Josephine Hughes, Andrew Spielberg, Daniela Rus, and Wojciech Matusik from MIT. It appeared in ACM Transactions on Graphics 39(6), Proceedings of SIGGRAPH Asia 2020.
- Project page: people.csail.mit.edu/jiex/papers/robogrammar
- Paper: robogrammar.pdf
- Code: github.com/allanzhao/RoboGrammar
1. The Design Problem
RoboGrammar receives:
- a library of physical primitives such as body links, limb links, joints, connectors, and wheels;
- one or more terrains;
- a locomotion reward.
It returns a robot morphology and a controller optimized for those conditions. Conceptually,
[ (G^\star,U^\star) = \arg\max_{G\in\mathcal L(\mathcal G),\,U} J(G,U;\mathcal T), ]
where (\mathcal G) is the graph grammar, (\mathcal L(\mathcal G)) is the set of complete robot graphs it can generate, (U) is a control sequence, and (\mathcal T) is the terrain.
The difficulty comes from two nested combinatorial problems. A short sequence of grammar rules can branch into hundreds of thousands of bodies. Every completed body then needs a good controller before its morphology can be judged. Most computation is spent on control synthesis and simulation, so search efficiency matters more than generating candidates quickly.
RoboGrammar organizes this process into:
[ \text{components + terrain} \rightarrow \text{grammar-constrained design tree} \rightarrow \text{GHS candidate selection} \rightarrow \text{MPC evaluation} \rightarrow \text{best morphology + gait}. ]
2. Robot Structure as a Graph
A robot is represented as a directed acyclic graph. Nodes correspond to physically realizable components or temporary grammar symbols. Edges express component connectivity.
The grammar assumes an arthropod-like organization: a sequence of body segments, optional head and tail, and limb pairs attached to body segments. Legs are bilaterally symmetric. One graph branch represents both members of a leg pair, compressing repetition and simplifying production rules. Head and tail appendages may be asymmetric.
Once derivation finishes, the robot graph is expanded into a kinematic tree for simulation. A node may produce multiple physical components because a single grammar branch can encode a symmetric pair. Tree structure supports efficient articulated-body dynamics.
This representation builds a strong inductive bias into the design language. It guarantees a meaningful root-to-limb hierarchy and generates animal-like robots efficiently. It also excludes robots that cannot be expressed through that hierarchy.
3. The Recursive Graph Grammar
The grammar is defined as
[ \mathcal G=(N,T,A,R,S), ]
where:
- (N) contains non-terminal symbols used during construction;
- (T) contains terminal symbols corresponding to physical components;
- (A) stores component attributes such as joint angle and rotation range;
- (R) is the set of production rules;
- (S) is the start symbol.
A rule has the form
[ Q\rightarrow W, ]
with (Q\in N) and (W) a replacement subgraph. A graph containing non-terminals is a partial design. A graph containing only terminal symbols is a complete design that can be converted to a physical simulation model.
Rules fall into two categories.
Structural Rules
Structural rules create body and limb topology. They initialize and extend the torso, attach symmetric limb pairs, add limb segments, or leave a body segment without legs. Recursion lets a compact rule set generate robots with many body segments and appendages.
Component Rules
Component rules replace abstract symbols with specific body links, limb links, rigid joints, roll joints, twist joints, knees, elbows, connectors, mounts, or wheels. Joint terminals carry attributes such as initial angle (\theta_i) and allowed rotation range (\theta_r).
The experiment caps derivations at 40 rule applications. Without that bound, recursive rules allow an unbounded number of segments. Increasing the cap expands morphological complexity and search cost together.
4. How Grammar Encodes Fabricability
Unconstrained graph mutation produces many disconnected, self-intersecting, or mechanically meaningless structures. RoboGrammar moves feasibility upstream into the generative language:
- terminal nodes correspond to available physical parts;
- production rules specify legal connections;
- symmetric legs are created as matched pairs;
- each body segment receives at most one leg pair;
- completed robots convert to kinematic trees;
- initial self-collisions are detected and rejected before evaluation.
“Fabricable” here means that the simulated configuration can be assembled from the allowed components with valid connectivity. It does not guarantee actuator wiring, structural strength, collision-free motion over a full trajectory, manufacturing tolerance, or sim-to-real agreement.
The important methodological point is that the grammar converts hard constraints into syntax. Search spends its evaluations inside a design language already shaped by engineering knowledge.
5. Simulation and Control with MPPI
Completed robots are simulated as articulated rigid bodies using Featherstone-style recursive dynamics in Bullet Physics. The simulation includes terrain contact, self-collision, position-controlled joints, and velocity-controlled wheels. Joint torque is limited to 1 Nm.
For each morphology, RoboGrammar uses a sampling-based MPC method based on Model Predictive Path Integral control (MPPI). It maintains an action horizon
[ U=[u_0,u_1,\dots,u_{H-1}] ]
and samples (K) perturbed candidates (U_k). Each candidate is rolled out in a separate simulator. Returns (r_k) produce exponential weights
[ w_k=\exp\bigl(\kappa(r_k-\max_l r_l)\bigr), ]
and the horizon is updated by the weighted average
[ U \leftarrow \frac{\sum_{k=1}^{K}w_kU_k} {\sum_{k=1}^{K}w_k}. ]
The first command is committed, the window shifts, and the procedure repeats. The paper uses 64 samples, a default horizon of 16 control intervals, and a simulation timestep of (1/240) s.
6. Sampling for Periodic but Reactive Gaits
Half of MPPI’s samples are warm-start samples centered on the previously optimized action sequence shifted forward. They preserve local continuity.
The other half are history samples. Their mean repeats a recent block of control inputs, explicitly biasing search toward periodic gait structure. The repeated history length varies from half to all of the MPC horizon.
This mixture captures two locomotion needs. Periodicity makes walking efficient, while receding-horizon replanning lets the controller respond to steps, gaps, and walls. The upward-step example begins with a cyclic trot and switches to an ad hoc motion for higher steps.
The same sampling bias also limits the result. Highly dynamic or deliberately aperiodic gaits are unlikely to be discovered, especially under low motor torque and high damping.
7. Terrain-Conditioned Reward
The same reward is used across terrains:
[ r(t) = \mathbf w_x\cdot\mathbf d_x(t) + \mathbf w_y\cdot\mathbf d_y(t) + \mathbf w_v\cdot\mathbf v(t). ]
Here, (\mathbf d_x) and (\mathbf d_y) are the robot base’s forward and upward axes in world coordinates, and (\mathbf v) is base velocity. The first two terms reward preservation of the initial orientation; the last rewards forward progress. Terrain changes the dynamics and feasible path while the objective stays fixed.
The six terrains are:
- Flat: high-friction, obstacle-free ground.
- Frozen lake: a low-friction surface with coefficient 0.05.
- Ridged: repeated hurdles that reward climbing or jumping.
- Wall: a slalom of tall barriers that requires fast turning.
- Gap: platforms separated by increasingly wide gaps.
- Upward stepped: stairs with varying heights.
Because reward is held constant, morphology differences can be attributed to terrain demands instead of task-specific scoring changes.
8. Graph Heuristic Search: The Key Algorithm
Grammar restricts the language of designs, but the derivation tree remains too large for exhaustive search. GHS learns a value function on partial robot graphs:
[ V_\theta(g) \approx \max_{d\in\operatorname{Complete}(g)}J(d), ]
where (\operatorname{Complete}(g)) contains all completed robots reachable from partial design (g). The heuristic estimates the best performance hidden below a branch, not the immediate quality of an unfinished body.
GHS interleaves three phases.
8.1 Design Phase
Starting from (S), rules are applied until a complete robot appears. At each partial graph (s_l), an (\epsilon)-greedy decision either picks a random valid rule or selects
[ a_{l+1} = \arg\max_a V_\theta(P(s_l,a)), ]
where (P(s,a)) applies rule (a). Sixteen complete candidates are sampled in each iteration. A second (\epsilon)-greedy decision chooses which one receives the expensive MPC evaluation.
The exploration rate decays from 1.0 to 0.1. Early search collects diverse graphs while the heuristic is inaccurate; later search exploits its predictions.
8.2 Evaluation Phase
Only one candidate per iteration is evaluated. MPPI supplies its gait and average reward. Because MPC is stochastic, a design’s stored score is the best reward observed across repeated evaluations.
Every partial ancestor on the chosen derivation path receives a target equal to the maximum reward of any completed descendant seen so far:
[ \widehat V(g) \leftarrow \max\bigl(\widehat V(g),r_{\text{descendant}}\bigr). ]
8.3 Learning Phase
The heuristic minimizes
[ \mathcal L(\theta) = \sum_{g\in\mathcal B} \left| V_\theta(g)-\widehat V(g) \right|_2^2 ]
over minibatches of partial and complete graphs. The paper runs 25 Adam steps after each design evaluation.
9. Why a GNN Is the Natural Heuristic
Partial robots vary in size and topology, making fixed-size MLP inputs awkward. RoboGrammar uses a DiffPool-style graph neural network. Node features encode component geometry, initial transform, joint rotation and servo properties, or one-hot non-terminal identity.
GraphSAGE layers aggregate local structure; DiffPool hierarchically reduces graph cardinality; final pooling produces a scalar performance estimate. The architecture is invariant to node ordering, so isomorphic robot graphs receive the same prediction without explicit permutation handling.
The correspondence between representation and model is strong: grammar builds a robot hierarchically, and DiffPool learns hierarchical graph summaries. The GNN can also evaluate incomplete graphs containing non-terminals, which is essential for branch prioritization.
10. Comparison with MCTS and Random Search
The paper implements two baselines.
Random search repeatedly samples valid rule sequences and evaluates the resulting robot.
MCTS represents partial designs as search-tree nodes, selects edges with a UCT criterion, randomly completes a selected partial design, evaluates it with MPC, and backs up visit counts and maximum reward. The implementation handles transpositions, uses UCT-RAVE, and blocks partial designs after repeated failures to sample a simulable completion.
On flat, frozen-lake, ridged, and wall terrains, GHS consistently finds higher-reward robots. GHS uses 2,000 iterations, while MCTS and random search receive 5,000. This matters because each MPC evaluation takes roughly 40–60 seconds and dominates runtime.
A 2,000-iteration GHS run takes about 31 hours on a 32-core Google Cloud instance; approximately 20 hours are evaluation. The learned heuristic earns its value by reducing how many completed robots need this expensive test.
11. Terrain Produces Specialized Bodies
The optimized morphologies reveal how environment shapes mechanical strategy.
On flat terrain, successful robots often have short legs spaced far apart. Low limb inertia supports fast cycling, and obstacle clearance is unnecessary.
On frozen lake, compact, highly articulated arms maintain ground contact while part of the body slides. The body exploits low friction instead of merely fighting it.
On ridged terrain, long limbs swing upward to clear obstacles. Quadrupeds dominate, with some tripedal solutions using the body as a third contact.
On gap terrain, long limbs are oriented for forward reach. Joints that produce horizontal motion become more common than those emphasizing vertical lift.
On wall terrain, a long articulated body supports sharp turns around barriers. MPC pairs morphology with an exaggerated turning gait.
These are co-design results: the terrain selects a body, and MPPI discovers how to use that body.
12. Multi-Terrain Design and Pareto Structure
RoboGrammar also evaluates 20,000 randomly sampled designs on combinations of flat, ridged, and wall terrains. Pareto fronts contain multiple morphologies with different trade-offs. No single body dominates every terrain pair.
This result has two implications. First, the grammar is expressive enough to generate diverse high-performing strategies. Second, “optimal robot” is incomplete without specifying the deployment distribution. A specialized body may win on one terrain while a more moderate morphology offers better multi-terrain robustness.
The paper uses random search for Pareto analysis to avoid steering samples toward one objective. The experiment studies the design language’s coverage separately from GHS’s single-objective search bias.
13. Search Bias and Grammar Bias
Every layer introduces a prior:
- The grammar favors symmetric arthropod-like bodies.
- The 40-step derivation cap limits complexity.
- GHS focuses on branches that resemble previously successful graphs.
- MCTS prefers shallower derivations because it expands the tree locally.
- MPPI favors stable, approximately periodic motion.
- The reward favors forward velocity and upright orientation.
These biases make the problem tractable. They also determine what cannot emerge. The paper’s design-length analysis shows the effect directly: among the best 100 flat-terrain designs, GHS averages 25.0 derivation steps, MCTS 20.9, and random search 23.4.
Automated design is therefore never prior-free. RoboGrammar’s contribution is to make several useful priors explicit and programmable.
14. Strengths and Limitations
Strengths. RoboGrammar joins a meaningful design language, efficient learned search, dynamics simulation, and controller synthesis in one end-to-end system. The grammar prevents many invalid candidates before evaluation and can be edited when component inventory changes. GHS learns from both complete and partial graphs and substantially improves sample efficiency. Terrain-specific and Pareto results demonstrate genuine morphological diversity.
Limitations. The demonstrated grammar covers bilaterally symmetric, arthropod-inspired rigid robots. New domains require expert-authored rules. Link dimensions and other continuous design variables are fixed; attribute grammars or post-optimization would be needed to tune them. The control scheme is biased toward stable periodic locomotion and may miss dynamic gaits.
Physical fabricability is asserted at the component-and-connectivity level. The paper does not build the generated robots or address sim-to-real calibration, actuator wiring, structural load, power, sensing, or manufacturing tolerance. Search remains expensive even with GHS, and the learned heuristic is not admissible, so it offers no guarantee of finding a global optimum.
15. My Takeaway
RoboGrammar’s deepest idea is to treat robot design as program synthesis over a mechanical language. A morphology is a derivation, a partial morphology is a program prefix, and GHS learns which prefixes are worth completing. MPC supplies the expensive execution test.
This decomposition remains relevant beyond the specific 2020 system. Modern extensions could learn the grammar itself, use graph foundation models as heuristics, amortize controller learning across designs, optimize discrete topology together with continuous dimensions, or add fabrication and sim-to-real constraints to the syntax.
The paper also offers a useful lesson about automation: creativity and constraints are compatible. The grammar removes nonsensical regions of design space, which gives the search enough efficiency to discover morphology that still looks surprising. Good generative design starts by choosing a language in which useful novelty is easy to express.